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

2017-01-07 19:00:12  mikespook
阅读 170 次  0 条评论  收藏

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

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

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

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

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

AST

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

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

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

Go 接口

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

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

      我们扫描到的字符串。可能是数值“42”。
      表示元素的标识符。token.LPAREN 是一个左括号。
      元素开始的位置。在文件的基数和基数加上文件的大小之间的数值。

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

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

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

对象

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

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

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

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

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

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

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

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

AST 工具

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

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

继续前进

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

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

本文来自:mikespook 的博客

感谢作者:mikespook

查看原文:[翻译]编译器(8)-抽象语法树

0条评论

文章点评:

(您需要 登录 后才能评论 没有账号 ?)
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet