CPython编译器的工作原理

在本系列的第一篇文章中，我们介绍了CPython VM。我们已经了解到它是通过执行一系列称为字节码的指令来工作的。我们还看到，Python字节码不足以完全描述一段代码的功能。这就是存在代码对象概念的原因。执行诸如模块或函数的代码块意味着执行相应的代码对象。代码对象包含块的字节码、常量和块中使用的变量名称以及块的各种属性。

通常，Python程序员不编写字节码，也不创建代码对象，而是编写普通的Python代码。所以CPython必须能够从源代码创建代码对象。此工作由CPython编译器完成。在这一部分中，我们将探讨它是如何工作的。

注意：在这篇文章中，我指的是CPython3.9。随着CPython的发展，一些实现细节肯定会发生变化。我将尝试跟踪重要更改并添加更新笔记。

我们理解CPython编译器的职责是什么，但是在看它是如何实现之前，让我们先弄清楚为什么我们首先称它为编译器？

一般而言，编译器是将一种语言的程序翻译成另一种语言的等效程序的程序。有很多类型的编译器，但大多数时候我们所说的编译器是指静态编译器，它将高级语言中的程序翻译成机器代码。CPython编译器与这种类型的编译器有什么共同之处吗？为了回答这个问题，让我们来看看静态编译器的传统三阶段设计。

编译器的前端将源代码转换为某种中间表示(IR)。然后，优化器获取一个IR，对其进行优化，并将优化后的IR传递给生成机器代码的后端。如果我们选择不特定于任何源语言和任何目标计算机的IR，那么我们将获得三阶段设计的主要好处：对于支持新的源语言的编译器来说，只需要额外的前端，而要支持新的目标机器，只需要额外的后端。

LLVM工具链是该模型成功的一个很好的例子。C、Rust、Swift和许多其他编程语言的前端依赖于LLVM来提供更复杂的编译器部分。LLVM的创建者克里斯·拉特纳(Chris Lattner)很好地概述了它的架构。

然而，CPython不需要支持多种源语言和目标机器，只需要支持Python代码和CPythonVM。不过，CPython编译器是三阶段设计的实现。要了解原因，我们应该更详细地检查三阶段编译器的各个阶段。

上图代表了一个经典编译器的模型。现在将其与下图中的CPython编译器的体系结构进行比较。

看起来很像，不是吗？这里的要点是，任何以前研究过编译器的人都应该熟悉CPython编译器的结构。如果你没有，一本著名的龙书是编译器构建理论的极好的介绍。这本书很长，但即使只读前几章，你也会从中受益。

我们所作的比较需要几点意见。首先，从3.9版开始，CPython默认使用一个新的解析器，该解析器可以直接输出AST(抽象语法树)，而不需要执行构建解析树的中间步骤。因此，CPython编译器的模型进一步简化。其次，与静态编译器的对应阶段相比，CPython编译器的某些阶段所做的工作非常少，以至于有些人可能会说CPython编译器只不过是一个前端。我们不会对核心编译器作者持这种观点。

这些图表很不错，但是它们隐藏了很多细节，可能会产生误导，所以让我们花一些时间来讨论CPython编译器的总体设计。

前端采用Python代码并生成AST。后端获取AST并生成代码对象。在整个CPython源代码中，术语解析器和编译器分别用于前端和后端。这是“编译器”一词的另一种含义。将其称为代码对象生成器可能更好，但我们将坚持使用编译器，因为它似乎不会造成太多麻烦。

解析器的工作是检查输入是否是语法正确的Python代码。如果不是，解析器将报告如下错误：

如果输入是正确的，则解析器根据语法规则对其进行组织。语法定义了一种语言的语法。形式语法的概念对于我们的讨论是如此重要，我认为，我们应该离题一点，记住它的形式定义。

\(\Sigma\)-终端符号的有限集合，或简称终端(通常用小写字母表示)。

\(n\)-非终端符号的有限集合，或简称为非终端(通常用大写字母表示)。

\(P\)-一组产生式规则。在上下文无关文法(包括Python文法)的情况下，产生式规则只是从非终结点到任何终端序列和非终结点(如\(A\to AB\))的映射。

