[译]Let’s Build A Simple Interpreter. Part 11.

Posted on | Comments:

原文地址：Let’s Build A Simple Interpreter. Part 11.

有一天我坐在我的房间里，回想我们已经学了多少了，觉得我应该回顾一下我们到现在为止 都学了什么以及还有多少要学。

Figure 1: recap

到现在为止我们都学了：

  • 怎样把句子拆成 token。这个过程叫做 词法分析 (lexical analysis)，解释器中做该 工作的部分叫做 词法分析器 (lexical analyzer, lexer, scanner, 或者 tokenizer)。 我们学习了在不使用正则表达式或 Lex 这样的工具的情况下，怎么从头写我们自己的 lexer 。
  • 如何在 token 流中识别出一个短语。在 token 流中识别出一个短语的过程，或者换一种 说法，在 token 流中找到结构的过程叫做 句法分析 (parsing 或 syntax analysis)。 解释器中做该工作的部分叫做 词法解析器 (parser 或 syntax analyzer)。
  • 怎样使用 句法图 (syntax diagrams)来表示一门编程语言的句法规则，这是编程语言 句法规则的一种图形表示。 句法图 用图形的方式告诉我们哪些语句是合法的以及哪些 是不合法的。
  • 怎样使用另一种广泛使用的方法来表示编程语言的句法。它叫做 上下文无关语法 (context-free grammars, 简称 grammars)或 BNF (Backus-Naur Form)。
  • 如何将一个语法编成代码以及如何写一个 递归下降解析器 (recursive-descent parser)。
  • 怎样写一个十分基础的 解释器 。
  • 操作符的 结合性 和 优先级 是怎么工作的以及怎样使用优先级表构建语法。
  • 怎样将解析到的语句构建成一个 抽象语法树 (Abstract Syntax Tree, AST) 以及如何 将整个 Pascal 源程序用一个大的 AST 表示。
  • 怎样遍历一个 AST 以及如何将我们的解释器实现为一个 AST 结点访问者。

在掌握了这些知识和经验的基础上，我们构建了一个解释器，它可以扫描，解析以及构建一 个 AST 并且通过遍历这个 AST 对我们第一个完整的 Pascal 程序进行了解释。女士们先生 们，我真的觉得如果你走到了现在，你值得被拍拍后背。但是不要被冲昏了头脑，继续前进。 尽管我们已经说到了很多方面，但后面还有更令人兴奋的部分。

以我们已经学到的做基础，我们差不多可以解决下面的问题了：

  • 嵌套的过程和函数
  • 过程和函数调用
  • 语义分析（类型检查，确保变量在使用之前被声明，以及在程序说得通时做此基本检查）
  • 流程控制元素（如 IF 语句）
  • 复合数据类型（记录 Records）
  • 更多的内置类型
  • 源代码级别的调度器
  • 其他（上面没提到的所有其他好东西：）

不过在讲解这些主题之前，我们需要建立一个牢固的基础及基础设施。

Figure 2: foundation

这是我们深入到非常重要的主题如符号，符号表和作用域的开始。这些主题会需要多篇文章。 它们就是这么重要，你会知道为什么的。好了，让我们开始建立基础和基础设施吧，好吗？

首先，让我们聊聊符号以及为什么我们需要跟踪它们。什么是 符号 (symbol)？为了直观 的目的，我们将不正式地把 符号 定义为一些程序实体的标识符，如变量，子程序或者内 转类型。要想让符号起到作用，我们至少需要它们可以标识程序实体的以下信息：

  • 名字（例如，‘x’，‘y’，‘number’）
  • 类别（它是一个变量，子程序，还是内置类型？）
  • 类型（INTEGER，REAL）

今天我们会解决变量符号和内置类型符号，因为我们在之前已经使用过变量了类型了。顺便 说一下，“内置”类型仅仅意味着一个不是由你定义却可以直接使用的类型，就像你以前用过 的 INTEGER 和 REAL 类型一样。

让我们看一眼下面的 Pascal 程序，特别注意一下变量声明部分。可以看到在下面的图片中 该部分有 4 个符号：两个变量符号（x和y）以及两个内置类型符号（INTEGER 和 REAL）。

Figure 3: prog symbols

