76

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

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

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

4

3 回答 3

42

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

根据解析器所做的工作量，解析表达式形成的结果树可能已经是抽象语法树。或者它可能是一个简单的解析树，需要第二遍来构造 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。这些工具对您的语法进行描述，并为 tokenzier 和解析器生成代码。（大多数流行语言和一些不流行的语言都有代码生成器。）

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

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

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

  • 如果 Python 是你的菜，那么pyparsing可能适合你。

于 2009-11-12T11:46:37.070 回答
4

在回答“如何构建 AST”的问题时，答案并不令人满意。

这篇文章 来自Crafting Interpreters 系列，为初学者提供了简洁而轻松的答案。完成与实施。Stackoverflow 不是链接的地方，所以我将复制要点。

递归下降解析

有一整套解析技术，其名称似乎大多是“L”和“R”的组合——LL(k)、LR(1)、LALR——以及更奇特的野兽，如解析器组合器、Earley 解析器、分流码算法和 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人员真的需要聚在一起，理清他们的隐喻。甚至不要让我开始讨论堆栈应该增长的方向。

于 2020-09-12T09:17:34.857 回答
3

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

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

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

例子：

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

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

   +
 |   |
 a   * 
    | |
    a b
于 2016-05-09T10:07:03.657 回答