# Compiling Python Source Code

尽管一般并不认为 Python 是一门编译性的语言，但实际上在代码执行前 Python 源码仍会被编译成可以被 Python 虚拟机执行的字节码（ByteCode），Python 的编译过程非常直接，不涉及到很复杂的步骤

1. 将源代码 parsing 成一个 parse tree
2. 将 parse tree 转化为 AST（抽象语法树，abstract syntax tree）
3. 生成符号表（symbol table）
4. 将 AST 生成 code object，这一步包含
   1. 将 AST 转化为一个 flow control graph
   2. 从 control flow graph 产生 code object

# 从源码到 parse tree

按照 Dragon Book 中描述的 Python 的 parser 属于一种 LL(1) parser。CPython 目录下的 Grammar/Grammar 文件中包含了 Python 语言文法的 EBNF（Extended Backus-Naur Form， 扩展巴科斯范式）

Python BNF文法（部分）

......

stmt: simple_stmt | compound_stmt

simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE

small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt |

             import_stmt | global_stmt | nonlocal_stmt | assert_stmt)

expr_stmt: testlist_star_expr (annassign | augassign (yield_expr|testlist) |

                     [('=' (yield_expr|testlist_star_expr))+ [TYPE_COMMENT]] )

annassign: ':' test ['=' (yield_expr|testlist_star_expr)]

testlist_star_expr: (test|star_expr) (',' (test|star_expr))* [',']

augassign: ('+=' | '-=' | '*=' | '@=' | '/=' | '%=' | '&=' | '|=' | '^=' |

            '<<=' | '>>=' | '**=' | '//=')

# For normal and annotated assignments, additional restrictions enforced by the interpreter

del_stmt: 'del' exprlist

pass_stmt: 'pass'

flow_stmt: break_stmt | continue_stmt | return_stmt | raise_stmt | yield_stmt

break_stmt: 'break'

continue_stmt: 'continue'

return_stmt: 'return' [testlist_star_expr]

yield_stmt: yield_expr

raise_stmt: 'raise' [test ['from' test]]

import_stmt: import_name | import_from

import_name: 'import' dotted_as_names

# note below: the ('.' | '...') is necessary because '...' is tokenized as ELLIPSIS

import_from: ('from' (('.' | '...')* dotted_name | ('.' | '...')+)

              'import' ('*' | '(' import_as_names ')' | import_as_names))

import_as_name: NAME ['as' NAME]

......

每次从命令行中运行一个 Python 模块时，PyParser_ParseFileObject 函数会启动对这个模块 parsing 过程，它会调用 tokenization 函数 PyTokenizer_FromFile，它接受模块的文件名作为参数，将模块文件的内容分解为一个个合法的 python tokens 或者发现语法错误时进行报错。

# Python tokens

Python 源码可以看作是一段由 token 组成的序列，比如说 return 就是一个 keyword token，字面量 - 2 是一个数值字面量 token 等等。Parsing Python 源码的第一步就是将源码分割为一个个的 token。

Python 中存在以下几种 token：

1. identifiers：由程序员定义的名字，包括函数名、变量名、类名等等。它必须符合 Python 文档中指定的规范
2. operators：一些特殊符号，比如 +，* 能够对值进行运算产生结果
3. delimiters：这类符号用来给表达式分组、提供标点、赋值操作，包括（，），{，}，=，*= 等。
4. literals：字面量，这类符号用于提供一些类型的常量。比如字符串、bytes 类型的字面量：“Hello”，b"Hello"，数值类型的字面量 2，浮点类型字面量 1e100，虚数字面量 10j
5. comments：以 #开头字符串字面量，用户注释。commects 总是位于一个 physical line 的结尾（规范）
6. NEWLINE：用于指示一行（logical line）的结束
7. INDENT 与 DEDENT：表示一组符合语句（compound statements）的缩进层级（identation levels）

一组 tokens 通过一个 NEWLINE token 被分割，组成一个 logical line，因此我们可以说 Python 程序由一系列被 NEWLINE token 分割的 logical line 组成。这个 logical line 可以映射到 Python 语句。每一个 logical line 又由一系列的 physical lines 所组成，physical line 的结尾是一个换行符（end of line）。多个 physical line 可以被连接在一起，连接可能是隐式的，比如在括号中的时候（包括 ()，[]，{} 三种），也可能是显示的，就是在末尾使用一个反斜杠 \，

