[译]Let’s Build A Simple Interpreter. Part 13: Semantic Analysis.

Posted on | Comments:

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

Anything worth doing is worth overdoing.

在深入作用域这个主题之前，我想绕个“小”弯再谈一些关于符号，符号表和语义分析的细节。 本着“Anything worth doing is worth overdoing.”的精神，我希望你能觉得在处理嵌套作 用域之前这些内容对于构建一个更牢固的基本很有用。今天我们会继续增加我们关于怎样编 写解释器和编译器的知识。你会看到在这篇文章中覆盖到的内容是你在第十一部分中看到的 关于符号和符号表内容的更进一步推广。

Figure 1: img01

在本系列的最后四篇文章中我们会讨论余下的知识点。在下面你可以看到我们会覆盖到的主 要主题以及时间线：

Figure 2: img01

好了，让我们开始吧！

语义分析介绍

就算我们的 Pascal 程序是语法上正确的且可以成功地构建抽象语法树，它仍然可能包含一 些非常严重的错误。为了找出这些错误我们需要用到抽象语法树和符号表中的信息。

为什么我们不能在解析时，即句法分析时，检查这些错误呢？为什么我们不得不构建一个 AST 和一个叫符号表的东西来做这些？

简单来说，为了方便以及分离关注点。通过把多余的检查移动单独的阶段，我们可以每次专 注于一个任务，而不用让我们的解析器和解释器做不属于它们的工作。

当 parser 构建完 AST 时，我们知道程序是语法正确的；即它的句法是符合我们的语法规 则的，而现在我们可以专注于需要额外上下文和 parser 在构建 AST 时所没有的信息才能 进行的检查。再说得具体点，让我们看一下下面的 Pascal 赋值语句： 

1
x := x + y;

parser 可以正确地处理它，因为语法上这条语句是正确的（根据我们以前为赋值语句和表 达式定义的语法规则）。但故事还没结束，因为 Pascal 有一个要求，即变成必须在使用前 声明他们的类型。parser 怎么知道‘x’和‘y’是否被声明了呢？

其实，它不知道，而这正是我们需要一个单独的语义分析阶段来回答某个变量是否在使用之 前被声明等问题的原因。

什么是 语义分析 ？简单来说，它只是一个帮助我们判断一个程序是否有意义的过程，且 该程序从语言定义的角度来看是否有意义。

当说一个程序有意义的时候到底是什么意思？它和一门语言的的定义的语言要求有很大关系。

Pascal 语言，更具体点是 Free Pascal 的编译器，有具体的要求，如果程序没有符合， fpc 编译器就会报出一个错误表示该程序“没有意义”、不正确，甚至当句法看上去没问题时 也是如此。下面是其中一些要求：

  • 变量必须在使用之前被声明
  • 变量表达式中被用到时它的类型必须是匹配的
  • 不能有重复声明（例如，Pascal 禁止一个过程中的局部变量和过程的正式参数有相同的 名字）
  • 一个引用过程的名字必须是一个真正声明过的过程（在 Pascal 中的过程调用 foo() 中，如果 foo 指代一个基本类型 INTEGER，就没有意义）
  • 过程调用必须有正确数量的参数，且参数的数量也必须与过程声明中相匹配

在我们有足够的关于这个程序的上下文时，即作为中间表示可以遍历的 AST 和保存不同程 序实体如变量、过程和函数信息的符号表。

在我们实现语义分析阶段之后，我们的 Pascal 解释器的结构就会是这样：

Figure 3: img03

从上面的图片中可以看到我们的 lexer 将源代码作为输入，将其转换为 token 作为 parser 的输入从而验证程序是语法正确的，然后 parser 会生成一个抽象语法树，我们的 新的语义分析阶段会使用该语法树来确保程序符合不同的 Pascal 语言要求。在语义分析阶 段中，语义分析器会建立并使用符号表。在语义分析之后，我们的解释器会得到该语法树， 通过遍历 AST 来对程序进行求值并产生程序输出。

让我们看一下语义分析阶段的一些细节。

符号和符号表

在下面这一节中，我们会讨论怎样实现部分语义检查以及怎样构建符号表：换一种说法就是， 我们将会讨论怎样对我们的 Pascal 程序执行语义分析。记住尽管语义分析听上去很高大上， 它不过是在解析程序和构建 AST 后另一个检查的步骤，用来检查源代码中 parser 因为缺 少特定信息（上下文）而无法检查出来的错误。

