c++ - LR解析时构造AST

Question

我已经编写了一个 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 的子类，因此我必须创建一个子类，其中包含每个子节点的 vector<>。但是，由于并非每个节点都需要是列表结构，因此在我可以访问内部列表之前，我必须 dynamic_cast<> 到子类。

我觉得应该有一种更简洁的方法来处理子节点列表，而不必依赖 dynamic_cast<>。

另一个问题是关于 FuncDec 节点的。它有 pParams，它应该是一个 ParamList(或 vector 直接)，但要做到这一点，我必须 dynamic_cast<> 传入的 ASTNode 到 ParamList 或 Param 节点。同样，我觉得应该有一种不使用 dynamic_cast<> 的方法，但我想不出一个。

此外，如果您对我如何更好地构建或实现任何东西有任何其他建议，我们将不胜感激:)

Answer 1

我的 LRSTAR Parser Generator仅使用一个类 Node.js 创建抽象语法树 (AST)。每个节点都是相同的结构，一个指向 token 的指针(如果是叶节点，则在符号表中)，以及指向父节点、子节点和下一个节点的指针。 next 指针允许您拥有节点列表(父节点的多个子节点)。这多年来一直运作良好。

在 AST 的处理过程中，与节点关联的函数负责节点的处理。例如，add 函数将执行与 subtract 函数不同的操作。功能不同，而不是每种类型都有不同的类的节点。

这是我使用的节点结构:

  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.
  };