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

  1. 新增 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
  2. 修改 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 }

上面这段示例程序包含一个带参数的过程。下面是为了支持带参数的过程声明所要做的修改:

  1. 增加 Param AST 结点

    class Param(AST):
        def __init__(self, var_node, type_node):
    	self.var_node = var_node
    	self.type_node = type_node
  2. 修改 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
  3. 修改 declarations 规则以反映过程声明子规则的变化

    def declarations(self):
        """declarations : (VAR (variable_declaration SEMI)+)*
    		    | (PROCEDURE ID (LPAREN formal-parameter_list RPAREN)? SEMI block SEMI)*
    		    | empty
        """
  4. 增加 formal_parameter_list 规则和方法

    def formal_parameter_list(self):
        """ formal_parameter_list : formal_parameters
    			      | formal_parameters SEMI formal_parameter_list
        """
  5. 增加 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_Programvisit_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)