实践贴：如何编写一个简单的Python编译器-InfoQ

本文最初发表在 Medium 博客，经原作者 Max Gorynski 授权，InfoQ 中文站翻译并分享。

在本文中，我们将用 Python 编写一个 Python 到 C 的编译器。这一点特别容易做到，因为 Python 有一个内置的解析器库，并且许多CPython内部构件对编写扩展程序来说都是公开的。

到本文的最后，通过几百行 Python 代码，我们将能够编译并运行以下程序：

$ cat tests/recursive_fib.pydef fib(n):    if n == 0 or n == 1:        return n    return fib(n - 1) + fib(n - 2)
def main():    print(fib(40))$ python3 pyc tests/recursive_fib.py$ ./bin/a.out102334155

复制代码

本文实现了一个非常小的 Python 子集，甚至完全放弃了管理内存的尝试，因为我无法理解手动引用计数。也许有一天我能找到一种方法来实现简单 GC 的交换，像 Boehm 那样。

这个项目的源代码可以在Github上找到。

依赖

我们需要 Python3、GCC、libpython3 和 clang-format。

在基于 Fedora 的系统上，执行命令如下：

$ sudo dnf install gcc python3-devel clang-format python3

复制代码

在基于 Debian 的系统上，则需执行如下命名：

$ sudo apt install gcc python3-dev clang-format python3

复制代码

该程序在Windows、Mac、FreeBSD等系统上可能也能正常运行，但是我还没有测试过（或提供自定义的编译器指令）。欢迎大家进行PR！

手写的第一遍

在进入编译器之前，让我们用 C 语言使用 libpython 手工编写一个斐波纳契数列（fibonacci）。

正如Python嵌入式指南所描述的那样，我们需要包含 libpython 并在main.c中初始化它：

#define PY_SSIZE_T_CLEAN#include <Python.h>int main(int argc, char *argv[]) {  Py_Initialize();  return 0;}

复制代码

为了针对 libpython 进行编译，我们将在python3-devel中安装python3-config，并使用它来告诉我们编译过程中的每一步应该输入什么内容。

$ gcc -c -o main.o $(python3-config --cflags) main.c$ gcc $(python3-config --ldflags) main.o$ ./a.out; echo $?0

复制代码

太酷了！现在，我们考虑翻译斐波纳契数列的实现，我们希望尽可能长时间地将所有内容作为 Python 对象进行保留。这意味着需要在所有函数之间传递和接收PyObject*，并将所有 C 的整数转换为PyLong* （其为PyObject*的“子类型”）。可以想象在你对其进行操作之前，Python 中的所有内容都是一个object。

有关Python中对象的更多信息，请查看Python文档中的“数据模型”页面。

要将一个 C 的整数映射到一个PyLong*，我们使用PyLong_FromLong。反向映射，我们使用PyLong_AsLong。

要比较两个PyObject*，我们可以使用PyObject_RichCompareBool，它可以在不考虑参数类型的情况对这两个参数进行比较。如果没有这个辅助函数，我们将不得不编写复杂的检查来确保两边相同，如果相同，则将它们解包为它们的基础 C 值并比较 C 值。

我们可以使用PyNumber_Add和PyNumber_Subtract来进行基本的算术运算，还有许多类似的辅助函数可供我们进行后续操作。

现在我们可以编写翻译程序了：

#define PY_SSIZE_T_CLEAN#include <Python.h>PyObject* fib(PyObject* n) {  PyObject* zero = PyLong_FromLong(0);  PyObject* one = PyLong_FromLong(1);  if (PyObject_RichCompareBool(n, zero, Py_EQ) || PyObject_RichCompareBool(n, one, Py_EQ)) {    return n;  }  PyObject* left = fib(PyNumber_Subtract(n, one));  PyObject* two = PyLong_FromLong(2);  PyObject* right = fib(PyNumber_Subtract(n, two));  return PyNumber_Add(left, right);}int main(int argc, char *argv[]) {  Py_Initialize();  PyObject* res = fib(PyLong_FromLong(7)); // Should be 13  return PyLong_AsLong(res);}

