CPython编译器的工作原理¶
原文链接：https://tenthousandmeters.com/blog/python-behind-the-scenes-2-how-the-cpython-compiler-works/
今日主题¶
在本系列的第一篇文章中，我们研究了CPython VM。我们已经了解到它是通过执行一系列称为 字节码的指令来工作的。我们还看到Python字节码不足以完全描述一段代码的作用。 这就是为什么存在代码对象的概念。执行模块或函数等代码块意味着执行相应的代码对象。 代码对象包含块的字节码、常量和块内使用的变量名称以及块的各种属性。
通常，Python程序员不编写字节码，也不创建代码对象，而是编写普通的Python代码。 因此CPython必须能够从源代码创建代码对象。这项工作由CPython编译器完成。 在这一部分，我们将探讨它是如何工作的。
注意：在这篇文章中，我指的是CPython 3.9。随着CPython的发展，一些实现细节肯定会发生变化。 我将尝试跟踪重要更改并添加更新说明。
CPython编译器是什么¶
我们了解了CPython编译器的职责是什么，但在了解它是如何实现的之前，让我们先弄清楚为什么 我们称它为编译器。
一般意义上的编译器是将一种语言的程序翻译成另一种语言的等效程序的程序。编译器有很多种， 但大多数时候我们所说的编译器是指静态编译器，它将高级语言的程序翻译成机器码。 CPython编译器与这种类型的编译器有什么共同之处吗？要回答这个问题，我们先来看看静态编译器的 传统三阶段设计。
编译器的前端将源代码转换为某种中间表示(IR)。然后优化器获取一个IR，对其进行优化并将优化后的 IR传递给生成机器代码的后端。如果我们选择不特定于任何源语言和任何目标机器的IR， 那么我们将获得三阶段设计的一个关键好处：对于支持新源语言的编译器，只需要一个额外的前端， 并且支持新的目标机器，只需要一个额外的后端。
LLVM工具链是该模型成功的一个很好的例子。 C、Rust、Swift和许多其他编程语言的前端 依赖LLVM来提供更复杂的编译器部分。LLVM 的创建者Chris Lattner对其架构进行了很好的概述 。
然而，CPython不需要支持多种源语言和目标机器，而只需要一个Python代码和CPython VM。 尽管如此，CPython编译器是三阶段设计的实现。要了解原因，我们应该更详细地检查三阶段编译器的各个阶段。
上图代表了一个经典编译器的模型。现在将其与下图中的CPython编译器的架构进行比较。
看起来很像，不是吗？这里的重点是，任何以前研究过编译器的人都应该熟悉CPython编译器的结构。 如果没有，著名的龙书 是对编译器构造理论的极好介绍。它很长，但即使只阅读前几章你也会受益。
我们所做的比较需要一些评论。首先，从3.9版本开始，CPython默认使用一个新的解析器， 可以直接输出AST（抽象语法树），而无需构建解析树的中间步骤。因此，CPython编译器的模型被进一步简化。 其次，与静态编译器的对应阶段相比，CPython编译器的某些呈现阶段所做的很少， 以至于有些人可能会说CPython编译器只不过是一个前端。我们不会对铁杆编译器编写者采取这种观点。
编译器架构概述¶
这些图表很好，但是它们隐藏了许多细节并且可能会产生误导，所以让我们花一些时间来讨论CPython编译器的整体设计。
CPython编译器的两个主要组件是：
- 前端
- 后端
前端输入Python代码并生成AST。后端采用AST并生成代码对象。在整个CPython源代码中， 术语解析器和编译器分别用于前端和后端。这是编译器这个词的另一个含义。将其称为代码对象生成器之类 的东西可能会更好，但我们将坚持使用编译器，因为它似乎不会造成太多麻烦。
解析器的工作是检查输入是否是语法正确的Python代码。如果不是，则解析器会报告如下错误：
x = y = = 12
^
SyntaxError: invalid syntax
根据经典定义，文法是四项的元组：
- Σ - 一组有限的终结符，或简称终结符（通常用小写字母表示）。
- N – 一组有限的非终结符，或简单的非终结符（通常用大写字母表示）。
- P——一组产生式规则。在上下文无关文法（包括Python语法）的情况下，产生式规则只是从 非终结符到任何终结符和非终结符序列（如 A→aB）的映射。
- 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是一种简单的声明性语言，用于描述树状IR，这就是AST。 下面是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的样子。但是，解析器需要在C代码中表示AST。幸运的是， 从它们的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来处理Python代码。例如，当断言语句失败时，pytest对AST进行更改以 提供有用的信息，如果表达式的计算结果为False，它本身只会引发AssertionError。 另一个例子是Bandit，它通过分析AST来发现Python代码中的常见安全问题。
现在，当我们稍微研究了Python AST时，我们可以看看解析器如何从源代码构建它。
从源代码到 AST¶
事实上，正如我之前提到的，从3.9版本开始，CPython没有一个而是两个解析器。默认情况下使用新的解析器。
也可以通过传递-X oldparser选项来使用旧的解析器。然而，在CPython 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)文法的解析是一个已解决的问题。解决方案是充当自顶向下解析器的下推自动机(PDA )。 PDA通过使用堆栈模拟输入字符串的生成来运行。为了解析一些输入，它从堆栈上的开始符号开始。然后它查看 输入中的第一个符号，猜测应该将哪个规则应用于起始符号并将其替换为该规则的右侧。 如果堆栈顶部的符号是与输入中的下一个符号匹配的终结符，PDA将弹出它并跳过匹配的符号。 如果顶部符号是非终结符，则PDA会尝试根据输入中的下一个符号猜测替换它的规则。 该过程重复进行，直到扫描了整个输入或PDA无法将堆栈中的终端与输入中的下一个符号匹配。 后一种情况意味着无法解析输入字符串。
由于产生式规则的编写方式，CPython无法直接使用此方法，因此必须开发新方法。为了支持扩展符号， 旧的解析器用确定性有限自动机(DFA )来表示文法的每个规则，DFA以等效于正则表达式而闻名。 解析器本身是一个类似于PDA的基于堆栈的自动机，但它不是将符号推入堆栈，而是推入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;
A parsing rule is represented as a Deterministic Finite-state Automaton (DFA). A node in a DFA represents a state of the parser; an arc represents a transition. Transitions are either labeled with terminal symbols or with nonterminals. When the parser decides to follow an arc labeled with a nonterminal, it is invoked recursively with the DFA representing the parsing rule for that as its initial state; when that DFA accepts, the parser that invoked it continues. The parse tree constructed by the recursively called parser is inserted as a child in the current parse tree.
解析器在解析输入时构建解析树，也称为具体语法树(CST)。与AST相比，解析树直接对应于派生输入时 应用的规则。解析树中的所有节点都使用相同的节点结构表示：
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;
分词器¶
从句法的角度来看，Python并不是一门简单的语言。然而，Python语法看起来很简单， 包括注释在内大约有200行。这是因为语法的符号是标记而不是单个字符。标记（Token）由类型表示， 例如 NUMBER、NAME、NEWLINE、值和源代码中的位置。 CPython区分了63种标记， 所有这些都在Grammar/Tokens中列出。我们可以使用标准的tokenize 模块来查看标记化程序的样子：
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 ''
这就是解析器对程序的解析结果。当解析器需要一个令牌时，它会从令牌生成器请求一个。分词器一次从缓冲区
读取一个字符，并尝试将看到的前缀与某种类型的标记相匹配。分词器如何使用不同的编码？它依赖于io模块。
首先，分词器检测编码。如果未指定编码，则默认为UTF-8。然后，tokenizer用C调用打开一个文件，
相当于Python的open(fd, mode='r', encoding=enc)，通过调用readline()函数读取其内容。
此函数返回一个unicode字符串。标记器读取的字符只是该字符串（或 EOF）的UTF-8表示中的字节。
我们可以直接在语法中定义数字或名称是什么，尽管它会变得更复杂。我们不能做的是在不使其上下文敏感
的情况下表达语法中缩进的重要性，因此不适合解析。分词器通过提供INDENT和DEDENT标记
使解析器的工作变得更加容易。它们的意思是大括号在像C这样的语言中的意思。标记器足够强大，
可以处理缩进，因为它有状态。当前缩进级别保持在堆栈顶部。当级别增加时，它会被压入堆栈。
如果级别降低，则从堆栈中弹出所有更高级别。
旧的解析器是CPython代码库的一个重要部分。语法规则的DFA是自动生成的，但解析器的其他部分是 手工编写的。这与新的解析器形成对比，后者似乎是解析Python代码问题的更优雅的解决方案。
新解析器¶
新的解析器带有新的语法。该文法是解析表达式文法(PEG) 。
重要的是要理解PEG不仅仅是一类语法。这是定义文法的另一种方式。PEG由Bryan Ford于2004年引入，
作为描述编程语言并根据描述生成解析器的工具。PEG与传统形式语法的不同之处在于其规则将非终结符
映射到解析表达式，而不仅仅是符号序列。这符合CPython的精神。解析表达式是归纳定义的。
如果e、e1和e2是解析表达式，也就是：
- 空字符串
- 任何终端
- 任何非终结符
- e1e2，一个序列
- e1/e2，优先选择
- e∗，零次或多次重复
- !e，非谓词。
PEG是分析文法，这意味着它们的设计不仅可以生成语言，还可以分析它们。福特正则化将解析表达式e
识别输入x的含义形式化。基本上，任何使用解析表达式识别输入的尝试都可能成功或失败，
也可能消耗或不消耗某些输入。例如，将解析表达式a应用于输入ab会导致成功并消耗a。
这种形式化允许将任何PEG转换为递归下降解析器 。 递归下降解析器将文法的每个非终结符与解析函数相关联。在PEG的情况下，解析函数的主体是相应解析表达式的实现。如果解析表达式包含非终结符， 则递归调用它们的解析函数。
一个非终结符可能有多个产生式规则。递归下降解析器必须决定使用哪一个来导出输入。如果语法是 LL(k)， 则解析器可以查看输入中的下k个标记并预测正确的规则。这样的解析器称为预测解析器。如果无法预测， 则使用回溯法。具有回溯功能的解析器尝试一个规则，如果失败，则回溯并尝试另一个。这正是PEG中 的优先选择运算符所做的。因此，PEG解析器是带有回溯的递归下降解析器。
回溯方法功能强大，但计算成本可能很高。考虑一个简单的例子。我们将表达式AB/A应用于在A上成功 但在B上失败的输入。根据优先选择运算符的解释，解析器首先尝试识别A，成功，然后尝试识别B。 它失败在B上并尝试再次识别A。由于这种冗余计算，解析时间可以是输入大小的指数。为了解决这个问题， 福特建议使用一种记忆技术，即缓存函数调用的结果。使用这种技术，解析器（称为 Packrat 解析器） 可以保证在线性时间内工作，但会消耗更高的内存。这就是CPython的新解析器所做的。这是一个 Packrat解析器！
无论新解析器有多好，都必须给出替换旧解析器的理由。这就是PEP的用途。 PEP 617 -- CPython的新PEG解析器 提供了旧解析器和新解析器的背景，并解释了转换背后的原因。简而言之，新的解析器消除了对语法的LL(1) 限制，应该更容易维护。Guido van Rossum写了一个关于PEG解析的优秀系列，其中他详细介绍了 如何实现一个简单的PEG解析器。轮到我们，我们将看看它的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类的实例表示。要创建这样的实例，必须有语法文件的解析器。这个解析器也是 由解析器生成器从元语法自动生成的。这就是解析器生成器可以在Python中生成解析器的原因。 但是什么解析元语法呢？嗯，它与语法使用相同的表示法，因此生成的语法解析器也能够解析元语法。 当然，语法解析器必须自举，即第一个版本必须手工编写。完成后，所有解析器都可以自动生成。
与旧的解析器一样，新的解析器从标记器获取标记。这对于PEG解析器来说是不寻常的， 因为它允许统一标记化和解析。但是我们看到分词器做了一项重要的工作，所以CPython 开发人员决定使用它。
在这个注释上，我们结束对解析的讨论，看看在AST旁边会发生什么。
AST优化¶
CPython编译器的架构图向我们展示了AST优化器以及解析器和编译器。 这可能过分强调了优化器的作用。AST优化器仅限于常量折叠，仅在CPython 3.7中引入。 在CPython 3.7之前，常量折叠是在后期由窥孔优化器完成的。尽管如此，由于AST优化器， 我们可以这样写：
n = 2 ** 32 # easier to write and to read
并期望在编译时计算它。
一个不太明显的优化示例是将常量列表和常量集分别转换为元组和frozenset。当在in或
not in运算符的右侧使用列表或集合时，将执行此优化。
从AST到代码对象¶
到目前为止，我们一直在研究CPython如何从源代码创建 AST，但正如我们在第一篇文章中看到的， CPython VM对AST一无所知，只能执行代码对象。将AST转换为代码对象是编译器的工作。 更具体地说，编译器必须返回包含模块字节码的模块代码对象以及模块中其他代码块的代码对象， 例如定义的函数和类。
有时，了解问题解决方案的最佳方法是考虑自己的解决方案。让我们思考一下，如果我们是编译器，
我们会怎么做。我们从代表模块的AST的根节点开始。此节点的子节点是语句。让我们假设第一条语句
是一个简单的赋值，如x = 1。它由Assign AST节点表示：
Assign(targets=[Name(id='x', ctx=Store())], value=Constant(value= 1))。
要将这个节点转换为代码对象，我们需要创建一个，将常量1存储在代码对象的常量列表中，
将变量x的名称存储在代码对象中使用的名称列表中，并发出LOAD_CONST和STORE_NAME指示。
我们可以编写一个函数来做到这一点。但即使是简单的分配也可能很棘手。例如，假设在函数体内
进行了相同的赋值。如果x是局部变量，我们应该发出STORE_FAST指令。如果x是一个全局变量，
我们应该发出STORE_GLOBAL指令。最后，如果x被嵌套函数引用，我们应该发出STORE_DEREF
指令。问题是确定变量x的类型是什么。CPython 通过在编译前构建符号表来解决这个问题。
符号表¶
符号表包含有关代码块和其中使用的符号的信息。它由单个符号表结构和一组_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;
CPython使用术语命名空间作为符号表上下文中代码块的同义词。因此，我们可以说符号表条目是
对命名空间的描述。符号表条目通过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(10)作为参数传递给它。此参数称为.0。CPython还向我们隐瞒了什么？
符号表条目分两次构造。在第一遍期间，CPython遍历AST并为它遇到的每个代码块创建一个符号表条目。 它还收集可以当场收集的信息，例如块中是否定义或使用了符号。但是有些信息在第一次通过时很难 推断出来。考虑这个例子：
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_blocks字段是一个字典，编译器使用它来获取给定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 ...
字节码是线性的。测试节点的指令应该在前，body块的指令应该在orelse块的指令之前。
控制流语句的问题在于它们涉及跳转，并且跳转通常在它指向的指令之前发出。在我们的例子中，
如果第一个测试成功，我们想直接跳到第一个body指令，但我们还不知道它应该在哪里。
如果第二个测试失败，我们必须跳过body块到orelse块，但是只有在我们翻译body块之后，
第一个orelse指令的位置才会知道。
如果我们将每个块的指令移动到一个单独的数据结构中，我们就可以解决这个问题。然后， 我们不是将跳转目标指定为字节码中的具体位置，而是指向这些数据结构。最后，当所有块都被翻译 并知道它们的大小时，我们计算跳转的参数并将块组装成单个指令序列。这就是编译器所做的。
我们正在谈论的块称为基本块。它们并非特定于CPython，尽管CPython的基本块概念与传统定义不同。 根据龙书，基本块是最大的指令序列，使得：
- 控制只能进入块的第一条指令；和
- 控制将离开块而不暂停或分支，除非可能在最后一条指令处。
CPython放弃了第二个要求。换句话说，除了第一个基本块的指令不能作为跳转的目标， 但一个基本块本身可以包含跳转指令。为了翻译我们示例中的AST，编译器创建了四个基本块：
- 测试说明 0-14
- body说明 16-20
- orelse的说明 22-24；和
- 说明 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字段更感兴趣。
正如注释所说，它指向正常控制流到达的下一个块，这意味着它可以用于以正确的顺序组装块。
再次回到我们的示例，测试块指向主体块，主体块指向orelse块，而orelse块指向if
语句之后的块。因为基本块相互指向，所以它们形成了一个称为控制流图(CFG)的图。
帧块（frame block）¶
还有一个问题需要解决：如何理解在编译诸如continue和break之类的语句时跳转到哪里？
编译器通过引入另一种称为帧块的块来解决这个问题。有不同种类的框架块。例如，WHILE_LOOP
帧块指向两个基本块：主体块和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;
};
我们已经确定了三个重要问题，并且我们已经看到了编译器如何解决它们。现在，让我们将所有内容 放在一起，看看编译器从头到尾是如何工作的。
编译器单元、编译器和汇编器¶
正如我们已经发现的，在构建符号表后，编译器执行另外两个步骤将AST转换为代码对象：
- 它创建了一个基本块的CFG；和
- 它将一个CFG组装成一个代码对象。
对程序中的每个代码块执行此两步过程。编译器首先构建模块的CFG，最后将模块的CFG组装到
模块的代码对象中。在这两者之间，它通过递归调用compiler_visit_*和compiler_*
函数来遍历AST，其中*表示访问或编译的内容。例如，compiler_visit_stmt
将给定语句的编译委托给适当的compiler_*函数，并且compiler_if函数知道如何编译
If AST节点。如果一个节点引入了新的基本块，编译器就会创建它们。如果一个节点开始
一个代码块，编译器会创建一个新的编译单元并输入它。编译单元是捕获代码块编译状态的数据结构。
它充当代码对象的可变原型并指向新的CFG。当编译器退出开始当前代码块的节点时，
编译器会组装此CFG。汇编代码对象存储在父编译单元中。与往常一样，我鼓励您查看结构定义：
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 */
};
另一个对编译至关重要的数据结构是编译器结构，它表示编译的全局状态。这是它的定义：
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 */
};
定义前的注释解释了两个最重要的字段的用途：
The u pointer points to the current compilation unit, while units for enclosing blocks are stored in c_stack. The u and c_stack are managed by compiler_enter_scope() and compiler_exit_scope().
要将基本块组装成代码对象，编译器首先必须通过用字节码中的位置替换指针来修复跳转指令。 一方面，这是一项简单的任务，因为所有基本块的大小都是已知的。另一方面，当我们修复跳转时， 基本块的大小可能会改变。当前的解决方案是在大小改变时保持循环中的固定跳跃。 以下是来自此解决方案源代码的诚实评论：
This is an awful hack that could hurt performance, but on the bright side it should work until we come up with a better solution.
其余的很简单。编译器迭代基本块并发出指令。进度保存在汇编器结构中：
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 */
};
此时，当前编译单元和汇编器包含创建代码对象所需的所有数据。恭喜！我们几乎做完了！
窥孔优化器¶
创建代码对象的最后一步是优化字节码。这是窥孔优化器的工作。以下是它执行的一些类型的优化：
- 像
if True: ...和while True: ...这样的语句会生成一系列LOAD_CONST trueconst和POP_JUMP_IF_FALSE指令。窥孔优化器消除了此类指令。 - 像
a, = b这样的语句会导致生成元组然后解包的字节码。窥孔优化器用一个简单的赋值代替它。 - 窥孔优化器在
RETURN后删除不可达的指令。
本质上，窥孔优化器去除了冗余指令，从而使字节码更加紧凑。字节码优化后，编译器创建代码对象，VM准备执行它。
总结¶
这是一篇很长的文章，所以总结一下我们学到的东西可能是个好主意。 CPython编译器的架构遵循传统设计。 它的两个主要部分是前端和后端。前端也称为解析器。它的工作是将源代码转换为AST。解析器从分词器获取标记， 分词器负责从文本中生成有意义的语言单元流。历史上，解析由几个步骤组成，包括生成解析树和将解析树 转换为AST。在CPython 3.9中，引入了新的解析器。它基于解析表达式语法并立即生成AST。后端， 也被矛盾地称为编译器，采用AST并生成代码对象。它通过首先构建一个符号表，然后通过创建一个称为 控制流图的程序的另一个中间表示来实现这一点。CFG被组装成单个指令序列，然后由窥孔优化器进行优化。 最终，代码对象被创建。
在这一点上，我们有足够的知识来熟悉CPython源代码并了解它所做的一些事情。这是我们下次的计划。