我们怎样在代码中表示符号呢？让我们在 Python 中新建一个基类 Symbol: 

1
2
3
4
class Symbol():
    def __init__(self, name, type=None):
	self.name = name
	self.type = type

如你所见，这个类接收参数 name 和一个可选参数 type （不是所有的符号都有一个与 之关联的类型）。那符号的类别呢？我们会把一个符号的类别编码进类名里去，即我们会创 建不同的类来表示不同的符号类别。

让我们从基本内置类型开始。至今为止我们在声明变量时共见过两种内置类型： INTEGER 和 REAL。我们怎么在代码中表示一个内置类型符号？下面是方式之一： 

1
2
3
4
5
6
7
8
class BuiltinTypeSymbol(Symbol):
    def __init__(self, name):
	super(BuiltinTypeSymbol, self).__init__(name)

    def __str__(self):
	return self.name

    __repr__ = __str__

这个类继承自 Symbol 类且它的构建函数只要求一个该类型的名字。类别被编码进了类名， 内置类型符号的基类的 type 参数是 None 。双下划线或 dunder(Double UNDERscore) 方法 __str__ 和 __repr__ 是特殊的 Python 方法，定义它们是为了在打印一个符号 对象时有一个漂亮的格式整齐的消息。

下载文件 interpreter 并保存为 spi.py; 在保存该文件的目录下启动一个 python shell，并试着使用我们刚刚一起定义的类： 

$ python
>>> from spi import BuiltinTypeSymbol
>>> int_type = BuiltinTypeSymbol('INTEGER')
>>> int_type
INTEGER
>>> real_type = BuiltinTypeSymbol('REAL')
>>> real_type
REAL

我们怎样表示一个变量符号？让我们新建一个 VarSymbol 类： 

1
2
3
4
5
6
7
8
class VarSymbol(Symbol):
    def __init__(self, name, type):
	super(VarSymbol, self).__init__(name, type)

    def __str__(self):
	return f'<{self.name}:{self.type}>'

    __repr__ = __str__

在这个类中，我们让 name 和 type 这两个参数都变成必须的，而类名 VarSymbol 清楚地表明了这个类标识了一个变量符号（类别是 variable.）

回到 python 交互 shell 来看看我们怎样可以手工构建一个变量符号的对象，而我们已经 知道了如何构建 BuiltinTypeSymbol 类的对象： 

$ python
>>> from spi import BuiltinTypeSymbol, VarSymbol
>>> int_type = BuiltinTypeSymbol('INTEGER')
>>> real_type = BuiltinTypeSymbol('REAL')
>>>
>>> var_x_symbol = VarSymbol('x', int_type)
>>> var_x_symbol
<x:INTEGER>
>>> var_y_symbol = VarSymbol('y', real_type)
>>> var_y_symbol
<y:REAL>

如你所见，我们先创建了一个内置类型符号的实例，然后将它作为参数传递给了 VarSymbol 的构建函数。

下面是我们定义的符号的层级结构的可视化表示：

Figure 4: symbol hierarchy

到目前为止还不错，但我们还没有回答我们到底为什么需要跟踪这些符号。

下面是一些原因：

  • 确保我们在向一个变量赋值时，类型是正确的（类型检查）
  • 确保变量在使用之前被声明

看一眼下面不正确的 Pascal 程序，例如：

Figure 5: symtracking

1
PROGRAM Part11;
VAR
   x : INTEGER;
   y : REAL;

BEGIN
   y := 3.5;
   x := 2 + y;  { 1 }
   x := a;      { 2 }
END.

上面的程序中有两个问题（你可以使用 fpc 编译来查看它们）：

  • 在表达式“x := 2 + y;”中，我们将一个浮点型值赋给了变量“x”，而它被声明为了整型。 因为类型不相容所以编译不会通过。
  • 在赋值语句“x := a;”中，我们引用了不曾声明的变量“a”──错！

为了可以在运行时对程序源码进行解释/求值之前就识别出这样的问题，我们需要跟踪程序 符号。那我们把跟踪的符号存放在哪儿呢？我想你猜对了──在符号表里！