缩进对于 Python 语句的分组非常重要，Python grammar 中有一条规则用于对它进行描述：suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT，因此 Python tokenizer 的一项主要任务就是生成 INDENT 和 DEDENT 到 parse tree。

Tokenizer 使用一个栈来保持对缩进的跟踪，INDENT 和 DEDENT token 生成算法如下

# 伪代码

使用 0 初始化 indent栈

for 每一个 logical line:

    if (当前行的缩进级别 > 栈顶的级别):

        push(当前缩进级别)

        生成一个 INDENT token

    if (当前行的缩进级别 < 栈顶的级别):

        if (栈中不存在一个缩进级别 == 当前缩进级别):

            报告一个错误

        for 栈顶的每一个 != 当前行缩进级的值:

            移除这个值

            生成一个 DEDENT token

    tokenize(当前行)

对每一个栈上的值（处了0）生成DEDENT token

CPython 的实现中 PyTokenizer_FromFile 函数会按照从左到右，从上到下的对 Python 源码文件进行扫描并进行 tokenize。空格字符除了终止符被用来分隔开 token，但这不是必须的。如果其中存在歧义，则按照从右到左合法的可能的最长字符串来理解。比如说 2+2，是一个字面量 2，一个 operator +，另一个字面量 2。

在 python 中提供了 tokenize 的接口（标准模块函数 tokenize.tokenize）可以使用它对 python 源代码进行 tokenize，它接受一个 ByteIO.readline 的 callable 对象返回一个 tokens 的 generator，对这个 generator 进行迭代就能得到被解析模块的 tokens 序列

>>> from tokenize import tokenize

>>> f = open("./demo1.py", "rb") # 只有一行 print ("hello")

>>> for t in tokenize(f.readline):

...     print(t)

...

TokenInfo(type=62 (ENCODING), string='utf-8', start=(0, 0), end=(0, 0), line='')

TokenInfo(type=1 (NAME), string='print', start=(1, 0), end=(1, 5), line='print("hello")')

TokenInfo(type=54 (OP), string='(', start=(1, 5), end=(1, 6), line='print("hello")')

TokenInfo(type=3 (STRING), string='"hello"', start=(1, 6), end=(1, 13), line='print("hello")')

TokenInfo(type=54 (OP), string=')', start=(1, 13), end=(1, 14), line='print("hello")')

TokenInfo(type=4 (NEWLINE), string='', start=(1, 14), end=(1, 15), line='')

TokenInfo(type=0 (ENDMARKER), string='', start=(2, 0), end=(2, 0), line='')

还可以在命令行直接调用 tokenize

$ python -m tokenize demo1.py

0,0-0,0:            ENCODING       'utf-8'

1,0-1,5:            NAME           'print'

1,5-1,6:            OP             '('

1,6-1,13:           STRING         '"hello"'

1,13-1,14:          OP             ')'

1,14-1,15:          NEWLINE        ''

2,0-2,0:            ENDMARKER      ''

tokenizer 生成的 tokens 随后会被传递给 parser 根据 Python 的语法来生成 parse tree。当 parser 发现一个 token 违反了语法规则时，就会抛出 SyntaxError。

Python 中有一个 parser 模块提供了有限的对 parse tree 的访问能力

>>> import parser

>>> from pprint import pprint

>>> code_str = """

... def hello_world():

...     return "hello world"

... """

>>> st = parser.suite(code_str)

>>> pprint(parser.st2list(st))

[257,

 [269,

  [295,

   [263,

    [1, 'def'],

    [1, 'hello_world'],

    [264, [7, '('], [8, ')']],

    [11, ':'],

    [304,

     [4, ''],

     [5, ''],

     [269,

      [270,

       [271,

        [278,

         [281,

          [1, 'return'],

          [274,

           [306,

            [310,

             [311,

              [312,

               [313,

                [316,

                 [317,

                  [318,

                   [319,

                    [320,

                     [321,

                      [322,

                       [323,

                        [324, [325, [3, '"hello world"']]]]]]]]]]]]]]]]]]]],

       [4, '']]],

     [6, '']]]]],

 [4, ''],

 [0, '']]

