如何用Python,来解释Python运行，实现Python解释器

Stubborn · 发表于 2020-6-6 14:15:32

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 Stubborn 于 2020-6-6 14:17 编辑

实现Python解释器

Python解释器是如何工作的？

Python解释器是一个虚拟机,模拟真实计算机的软件。我们这个虚拟机是栈机器，它用几个栈来完成操作（与之相对的是寄存器机器，它从特定的内存地址读写数据）。

Python解释器是一个字节码解释器：它的输入是一些命令集合称作字节码。当你写Python代码时，词法分析器，语法解析器和编译器生成code object让解释器去操作。每个code object都包含一个要被执行的指令集合 --- 它就是字节码 --- 另外还有一些解释器需要的信息。字节码是Python代码的一个中间层表示：它以一种解释器可以理解的方式来表示源代码。这和汇编语言作为C语言和机器语言的中间表示很类似。

示例：

Python 3.7.5 (default, Nov  1 2019, 02:16:38) 
[Clang 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def loop():
...     x = 0
...     while x<5:
...         if x == 4:
...             break
...         x = x +1
...         print(x)
...     return
... 
>>> loop.__code__.co_code
b'd\x01}\x00x&|\x00d\x02k\x00r*|\x00d\x03k\x02r\x18P\x00|\x00d\x04\x17\x00}\x00t\x00|\x00\x83\x01\x01\x00q\x06W\x00d\x00S\x00'
>>> list(loop.__code__.co_code)
[100, 1, 125, 0, 120, 38, 124, 0, 100, 2, 107, 0, 114, 42, 124, 0, 100, 3, 107, 2, 114, 24, 80, 0, 124, 0, 100, 4, 23, 0, 125, 0, 116, 0, 124, 0, 131, 1, 1, 0, 113, 6, 87, 0, 100, 0, 83, 0]
>>>

上面，我们可以得到一段代码的字节码，你看不懂？没事，我也看不懂。在看下另外一段代码。

>>> import dis
>>> dis.dis(loop)
  2           0 LOAD_CONST               1 (0)
              2 STORE_FAST               0 (x)

  3           4 SETUP_LOOP              38 (to 44)
        >>    6 LOAD_FAST                0 (x)
              8 LOAD_CONST               2 (5)
             10 COMPARE_OP               0 (<)
             12 POP_JUMP_IF_FALSE       42

  4          14 LOAD_FAST                0 (x)
             16 LOAD_CONST               3 (4)
             18 COMPARE_OP               2 (==)
             20 POP_JUMP_IF_FALSE       24

  5          22 BREAK_LOOP

  6     >>   24 LOAD_FAST                0 (x)
             26 LOAD_CONST               4 (1)
             28 BINARY_ADD
             30 STORE_FAST               0 (x)

  7          32 LOAD_GLOBAL              0 (print)
             34 LOAD_FAST                0 (x)
             36 CALL_FUNCTION            1
             38 POP_TOP
             40 JUMP_ABSOLUTE            6
        >>   42 POP_BLOCK

  8     >>   44 LOAD_CONST               0 (None)
             46 RETURN_VALUE
>>>

他们格式对应是这样的：
源码行号 | 跳转注释符 | 指令在函数中的偏移 | 指令符号（助记符） | 指令参数 | 实际参数值

首先我们看下源码行号为4的代码块，相信学习过Python的朋友，能一眼看出，这是在描述<if x == 4:>这行代码的解释。这四行代码的解释是这样的。
  4       14 LOAD_FAST             0 (x)          ==>>加载_FAST，x是一个变量，所以这里是加载一个x的变量
         16 LOAD_CONST             3 (4)       ==>>加载——CONST，4是一个常量，这里是加载一个4的常量
         18 COMPARE_OP             2 (==)    ==>>COMPARE_OP，进行比较操作，x == 4 吗？
         20 POP_JUMP_IF_FALSE    24       ==>>结果是False，进行跳转，跳转到 24(值函数的中的偏移)
                                                                  ==>> 24 即第六行的源码。x = x + 1

然后在回头看下我们code object对象。这个列表对于我们又什么用处

[100, 1, 125, 0, 120, 38, 124, 0, 100, 2, 107, 0, 114, 42, 124, 0, 100, 3, 107, 2, 114, 24, 80, 0, 124, 0, 100, 4, 23, 0, 125, 0, 116, 0, 124, 0, 131, 1, 1, 0, 113, 6, 87, 0, 100, 0, 83, 0]

第一个100，为命令的索引，dis.opname[100]就可以得到 LOAD_CONST 命令。
第二个1， 为指令为指令参数。LOAD_CONST是常量集。 这个指令参数，告诉我们，如何从常量集中，取出对应的参数。cond.__code__.co_consts[1]就可以取到0

第三个125，为命令的索引，dis.opname[125]就可以得到 STORE_FAST 命令。
第四个0，为指令参数。作用同上，cond.__code__.co_varnames[0]

好了，如果看完这里了，我们开始写一个简单的Python解释器吧！？？？？？？？（小朋友，你是否有很多问好）

我们来解释下这个代码：

5+7

假设我们得到一个这样的指令集

what_to_execute = {
    "instructions": [("LOAD_VALUE", 0),  # the first number
                     ("LOAD_VALUE", 1),  # the second number
                     ("ADD_TWO_VALUES", None),
                     ("PRINT_ANSWER", None)],
    "numbers": [7, 5] }

Python解释器是一个栈机器，所以它必须通过操作栈来完成这个加法。(Figure 1.1)解释器先执行第一条指令，LOAD_VALUE，把第一个数压到栈中。接着它把第二个数也压到栈中。然后，第三条指令，ADD_TWO_VALUES,先把两个数从栈中弹出，加起来，再把结果压入栈中。最后一步，把结果弹出并输出。

LOAD_VALUE这条指令告诉解释器把一个数压入栈中，但指令本身并没有指明这个数是多少。指令需要一个额外的信息告诉解释器去哪里找到这个数。所以我们的指令集有两个部分：指令本身和一个常量列表。（在Python中，字节码就是我们称为的“指令”，而解释器执行的是code object。）

为什么不把数字直接嵌入指令之中？想象一下，如果我们加的不是数字，而是字符串。我们可不想把字符串这样的东西加到指令中，因为它可以有任意的长度。另外，我们这种设计也意味着我们只需要对象的一份拷贝，比如这个加法 7 + 7, 现在常量表 "numbers"只需包含一个7。

你可能会想为什么会需要除了ADD_TWO_VALUES之外的指令。的确，对于我们两个数加法，这个例子是有点人为制作的意思。然而，这个指令却是建造更复杂程序的轮子。比如，就我们目前定义的三个指令，只要给出正确的指令组合，我们可以做三个数的加法，或者任意个数的加法。同时，栈提供了一个清晰的方法去跟踪解释器的状态，这为我们增长的复杂性提供了支持。

现在让我们来完成我们的解释器。解释器对象需要一个栈，它可以用一个列表来表示。它还需要一个方法来描述怎样执行每条指令。比如，LOAD_VALUE会把一个值压入栈中。

class Interpreter:
    def __init__(self):
        self.stack = []

    def LOAD_VALUE(self, number):
        self.stack.append(number)

    def PRINT_ANSWER(self):
        answer = self.stack.pop()
        print(answer)

    def ADD_TWO_VALUES(self):
        first_num = self.stack.pop()
        second_num = self.stack.pop()
        total = first_num + second_num
        self.stack.append(total)/code]