复制代码

编译并运行它：

$ gcc -c -o main.o $(python3-config --cflags) main.c$ gcc $(python3-config --ldflags) main.o$ ./a.out; echo $?13

复制代码

非常棒！但是我们在某个地方作弊了。我们假设fib函数的输入是一个整数，并且将这个假设传播到了所有编写了PyNumber_ *操作的地方。当我们编写编译器时，在调用数字辅助函数之前，需要检查两个参数是否都是整数，否则可能需要调用字符串连接辅助函数或其他完全相同的函数。

编译器架构

我们将代码分为四个主要部分：

libpyc.c：生成代码的辅助函数
pyc/context.py：作用域和在内存中编码的实用程序
pyc/codegen.py：从Python AST生成C代码
pyc/__main__.py：启动入口（entrypoint）

当我使用现有的解析器编写新的编译器时，我几乎总是从启动入口和代码生成器开始，这样我就可以研究AST了。但是，如果我们先从实用程序开始，那么解释代码是最容易的。

我们还需要一个空的pyc/__init__.py。

libpyc.c

这个 C 文件中将包含三个辅助函数，用于进行安全地加法、减法和打印操作。它将被连接到生成的 C 文件的顶部。目前，我们仅支持整数，但是此结构为以后支持更多类型打下了基础。

在调用特定于数字的方法之前，我们将使用PyLong_Check。

#define PY_SSIZE_T_CLEAN#include <Python.h>inline PyObject* PYC_Add(PyObject* l, PyObject* r) {  // TODO: allow __add__ override  // Includes ints and bools  if (PyLong_Check(l) && PyLong_Check(r)) {    return PyNumber_Add(l, r);  }  // TODO: handle str, etc.  // TODO: throw exception  return NULL;}inline PyObject* PYC_Sub(PyObject* l, PyObject* r) {  // TODO: allow __add__ override  // Includes ints and bools  if (PyLong_Check(l) && PyLong_Check(r)) {    return PyNumber_Subtract(l, r);  }  // TODO: handle str, etc.  // TODO: throw exception  return NULL;}inline PyObject* PYC_Print(PyObject* o) {  PyObject_Print(o, stdout, Py_PRINT_RAW);  printf("\n");  return Py_None;}

复制代码

就是这样！我们可以在 Python 中将它们生成为字符串，但这样做会很麻烦。通过使用一个专用的 C 文件，我们可以利用语法突出显示功能，因为这个文件只是 C 代码。并且由于我们已将所有函数标记为内联函数（inline），因此在 Python 中不将这些函数作为字符串嵌入是没有任何运行时成本的。

pyc/context.py

该文件将包含一个Context类，用于管理作用域中的标识符，并将其代理给一个包含了编写 C 代码行辅助函数的Writer类。

我们将在Context中拥有Writer类的两个实例，这样我们就可以写入主体（或当前/主要）区域和初始化区域。

如果有任何变量声明在了顶层，则必须使用初始化区域。我们不能在函数外用 C 语言初始化这些变量，因为每个PyObject*都必须在调用Py_Initialize之后创建。在进入编译后的 Pythonmain函数之前，这一部分将被写入 C 的main函数中。

import copy
class Writer():    content = ""    def write(self, exp: str, indent: int = 0):        self.content += ("  " * indent) + exp    def writeln(self, stmt: str, indent: int = 0):        self.write(stmt + "\n", indent)    def write_statement(self, stmt: str, indent: int = 0):        self.writeln(stmt + ";", indent)
class Context():    initializations = Writer()    body = Writer()    indentation = 0    scope = 0    ret = None    namings = {}    counter = -1    def __getattr__(self, name: str) -> object:        # Helpers to avoid passing in self.indentation every time        outputs = [initializations", "body"]        for output in outputs:            if name.startswith(output):                return lambda s, i=None: getattr(getattr(self, output), name[len(output)+1:])(s, i if i is not None else self.indentation)        return object.__getattr__(self, name)    def get_local(self, source_name: str) -> dict:        return self.namings[source_name]    def register_global(self, name: str, loc: str):        self.namings[name] = {            "name": loc,            "scope": 0,        }    def register_local(self, local: str = "tmp") -> str:        self.counter += 1        self.namings[local] = {            "name": f"{local}_{self.counter}",            # naming dictionary is copied, so we need to capture scope            # at declaration            "scope": self.scope,        }        return self.namings[local]["name"]    def copy(self):        new = copy.copy(self)        # For some reason copy.deepcopy doesn't do this        new.namings = dict(new.namings)        return new    def at_toplevel(self):        return self.scope == 0

