09 调用栈与活动记录 | 《Let’s Build A Simple Interpreter》笔记

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

为了实现统一访问全局变量和局部变量，本文将把 GLOBAL_MEMORY 字典替换成调用栈与活动记录。

调用栈

调用栈一个堆栈数据结构，将类似字典的对象作为其元素，用于跟踪当前正在执行的过程/函数调用。调用栈保存的类似字典的对象称为活动记录，也被称为“堆栈帧”或者“帧”。

class CallStack:
    def __init__(self):
        self._records = []

    def push(self, ar):
        self._records.append(ar)

    def pop(self):
        return self._records.pop()

    def peek(self):
        return self._records[-1]

    def __str__(self):
        s = '\n'.join(repr(ar) for ar in reversed(self._records))
        s = f'CALL STACK\n{s}\n'
        return s

    def __repr__(self):
        return self.__str__()

活动记录

活动记录是一个类似字典的对象，用于维护有关当前正在执行的过程或函数调用以及程序本身的信息。例如，过程调用的活动记录将包含其形式参数及其局部变量的当前值。

class ARType(Enum):
    PROGRAM   = 'PROGRAM'


class ActivationRecord:
    def __init__(self, name, type, nesting_level):
        self.name = name
        self.type = type
        self.nesting_level = nesting_level
        self.members = {}

    def __setitem__(self, key, value):
        self.members[key] = value

    def __getitem__(self, key):
        return self.members[key]

    def get(self, key):
        return self.members.get(key)

    def __str__(self):
        lines = [
            '{level}: {type} {name}'.format(
                level=self.nesting_level,
                type=self.type.value,
                name=self.name,
            )
        ]
        for name, val in self.members.items():
            lines.append(f'   {name:<20}: {val}')

        s = '\n'.join(lines)
        return s

    def __repr__(self):
        return self.__str__()

ActivationRecord 类构造函数接受三个参数：

• 活动记录的名称：本文将使用程序名称以及过程/函数名称作为相应活动记录的名称
• 激活记录的类型（例如 PROGRAM）：这些在称为 ARType（活动记录类型）的单独枚举类中定义
• 活动记录的嵌套级别：活动记录的嵌套级别对应于相应过程或函数声明的范围级别加一；对于程序，嵌套级别将始终设置为 1

interpreter 的改动

1. 用调用栈替换 GLOBAL_MEMORY 字典

class Interpreter(NodeVisitor):
    def __init__(self, tree):
        self.tree = tree
        self.call_stack = CallStack()

2. 更新 visit_Program 方法，使用调用栈来压入和弹出一个将保存全局变量值的活动记录

class Interpreter(NodeVisitor):
    def visit_Program(self, node):
        program_name = node.name

        # 创建一个活动记录
        ar = ActivationRecord(
            name=program_name,
            type=ARType.PROGRAM,
            nesting_level=1,
        )

        # 将活动记录压入调用栈，以便解释器的其余部分可以使用调用栈顶部的活动记录来存储和访问全局变量
        self.call_stack.push(ar)

        # 当解释器访问程序体时，它使用调用栈顶部的活动记录来存储和访问全局变量
        self.visit(node.block)

        # 从调用堆栈中弹出活动记录，因为此时解释器对程序的执行已经结束，可以安全地丢弃不再使用的活动记录
        self.call_stack.pop()

3. 更新 visit_Assign 方法，在调用栈顶部的活动记录中存储一个键值对

class Interpreter(NodeVisitor):
    def visit_Assign(self, node):
        var_name = node.left.value
        var_value = self.visit(node.right)

        ar = self.call_stack.peek()
        ar[var_name] = var_value

上面的代码使用 peek() 方法获取堆栈顶部的活动记录（visit_Program 方法压入堆栈的那个），然后使用该活动记录存储值 var_name:var_value 键值对。

4. 更新 visit_Var 方法以从调用栈顶部的活动记录中通过其名称访问值

class Interpreter(NodeVisitor):
    def visit_Var(self, node):
        var_name = node.value

        ar = self.call_stack.peek()
        var_value = ar.get(var_name)

        return var_value