函数调用 parser.suite (source) 会返回一个 Python 中对 parser tree 的中间值表示即 parser tree（ST）对象。list 中的第一个元素为一个 int 类型的数字，表示 Python grammar 中对应的 identifier 编号

途中展示了代码中产生的 parse tree 结构，可以看到其中每个节点的类型可以用一个整数来表示，这些整数的定义位于头文件 Include/token.h 和 Include/grammar.h 中

在 CPython 虚拟机中，使用树结构来对 parser tree 进行表示。每一个产生式规则（production rule）是树中的一个节点（node）。对 node 的定义位于头文件 Include/node.h 中。

typedef struct _node {

    short               n_type;

    char                *n_str;

    int                 n_lineno;

    int                 n_col_offset;

    int                 n_nchildren;

    struct _node        *n_child;

} node;

可以对 parser tree 进行遍历，访问节点的类型、子节点、行号等，这些操作以宏（macro）的形式定义在头文件 Include/node.h 中，用于与 parse tree 的节点进行交互。

# 从 parse tree 到 AST

生成 parse tree 之后，下一步就是将其转换为 AST（抽象语法树，Abstract Syntax Tree）。AST 是一种与语法细节无关的代码表示，如上图 parse tree 中有一个逗号节点（colon node），因为它属于其中的语法构造（syntax construct），但是 AST 中将不会包含这样的语法构造

>>> import ast

>>> node = ast.parse(code_str, mode="exec")

>>> ast.dump(node)

"Module(body=[FunctionDef(name='hello_world', args=arguments(posonlyargs=[], args=[], kwonlyargs=[], kw_defaults=[], defaults=[]), body=[Return(value=Constant(value='hello world'))], decorator_list=[])], type_ignores=[])"

AST 节点的定义可以在 Parser/Python.asdl 文件中找到（ASDL 是一种用来描述 AST 的语言，参考 Eli Bendersky 的博文）。

AST 中几乎所有的定义都与特定的语法构造有关，比如 if 语句或者属性查找（attribute lookup）。

在 CPython 的实现中，AST 节点以 C 结构体的形式定义在 Include/Python-ast.h 中。实际上，这些结构体是通过 Python 代码生成的，Parser/asdl_c.py 模块可以根据 AST 的 asdl 定义来生成它们。比如说，语句（statement）节点的结构体一部分定义如下

struct _stmt {

    enum _stmt_kind kind;

    union {

        struct {

            identifier name;

            arguments_ty args;

            asdl_seq *body;

            asdl_seq *decorator_list;

            expr_ty returns;

            string type_comment;

        } FunctionDef;

        struct {

            identifier name;

            arguments_ty args;

            asdl_seq *body;

            asdl_seq *decorator_list;

            expr_ty returns;

            string type_comment;

        } AsyncFunctionDef;

        struct {

            identifier name;

            asdl_seq *bases;

            asdl_seq *keywords;

            asdl_seq *body;

            asdl_seq *decorator_list;

        } ClassDef;

        ......

    }

    int lineno;

    int col_offset;

    int end_lineno;

    int end_col_offset;

}

上面的代码中，union 类型用来表示任意一个位于其中的 C 类型。文件 Python/ast.c 中的 PyAST_FromNode 函数能够根据 parse_tree 来生成 AST 之后，生成 AST 之后，下一个就是根据 AST 来生成字节码了。

# 构建符号表

生成 AST 之后，下一步是生成符号表（symbol table）。符号表就如同它的名字所暗示的那样，是一个代码块（code block）与上下文（context）中所使用到的名字的集合。

符号表的构建过程涉及到对一个代码块中所包含的所有名字以及这些名字正确作用域赋值的分析。在讨论复杂的符号表生成之前，首先对一些名字（names）、绑定（bindings）相关概念进行讨论。

# 名字与绑定

在 Python 中，对象通过名字进行引用，names 与 C++ 和 Java 中变量并不一样。

>>> x = 5

上述代码，x 其实是一个对于对象 5 的引用，将对象 5 的引用赋值给名字（name）x 的过程称为绑定（bindind）。一个绑定行为所产生的结果是一个名字在执行过程中最内层的作用域中与一个对象产生关联。