语法定义了由可以通过应用产生式规则生成的所有终端序列组成的语言。要生成某个序列，可以从符号\(S\)开始，然后根据产生式规则递归地用序列替换每个非终端，直到整个序列由终端组成。使用已建立的符号约定，列出产生式规则来指定语法就足够了。例如，下面是一个生成交替的1和0序列的简单语法：

解析器的最终目标是生成AST。AST是一种树数据结构，用作源代码的高级表示。下面是标准ast模块生成的一段代码和相应AST的转储的示例：

$python-m ast example1.pyModule(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())]，key=[])。

AST节点的类型是使用Zephyr抽象语法定义语言(ASDL)正式定义的。ASDL是一种简单的声明性语言，创建该语言是为了描述树状IRS，这就是AST。以下是来自Parser/Python.asdl的Assign和expr节点的定义：

Stmt=...|ASSIGN(表达式*目标，表达式值，字符串？TYPE_COMMENT)|...expr=...|call(expr函数，expr*参数，关键字*关键字)|...。

ASDL规范应该会让我们对Python AST有一个概念。但是，解析器需要在C代码中表示AST。幸运的是，从ASDL描述为AST节点生成C结构很容易。这就是CPython所做的，结果如下所示：

Struct_stmt{enum_stmt_Kind；Union{//...。其他类型的语句struct{asdl_seq*target；expr_ty value；string type_Comment；}ASSIGN；//...。其他类型的语句}v；int lineno；int colOffset；int end_lineno；int end_colOffset；}；struct_expr{enum_expr_Kind；Union{//...。其他类型的表达式struct{expr_ty func；asdl_seq*args；asdl_seq*关键字；}调用；//...。其他类型的表达式}v；//...。与in_stmt}相同；

AST是一种易于使用的表示形式。它告诉程序做什么，隐藏所有不重要的信息，如缩进、标点符号和Python的其他语法特性。

AST表示的主要受益者之一是编译器，它可以相对简单的方式遍历AST并发出字节码。除了编译器之外，许多Python工具还使用AST来处理Python代码。例如，pytest对AST进行更改，以便在assert语句失败时提供有用的信息，这本身不做任何事情，但如果表达式的计算结果为false，则会引发AssertionError。另一个例子是Bandit，它通过分析AST来查找Python代码中的常见安全问题。

现在，当我们稍微研究了Python AST之后，我们可以看看解析器是如何从源代码构建它的。

事实上，正如我前面提到的，从3.9版开始，CPython有两个解析器，而不是一个。默认情况下使用新的解析器。也可以通过传递-X oldparser选项来使用旧的解析器。然而，在CPython3.10中，旧的解析器将被完全删除。

这两个解析器非常不同。我们将把重点放在新的解析器上，但在讨论旧的解析器之前也要先讨论。

在很长一段时间里，Python的语法都是由生成语法正式定义的。这是我们前面谈过的一种语法。它告诉我们如何生成属于该语言的序列。问题是生成语法并不直接对应于能够解析这些序列的解析算法。幸运的是，聪明人已经能够区分生成语法的类别，可以为其构建相应的解析器。这些语法包括上下文无关、LL(K)、LR(K)、LALR和许多其他类型的语法。Python语法是LL(1)。它是使用一种扩展的巴科斯-诺尔形式(EBNF)指定的。要了解如何使用它来描述Python的语法，请看一下WHILE语句的规则。

File_input：(newline|stmt)*ENDMARKERstmt：Simple_stmt|复合_stmt复合_stmt：...|while_stmt|...While_stmt：'；While'；namedexpr_test'；：'；Suite['；Else'；'；：'；Suite]Suite：Simple_stmt|newline缩进stmt+DEDENT...

我们可以理解为什么Guido van Rossum选择使用正则表达式。它们允许以更自然(对于程序员而言)的方式表达编程语言的语法。我们可以不写\(A\to AA|a\)，而只写\(A\to a+\)。这一选择是有代价的：CPython必须开发一种方法来支持扩展表示法。

LL(1)文法的解析是一个已解决的问题。解决方案是下推自动机(PDA)，它充当自上而下的解析器。PDA通过使用堆栈模拟输入串的生成来操作。要解析某些输入，它从堆栈上的开始符号开始。然后，它查看输入中的第一个符号，猜测哪个规则应该应用于开始符号，并将其替换为该规则的右侧。如果堆栈上的顶部符号是与输入中的下一个符号匹配的端子，则PDA弹出它并跳过匹配的符号。如果顶部符号是非终端，则PDA会尝试根据输入中的符号猜测要用来替换它的规则。重复该过程，直到整个输入被扫描，或者如果PDA不能将堆栈上的端子与输入中的下一个符号匹配，从而导致错误。

由于产生式规则的编写方式，CPython不能直接使用此方法，因此必须开发新方法。为了支持扩展表示法，旧的解析器使用确定性有限自动机(DFA)来表示语法的每个规则，DFA以等价于正则表达式而闻名。解析器本身是基于堆栈的自动机，类似于PDA，但它不是将符号推送到堆栈上，而是推送DFAS的状态。下面是旧解析器使用的关键数据结构：

Tyfinf struct{int s_state；/*当前DFA中的状态*/const DFA*s_DFA；/*当前DFA*/struct_node*s_parent；/*添加下一个节点的位置*/}stackentry；tyfinf struct{stackentry*s_top；/*top entry*/stackentry s_base[MAXSTACK]；/*堆栈条目数组*//*NB堆栈向下增长*/}堆栈；tyfinf struct{STACKENTRY*s_STACK]；/*堆栈条目数组*//*NB堆栈向下增长*/}堆栈；tyfinf struct{STACKENTY*s_STACK；/*解析器状态堆栈*/语法*p_Grammar；/*语法使用*/基本上是DFAS节点的集合*p_tree；/*解析树顶部*/...}parser_state；

解析规则被表示为确定性有限状态自动机(DFA)。DFA中的节点表示解析器的状态；弧形表示转换。过渡使用端子符号或非端子进行标记。当解析器决定遵循用非终端标记的弧线时，它被递归调用，DFA表示该解析器的解析规则作为其初始状态；当该DFA接受时，调用它的解析器继续。由通常称为解析器的解析器构造的解析树作为子级插入到当前解析树中。

解析器在解析输入时构建解析树，也称为具体语法树(CST)。与AST相反，解析树直接对应于派生输入时应用的规则。解析树中的所有节点都使用相同的节点结构表示：

Tyfinf struct_node{Short n_type；char*n_str；int n_lineno；int n_ol_Offset；int n_nChildren；struct_node*n_Child；int n_end_lineno；int n_end_colOffset；}node；

然而，解析树并不是编译器所等待的。必须将其转换为AST。此工作在Python/ast.c中完成。该算法递归地遍历解析树，并将其节点转换为AST节点。几乎没有人觉得这近6000行代码令人兴奋。

从语法角度来看，Python不是一种简单的语言。Python语法很难，看起来很简单，包括注释在内可以容纳大约200行。这是因为语法的符号是符号，而不是单个字符。令牌由类型表示，例如编号、名称、换行符、值和源代码中的位置。CPython区分了63种类型的记号，所有这些记号都列在语法/记号中。使用标准的标记化模块，我们可以看到标记化的程序是什么样子：

$python-m标记化示例2.py 0，0-0，0：编码'；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：换行'；\n'；2，0-2，4：缩进'；'；2，4-2，6：名称'；2，7-2，8：名称'；x'；2，9-2，11：操作'；>；='；2，12-2，13：编号'；0'；2，13-2，14：操作'；：'；2，14-2，15：换行'；\n'；3，0-3，8：缩进'；'；3，8-3，14：名称'；返回'；3，15-3，16：名称'；x'；3，16-3，17：新行'；\n'；4，4-4，4：DEDENT'；4，4-4，10：名称'；返回'；4，11-4，12：编号'；0'；4，12-4，13：新行'；\n&5，0：DEDENT'；'；5，0-5，0：ENDMARKER'；'；'；

这就是程序在解析器看来的样子。当解析器需要令牌时，它会从令牌化器请求一个令牌。记号赋予器一次从缓冲区读取一个字符，并尝试将SEW前缀与某种类型的记号相匹配。令牌器如何使用不同的编码？它依赖于IO模块。首先，令牌器检测编码。如果未指定编码，则默认为UTF-8。然后，记号赋予器使用C调用打开一个文件，该调用相当于Python的open(fd，mode='；r'；，coding=enc)，并通过调用readline函数读取其内容。此函数返回Unicode字符串。标记器读取的字符只是该字符串(或EOF)的UTF-8表示形式中的字节。

我们可以直接在语法中定义数字或名称是什么，尽管这会变得更加复杂。我们不能做的是表达语法中缩进的重要性，而不使其与上下文相关，因此不适合进行语法分析。标记器通过提供INTENT和DEDENT标记使解析器的工作变得容易得多。它们的意思是花括号在像C这样的语言中的意思。记号赋予器足够强大，可以处理缩进，因为它有状态。当前缩进级别保持在堆栈的顶部。当级别增加时，它会被推到堆栈上。如果级别降低，则从堆栈中弹出所有更高级别。

旧的解析器是CPython代码库的一部分。语法规则的DFA是自动生成的，但是解析器的其他部分是手工编写的。这与新的解析器形成对比，新解析器似乎是解析Python代码问题的更优雅的解决方案。

新的解析器附带了新的语法。此语法是解析表达式语法(PEG)。需要理解的重要一点是，PEG不仅仅是一类语法。这是定义语法的另一种方式。PEGS由Bryan Ford在2004年引入，作为描述编程语言和基于描述生成解析器的工具。PEG与传统形式语法的不同之处在于，它的规则将非终止符映射到解析表达式，而不仅仅是符号序列。这符合CPython的精神。对解析表达式进行归纳定义。如果\(e\)、\(e_1\)和\(e_2\)是解析表达式，那么也是：

PEG是分析语法，这意味着它们不仅被设计用来生成语言，而且还用来分析它们。Ford形式化了解析表达式\(e\)识别输入\(x\)的含义。基本上，任何使用某个解析表达式识别输入的尝试都可能成功，也可能失败，也可能消耗一些输入，也可能不使用。例如，将解析表达式\(a\)应用于输入\(ab\)会导致成功并消耗\(a\)。

这种形式化允许将任何PEG转换为递归下降解析器。递归下降解析器将语法的每个非末尾与解析函数相关联。在PEG的情况下，解析函数的主体是相应解析表达式的实现。如果解析表达式包含非终结符，则递归调用它们的解析函数。

如果某个非终端具有多个产生式规则，则递归下降解析器必须在产生式规则之间进行选择。如果语法是LL(K)，解析器可以查看输入中的下k个标记并预测正确的规则。这样的解析器称为预测性解析器。如果无法预测，则使用回溯方法。具有回溯功能的解析器尝试一条规则，如果失败，则回溯并尝试另一条规则。这正是PEG中按优先级排序的选择运算符所做的事情。因此，PEG解析器是带回溯的递归下降解析器。

回溯方法功能强大，但计算成本可能很高。考虑一个简单的例子。我们将表达式\(AB/A\)应用于在\(A\)上成功，但在\(B\)上失败的输入。根据优先选择运算符的解释，解析器首先尝试识别\(A\)，然后成功，然后尝试识别B。解析器在\(B\)上失败，然后再次尝试识别\(A)。由于这种冗余计算，解析时间可能是输入大小的指数级。为了解决这个问题，福特建议使用记忆技术，即缓存函数调用的结果。使用这种技术，可以保证解析器(称为PackRAT解析器)在线性时间内工作，但代价是占用更高的内存。这就是CPython的新解析器所做的事情。这是一个打包的解析器！

无论新解析器有多好，都必须给出更换旧解析器的原因。这就是PEP的作用。PEP617--用于CPython的新PEG解析器提供了旧解析器和新解析器的背景知识，并解释了转换背后的原因。简而言之，新的解析器消除了对语法的LL(1)限制，应该更易于维护。Guido van Rossum写了一个关于PEG解析的优秀系列，在这个系列中他进行了int。

.