如何找到我python编译器的位置（译Python幕后2）
如何找到我python编译器的位置（译Python幕后2）CPython 编译器与静态编译器有什么共同点吗？为回答这个问题，让我们先来看看传统静态编译器的三段式设计。通常来说，编译器指的是一个程序，负责把某种语言（源语言）编写的程序翻译成等价的、用另一种语言（目标语言）编写的程序。编译器有很多种类型，不过多数情况下，我们说的编译器是指静态编译器，即把高级语言程序翻译为机器码的程序。一般来说，Python 程序员不会手写字节码，也不会手动创建代码对象，他们写的是普通的 Python 代码。因此，CPython 就必须能把 Python 源代码转换为代码对象。这个转换是由 CPython 编译器完成的。本文要讨论的，就是这个转换过程。 注意：文章中默认使用 CPython 3.9，随着 CPython 的演化，一些实现细节可能会有所调整，我会尽力留意一些重要变化并更新文章内容。我们已经知道 CPython 编译器的功能，在进一步讨论其实现方式之前，首
这是一篇译文，原文系列地址：https://tenthousandmeters.com/tag/python-behind-the-scenes/
欢迎关注：ReadingPython
今天的主题在本系列译｜Python幕后（1）：CPython VM 原理中，我们讨论了 CPython VM 的工作原理。
我们已经知道，CPython VM 会执行一系列称为字节码的指令，我们也知道，单纯的字节码并不能完整描述一块代码的功能，因此有了代码对象（code object）。当我们执行一个代码块，比如某个函数或模块时，实际上就是执行它们各自对应的代码对象。代码对象中既包含了代码块的字节码，也包含了代码块中用到的常量、变量及其它各类信息。
一般来说，Python 程序员不会手写字节码，也不会手动创建代码对象，他们写的是普通的 Python 代码。因此，CPython 就必须能把 Python 源代码转换为代码对象。这个转换是由 CPython 编译器完成的。本文要讨论的，就是这个转换过程。
注意：文章中默认使用 CPython 3.9，随着 CPython 的演化，一些实现细节可能会有所调整，我会尽力留意一些重要变化并更新文章内容。
CPython 编译器
我们已经知道 CPython 编译器的功能，在进一步讨论其实现方式之前，首先谈一下为什么我们把它叫做编译器。
通常来说，编译器指的是一个程序，负责把某种语言（源语言）编写的程序翻译成等价的、用另一种语言（目标语言）编写的程序。编译器有很多种类型，不过多数情况下，我们说的编译器是指静态编译器，即把高级语言程序翻译为机器码的程序。
CPython 编译器与静态编译器有什么共同点吗？为回答这个问题，让我们先来看看传统静态编译器的三段式设计。
编译器前端将源代码转换成某种中间表示（IR：intermediate representation），接着优化器执行优化动作，后端将优化后的中间表示转换成机器码。如果我们选择一种不依赖特定源语言，也不依赖特定机器的中间表示，就可以获得三段式设计的巨大优势：只需要新增一个前端就可以支持一种新的源语言，新增一个后端就可以支持一种新的目标机器。
LLVM 工具链就是这种设计的成功例子。它有对应于 C、Rust、Swift 以及许多其它语言的前端，各种语言都能用到 LLVM 提供的复杂编译功能。LLVM 的作者 Chris Lattner 对这种设计结构有很好的介绍。
CPython 并不需要支持多种源语言，也不需要支持多种目标机器，只要能支持 Python 代码和 CPython 虚拟机就行。不过，它还是实现了这种三段式设计。要理解其中缘由，还须进一步考察三段式设计的细节。
上图展示了一个经典编译器模型，可与下图 CPython 编译器模型进行比较。
很相似不是吗？我想说的是，对一个了解静态编译器的人来说，很容易就可以熟悉 CPython 编译器。如果对静态编译器不熟悉，可以参考龙书，它对编译器结构的介绍极其精彩。这本书很长，但哪怕只看前面几章，你也会获益匪浅。（译者注：本文会涉及一些编译知识，学过《编译原理》的同学可能读起来会更顺畅一些。）
关于上面的比较，有必要做几点补充：
- 一是，3.9 版本之后，CPython 默认使用新的解析器，不再构建解析树，而是直接生成抽象语法树（AST：Abstract Syntax Tree），因此，CPython 编译器的模型更加简化了。
- 二是，相对于静态编译器来说，CPython 编译器在许多阶段所做的事情很少，因此，有些人认为，CPython 编译器不过是个编译器前端而已。本文不取这种硬核定义。
编译器结构概览
前面的图示很漂亮，但也隐藏了很多细节，可能造成一些误导。我们不妨花些时间讨论下 CPython 编译器的整体设计。
CPython 编译器的两个主要组成部分是：
- 前端；及
- 后端；
前端处理 Python 代码，生成 AST（抽象语法树），后端处理 AST，生成代码对象。在 CPython 源码中，一直用解析器指代前端，编译器指代后端，不过这只是编译器这个词的另一种用法而已。或许用代码对象生成器称呼后端更合适，但本文还是会使用编译器，希望这个用词不会给读者带来太多麻烦。
解析器的工作是检查输入的 Python 代码在句法上是否正确，如果不正确，则报告错误，比如下面这个例子：
x = y = = 12
^
SyntaxError: invalid syntax
如果正确，则根据语法规则组织代码。
语法定义了一门语言的句法结构。鉴于语法这个概念对我们的讨论极其关键，我想，这里还是把语法的正式定义列出。在经典定义中，语法是下面四个要素的组合：
- Σ – 终结符号的有限集合，简称终结符（通常由小写字母表示）；
- N – 非终结符号的有限集合，简称非终结符（通常由大写字母表示）；
- P – 一系列生成规则，对 Python 这类上下文无关文法来说，一条生成规则就是从一个非终结符到一个终结符与非终结符系列的映射，如 A->aB；
- S – 一个特定的非终结符；
语法定义了一门语言根据规则可以生成的所有终结符序列。为生成一个序列，首先做的是解析 S，然后递归解析 S 的解析结果，将系列中的所有非终结符转换为终结符。通过列出所有生成规则，即可充分定义一个语法。下面是一个简单语法的例子，它将生成一个 1 和 0 的交替序列。
S→10S|10
我们会在之后讨论解析器的时候进一步讨论语法。
抽象语法树
解析器的最终目的是生成 AST。AST 是一种树状数据结构，是源代码的高级表示。下面的例子展示了两行源代码，及其通过 ast 标准库生成的对应 AST：
x = 123
f(x)$ python -m ast example1.py
Module(
body=[
Assign(
targets=[
Name(id='x' ctx=Store())]
value=Constant(value=123))
Expr(
value=Call(
func=Name(id='f' ctx=Load())
args=[
Name(id='x' ctx=Load())]
keywords=[]))]
type_ignores=[])
AST 节点的各种类型由 Zephyr 抽象语法树定义语言（ASDL）定义。ASDL 是一种简单的描述式语言，用于表示编译器的树型中间表示形式。下面是 Parser/Python.asdl 中对 Assign 和 ExPr 节点的描述：
stmt = ... | Assign(expr* targets expr value string? type_comment) | ...
expr = ... | Call(expr func expr* args keyword* keywords) | ...
从这些 ASDL 描述中，我们可以知道 Python AST 大概的样子。当然，解析器还要把 AST 转换成 C 代码。幸运的是，把 ASDL 描述的 AST 节点转换为 C 语言数据结构并不困难，这也是 CPython 要完成的工作，转换的结果如下：
struct _stmt {
enum _stmt_kind kind;
union {
// ... other kinds of statements
struct {
asdl_seq *targets;
expr_ty value;
string type_comment;
} Assign;
// ... other kinds of statements
} v;
int lineno;
int col_offset;
int end_lineno;
int end_col_offset;
};
struct _expr {
enum _expr_kind kind;
union {
// ... other kinds of expressions
struct {
expr_ty func;
asdl_seq *args;
asdl_seq *keywords;
} Call;
// ... other kinds of expressions
} v;
// ... same as in _stmt
};
AST 在隐藏 Python 的缩进、标点等次要句法特征的同时，可以很好地描述一个程序的意图。
编译器是 AST 的主要受益者之一，通过扫描 AST，它可以以一种相对直接的方式生成字节码。此外，很多 Python 工具也利用了 AST。例如，pytest 对 AST 做了一些调整，从而可以在 assert 语句失败后提供许多有用信息，真正由它自己完成的工作，不过是在表达式的值为 False 时抛出 AssertionError 而已。另一个例子是 Bandit，通过分析 AST，可以找出 Python 代码中的常见安全漏洞。
对 Python AST 有些了解之后，我们可以来看看解析器是如何生成抽象语法树的。
从源代码到AST
之前已经提过，从 3.9 开始，CPython 支持两个解析器。默认使用的是新版解析器，用户可以通过 -X oldparser 选项选择旧版解析器。不过，3.10 版本之后将不再支持旧版解析器。
两个版本的解析器差异很大，我们先讨论旧版，然后重点关注新版解析器。
旧版解析器很长一段时间内，Python 都使用生成语法来定义其句法规则。我们之前已经讨论过，这种语法可以告诉我们如何生成对应语言的符号序列。问题在于，生成语法并不能直接告诉我们如何解析生成的符号序列。
幸运的是，聪明的前辈们已经确定哪些生成语法可以生成对应的解析器，包括上下文无关文法、LL(k)，LR(k)，LALR 文法等。Python 使用的是 LL(1) 文法，具体地说，是扩展巴科斯范式（EBNF）。
为了解它是如何描述 Python 句法的，我们可以简单看一下 while 语句的规则：
file_input: (NEWLINE | stmt)* ENDMARKER
stmt: simple_stmt | compound_stmt
compound_stmt: ... | while_stmt | ...
while_stmt: 'while' namedexpr_test ':' suite ['else' ':' suite]
suite: simple_stmt | NEWLINE INDENT stmt DEDENT
...
CPython 还支持了一些新的标记符号，例如：
- 一组选项：（a|b）
- 可选部分：[a]
- 零或多个与一或多个：a* / a
我们可以看到 Guido van Rossum 选择正则表达式的原因。新的标记可以让我们以一种（对程序员来说）更自然的方式描述一门编程语言的句法。我们可以直接写 A->a ，而不是 A->aA|a。代价就是，CPython 必须以某种方式支持这些扩展标记。
LL(1) 语法的解析是一个已解决的问题，即通过下推自动机（Pushdown Automaton PDA）实现的自顶向下解析器。
下推自动机通过一个栈来完成工作，栈内有一个开始符号，在解析一段输入时，它会检查输入的第一个符号，并推测应使用何种规则进行转换，以规则右边的语句替代开始符号。如果栈顶是一个终结符且与输入的符号匹配，则弹出这个终结符并跳过匹配的符号，如果栈顶是一个非终结符，则根据之后的输入推测替换规则。这个过程持续进行，直到完成整个输入的扫描，或者无法匹配栈内终结符与输入符号。无法匹配即表示输入字符串无法解析。
当然，CPython 不能直接使用这个方法。为了支持扩展标记，旧版解析器使用确定有限自动机（DFA）表示每条语法规则，而确定有限自动机与正则表达式是等价的。解析器依然是一个基于栈的自动机，但它推入栈的不再是语法符号，而是 DFA 状态。下面是它使用的一些关键数据结构：
typedef struct {
int s_state; /* State in current DFA */
const dfa *s_dfa; /* Current DFA */
struct _node *s_parent; /* Where to add next node */
} stackentry;
typedef struct {
stackentry *s_top; /* Top entry */
stackentry s_base[MAXSTACK];/* Array of stack entries */
/* NB The stack grows down */
} stack;
typedef struct {
stack p_stack; /* Stack of parser states */
grammar *p_grammar; /* Grammar to use */
// basically a collection of DFAs
node *p_tree; /* Top of parse tree */
// ...
} parser_state;
Parser/parser.c 中的注释对这种方法做了说明：
每条解析规则由一个确定有限自动机（DFA）表示，DFA 的每个节点代表解析器的一种状态，每条连接表示一次状态转换，每次状态转换带有一个终结符或非终结符标记。当解析器经由某个非终结符进行状态转换时，即由代表对应规则的 DFA 以该非终结符为初始状态递归调用解析器。被递归调用的解析器作为子节点插入原有解析树中。
解析器在解析输入时构造了一个解析树，或称具体语法树（Concrete Syntax Tree CST）。与抽象语法树不同，具体语法树与解析对应输入的语法规则直接关联，每个节点都由统一的数据结构表示：
typedef struct _node {
short n_type;
char *n_str;
int n_lineno;
int n_col_offset;
int n_nchildren;
struct _node *n_child;
int n_end_lineno;
int n_end_col_offset;
} node;
对编译器来说，解析树还必须转换成 AST，这个过程是由 Python/ast.c 实现的。具体算法是，递归扫描解析树，将其节点转换为 AST 节点。不过，我想，大概没什么人会对这近 6000 行代码感兴趣。
分词器从句法角度看，Python 并不是一门简单的语言。不过从语法看，则要简单得多，包括注释，整个代码不过 200 行左右。这是因为语法要处理的是 token 而不是单独的字符。
每个 token 由类型，值和它在源码中的位置组成。类型包括 NUMBER、NAME、NEWLINE 等，CPython 中的 token 类型总共有 63 种，罗列在 Grammar/Tokens 中。通过标准库中的 tokenize 模块，我们可以将一段程序转换成 token 形式：
def x_plus(x):
if x >= 0:
return x
return 0$ python -m tokenize example2.py
0 0-0 0: ENCODING 'utf-8'
1 0-1 3: NAME 'def'
1 4-1 10: NAME 'x_plus'
1 10-1 11: OP '('
1 11-1 12: NAME 'x'
1 12-1 13: OP ')'
1 13-1 14: OP ':'
1 14-1 15: NEWLINE '\n'
2 0-2 4: INDENT ' '
2 4-2 6: NAME 'if'
2 7-2 8: NAME 'x'
2 9-2 11: OP '>='
2 12-2 13: NUMBER '0'
2 13-2 14: OP ':'
2 14-2 15: NEWLINE '\n'
3 0-3 8: INDENT ' '
3 8-3 14: NAME 'return'
3 15-3 16: NAME 'x'
3 16-3 17: NEWLINE '\n'
4 4-4 4: DEDENT ''
4 4-4 10: NAME 'return'
4 11-4 12: NUMBER '0'
4 12-4 13: NEWLINE '\n'
5 0-5 0: DEDENT ''
5 0-5 0: ENDMARKER ''
上面就是解析器所看到的程序。解析过程中，解析器请求分词器返回下一个 token，分词器则从缓存中每次读入一个字符，尝试与某种 token 类型的前缀进行匹配。
那么，分词器是如何处理不同编码格式的呢？实际上依赖于 io 模块。分词器会先检查编码格式，如果没有指定，则默认使用 UTF-8，随后调用 C 程序打开文件，这个调用类似于 Python 中的 open(fd mode='r' encoding=enc)，再通过 readline() 函数读取文件内容，这个函数将返回一个 unicode 字符串。分词器最终获取的是 UTF-8 格式的字符串字节码（或文件结束符 EOF）。
我们可以在语法中直接定义一个数字或名称的具体含义，同时还要以一种上下文无关的方法表示缩进的意义，否则就没法进行解析。通过引入 INDENT 与 DEDENT token，分词器可以以一种比较便捷的方式完成这项工作，它们的含义类似于 C 语言中的大括号。由于分词器是有状态的，处理这些缩进并不困难。当前缩进级别存储在一个栈的顶部，新的缩进意味着将新的级别压入栈，减少缩进则表示要弹出一个级别。
旧版解析器是 CPython 代码的重要组成部分，其中语法规则对应的 DFA 是自动生成的，其它代码都由手写实现。这一点上，新版解析器完全不同， 是一种优雅得多的方案。
新版解析器新版解析器使用了一种新的解析表达式语法（Parsing Expression Grammar PEG）。读者需要理解的是，PEG 不仅是一种新的语法类型，而且是一种新的语法定义方式。PEG 由 Bryan Ford 在 2004 年提出，用于描述一门编程语言，并生成对应的解析器。
与传统语法形式不同的是，PEG 规则中，非终结符映射的并不是终结符或非终结符系列，而是解析表达式（parsing expression）。CPython 以归纳方式定义解析表达式，如果 e，e1，e2 是解析表达式，那么下面这些都是解析表达式：
- 空字符串
- 任意终结符
- 任意非终结符
- e1e2，即解析表达式序列
- e1/e2，一个带优先级的选项
- e∗，零或多次重复
- !e，一个逻辑非谓语
PEG 是分析型语法，能生成语言，也能分析语言。它以规范形式定义了解析表达式 e 识别输入 x 的具体含义。简单地说，解析表达式识别输入，成功时会消耗部分输入，失败时则不会。例如，将解析表达式 a 应用于输入 ab，将成功消耗 a。
这种规范形式使 PEG 可以转换成一个递归下降解析器（recursive descent parser）。递归下降解析器中，每个非终结符对应一个解析函数，在 PEG 场景下，也就是对应的解析表达式的具体实现。如果一个解析表达式包含其它非终结符，则其解析函数会递归调用。
一个非终结符可能有多条解析规则，递归下降解析器必须判断使用哪一条。如果使用的是 LL(k) 语法，解析器可以根据之后的 k 个 token 判断正确的规则，这种解析器被称为预测解析器（predictive parser）。如果无法预测，则使用回溯法，尝试一条规则，失败时回溯并尝试另一条规则。这正是 PEG 中带优先级的选项对应的场景。因此，一个 PEG 解析器就是一个使用回溯法的递归下降解析器。
回溯法很强大，但可能导致很大的性能开销。举个简单的例子，我们对某个输入应用 AB/A 解析表达式，在解析 A 时成功了，但解析 B 时失败了，根据优先序，解析器接着又要解析一遍 A。
由于这些冗余计算，解析所需要的时间随输入的增长而指数增长。为应对这个问题，Ford 建议将每次解析函数的调用结果缓存下来，以消耗更多内存为代价，在线性时间完成解析，这种解析器被称为 packrat parser。这也是 CPython 解析器所采取的策略。
不论新解析器有多好，替换旧解析器的具体原因还是要解释清楚，这正是 PEP 617 -- New PEG parser for CPython 的内容。简单地说，新解析器解除了 LL(1) 语法的限制，维护起来更简单。关于 PEG 解析器，Guido van Rossum 写过一系列文章，读者可以深入细节，并实现一个简单的解析器。当然，本文中，我们还是看看 CPython 的解析器实现。
如果我告诉你，新版语法文件是旧版的三倍大小，你可能会觉得惊讶。原因是，新版语法文件不只是语法，而且包含了其语法制导翻译模式（SDTS）。SDTS 的语法规则有其对应的动作，解析器在规则应用成功时执行对应的动作。CPython 在语法解析的同时，通过执行对应动作构造 AST。
我们看过 while 语句在旧版语法中的定义，下面是其新版定义：
file[mod_ty]: a=[statements] ENDMARKER { _PyPegen_make_module(p a) }
statements[asdl_seq*]: a=statement { _PyPegen_seq_flatten(p a) }
statement[asdl_seq*]: a=compound_stmt { _PyPegen_singleton_seq(p a) } | simple_stmt
compound_stmt[stmt_ty]:
| ...
| &'while' while_stmt
while_stmt[stmt_ty]:
| 'while' a=named_expression ':' b=block c=[else_block] { _Py_While(a b c EXTRA) }
...
规则以非终结符的名称开始，随后是解析函数返回值的 C 语言类型，冒号右边的是解析表达式。大括号中的内容表示要执行的动作，只是简单的函数调用，返回 AST 节点或者这些节点的属性值。
新的解析器在 Parser/pegen/parse.c 实现，这个文件是解析器生成器自动生成的。这个解析器生成器是用 Python 写的，它能根据语法规则生成 C 或 Python 表示的 PEG 解析器。
在生成器中，语法文件中的规则会被转换为 Grammar 类的一个实例。这个转换过程又要用到语法文件解析器，这个解析器也是自动生成的，使用的是元语法（metagrammar）的解析器生成器。那么，怎么解析元语法呢？元语法符号也是语法符号，因此，语法文件解析器也可以解析元语法。当然，还有一个初次启动的问题，也就是说，最初的解析器一定是手写的，之后的所有解析器都是自动生成的了。
与旧版解析器一样，新版解析器也从分词器获取 token。其实，PEG 解析器一般不用单独的分词器，因为分词与解析的过程是可以统一进行的。不过，鉴于分词器所做的重要工作，CPython 开发者们觉得还是可以利用一下。
现在，我们将结束对解析器的讨论，看看之后的处理过程。
抽象语法树优化之前的图中，我们看到，CPython 编译器的架构中除了编译器和解析器，还有 AST 优化器，这幅图可能过度强调了优化器的的地位。实际上，AST 优化器只提供简单的常数折叠（constant folding）功能，而且是 CPython 3.7 版本才引入的。3.7 版本之前，常数折叠是在之后的窥孔优化（peephole optimize）阶段完成的。
不管怎么说，AST 优化器使我们可以写出如下代码：
n = 2 ** 32 # 更易于书写，也更易于理解
并相信其计算过程会在编译时完成。
另一个不那么明显的优化例子是，将一个常数列表或可变集合转换成一个元组或不可变集合。这个优化动作会在对应列表或可变集合用于 in 或 not in 操作右边时发生。
从AST到代码对象
目前为止，我们已经讨论了 CPython 如何从源代码构建抽象语法树，不过，如我们在第一篇文章中所知道的，CPython 虚拟机并不知道什么是 AST，只执行字节码。
将 AST 转换为字节码是编译器要完成的工作。更准确地说，编译器必须返回模块的代码对象，包括模块的字节码，也包括模块中定义的函数和类等其它代码块的代码对象。
有时，理解一个方案的最好方式是提出一个自己的方案。假设我们自己就是编译器，我们会怎么做呢？
一个模块生成了一个 AST，让我们从树的根节点开始。假设第一个语句是个简单的赋值语句，比如 x = 1，它在 AST 中表示为一个 Assign 节点：Assign(targets=[Name(id='x' ctx=Store())] value=Constant(value=1))。
为转换这个节点，我们需要创建一个代码对象，将常数 1 存储至代码对象的常数列表，将变量名 x 存储至代码对象的名称列表，然后生成 LOAD_CONST 和 STORE_NAME 指令。我们可以写一个函数完成这些工作。
不过，即使是一个简单的赋值语句，也有一些麻烦的问题需要处理。
比如说，同样的赋值语句也可能出现在某个函数体内，如果 x 是一个局部变量，我们应该生成的是 STORE_FAST 指令，如果是全局变量，应该生成 STORE_GLOBAL 指令，又如果变量被嵌套函数引用，则应该生成 STORE_DEREF 指令。问题在于，我们怎么判断 x 到底是哪种变量呢？为处理这个问题，CPython 在编译前会构造一个符号表。
符号表符号表中保存了代码块及其所使用的符号的相关信息，由一个 symtable 结构及许多 _symtable_entry 结构表示，程序中的每个代码块都有一个对应的符号表。
符号表实体中保存了代码块的各类属性，包括名称，类型（模块、类或函数），以及一个变量名称与其标识的映射表，这些标识确定了一个变量的作用域与使用方式。下面是 _symtable_entry 结构的完整定义：
typedef struct _symtable_entry {
PyObject_HEAD
PyObject *ste_id; /* int: key in ste_table->st_blocks */
PyObject *ste_symbols; /* dict: variable names to flags */
PyObject *ste_name; /* string: name of current block */
PyObject *ste_varnames; /* list of function parameters */
PyObject *ste_children; /* list of child blocks */
PyObject *ste_directives;/* locations of global and nonlocal statements */
_Py_block_ty ste_type; /* module class or function */
int ste_nested; /* true if block is nested */
unsigned ste_free : 1; /* true if block has free variables */
unsigned ste_child_free : 1; /* true if a child block has free vars
including free refs to globals */
unsigned ste_generator : 1; /* true if namespace is a generator */
unsigned ste_coroutine : 1; /* true if namespace is a coroutine */
unsigned ste_comprehension : 1; /* true if namespace is a list comprehension */
unsigned ste_varargs : 1; /* true if block has varargs */
unsigned ste_varkeywords : 1; /* true if block has varkeywords */
unsigned ste_returns_value : 1; /* true if namespace uses return with
an argument */
unsigned ste_needs_class_closure : 1; /* for class scopes true if a
closure over __class__
should be created */
unsigned ste_comp_iter_target : 1; /* true if visiting comprehension target */
int ste_comp_iter_expr; /* non-zero if visiting a comprehension range expression */
int ste_lineno; /* first line of block */
int ste_col_offset; /* offset of first line of block */
int ste_opt_lineno; /* lineno of last exec or import * */
int ste_opt_col_offset; /* offset of last exec or import * */
struct symtable *ste_table;
} PySTEntryObject;
在符号表中，命名空间与代码块是同义词，因此，我们也可以说，一个符号表描述了一个命名空间。不同的符号表通过 ste_children 属性构成层次关系，这个属性下保存着一个命名空间列表。通过标准库中的 symtable 模块，我们可以看到这种层次关系：
# example3.py
def func(x):
lc = [x i for i in range(10)]
return lc>>> from symtable import symtable
>>> f = open('example3.py')
>>> st = symtable(f.read() 'example3.py' 'exec') # module's symtable entry
>>> dir(st)
[... 'get_children' 'get_id' 'get_identifiers' 'get_lineno' 'get_name'
'get_symbols' 'get_type' 'has_children' 'is_nested' 'is_optimized' 'lookup']
>>> st.get_children()
[<Function SymbolTable for func in example3.py>]
>>> func_st = st.get_children()[0] # func's symtable entry
>>> func_st.get_children()
[<Function SymbolTable for listcomp in example3.py>]
>>> lc_st = func_st.get_children()[0] # list comprehension's symtable entry
>>> lc_st.get_symbols()
[<symbol '.0'> <symbol 'i'> <symbol 'x'>]
>>> x_sym = lc_st.get_symbols()[2]
>>> dir(x_sym)
[... 'get_name' 'get_namespace' 'get_namespaces' 'is_annotated'
'is_assigned' 'is_declared_global' 'is_free' 'is_global' 'is_imported'
'is_local' 'is_namespace' 'is_nonlocal' 'is_parameter' 'is_referenced']
>>> x_sym.is_local() x_sym.is_free()
(False True)
从这个例子中可以看到，每个代码块都有一个对应的符号表。我们在列表推导式的命名空间中看到了一个奇怪的 .0 符号，同样奇怪的是，却没有包含 range 符号。这是因为列表推导式被实现为一个匿名函数，而 range(10) 被当作一个参数传递给了这个匿名函数，也就是 .0 符号所表示的对象。那么，CPython 还对我们隐藏了什么？
符号表的构造需要遍历两次 AST。第一次遍历时，CPython 会为它遇到的每个代码块创建一个符号表，同时也收集此时能确定的相关信息，如代码块中用到的符号等。但有些信息无法在第一次遍历就推导出来。考虑下面这个例子：
def top():
def nested():
return x 1
x = 10
...
在为 nested() 函数构造符号表时，我们不确定 x 是一个全局变量还是定义在 top() 函数中但自由变量，因为那时还没看到一个赋值语句。
于是，CPython 会进行第二次遍历。在第二次遍历开始时，符号在哪里定义过，在哪里使用过已经明确了，通过从顶向下递归访问符号表，可以填充所需的其它信息。在外层定义的符号可以传递到嵌套命名空间，内层使用的变量名也可以往外传递。
符号表的管理则依赖 symtable 数据结构。不论是构建符号表还是编译时使用符号表，都离不开这个数据结构。下面是其定义：
struct symtable {
PyObject *st_filename; /* name of file being compiled
decoded from the filesystem encoding */
struct _symtable_entry *st_cur; /* current symbol table entry */
struct _symtable_entry *st_top; /* symbol table entry for module */
PyObject *st_blocks; /* dict: map AST node addresses
* to symbol table entries */
PyObject *st_stack; /* list: stack of namespace info */
PyObject *st_global; /* borrowed ref to st_top->ste_symbols */
int st_nblocks; /* number of blocks used. kept for
consistency with the corresponding
compiler structure */
PyObject *st_private; /* name of current class or NULL */
PyFutureFeatures *st_future; /* module's future features that affect
the symbol table */
int recursion_depth; /* current recursion depth */
int recursion_limit; /* recursion limit */
};
最值得关注的是 st_stack 和 st_blocks 属性。st_stack 属性是一个符号表构成的栈，在构造符号表的第一次遍历时，CPython 进入一个代码块就往栈中推入一个符号表对象，退出一个代码块就从栈中弹出一个对象。st_block 属性是一个符号表与 AST 节点的关系映射表。st_cur 与 st_top 属性也很重要，不过它们的含义应该是不言自明的。
如果想更深入地了解符号表及其构造，我强烈推荐 Eli Bendersky 的文章。
基本块符号表可以帮助我们完成变量相关语句的翻译，如 x = 1，但如果要翻译一个更复杂的控制流语句，就会碰到新的问题。考虑下面这个代码片段：
if x == 0 or x > 17:
y = True
else:
y = False
...
对应的 AST 子树有如下结构：
If(
test=BoolOp(...)
body=[...]
orelse=[...]
)
编译器会将它翻译为下面的字节码：
1 0 LOAD_NAME 0 (x)
2 LOAD_CONST 0 (0)
4 COMPARE_OP 2 (==)
6 POP_JUMP_IF_TRUE 16
8 LOAD_NAME 0 (x)
10 LOAD_CONST 1 (17)
12 COMPARE_OP 4 (>)
14 POP_JUMP_IF_FALSE 22
2 >> 16 LOAD_CONST 2 (True)
18 STORE_NAME 1 (y)
20 JUMP_FORWARD 4 (to 26)
4 >> 22 LOAD_CONST 3 (False)
24 STORE_NAME 1 (y)
5 >> 26 ...
字节码是线性的。首先是 test 节点的指令，之后是 body 块指令，最后到 orelse 块指令。控制流语句的问题在于它需要跳转，而跳转指令往往要在跳转目的地确定之前生成。
在上面的例子中，如果第一个条件测试成功，可以直接跳转到 body 块，但我们还不知道它的具体位置，如果第二个条件测试失败，则必须跳过 body 块，直接执行 orelse 块，它的地址也只有在翻译完 body 块后才能确定。
为解决这个问题，我们可以将每个代码块的指令移入独立的数据结构中，在跳转时，地址不指向具体的字节码位置，而指向这些数据结构。在所有代码块都完成翻译，大小确定之后，我们再来计算跳转参数，并将这些块集合成一个总的指令序列。这也是 CPython 编译器的工作方式。
上面所说的代码块被称为基本块，它们并不是 CPython 所独有的，不过 CPython 中的基本块与传统意义上的基本块还是有所区别。根据龙书，基本块是一个满足下列条件的最长指令序列：
- 指令执行必定从块的第一个指令开始；
- 指令执行由最后一个指令结束，不会有分支或其它停止的情况；
CPython 中的基本块取消了第二个条件。也就是说，只有第一条指令可以作为跳转目的地，但基本块本身可能包含跳转指令。在上面的例子中，为翻译 AST，编译器会创建 4 个基本块：
- 指令 0-14 表示 test 块
- 指令 16-20 表示 body 块
- 指令 22-24 表示 orelse 块
- 指令 26-... 表示 if 语句后的任意块
基本块由 basicblock_ 数据结构表示，定义如下：
typedef struct basicblock_ {
/* Each basicblock in a compilation unit is linked via b_list in the
reverse order that the block are allocated. b_list points to the next
block not to be confused with b_next which is next by control flow. */
struct basicblock_ *b_list;
/* number of instructions used */
int b_iused;
/* length of instruction array (b_instr) */
int b_ialloc;
/* pointer to an array of instructions initially NULL */
struct instr *b_instr;
/* If b_next is non-NULL it is a pointer to the next
block reached by normal control flow. */
struct basicblock_ *b_next;
/* b_seen is used to perform a DFS of basicblocks. */
unsigned b_seen : 1;
/* b_return is true if a RETURN_VALUE opcode is inserted. */
unsigned b_return : 1;
/* depth of stack upon entry of block computed by stackdepth() */
int b_startdepth;
/* instruction offset for block computed by assemble_jump_offsets() */
int b_offset;
} basicblock;
下面是 instr 数据结构的定义：
struct instr {
unsigned i_jabs : 1;
unsigned i_jrel : 1;
unsigned char i_opcode;
int i_oparg;
struct basicblock_ *i_target; /* target block (if jump instruction) */
int i_lineno;
};
可以看到，基本块之间不仅通过跳转指令连接，也通过 b_list 和 b_next 属性连接。通过 b_list，编译器可以找到分配的所有块，用于完成释放内存等工作。不过，当前我们更感兴趣的是 b_next 属性，如注释所说，它指向正常控制流的下一个块，也就是说，通过它可以以正确的顺序完成块与块之间的组合。回到我们的例子，test 块指向 body 块，body 块指向 orelse 块，而 orelse 块指向 if 语句之后的块。由于基本块之间的互相跳转，它们形成的图被称为控制流图（Control Flow Graph CFG）。
栈帧块（frame block）另一个需要解决的问题是：如何找到 continue 和 break 语句对应的跳转位置？编译器解决这个问题的方式是引入另一种块，称为栈帧块。
栈帧块有不同类型，以 WHILE_LOOP 栈帧块为例，它指向两个基本块：body 块及 while 语句之后的块。在编译 continue 或 break 语句时，可以利用这些基本块进行跳转。由于栈帧块之间可以相互嵌套，编译器会给每个代码块一个栈来保存栈帧块信息。处理 try-except-finally 之类的语句时，栈帧块结构也很有用，不过我们暂时不作深入讨论。
下面让我们来看看 fblockinfo 数据结构：
enum fblocktype { WHILE_LOOP FOR_LOOP EXCEPT FINALLY_TRY FINALLY_END
WITH ASYNC_WITH HANDLER_CLEANUP POP_VALUE };
struct fblockinfo {
enum fblocktype fb_type;
basicblock *fb_block;
/* (optional) type-specific exit or cleanup block */
basicblock *fb_exit;
/* (optional) additional information required for unwinding */
void *fb_datum;
};
我们已经看到编译器处理的三个重要问题，接下来，我们把这些信息串起来，看看编译器的整体工作流程。
编译单元，编译器与组合器（assembler）如我们已经讨论的，构造符号表之后，编译器通过以下两个步骤完成 AST 到代码对象的转换：
- 根据基本块创建控制流图
- 将控制流图组合成代码对象
程序中每个代码块的编译都会经过这两个步骤。编译器工作的第一步是构建模块的控制流图，最后一步是将模块控制流图转换成模块代码对象，中间的过程，就是遍历 AST，递归调用 compiler_visit_* 和 compiler_* 函数，* 表示被访问与编译的对象。例如，compiler_visit_stmt 函数会调用正确的 compiler_* 函数完成对应语句的编译，而 compiler_if 函数知道如何编译一个 If AST 节点。
编译器会根据节点需要创建基本块，或在开始处理新的代码块时创建并进入新的编译单元。编译单元是用于保存特定代码块的编译状态的数据结构，它就像是代码对象的可变原型，并指向一个新的控制流图。在退出当前代码块开始处理的节点时，编译器会组合控制流图，生成代码对象，生成的代码对象保存至父编译单元中。
这里，我还是建议你看看对应的数据结构：
struct compiler_unit {
PySTEntryObject *u_ste;
PyObject *u_name;
PyObject *u_qualname; /* dot-separated qualified name (lazy) */
int u_scope_type;
/* The following fields are dicts that map objects to
the index of them in co_XXX. The index is used as
the argument for opcodes that refer to those collections.
*/
PyObject *u_consts; /* all constants */
PyObject *u_names; /* all names */
PyObject *u_varnames; /* local variables */
PyObject *u_cellvars; /* cell variables */
PyObject *u_freevars; /* free variables */
PyObject *u_private; /* for private name mangling */
Py_ssize_t u_argcount; /* number of arguments for block */
Py_ssize_t u_posonlyargcount; /* number of positional only arguments for block */
Py_ssize_t u_kwonlyargcount; /* number of keyword only arguments for block */
/* Pointer to the most recently allocated block. By following b_list
members you can reach all early allocated blocks. */
basicblock *u_blocks;
basicblock *u_curblock; /* pointer to current block */
int u_nfblocks;
struct fblockinfo u_fblock[CO_MAXBLOCKS];
int u_firstlineno; /* the first lineno of the block */
int u_lineno; /* the lineno for the current stmt */
int u_col_offset; /* the offset of the current stmt */
};
编译过程中的另一个重要数据结构是 compiler，它代表编译过程的全局状态，下面是其定义：
struct compiler {
PyObject *c_filename;
struct symtable *c_st;
PyFutureFeatures *c_future; /* pointer to module's __future__ */
PyCompilerFlags *c_flags;
int c_optimize; /* optimization level */
int c_interactive; /* true if in interactive mode */
int c_nestlevel;
int c_do_not_emit_bytecode; /* The compiler won't emit any bytecode
if this value is different from zero.
This can be used to temporarily visit
nodes without emitting bytecode to
check only errors. */
PyObject *c_const_cache; /* Python dict holding all constants
including names tuple */
struct compiler_unit *u; /* compiler state for current block */
PyObject *c_stack; /* Python list holding compiler_unit ptrs */
PyArena *c_arena; /* pointer to memory allocation arena */
};
数据结构前的注释对其中最重要的两个属性做了说明：
u 指针指向当前编译单元，c_stack 中保存了外层编译单元。这两个属性由 compiler_enter_scope() 和 compiler_exit_scope() 函数管理。
将基本块组合成代码对象时，编译器必须将跳转指令中的指针改为字节码位置。因为所有基本块的大小都已经知道了，这项工作不会太麻烦，不过，每当我们修改一次代码，基本块的大小都会改变。当前处理这个问题的方式是，每当基本块的大小改变，就调整相关的各个跳转指令。关于这个方案，CPython 源码中的注释倒说得很坦诚：
这是个影响性能的糟糕方案，但在有人提出更好的方案前至少能工作。
接下来的流程就很直观了，编译器迭代处理基本块，生成对应指令。这个过程的整体进展保存在 assembler 数据结构中：
struct assembler {
PyObject *a_bytecode; /* string containing bytecode */
int a_offset; /* offset into bytecode */
int a_nblocks; /* number of reachable blocks */
basicblock **a_postorder; /* list of blocks in dfs postorder */
PyObject *a_lnotab; /* string containing lnotab */
int a_lnotab_off; /* offset into lnotab */
int a_lineno; /* last lineno of emitted instruction */
int a_lineno_off; /* bytecode offset of last lineno */
};
此时，当前编译单元与组合器已经包含创建代码对象所需的完整信息。恭喜你，马上就搞定了！
窥孔优化器（peephole optimizer）创建代码对象的最后一步是优化字节码，这是窥孔优化器的工作。下面是它执行的一些优化示例：
- if True: ...，while True: ... 语句会生成一系列 LOAD_CONST trueconst，POP_JUMP_IF_FALSE指令，优化器会消除这些指令；
- 类似 a = b 的语句生成的字节码会创建元组，而后又进行拆包，优化器会将其替换成一个简单的赋值指令；
- 移除 RETURN 之后的不可到达指令；
简单地说，窥孔优化器会移除冗余指令，使字节码更加紧凑。优化完成后，编译器将完成代码对象的创建，之后，CPython 虚拟机就可以执行这些代码对象了。
总结
这篇文章很长，最好还是总结一下。
CPython 编译器的架构遵循传统设计，可以分成前端、后端两个部分。前端可以称为解析器，负责将源代码转换成 AST。解析器依赖分词器提供的 token，分词器的工作，就是处理输入的文本，输出有意义的语法单元。在旧版解析器中，解析过程需要先生成解析树，再将解析树转换成 AST。3.9 版本后，CPython 引入了新的解析器，基于解析表达式语法直接生成 AST。
后端也被称为（狭义的）编译器，负责将 AST 转换成代码对象。它先构造符号表，然后又构造了一种程序的中间表示，叫做控制流图。控制流图最后被组合为整体的指令序列，经过窥孔优化器的优化，最终生成代码对象。
现在，我们已经具备足够的知识，下一篇文章中，我们将继续深入 CPython 源码，理解它所做的工作。
欢迎关注：ReadingPython