绑定可能发生在几个不同的情况下，比如在变量赋值过程中，或者发生在函数或者方法调用时实参与型参的绑定。

名字只是符号，它们并没有与类型相关联，名字只是对带有类型的对象的引用而已

# 代码块

代码块（code block）是 Python 的重要概念之一，对于理解 Python 虚拟机的内部机制非常重要。

代码块是一个能够在 Python 中作为独立单元执行的代码片段，比如模块、函数和类，REPL 中的命令，命令行中使用 - c 参数执行的脚本也是代码块。一个代码块由多个与它相关的 namespace，比如一个模块代码能够访问 global namespace，一个函数代码块可以同时访问 local 和 global namespace。

# Namespace

namespace，名字空间，可以理解为一个环境（context）在其中，一系列名字与对象被绑定在一起。比如 builtin namespace 是一个包含了所有 built-in 函数的 namespace，它可以通过__builtins__.__dict__被访问。解释器能够访问多个 namespace，包括 global，builtin，local。这些 namespace 在不同的时间点被创建，具有不同的生命周期。比如一个新的 local namespace 在一个函数调用时创建，在一个函数退出或返回时销毁。global namespace 在一个模块开始执行时被创建，并且所有定义在其中的名字能够在模块级别上进行访问。而 built-in namespace 则在解释器被调用时创建，并且其中包含了所有的 builtin names。这三者是 Python 解释器中所主要使用的 namespace。

# Scope

一个作用域（scope）是程序中的一块区域，在作用域中 namespace 可以不通过任何的 . （dotnotaion）直接访问。在运行时（runtime）中存在以下几种作用域：

1. 局部命名空间的最内层作用域
2. 闭合函数（enclosing functions）作用域（存在嵌套函数时有用）
3. 当前模块的 globals 作用域
4. 包含 builtin namespace 的作用域

当一个名字在 Python 中可用时，解释器会在 scope 的 namespace 中以由内到外的顺序进行搜索，如果在所有的 namespace 中都没有找到，就会抛出 NameError 异常，Python 支持静态作用域（static scoping），也被称为词法作用域（lexical scoping），也就是说通过对程序代码的检查就可以推到出名字绑定。

未定义行为，在函数内修改 locals ()，会报错

>>> def func():

...     locals()['a'] = 1

...     print(locals()['a'])

...     print(a)

...     return locals()

...

>>> func()

1

Traceback (most recent call last):

  File "<stdin>", line 1, in <module>

  File "<stdin>", line 4, in func

NameError: name 'a' is not defined

这是一个 Python 中的未定义行为，可以参考 PEP558

Python 中存在一个作用域规则，看起来很奇怪，它会阻止在 local 作用域中修改 global 作用域中的对象。如果发生这样的行为，解释器会抛出 UnBoundLocalError 异常。

>>> a = 1

>>> def inc_a():

...     a += 1

...

>>> inc_a()

Traceback (most recent call last):

  File "<stdin>", line 1, in <module>

  File "<stdin>", line 2, in inc_a

UnboundLocalError: local variable 'a' referenced before assignment

在函数内的 a 在查找时被编译为 LOAD_FAST 字节码，会在局部作用域中查找

case TARGET(LOAD_FAST): {

    PyObject *value = GETLOCAL(oparg);

    if (value == NULL) {

        // 找不到，抛出异常

        format_exc_check_arg(tstate, PyExc_UnboundLocalError,

                                UNBOUNDLOCAL_ERROR_MSG,

                                PyTuple_GetItem(co->co_varnames, oparg));

        goto error;

    }

    // ......

}

为了能够在局部作用域中对全局作用域中的对象进行修改，需要使用 global 关键字

>>> a = 1

>>> def inc_a():

...     global a

...     a += 1

...

>>> inc_a()

>>> a

2

最终 a 被编译为 LOAD_GLOBAL，会在全局作用域中或者内置里查找，再通过 STORE_GLOBAL 设置

case TARGET(LOAD_GLOBAL): {

    PyObject *name;

    PyObject *v;

    if (PyDict_CheckExact(f->f_globals)

        && PyDict_CheckExact(f->f_builtins))

    {

        // ......

    }

    // ......

}

