06 过程声明与变量作用域 | 《Let’s Build A Simple Interpreter》
本文最后更新于:2021年8月31日
过程的定义
过程声明是一个定义一个标识符(过程名)的语言结构,它将该标识符与一个 Pascal 代码块关联起来。
对于 Pascal 过程和它的声明:
- Pascal 过程没有返回语句,它们在到达相应代码块结尾时退出
- Pascal 过程可以互相嵌套
无参数过程声明
语法
这是本节的测试程序:
PROGRAM Part12;
VAR
a : INTEGER;
PROCEDURE P1;
VAR
a : REAL;
k : INTEGER;
PROCEDURE P2;
VAR
a, z : INTEGER;
BEGIN {P2}
z := 777;
END; {P2}
BEGIN {P1}
END; {P1}
BEGIN {Part12}
a := 10;
END. {Part12}
这是修改过的语法:
declarations : VAR (variable_declaration SEMI)+
| (PROCEDURE ID SEMI block SEMI)*
| empty
过程声明子规则包含了保留关键字 PROCEDURE 后跟一个标识符(过程名),后跟一个分号,后再跟一个 block 规则,最后由分号结尾。
lexer
增加一个名为 PROCEDURE
的 token,并将其添加到保留关键字中:
RESERVED_KEYWORDS = {
'PROGRAM': Token('PROGRAM', 'PROGRAM'),
'VAR': Token('VAR', 'VAR'),
'DIV': Token('DIV', 'DIV'),
'INTEGER': Token('INTEGER', 'INTEGER'),
'REAL': Token('REAL', 'REAL'),
'BEGIN': Token('BEGIN', 'BEGIN'),
'END': Token('END', 'END'),
'PROCEDURE': Token('PROCEDURE', 'PROCEDURE'),
}
parser
新增
ProcedureDecl
AST 结点。ProcedureDecl
AST 结点代表了一个过程声明。它的构建函数接受过程名和代码块的 AST 结点作为参数:class ProcedureDecl(AST): def __init__(self, proc_name, block_node): self.proc_name = proc_name self.block_node = block_node
修改 parser 的
declarations
方法以支持过程声明:def declarations(self): """declarations : VAR (variable_declaration SEMI)+ | (PROCEDURE ID SEMI block SEMI)* | empty """ declarations = [] if self.current_token.type == VAR: self.eat(VAR) while self.current_token.type == ID: var_decl = self.variable_declaration() declarations.extend(var_decl) self.eat(SEMI) while self.current_token.type == PROCEDURE: self.eat(PROCEDURE) proc_name = self.current_token.value self.eat(ID) self.eat(SEMI) block_node = self.block() proc_decl = ProcedureDecl(proc_name, block_node) declarations.append(proc_decl) self.eat(SEMI) return declarations
interpreter
在 Interpreter 类中增加一个新的空的 visit_ProcedureDecl
方法,这会让的解释器忽略所有的过程声明:
def visit_ProcedureDecl(self, node):
pass
有参数过程声明
符号作用域表
作用域的概念这里不再赘述,至少使用过一门编程语言的同学对整个概念都很了解。Pascal 程序所用的被称为词法作用域(lexically scoped),又叫做静态作用域,因为你可以只看源码而不用执行这个程序,单纯根据文本规则就可以确定哪个名字(引用)会解析到哪个声明。例如在 Pascal 中,像 program end 这样的词法 关键字就划定了一个作用域的文本边界:
当我们讨论嵌套作用域时,使用作用域级别来表示它们的嵌套关系会很方便。通过名字来指代作用域也会很方便。当开始讨论嵌套作用域时,我们会同时使用作用域级别和作用域名字。符号作用域表(scoped symbol table)可以很好地描述下面这两个信息:
- 每个变量(符号)都是在哪一级别被声明的
- 一个变量名引用了哪一级别的哪个声明
为了实现符号作用域表,需要增强 SymbolTable 类,将其重命名为类 ScopedSymbolTable,添加两个新的字段 scope_level 和 scope_name,并修改符号作用域表的构造函数。
class ScopedSymbolTable():
def __init__(self, scope_name, scope_level):
self._symbols = OrderedDict()
self.scope_name = scope_name
self.scope_level = scope_level
self._init_builtins()
def _init_builtins(self):
self.insert(BuiltinTypeSymbol('INTEGER'))
self.insert(BuiltinTypeSymbol('REAL'))
def __str__(self):
h1 = 'SCOPE (SCOPED SYMBOL TABLE)'
lines = ['\n', h1, '=' * len(h1)]
for header_name, header_value in (
('Scope name', self.scope_name),
('Scope level', self.scope_level),
):
lines.append('%-15s: %s' % (header_name, header_value))
h2 = 'Scope (Scoped symbol table) contents'
lines.extend([h2, '-' * len(h2)])
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
下面是一段展示语义分析器如何实例化 ScopedSymbolTable
类的代码:
class SemanticAnalyzer(NodeVisitor):
def __init__(self):
self.scope = ScopedSymbolTable(scope_name='global', scope_level=1)
...
带有形式参数的过程声明
program Main;
var x, y: real;
procedure Alpha(a : integer);
var y : integer;
begin
x := a + x + y;
end;
begin { Main }
end. { Main }
上面这段示例程序包含一个带参数的过程。下面是为了支持带参数的过程声明所要做的修改:
增加
Param
AST 结点class Param(AST): def __init__(self, var_node, type_node): self.var_node = var_node self.type_node = type_node
修改
ProcedureDecl
结点的构建函数以接受一个额外的参数:params
class ProcedureDecl(AST): def __init__(self, proc_name, params, block_node): self.proc_name = proc_name self.params = params # a list of Param nodes self.block_name = block_name
修改
declarations
规则以反映过程声明子规则的变化def declarations(self): """declarations : (VAR (variable_declaration SEMI)+)* | (PROCEDURE ID (LPAREN formal-parameter_list RPAREN)? SEMI block SEMI)* | empty """
增加
formal_parameter_list
规则和方法def formal_parameter_list(self): """ formal_parameter_list : formal_parameters | formal_parameters SEMI formal_parameter_list """
增加
formal_parameters
规则和方法def formal_parameters(self): """ formal_parameters : ID (COMMA ID)* COLON type_spec """ param_nodes = []
下面是示例程序对应的 AST:
过程符号
和变量声明和内置类型声明一样,对于过程也有一个单独的符号类:
class ProcedureSymbol(Symbol):
def __init__(self, name, params=None):
super(ProcedureSymbol, self).__init__(name)
# a list of formal parameters
self.params = params if params is not None else []
def __str__(self):
return '<{class_name}(name={name}, parameters={params})>'.format(
class_name=self.__class__.__name__,
name=self.name,
params=self.params,
)
__repr__ = __str__
过程符号有一个名字(即过程名),它们的类别是过程(被编码进了类名),类型是 None
因为在 Pascal 中过程不返回任何东西。过程符号还保存了关于过程声明的附加信息,即如上面的代码所示,它保存了过程的形参。加上过程符号,新的符号层级如下所示:
嵌套作用域
为了讨论方便,本节使用一个修剪过的程序版本。下面的版本没有变量引用,只有变量和过程声明:
program Main;
var x, y : real;
procedure Alpha(a : integer);
var y : integer;
begin
end;
begin { Main }
end. { Main }
在声明一个新的过程时,就引入了一个新的作用域,而这个作用域嵌套在了由 PROGRAM 引入的全局作用域,所以这是一个有嵌套作用域的 Pascal 程序的例子。一个过程的作用域就是这个过程的整个主体。过程作用域的开始是由关键字 PROCEDURE 标识的,而由关键字 END 和一个分号标识结束。
关键字 PROGRAM 和 PROCEDURE 会引入新的作用域。在 AST 中,相应的结点是 Program 和 ProcedureDecl 。因此需要修改 visit_Program 方法并增加 visit_ProcedureDecl 方法来创建作用域符号表:
def visit_Program(self, node):
print('ENTER scope: global')
global_scope = ScopedSymbolTable(
scope_name='global',
scope_level=1,
)
self.current_scope = global_scope
# visit subtree
self.visit(node.block)
print(global_scope)
print('LEAVE scope: global')
def visit_ProcedureDecl(self, node):
proc_name = node.proc_name
proc_symbol = ProcedureSymbol(proc_name)
self.current_scope.insert(proc_symbol)
print('ENTER scope:%s' % proc_name)
# Scope for parameters and local variables
procedure_scope = ScopedSymbolTable(
scope_name=proc_name,
scope_level=2,
)
# 将过程作用域赋值给变量 self.current_scope 以表明这是当前的作用域
# 所有的符号操作(插入和查找)会使用当前作用域
self.current_scope = procedure_scope
# 处理了过程的形式参数,将它们插入到当前作用域并添加到过程符号中
for param in node.params:
param_type = self.current_scope.lookup(param.type_node.value)
param_name = param.var_node.value
var_symbol = VarSymbol(param_name, param_type)
self.current_scope.insert(var_symbol)
proc_symbol.params.append(var_symbol)
self.visit(node.block_node)
print(procedure_scope)
print('LEAVE scope: %s' % proc_name)
内存中的作用域看上去像下面这样,只是两个独立的作用域符号表:
INTEGER 和 REAL 存在于两个作用域符号表中,原因是我们为每一个作用域都新建了单独的作用域符号表。
作用域树:作用域符号表链
通过在作用域符号表之间创建一个连接来把它们链在一起,这种方式就像一棵树(作用域树):
代码方面的修改主要包括两点:
- 修改
ScopedSymbolTable
类,增加一个变量enclosing_scope
用来保存包含该作用域的作用域。这就是上面图中两个作用域之间的连接 - 修改
visit_Program
和visit_ProcedureDecl
这两个方法,使用修改过的ScopedSymbolTable
类来创建一个指向所嵌套于的作用域的真实的连接
class ScopedSymbolTable(object):
def __init__(self, scope_name, scope_level, enclosing_scope=None):
self._symbols = OrderedDict()
self.scope_name = scope_name
self.scope_level = scope_level
self.enclosing_scope = enclosing_scope
self._init_builtins()
...
def visit_Program(self, node):
print('ENTER scope: global')
global_scope = ScopedSymbolTable(
scope_name='global',
scope_level=1,
enclosing_scope=self.current_scope, # None
)
self.current_scope = global_scope
# visit subtree
self.visit(node.block)
print(global_scope)
# 在将要离开 Program 结点之前把变量 self.current_scope 重置为了它以前的值
self.current_scope = self.current_scope.enclosing_scope
print('LEAVE scope: global')
def visit_ProcedureDecl(self, node):
proc_name = node.proc_name
proc_symbol = ProcdureSymbol(proc_name)
self.current_scope.insert(proc_symbol)
print('ENTER scope: %s' % proc_name)
# Scope for parameters and local variables
procedure_scope = ScopedSymbolTable(
scope_name=proc_name,
scope_level=self.current_scope.scope_level + 1,
enclosing_scope=self.current_scope
)
self.current_scope = procedure_scope
# Insert parameters into the procedure scope
for param in node.params:
param_type = self.current_scope.lookup(param.type_node.value)
param_name = param.var_node.value
var_symbol = VarSymbol(param_name, param_type)
self.current_scope.insert(var_symbol)
proc_symbol.params.append(var_symbol)
self.visit(node.block_node)
print(procedure_scope)
# 在将要离开 ProcedureDecl 结点之前把变量 self.current_scope 的恢复为以前的值
self.current_scope = self.current_scope.enclosing_scope
print('LEAVE scope: %s' % proc_name)
可以把上面的作用域树想象成一组作用域栈。
嵌套作用域和名字解析
下面是一个包含变量引用的示例程序:
program Main;
var x, y: real;
procedure Alpha(a : integer);
var y : integer;
begin
x := a + x + y;
end;
begin { Main }
end. { Main }
像 Pascal 这样的词法(静态)作用域语言在解析名字时遵循最近嵌套作用域 (the most closely nested scope)原则。它的意思是,在每个作用域中,一个名字解析为词法上最近的声明。为了实现这样的查找行为,需要先在当前作用域中进行查找,再从外一层的作用域中查找,一直重复直到找到或者到达了作用域树的最顶层而没有作用域。只需要简单地扩展一下 ScopedSymbolTable
类中的 lookup
方法,使它继续沿着作用域树向上查找就行了:
def lookup(self, name):
print('Lookup: %s. (Scope name: %s)' % (name, self.scope_name))
# 'symbol' is either an instance of the Symbol class or None
symbol = self._symbols.get(name)
# 在当前作用域中根据名字来查找符号,如果找到了就返回
if symbol is not None:
return symbol
# 如果没有找到,递归地遍历作用域树,沿着连接从上一级作用域中查找该符号
if self.enclosing_scope is not None:
return self.enclosing_scope.lookup(name)
评论系统采用 utterances ,加载有延迟,请稍等片刻。