用C++生成AST

Question

我正在用C++编写一个解释器,到目前为止我已经有了生成令牌的词法分析器了.问题是我不确定如何生成一个解析树的"walk".

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

我不确定是否自上而下,左右或自下而上,左右.

任何人都可以为我提供简单的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分配记录,而不是在堆上单独动态分配所有内容.最后,代替字符串,通常最好在原始源代码中使用偏移量和长度.

Answer 2

您可以使用一些解析器生成器,如bison或ANTLR.两者都有很好的文档与教程部分.语法规则的动作部分(提供给bison或antlr生成用于解析的C++代码)将构建抽象语法树.

如果不了解您想要解析和解释的形式语言的语法(和语义),我们将无法提供更多帮助.

如果您的语言是中缀计算器,那么野牛就有这样的例子.

您可能应该考虑使用类层次结构来表示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)函数可能是鼓舞人心的.