复制代码

这些都是很无聊的样板代码。我们继续吧。

pyc/main.py

启动入口（entrypoint）负责读取源代码、解析源代码、调用代码生成器、将源代码写入 C 文件并进行编译。

首先，读取并解析源代码：

import astimport osimport subprocessimport shutilimport sysfrom context import Contextfrom codegen import generateBUILTINS = {    "print": "PYC_Print",}
def main():    target = sys.argv[1]    with open(target) as f:        source = f.read()    tree = ast.parse(source, target)

复制代码

然后，我们将libpyc.c写入主体部分，注册内建函数，并运行代码生成器：

...def main()    ...    ctx = Context()    with open("libpyc.c") as f:        ctx.body_write(f.read() + "\n")    for builtin, fn in BUILTINS.items():        ctx.register_global(builtin, fn)    generate(ctx, tree)

复制代码

接下来，我们创建一个干净的输出目录，并用生成的代码编写main.c和main函数来初始化 Python 和所有的全局变量：

...def main():   ...    # Create and move to working directory    outdir = "bin"    shutil.rmtree(outdir, ignore_errors=True)    os.mkdir(outdir)    os.chdir(outdir)    with open("main.c", "w") as f:        f.write(ctx.body.content)        main = ctx.namings.get("main")["name"]        f.write(f"""int main(int argc, char *argv[]) {{  Py_Initialize();  // Initialize globals, if any.{ctx.initializations.content}  PyObject* r = {main}();  return PyLong_AsLong(r);}}""")

复制代码

最后，我们对生成的 C 代码运行clang-format和gcc：

...def main():    ...    subprocess.run(["clang-format", "-i", "main.c"])    cflags_raw = subprocess.check_output(["python3-config", "--cflags"])    cflags = [f.strip() for f in cflags_raw.decode().split(" ") if f.strip()]    cmd = ["gcc", "-c", "-o", "main.o"] + cflags + ["main.c"]    subprocess.run(cmd)    ldflags_raw = subprocess.check_output(["python3-config", "--ldflags"])    ldflags = [f.strip() for f in ldflags_raw.decode().split(" ") if f.strip()]    cmd = ["gcc"] + ldflags + ["main.o"]    subprocess.run(cmd)

复制代码

完整代码如下：

import astimport osimport subprocessimport shutilimport sysfrom context import Contextfrom codegen import generateBUILTINS = {    "print": "PYC_Print",}
def main():    target = sys.argv[1]    with open(target) as f:        source = f.read()    tree = ast.parse(source, target)    ctx = Context()    with open("libpyc.c") as f:        ctx.body_write(f.read() + "\n")    for builtin, fn in BUILTINS.items():        ctx.register_global(builtin, fn)    generate(ctx, tree)    # Create and move to working directory    outdir = "bin"    shutil.rmtree(outdir, ignore_errors=True)    os.mkdir(outdir)    os.chdir(outdir)    with open("main.c", "w") as f:        f.write(ctx.body.content)        main = ctx.namings.get("main")["name"]        f.write(f"""int main(int argc, char *argv[]) {{  Py_Initialize();  // Initialize globals, if any.{ctx.initializations.content}  PyObject* r = {main}();  return PyLong_AsLong(r);}}""")    subprocess.run(["clang-format", "-i", "main.c"])    cflags_raw = subprocess.check_output(["python3-config", "--cflags"])    cflags = [f.strip() for f in cflags_raw.decode().split(" ") if f.strip()]    cmd = ["gcc", "-c", "-o", "main.o"] + cflags + ["main.c"]    subprocess.run(cmd)    ldflags_raw = subprocess.check_output(["python3-config", "--ldflags"])    ldflags = [f.strip() for f in ldflags_raw.decode().split(" ") if f.strip()]    cmd = ["gcc"] + ldflags + ["main.o"]    subprocess.run(cmd)
main()