这三个方法完成了解释器所理解的三条指令。但解释器还需要一样东西：一个能把所有东西结合在一起并执行的方法。这个方法就叫做run_code, 它把我们前面定义的字典结构what-to-execute作为参数，循环执行里面的每条指令，如何指令有参数，处理参数，然后调用解释器对象中相应的方法

[code]    def run_code(self, what_to_execute):
        instructions = what_to_execute["instructions"]
        numbers = what_to_execute["numbers"]
        for each_step in instructions:
            instruction, argument = each_step
            if instruction == "LOAD_VALUE":
                number = numbers[argument]
                self.LOAD_VALUE(number)
            elif instruction == "ADD_TWO_VALUES":
                self.ADD_TWO_VALUES()
            elif instruction == "PRINT_ANSWER":
                self.PRINT_ANSWER()

为了测试，我们创建一个解释器对象，然后用前面定义的 7 + 5 的指令集来调用run_code。

    interpreter = Interpreter()
    interpreter.run_code(what_to_execute)

显然，它会输出12

尽管我们的解释器功能受限，但这个加法过程几乎和真正的Python解释器是一样的。这里，我们还有几点要注意。

首先，一些指令需要参数。在真正的Python bytecode中，大概有一半的指令有参数。像我们的例子一样，参数和指令打包在一起。注意指令的参数和传递给对应方法的参数是不同的。

