2021-08-22发表2023-12-16更新《Let’s Build A Simple Interpreter》笔记19 分钟读完 (大约2871个字)0次访问

06 过程声明与变量作用域 | 《Let’s Build A Simple Interpreter》笔记

本系列是《Let’s Build A Simple Interpreter》的阅读笔记。

过程的定义

过程声明是一个定义一个标识符（过程名）的语言结构，它将该标识符与一个 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}

这是修改过的语法：

1
2
3

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 结点作为参数：
1
2
3
4
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 方法，这会让的解释器忽略所有的过程声明：

1 2	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 规则和方法

1
2
3

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)

06 过程声明与变量作用域 | 《Let’s Build A Simple Interpreter》笔记

http://www.zh0ngtian.tech/posts/229ef3c1.html

作者

zhongtian

发布于

2021-08-22

更新于

2023-12-16

06 过程声明与变量作用域 | 《Let’s Build A Simple Interpreter》笔记

过程的定义

无参数过程声明

语法

lexer

parser

interpreter

有参数过程声明

符号作用域表

带有形式参数的过程声明

过程符号

嵌套作用域

作用域树：作用域符号表链

嵌套作用域和名字解析

作者

发布于

更新于

许可协议

评论

目录