摘要

从历史上看 (到 2.4)，从源代码到字节码的编译涉及两个步骤

1. 将源代码解析成解析树 (Parser/pgen.c)
2. 根据解析树生成字节码 (Python/compile.c)

从历史上看，这不是标准编译器的工作方式。编译的通常步骤是

1. 将源代码解析成解析树 (Parser/pgen.c)
2. 将解析树转换为抽象语法树 (Python/ast.c)
3. 将 AST 转换为控制流图 (Python/compile.c)
4. 根据控制流图生成字节码 (Python/compile.c)

从 Python 2.5 开始，现在使用上述步骤。进行此更改是为了通过将其分解为三个步骤来简化编译。本文档的目的是概述后三个步骤的工作原理。

本文档不涉及解析工作原理，超出了解释编译所需内容的范围。它在整个系统的工作原理方面也不详尽。您很可能需要阅读一些源代码才能完全了解所有细节。

解析树

Python 的解析器是 LL(1) 解析器，主要基于“龙书”[Aho86] 中介绍的实现。

Python 的语法文件可以在 Grammar/Grammar 中找到，语法规则的数值存储在 Include/graminit.h 中。令牌类型的数值（文字令牌，例如 :、数字等）保存在 Include/token.h 中。解析树由 node * 结构体组成（如 Include/node.h 中定义）。

可以使用以下宏（它们都在 Include/token.h 中定义）来查询节点结构体中的数据

• CHILD(node *, int)

  使用零偏移索引返回节点的第 n 个子节点

• RCHILD(node *, int)

  从右侧返回节点的第 n 个子节点；使用负数！

• NCH(node *)

  节点拥有的子节点数量

• STR(node *)

  节点的字符串表示形式；例如，对于 COLON 令牌，将返回 :

• TYPE(node *)

  在 Include/graminit.h 中指定的节点类型

• REQ(node *, TYPE)

  断言节点是预期类型

• LINENO(node *)

  检索导致创建解析规则的源代码的行号；在 Python/ast.c 中定义

为了将所有这些示例联系起来，请考虑“while”规则

while_stmt: 'while' test ':' suite ['else' ':' suite]