第二，指令ADD_TWO_VALUES不需要任何参数，它从解释器栈中弹出所需的值。这正是以栈为基础的解释器的特点。

如果我说这里写完了，你肯定会说，What???

这么简单，一看就会是不是

Stubborn · 发表于 2020-6-6 14:18:30

本帖最后由 Stubborn 于 2020-6-6 14:48 编辑

我们的目的就是，实现这个函数，最终效果就是,打印 2 3 4 4，不要问我为什么不直接用exec(),这还有问，用了我咋知道，Python解释器怎么解释函数运行的啊（吃饱了撑的啊）

    code = """
def loop():
    x = 1
    while x < 5:
        if x==4:
            break
        x = x + 1
        print(x)
    return x
print(loop())
"""

Byterun 中有 4 种主要的类型对象：

VirtualMachine类，管理最高层的结构，特别是调用栈，同时管理指令到操作的映射，是最开始写的 Interpreter 类的高级版本。
Frame 类，每一个 Frame 对象都维护一个 code object 引用，并管理一些必要的状态信息，例如全局与局部的命名空间，以及对调用它自身的帧的引用和最后执行的字节码
Function 类，我们实现 Function 来控制新的帧的创建。
Block 类，一个只包装了三个属性的类，控制代码流程的时候会用到。
InstructionSet 是VirtualMachine类的基类，主要负责实现一些指令集命令，和栈的基本操作

The Frame Class

frame是一个属性的集合，它没有任何方法。前面提到过，这些属性包括由编译器生成的code object；局部，全局和内置命名空间；前一个frame的引用；一个数据栈；一个块栈；最后执行的指令。（对于内置命名空间我们需要多做一点工作，Python对待这个命名空间不同；但这个细节对我们的虚拟机不重要。）

class Frame(object):
    def __init__(self, code_obj, globals, locals, prev_frame):
        """
        栈帧对象
        维护一个 code object 引用
        并管理一些必要的状态信息例如全局与局部的命名空间以及对调用它自身的帧的引用和最后执行的字节码

        self.code_obj --> 由编译器生成的 code object
        self.globals --> 全局的命名空间
        self.locals --> 局部的命名空间
        self.builtins -->内置命名空间
        self.prev_frame --> 前一个frame的引用
        self.stack --> 数据栈
        self.block_stack --> 块栈
        self.pointer  -->执行命令的指针
        """
        self.code_obj = code_obj
        self.globals = globals
        self.locals = locals
        self.prev_frame = prev_frame
        self.stack = []

        if prev_frame:
            self.builtins = prev_frame.builtins
        else:
            self.builtins = locals['__builtins__']
            if hasattr(self.builtins, '__dict__'):
                self.builtins = self.builtins.__dict__

        self.pointer = 0
        self.block_stack = []

The Function and Block Class

Function的实现有点扭曲，但是大部分的细节对理解解释器不重要。重要的是当调用函数时 --- __call__方法被调用 --- 它创建一个新的Frame并运行它。

Block = namedtuple("Block", "type, handler, stack_height")


def make_cell(value):
    # TODO: 创建一个真实的Python闭包并获取一个单元格。
    fn = (lambda x: lambda: x)(value)
    return fn.__closure__[0]


