如何构造抽象语法树

Question

我对AST是什么有一个大概,但我想知道如何构建一个.

如果给你一个语法和一个解析树,你如何构建AST？

如果给你一个语法和表达,你怎么做？

Answer 1

好吧,首先,语法用于从表达式构造一个解析树.因此,如果您已经有一个解析树,则不需要语法.

根据解析器的工作量,通过解析表达式形成的结果树可能已经是一个抽象语法树.或者它可能是一个简单的解析树,需要第二遍来构建ast.

要从语法和表达式构造解析树,首先必须将语法转换为工作代码.通常,您将工作拆分为一个tokenizer,它将表示表达式的输入流拆分为一个标记列表,一个解析器获取标记列表并从中构造一个解析树\ ast.

因此表达式1 + 2*(3+4)可能会被拆分为这样的标记列表:

1 - int
+ - add_operator
2 - int
* - mul_operator
( - lparen
3 - int
+ - add_operator
4 - int
) - rparen

第一列是实际文本值.第二个代表令牌类型.这些标记被输入到解析器中,该解析器是根据您的语法构建的,并识别标记并构建解析树.

那么,如何编写词法标记化器和实际的解析器呢？你可以手动滚动自己.或者,更常见的是,使用解析器生成器,如coco或antlr或lex/yacc.这些工具描述了您的语法并为tokenzier和parser生成代码.(代码生成器适用于大多数流行语言,也适用于一些不受欢迎的语言.)

如何构建解析器在很大程度上取决于您使用的语言.如何在Haskell中编写解析器与在C中编写解析器的方式完全不同,例如C.

• 这是一个教程,向您展示如何构建自己的递归下降解析器.

• Coco是各种语言的解析器生成器,它还附带有关如何入门的文档.

• 如果Python是你的东西,那么pyparsing也许适合你.

Answer 2

对于“如何构建 AST”这个问题，答案并不令人满意。

\n

这篇文章 收录于Crafting Interpreters 系列，为初学者提供了简洁明了的答案。完成实施。Stackoverflow 不是一个提供链接的地方，所以我将复制要点。

\n\n

递归下降解析

\n

有一整套解析技术，其名称大多是 \xe2\x80\x9cL\xe2\x80\x9d 和 \xe2\x80\x9cR\xe2\x80\x9d\xe2\x80\x94LL(k) 的组合、LR(1)、LALR\xe2\x80\x94 以及更奇特的野兽，如解析器组合器、Earley 解析器、调车场算法和 Packrat 解析。对于我们的第一个解释器，一种技术就足够了：递归下降。

\n

递归下降是构建解析器的最简单方法，并且不需要使用复杂的解析器生成工具（例如 Yacc、Bison 或 ANTLR）。您所需要的只是简单的手写代码。不过，不要被它的简单性所迷惑。递归下降解析器快速、健壮，并且可以支持复杂的错误处理。事实上，GCC、V8（Chrome 中的 JavaScript VM）、Roslyn（用 C# 编写的 C# 编译器）和许多其他重量级生产语言实现都使用递归下降。太棒了。

\n

它被认为是自上而下的解析器，因为它从顶部或最外层语法规则（此处为表达式）开始，并向下进入嵌套子表达式，最后到达语法树的叶子。这与像 LR 这样的自下而上解析器形成鲜明对比，后者从主要表达式开始并将它们组合成越来越大的语法块。

\n

递归下降解析器是将 Grammar\xe2\x80\x99s 规则直接直译为命令式代码。每个规则都成为一个函数。规则的主体翻译成代码大致如下：

\n

Grammar notation    Code representation\nTerminal            Code to match and consume a token\nNonterminalCall     to that rule\xe2\x80\x99s function\n|                   if or switch statement\n* or +              while or for loop\n?                   if statement\n

\n

它\xe2\x80\x99s称为\xe2\x80\x9c递归下降\xe2\x80\x9d，因为当语法规则引用自身时\xe2\x80\x94直接或间接\xe2\x80\x94转换为递归方法调用。

\n\n

旁注：

\n

它\xe2\x80\x99s 称为\xe2\x80\x9c 递归下降\xe2\x80\x9d 因为它沿着语法走下去。令人困惑的是，在谈论 \xe2\x80\x9chigh\xe2\x80\x9d 和 \xe2\x80\x9clow\xe2\x80\x9d 优先级时，我们也隐喻地使用方向，但方向是相反的。在自上而下的解析器中，您首先到达优先级最低的表达式，因为它们可能依次包含更高优先级的子表达式。\n自上而下的语法规则按优先级递增的顺序排列。

\n

原图链接

\n

\n

CS 人员确实需要聚集在一起并理顺他们的隐喻。Don\xe2\x80\x99t 甚至让我开始了解堆栈应该向哪个方向增长。

\n\n