表示此规则的节点将具有 TYPE(node) == while_stmt，并且子节点数量可以是 4 或 7，具体取决于是否存在“else”语句。要访问应该是第一个“:”的节点并要求它是一个实际的“:”令牌，请使用 (REQ(CHILD(node, 2), COLON)。

抽象语法树 (AST)

抽象语法树 (AST) 是程序结构的高级表示形式，不需要包含源代码；可以将其视为源代码的抽象表示。AST 节点的规范使用 Zephyr 抽象语法定义语言 (ASDL) [Wang97] 指定。

Python 的 AST 节点的定义位于文件 Parser/Python.asdl 中。

每个 AST 节点（表示语句、表达式和几种特殊类型，例如列表推导和异常处理程序）都由 ASDL 定义。AST 中的大多数定义对应于特定的源代码结构，例如“if”语句或属性查找。定义与其在任何特定编程语言中的实现无关。

以下 Python ASDL 结构片段演示了这种方法和语法

module Python
{
      stmt = FunctionDef(identifier name, arguments args, stmt* body,
                          expr* decorators)
            | Return(expr? value) | Yield(expr value)
            attributes (int lineno)
}

上面的示例描述了三种不同类型的语句；函数定义、返回值语句和 yield 语句。这三种类型都被认为是 stmt 类型，如“|”分隔各种类型所示。它们都接受各种类型和数量的参数。

参数类型上的修饰符指定所需的数值；“?”表示它是可选的，“*”表示 0 个或更多个，没有修饰符表示参数只有一个值并且它是必需的。例如，FunctionDef 接受一个标识符作为名称，‘arguments’ 作为参数，零个或多个 stmt 参数作为‘body’，以及零个或多个 expr 参数作为‘decorators’。

请注意，像“arguments”这样的节点类型表示为单个 AST 节点，而不是像 stmt 那样表示为一系列节点，这可能与人们的预期相符。

这三种类型都具有‘attributes’ 参数；这是由‘attributes’之前没有‘|’表示的。

上面的语句定义将生成以下 C 结构类型

typedef struct _stmt *stmt_ty;

struct _stmt {
      enum { FunctionDef_kind=1, Return_kind=2, Yield_kind=3 } kind;
      union {
              struct {
                      identifier name;
                      arguments_ty args;
                      asdl_seq *body;
              } FunctionDef;

              struct {
                      expr_ty value;
              } Return;

              struct {
                      expr_ty value;
              } Yield;
      } v;
      int lineno;
 }

还生成了一系列构造函数，这些函数将分配（在本例中）一个 stmt_ty 结构体，并进行适当的初始化。‘kind’ 字段指定初始化联合的哪个组件。FunctionDef() 构造函数将‘kind’ 设置为 FunctionDef_kind，并初始化‘name’、‘args’、‘body’ 和‘attributes’ 字段。

内存管理

在讨论编译器的实际实现之前，需要讨论内存的处理方式。为了简化内存管理，使用了竞技场。这意味着内存被集中在一个位置，以便于分配和删除。这使我们免除了显式内存分配。因为编译器为所有需要的内存注册了与竞技场相关的内存，所以只需调用一次释放竞技场即可完全释放编译器使用的所有内存。

一般来说，除非您正在处理编译器的关键核心，否则可以完全忽略内存管理。但是，如果您在编译器的最开始或最后工作，则需要关注竞技场的工作原理。所有与竞技场相关的代码都在 Include/pyarena.h 或 Python/pyarena.c 中。

PyArena_New() 将创建一个新的竞技场。返回的 PyArena 结构将存储指向分配给它的所有内存的指针。这将进行簿记，以记录编译器完成后需要释放哪些内存。释放通过 PyArena_Free() 完成。这只需在编译器退出的战略区域中调用。

如上所述，一般来说，在处理编译器时，您无需担心内存管理。技术细节被设计为在大多数情况下对您隐藏。

唯一的例外是管理 PyObject 时出现。由于 Python 的其余部分使用引用计数，因此在竞技场中添加了额外的支持以清理每个分配的 PyObject。这些情况非常少见。但是，如果您分配了一个 PyObject，则必须通过调用 PyArena_AddPyObject() 告诉竞技场。

解析树到 AST

AST 是使用函数 PyAST_FromNode() 从解析树生成的（参见 Python/ast.c）。

该函数开始对解析树进行树遍历，在遍历过程中创建各种 AST 节点。它是通过分配所需的所有新节点，为任何必需的支持函数调用适当的 AST 节点创建函数，并根据需要连接它们来完成此操作。

请意识到，语法规范和解析树中的节点之间没有自动或符号连接。解析树不会像 yacc 中那样直接提供帮助。

例如，您必须跟踪正在处理的解析树中的哪个节点（例如，如果您正在处理“if”语句，则需要注意“:”令牌以找到条件的结束位置）。

用于从解析树生成 AST 节点的函数都以 ast_for_xx 命名，其中 xx 是函数处理的语法规则（alias_for_import_name 是对此的例外）。这些函数反过来调用由 ASDL 语法定义并在 Python/Python-ast.c 中包含的构造函数（由 Parser/asdl_c.py 生成）来创建 AST 的节点。这将导致一系列 AST 节点存储在 asdl_seq 结构体中。

用于创建和使用 asdl_seq * 类型的函数和宏可以在 Python/asdl.c 和 Include/asdl.h 中找到

• asdl_seq_new()

  为指定长度的 asdl_seq 分配内存

• asdl_seq_GET()

  获取 asdl_seq 中特定位置保存的项目

• asdl_seq_SET()

  将 asdl_seq 中的特定索引设置为指定的值

• asdl_seq_LEN(asdl_seq *)

  返回 asdl_seq 的长度

如果您正在处理语句，则还必须注意跟踪生成语句的行号。目前，行号作为最后一个参数传递给每个 stmt_ty 函数。

控制流图

控制流图（通常用其缩写 CFG 表示）是一个有向图，它使用包含中间表示（缩写为“IR”，在本例中是 Python 字节码）的基本块来模拟程序的流程。基本块本身是具有单个入口点但可能具有多个出口点的 IR 块。单个入口点是基本块的关键；这与跳转有关。入口点是更改控制流的东西（例如函数调用或跳转）的目标，而出口点是会更改程序流程的指令（例如跳转和‘return’语句）。这意味着基本块是一段代码，从入口点开始运行，直到到达出口点或块的末尾。

例如，考虑一个带有“else”块的“if”语句。 “if”语句的保护是一个基本块，它由包含指向“if”语句的代码的基本块指向。 “if”语句块包含跳转（这是出口点），分别跳转到“if”语句的真体和“else”语句体（可能为NULL），它们各自都是它们自己的基本块。 这两个块又都指向表示整个“if”语句之后的代码的基本块。

CFG 通常距离最终代码输出只有一步之遥。 通过对 CFG 进行后序深度优先搜索，按照边进行遍历，可以直接从基本块（根据输出顺序调整跳转目标）生成代码。

AST 到 CFG 到 字节码

创建 AST 后，下一步是创建 CFG。 第一步是将 AST 转换为 Python 字节码，而无需将跳转目标解析为特定偏移量（这将在 CFG 转换为最终字节码时计算）。 本质上，这将 AST 转换为 Python 字节码，并通过 CFG 的边表示控制流。

转换分为两个阶段进行。 第一个阶段创建命名空间（变量可以分类为局部变量、闭包的自由/单元变量或全局变量）。 完成后，第二个阶段本质上将 CFG 展平为一个列表，并计算最终字节码输出的跳转偏移量。

转换过程由对 Python/compile.c 中的 PyAST_Compile() 函数的调用启动。 此函数完成 AST 到 CFG 的转换以及从 CFG 输出最终字节码。 AST 到 CFG 的步骤主要由 PyAST_Compile() 调用的两个函数处理； PySymtable_Build() 和 compiler_mod()。 前者位于 Python/symtable.c 中，而后者位于 Python/compile.c 中。

PySymtable_Build() 从进入 AST（传入）的起始代码块开始，然后调用适当的 symtable_visit_xx 函数（xx 是 AST 节点类型）。 接下来，使用各种代码块来划分局部变量的范围，并使用 symtable_enter_block() 和 symtable_exit_block() 分别进入和退出块，遍历 AST 树。

创建符号表后，就该创建 CFG 了，其代码位于 Python/compile.c 中。 这是由几个函数处理的，这些函数通过各种 AST 节点类型来分解任务。 这些函数都命名为 compiler_visit_xx，其中 xx 是节点类型的名称（例如 stmt、expr 等）。 每个函数都会接收一个 struct compiler * 和 xx_ty，其中 xx 是 AST 节点类型。 通常，这些函数包含一个大型的“switch”语句，根据传递给它的节点类型进行分支。 简单的事情在“switch”语句中内联处理，而更复杂的转换则委托给其他名为 compiler_xx 的函数，其中 xx 是正在处理的内容的描述性名称。

在转换任意 AST 节点时，使用 VISIT() 宏。 将调用适当的 compiler_visit_xx 函数，具体取决于为 传入的值（因此 VISIT(c, expr, node) 调用 compiler_visit_expr(c, node)）。 VISIT_SEQ 宏非常类似，但它是在 AST 节点序列（那些作为使用“*”修饰符的节点参数创建的值）上调用。 还有 VISIT_SLICE() 用于专门处理切片。

字节码的发出由以下宏处理

• ADDOP()

  添加指定的 opcode

• ADDOP_I()

  添加一个带参数的 opcode

• ADDOP_O(struct compiler *c, int op, PyObject *type, PyObject *obj)

  添加一个带适当参数的 opcode，该参数基于指定的 PyObject 在 PyObject 序列对象中的位置，但不会处理 mangling 的名称； 用于需要对对象（例如全局变量、常量或参数）进行命名查找的情况，在这些情况下，名称 mangling 是不可能的，并且名称的范围是已知的

• ADDOP_NAME()

  与 ADDOP_O 相同，但也会处理名称 mangling； 用于基于名称加载属性或导入

• ADDOP_JABS()

  创建指向基本块的绝对跳转

• ADDOP_JREL()

  创建指向基本块的相对跳转

一些用于发出字节码的辅助函数，它们被命名为 compiler_xx()，其中 xx 是函数帮助处理的内容（列表、boolop 等）。 一个非常有用的函数是 compiler_nameop()。 此函数会查找变量的范围，并根据表达式上下文发出适当的 opcode 来加载、存储或删除变量。

至于处理语句定义所在的行号，由 compiler_visit_stmt() 处理，因此无需担心。

除了根据 AST 节点发出字节码之外，还必须处理基本块的创建。 以下是用于管理基本块的宏和函数

• NEW_BLOCK()

  创建块并将其设置为当前块

• NEXT_BLOCK()

  基本上是 NEW_BLOCK() 加上来自当前块的跳转

• compiler_new_block()

  创建块但不使用它（用于生成跳转）

创建 CFG 后，必须将其展平，然后发出最终的字节码。 展平使用后序深度优先搜索处理。 展平后，根据展平过程对跳转偏移量进行回补，然后创建 PyCodeObject 文件。 所有这些都通过调用 assemble() 处理。

引入新的字节码

有时，新功能需要新的 opcode。 但是添加新的字节码并不像在编译器的 AST -> 字节码步骤中突然引入新的字节码那么简单。 Python 中的许多代码片段都依赖于对现有字节码的信息的正确性。

首先，您必须选择一个名称和一个唯一的标识符编号。 字节码的官方列表可以在 Include/opcode.h 中找到。 如果 opcode 需要参数，则必须为其指定一个大于分配给 HAVE_ARGUMENT 的唯一编号（如 Include/opcode.h 中所示）。

选择名称/编号对并在 Include/opcode.h 中输入后，您还必须将其输入到 Lib/opcode.py 和 Doc/library/dis.rst 中。

使用新的字节码时，您还必须更改称为 .pyc 文件的魔术数的内容。 Python/import.c 中的变量 MAGIC 包含该编号。 更改此编号将导致所有具有旧 MAGIC 的 .pyc 文件在导入时由解释器重新编译。

最后，您需要引入新字节码的使用。 更改 Python/compile.c 和 Python/ceval.c 将是主要更改位置。 但您还需要更改“compiler”包。 要执行此操作的关键文件是 Lib/compiler/pyassem.py 和 Lib/compiler/pycodegen.py。

如果您在此处进行的更改可能会影响已存在的字节码的输出，并且您没有不断更改魔术数，请确保删除您旧的 .py(c|o) 文件！ 即使您最终会更改魔术数，如果您更改了字节码，但您会在调试工作时更改字节码输出，而不会不断增加魔术数。 这意味着您最终会得到陈旧的 .pyc 文件，这些文件不会被重新创建。 运行 find . -name '*.py[co]' -exec rm -f {} ';' 应该会删除您所有的 .pyc 文件，从而强制创建新的文件，并允许您正确测试新字节码。

代码对象

PyAST_Compile() 的结果是 PyCodeObject，它在 Include/code.h 中定义。 这样，您就拥有了可执行的 Python 字节码！

代码对象（字节码）在 Python/ceval.c 中执行。 此文件还需要在 PyEval_EvalFrameEx() 中的大型 switch 语句中为新的 opcode 添加一个新的 case 语句。

重要文件

• Parser/

  • Python.asdl

    ASDL 语法文件

  • asdl.py

    “Zephyr 抽象语法定义语言的实现”。 使用 SPARK 来解析 ASDL 文件。

  • asdl_c.py

    “从 ASDL 描述生成 C 代码”。 生成 Python/Python-ast.c 和 Include/Python-ast.h。

  • spark.py

    SPARK 解析器生成器

• Python/

  • Python-ast.c

    创建与 ASDL 类型相对应的 C 结构体。 还包含用于封送 AST 节点的代码（核心 ASDL 类型在 asdl.c 中具有封送代码）。 “由 Parser/asdl_c.py 自动生成的”。 此文件必须在每次语法更改提交后单独提交，因为 __version__ 值设置为最新的语法更改修订号。

  • asdl.c

    包含用于处理 ASDL 序列类型的代码。 还包含用于处理封送核心 ASDL 类型（例如数字和标识符）的代码。 由 Python-ast.c 用于封送 AST 节点。

  • ast.c

    将 Python 的解析树转换为抽象语法树。

  • ceval.c

    执行字节码（即，评估循环）。

  • compile.c

    根据 AST 发出字节码。

  • symtable.c

    从 AST 生成符号表。

  • pyarena.c

    竞技场内存管理器的实现。

  • import.c

    字节码版本控制的魔术数（名为 MAGIC）的所在地

• Include/

  • Python-ast.h

    包含由 Python/Python-ast.c 生成的 C 结构体的实际定义。 “由 Parser/asdl_c.py 自动生成”。

  • asdl.h

    对应 Python/ast.c 的头文件。

  • ast.h

    声明 PyAST_FromNode() 为外部函数（来自 Python/ast.c）。

  • code.h

    Objects/codeobject.c 的头文件； 包含 PyCodeObject 的定义。

  • symtable.h

    Python/symtable.c 的头文件。 struct symtable 和 PySTEntryObject 在此处定义。

  • pyarena.h

    对应 Python/pyarena.c 的头文件。

  • opcode.h

    字节码的主列表； 如果修改了此文件，则必须相应地修改其他几个文件（参见“引入新字节码”）

• Objects/

  • codeobject.c

    包含 PyCodeObject 相关的代码（最初位于 Python/compile.c 中）。

• Lib/

  • opcode.py

    如果修改了 Include/opcode.h，则必须修改的文件之一。

  • compiler/

    • pyassem.py

      如果更改了 Include/opcode.h，则必须修改的文件之一。

    • pycodegen.py

      如果更改了 Include/opcode.h，则必须修改的文件之一。

已知的与编译器相关的实验

本节列出了已知的涉及编译器（包括字节码）的实验。

Skip Montanaro 在 Python 研讨会上发表了一篇关于 peephole 优化器的论文 [1]。

Michael Hudson 有一个名为 Bytecodehacks 的非活动 SourceForge 项目 [2]，它提供了直接玩弄字节码的功能。

一个将 LOAD_ATTR/CALL_FUNCTION 的功能结合在一起的 opcode 被命名为 CALL_ATTR [3]。 目前仅适用于经典类，对于新式类，粗略的基准测试表明由于必须同时支持经典类和新式类，实际上出现了速度下降。

参考文献