Построение AST во время парсинга LR

Я написал синтаксический анализатор LR(1), который может успешно анализировать строки на языке моей грамматики в конкретное синтаксическое дерево, но сейчас я пытаюсь построить абстрактное синтаксическое дерево.

Я использую схему наследования для своих узлов AST:

struct ASTNode {
    virtual Type typeCheck() = 0;
}

struct IDNode : public ASTNode {
    string name;
    ...
}

struct INTNode : public ASTNode {
    int value;
    ...
}

struct BOPNode : public ASTNode {
    ASTNode *pLeft;
    ASTNode *pRight;
    ...
}

struct Add_BOPNode : public BOPNode {
    ...
}

struct ParamNode : public ASTNode {
    string name;
    ASTNode *pTypeSpecifier;
    ...
}

struct ParamListNode : public ASTNode {
    vector<ParamNode*> params;
    ...
}

struct FuncDec : public ASTNode {
    string functionName;
    ASTNode *pFunctionBody;
    ASTNode *pReturnType;
    ASTNode *pParams;
    ...
}

Когда я выполняю сокращение в парсере LR(1), я генерирую новый узел в зависимости от правила, которое использовалось для сокращения. Это довольно просто для большинства узлов, но я не уверен в правильном способе реализации узла, содержащего список других узлов.

Используя ParamListNode выше в качестве примера:

struct stack_item {
    int state;
    int token;
    string data;
    ASTNode *node;
};

/// rule = the number of the rule being reduced on
/// rhs = the items on the right-hand side of the rule

ASTNode* makeNode(int rule, vector<stack_item> rhs) {
    switch(rule) {
        /// <expr> ::= <expr> '+' <term>
        case 1: return new Add_BOPNode(rhs[0].node, rhs[2].node);

        /// <param> ::= IDENT(data) ':' <type>
        case 2: return new ParamNode(rhs[0].data, rhs[2].node);

        /// <param_list> ::= <param>
        case 3: return new ParamList(rhs[0].node);

        /// <param_list> ::= <param_list> ',' <param>
        case 4: {
            auto list = dynamic_cast<ParamListNode*>(rhs[0].node);
            list->params.push_back(rhs[2].node);
            return list;
        }

        ...
    }
}

Поскольку для создания узла требуется возврат подкласса ASTNode, я должен создать подкласс, который заключает в себе вектор‹> с каждым подузлом. Однако, поскольку не каждый узел должен быть структурой списка, мне нужно выполнить dynamic_cast‹> к подклассу, прежде чем я смогу получить доступ к внутреннему списку.

Я чувствую, что должен быть более чистый способ обработки списка подузлов без необходимости полагаться на dynamic_cast‹>.

Еще вопрос по узлу FuncDec. У него есть pParams, который должен быть ParamList (или vector‹Param*> напрямую), но для этого мне пришлось бы dynamic_cast‹> входящий ASTNode в узел ParamList или Param. Опять же, я чувствую, что должен быть способ не использовать dynamic_cast‹>, но я не могу его придумать.

Кроме того, если у вас есть какие-либо другие предложения о том, как я могу лучше структурировать или реализовать что-либо, я буду очень признателен :)


c++ parsing abstract-syntax-tree lr
person Sarathi    schedule 19.02.2016    source источник
comment
Как выглядит stack_item?   -  person Simon Kraemer    schedule 19.02.2016
comment
@SimonKraemer Я добавил определение структуры stack_item в начало второго блока кода.   -  person Sarathi    schedule 19.02.2016
comment
Хм. Может я что-то не так понимаю, но зачем вам stack_item? Не проще ли построить узлы напрямую, используя конкретные типы?   -  person Simon Kraemer    schedule 19.02.2016
comment
@SimonKraemer stack_item — это структура, которая попадает в мой стек синтаксического анализа во время синтаксического анализа LR. Мне нужно было отслеживать, какая часть AST принадлежит каждому элементу стека синтаксического анализа, чтобы я мог связать их вместе во время редукции. Вот почему я добавил свойство node в stack_item. Кроме того, некоторые символы в правой части правила являются терминалами со связанными с ними данными, такими как IDENT (данные), поэтому мне также нужно было иметь возможность передавать эти данные на ASTNode, которым они нужны.   -  person Sarathi    schedule 19.02.2016
comment
Вы можете создать узел объединения, который имеет либо традиционные дочерние элементы, либо список дочерних элементов, и просто получить доступ к тому, что вы хотите. Вы теряете некоторую безопасность типов, потому что вы можете по ошибке получить доступ к списку, когда вы должны были получить доступ к дочернему элементу, но тогда любая ошибка кодирования, которую вы ошибаетесь, является проблемой, поэтому не делайте этого :-}   -  person Ira Baxter    schedule 11.08.2018

Ответы (1)


arrow_upward
1
arrow_downward

Мой генератор синтаксического анализа LSTAR создает дерево абстрактного синтаксиса (AST), используя только один класс Node. Каждый узел представляет собой одну и ту же структуру, указатель на токен (в таблице символов, если это конечный узел) и указатели на родительский, дочерний и следующий узлы. Следующий указатель позволяет вам иметь список узлов (несколько дочерних узлов для родительского узла). Это хорошо работает уже много лет.

Во время обработки AST это функция, связанная с узлом, которая заботится об обработке узла. Например, функция добавления будет делать что-то другое, чем функция вычитания. Функции разные, вместо того, чтобы иметь разные классы для каждого типа узла.

Вот структура узла, которую я использую:

  class Node
  {
     public:
     int    id;      // Node id number              
     int    prod;    // Production (rule) number           
     int    sti;     // Symbol-table index (perm or temp var).
     int    prev;    // Previous node.                          
     int    next;    // Next node.                          
     int    line;    // Line number.                      
     int    child;   // Child node.                       
     int    parent;  // Parent node.
  };
person Community    schedule 20.03.2017