在 C++ 中生成 AST

Question

我正在用 C++ 编写解释器，到目前为止，我已经使用词法分析器生成标记。问题是我不确定如何生成 "walk" 解析树。

我正在考虑使用数组的数组来制作我的解析树，但我不确定如何以正确的顺序将标记实际插入到解析树中。

我不确定是自上而下、左-右还是自下而上、右-左。

谁能给我一个简单的 LALR(1) 算法？

Answer 1

人们将 AST 构建为堆分配树。（是的，你可以做一个数组，但它并不那么方便）。我建议您阅读野牛文档；它会向您解释如何建造树木，您可以遵循这种风格。

根据你的问题猜测你的经验水平，如果我是你，我会在你回来之前至少构建一个基于 flex/bison 的 parser/AST 构建器以获得良好的体验自己构建一切。

Answer 2

您可以使用一些 parser generator like bison or ANTLR。两者都有很好的教程部分文档。语法规则的操作部分（提供给 bison 或 antlr，生成用于解析的 C++ 代码）将构建抽象语法树。

如果不了解您要解析和解释的正式语言的 syntax (and the semantics)，我们将无能为力。

如果你的语言是一个中缀计算器，bison有这样一个example。

您可能应该想到一个 class 层次结构来表示您的 AST. You'll have a class for leafs (e.g. numbers), a class for addition node (with two sons as smart pointers 到其他节点的节点），等等...

例如

class ASTNode {
/// from 
///... add some things here, e.g. a virtual print method
};

class NumberNode : public ASTNode {
   long number;
   /// etc...
};

class BinaryOpNode : public ASTNode {
   std::unique_ptr<ASTNode> left;
   std::unique_ptr<ASTNode> right;
 /// etc....
};

class AdditionNode : public BinaryOpNode {
/// etc....
};

class CallNode : public ASTNode {
   std::shared_ptr<Function> func;
   std::vector<std::unique_ptr<ASTNode>> args;
};

对于可变参数的节点（即任意数量的儿子），您需要一个智能指针向量，如上面的 args。

要遍历树，您将进行递归遍历，因此最好使用智能指针。另请阅读有关访问文件树的 visitor pattern. And with C++11 std::function-s and anonymous closures -i.e lambdas- , you could have a visit virtual function (to which you give a closure visiting each node). The Unix nftw(3) 函数的信息。

Answer 3

我要在这里反对传统智慧，并说你应该用自然语言特定的数据结构手动构建你的 AST。

泛型 "AST data structure" 过于笼统，无法舒适地工作——使用 AST 来做任何有用的代码将被变通方法所掩盖，无法访问它想要的数据。如果你走这条路（或使用解析器生成器），你可能最终会构建一个翻译层，从通用结构到对你的语言实际有意义的 AST。为什么不避开中间人，直接构建最终的数据结构呢？

我建议编写第一个句法传递，它为每个可能的构造消耗它所需的标记（可能根据需要向前看一个标记）。这种句法传递将从数据结构的链接实例中构建 AST，这些数据结构代表您的语言中的每种可能构造。例如，如果您的程序可以包含一系列语句，其中每个语句可以是函数声明或函数调用，则可以创建以下数据结构：

AST (struct)
    -> std::vector<Statement*> statements

StatementKind (enum class)
    -> Function
    -> Call

Statement (struct)
    -> StatementKind kind

Function : Statement (struct)
    -> std::string name
    -> std::vector<Statement*> body

Call : Statement (struct)
    -> std::string name
    -> Function* called

然后构建初始 AST 的语法传递可能如下所示：

auto ast = parseAST();

其中parseAST重复调用parseStatement，消耗and/or peeks at tokens 判断语句是函数定义还是函数调用，然后调用parseFunction或 parseCall 适当。这称为手写递归下降解析器，根据我的经验，这是迄今为止您可以编写的最简单和最好的解析器类型。是的，有样板可写，但它也是非常清晰和灵活的代码。

句法阶段会生成语法错误消息，并在发现错误时尽可能地恢复（这是分号分隔语言的一个论据——编译器和工具通常可以从错误中恢复更容易，因为在尝试解析下一个构造之前遇到错误时跳到下一个分号通常就足够了。

如果一个函数在定义之前允许被调用，这也很容易处理——只解析调用部分而不检查在你第一次解析它时是否存在同名的函数，然后关联稍后。

通过 AST 的第二个语义传递将使用任何缺少的交叉引用数据对其进行注释（例如，使用这些函数的定义解析函数调用的函数名称，或者如果找不到名称则生成错误）。一旦完成，你就有了一个完整的 AST，保证代表一个有效的程序（因为你在这个过程中做了所有的语义错误检查），并且可以对其应用优化，然后是代码生成阶段（以及更多的优化沿着方式）。

请注意，我完全没有提及 LL 或 LR 解析器等。您的语言的理论符号和分类很重要（例如，因为它可以证明它没有歧义），但从实现的角度来看显然，拥有干净、易于理解且最重要的是 易于修改 的代码比遵守特定的解析机制要重要得多。使用手写解析器的其他编译器示例包括 GCC、Clang 和 Google 的 V8 等。

在效率方面，AST 在构建后通常会迭代多次，并且需要在内存中停留直到过程的后期（可能一直到最后，取决于您如何进行代码生成），因此最好使用对象池为 AST 分配记录，而不是在堆上单独动态分配所有内容。最后，代替字符串，通常最好在原始源代码中使用偏移量和长度。

Answer 4

我使用了一套BNF生产方法来生成特定类型的节点（结构继承）来生成AST。使用 std::move()，您可以转移指针所有权以避免悬空指针。然后是public递归访问方法（switch-case），按照一定的遍历模式（post/pre顺序）遍历AST，检查AST节点类型，每次访问执行accept() .接受绑定到必须由用户实现的调度程序接口（打印树、执行树等）。对于每次访问，都会调用用户端的相应方法。

Answer 5

帮自己一个忙，使用提升精神。这是 AST 示例的快速 link。 https://www.boost.org/doc/libs/1_77_0/libs/spirit/doc/html/spirit/qi/tutorials/mini_xml___asts_.html

该库不仅维护良好且经过深思熟虑，而且非常易于使用且文档非常出色。基本上，它允许您以非常易读的 C++ 方式编写语法。我强烈推荐它。

在 C++ 中生成 AST

Generate an AST in C++

c++

algorithm

parsing

abstract-syntax-tree

lalr