在C中生成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分配记录,而不是在堆上单独动态分配所有内容.最后,代替字符串,通常最好在原始源代码中使用偏移量和长度.