复制代码

完成了!

pyc/codegen.py

最后，我们编写一个从 Python AST 到 C 的转换层。我们将其分为 10 个辅助函数。有AST规范作为参考是很有帮助的。

1/10： generate

代码生成器的入口是generate(ctx: Context, exp)。它能为具有body属性（该属性能存储语句列表）的任何对象生成代码。此函数能为模块、函数体、if 主体等对象生成代码。

我们最先支持的语句是：

ast.Assign
ast.FunctionDef
ast.Return
ast.If
和ast.Expr

对于每个语句，我们只需简单地将生成器传递给关联的辅助函数。不过，在生成表达式的情况下，我们还需在表达式的结果上添加一个空（noop）操作符，否则编译器给出一个未使用变量的警告。

def generate(ctx: Context, module):    for stmt in module.body:        if isinstance(stmt, ast.Assign):            generate_assign(ctx, stmt)        elif isinstance(stmt, ast.FunctionDef):            generate_function_def(ctx, stmt)        elif isinstance(stmt, ast.Return):            generate_return(ctx, stmt)        elif isinstance(stmt, ast.If):            generate_if(ctx, stmt)        elif isinstance(stmt, ast.Expr):            r = generate_expression(ctx, stmt.value)            ctx.body_writeln("// noop to hide unused warning")            ctx.body_write_statement(f"{r} += 0")        else:            raise Exception(f"Unsupported statement type: {type(stmt)}")

复制代码

记住要主动抛出异常，否则使用新语法调试程序会很困难。

让我们继续深入研究一下这些辅助函数。

2/10：generate_assign

要生成赋值代码，我们需要检查我们是否处于顶层。如果是在顶层，则可以声明该变量，但还不能初始化它。所以我们要将初始化代码添加到程序的initialization部分。

如果不是在顶层，则可以在一个语句中声明并赋值。

不过，在执行这两种操作之前，我们都需要先注册变量名，这样我们就可以在生成的代码中获得一个安全的本地名称。然后，我们编译右侧，这样我们就可以将它赋值给左边。

import astfrom context import Context
def initialize_variable(ctx: Context, name: str, val: str):    if ctx.at_toplevel():        decl = f"PyObject* {name}"        ctx.body_write_statement(decl, 0)        init = f"{name} = {val}"        ctx.initializations_write_statement(init)    else:        ctx.body_write_statement(f"PyObject* {name} = {val}")
def generate_assign(ctx: Context, stmt: ast.Assign):    # TODO: support assigning to a tuple    local = ctx.register_local(stmt.targets[0].id)    val = generate_expression(ctx, stmt.value)    initialize_variable(ctx, local, val)

复制代码

为了实现完成该工作，我们还需要实现generate_expression。

3/10：generate_expression

与generate中的语句一样，我们需要实现以下几种表达式：

ast.Num
ast.BinOp
ast.BoolOp
ast.Name
ast.Compare
和ast.Call

对于ast.Num，我们只需将字面数字包装为PyLong*。对于ast.Name，我们只需在上下文中查找本地名称。其他的我们则委托给更多的其他辅助函数。

def generate_expression(ctx: Context, exp) -> str:    if isinstance(exp, ast.Num):        # TODO: deal with non-integers        tmp = ctx.register_local("num")        initialize_variable(ctx, tmp, f"PyLong_FromLong({exp.n})")        return tmp    elif isinstance(exp, ast.BinOp):        return generate_bin_op(ctx, exp)    elif isinstance(exp, ast.BoolOp):        return generate_bool_op(ctx, exp)    elif isinstance(exp, ast.Name):        return ctx.get_local(exp.id)["name"]    elif isinstance(exp, ast.Compare):        return generate_compare(ctx, exp)    elif isinstance(exp, ast.Call):        return generate_call(ctx, exp)    raise Exception(f"Unsupported expression: {type(exp)}")

