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

文章来源：infoqPhil Eaton

本文最初发表在 Medium 博客，经原作者 Max Gorynski 授权，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

发表于: 2020-08-282020-08-28 09:00:00
本文为 InfoQ 中文站特供稿件
首发地址：https://www.infoq.cn/article/eI4yJXOJM2qEwZMmINEL
如有侵权，请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长进交流群

领取专属 10元无门槛券

私享最新 技术干货