Python 还有一个 nonlocal 关键字用来在内层的作用域中修改一个外层的非全局作用域。比如嵌套函数（闭包（closure））

>>> def make_counter():

...     count = 0

...     def counter():

...         nonlocal count

...         count += 1

...         return count

...     return counter

...

>>> counter_1 = make_counter()

>>> counter_2 = make_counter()

>>> counter_1()

1

>>> counter_1()

2

>>> counter_2()

1

>>> counter_2()

2

了解 names 与 binding 的概念之后，来看如何根据 AST 生成符号表

符号表涉及到一系列的函数调用：

run_mod -> PyAST_CompileObject -> PySymtable_BuildObject

函数 PySymtable_BuildObject 所接受的两个参数分别是之前生成的 AST 对象与该模块的文件名。符号表的创建算法可以分为两个步骤，第一个步骤中，被作为参数传递给 PySymtable_BuildObject 的 AST 中的每个节点都会被按照顺序遍历，创建出一系列在 AST 中被使用的符号。

伪代码描述

# 从AST创建符号表的算法

for node in AST: # 遍历AST

    if (node 是一个 code block 的起始):

        ste = 新建符号表项目()

        st.st_stack_push(ste) # 新的符号表入栈

        st.current_ste.children.append(st) # 将新表项加入上一个表项的子表项

        st.current_ste = ste # 将符号表的当前表项设置为新建的符号表项

        for node1 in code_block.nodes: # 遍历code_block里的所有节点

            # 递归访问node1创建符号加入表项中，XXX是node1的类型

            symtable_visit_XXX(node1)

        st.st_stack.pop() # 将当前表项移出栈

        st.current_st = st_stack.pop()

    else:

        递归访问node与sub_nodes(node) 创建符号加入符号表

在第一轮在 AST 上进行的算法完成后，符号表内已经包含了模块中使用的所有名字，但并不包含这些名字的上下文信息，比如说，解释器不能告诉你一个给定的变量是一个全局变量，局部变量还是自由变量（free variables）。

符号表生成的第二阶段从一个对 Python/symtable.c 中 symtable_analyze 函数调用开始。这个阶段的算法将对第一个阶段中产生的符号分配作用域（local、global、free）。

Parser/symtable.c 文件中的注释信息十分丰富设置九分（压力吗斯内）

符号表需要两个 pass 才能确定每个名称的范围，第一个 pass 通过 symtable visit * 函数从 AST 收集原始信息，而第二个 pass 通过 pass1 中创建 PySTEntryObject 分析这些信息。

在 pass2 中输入函数时，父级将传递对其子级可见的所有名称绑定集，这些绑定用于确定非全局变量是自由变量还是隐式全局变量，在这组可见名称中必须存在明确声明为非本地的名称，如果不存在，则会引发语法错误。进行局部分析后，它使用在第 1 遍过程中创建的一组更新的名称绑定分析每个子块。

全局变量也有两种，隐式和显式。使用全局语句声明显式全局变量。隐式全局变量是一个自由变量，编译器在封闭的函数范围内未发现其绑定。隐式全局是全局或内置的。

Python 的模块和类块使用 xxx_NAME 操作码来处理这些名称，以实现稍微奇怪的语义。在这样的块中，名称被分配为全局名称，直到被分配给该名称为止。然后将其视为本地对象。

子代更新自由变量（free variables）集合。如果将局部变量添加到子级设置的自由变量中，则该变量将标记为单元格。定义的功能对象必须为可能超过功能范围的变量提供运行时存储。在分析函数返回其父级之前，将单元变量从自由集合中删除。

尽管注释试图用简单清晰的语言来解释过程，但仍有比较模糊的地方。比如：passes the set of all name bindings visible to its children，parent 与 children 指的是什么？我们来看下符号表的数据结构

# 符号表数据结构

符号表生成过程中有两个核心的数据结构：

1. The symbol table data structure（符号表）
2. The symbol table entry data structure（符号表项目）

符号表数据结构定义在头文件 Include/symtable.h 中，我们可以认为符号表由一系列持有给定模块中不同 code blocks 信息的表项所组成。

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

};