class Function(object):
    __slots__ = [
        'func_code', 'func_name', 'defaults', 'globals',
        'locals', 'func_dict', 'func_closure',
        '__name__', '__dict__',
        '_vm', '_func',
    ]

    def __init__(self, name, code, globs, defaults, closure, vm):
        """
        name ->  函数的名字    str object
        code ->  函数的主体对象，code object
        globs -> 函数的全局变量 tuple object
        defaults-> 函数的默认参数 tuple object
        closure -> 闭包函数体 function object
        vm -> 解释器  VirtualMachine object
        """
        # code ==>>>>> <code object loop at 0x11c280030, file "tmp", line 2>

        self._vm = vm
        self.func_code = code
        self.func_name = self.__name__ = name or code
        self.defaults = tuple(defaults)
        self.globals = globs
        self.locals = self._vm.frame.locals
        self.__dict__ = {}
        self.func_closure = closure
        self.__doc__ = code.co_consts[0] if code.co_consts else None

        kw = {
            'argdefs': self.defaults,
        }
        if closure:
            kw['closure'] = tuple(make_cell(0) for _ in closure)
        self._func = types.FunctionType(code, globs, **kw)

    def __call__(self, *args, **kwargs):
        """
        定义函数的调用时，创建一个新的Frame对象，并运行它
        """
        args = inspect.getcallargs(self._func, *args, **kwargs)
        # TODO:使用args提供参数映射：值以传递给新的栈帧
        frame = self._vm.make_frame(
            self.func_code, args, self.globals, {}
        )
        return self._vm.run_frame(frame)

The InstructionSet Class

class InstructionSet:
    """
    指令方法集
    """

    # TODO: Operators

    UNARY_OPERATORS = {
        'POSITIVE': operator.pos,
        'NEGATIVE': operator.neg,
        'NOT': operator.not_,
        'CONVERT': repr,
        'INVERT': operator.invert,
    }
    BINARY_OPERATORS = {
        'POWER': pow,
        'MULTIPLY': operator.mul,
        'DIVIDE': getattr(operator, 'div', lambda x, y: None),
        'FLOOR_DIVIDE': operator.floordiv,
        'TRUE_DIVIDE': operator.truediv,
        'MODULO': operator.mod,
        'ADD': operator.add,
        'SUBTRACT': operator.sub,
        'SUBSCR': operator.getitem,
        'LSHIFT': operator.lshift,
        'RSHIFT': operator.rshift,
        'AND': operator.and_,
        'XOR': operator.xor,
        'OR': operator.or_,
    }
    COMPARE_OPERATORS = [
        operator.lt,
        operator.le,
        operator.eq,
        operator.ne,
        operator.gt,
        operator.ge,
        lambda x, y: x in y,
        lambda x, y: x not in y,
        lambda x, y: x is y,
        lambda x, y: x is not y,
        lambda x, y: issubclass(x, Exception) and issubclass(x, y),
    ]

    def __init__(self):
        self.frames = []
        self.frame = None
        self.value = None

    def jump(self, jump):
        """指令跳转指针"""
        self.frame.pointer = jump

    # TODO  栈帧基本操作
    def push_frame(self, *args):
        self.frame.stack.extend(args)

    def pop_frame(self):
        return self.frame.stack.pop()

    def pops_frame(self, n):
        if n:
            ret = self.frame.stack[-n:]
            self.frame.stack[-n:] = []
            return ret
        else:
            return []

    def pop_frames(self):
        self.frames.pop()
        if self.frames:
            self.frame = self.frames[-1]
        else:
            self.frame = None

    #  TODO  指令集
    def make_function(self, argc):
        """
        创建一个Function对象，并压入栈
        """

        name = self.pop_frame()
        code = self.pop_frame()
        defaults = self.pops_frame(argc)
        globs = self.frame.globals
        fn = Function(name, code, globs, defaults, None, self)
        self.push_frame(fn)

    def load_const(self, const):
        """压栈const常量"""
        self.push_frame(const)

    def load_name(self, name):
        """加载一个name变量,如果不存在，抛出异常"""
        if name in self.frame.locals:
            val = self.frame.locals[name]
        elif name in self.frame.globals:
            val = self.frame.globals[name]
        elif name in self.frame.builtins:
            val = self.frame.builtins[name]
        else:
            raise NameError("name '%s' is not defined" % name)
        self.push_frame(val)

    def load_global(self, name):
        """加载一个name变量,如果不存在，抛出异常"""
        if name in self.frame.globals:
            val = self.frame.globals[name]
        elif name in self.frame.builtins:
            val = self.frame.builtins[name]
        else:
            raise NameError("name '%s' is not defined" % name)
        self.push_frame(val)

    def load_fast(self, name):
        """从locals取出一个name值, 压栈"""
        if name in self.frame.locals:
            val = self.frame.locals[name]
        else:
            raise UnboundLocalError(
                "local variable '%s' referenced before assignment" % name
            )
        self.push_frame(val)

    def store_name(self, name):
        """给name变量赋值，添加到Frame的全局变量空间"""
        self.frame.locals[name] = self.pop_frame()

    store_fast = store_name

    def call_function(self, arg):
        """调用用函数,把结果压入栈帧"""
        _, pops = divmod(arg, 256)
        args = self.pops_frame(pops)
        func = self.pop_frame()
        r = func(*args)

        self.push_frame(r)

    def compare_op(self, index):
        """比较运算操作"""
        x, y = self.pops_frame(2)
        self.push_frame(
            self.COMPARE_OPERATORS[index](x, y)
        )

    def pop_jump_if_false(self, jump):
        val = self.pop_frame()
        if not val:
            self.frame.pointer = jump

    def jump_absolute(self, jump):
        self.jump(jump)

    def binary_add(self, *args):
        x, y = self.pops_frame(2)
        self.push_frame(x + y)

    def pop_top(self, *args):
        self.pop_frame()

    def return_value(self, *args):
        """设置返回值"""

        self.value = self.pop_frame()
        return 'return'

    def break_loop(self, *args):
        return 'break'

    def setup_loop(self, dest):
        stack_height = len(self.frame.stack)
        self.frame.block_stack.append(Block('loop', dest, stack_height))

