本文尝试理解Python前端的编译实现内幕，如果仅仅是读取文档，或者查看Python的实现代码，会让人感觉迷迷糊糊的，所以我的想法是动手来做一些事情：添加一个新语句until到Python编译器实现里。
所有跟本文相关的代码，都是使用Python3.4.3版本的代码，可以从CSDN的代码托管里找到，连接如下：
https://code.csdn.net/caimouse/milang/tree/master
打开上面连接下载代码，就是简单直接打包下载，然后解压到一个目录即可。
在一些编译语言里，比如像Ruby，它有实现一个until语句，它的功能与while语句有点像（until num == 0 等同于while num != 0）。在Ruby语言里，语法使用的例子可以写成下面这样：
num = 3
until num == 0 do
puts num
num -= 1
end
在上面例子里将会输出如下：
3
2
1
所以我想添加一个与上面相同语法的语句到Python里，它的例子代码如下所示：
num = 3
until num == 0:
print(num)
num -= 1
本文不是建议往官方Python实现里添加一个until语句，让Python发行版本添加一个新语法，而是作为一个理解Python内部实现的例子，动手的基本材料。尽管until语句使用起来更简洁一些，并且本文添加这个实现进去也不困难，但我还是完全遵守Python的极简主义的，语法数量上的最简单化。实现这个语法的目的，只是为了理解上更容易一些。
Python使用一个叫做pgen分析生成器来处理语法定义，它是一个LL(1)的语法分析器，负责把Python源码转换为分析树。pgen分析器主要读取一个文件Grammar/Grammar，而它只是一个简单的文本文件，定义整个Python语法规则。
为了增加until语句，需要在语法文件里修改两个地方。第一个修改的地方，就是添加until语句。我发现添加在while语句后面位置最为合适，而while语句定义为while_stmt，我也照猫画虎一样，在后面添加了until_stmt语句，如下所示：
compound_stmt: if_stmt | while_stmt | until_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
while_stmt: 'while' test ':' suite ['else' ':' suite]
until_stmt: 'until' test ':' suite
或许你已经注意到上面的语法里，until的语法与while的语法有点不同，在until语法里没有else语句。这样做的原因，主要就是为了与上面while语法要有点区别，同时我也不喜欢在循环之后，还要有一个else语句成分，本次这样做也不必要考虑Python宗旨了，因为这里只是作为教学。
第二个改变，就是在compound_stmt语句里包括until_stmt语句，正如你上面看到那样，它同样是添加在while_stmt语句后面。
在Linux系统里，当修改Grammar/Grammar文件之后，调用make程序来编译，就会注意到使用pgen程序来重新把语法文件生成两个文件：Include/graminit.h和Python/graminit.c，然后与此相关的文件就进行重新编译。
在Windows系统里，当修改Grammar/Grammar文件之后，并没有相应的工程来生成pgen程序，也没有相应的工程来对语法进行处理。这时，就需要先建立一个pgen的工程，把pgen相关的文件添加到工程里，进行编译生成pgen程序。在目录cpython\PCbuild\Pgen建立一个工程Pgen.sln，这个工程是一个终端的应用程序，需要把下面的文件添加进去：
acceler.c
bitset.c
dynamic_annotations.c
firstsets.c
grammar.c
grammar1.c
listnode.c
metagrammar.c
mysnprintf.c
node.c
obmalloc.c
parser.c
parsetok_pgen.c
pgen.c
pgenmain.c
printgrammar.c
tokenizer_pgen.c
最后编译这个工程，就会生成pgen.exe可执行文件。为了从Grammar/Grammar文件重新生成相关的文件，需要在目录cpython下面编写一个批处理文件gram.bat，这个文件内容如下：
.\PCbuild\Pgen\Debug\pgen.exe Grammar/Grammar Include/graminit.h Python/graminit.c
如果修改一次语法文件，就需要运行一次这个批处理文件，以便新修改的语法文件起作用。
经过Python词法分析器处理之后，就会生成一棵分析树，然后再把分析树转换为AST树。因为AST树在后面编译阶段处理时变得更加简单。
因此，需要修改定义AST树的文件Parser/Python.asdl文件，这个文件详细描述了Python的AST树的结构，同时我添加了until语句到这个文件里，如下所示：
| While(expr test, stmt* body, stmt* orelse)
| Until(expr test, stmt* body)
如果你现在去运行make程序，会注意到要编译这些文件就需要运行Parser/asdl_c.py文件，此文件的作用就是把AST的定义文件生成C代码文件。这是另外一个使用定义语言来简化Python的源码生成的例子，像之前的Grammar/Grammar一样，它这里是采用定义语言DSL。由于Parser/asdl_c.py是一个Python脚本文件，要运行它就得先安装有Python运行版本。你也许会问，本来是为了生成Python编译器的，结果还需要Python编译器来运行，那么在没有Python编译器之前，怎么样生成这个文件。其实这个问题，就是编译器的自举问题。一般情况是这样，先使用别的语言来编写第一个版本，然后再从第一个版本来编译第二个版本，这样就完成自举的问题了。因此，这里要编译Python3.4版本，必须安装Python2.7的版本来运行Parser/asdl_c.py文件。
在Linux系统下，运行make来编译，就可以生成AST定义节点代码（Include/Python-ast.h和Python/Python-ast.c）。在Windows系统下，采用批处理文件来完成这个工作，创建一个批处理文件asdl.bat，内容如下：
c:\python27\python.exe Parser/asdl_c.py -h Include Parser/Python.asdl
c:\python27\python.exe Parser/asdl_c.py -c Python Parser/Python.asdl
当生成这些代码之后，还需要手工地添加一些代码，才可以把分析树转换为AST节点。跟前面的做法一样，在文件Python/ast.c的函数ast_for_stmt里找到while语句的地方，然后在那个switch大循环里添加until_stmt：
case while_stmt:
return ast_for_while_stmt(c, ch);
case until_stmt:
return ast_for_until_stmt(c, ch);
接着下来就是实现ast_for_until_stmt函数的功能，它的代码如下：
static stmt_ty
ast_for_until_stmt(struct compiling *c, const node *n)
{
/* until_stmt: 'until' test ':' suite */
REQ(n, until_stmt);
if (NCH(n) == 4) {
expr_ty expression;
asdl_seq *suite_seq;
expression = ast_for_expr(c, CHILD(n, 1));
if (!expression)
return NULL;
suite_seq = ast_for_suite(c, CHILD(n, 3));
if (!suite_seq)
return NULL;
return Until(expression, suite_seq, LINENO(n), n->n_col_offset, c->c_arena);
}
PyErr_Format(PyExc_SystemError,
"wrong number of tokens for 'until' statement: %d",
NCH(n));
return NULL;
}
从这段代码看来，它与ast_for_while_stmt大体相同，但是until语句不支持else部分，所以就删除相应处理代码。由于AST代码处理是使用递归方式，可以使用其它相应的代码来处理，比如ast_for_expr来处理条件表达式，ast_for_suite来处理until语句的主体部分。在函数的最后把until语句生成的新节点返回。
注意到这里使用分析树的节点n时，需要使用宏处理函数NCH和CHILD。要查看这些宏的定义，可以到文件Include/node.h文件头里查看。
在这里我选择了创建新的AST节点来处理until语句，其实这样做是不必要的。并且这样可以节省一些工作，实现新的语法功能完全可以使用以前存在的AST节点代码来实现，如下这样：
until condition:
# do stuff
与上面代码相同功能代码，可写成这样：
while not condition:
# do stuff
因此，如果只想简单起见，在函数ast_for_until_stmt里直接使用Not while的AST节点的代码，就可以了，而不必要创建until语句的新的AST节点代码。从而连后面生成字节码部分也可省略掉，不过本文主要就是为了演示和教学作用，因此采用目前这种方式来做。
接着下来就是把AST转换为Python字节码。在编译过程中，Python会把AST转换为CFG（Control Flow Graph），由于这里为了显示出大体处理流程，故意把这些细节忽略掉，这样就不会有太多其它信息干扰着添加语法的流程。
下一步需要添加代码的文件是Python/compile.c，在这个文件里找到while语句处理地方，主要在函数compiler_visit_stmt来处理，这个函数作用就是编译语句为字节码。我在下面的语句下面添加了一个case语句：
case While_kind:
return compiler_while(c, s);
case Until_kind:
return compiler_until(c, s);
如果你看到Until_kind有点疑问，它到底是什么样得来的。其实它是一个常量（实际上是_stmt_kind枚举值），这个值是通过编译AST定义文件时自动生成的，保存在文件Include/Python-ast.h里。从上面也会发现函数compiler_until很陌生，没错，这个函数还没有告诉你是怎么样编写它，后面接着就来介绍这个函数。
如果你跟我一样有好奇心，也会发现函数compiler_visit_stmt在所有Python源文件里查找不到，感觉到它是一个很奇怪的函数。当遇到这种情况下，使用一个编译选项-C，就可以生成宏替换的临时文件出来，然后在这个临时文件里就可以找到相应的函数名称。实际上，经过一段时间查找之后，就会发现它是使用宏定义的机制来动态生成函数名称的，这个宏叫做VISIT名称，定义在源文件Python/compile.c里：
#define VISIT(C, TYPE, V) {\
if (!compiler_visit_ ## TYPE((C), (V))) \
return 0; \
这个宏就是用来在函数compiler_body里调用compiler_visit_stmt函数。明白这个宏之后，再回到添加AST转换为字节码的方面上，根据上面流程，compiler_until函数定义如下：
static int
compiler_until(struct compiler *c, stmt_ty s)
{
basicblock *loop, *end, *anchor = NULL;
int constant = expr_constant(c, s->v.Until.test);
if (constant == 1) {
return 1;
}
loop = compiler_new_block(c);
end = compiler_new_block(c);
if (constant == -1) {
anchor = compiler_new_block(c);
if (anchor == NULL)
return 0;
}
if (loop == NULL || end == NULL)
return 0;
ADDOP_JREL(c, SETUP_LOOP, end);
compiler_use_next_block(c, loop);
if (!compiler_push_fblock(c, LOOP, loop))
return 0;
if (constant == -1) {
VISIT(c, expr, s->v.Until.test);
ADDOP_JABS(c, POP_JUMP_IF_TRUE, anchor);
}
VISIT_SEQ(c, stmt, s->v.Until.body);
ADDOP_JABS(c, JUMP_ABSOLUTE, loop);
if (constant == -1) {
compiler_use_next_block(c, anchor);
ADDOP(c, POP_BLOCK);
}
compiler_pop_fblock(c, LOOP, loop);
compiler_use_next_block(c, end);
return 1;
}
在这里得说明一下：这些代码编写不是深度理解Python字节码的生成过程之下写出来的，可能存某方面优化的问题。就像本文其它地方一样，都是模仿while语句的情况下写出来，这里主要模仿了函数compiler_while。因此，理解这些代码需要比较小心一些，由于Python的虚拟机VM都基于栈的方式，查看dis模块的相关文档，对应着反汇编的指令码来看，可能会更加明了。
由于添加until语句，但没有添加到符号表，这时需要做这个工作了。当编译AST时，就会生成符号表。在符号表管理的源文件Python/symtable.c里，可以找到函数PySymtable_Build，而这个函数被PyAST_Compile调用来创建符号表。这个符号表记录了那些变量是全局的，那些变量是局部的作用域。
为了解决符号表的问题，需要修改源文件Python/symtable.c里的函数symtable_visit_stmt，添加相应的until语句处理代码，也跟while语句类似：
case While_kind:
VISIT(st, expr, s->v.While.test);
VISIT_SEQ(st, stmt, s->v.While.body);
if (s->v.While.orelse)
VISIT_SEQ(st, stmt, s->v.While.orelse);
break;
case Until_kind:
VISIT(st, expr, s->v.Until.test);
VISIT_SEQ(st, stmt, s->v.Until.body);
break;
到目前为止，所有相关的代码全部添加完成了。这样时再编译成功之后，就可以使用until语句了。
当我们编译整个Python代码之后，就会生成Python可执行文件。在Linux之下采用make的方式来编译，在 Windows之下采用VC的工程进行编译。然后打开Python.exe程序，运行之后在交互界面输入until语句测试：
>>> until num == 0:
... print(num)
... num -= 1
...
3
2
1
哗，居然可以运行了。下面让我们再来查看一下这段代码生成什么样的字节码，这需要使用dis模块的功能：
>>> import dis
>>> def myfoo(num):
... until num == 0:
... print(num)
... num -= 1
...
字节码的指令如下：
>>> dis.dis(myfoo)
2 0 SETUP_LOOP 36 (to 39)
>> 3 LOAD_FAST 0 (num)
6 LOAD_CONST 1 (0)
9 COMPARE_OP 2 (==)
12 POP_JUMP_IF_TRUE 38
3 15 LOAD_GLOBAL 0 (print)
18 LOAD_FAST 0 (num)
21 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
24 POP_TOP
4 25 LOAD_FAST 0 (num)
28 LOAD_CONST 2 (1)
31 INPLACE_SUBTRACT
32 STORE_FAST 0 (num)
35 JUMP_ABSOLUTE 3
>> 38 POP_BLOCK
>> 39 LOAD_CONST 0 (None)
42 RETURN_VALUE
>>>
在这段字节码指令里，最为关键的操作码地址是12的代码行：当条件为true时，就跳到这个循环后面，这个语意是符合until语句的。如果没有符合条件，就继续执行循环体，从操作码地址35跳回来继续判断。
在本文里主要演示了怎么样添加一个新语句到Python里。在Python编译器添加新语法尽管有比较多的地方要修改，但是增加功能是不困难的，因为这里都采用相似或存在的语句作为参考。
Python编译器是一类复杂的软件，并且我不是这方面的专家。但是我对Python的内部实现很感兴趣，特别它的前端实现方式。因此，通过这个练习之后，对比只是理论地学习编译器原理和代码要好很多。通过本文的学习可以打下一个稳固的基础，为下一步学习编译器内部实现提供非好的参考。
参考文档：
http://eli.thegreenplace.net/2010/06/30/python-internals-adding-a-new-statement-to-python
蔡军生 QQ:9073204 深圳