一个 Python 模块可能包含多个 code block，比如多个函数定义。结构体中的 st_blocks 字段是一个所有 code block（AST node）到符号表项的映射。st_top 字段是一个符号表项，对应于一个被编译的模块（注意，模块也是一个 code block），所以它将包含所有定义在模块 global namespace 中的名字。st_cur 字段指向一个符号表项目，该表项对应于正在被处理的 code block（AST node）。模块中的每个 code block 都有一个它自己的符号表项，它持有所有定义在其中的符号。

再来看一下 Include/symtable.h 中 _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_symbols 字段是一个包含了该 code block 中所确认到的所有符号到 flag 的映射，其中 flag 是一个数值类型的值，它提供了符号在该环境中所具有的含义。比如，一个符号可能是一个函数参数或者是一个全局定义。flag 具体被定义在文件 Include/stmtable.h 中

/* Flags for def-use information */

#define DEF_GLOBAL 1           /* global stmt */

#define DEF_LOCAL 2            /* assignment in code block */

#define DEF_PARAM 2<<1         /* formal parameter */

#define DEF_NONLOCAL 2<<2      /* nonlocal stmt */

#define USE 2<<3               /* name is used */

#define DEF_FREE 2<<4          /* name used but not defined in nested block */

#define DEF_FREE_CLASS 2<<5    /* free variable from class's method */

#define DEF_IMPORT 2<<6        /* assignment occurred via import */

#define DEF_ANNOT 2<<7         /* this name is annotated */

#define DEF_COMP_ITER 2<<8     /* this name is a comprehension iteration variable */

假设一个模块包含如下代码：

def make_counter():

    count = 0

    def counter():

        nonlocal count

        count += 1

        return count

    return counter

那么它被编译后会产生三个符号表项：

1. 第一个表项是模块级别的表项，它将包含定义一个带有局部作用域的 make_counter
2. 第二个表项是进入到 make_counter 函数中，它包含定义在局部作用域的 count 和 counter
3. 第三个表项是进入到嵌套定义的 counter 函数，它包含一个被标记为 free 的 count 变量

值得注意的是，虽然 make_counter 在模块 code block 表项中是局部的，但它会被看作是被全局定义在模块 code block 中，因为符号表的 st_global 字段指向了 st_top 对应的符号，也就是模块 code block 下的符号（st_top->ste_symbols）。

# 从 AST 到 code objects

符号表生成之后，编译过程的下一步就是根据 AST 以及符号表中的信息来生成 code object。负责这个过程的处理函数定义在文件 Python/compile.c 中。生成 code object 也是一个多步的过程。在第一步中，AST 被转换为 Python 字节码指令的基础块（basic blocks）。这里使用的算法与生成符号表时的算法很相似。由一系列命名为 compiler_visit_xx 的函数来进行，xx 指的是节点的类型，这些函数都会递归地访问每一个 AST 节点，并在访问过程中产生 Python 字节码指令的基础块。基础指令块以及块之间的路劲被隐式的表示为图（graph）结构，也称之为控制流图（control flow graph，CFG）。这个图体现了在运行过程中的代码路径。然后进入 code object 生成的第二阶段，以后缀深度优先遍历的方式将前一步生成的控制流图扁平化（flatten），图被扁平化之后，跳转偏移量被计算出来作为 jump 指令的参数。然后再根据这些指令生成 code object，为了更好理解，看如下函数

def fizzbuzz(n):

    if n % 3 == 0 and n % 5 == 0:

        return 'FizzBuzz'

    elif n % 3 == 0:

        return 'Fizz'

    elif n % 5 == 0:

        return 'Buzz'

    else:

        return str(n)

函数对应的 AST 如图：

fizzbuzz 函数对应的控制流图，其中的直线代表代码正常的运行顺序，曲线代表跳转。

接下来看看看看每个 block 对应的字节码

Block 1：在这个 block 表达式中 n % 3 == 0 and n % 5 == 0 通过以下指令实现

2           0 LOAD_FAST                0 (n)

            2 LOAD_CONST               1 (3)

            4 BINARY_MODULO

            6 LOAD_CONST               2 (0)

            8 COMPARE_OP               2 (==)

            10 POP_JUMP_IF_FALSE       28

            12 LOAD_FAST                0 (n)

            14 LOAD_CONST               3 (5)

            16 BINARY_MODULO

            18 LOAD_CONST               2 (0)

            20 COMPARE_OP               2 (==)

            22 POP_JUMP_IF_FALSE       28

