9

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

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

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

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

4

5 回答 5

20

我将在这里与传统观点背道而驰，说您应该使用特定于自然语言的数据结构手动构建您的 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();

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

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

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

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

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

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

于 2015-02-15T20:28:29.230 回答
8

您可以使用一些解析器生成器，例如bison或ANTLR。两者都有很好的文档和教程部分。语法规则的动作部分（输入bisonor 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)函数可能会很有启发性。

于 2015-02-15T20:06:50.163 回答
2

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

根据您的问题猜测您的经验水平，如果我是您，我将至少构建一次基于 flex/bison 的解析器/AST 构建器以获得良好的体验，然后再返回自己构建所有内容。

于 2015-02-15T19:58:34.467 回答
1

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

于 2020-06-09T12:16:51.593 回答
0

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

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

于 2021-11-07T19:10:52.537 回答