如何从BNF设计抽象语法树（AST）

Question

我已经定义了自己语言的BNF，但不知如何设计AST。

例如，以下是我BNF的前几行：

<program> ::= <import declarations>? <class declaration>?
<import declarations> ::= <import declaration> | <import declarations> <import declaration>
<class declaration> ::= class <identifier> <class body>
<import declaration> ::= import <type name> ';'

我该如何从我的AST中表达这个呢？我应该像这样设计它吗？

typedef vector<ImportDeclaration*> ImportDeclarationList;

class Program {
    ImportDeclarationList importDeclarations;
    ClassDeclaration classDeclaration;
};

class ImportDeclaration {
    TypeName typeName;
};

class ClassDeclaration {
    Identifier identifer;
    ClassBody classbody;
};

我需要在这些类之间添加一些继承吗？

有没有关于如何从BNF设计AST的书籍？

- 47dev47null

---

节点需要包含一个“抽象”语法类别（通常接近于许多规则的LHS）。 请参阅https://dev59.com/knI-5IYBdhLWcg3wYXL8#1916687，了解AST与CST之间的讨论，以及为什么您可能希望节点包含具体语法类别（例如，规则的确切LHS或叶子的具体名称）。 - Ira Baxter

Answer 1

你只需要实现一个树形数据结构。这意味着你需要一些类，比如Node，所有AST的其他可能元素都必须从它继承。然后你可以使用成员指针(Node*)。如果孩子的数量可能会变化，你可以将它们存储在std::vector中。 例如，对于一个非常简单的产生式（假设IntLiteral是一个终端符号）：

Addition := IntLiteral + IntLiteral

可以为AST编写以下代码：

struct Node {
    virtual Node* clone() { return new Node(*this);};
    virtual ~Node() {}
};
class IntLiteral : Node {
    int value;
public:
    IntLiteral(int v) : value(v) {}
    virtual IntLiteral* clone()
    {
        return new IntLiteral(*this);
    }
};
class Addition : Node {
    Node* left;
    Node* right;
public:
    Addition(Node* l, Node* r)
        : Node(), left(l->clone()), right(r->clone()) {}
    virtual Addition* clone()
    {
        return new Addition(*this);
    }
};

假设您正在手动实现，您可以在解析器代码的接受函数中向根节点（在此情况下为Addition*类型）添加节点。

实际上，您可能希望为每个节点都有一个“生成”函数。或者，更好的方法是，您需要访问器和树遍历器来生成代码。

有很多关于解析器的书籍，其中之一是经典的“龙书”，尽管重点实际上是编译器。

- Aleph