今天我们会专注于以下两个静态语义检查1：

  1. 变量在使用之前被声明
  2. 没有重复的变量声明

让我们从第一个检查开始并确保我们的 Pascal 程序变量在使用之前进行了声明。看看下面 的语法正确但是语义错误的程序（呃…在一个句子中读出这个词真困难。：） 

1
program Main;
   var x : integer;

begin
   x := y;
end.

上面的程序有一个变量声明和两个变量引用。你可以从下面的图片中看出：

Figure 4: img04

让我们验证一下该程序确实是语法正确且我们的 parser 没有在解析它时抛出错误。常言说， 信任但要确认。：）下载 spi.py，启动一个 Python shell，自己试一下： 

>>> from spi import Lexer, Parser
>>> text = """
program Main;
   var x : integer;

begin
    x := y;
end.
"""
>>>
>>> lexer = Lexer(text)
>>> parser = Parser(lexer)
>>> tree = parser.parse()
>>>

看见没？没有错误。我们甚至可以使用 genastdot.py 为这个程序生成一个 AST 图。首先， 把源代码保存到一个文件中，比如 semanticerror01.pas，然后运行下面的命令： 

1
$ python genastdot.py semanticerror01.pas > semanticerror01.dot
$ dot -Tpng -o ast.png semanticerror01.dot

下面是这个 AST 图：

Figure 5: img05

所以，它是一个语法（句法）正确的程序，但这个程序没有意义因为我们甚至不知道变量 y 的类型（这就是需要声明的原因）以及将 y 赋值给 x 是否有意义。假如 y 是 一个字符串呢，将字符串赋值给整型是否有意义？没有，至少在 Pascal 中没有。

所以上面的程序有一个语义错误，因为变量 y 没有声明，我们不知道它的类型。为了捕 捉到类似的错误，我们需要学习怎样检查变量是否在使用之前被声明。那么让我们学习怎样 做吧。

让我们仔细看一下下面这个句法和语义都正确的示例程序： 

1
program Main;
   var x, y : integer;

begin
   x := x + y;
end.
  • 它有两个变量声明： x 和 y
  • 它在赋值语句 x := x + y; 有三个变量引用(x, 另一个 x, 还有 y)

Figure 6: img06

这个程序在语法上是正确的，所有的变量都声明了，而且可以看到将两个整数相加并将结果 赋值给整型变量肯定有意义。这很好，但我们怎样通过程序检查赋值语句 x := x + y; 中变量（变量引用） x 和 y 被声明过？

我们可以通过实现下面的算法用几步来做到：

  1. 遍历所有的变量声明
  2. 对于每个遇到的变量声明，收集所有关于它的必要信息
  3. 将收集到的信息保存在某个地方供将来使用，在有变量引用时将变量名作为键
  4. 当你看到一个变量引用，例如在赋值语句 x := x + y; 中，通过变量名搜索存储的内 容看有没有相关的信息。如果有，该变量就被声明过。如果没有，该变量就还没有被声 明，就是一个语义错误。

我们程序的流程图看起来像这样：

Figure 7: img07

在我们可以实现这个算法之前，需要回答一些问题：

  • A. 我们需要收集变量的什么信息？
  • B. 我们应该把收集到的信息存放在哪里以及如何存放？
  • C. 我们怎样实现“遍历所有变量声明”这一步？

我们的计划是这样：

  1. 找到上面 A，B 和 C 的答案。
  2. 使用这些答案来实现我们第一个静态语义检查──对变量在使用之前被声明的检查──算法 中的这些步骤。

好了，让我们开始吧。

让我们为问题“我们需要收集变量的什么信息？”找到一个答案

那么，对于一个变量来说，我们需要收集什么必要的信息呢？下面是一些重要的部分：

  • 名字(Name)（我们需要知道一个声明过的变量的名字，因为我们会通过它们的名字来查找 变量）
  • 类别(Category)（我们需要知道一个标识符是什么类型：变量，类型，过程，等待）
  • 类型(Type)（我们需要这个信息来进行类型检查）

