实践贴：如何编写一个简单的Python编译器 作者 | Phil Eaton 译者 | 刘雅梦策划&编辑 | Linda 我用 Python 编写了一个 Python 到 C 的编译器，并使用该编译器编译并运行一个斐波纳契（Fibonacci）数列程序。 本文最初发表在 notes.eatonphil 网站，由InfoQ 中文站翻译并分享。 在本文中，我们将用 Python 编写一个 Python 到 C 的编译器。这一点特别容易做到，因为 Python 有 一个内置的解析器库，并且 许多 CPython 内部构件对编写扩展程序来说都是公开的。 到本文的最后，通过几百行 Python 代码，我们将能够编译并运行以下程序： $ cat tests/recursive_fib.py def 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.out 102334155 本文实现了一个非常小的 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 ast import os import subprocess import shutil import sys from context import Context from codegen import generate BUILTINS = { "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 ast import os import subprocess import shutil import sys from context import Context from codegen import generate BUILTINS = { "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 ast from 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.py def 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.out 102334155 微基准测试，或使编译器 Twitter 不高兴 请记住，这个实现只完成了 CPython 所做工作的一小部分。 如果你要计时生成的代码： $ python3 pyc tests/recursive_fib.py $ time ./bin/a.out 102334155 ./bin/a.out 18.69s user 0.03s system 99% cpu 18.854 total CPython (将main()附加到源文件)： time python3 tests/recursive_fib.py 102334155 python3 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 你也「在看」吗？?? 阅读原文