实例教程,用python实现字节码编译器和解释器实例教程,用python实现字节码编译器和解释器

我们都知道编译源码需要词法分析、语法分析、语义分析与中间代码产生、优化和目标代码生成等五个过程。对于一个语言来说,有两个最重要功能,编译器和解释器。实现由源代码到字节码的转化,然后才能执行。本文中虫虫以CPython 3.6字节码为实例,实现一个我们自己的字节码编译器和解释器,以此来熟悉基本的编译器工作原理(),当然如果想深入理论学习,建议大家去学习了《编译原理》这本教材。

基本定义

首先,我们介绍一些简单的定义,以帮助区分解释器的类型:

树遍历解释器:逐节点地处理程序AST(abstract syntax tree,抽象语法数),基于某些评估规则进行递归评估。对于像Add(Lit 1,Lit 2)这样的程序,它可能会看到添加规则,递归地计算参数,将它们一起添加,然后将结果打包为适当的值类型。

字节码解释器不直接在AST上工作。他们研究预处理的AST。这简化了执行模型,可以产生令人印象深刻的速度。像Add(Lit 1,Lit 2)这样的程序会被编译成以下字节码:

PUSH 1

PUSH 2

ADD

然后解释器将按指令进行解析,这个过程有和CPU工作处理类似。

JIT解释器和字节码解释器一样,除了编译为特定于语言实现的字节码,它们尝试编译为本机的机器指令。大多数生产级JIT解释器会缓冲最多被调用的函数来"预热处理",然后在后台将它们编译为本机代码。所以 "热代码"会得到优化并且具有较小的性能损失。

树遍历解释器

Lisp解释器具有非常简单的语义。下面是一个Lisp REPL(read-eval-print-loop)示例,其中所有命令都被解析为AST,然后立即处理输出。

1

1

>>> "hello"

hello

>>> (val x 3)

None

3

>>> (set x 7)

None

7

>>> (if True 3 4)

3

>>> (lambda (x) (+ x 1))

>>> ((lambda (x) (+ x 1)) 5)

6

>>> (define f (x) (+ x 1))

None

>>> (f 10)

11

类似的,我们的解释器,首先编写一个名为compile的函数,它接受一个由Python列表表示的表达式(类似于['+',5,['+',3,5]])并返回一个列表字节码指令。然后我们将编写eval,它接受这些指令并返回一个Python值(在本例中为int 13)。除了更快之外,它应该与树遍历解释器的行为相同。

指令集

在我们的解释器中,我们还需要一组指令,为了便捷我们从CPython运行时指令集架构中直接带过来。 CPython是一个基于堆栈的架构,所以我们的解释器架构也是如此:

LOAD_CONST

将常量推入堆栈。

STORE_NAME

将值存储到环境中。

LOAD_NAME

从环境中读取值。

CALL_FUNCTION

调用函数(内置或用户定义)。

RELATIVE_JUMP_IF_TRUE

如果堆栈顶部的值为true,则跳转。

RELATIVE_JUMP

跳转。

MAKE_FUNCTION

从堆栈上的代码对象创建一个函数对象,并将其推送到堆栈上。

通过上述指令元语,我们来定义整个语言。一般情况下,在指令集中都会定义数学运算用来提高速度,此处我们将其定义为内置函数,因为它快速而简单。

Opcode枚举 和Instruction类

我们定义了一个Opcode枚举:

它的唯一目的是枚举所有可能的操作码,稍后我们会添加。Python的枚举API有点复杂,我们不再多说,你把他想象成一个个整数列表就好了。

接着,我们编写一个存储操作码和可选参数对的Instruction类:

我们为每个操作码定义一个指令实例,将制定好参数。然后,当字节码编译时,我们可以通过使用给定的参数调用它们,创建每个指令的实例:

创建父节点操作码:

STORE_NAME = Instruction(Opcode.STORE_NAME, "name")

创建实例:

[STORE_NAME("x"),STORE_NAME("y")]

定义好了编译基础设施,让我们开始编译。

整型

根据我们上面的基础,我们开始撰写编译函数:

现在,它还只是一个原型,没有啥用处。我们陆续扩展功能。

最简单的编译方法是整数。我先来给整数添加操作的指令,然后实现它。

LOAD_CONST,对应Python操作码,它可以做类似的操作。我们可以调用PUSH_CONST,在我看来更好地暗示它将被推送到VM堆栈。我们指定了CONST,因为该指令只应用于文本值:5,"hello"等。值由表达式本身完全定义。