什么是 符号表 ？符号表是一种抽象数据结构（ADT），用来跟踪源码中的各种符号。今 天我们会将我们的符号表实现为一个包含辅助方法的单独的类： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class SymbolTable():
    def __init__(self):
	self._symbols = OrderedDict()

    def __str__(self):
	s = 'Symbols: {symbols}'.format(
	    symbols = [value for value in self._symbols.values()]
	)
	return s

    def define(self, symbol):
	print('Define: %s' % symbol)
	self._symbols[symbol.name] = symbol

    def lookup(self, name):
	print('Lookup: %s' % name)
	# 'symbol' is either an instance of the Symbol class or 'None''
	return symbol

我们会在符号表上做两种主要操作：存储符号和根据名字进行查找：因此我们需要两个辅助 方法 ── define 和 lookup.

define 方法接收一个符号作为参数并将它存储在内部的有序字典 _symbols 中，使用 符号的名字作为键而符号本身作为值。方法 lookup 接收一个符号名作为参数，在找到时 返回一个符号，否则返回“None”。

让使用刚刚使用来手工创建符号和内置类型符号的相同 Pascal 程序我们手工填充一下符号 表： 

1
PROGRAM Part11;
VAR
   x : INTEGER;
   y : REAL;

BEGIN

END.

再次启动 Python shell 并尝试以下的例子： 

$ python
>>> from spi import SymbolTable, BuiltinTypeSymbol, VarSymbol
>>> symtab = SymbolTable()
>>> int_type = BuiltinTypeSymbol('INTEGER')
>>> symtab.define(int_type)
Define: INTEGER
>>> symtab
Symbols: [INTEGER]
>>>
>>> var_x_symbol = VarSymbol('x', int_type)
>>> symtab.define(var_x_symbol)
Define: <x:INTEGER>
>>> symtab
Symbols: [INTEGER, <x:INTEGER>]
>>>
>>> real_type = BuiltinTypeSymbol('REAL')
>>> symtab.define(real_type)
Define: REAL
>>> symtab
Symbols: [INTEGER, <x:INTEGER>, REAL]
>>>
>>> var_y_symbol = VarSymbol('y', real_type)
>>> symtab.define(var_y_symbol)
Define: <y:REAL>
>>> symtab
Symbols: [INTEGER, <x:INTEGER>, REAL, <y:REAL>]

如果你查看字典 _symbols 的内容，它看上去是下面这样的：

Figure 6: symtab

我们怎样将建立符号表的过程自动化？我们只是编写另一个结点访问者来遍历由 parser 建 立的 AST！这是另一个展示像 AST 这样的中间表示很有用的例子。相比于扩展我们的 parser 来处理符号表，我们将需求拆分并写了一个新的结点访问类。漂亮而简洁。：）

不过在做这些事之前，让我们扩展我们的 SymbolTable 类使它在创建符号表实例时初始 化内置类型。下面是今天 SymbolTable 类的完整源代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class SymbolTable():
    def __init__(self):
	self._symbols = OrderedDict()
	self._init_builtins()

    def _init_builtins(self):
	self.define(BuiltinTypeSymbol('INTEGER'))
	self.define(BuiltinTypeSymbol('REAL'))

    def __str__(self):
	s = 'Symbols: {symbols}'.format(
	    symbols = [value for value in self._symbols.values()]
	)
	return s

    __repr__ = __str__

    def define(self, symbol):
	print('Define: %s' % symbol)
	self._symbols[symbol.name] = symbol

    def lookup(self, name):
	print('Lookup: %s' % name)
	symbol = self._symbols.get(name)
	# 'symbol' is either an instance of the Symbol class or 'None'
	return symbol

现在看看 SymbolTableBuilder AST 结点的访问者： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class SymbolTableBuilder(NodeVisitor):
    def __init__(self):
	self.symtab = SymbolTable()

    def visit_Block(self, node):
	for declaration in node.declarations:
	    self.visit(declaration)
	self.visit(node.compound)

    def visit_Program(self, node):
	self.visit(node.block)

    def visit_BinOp(self, node):
	self.visit(node.left)
	self.visit(node.right)

    def visit_Num(self, node):
	pass

    def visit_UnaryOp(self, node):
	self.visit(node.expr)

    def visit_Compound(self, node):
	for child in node.children:
	    self.visit(child)

    def visit_NoOp(self, node):
	pass

    def visit_VarDecl(self, node):
	type_name = node.type_node.value
	type_symbol = self.symtab.lookup(type_name)
	var_name = node.var_node.value
	var_symbol = VarSymbol(var_name, type_symbol)
	self.symtab.define(var_symbol)

