1. FlyPython首页
  2. Python高级话题

Python高级话题：CPython编译器的工作方式

flypython • • Python高级话题

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

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

注意：在本文中，我指的是CPython 3.9。随着CPython的发展，某些实现细节肯定会发生变化。我将尝试跟踪重要的更改并添加更新说明。

什么是CPython编译器

我们了解了CPython编译器的职责，但是在研究其实现方式之前，让我们弄清楚为什么我们首先将其称为编译器？

一般而言，编译器是将一种语言的程序翻译成另一种语言的等效程序的程序。编译器的类型很多，但是在大多数情况下，编译器是指静态编译器，它可以将高级语言的程序转换为机器代码。CPython编译器与这种类型的编译器有共同点吗？为了回答这个问题，让我们看一下静态编译器的传统三阶段设计。

图1

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

LLVM工具链是该模型成功的一个很好的例子。有一些C，Rust，Swift和许多其他编程语言的前端，它们依赖LLVM提供编译器的更复杂部分。LLVM的创建者Chris Lattner很好地概述了其体系结构。

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

图1

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

图1

看起来相似，不是吗？这里的要点是，以前学习过编译器的任何人都应该熟悉CPython编译器的结构。如果没有的话，一本著名的Dragon Book是对编译器构造理论的出色介绍。它很长，但是即使只阅读前几章，您也会从中受益。

我们进行的比较需要一些评论。首先，从3.9版开始，CPython默认使用一个新的解析器，该解析器立即输出AST（抽象语法树），而无需建立解析树的中间步骤。因此，CPython编译器的模型被进一步简化。其次，与静态编译器的相应阶段相比，CPython编译器的某些现成阶段做得很少，有人可能会说CPython编译器不过是前端。我们不会采用硬核编译器作者的这种观点。

编译器架构概述

这些图很不错，但是它们隐藏了许多细节并且可能会引起误解，因此让我们花一些时间讨论CPython编译器的总体设计。

CPython编译器的两个主要组件是：

  1. 前端；
  2. 后端。

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

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

x  =  y  =  =  12 
        ^ 
SyntaxError: invalid syntax

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

根据经典定义，语法是一个包含四个项目的元组：

  • Σ –一组有限的终端符号，或简称为终端（通常用小写字母表示）。
  • ñ –一组有限的非终止符号，或简称为非终止符（通常用大写字母表示）。
  • P–一套生产规则。对于上下文无关的语法（包括Python语法），生产规则只是从非终结符到任何终结符和非终结符序列（例如甲→ 一乙。
  • 小号 –一个杰出的非终端。

语法定义了一种语言，其中包含可以通过应用生产规则生成的所有终端序列。要生成一些序列，请从符号开始小号然后根据生产规则将每个非末端递归替换为一个序列，直到整个序列由末端组成。使用已建立的约定惯例，列出生产规则来指定语法就足够了。例如，这是一个简单的语法，该语法生成​​交替的一和零的序列：

S→ 10 S|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 and Expr节点的定义：

stmt = ... | Assign(expr* targets, expr value, string? type_comment) | ...
expr = ... | Call(expr func, expr* args, keyword* keywords) | ...

ASDL规范应使我们了解Python AST的外观。但是，解析器需要在C代码中表示AST。幸运的是，从AST节点的ASDL描述中生成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进行更改，以在assert语句失败时提供有用的信息，该语句本身不执行任何操作，但AssertionError如果表达式的计算结果为，则会引发an False。另一个例子是Bandit，它通过分析AST查找Python代码中的常见安全问题。

现在，当我们对Python AST进行了一些研究之后，我们可以看看解析器如何从源代码构建它。

从源代码到AST

实际上，正如我之前提到的，从3.9版开始，CPython没有一个，而是两个解析器。默认情况下使用新的解析器。通过-X oldparser选项也可以使用旧的解析器。但是，在CPython 3.10中，旧的解析器将被完全删除。

这两个解析器有很大的不同。我们将重点介绍新的解析器，但同时也讨论旧的解析器。

旧解析器