Stubborn · 发表于 2020-6-6 14:20:57

本帖最后由 Stubborn 于 2020-6-6 14:53 编辑

class VirtualMachine(InstructionSet):

    def run_code(self, code, globals=None, locals=None):
        """
        运行 Python 程序的入口，程序编译后生成 code_obj
        这里 code_obj 在参数 code 中
        run_code 根据输入的 code_obj 新建一个 frame 并开始运行
        """
        frame = self.make_frame(code, globals, locals)
        self.run_frame(frame)

    def make_frame(self, code, callargs=None, globals=None, locals=None):
        """
        创建一个栈帧对象
        """
        callargs = {} if callargs is None else callargs

        if globals is not None and locals is None:
            locals = globals

        elif self.frames:
            globals = self.frame.globals
            locals = dict()

        else:
            globals = locals = {
                '__builtins__': __builtins__,
                '__name__': '__main__',
                '__doc__': None,
                '__package__': None,
            }

        locals.update(callargs)
        frame = Frame(
            code_obj=code,
            globals=globals,
            locals=locals,
            prev_frame=self.frame
        )
        return frame

    def run_frame(self, frame):
        self.frames.append(frame)
        self.frame = frame

        while True:
            # TODO: args = [指令名字，参数]
            method, args = self.parse()
            why = self.dispatch(method, args)

            while why and frame.block_stack:
                why = self.manage(why)

            if why:
                break

        self.pop_frames()

        return self.value

    def parse(self):
        """
        获取指令，以及参数
        """
        code_obj = self.frame.code_obj
        pointer = self.frame.pointer

        byte, arg = code_obj.co_code[pointer: pointer + 2]
        byte_name = dis.opname[byte]

        self.frame.pointer += 2

        if byte in dis.hasconst:
            # TODO: 如果指令是常量集参数，取出一个对应的常量
            arg = code_obj.co_consts[arg]

        elif byte in dis.hasname:
            # TODO: 如果指令是变量集参数，取出一个对应的变量
            arg = code_obj.co_names[arg]

        elif byte in dis.haslocal:
            # TODO: 如果指令是局部变量集参数，取出一个对应的局部变量
            arg = code_obj.co_varnames[arg]
        elif byte in dis.hasjrel:
            # TODO: 如果指令是跳转指令，计算跳转位置
            arg = self.frame.pointer + arg

        args = [arg]
        # TODO : 测试指令，以及传递的指令参数  print(f"byte<::>{byte_name:}\targs<::>{args:}")
        return byte_name, args

    def error(self):
        raise AttributeError(
            f"type object '{self.__name__}' has no attribute '{self.method}'"
        )

    def dispatch(self, method, args):
        """
        dispatch 对于给出的指令调用相应的方法，这在 CPython 的 C 语言实现中使用 switch 写了 1500 多行，好像怪吓人的，
            但是我们用Python，getattr 可以根据指令名动态查找并调用对应方法。这里假设指令为 FOO_BAR ，
            对应方法名为 byte_FOO_BAR ，每个方法都会返回 None 或者一个名为 why 的字符串（这与帧调用返回时的返回值不同），
            why 会用来记录一些内部指标或者解释器状态。
        """
        self.method = function_obj = getattr(self, method.lower(), self.error)
        why = function_obj(*args)

        return why

    def manage(self, why):
        """
        管理一个 frame 的 block 栈
        在循环、异常处理、返回这几个方面操作 block 栈与数据栈
        """
        frame = self.frame
        block = frame.block_stack[-1]
        if block.type == 'loop' and why == 'continue':
            self.jump(self.return_value)
            why = None
            return why

        self.frame.block_stack.pop()
        self.unwind_block(block)

        if block.type == 'loop' and why == 'break':
            why = None
            self.jump(block.handler)
            return why

        if (block.type in ['setup-except', 'finally'] and why == 'exception'):
            height = len(self.frame.stack)
            self.frame.block_stack.append(Block('except-handler', handler=None, stack_height=height))

            exctype, value, tb = self.last_exception
            self.push_frame(tb, value, exctype)
            self.push_frame(tb, value, exctype)  # yes, twice
            why = None
            self.jump(block.handler)
            return why

        elif block.type == 'finally':
            if why in ('return', 'continue'):
                self.push_frame(self.return_value)

            self.push_frame(why)

            why = None
            self.jump(block.handler)
            return why
        return why

    def unwind_block(self, block):
        """展开与给定块相对应的数据堆栈上的值"""
        if block.type == 'except-handler':
            # TODO: 异常本身作为类型、值和回溯在堆栈上。
            offset = 3
        else:
            offset = 0

        while len(self.frame.stack) > block.stack_height + offset:
            self.pop_frame()

        if block.type == 'except-handler':
            traceback, value, exctype = self.pops_frame(3)
            self.last_exception = exctype, value, traceback

Stubborn · 发表于 2020-6-6 14:55:36

最后，我们附上测试代码，可以愉快的看到屏幕输出了，在这里，还要说，鱼友还可以在这个代码的基础上，扩展，进一步的全面解释Python运行，而不是解释一个loop函数
2
3
4
4

if __name__ == '__main__':
    code = """
def loop():
    x = 1
    while x < 5:
        if x==4:
            break
        x = x + 1
        print(x)
    return x
print(loop())
"""
    # compile 能够将源代码编译成字节码
    code_obj = compile(code, "tmp", "exec")
    vm = VirtualMachine()
    vm.run_code(code_obj)

SHRS23 · 发表于 2020-6-6 16:12:57

套…套娃？

账号		自动登录	找回密码
密码			立即注册

[技术交流] 如何用Python,来解释Python运行，实现Python解释器

马上注册，结交更多好友，享用更多功能^_^

评分

解释一个简单的函数

The VirtualMachine Class