这是Instruction类的并行(在模块范围定义):

LOAD_CONST = Instruction(Opcode.LOAD_CONST, "const")

参数名称"const"仅用于字节码文档。创建和执行该指令时,它将被实际值替换。接下来,让我们给compile函数添加功能:

compile将遍历表达式树并将已编译的子表达式中的指令列表合并在一起,因此每个分支都必须返回一个列表。当我们有嵌套的情况时,看起来会更好。我们调用测试一下:

既然我们已经有了指令,我们也应该能够运行它。我们写一个基本的eval循环:

pc是"程序计数器"的缩写,相当于术语"指令指针"。我们的想法是逐个遍历指令,并按顺序执行它们。

当它无法处理特定指令时,此循环将抛出,因此它是合理的脚手架,但不多。让我们添加一个实例来处理eval中的LOAD_CONST。

稍后我们会调用它,eval会返回堆栈顶部的值。这是我们开始。

assert eval(compile(5)) == 5

assert eval(compile(7)) == 7

现在我们在运行它:

命名

现在,我们的例程还不能做任何事情,唯一做的事是将一个数字推入堆栈的程序。下面让我们添加一些将这些值赋值给变量的操作码。

下面我们会添加指令STORE_NAME,它从堆栈中取出一个值并将其存储在当前环境中,还有LOAD_NAME,它从当前环境读取值并将其推送到堆栈中。

先来说说上面提到的环境概念,其抽象为一个Env类:

执行模型将为每个函数调用框架创建一个新的Env,并为每个闭包框架创建一个新的env,目前没有完全实现,请暂时忽略。

我们现在关心的是全局环境。我们将创建一个用于存储值的全局环境。然后我们将通过eval函数对其进行处理,以便我们可以使用它。先扩展commpile函数的功能:

我们新增加了第二个分支来检查表达式是否是一个列表。由于我们现在几乎没有错误处理,我还添加了一些断言以帮助简化代码。

在val的情况下,我们想要提取名称和子表达式:编译像5这样的简单值,还有(+ 1 2)类似的表达式。然后,我们要编译子表达式并添加STORE_NAME指令。

让我们测试一下我们能做什么:

assert compile(['val', 'x', 5]) == [LOAD_CONST(5), STORE_NAME('x')]

现在让我们回到eval函数:

注意到,我们添加一个env参数,以便我们可以在不同的上下文中计算表达式并获得不同的结果。我们还为STORE_NAME添加了一个实例。执行会报错:

为了,正常运行,我们必须修改,其他测试以传递一个env参数。

让我们创建第一个环境并测试STORE_NAME。

现在我们添加编译器和评估器功能来读取这些存储的值。编译器只需检查变量访问,表示为字符串。

并为它添加一个测试:

assert compile('x') == [LOAD_NAME('x')]

现在我们可以生成LOAD_NAME了,让我们为它添加eval支持。

为了测试它,我们首先手动将名称存储到环境中,然后查看LOAD_NAME是否可以将其读回。

内置函数

我们还可以按需添加函数操作码,或者添加一个操作码,允许我们调用本机(Python)代码并以这种方式扩展我们的解释器。

在该实例中,我们将添加CALL_FUNCTION操作码,它将用于内置函数和用户定义函数。我们稍后会介绍用户定义的函数。

当表达式的形式为(x0 x1 x2 ...)并且x0不是像val这样的预设识别名称之一时,将生成CALL_FUNCTION。编译器应生成代码以首先加载函数,然后将参数加载到堆栈中。然后CALL_FUNCTION指令。这与CPython的实现非常相似。

CALL_FUNCTION指令的定义如下:

CALL_FUNCTION = Instruction(Opcode.CALL_FUNCTION, "nargs")

CALL_FUNCTION指令带有传递给函数的参数个数,以便我们可以正确调用它。请注意,我们这样做而没有在函数中存储正确数量的参数,主要是这样函数就可以可以自持可变数量的参数。

我们扩充complie函数增加调用表达式功能。

我为列表表达式添加了一个默认情况。看到它编译名称,然后编译参数,然后发出一个CALL_FUNCTION。我们添加一些测试实例:

现在让我们同步扩充eval函数的功能:

请注意,我们正在从堆栈中读取参数是以相反的顺序从堆栈中读取的。这是堆栈的LIFO特性(先入后出)。

我们需要检查fn是否可调用。由于我们在堆栈上允许原始Python对象,因此我们必须确保我们实际上要调用Python函数。然后我们将使用参数列表调用该函数并将其结果推送到堆栈上。

以下是现实生活中的测试结果:

如果我们将lambda表达式填充到环境中,我们将获得这些超级简单的内置函数。但这不是最优+功能。让我们制作一个可变的变量。

因为我们将参数传递给列表,所以我们可以做各种类似的操作。

只提到过,我们在STORE_NAME中添加一个用于编译嵌套表达式的测试。

你还可以随心所以添加自己需要的内置函数,比如添加print功能:

应该能看到以正确顺序传递的参数。注意,如果使用的是Python 2,则应将print打包在lambda中,在Python 2 语法中print不是函数。

条件语句

如果没有条件,一个语言就做不了啥事。虽然我们可以将条件作为内置函数。但是我们在这选择更正常的传统条件语法:

(if a b c)

会被编译为

我们还将采用CPython方法生成相对跳转JUMP。

为此,我们需要新添加两个操作码和说明:

RELATIVE_JUMP_IF_TRUE = Instruction(Opcode.RELATIVE_JUMP_IF_TRUE, "off")

RELATIVE_JUMP = Instruction(Opcode.RELATIVE_JUMP, "off")

它们中的每一个都采用偏移量来表示跳转的距离。

我们的编译器函数需要新增加:

首先编译条件。然后,编译将在条件通过时执行的分支。 if-false分支有点棘手,那里包含了跳转到结尾。这是为了跳转到if-true分支的偏移计算是正确。

同样我们添加一些测试来检查我们的工作:

我们特意添加了第二个测试来仔细检查嵌套表达式是否正常工作。

增加eval函数的功能:

对应的测试案例:

自定义函数

用户定义的函数对于一个语言是否真正可以用很关键。我们一个简单的Function对象。

params将是一个命名元组,body是一个指令元组,env是一个环境。

所有函数都是一个闭包。可以引用定义函数的范围中定义的变量。基本格式如下:

((lambda (x) (+ x 1)) 5)

或者为:

(define inc (x) (+ x 1))

(inc 5)

实际上,我们将使用语法转换来根据val和lambda重写定义。

要实现这些功能,我们需要新增加操作码:MAKE_FUNCTION。该指令会将在堆栈中的一些对象转换为Function对象。

MAKE_FUNCTION = Instruction(Opcode.MAKE_FUNCTION, "nargs")

这需要一个整数,即函数所期望的参数数量。现在我们只允许位置,非可选参数。如果我们想要有额外的调用约定,我们必须稍后添加它们。

来给complie增加功能:

对于lambda来说,它非常简单。push参数,push body代码,然后就可以用。

define有点小技巧。他是一个宏并在编译之前重写AST。如果我们想要更专业,需要新建一个宏系统,以便标准库可以定义define和if ...这超出本文范围。

测试代码:

为了让功能真正可用,我们给eval函数增加处理MAKE_FUNCTION操作码。

与调用函数一样,我们按照push顺序的相反方式读取所有内容。首先是body,然后是参数,检查他的长度,然后push新的Function对象。

但是函数在没有可调用的情况下并不是特别有用。为了让其调用实现功能:

第一个策略是简单的策略,即在CALL_FUNCTION中添加另一个处理Function对象的案例。这大多数编程语言中都是这样的:

请注意,函数环境仅由给定的参数组成,其父元素是存储的环境 - 而不是当前的环境。

另一种方法更像是Pythonic。它将Function转换为可调用对象,将自定义设置代码放入Function本身。如果选择这样做,请单独保留CALL_FUNCTION并以这种方式修改Function:

然后eval应该调用函数,就像它是一个普通的Python函数一样。

测试用例:

最后,我们写一个递归函数实例:

表达式列表

编写一个可以获取表达式列表,编译表达式并加函数compile_program就更好。所以我们还要添加一个begin关键字。

编译函数增加对应功能:

本文中,我们使用Python实例编写了一个字节码编译和解释器,用以说明相应的编译原理,和开头提到的一样,基本原理适用于任何语言,你可以使用你最那首的语言Perl,golang,rust,js甚至是R来实现自己的例子。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190104A0ZUHX00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券