很长时间以来，Python的语法是由生成语法正式定义的。这是我们之前谈到的一种语法。它告诉我们如何生成属于该语言的序列。问题在于，生成语法并不直接对应于能够解析这些序列的解析算法。幸运的是，聪明的人已经能够区分生成语法的类别，可以为其建立相应的解析器。这些包括上下文无关，LL（k）， LR（k），LALR和许多其他类型的语法。Python语法是LL（1）。使用一种扩展Backus–Naur形式指定（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 → 一个+。这种选择带来了代价：CPython必须开发一种方法来支持扩展符号。

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

由于生产规则的编写方式，CPython无法直接使用此方法，因此必须开发新方法。为了支持扩展的表示法，旧的解析器使用确定性有限自动机（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;

来自Parser / parser.c的评论总结了该方法：

解析规则表示为确定性有限状态自动机（DFA）。DFA中的一个节点代表解析器的状态；弧表示过渡。过渡用终端符号或非终端标记。当解析器决定遵循标有非终结符的弧时，将以表示该解析规则的DFA作为初始状态递归调用它；当DFA接受时，调用它的解析器将继续。由递归调用的解析器构造的解析树将作为子代插入当前的解析树中。

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

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节点。几乎没有人发现这将近6,000行代码令人兴奋。

标记器

从语法的角度来看，Python不是一种简单的语言。Python语法强悍，看起来很简单，适合大约200行，包括注释。这是因为语法符号是标记，而不是单个字符。令牌由类型表示，如NUMBER，NAME，NEWLINE，的值，并在源代码中的位置。CPython可以区分63种令牌，所有令牌都在语法/令牌中列出。使用标准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。然后，令牌生成器通过C调用打开一个文件，该调用等效于Python的C调用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的精神。解析表达式是归纳定义的。如果Ë， Ë1个和 Ë2 解析表达式，那么也是如此：

  1. the empty string
  2. any terminal
  3. any nonterminal
  4. e1e2, a sequence
  5. e1/e2, prioritized choice
  6. e∗, zero-or-more repetitions
  7. !e, a not-predicate.

PEG是一种分析语法，这意味着它们不仅被设计用来生成语言，而且还可以分析它们。福特正式化了解析表达式的含义Ë 识别输入 X。基本上，任何使用某种解析表达式识别输入的尝试都可能成功或失败，并且消耗或不消耗某些输入。例如，应用解析表达式一种 输入 一b 导致成功并消耗 一种。

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

如果某个非终结符具有多个规则，则递归下降解析器必须在生产规则之间进行选择。如果语法是LL（k），则解析器可以查看输入中的下k个标记，并预测正确的规则。这样的解析器称为预测解析器。如果无法预测，则使用回溯方法。具有回溯功能的解析器尝试一个规则，如果失败，则回溯并尝试另一个规则。这正是PEG中优先选择操作符所做的。因此，PEG解析器是具有回溯功能的递归下降解析器。

回溯方法功能强大，但计算成本很高。考虑一个简单的例子。我们应用表达式A B / A 到成功的输入 一种 但随后失败 乙。根据优先选择运算符的解释，解析器首先尝试识别一种，成功，然后尝试识别B。失败 乙 并试图认识 一种再次。由于这种冗余计算，解析时间在输入大小上可能是指数级的。为了解决这个问题，福特建议使用一种记忆技术，即，缓存函数调用的结果。使用此技术，可以保证解析器（称为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解析器的程序。语法由语法类的实例表示。但是要构建语法对象，必须为语法文件提供一个解析器。这个解析器还通过从所述解析器生成自动生成metagrammar。这就是解析器生成器可以在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。

从AST到代码对象

到目前为止，我们一直在研究CPython如何从源代码创建AST，但是正如我们在第一篇文章中看到的那样，CPython VM对AST一无所知，并且只能执行代码对象。AST到代码对象的转换是编译器的工作。更具体地说，编译器必须返回包含模块字节码的模块代码对象以及模块中其他代码块（例如定义的函数和类）的代码对象。

有时，理解问题解决方案的最佳方法是思考自己的问题。让我们考虑一下如果我们是编译器该怎么做。我们从代表模块的AST的根节点开始。该节点的子级是语句。假设第一条语句是一个简单的赋值，例如x = 1。它由AssignAST节点表示：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结构和一组_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;

在符号表的上下文中，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符号，这也很奇怪。这是因为列表理解是作为匿名函数实现的，并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 ...