符号会保存关于变量的这些信息（名字，类别，类型）。什么是符号？ 符号 就是一个用 来标识像变量，子过程或内置类型这样的程序实体的标识符。

在下面的例子程序中有两个变量声明，我们用来创建两个变量符号： x 和 y 。

Figure 8: img08

在这段代码中，我们会用一个名为 Symbol 的包含字段 name 和 type 的类来表示符 号： 

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

如你所见，该类接受参数 name 及一个可选参数 type （并非所有的符号都有相关联的 类型信息，我们很快就能看到）。

那么类别呢？我们会把类别编码进类名中。或者，我们也可以将一个符号的类别存储在 Symbol 类的一个专用字段 category 中： 

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

不过，创建一组有层级的以类名标识类别的类会更清楚。

直到现在我有些回避了一个话题，即内置类型。如果你再看一眼我们的示例程序： 

1
program Main;
   var x, y : integer;

begin
   x := x + y;
end.

你可以看到变量 x 和 y 被声明为了 integer. integer 类型什么？ integer 类型 是另一种符号，一个内置类型符号(built-in type symbol)。它被叫做内置是因为它不需要 在 Pascal 程序中被显示地声明。声明这些类型符号并使它们可供程序员使用是我们的解释 器的现任：

Figure 9: img09

我们将会为内置类型创建一个单独的类叫做 BuiltinTypeSymbol. 下面是我们内置类型 的类定义： 

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

    def __str__(self):
	return self.name

    def __repr__(self):
	return f"<{self.__class__.__name__}(name='{self.name}')"

类 BuiltinTypeSymbol 继承自类 Symbol, 且它的构建函数只要求类型的名字，如 integer 或 real. 和我们前面讨论的一样，‘内置类型’的类别被编码进了类名中，这 样当我们创建一个 BuiltinTypeSymbol 的实例时，父类中的参数 type 就自动被设置 为了 None.

ASIDE

带有双下划线或 dunder("Double UNDERscore")的方法 __str__ 和 __repr__ 是特殊 的 Python 方法。我们定义它们可以使得在打一个符号对象到标准输出时有一个漂亮格式的 消息。

顺便说一下，内置类型就是参数 type 在构建函数中可选的原因。

下面是到现在为止的符号类层次结构：

Figure 10: img10

让我们在 Python shell 里试一下内置类型。下载解释器文件并保存为 spi.py；从将文件 保存到的目录启动一个 Python shell，交互式地尝试一下我们刚定义的类： 

