abstract-syntax-tree - 如何构建抽象语法树

Question

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

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

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

Answer 1

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

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

要从语法和表达式构建解析树，您首先必须将语法转换为工作代码。通常，您会将工作拆分为标记生成器和解析器，标记生成器将表示表达式的输入流拆分为标记列表，解析器获取标记列表并从中构造解析树\ast。

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

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

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

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

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

• 这是一个教程，向您展示如何 build your own recursivedescent parser .

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

• 如果您喜欢 Python，那么 pyparsing也许适合你。