有两个途径可以离开这个 block，直接执行完毕之后离开或者执行 POP_JUMP_IF_FALSE 指令跳转离开进入 block 2。

当解释器执行 if 语句的字节码指令时，它会从栈上读取一个对象，根据对象的布尔值来决定执行下一条指令或者跳转到另一个地方继续执行那里的指令。指令 POP_JUMP_IF_FALSE 就是一个负责跳转的指令。

Block 2：包含以下指令

4     >>   28 LOAD_FAST                0 (n)

           30 LOAD_CONST               1 (3)

           32 BINARY_MODULO

           34 LOAD_CONST               2 (0)

           36 COMPARE_OP               2 (==)

           38 POP_JUMP_IF_FALSE       44

elif 语句和 n % 3 == 0 在同一个 block 中，原因很明显，因为该 block 不需要额外的 jump 出口。

Block 3：与 Block 2 相似，只是指令的参数不同

Block 4：映射到最终的 orElse AST 指令节点

9     >>   60 LOAD_GLOBAL              0 (str)

           62 LOAD_FAST                0 (n)

           64 CALL_FUNCTION            1

           66 RETURN_VALUE

           68 LOAD_CONST               0 (None)

           70 RETURN_VALUE

LOAD_GLOBAL 接受一个 str 参数，将 str 函数加载到栈上。LOAD_FAST 将参数 n 加载到栈上。RETURN_VALUE 将把栈上调用 CALL_FUNCTION 后得到的值返回。

# 编译器数据结构

下图展示了组成 CFG 基础块生成过程中涉及到的主要数据结构之间的关系：

在顶层是一个 compiler 数据结构，它捕获了模块的全局编译过程，这个结构体定义在 Python/compile.c 文件中。

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

};

1. *c_st：指向之前生成的符号表
2. *u：一个到 compiler unit 结构体的引用。这个结构体封装了与一个 code block 进行交互所需的信息。本字段指向目前正在处理的 code block 所对应的 compiler unit。
3. *c_stack：一个到 compiler unit 栈的引用。当一个 code block 由多个 code block 所组成时，这个字段负责当前遇到一个新的 block 时 compiler unit 结构体的储存与恢复。当进入一个新的 code block 时，一个新的作用域被创建，然后 compiler_enter_scope() 会将当前的 compiler unit（u）push 到栈中。同时 c_stack 创建一个新的 compiler unit 对象，并将其设置为当前 compiler unit。当离开一个 block 时，*c_stack 会根据复原状态进行弹出。

对于每个被编译的模块，对应一个被初始化的 complier 数据结构。当 AST 被遍历，其中每一个 code block 对应的 compiler_unit 数据结构会被生成。

# compiler_unit 数据结构

compiler_unit 结构体定义，它持有生成一个 code block 对应的字节码指令所需的信息。

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

};

字段 u_blocks 与 u_curblock 用于引用那些组成被编译的 code block 的基础块。*u_ste 字段为到一个被编译的 code block 中的符号表项的引用。其余字段从名字上比较好理解。组成 code block 的不同节点在编译过程中被遍历，并且根据一个节点类型是否能够起始一个 basic block，一个含有 node 对应指令的 basic block 会被创建，或者有新指令被添加到已有的 basic block 中。能够起始一个 basic block 的节点类型包括但不限于：

1. 函数节点
2. 跳转目标
3. 异常处理
4. 布尔运算等

# basic block 与 instruction 数据结构

一个 basic block 是一个具有单一入口与多个出口的指令序列。

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;

CFG 由一系列 basic blocks 以及它们之间的连接所组成。*b_instr 字段引用到一个指令结构体的数组，一个指令结构体对应一条字节码指令，字节码指令的编号可在头文件 Include/opcode.h 中找到。指令结构体 instr 定义在文件 Python/compile.c 中

//instr 数据结构

struct instr {

    unsigned i_jabs : 1; // 绝对跳转 jump absolute

    unsigned i_jrel : 1; // 相对跳转 jump relative

    unsigned char i_opcode;

    int i_oparg;

    struct basicblock_ *i_target; /* target block (if jump instruction) */