你以前已经在 Interpreter 类中见过这些方法中的大多数了，不过 visit_VarDecl 值 得特别提一下。再看一遍： 

1
2
3
4
5
6
def visit_VarDecl(self, node):
    type_name = node.type_node.value
    type_symbol = self.symtab.lookup(type_name)
    var_name = node.var_node.value
    var_symbol = VarSymbol(var_name, type_symbol)
    self.symtab.define(var_symbol)

这个方法负责访问（遍历） VarDecl 结点并将相应的符号保存到符号表中。首先，该方 法根据名字从符号表中查找内置类型，然后创建一个 VarSymbol 的实例并将它保存（定 义）在符号表中。

让我们拉出我们的 SymbolTableBuilder AST 遍历者出来遛遛： 

$ python
>>> from spi import Lexer, Parser, SymbolTableBuilder
>>> text = """
... PROGRAM Part11;
... VAR
...    x : INTEGER;
...    y : REAL;
...
... BEGIN
...
... END.
... """
>>> lexer = Lexer(text)
>>> parser = Parser(lexer)
>>> tree = parser.parse()
>>> symtab_builder = SymbolTableBuilder()
Define: INTEGER
Define: REAL
>>> symtab_builder.visit(tree)
Lookup: INTEGER
Define: <x:INTEGER>
Lookup: REAL
Define: <y:REAL>
>>> # Let’s examine the contents of our symbol table
…
>>> symtab_builder.symtab
Symbols: [INTEGER, REAL, <x:INTEGER>, <y:REAL>]

在上面的交互会话中，可以看到一系列的“Define: …”和“Lookup: …”信息，表示了符号在符 号表中定义和查找的顺序。会话中的最后一条命令打印出了符号表的内容，可以看到它和前 面手工构建的符号表的内容完全一样。AST 结点访问者有帮你做所有工作的魔力。：）

我们已经可以把符号表和符号表构建器好好利用上：我们可以用它们来验证变量在声明和表 达式中使用之前被声明。我们需要做的只是向访问者里多加入两个方法： visit_Assign 和 visit_Var. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def visit_Assign(self, node):
    var_name = node.left.value
    var_symbol = self.symtab.lookup(var_name)
    if var_symbol is None:
	raise NameError(repr(var_name))

    self.visit(node.right)

def visit_Var(self, node):
    var_name = node.value
    var_symbol = self.symtab.lookup(var_name)

    if var_symbol is None:
	raise NameError(repr(var_name))

如果这些方法在符号表中找不到某个符号就会抛出一个 NameError 异常。

看一下下面的程序，我们引用了还未声明的变量“b”： 

1
PROGRAM NameError1;
VAR
   a : INTEGER;

BEGIN
   a := 2 + b;
END.

让我们看一看，如果我们构建一个该程序的 AST 并将其传递给我们的符号表构建器来遍历： 

$ python
>>> from spi import Lexer, Parser, SymbolTableBuilder
>>> text = """
... PROGRAM NameError1;
... VAR
...    a : INTEGER;
...
... BEGIN
...    a := 2 + b;
... END.
... """
>>> lexer = Lexer(text)
>>> parser = Parser(lexer)
>>> tree = parser.parse()
>>> symtab_builder = SymbolTableBuilder()
Define: INTEGER
Define: REAL
>>> symtab_builder.visit(tree)
Lookup: INTEGER
Define: <a:INTEGER>
Lookup: a
Lookup: b
Traceback (most recent call last):
  ...
  File "spi.py", line 674, in visit_Var
    raise NameError(repr(var_name))
NameError: 'b'

正是我们所期望的结果！

下面是另一个错误示例，它尝试向一个未定义的变量‘a’赋值： 

1
PROGRAM NameError2;
VAR
   b : INTEGER;

BEGIN
   b := 1;
   a := b + 2;
END.

同时，在 Python shell 中： 

