在 C 中生成 AST

Question

我正在用 C++ 制作解释器，到目前为止，我已经让我的词法分析器生成标记。问题是我不确定如何生成“walk”解析树。

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

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

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

原文由 Francis 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我将在这里与传统观点背道而驰，说您应该使用特定于自然语言的数据结构手动构建您的 AST。

通用的“AST 数据结构”将过于笼统而无法舒适地使用——使用 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 ，这会消耗和/或查看标记以确定语句是函数定义还是函数调用，然后调用 parseFunction parseCall 适当。这称为手写递归下降解析器，根据我的经验，这是迄今为止您可以编写的最简单和最好的解析器类型。是的，有样板要写，但它也是非常清晰和灵活的代码。

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

如果允许在定义之前调用函数，这也很容易处理 - 只需解析调用部分而不检查在您第一次解析时是否存在具有该名称的函数，然后再关联它。

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

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

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

原文由 Cameron 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您可以使用一些 解析器生成器，例如 bison 或 ANTLR 。两者都有很好的文档和教程部分。语法规则的动作部分（馈送到 bison 或 antlr ，生成用于解析的 C++ 代码）将构建抽象语法树。

如果不了解更多您想要解析和解释的形式语言的 语法（和 语义），我们将无能为力。

如果你的语言是中缀计算器，bison 就有这样的 例子。

您可能应该考虑一个类层次结构来表示 AST 的节点。您将有一个叶子类（例如数字），一个添加节点类（有两个儿子作为指向其他节点的 智能指针）等等……

例如

class ASTNode {
/// from http://stackoverflow.com/a/28530559/841108
///... 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 上面。

要遍历树，您将进行递归遍历，以便更好地使用智能指针。另请阅读 访问者模式。并且使用 C++11 std::function -s 和匿名闭包 -ie lambdas - ，你可以有一个 visit 虚函数（你给它一个访问每个节点的闭包）。访问文件树的 Unix nftw(3) 函数可能会很有启发性。

原文由 Basile Starynkevitch 发布，翻译遵循 CC BY-SA 3.0 许可协议