摘要

历史上（直到 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) 解析器，主要基于 Dragon Book [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)
}

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

参数类型上的修饰符指定所需值的数量；'?' 表示它是可选的，'*' 表示 0 个或更多，没有修饰符表示参数只有一个值且是必需的。例如，FunctionDef 接受一个用于名称的标识符，'arguments' 用于 args，零个或更多 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' 字段。

内存管理

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

通常，除非您正在处理编译器的核心关键部分，否则可以完全忽略内存管理。但如果您正在处理编译器的最初或最终阶段，您需要关注竞技场的工作原理。所有与竞技场相关的代码都位于 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 结构体中。

Python/asdl.c 和 Include/asdl.h 中用于创建和使用 asdl_seq * 类型的函数和宏：

• 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() 分别进入和退出各种代码块，这些代码块勾勒出局部变量的作用范围。

一旦符号表创建完成，就到了 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)

  根据 PyObject 序列对象中指定 PyObject 的位置添加带有适当参数的 opcode，但不对混淆名称进行处理；用于需要按名称查找对象的情况，例如全局变量、常量或参数，这些情况下名称混淆是不可能的，并且名称的作用域是已知的

• ADDOP_NAME()

  与 ADDOP_O 类似，但也处理名称混淆；用于基于名称的属性加载或导入

• ADDOP_JABS()

  创建到基本块的绝对跳转

• ADDOP_JREL()

  创建到基本块的相对跳转

有几个辅助函数会发出字节码，它们命名为 compiler_xx()，其中 xx 表示函数辅助的内容（list、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

    执行字节码（又称 eval 循环）。

  • compile.c

    根据 AST 发出字节码。

  • symtable.c

    从 AST 生成符号表。

  • pyarena.c

    arena 内存管理器的实现。

  • 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 研讨会上发表了一篇关于窥孔优化器 [1] 的论文。

Michael Hudson 有一个不活跃的 SourceForge 项目，名为 Bytecodehacks [2]，它提供直接操作字节码的功能。

创建了一个名为 CALL_ATTR 的 opcode [3]，用于结合 LOAD_ATTR/CALL_FUNCTION 的功能。目前仅适用于经典类，对于新式类，粗略基准测试显示由于必须同时支持经典类和新式类而导致实际性能下降。

参考资料