$ python
>>> from spi import BuiltinTypeSymbol
>>> int_type = BuiltinTypeSymbol('integer')
>>> int_type
<BuiltinTypeSymbol(name='integer')>
>>>
>>> real_type = BuiltinTypeSymbol('real')
>>> real_type
<BuiltinTypeSymbol(name='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.__class__.__name__}(name='{self.name}', type='{self.type}')"

    __repr__ = __str__

在这个类中，参数 name 和 type 都是必须的，而类名 VarSymbol 清楚地表明了它 的实例标识了一个变量符号(类别是 variable)。参数 type 是 BuiltinTypeSymbol 类的一个实例。

回到交互式 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
<VarSymbol(name='x', type='integer')>
>>>
>>> var_y_symbol = VarSymbol('y', real_type)
>>> var_y_symbol
<VarSymbol(name='y', type='real')>
>>>

如你所见，我们先创建了一个内置类型符号的实例，然后将它作为第二个参数传递给了 VarSymbol 的构建函数：变量符号必须同时提供名字和与之相关的类型，就像我们在之前 见过很多的类似 var x : integer; 的变量声明。

下面是我们已定义的符号的完整层次结构的图形表示：

Figure 11: img11

好了，继续回答问题“我们应该把收集到的信息存放在哪里以及如何存放？”

现在有了表示所有变量声明的符号，我们应该把它们存放在哪儿以便将来在碰到变量引用 （名字）时查找它们？

答案就是，你可以已经知道了，放在符号表里。

什么是符号表？ 符号表 是一个抽象数据类型，用来跟踪源码中的各种符号。把它理解为 一个字典，其中符号名是键，值是一个符号类（或它的一个子类）的实例。为了表示代码中 的符号表，我们会用一个被恰当地命名为 SymbolTable 的专门的类。：）为了在符号表 中存储符号，我们会向符号表类中添加 insert 方法。 insert 方法接收一个符号作为 参数并在内部将其保存在名为 _symbols 的有序字典中，其中符号名为键，符号实例为值： 

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

    def __str__(self):
	symtab_header = 'Symbol table contents'
	lines = ['\n', symtab_header, '_' * len(symtab_header)]
	lines.extend(
	    ('%7s: %r' % (key, value))
	    for key, value in self._symbols.items()
	)
	lines.append('\n')
	s = '\n'.join(lines)
	return s

    __repr__ = __str__

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

让我们为下面的示例程序手工填充符号表。因为我们还不知道怎样搜索，所以我们的程序不 会包含任何变量引用，只有变量声明： 

1
program SymTab1;
var x, y : integer;

begin

end.

下载 symtab01.py，它包含了我们的新 SymbolTable 类，并从命令行上运行它。对于上 面的程序，输出应该类似： 

$ python symtab01.py
Insert: INTEGER
Insert: x
Insert: y


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

现在让我们在 Python shell 中手工建立并填充一个符号表： 

$ python
>>> from symtab01 import SymbolTable, BuiltinTypeSymbol, VarSymbol
>>> symtab = SymbolTable()
>>> int_type = BuiltinTypeSymbol('INTEGER')
>>> # now let's store the built-in type symbol in the symbol table
...
>>> symtab.insert(int_type)
Insert: INTEGER
>>>
>>> symtab


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>


>>> var_x_symbol = VarSymbol('x', int_type)
>>> symtab.insert(var_x_symbol)
Insert: x
>>> symtab


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
      x: <VarSymbol(name='x', type='INTEGER')>


>>> var_y_symbol = VarSymbol('y', int_type)
>>> symtab.insert(var_y_symbol)
Insert: y
>>> symtab


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>


>>>

到现在为止我们已经回答了两个前面提出的问题：

  • A. 我们需要收集变量的什么信息？

    名字，类别和类型。且我们用符号来保存这些信息。

  • B. 我们应该把收集到的信息存放在哪里以及如何存放？

    我们用 insert 方法把收集到的符号放在符号表中。

现在让我们寻找第三个问题的答案： ‘我们怎样实现“遍历所有变量声明”这一步？’

这个非常简单。因为我们已经有了 parser 所生成的 AST 了，只需要建立一个新的 AST visitor 类负责遍历语法树并在访问到 VarDecl 结点时做不同的动作就行了！

现在我们已经回答了所有三个问题：

  • A. 我们需要收集变量的什么信息？

    名字，类别和类型。且我们用符号来保存这些信息。

  • B. 我们应该把收集到的信息存放在哪里以及如何存放？

    我们用 insert 方法把收集到的符号放在符号表中。

  • C. 我们怎样实现“遍历所有变量声明”这一步？

    我们创建一个新的 AST visitor，它在访问到 VarDecl 结点时会做些处理。

让我们创建一个新的语法树 visitor 类并命名为 SemanticAnalyzer. 看一下下面的程序， 如： 

1
program SymTab2;
var x, y : integer;

begin

end.

为了分析上面的程序，我们不需要实现所有的 visit_xxx 方法，只需要一个子集就够了。 下面是 SemanticAnalyzer 类的骨架，实现了足够多的 visit_xxx 方法使得它可以成 功遍历上面示例程序的 AST： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class SemanticAnalyzer(NodeVisitor):
    def __init__(self):
	self.symtab = SymbolTable()

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

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

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

    def visit_NoOp(self, node):
	pass

    def visit_VarDecl(self, node):
	#  Actions go here
	pass

现在，我们有实现静态语义检查──确保所有变量在使用之前被声明的检查──算法前三步的所 有部分了。

再看一遍我们算法的步骤：

  1. 遍历所有的变量声明
  2. 对于每个遇到的变量声明，收集所有关于它的必要信息
  3. 将收集到的信息保存在某个地方供将来使用，在有变量引用时将变量名作为键
  4. 当你看到一个变量引用，例如在赋值语句 x := x + y; 中，通过变量名搜索存储的内 容看有没有相关的信息。如果有，该变量就被声明过。如果没有，该变量就还没有被声 明，就是一个语义错误。

让我们实现这些步骤。实际上，我们唯一需要做的事就是实现 SemanticAnalyzer 类的 visit_VarDecl 方法。实现如下： 

1
2
3
4
5
6
7
8
9
10
11
def visit_VarDecl(self, node):
    # For now, manually create a symbol for the INTEGER built-in type
    # and insert the type symbol in the symbol table.
    type_symbol = BuiltinTypeSymbol('INTEGER')
    self.symtab.insert(type_symbol)

    # We have all the information we need to create a variable symbol.
    # Create the symbol and insert it into the symbol table.
    var_name = node.var_node.value
    var_symbol = VarSymbol(var_name, type_symbol)
    self.symtab.insert(var_symbol)

如果你看一下该方法的实现，就会发现它实际上合并了所有三个步骤：

  1. 这个方法在我们调用 SemanticAnalyzer 的实例的 visit 方法时，遇到变量声明时 被调用一次。这做到了算法的步骤 1：“遍历所有的变量声明”
  2. 对于每个变量声明， visit_VarDecl 方法会收集必要的信息并建立一个变量符号的实 例。这做到了算法的步骤 2：“对于每个遇到的变量声明，收集所有关于它的必要信息”
  3. 方法 visit_VarDecl 会将从变量声明收集到的信息使用符号表的 insert 方法保存 在符号表中。这做到了算法的步骤 3：“将收集到的信息保存在某个地方供将来使用，在 有变量引用时将变量名作为键”

要查看所有这些步骤的运行效果，下载文件 symtab02.py，先学习它的源码，再在命令行上 运行它并检查它的输出： 

$ python symtab02.py
Insert: INTEGER
Insert: x
Insert: INTEGER
Insert: y


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

你可能注意到有 Insert: INTEGER 有两行。我们会在下一节讨论语义检查算法最后一步 （步骤4）的实现时改正这个问题。

好了，让我们实现算法的第4步。下面是第4步修改过的版本，以反映符号和符号表的引入： 当你看到一个变量引用（名字）──比如在赋值语句 x := x + y 中──根据变量的名字在符 号表中查找是否存在与该名字相关的变量符号。如果存在，该变量就被声明过。如果不存在， 该变量就还没有被声过，这就是一个语义错误。

为了实现步骤4,我们需要对符号表和语义分析器做些修改：

  1. 我们需要向符号表中添加一个方法来根据名字查找一个符号。
  2. 我们需要更新语义分析器使它在每次遇到一个变量引用时就在符号表中进行查找。

首先，让我们为 SymbolTable 类添加 lookup 方法，它负责通过名字查找符号。换句 话说， lookup 方法负责将一个变量名（变量引用）解析为它的声明。将变量引用映射到 它的声明的过程叫做 名字解析 (name resolution)。在这里我们的 lookup 方法所做 的就是名字解析： 

1
2
3
4
5
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

该方法接受一个符号名作为参数，并在查找到时返回一个符号，否则返回 None. 就这么 简单。

既然已经开始修改了，就让我们也修改一下 SymbolTable 类来初始化内置类型吧。我们 会通过添加 _init_builtins 方法并在 SymbolTable 类的构建函数中调用它来做这件 事。 _init_builtins 方法会为 integer 和 real 分别在符号表中插入两个类型符 号。

下面是我们修改过的 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
27
28
29
30
31
class SymbolTable(object):
    def __init__(self):
	self._symbols = OrderedDict()
	self._init_builtins()

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

    def __str__(self):
	symtab_header = 'Symbol table contents'
	lines = ['\n', symtab_header, '_' * len(symtab_header)]
	lines.extend(
	    ('%7s: %r' % (key, value))
	    for key, value in self._symbols.items()
	)
	lines.append('\n')
	s = '\n'.join(lines)
	return s

    __repr__ = __str__

    def insert(self, symbol):
	print('Insert: %s' % symbol.name)
	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

既然我们有了内置类型符号和 lookup 方法可以在遇到变量名（以及其他名字如类型名） 时查找我们的符号表，就让我们修改 SemanticAnalyzer 的 visit_VarDecl 方法，将 我们手工构造 INTEGER 内置类型符号，并将其插入到符号表中的两行替换成查找 INTEGER 类型符号的代码。

这个修改也会改正我们前面见过的输出两次 Insert: INTEGER 的问题。

下面是修改前的 visit_VarDecl 方法: 

1
2
3
4
5
6
7
8
9
10
11
def visit_VarDecl(self, node):
    # For now, manually create a symbol for the INTEGER built-in type
    # and insert the type symbol in the symbol table.
    type_symbol = BuiltinTypeSymbol('INTEGER')
    self.symtab.insert(type_symbol)

    # We have all the information we need to create a variable symbol.
    # Create the symbol and insert it into the symbol table.
    var_name = node.var_node.value
    var_symbol = VarSymbol(var_name, type_symbol)
    self.symtab.insert(var_symbol)

然后是修改后的： 

1
2
3
4
5
6
7
8
9
def visit_VarDecl(self, node):
    type_name = node.type_node.value
    type_symbol = self.symtab.lookup(type_name)

    # We have all the information we need to create a variable symbol.
    # Create the symbol and insert it into the symbol table.
    var_name = node.var_node.value
    var_symbol = VarSymbol(var_name, type_symbol)
    self.symtab.insert(var_symbol)

让我们将熟悉的只有变量声明的 Pascal 程序传递给修改过的版本： 

1
program SymTab3;
var x, y : integer;

begin

end.

下载包含所有我们讨论过的改过的文件 symtab03.py，在命令行上运行它，确认在程序输出 中已经没有重复的 Insert: INTEGER 了： 

$ python symtab03.py
Insert: INTEGER
Insert: REAL
Lookup: INTEGER
Insert: x
Lookup: INTEGER
Insert: y


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
   REAL: <BuiltinTypeSymbol(name='REAL')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

你也可以从输出中看到我们的语义分析器对内置类型 INTEGER 进行了两次查找：第一次 是因为变量 x 的声明，第二次是因为变量 y 的声明。

现在让我们把注意力放在变量引用（名字）和怎样把一个变量名──比如在算术表达式中──解 析为它的变量声明（变量符号）上。让我们看一下下面的示例程序，其中有一个赋值语句 x := x + y; 包含了三个变量引用： x, 另一个 x, 还有 y: 

1
program SymTab4;
var x, y : integer;

begin
   x := x + y;
end.

我们在实现符号表时已经实现了 lookup 方法了。现在需要做的是扩展我们的语义分析器， 使它每次遇到变量引用时就使用 lookup 根据名字查找符号表。 SemanticAnalyzer 的 哪个方法会在遍历 AST 的过程中每次遇到变量引用时就被调用呢？就是 visit_Var 方法。 让我们把它添加到类里。很简单：它所做的工作就是根据名字查找变量符号： 

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

由于示例程序 SymTab4 有一个右边是算术加法的赋值语句，我们需要往 SemanticAnalyzer 中添加另外两个方法，使得它可以真正地遍历 SymTab4 程序的 AST 并对所有的 Var 结点调用 visit_Var 方法。这两个方法是 visit_Assign 和 visit_BinOp. 它们没有改动：你之前已经见过这些方法了。如下所示： 

1
2
3
4
5
6
7
8
9
def visit_Assign(self, node):
    # right-hand side
    self.visit(node.right)
    # left-hand side
    self.visit(node.left)

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

文件 symtab04.py 中包含了我们刚刚讨论的改动的完整源码。下载该文件，在命令行上运 行它，并检查将包含一个赋值语句的 SymTab4 程序传给它时的输出。

在我的笔记本上输出如下： 

$ python symtab04.py
Insert: INTEGER
Insert: REAL
Lookup: INTEGER
Insert: x
Lookup: INTEGER
Insert: y
Lookup: x
Lookup: y
Lookup: x


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
   REAL: <BuiltinTypeSymbol(name='REAL')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

花点时间分析输出结果，确保你理解以该顺序输出的原因。

语义错误

到现在为止我们见过的程序都对变量进行了声明，但如果我们的程序有一个变量引用不能被 解析到任何声明呢，即没有被声明呢？这是一个语义错误，我们需要扩展我们的语义分析器 来警示这个错误。

看一下下面这个存在语义错误的程序，其中变量 y 在赋值语句中使用之前没有被声明： 

1
program SymTab5;
var x : integer;

begin
   x := y;
end.

要警示这个错误，我们需要修改 SemanticAnalyzer 的 visit_Var 方法，使它在 lookup 方法不能解析一个名字并返回 None 时抛出一个异常。下面是修改过的 visit_Var: 

1
2
3
4
5
6
7
8
def visit_Var(self):
    var_name = node. value
    var_symbol = self.symtab.lookup(var_name)

    if var_symbol is None:
	raise Exception(
	    "Error: Symbol(identifier) not found '%s'" % var_name
	)

下载 symtab05.py，在命令行上运行它，看看会发生什么： 

$ python symtab05.py
Insert: INTEGER
Insert: REAL
Lookup: INTEGER
Insert: x
Lookup: y
Error: Symbol(identifier) not found 'y'


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
   REAL: <BuiltinTypeSymbol(name='REAL')>
      x: <VarSymbol(name='x', type='INTEGER')>

可以看到错误信息 Error: Symbol(identifier) not found 'y' 以及符号表的内容。

祝贺你完成我们的语义分析器的当前版本，它可以静态检查程序中变量是否在使用之前声明， 如果没有，就抛出一个异常来表示一个语义错误！

让我们暂停一秒钟来庆祝这个重要的里程碑。好了，一秒钟结束了，我们需要继续另一个静 态语义检查。为了好玩以及一些好处，让我们扩展我们的语义分析器来检查声明中的重复标 识符。

让我们看一下下面的程序，SymTab6: 

1
program SymTab6;
var x, y : integer;
var y : real;
begin
   x := x + y;
end.

变量 y 被声明了两次：第一次是 integer， 第二次是 real。

为了捕捉到这个语义错误我们需要修改我们的 visit_VarDecl 方法，使它在插入一个新 符号之前，检查符号表中是否已经存在一个同名的符号了。下面是这个方法的新版： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def visit_VarDecl(self, node):
    type_name = node.type_node.value
    type_symbol = self.symtab.lookup(type_name)

    # We have all the information we need to create a variable symbol.
    # Create the symbol and insert it into the symbol table.
    var_name = node.var_name.value
    var_symbol = VarSymbol(var_name, var_symbol)

    # Signal an error if the table alrady has a symbol
    # with the same name
    if self.symtab.lookup(var_name) is not None:
	raise Exception(
	    "Error: Duplicate identifier '%s' found" % var_name
	)

    self.symtab.insert(var_symbol)

文件 symtab06.py 包含了所有的变化。下载并在命令行上运行它： 

$ python symtab06.py
Insert: INTEGER
Insert: REAL
Lookup: INTEGER
Lookup: x
Insert: x
Lookup: INTEGER
Lookup: y
Insert: y
Lookup: REAL
Lookup: y
Error: Duplicate identifier 'y' found


Symbol table contents
_____________________
INTEGER: <BuiltinTypeSymbol(name='INTEGER')>
   REAL: <BuiltinTypeSymbol(name='REAL')>
      x: <VarSymbol(name='x', type='INTEGER')>
      y: <VarSymbol(name='y', type='INTEGER')>

研究一下输出和符号表的内容。确保你理解发生了什么。

总结

让我们快速回顾一下我们今天学了什么：

  • 我们在更一般的层面上学习了更多关于符号，符号表，和语义分析
  • 我们学习了名字解析以及语义分析器如何将名字解析为它们的声明
  • 我们学习了编写一个语义分析器，它可以遍历 AST，建立符号表，以及做基本的语义检查

作为提醒，现在我们的解释器结构看上去如下：

Figure 12: img03

我们完成了今天的语义检查，终于做好了学习作用域及它们与符号表的关系，在嵌套作用域 存在的情况下进行语义检查等主题。这些会是下一篇文章的中心主题。敬请关注，下次再见！

本系列的所有文章：

Footnotes:

1

静态语义检查就是我们可以在对程序进行解释（求值）之前进行的查检，即在调用 一个 Interpreter 类的实例的 interpret 方法之前。所有之前提到的 Pascal 要求都可以通过遍历 AST 及使用符号表中的信息在静态语义检查时被满足。

动态语义检查则要求检查在对程序的解释（求值）过程中进行。例如，检查除法没 有以 0作为分母，以及数组的索引没有越界都是动态语义检查。我们今天关注的是 静态语义检查。

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