复制代码

对于每个表达式代码生成器辅助函数，我们将表达式存储在一个局部变量中，并返回该变量的名称，以便 AST 中的父节点可以引用该子节点。这可能会导致代码生成效率低下（无用的赋值），但是对于这样的项目而言，这并不是什么大问题，而且 GCC 很可能会对其进行优化。更烦人的是，无用的赋值只会使生成的代码难以阅读。

4/10：generate_bin_op

对于二进制运算符，我们需要支持加减运算。其他二进制操作符，如“等号”或“和/或”，用ast.Compare和ast.BoolOp表示。

这很容易编写，因为我们已经在libpyc.c: PYC_Sub和PYC_Add中准备了辅助函数：

def generate_bin_op(ctx: Context, binop: ast.BinOp) -> str:    result = ctx.register_local("binop")    l = generate_expression(ctx, binop.left)    r = generate_expression(ctx, binop.right)    if isinstance(binop.op, ast.Add):        ctx.body_write_statement(f"PyObject* {result} = PYC_Add({l}, {r})")    elif isinstance(binop.op, ast.Sub):        ctx.body_write_statement(f"PyObject* {result} = PYC_Sub({l}, {r})")    else:        raise Exception(f"Unsupported binary operator: {type(binop.op)}")    return result

复制代码

很容易。

5/10：generate_bool_op

我们只需要支持斐波纳契数列程序中的or，但是 Python 中的or比 C 中的要复杂得多。在 Python 中，第一个为真的值会使表达式短路，结果是表达式的值，而不是True。

我们将使用goto进行短路，并使用PyObject_IsTrue进行是否为真的检查：

def generate_bool_op(ctx: Context, boolop: ast.BoolOp) -> str:    result = ctx.register_local("boolop")    ctx.body_write_statement(f"PyObject* {result}")    if isinstance(boolop.op, ast.Or):        done_or = ctx.register_local("done_or")        for exp in boolop.values:            v = generate_expression(ctx, exp)            ctx.body_write_statement(f"{result} = {v}")            ctx.body_writeln(f"if (PyObject_IsTrue({v})) {{")            ctx.body_write_statement(f"goto {done_or}", ctx.indentation+1)            ctx.body_writeln("}")        ctx.body_writeln(f"{done_or}:\n", 0)    return result

复制代码

现在我把它先写下来，如果我们使用循环的话，可以把这个函数移到libpyc.c中。也许会在下一个迭代中改进。

我们继续。

6/10：generate_compare

此函数处理相等和不相等的检查。我们将修改手工翻译程序中使用的PyObject_richcarebool辅助函数。

唯一需要记住的是，右侧是作为数组传递的。因此，我们必须对其遍历，然后对列表中的所有对象应用相等/不相等检查。

def generate_compare(ctx: Context, exp: ast.Compare) -> str:    result = ctx.register_local("compare")    left = generate_expression(ctx, exp.left)    ctx.body_write_statement(f"PyObject* {result} = {left}")    for i, op in enumerate(exp.ops):        v = generate_expression(ctx, exp.comparators[i])        if isinstance(op, ast.Eq):            ctx.body_write_statement(f"{result} = PyObject_RichCompare({result}, {v}, Py_EQ)")        elif isinstance(op, ast.NotEq):            ctx.body_write_statement(f"{result} = PyObject_RichCompare({result}, {v}, Py_NE)")        else:            raise Exception(f"Unsupported comparison: {type(op)}")    return result

复制代码

7/10：generate_call

最后一个表达式很简单。我们首先编译调用的参数，然后编译函数本身，然后像其他任何 C 函数一样使用参数调用函数。直接调用 C 函数会影响与 Python 库的交互（基本上，我们无法与任何库进行交互），但这是最简单的开始方法。

