如何构建抽象语法树

Question

如何构建抽象语法树

abstract-syntax-tree

86

我大致了解AST是什么，但我想知道如何构建它。

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

如果你有一个语法和一个表达式，你该如何构造AST？

- neuromancer

16

HS在这里提供的“答案”令人困惑，实际上并没有直接回答问题。这个问题的答案实际上在这里：https://dev59.com/KF8f5IYBdhLWcg3wFvWn#25106688 - Ira Baxter

3个回答

11

答案并没有令人满意地回答“如何构建AST”的问题。

这篇来自《Crafting Interpreters》系列的文章对于初学者来说，清晰简单地回答了这个问题，并提供了实现方法。由于Stackoverflow不允许链接，因此我将复制主要内容。同时，该文章已经归档。

递归下降解析

有一整套解析技术，它们的名称大多似乎是“L”和“R”的组合 - LL(k)、LR(1)、LALR - 以及更奇特的东西，如解析器组合器、Earley解析器、shunting yard算法和packrat解析器。对于我们的第一个解释器来说，一种技术就足够了：递归下降。

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

它被认为是自顶向下的解析器，因为它从顶部或最外层的语法规则（这里是表达式）开始，然后进入嵌套子表达式，最后到达语法树的叶子节点。这与自底向上的解析器（如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

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

注：

它被称为“递归下降”，因为它沿着语法向下遍历。令人困惑的是，当我们谈论“高”和“低”优先级时，方向在比喻上也被反转了。在自顶向下的解析器中，您首先到达最低优先级的表达式，因为它们可能包含更高优先级的子表达式。按递增优先级顺序排列的自顶向下的语法规则。

原始图片链接

CS人需要聚在一起，整理好他们的隐喻。甚至不要让我开始谈论堆栈应该增长的方向。

- Default

2

我将从一般的角度回答这个问题，不会试图谈论词法分析器和语法分析器。

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

抽象语法树（AST）不包含任何非终结符号。它只包含符号。

例如：

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

这是一个非常快速的展示a+a*b的版本。需要注意的是，抽象语法树的解释取决于树的优先级以及你所使用的遍历类型（中序、前序、后序）。这将是您编写到搜索树中的通用函数。然而，一般来说，该解析树的AST可能如下所示：

   +
 |   |
 a   * 
    | |
    a b

- Dhruv Ghulati

26

很酷，但是如何“构建”一个语法树呢？ - ForceBru

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- HS. · Accepted Answer

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

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

要从语法和表达式构造解析树，你首先必须将你的语法转换为可工作的代码。通常，你会将工作分成一个分词器，它将表示表达式的输入流分成一系列标记，以及一个解析器，它接受标记列表并从中构造解析树\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之类的解析器生成器。这些工具接受您的语法描述，并生成用于令牌化和解析的代码。（针对大多数流行语言和一些不太流行的语言都有代码生成器。）

您构建解析器的方式在很大程度上取决于您使用的语言。在Haskell中编写解析器的方法完全不同于在C中编写的方法。

这里有一篇教程，向你展示如何构建自己的递归下降解析器。
Coco是各种语言的解析器生成器，还附带有入门文档。
如果你喜欢Python，那么pyparsing可能适合你。