如何构建抽象语法树

Question

我对AST有一个大概的概念，但我想知道如何构建一个。

如果给你一个语法和一棵解析树，你如何构造AST？

如果给你一个语法和一个表达式，你该怎么做呢？

Answer 1

首先，该语法用于从表达式构造解析树。所以如果你已经有了一个解析树，你就不需要语法了。

根据解析器所做的工作，解析表达式所形成的结果树可能已经是一个抽象语法树。或者它可以是一个简单的解析树，它需要第二次遍历来构造ast。

要从语法和表达式构建解析树，首先必须将语法转换为工作代码。通常，您会将工作分成一个分词器( tokenizer )和一个解析器( parser )，前者将表示表达式的输入流分割为一个标记列表，后者获取该标记列表并从中构造一个解析树。

因此，表达式1 + 2*(3+4)可能会被拆分成一个标记列表，如下所示：

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

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

那么，如何编写词法标记器和实际的解析器呢？你可以用手卷你自己的。或者，更常见的是，使用诸如coco或antlr或lex/yacc之类的解析器生成器。这些工具对您的语法进行描述，并为标记器和解析器生成代码。(代码生成器适用于大多数流行语言和一些不受欢迎的语言。)

如何构造解析器在很大程度上取决于所使用的语言。用Haskell编写解析器的方式与用C编写解析器的方式完全不同。

Python这里有一个教程，向您展示如何使用build your own recursive descent parser.

• Coco是一种适用于各种语言的解析器生成器，该教程还附带了有关如何入门的文档。

• 如果您喜欢使用

• ，那么pyparsing可能适合您。

Answer 2

在回答“如何构造一个AST”的问题上，答案是不令人满意的。

这是来自the series Crafting Interpreters的article archived，对于初学者来说，回答起来既简洁又容易。与实现一起完成。Stackoverflow不是一个链接的地方，所以我将复制要点。

递归下降解析

有一整套解析技术，它们的名称似乎大多是“L”和“R”-LL(K)，LR(1)，LALR的组合-还有更奇特的东西，如解析器组合器，厄利解析器，分流码数算法，以及packrat解析。对于我们的第一个解释器，一种技术就足够了:递归下降。

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

它被认为是一个自上而下的解析器，因为它从顶部或最外层的语法规则(here表达式)开始，然后向下进入嵌套的子表达式，最后到达语法树的叶子。这与LR这样的自下而上的解析器形成对比，LR从主表达式开始，然后将它们组合成越来越大的语法块。

递归下降解析器是将语法规则直接翻译成命令式代码。每条规则都变成了一个函数。规则的主体转换为大致如下的代码：

Grammar notation    Code representation
Terminal            Code to match and consume a token
NonterminalCall     to that rule’s function
|                   if or switch statement
* or +              while or for loop
?                   if statement

它被称为“递归下降”，因为当语法规则直接或间接地引用自身时，就会转换为递归方法调用。

附注：

它被称为“递归下降”，因为它遵循语法。令人困惑的是，当我们谈论“高”和“低”优先级时，我们也会用方向来比喻，但方向是相反的。在自上而下的解析器中，您首先到达优先级最低的表达式，因为它们可能包含优先级较高的子表达式。按优先级递增顺序的自上而下的语法规则。

Original image link

​

​

CS人员真的需要聚在一起，理清他们的比喻。甚至不要让我开始堆栈应该向哪个方向发展。

Answer 3

我将从一般的角度来回答这个问题，而不是试图讨论词法分析器和解析器。

解析树包含非终端符号，这些符号是上下文无关语法的一部分，并显示产生式链以获得由终端符号组成的字符串，无论是递归还是非递归。因此，当您拥有解析树时，您不需要语法-您可以从解析树派生语法。

AST不包含任何非终端符号。它只包含符号。

示例：

 E
 |
 E + T
 |   |
 T   M * M
 |   |   |
 M   a   b
 |
 a

这是显示a+a*b的一个非常快速的版本。注意，解释抽象语法树的方式取决于树的优先级，以及您执行哪种类型的遍历(按顺序、前顺序、后顺序)这将是您在搜索树中编码的通用函数。但是，通常情况下，解析树AST可能如下所示：

   +
 |   |
 a   * 
    | |
    a b