c++ - 在 C++ 中生成 AST

Question

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

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

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

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

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，保证代表一个有效的程序(因为你在这个过程中做了所有的语义错误检查)，并且可以对其应用优化，然后是代码生成阶段(以及更多的优化沿着方式)。

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

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