def generate_call(ctx: Context, exp: ast.Call) -> str:    args = ', '.join([generate_expression(ctx, a) for a in exp.args])    fun = generate_expression(ctx, exp.func)    res = ctx.register_local("call_result")    # TODO: lambdas and closures need additional work    ctx.body_write_statement(        f"PyObject* {res} = {fun}({args})")    return res

复制代码

这就是表达方式！只需要再支持几个声明辅助函数即可。

8/10： generate_function_def

这是很有趣的一个。首先，我们在作用域中注册函数名称。然后我们复制上下文，使函数体内的变量被包含在函数体内。我们扩大scope，这样我们就离开了顶层。最后，我们编译主体部分。

def generate_function_def(ctx: Context, fd: ast.FunctionDef):    name = ctx.register_local(fd.name)    childCtx = ctx.copy()    args = ", ".join([f"PyObject* {childCtx.register_local(a.arg)}" for a in fd.args.args])    ctx.body_writeln(f"PyObject* {name}({args}) {{", 0)    childCtx.scope += 1    childCtx.indentation += 1    generate(childCtx, fd)    if not childCtx.ret:        childCtx.body_write_statement("return Py_None")    ctx.body_writeln("}\n", 0)

复制代码

不必严格检查childCtx.ret，因为即使已经有返回了，我们也可以再发出一个返回。要求generate_return设置此属性，并对generate_function_def进行检查，这样就会使生成的代码更漂亮一些。

9/10：generate_return

非常简单，我们只编译要返回的值，然后发出一个return语句即可。

我们存储返回值，以便函数定义可以知道是否要添加return PyNone语句。

def generate_return(ctx: Context, r: ast.Return):    ctx.ret = generate_expression(ctx, r.value)    ctx.body_writeln("")    ctx.body_write_statement(f"return {ctx.ret}")

复制代码

我们还有最后一个声明要支持！

10/10：generate_if

你知道该怎么做：编译测试，如果测试是正确的，就进入编译后的主体。我们将再次处理 else 主体。

def generate_if(ctx: Context, exp: ast.If):    test = generate_expression(ctx, exp.test)    ctx.body_writeln(f"if (PyObject_IsTrue({test})) {{")    ctx.indentation += 1    generate(ctx, exp)    # TODO: handle exp.orelse    ctx.indentation -= 1    ctx.body_writeln("}\n")

复制代码

我们完成了这个编译器！

尝试一下

按照承诺：

$ cat tests/recursive_fib.pydef fib(n):    if n == 0 or n == 1:        return n    return fib(n - 1) + fib(n - 2)
def main():    print(fib(40))$ python3 pyc tests/recursive_fib.py$ ./bin/a.out102334155

复制代码

微基准测试，或使编译器 Twitter 不高兴

请记住，这个实现只完成了 CPython 所做工作的一小部分。

如果你要计时生成的代码：

$ python3 pyc tests/recursive_fib.py$ time ./bin/a.out102334155./bin/a.out  18.69s user 0.03s system 99% cpu 18.854 total

复制代码

CPython (将main()附加到源文件)：

time python3 tests/recursive_fib.py102334155python3 tests/recursive_fib.py  76.24s user 0.11s system 99% cpu 1:16.81 total

复制代码

我之所以提这一点，是因为我为针对C++/libV8的JavaScript做了一个类似的编译器项目，当时生成的代码速度与这个几乎相同或稍微慢一些。

在编写这些编译器方面，没有比这更好的了。

原文链接：

https://notes.eatonphil.com/writing-a-simple-python-compiler.html

发布

暂无评论

实践贴：如何编写一个简单的Python编译器

依赖

手写的第一遍

编译器架构

libpyc.c

pyc/context.py

pyc/main.py

pyc/codegen.py

1/10： generate

2/10：generate_assign

3/10：generate_expression

4/10：generate_bin_op

5/10：generate_bool_op

6/10：generate_compare

7/10：generate_call

8/10： generate_function_def

9/10：generate_return

10/10：generate_if

尝试一下

微基准测试，或使编译器 Twitter 不高兴

评论

更多内容推荐

推荐阅读

电子书

大厂实战PPT下载