>>> from spi import Lexer, Parser, SymbolTableBuilder
>>> text = """
... PROGRAM NameError2;
... VAR
...    b : INTEGER;
...
... BEGIN
...    b := 1;
...    a := b + 2;
... END.
... """
>>> lexer = Lexer(text)
>>> parser = Parser(lexer)
>>> tree = parser.parse()
>>> symtab_builder = SymbolTableBuilder()
Define: INTEGER
Define: REAL
>>> symtab_builder.visit(tree)
Lookup: INTEGER
Define: <b:INTEGER>
Lookup: b
Lookup: a
Traceback (most recent call last):
  ...
  File "spi.py", line 665, in visit_Assign
    raise NameError(repr(var_name))
NameError: 'a'

太好了，我们的新访问者也捕获到了这个问题！

在这儿我想强调的一点是，所有我们 SymbolTableBuilder 这个 AST 访问者所做的检查 都是在运行之前进行的，即在我们的解释器真正对源代码进行求值之前。为了把问题讲清楚， 如果我们要解释下面的程序： 

1
PROGRAM Part11;
VAR
   x : INTEGER;
BEGIN
   x := 2;
END.

符号表和运行时 GLOBAL_MEMORY 的内容在程序退出之前是像这样的：

Figure 7: symtab vs globmem

看出不同了吗？你能看出符号表中没有为变量“x”保存值2吗？这现在完全是解释器的工作了。

记得第九部分中的图片中符号表被用作了全局内存？

Figure 8: ast st02

不会现有啦！我们实际上摆脱了符号表作为全局内存的现任这一妥协之处。

让我们将以上代码放在一起并用下面的程序测试我们的新解释器： 

1
PROGRAM Part11;
VAR
   number : INTEGER;
   a, b   : INTEGER;
   y      : REAL;

BEGIN {Part11}
   number := 2;
   a := number;
   b := 10 * a + 10 * number DIV 4;
   y := 20 / 7 + 3.14
END.  {Part11}

将程序保存为 part11.pas 并传给使用解释器： 

$ python spi.py part11.pas
Define: INTEGER
Define: REAL
Lookup: INTEGER
Define: <number:INTEGER>
Lookup: INTEGER
Define: <a:INTEGER>
Lookup: INTEGER
Define: <b:INTEGER>
Lookup: REAL
Define: <y:REAL>
Lookup: number
Lookup: a
Lookup: number
Lookup: b
Lookup: a
Lookup: number
Lookup: y

Symbol Table contents:
Symbols: [INTEGER, REAL, <number:INTEGER>, <a:INTEGER>, <b:INTEGER>, <y:REAL>]

Run-time GLOBAL_MEMORY contents:
a = 2
b = 25
number = 2
y = 5.99714285714

我想两次提醒你注意 Interpreter 类和建立符号表无关，它依赖 SymbolTableBuilder 来确保源码中的变量在被 Interpreter 使用之前正确地声明过。

检查你的理解

  • 什么是符号？
  • 我们为什么要跟踪符号？
  • 什么是符号表？
  • 定义一个符号和解析/查找一个符号的区别是什么？

  • 对于以下的简短的 Pascal 程序，符号表和全局内存(Interpreter 中的字典 GLOBAL_MEMORY)的内容是什么？ 

    1
    PROGRAM Part11;
VAR
   x, y : INTEGER;
BEGIN
   x := 2;
   y := 3 + x;
END.

这就是今天的全部内容。在下一篇文章中，我会讨论作用域且会尝试解析嵌套过程。敬请关 注，下次再见！记住无论如何，“保持前进！”

Figure 9: keep going

另：我关于符号和符号表管理的主题爱 Terence Parr 的书《Language Implementation Patterns》影响很大。这是一本非常棒的书。我觉得它是我见过把这个主题讲解得最好的书， 而且它还讲解了类作用域，我不会在这个系列中讲解该主题，因为我们不会讨论面向对象的 Pascal。

另另：如果你等不及想学习编译器，我非常推荐可以免费获得的 Jack Crenshaw 的经典之 作“Let's Build a Compiler”。

顺便说一下，我还在写一本书“et’s Build A Web Server: First Steps”，解释了怎么从头 写一个基本的 Web 服务器。你可以从这里， 这里 和 这里 来感受一下这本书。

本系列的所有文章：

Last Updated 2018-05-26 Sat 14:12.
Render by hexo-renderer-org with Emacs 25.2.2 (Org mode 9.1.13)
0%