原文在此。
————翻译分隔线————

编译器(8)-抽象语法树

第一部分：介绍
第二部分：编译、转译和解释
第三部分：编译器设计概览
第四部分：语言设计概述
第五部分：Calc 1 语言规格说明书
第六部分：标识符
第七部分：扫描

在构建解析器之前，首先应当谈谈如何处理目标数据。

需要用某种抽象数据类型来保存所有需要解析的数据。树形数据结构很好的满足了我们的需求。这个树描述了编程语言的语法结构，它被很恰当的叫做抽象语法树（AST）。

AST

树形数据结构总是从一个根开始，我们的也是一样。通常，在一个成熟的编译器中，你通常会有一个代表包或程序的对象。在我们的例子中，我们只有一个文件，因此我们将有一个叫做 File 的对象。

这个对象的其他部分可以在我们的语法蓝图中找到。再次提醒，回顾我们创建语法规则的第五部分。它告诉我们到底需要什么。你是不是对于已经建立了标准而感到开心？当我们开始解析和语法分析的时候，它还是会提供有力的支持。

其他需要创建的对象：表达式和整数。

在构造需要的对象之前，需要考虑一下它们看起来应当是什么形态。对于它我们知道什么？

我们知道扫描器会为我们提供三个东西：

我们扫描到的字符串。可能是数值“42”。

表示元素的标识符。token.LPAREN 是一个左括号。

元素开始的位置。在文件的基数和基数加上文件的大小之间的数值。

在树中的所有对象都中共存的东西就是它们的位置。它们从哪里开始，到哪里结束。例如，错误报告不会关心它是什么类型的对象。只需要了解它的位置是多少。因此我们创建了一个 Node 的接口，有两个方法用于开始位置的 Pos，和用于结束位置的 End。

接下来，在我们的语法规则中有一个经常出现的元素：表达式。表达式可以是一个整数，或是一个由括号包裹的一串元素。它的接口将叫做 Expr。任何 Expr 对象必须实现 exprNode 同时完整匹配 Node 的接口。

现在就可以在编译器的不同部分之间通过各个接口传递对象，并且如果需要的话可以使用类型断言来得到它们真正的类型。当我们到达解析步骤的时候，这应该会变得更清晰一些。

我们需要实现三个对象和一个辅助对象：

我们将从 Integer 开始。之前我们已经考虑过整数类型其实与其他对象没有什么不同。可以花大量时间为语言的每个类型来创建对象，也可以只创建一个对象来保存所有的基本类型。

BasicLit 就是这样一个对象。不论我们有整数、浮点数、字符串还是字符都没有关系。这个对象可以满足以上所有需求。当然，当前我们只需要整数，不过最后我们总会作一些添加。这个对象保存了可以告诉我们对象类型的标识符、语法串开始的位置和字符串标识的语法串。

先跳过表达式，先看看 File。这个对象也是类似的。它作为起点，有一个字段：Root。回顾语法规则，可以发现，一个文件保存了一个表达式，而这个表达式又作为其他所有东西的根出现。

现在表达式是一个特殊的类型了。从数学角度来说，它们是双值表达式。有若干元素需要跟踪：一个运算符、左右括号和两个或以上数量的运算对象，运算对象又可以是表达式。

双值表达式不会永远是我们唯一的表达式类型。最终，我们会需要更多类型。只有左右括号在我们的语言中的每个表达式都会有的。这也就是通用表达式能带来帮助的地方。它唯一的作用就是处理括号。这个对象会嵌入所有的子表达式中去。

Go 的魅力就在于任何对象都可以通过嵌入的方式“继承”被嵌入的对象的方法。这不是真正的继承，不过编译器已经足够聪明了。无论如何，对于我们的目的，结果是一样的。

已经提到，BinaryExpr 需要有一个运算符和一组运算对象。我们有一个字段来保存运算对象和其在代码中的位置。运算对象保存在一个 slice 中，这些对象都完全满足 Expr 接口。

如果需要查询 AST，一个遍历这个树的的方法可以提供帮助。这个简单的 Walk 函数就是为此提供的。

通过 Print 方法可以打印出 AST，只需要遍历整个树并且按顺序打印每个一节点的信息。

我们很快就要进行解析步骤了，不过我希望确保 AST 的代码清晰。嵌套定义的表达式容易混淆，还有一些方法并没有提供使用它们的上下文。请在继续前回顾本文和前面的文章。

感谢上帝，将所有的部分组装起来进行解析，应当会让事情变得更加清晰一些。