    int i_lineno;

};

在上面的控制流图中，可以看到 block1 到 block2 存在两条可行的路径。第一条路径是正常执行由 block1 到 block2，第二条是在第一次比较时直接跳转到 block2。现在跳转的目标还是 basic block，但实际过程中 code object 中只有字节码流（bytecodes stream），并且只能通过偏移量对它进行索引，与 basic block 没有关系。我们必须将使用 block 中创建的隐式图作为跳转目标，并以某种方式将这些具有偏移的 block 替换为指令数组。这就是 basic blocks 的汇编（assembling）过程。

# 汇编 basic blocks

一旦 CFG 被生成，basic blocks 包含了字节码指令，但目前这些 blocks 还不是线性排列的。跳转指令的目标仍是 basic block 而不是指令流中的绝对偏移量。assemble 函数将会把 CFG 进行线性排列，生成 code object。

首先，assemble 函数会在任何没有 return 语句的 block 结尾添加一个 return None，现在你就直到为什么可以在函数和方法中可以不写 return 了吧。然后会以后序深度优先（post-order deep first）的方式遍历 CFG 图，对它进行扁平化。后序遍历指的是在遍历时先访问所有的子节点，再访问根节点。

图遍历

在对一个图进行后序深度优先遍历时，我们首先会递归的访问一个根节点的左子节点，然后是右子节点，然后才是这个根节点自己。比如以上面这个图结构，以后序深度优先遍历对它进行扁平化时，对节点的访问顺序是： H -> D -> I -> J -> E -> B -> K -> L -> F -> G -> C -> A。如果是前序遍历的话：A -> B -> D -> H -> E -> I -> J -> C -> F -> K -> L -> G。如果是中序遍历：H -> D -> B -> I -> E -> J -> A -> K -> L -> F -> C -> G

fizzbuzz 函数的 CFG 相对比较简单，如果对它进行后序遍历，顺序是 block5 -> block4 -> block3 -> block2 -> block1。当 CFG 被扁平化（线性化）后，扁平化图的跳转指令的跳转偏移量就可以被 assemble_jump_offsets 函数计算出来了。

对跳转偏移量的汇编需要两个阶段，第一个阶段，每条指令的偏移量会被计算出来放进指令数组中，向下面代码，这是一个简单的循环，它从被 CFG 扁平化后得到的数组的末尾开始从 0 开始生成每一个 block 对应的偏移量。

// 计算字节码偏移量

// ......

totsize = 0;

for (i = a->a_nblocks - 1; i >= 0; i--) {

    b = a->a_postorder[i];

    bsize = blocksize(b);

    b->b_offset = totsize;

    totsize += bsize;

}

// ......

在第二阶段，跳转指令的跳转目标偏移量被计算出来，这一步涉及到计算绝对跳转与相对跳转的跳转地址：

// 汇编跳转目标偏移量

// ......

for (b = c->u->u_blocks; b != NULL; b = b->b_list) {

    bsize = b->b_offset;

    for (i = 0; i < b->b_iused; i++) {

        struct instr *instr = &b->b_instr[i];

        int isize = instrsize(instr->i_oparg);

        /* Relative jumps are computed relative to

            the instruction pointer after fetching

            the jump instruction.

        */

        bsize += isize;

        if (instr->i_jabs || instr->i_jrel) {

            instr->i_oparg = instr->i_target->b_offset;

            if (instr->i_jrel) {

                instr->i_oparg -= bsize;

            }

            instr->i_oparg *= sizeof(_Py_CODEUNIT);

            if (instrsize(instr->i_oparg) != isize) {

                extended_arg_recompile = 1;

            }

        }

    }

}

// ......

随着跳转地址被计算，扁平化后的 CFG 内的指令以反向后序顺序（reverse post order）被生成。反向后序顺序是对 CFG 的拓扑排序，也就是说对于 CFG 中所有的边（u, v），在这个排序中 u 都会排在 v 前面。这样做的原因，一般来说想要把跳转的起点放在终点之前。当字节码生成完毕，code object 对象就可以根据这些字节码以及符号表中的信息进行生成，code object 对象返回给调用函数的时候，整个编译过程就在此结束了。

来源：https://leanpub.com/insidethepythonvirtualmachine