字节码是线性的。该test节点的指令应该放在第一位，而该body块的指令应该放在该块的指令之前orelse。控制流语句的问题在于它们涉及跳转，并且跳转通常在它指向的指令之前发出。在我们的示例中，如果第一个测试成功，我们想立即跳转到第一body条指令，但是我们不知道它应该在哪里。如果第二次测试失败，我们必须跳过该body块到该orelse块，但是orelse只有在翻译完该body块之后，第一条指令的位置才会知道。

如果将每个块的指令移到单独的数据结构中，则可以解决此问题。然后，我们指向这些数据结构，而不是将跳转目标指定为字节码中的具体位置。最后，在翻译完所有块并知道它们的大小后，我们将计算跳转的参数并将这些块组装为单个指令序列。这就是编译器的工作。

我们正在谈论的块称为基本块。它们不是特定于CPython的，尽管CPython的基本块的概念与常规定义不同。根据Dragon的书，基本块是最大的指令序列，例如：

  1. 控制只能输入该块的第一条指令；和
  2. 除非最后一条指令可能执行，否则控制将离开该块而不会暂停或跳转。

CPython放弃了第二个要求。换句话说，除了第一个基本块的指令外，其他任何指令都不能成为跳转的目标，但是基本块本身可以包含跳转指令。为了从我们的示例转换AST，编译器创建了四个基本块：

  1. instructions 0-14 for test
  2. instructions 16-20 for body
  3. instructions 22-24 for orelse; and
  4. instructions 26-… for whatever comes after the if statement.

基本块由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语句之后的块。由于基本块彼此指向，因此它们形成了一个称为“ 控制流图（CFG）”的图。

框块

还有一个问题要解决：在编译诸如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;
};

我们已经确定了三个重要的问题，并且看到了编译器如何解决它们。现在，让我们将所有内容放在一起，看看编译器从头到尾如何工作。

编译器单元，编译器和汇编器

正如我们已经弄清楚的那样，在构建符号表之后，编译器又执行了两个步骤将AST转换为代码对象：

  1. 创建基本块的CFG；和
  2. 它将CFG组装为代码对象。

对程序中的每个代码块执行此两步过程。编译器首先构建模块的CFG，最后将模块的CFG组装到模块的代码对象中。在两者之间，它通过递归调用compiler_visit_*和compiler_*函数来遍历AST ，其中 *表示所访问或编译的内容。例如，compiler_visit_stmt将给定语句的编译委托给适当的compiler_*函数，并且该compiler_if函数知道如何编译IfAST节点。如果节点引入了新的基本块，则编译器将创建它们。如果节点开始一个代码块，则编译器将创建一个新的编译单元并输入它。编译单元是一种数据结构，可捕获代码块的编译状态。它充当代码对象的可变原型，并指向新的CFG。编译器在退出以当前代码块开头的节点时组装此CFG。汇编的代码对象存储在父编译单元中。与往常一样，我鼓励您查看struct定义：

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 */
};

对于编译至关重要的另一个数据结构是compilerstruct，它表示编译的全局状态。这是它的定义：

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中。u和c_stack由editor_enter_scope（）和compile_exit_scope（）管理。

要将基本块组装成代码对象，编译器首先必须通过将指针替换为字节码中的位置来修复跳转指令。一方面，这是一件容易的事，因为所有基本块的大小都是已知的。另一方面，修复跳转时，基本块的大小可以更改。当前的解决方案是在大小更改时保持循环中的固定跳转。这是源代码对此解决方案的诚实评论：

这是一个可怕的hack，可能会损害性能，但从好的方面来说，它应该起作用，直到我们提出更好的解决方案为止。

其余的很简单。编译器遍历基本块并发出指令。进度保存在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 */
};

此时，当前的编译单元和汇编器包含创建代码对象所需的所有数据。恭喜你！我们做到了！几乎。

窥孔优化器

创建代码对象的最后一步是优化字节码。这是窥孔优化器的工作。这是它执行的一些优化类型：

  • 该语句喜欢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源代码并了解它的某些功能。那是我们下一次的计划。

原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/advanced-python/384.html

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 29/09/2020 22:00
下一篇 » 01/12/2020 16:35

相关推荐