前言
读了读编译原理，用一句简单的 Python 代码来理一遍 Python 的编译执行过程。
因为 Python 不像 PHP 那样使用了 re2c 和 Bison 那些工具进行编译，所以看起来要麻烦很多。
调试环境
源码下载地址：https://github.com/python/cpython/tree/2.7
编译安装跟 PHP 差不多，就不说了。
测试脚本：
print 1
研究语法分析的时候可以将 print 改成 prin 来观察分析过程，加上 -d 参数运行可以看到它的语法分析过程。
入口
Py_Main(main.c) -> PyRun_AnyFileExFlags(pythonrun.c) -> PyRun_SimpleFileExFlags(pythonrun.c) -> PyRun_FileExFlags(pythonrun.c)
PyRun_FileExFlags 中将编译执行分为两个部分来进行：
- 调用 PyParser_ASTFromFile 词法分析、语法分析生成 AST 树，解析 AST 树生成中间数据
- 调用 run_mod 解析数据生成 PyCodeObject(里面包括字节码等执行数据)，再执行字节码。
我们从 PyParser_ASTFromFile 往下看，经过 PyParser_ParseFileFlagsEx 会来到 parsetok 函数，这里就是语法分析的部分了。
词法分析
语法分析是一个死循环，不停地调用 PyTokenizer_Get 从源码中读取 token 进行语法分析，PyTokenizer_Get 函数 则会调用 tok_get 函数，这个函数里面的就是主要的词法分析逻辑，因为代码很长所以就不全贴了。
词法分析相关的数据(按行存放的源码、指向下一个要分析字符的指针等等)都存放在 tok 中，这是一个 tok_state 结构体：
/* Tokenizer state */
struct tok_state {
/* Input state; buf <= cur <= inp <= end */
/* NB an entire line is held in the buffer */
char *buf; /* Input buffer, or NULL; malloc'ed if fp != NULL */
char *cur; /* Next character in buffer */
char *inp; /* End of data in buffer */
char *end; /* End of input buffer if buf != NULL */
char *start; /* Start of current token if not NULL */
int done; /* E_OK normally, E_EOF at EOF, otherwise error code */
/* NB If done != E_OK, cur must be == inp!!! */
FILE *fp; /* Rest of input; NULL if tokenizing a string */
int tabsize; /* Tab spacing */
int indent; /* Current indentation index */
int indstack[MAXINDENT]; /* Stack of indents */
int atbol; /* Nonzero if at begin of new line */
int pendin; /* Pending indents (if > 0) or dedents (if < 0) */
char *prompt, *nextprompt; /* For interactive prompting */
int lineno; /* Current line number */
int level; /* () [] {} Parentheses nesting level */
/* Used to allow free continuations inside them */
/* Stuff for checking on different tab sizes */
const char *filename; /* For error messages */
int altwarning; /* Issue warning if alternate tabs don't match */
int alterror; /* Issue error if alternate tabs don't match */
int alttabsize; /* Alternate tab spacing */
int altindstack[MAXINDENT]; /* Stack of alternate indents */
/* Stuff for PEP 0263 */
int decoding_state; /* -1:decoding, 0:init, 1:raw */
int decoding_erred; /* whether erred in decoding */
int read_coding_spec; /* whether 'coding:...' has been read */
char *encoding;
int cont_line; /* whether we are in a continuation line. */
const char* line_start; /* pointer to start of current line */
#ifndef PGEN
PyObject *decoding_readline; /* codecs.open(...).readline */
PyObject *decoding_buffer;
#endif
const char* enc;
const char* str;
const char* input; /* Tokenizer's newline translated copy of the string. */
};
成员的用途在注释里都标注得很清楚了，源码在 tok 中是按行存放的，tok_get 函数每次调用 tok_nextc 从中取出一个字符进行分析。而在第一次进入 tok_get 函数的时候，tok 里面是没有源码的，在调用 tok_nextc 的时候会调用 decoding_fgets 读入一行源码。tok_nextc 函数除了读入源码和返回字符还有一些其他的操作，不过与本文主题不太相关所以不提。
在处理每行开头的时候会跳过空白字符，还有交互模式下缩进量的相关处理，略。
缩进量设计自定义函数、递归和类等结构，跟本文主题无关，暂时也不是深入研究。
之后就是很普通的了，扫描字符串然后返回 token，匹配方式比 PHP 难看一些，没有使用正则表达式来表示，而类型跟 PHP 的词法分析差不多，比较大的区别就是 Python 把关键词和变量名/函数名/类名等合一叫做 NAME，所以定义中的终结符 token 类型就少了很多，具体的定义可以看 token.h，里面有终结符 token 的定义，都是小于 256 的整型数。
语法分析
语法部分可以看 Grammar 文件，里面有比较好看的语法规则。
parsetok 函数在调用 PyTokenizer_Get 获取 token 之后，会传入 token 和 value 调用 PyParser_AddToken 开始语法分析，跟入这个函数之后就会发现，因为Python 的语法分析器是自己实现的，所以这里的逻辑显得比较难懂。
我们一点点往下看，首先是获取 token 在标签数组里面的数组下标，获取到下标之后有什么用之后再说：
ilabel = classify(ps, type, str);
if (ilabel < 0)
return E_SYNTAX;
classify 函数的具体实现如下：
static int
classify(parser_state *ps, int type, char *str)
{
grammar *g = ps->p_grammar;
register int n = g->g_ll.ll_nlabels;
if (type == NAME) {
register char *s = str;
register label *l = g->g_ll.ll_label;
register int i;
for (i = n; i > 0; i--, l++) {
if (l->lb_type != NAME || l->lb_str == NULL ||
l->lb_str[0] != s[0] ||
strcmp(l->lb_str, s) != 0)
continue;
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
if (ps->p_flags & CO_FUTURE_PRINT_FUNCTION &&
s[0] == 'p' && strcmp(s, "print") == 0) {
break; /* no longer a keyword */
}
#endif
D(printf("It's a keyword\n"));
return n - i;
}
}
{
register label *l = g->g_ll.ll_label;
register int i;
for (i = n; i > 0; i--, l++) {
if (l->lb_type == type && l->lb_str == NULL) {
D(printf("It's a token we know\n"));
return n - i;
}
}
}
D(printf("Illegal token\n"));
return -1;
}
可以看到，如果 token 为 NAME，则尝试将 value 作为一个关键词进行搜索。而搜索失败，或者 value 不为关键词的情况下，则按照 token 进行搜索。
搜索的数组是 g->g_ll.ll_nlabels，这是个什么东西？我们先看看 g 是个什么东西，在调用 PyParser_ParseFileFlagsEx 函数的时候：
node *n = PyParser_ParseFileFlagsEx(fp, filename, &_PyParser_Grammar, start, ps1, ps2, &err, &iflags);
而 _PyParser_Grammar 则在 graminit.c 里面定义：
grammar _PyParser_Grammar = {
85,
dfas,
{169, labels},
256
};
...
typedef struct {
int g_ndfas;
dfa *g_dfa; /* Array of DFAs */
labellist g_ll;
int g_start; /* Start symbol of the grammar */
int g_accel; /* Set if accelerators present */
} grammar;
...
typedef struct {
int ll_nlabels;
label *ll_label;
} labellist;
所以 g->g_ll.ll_nlabels 其实就是一个长度为 169 的 label 数组 labels，里面存放了所有的 token 和 关键词 NAME，大概是这样子的一个数组：
static label labels[169] = {
{0, "EMPTY"},
{256, 0},
{4, 0},
{268, 0},
{292, 0},
{257, 0},
{267, 0},
{0, 0},
{258, 0},
{327, 0},
{259, 0},
{50, 0},
{288, 0},
{7, 0},
{330, 0},
{8, 0},
{260, 0},
{261, 0},
{329, 0},
{262, 0},
{1, "def"},
{1, 0},
...
};
因为太多就不全放了，每个 label 里面前面是 token，后面则是 value。Python 的语法分析是个栈形/树形的过程，其中 0 这个下标表示其中一个 dfa 匹配结束，具体的分析匹配过程后面再说；而 {1, “def”} 代表的就是 def 这个关键词，而 {1, 0} 则代表其他不是关键词的 NAME。
仔细看这个数组会发现，除了 <256 的终结符="" token="" 外，还有一些="">256 的非终结符 token，这些非终结符我们后面再看。
我们回到 PyParser_AddToken，在获取了数组下标之后就进入一个死循环，先看这两句：
register dfa *d = ps->p_stack.s_top->s_dfa;
register state *s = &d->d_state[ps->p_stack.s_top->s_state];
ps->p_stack.s_top 很好理解，就是栈顶，栈的结构如下：
#define MAXSTACK 1500
typedef struct {
int s_state; /* State in current DFA */
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;
这两句就是从栈顶取出现在匹配状态和匹配中的 dfa，然后根据现在的状态获取 dfa 中的相应状态。dfa 中文名叫有限自动机，简单来说 1 个 dfa 就是语法分析中的一个匹配规则，dfa 的结构定义如下：
typedef struct {
int d_type; /* Non-terminal this represents */
char *d_name; /* For printing */
int d_initial; /* Initial state */
int d_nstates;
state *d_state; /* Array of states */
bitset d_first;
} dfa;
这些 dfa 也存放在 graminit.c 的一个数组里面：
static dfa dfas[85] = {
{256, "single_input", 0, 3, states_0,
"\004\050\060\000\000\000\000\124\360\024\114\220\023\040\010\000\200\041\044\015\002\001"},
{257, "file_input", 0, 2, states_1,
"\204\050\060\000\000\000\000\124\360\024\114\220\023\040\010\000\200\041\044\015\002\001"},
...
{267, "stmt", 0, 2, states_11,
"\000\050\060\000\000\000\000\124\360\024\114\220\023\040\010\000\200\041\044\015\002\001"},
{268, "simple_stmt", 0, 4, states_12,
"\000\040\040\000\000\000\000\124\360\024\114\000\000\040\010\000\200\041\044\015\000\001"},
{269, "small_stmt", 0, 2, states_13,
"\000\040\040\000\000\000\000\124\360\024\114\000\000\040\010\000\200\041\044\015\000\001"},
{270, "expr_stmt", 0, 6, states_14,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\040\010\000\200\041\044\015\000\000"},
{271, "augassign", 0, 2, states_15,
"\000\000\000\000\000\300\377\003\000\000\000\000\000\000\000\000\000\000\000\000\000\000"},
{272, "print_stmt", 0, 9, states_16,
"\000\000\000\000\000\000\000\004\000\000\000\000\000\000\000\000\000\000\000\000\000\000"},
...
{304, "test", 0, 6, states_48,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\040\010\000\200\041\044\015\000\000"},
{305, "or_test", 0, 2, states_49,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\010\000\200\041\044\015\000\000"},
{306, "and_test", 0, 2, states_50,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\010\000\200\041\044\015\000\000"},
{307, "not_test", 0, 3, states_51,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\010\000\200\041\044\015\000\000"},
{308, "comparison", 0, 2, states_52,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\200\041\044\015\000\000"},
{309, "comp_op", 0, 4, states_53,
"\000\000\000\000\000\000\000\000\000\000\040\000\000\000\310\077\000\000\000\000\000\000"},
{310, "expr", 0, 2, states_54,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\200\041\044\015\000\000"},
{311, "xor_expr", 0, 2, states_55,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\200\041\044\015\000\000"},
{312, "and_expr", 0, 2, states_56,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\200\041\044\015\000\000"},
{313, "shift_expr", 0, 2, states_57,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\200\041\044\015\000\000"},
{314, "arith_expr", 0, 2, states_58,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\200\041\044\015\000\000"},
{315, "term", 0, 2, states_59,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\200\041\044\015\000\000"},
{316, "factor", 0, 3, states_60,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\200\041\044\015\000\000"},
{317, "power", 0, 4, states_61,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\044\015\000\000"},
{318, "atom", 0, 11, states_62,
"\000\040\040\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\044\015\000\000"},
...
};
看过 Gammar 文件里面语法之后就会发现，这里的 dfa 其实就是非终结符 token，第一个数字就是他们的 token，第二个则是他们易读的书面形式。至于后面四个成员则涉及匹配中的状态转换，分别代表该 dfa 的初始状态、状态数量、状态定义/转换以及可接受的首个 token(这里接受与否使用八进制表示的，比如 print_stmt 的 \000\000\000\000\000\000\000\004，表示的就是数组下标 58，即可接受的首个 token 就是关键词 print)，详细的转换过程后面再说。
继续往下看：
if (s->s_lower <= ilabel && ilabel < s->s_upper) {
register int x = s->s_accel[ilabel - s->s_lower];
...
}
s 就是前面获取的状态，结构如下：
typedef struct {
short a_lbl; /* Label of this arc */
short a_arrow; /* State where this arc goes to */
} arc;
/* A state in a DFA */
typedef struct {
int s_narcs;
arc *s_arc; /* Array of arcs */
/* Optional accelerators */
int s_lower; /* Lowest label index */
int s_upper; /* Highest label index */
int *s_accel; /* Accelerator */
int s_accept; /* Nonzero for accepting state */
} state;
其中 s_lower 代表能接受的最小数组下标，s_upper 则是最大数组下标，s_accel 下标代表可接受的首个 token、值代表接受后转换成的状态，s_accept 代表能否结束这个 dfa 的匹配。这些数据同样初始化在 graminit.c 中，比如 file_input 这个 dfa 的状态集及其转换规则就是：
static arc arcs_1_0[3] = {
{2, 0},
{6, 0},
{7, 1},
};
static arc arcs_1_1[1] = {
{0, 1},
};
static state states_1[2] = {
{3, arcs_1_0},
{1, arcs_1_1},
};
每个状态中的两个数据分别代表转换规则数、转换规则集，而每条转换规则中的两个数据代表可以匹配的 labels 中的数组下标、匹配后要转换成的状态。而每个 dfa 的初试状态都是 0，也就是说接受 token 后会按照 arcs_1_0 中的规则进行状态转换，如果 token 下标为 2、6 则会转换为 0，7则会转换为 1。
这里就会发现，初始化定义里面是没有 s_lower 以及后面的数据的，而 dfa 和栈等分析所需的数据都来自 ps 这个 parser_state 结构体：
typedef struct {
stack p_stack; /* Stack of parser states */
grammar *p_grammar; /* Grammar to use */
node *p_tree; /* Top of parse tree */
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
unsigned long p_flags; /* see co_flags in Include/code.h */
#endif
} parser_state;
可以看到里面有栈、语法规则、AST 树等成员，我们回去看看它的初始化，回到 parsetok 函数中，这里有个 PyParser_New 函数调用：
parser_state *
PyParser_New(grammar *g, int start)
{
parser_state *ps;
if (!g->g_accel)
PyGrammar_AddAccelerators(g);
ps = (parser_state *)PyMem_MALLOC(sizeof(parser_state));
if (ps == NULL)
return NULL;
ps->p_grammar = g;
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
ps->p_flags = 0;
#endif
ps->p_tree = PyNode_New(start);
if (ps->p_tree == NULL) {
PyMem_FREE(ps);
return NULL;
}
s_reset(&ps->p_stack);
(void) s_push(&ps->p_stack, PyGrammar_FindDFA(g, start), ps->p_tree);
return ps;
}
...
static int
s_push(register stack *s, dfa *d, node *parent)
{
register stackentry *top;
if (s->s_top == s->s_base) {
fprintf(stderr, "s_push: parser stack overflow\n");1
return E_NOMEM;
}
top = --s->s_top;
top->s_dfa = d;
top->s_parent = parent;
top->s_state = 0;
return 0;
}
在命令行运行 python 文件的情况下，这里的 start 为 257，即代表 file_input 的 token，可以看到最后会将 file_input 的 dfa 压入栈中作为匹配的开始，并让 ps->p_tree 指向 AST 树的根。我们关注 PyGrammar_AddAccelerators 函数，状态转换中重要的 s_accel 等成员都是在这里生成的：
void
PyGrammar_AddAccelerators(grammar *g)
{
dfa *d;
int i;
d = g->g_dfa;
for (i = g->g_ndfas; --i >= 0; d++)
fixdfa(g, d);
g->g_accel = 1;
}
遍历所有的 dfa，然后对每个 dfa 调用 fixdfa，继续看：
static void
fixdfa(grammar *g, dfa *d)
{
state *s;
int j;
s = d->d_state;
for (j = 0; j < d->d_nstates; j++, s++)
fixstate(g, s);
}
再遍历 dfa 中的状态集，对每个状态调用 fixstate：
static void
fixstate(grammar *g, state *s)
{
arc *a;
int k;
int *accel;
int nl = g->g_ll.ll_nlabels;
s->s_accept = 0;
accel = (int *) PyObject_MALLOC(nl * sizeof(int));
if (accel == NULL) {
fprintf(stderr, "no mem to build parser accelerators\n");
exit(1);
}
for (k = 0; k < nl; k++)
accel[k] = -1;
a = s->s_arc;
for (k = s->s_narcs; --k >= 0; a++) {
int lbl = a->a_lbl;
label *l = &g->g_ll.ll_label[lbl];
int type = l->lb_type;
if (a->a_arrow >= (1 << 7)) {
printf("XXX too many states!\n");
continue;
}
if (ISNONTERMINAL(type)) {
dfa *d1 = PyGrammar_FindDFA(g, type);
int ibit;
if (type - NT_OFFSET >= (1 << 7)) {
printf("XXX too high nonterminal number!\n");
continue;
}
for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
if (testbit(d1->d_first, ibit)) {
if (accel[ibit] != -1)
printf("XXX ambiguity!\n");
accel[ibit] = a->a_arrow | (1 << 7) |
((type - NT_OFFSET) << 8);
}
}
}
else if (lbl == EMPTY)
s->s_accept = 1;
else if (lbl >= 0 && lbl < nl)
accel[lbl] = a->a_arrow;
}
while (nl > 0 && accel[nl-1] == -1)
nl--;
for (k = 0; k < nl && accel[k] == -1;)
k++;
if (k < nl) {
int i;
s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
if (s->s_accel == NULL) {
fprintf(stderr, "no mem to add parser accelerators\n");
exit(1);
}
s->s_lower = k;
s->s_upper = nl;
for (i = 0; k < nl; i++, k++)
s->s_accel[i] = accel[k];
}
PyObject_FREE(accel);
}
总结一下过程，首先生成一个跟 labels 数组相同长度的 int 数组，全部赋值为 -1，代表不接受这个数组下标代表的 token。
然后遍历该状态的转换规则计算可以接受的首个 token，根据该规则可以匹配的数组下标从 labels 中取出对应的 token，然后判断 token 的类型，如果是 0，代表这次转换可以结束这个 dfa 的匹配，然后将 s_accept 赋值为 1，代表这个状态可以转换到匹配结束的接受状态。如果是其他终结符，则将转换后的状态放入 accel 中。而如果是非终结符，则要取出该非终结符对应的 dfa，根据其八进制 biset 来确定能接受的首个 token：
(((d1->d_first)[((ibit) / (8*sizeof(char)))] & (1 << ((ibit) % (8*sizeof(char))))) != 0)
再将转换后的状态、代表非终结符的 1、代表非终结符 token 的数字 - 256 之后组合起来放入 accel：
accel[ibit] = a->a_arrow | (1 << 7) | ((type - NT_OFFSET) << 8);
后面就很简单了，从前遍历找到能接受的最小下标作为 s_lower，从后找到能接受的最大下标作为 s_upper，再将接受和转换的规则放入 s_accel 中。
这时候回过头来继续看 PyParser_AddToken 函数里面的状态转换就很好懂了，用测试脚本举例，语法分析过程如下：
Token NAME/'print' ... It's a keyword
DFA 'file_input', state 0: Push ...
DFA 'stmt', state 0: Push ...
DFA 'simple_stmt', state 0: Push ...
DFA 'small_stmt', state 0: Push ...
DFA 'print_stmt', state 0: Shift.
Token NUMBER/'1' ... It's a token we know
DFA 'print_stmt', state 1: Push ...
DFA 'test', state 0: Push ...
DFA 'or_test', state 0: Push ...
DFA 'and_test', state 0: Push ...
DFA 'not_test', state 0: Push ...
DFA 'comparison', state 0: Push ...
DFA 'expr', state 0: Push ...
DFA 'xor_expr', state 0: Push ...
DFA 'and_expr', state 0: Push ...
DFA 'shift_expr', state 0: Push ...
DFA 'arith_expr', state 0: Push ...
DFA 'term', state 0: Push ...
DFA 'factor', state 0: Push ...
DFA 'power', state 0: Push ...
DFA 'atom', state 0: Shift.
DFA 'atom', state 5: Direct pop.
Token NEWLINE/'' ... It's a token we know
DFA 'power', state 1: Pop ...
DFA 'factor', state 2: Pop ...
DFA 'term', state 1: Pop ...
DFA 'arith_expr', state 1: Pop ...
DFA 'shift_expr', state 1: Pop ...
DFA 'and_expr', state 1: Pop ...
DFA 'xor_expr', state 1: Pop ...
DFA 'expr', state 1: Pop ...
DFA 'comparison', state 1: Pop ...
DFA 'not_test', state 2: Pop ...
DFA 'and_test', state 1: Pop ...
DFA 'or_test', state 1: Pop ...
DFA 'test', state 1: Pop ...
DFA 'print_stmt', state 2: Pop ...
DFA 'small_stmt', state 1: Pop ...
DFA 'simple_stmt', state 1: Shift.
DFA 'simple_stmt', state 3: Direct pop.
DFA 'stmt', state 1: Direct pop.
Token NEWLINE/'' ... It's a token we know
DFA 'file_input', state 0: Shift.
Token ENDMARKER/'' ... It's a token we know
DFA 'file_input', state 0: Shift.
DFA 'file_input', state 1: Direct pop.
ACCEPT.
后面的两个 NEWLINE 和 ENDMARKER 是 python 添加上去的，源码里没有这几个标记。
首先，词法分析返回一个 NAME，语法分析首先调用 classify 进行确认，发现这是个关键词，然后从栈上取出 file_input 的 dfa，查询 file_input 是否接受这个关键词：
register int x = s->s_accel[ilabel - s->s_lower];
if (x != -1) {
...
}
然后判断接受这个关键词的下一个 dfa 是否属于非终结符：
if (x & (1<<7)) {
/* Push non-terminal */
int nt = (x >> 8) + NT_OFFSET;
int arrow = x & ((1<<7)-1);
dfa *d1 = PyGrammar_FindDFA(ps->p_grammar, nt);
if ((err = push(&ps->p_stack, nt, d1,
arrow, lineno, col_offset)) > 0) {
D(printf(" MemError: push\n"));
return err;
}
D(printf(" Push ...\n"));
continue;
}
如果属于非终结符则取出该非终结符的 token 和接受并转换后的状态，这里是 stmt 和 1，并将该非终结符的 dfa 作为下一次匹配的规则压入栈中。实际上 push 函数里面除了入栈，还对 AST 树进行了操作：
static int
push(register stack *s, int type, dfa *d, int newstate, int lineno, int col_offset)
{
int err;
register node *n;
n = s->s_top->s_parent;
assert(!s_empty(s));
err = PyNode_AddChild(n, type, (char *)NULL, lineno, col_offset);
if (err)
return err;
s->s_top->s_state = newstate;
return s_push(s, d, CHILD(n, NCH(n)-1));
}
此时 s->s_top->s_parent 就是 AST 树的根节点，调用 PyNode_AddChild 会将非终结符 stmt 挂到根节点的子节点上面，s_push 则会将栈顶元素的 s_parent 修改为这个 stmt 的节点，也就是说下一次 push 形成的子节点就会挂在 stmt 节点的子节点上面，这样就构成了一棵 AST 树。
就这样一遍遍重复将下一个 dfa 压入栈中，直到遇到非终结符 print_stmt，此时接受关键词的是值为 print 的终结符 NAME，所以会不会进入前面的判断，而是开始尝试出栈：
/* Shift the token */
if ((err = shift(&ps->p_stack, type, str, x, lineno, col_offset)) > 0) {
D(printf(" MemError: shift.\n"));
return err;
}
D(printf(" Shift.\n"));
/* Pop while we are in an accept-only state */
while (s = &d->d_state[ps->p_stack.s_top->s_state], s->s_accept && s->s_narcs == 1) {
D(printf(" DFA '%s', state %d: " "Direct pop.\n", d->d_name, ps->p_stack.s_top->s_state));
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
if (d->d_name[0] == 'i' && strcmp(d->d_name, "import_stmt") == 0)
future_hack(ps);
#endif
s_pop(&ps->p_stack);
if (s_empty(&ps->p_stack)) {
D(printf(" ACCEPT.\n"));
return E_DONE;
}
d = ps->p_stack.s_top->s_dfa;
}
return E_OK;
shift 的操作跟 push 相同，只是少了入栈。阅读 Grammar 中的语法，可以发现对于非终结符而言，可能会有跟现在的 atom 一样的情况，即接受完一个 token 之后不能再继续接受第二个 token 了，这个时候就需要直接将其出栈，否则会影响到下一个 token 的分析，而这种直接出栈的情况在代码中的实现就是将状态转换成一个只接受 0 这个下标的状态，即：
s->s_accept && s->s_narcs == 1
到这里，关键词 print 的分析就完成了，我们根据转换规则看下 print_stmt 的转换过程：
// print_stmt 的状态 0 转换集，下标 58 代表关键词 print
static arc arcs_16_0[1] = {
{58, 1}, // 终结符 print
};
static arc arcs_16_1[3] = {
{28, 2}, // 非终结符 test
{59, 3}, // 终结符 >>
{0, 1},
};
static arc arcs_16_2[2] = {
{29, 4}, // 终结符 ,
{0, 2},
};
static arc arcs_16_3[1] = {
{28, 5},
};
static arc arcs_16_4[2] = {
{28, 2},
{0, 4},
};
static arc arcs_16_5[2] = {
{29, 6},
{0, 5},
};
static arc arcs_16_6[1] = {
{28, 7},
};
static arc arcs_16_7[2] = {
{29, 8},
{0, 7},
};
static arc arcs_16_8[2] = {
{28, 7},
{0, 8},
};
初始状态 0，接受 print 转换为 1，此时可以接受非终结符 test 或者终结符 >>。接受 test 之后会转换成 2，可以接受终结符 , 并转换为 4，然后就是一个不断的循环 , test , test , test …。注意看会发现状态 2 的转换规则里面还有一条 {0, 2}，这其实是这个状态可以作为结束状态的意思，因为这个状态的 s_accept 会是 1，后面的判断里面会依此判断该 dfa 是否匹配完全了，而放在现在这个情景中的意思就是 print 后面可以只有一个 test，而不需要后面更多的 , 和 test。这部分也就是 Grammar 里面写的规则：
[ test (',' test)* [','] ]
接下来会读入一个 token NUMBER 进行分析，此时的栈顶 dfa 为 print_stmt，状态为 1，所以下一个接受的 dfa 为 test，同样一路入栈，最后到非终结符 atom，它接受终结符 NUMBER 并转换为状态 5：
static arc arcs_62_0[7] = {
{13, 1},
{146, 2},
{149, 3},
{152, 4},
{21, 5},
{154, 5},
{155, 6},
};
static arc arcs_62_5[1] = {
{0, 5},
};
而因为状态 5 的转换规则只有一个 0，所以会直接出栈，栈顶 dfa 变为 power，此时 power 的状态为 1。
接下来读入的 token 是 NEWLINE，而 power 状态 1 不接受这个 token，所以会直接来到最后的两部分处理：
if (s->s_accept) {
#ifdef PY_PARSER_REQUIRES_FUTURE_KEYWORD
if (d->d_name[0] == 'i' &&
strcmp(d->d_name, "import_stmt") == 0)
future_hack(ps);
#endif
/* Pop this dfa and try again */
s_pop(&ps->p_stack);
D(printf(" Pop ...\n"));
if (s_empty(&ps->p_stack)) {
D(printf(" Error: bottom of stack.\n"));
return E_SYNTAX;
}
continue;
}
/* Stuck, report syntax error */
D(printf(" Error.\n"));
if (expected_ret) {
if (s->s_lower == s->s_upper - 1) {
/* Only one possible expected token */
*expected_ret = ps->p_grammar->
g_ll.ll_label[s->s_lower].lb_type;
}
else
*expected_ret = -1;
}
return E_SYNTAX;
如果该状态的 s_accept 为 1，代表这个状态已经匹配完全，可以结束该 dfa 的匹配了，则可以将该 dfa 出栈并返回继续上一个 dfa 的匹配。如果 s_accept 为 0 而 dfa 又不接受这个 token，则代表语法错误了。
而 power 状态 1 的规则如下：
static arc arcs_61_1[3] = {
{144, 1},
{31, 2},
{0, 1},
};
所以可以出栈，继续 factor 的匹配，这样一路出栈入栈，最后一个 Direct pop 清空栈里面的 dfa 之后，语法分析就完成了。
解析 AST 树
AST 节点结构体：
typedef struct _node {
short n_type; // token
char *n_str; // 书面表达
int n_lineno;
int n_col_offset;
int n_nchildren;
struct _node *n_child;
} node;
调用 PyParser_ParseFileFlagsEx 构建完 AST 树之后，会调用 PyAST_FromNode 将其解析为 mod：
case file_input:
stmts = asdl_seq_new(num_stmts(n), arena);
if (!stmts)
return NULL;
for (i = 0; i < NCH(n) - 1; i++) {
ch = CHILD(n, i);
if (TYPE(ch) == NEWLINE)
continue;
REQ(ch, stmt);
num = num_stmts(ch);
if (num == 1) {
s = ast_for_stmt(&c, ch);
if (!s)
goto error;
asdl_seq_SET(stmts, k++, s);
}
else {
ch = CHILD(ch, 0);
REQ(ch, simple_stmt);
for (j = 0; j < num; j++) {
s = ast_for_stmt(&c, CHILD(ch, j * 2));
if (!s)
goto error;
asdl_seq_SET(stmts, k++, s);
}
}
}
return Module(stmts, arena);
ast_for_stmt 是个 switch：
if (TYPE(n) == stmt) {
assert(NCH(n) == 1);
n = CHILD(n, 0);
}
if (TYPE(n) == simple_stmt) {
assert(num_stmts(n) == 1);
n = CHILD(n, 0);
}
if (TYPE(n) == small_stmt) {
n = CHILD(n, 0);
/* small_stmt: expr_stmt | print_stmt | del_stmt | pass_stmt
| flow_stmt | import_stmt | global_stmt | exec_stmt
| assert_stmt
*/
switch (TYPE(n)) {
case expr_stmt:
return ast_for_expr_stmt(c, n);
case print_stmt:
return ast_for_print_stmt(c, n);
...
}
}
对各种语句调用专门的处理函数：
static stmt_ty
ast_for_print_stmt(struct compiling *c, const node *n)
{
/* print_stmt: 'print' ( [ test (',' test)* [','] ]
| '>>' test [ (',' test)+ [','] ] )
*/
expr_ty dest = NULL, expression;
asdl_seq *seq = NULL;
bool nl;
int i, j, values_count, start = 1;
REQ(n, print_stmt);
if (NCH(n) >= 2 && TYPE(CHILD(n, 1)) == RIGHTSHIFT) {
dest = ast_for_expr(c, CHILD(n, 2));
if (!dest)
return NULL;
start = 4;
}
values_count = (NCH(n) + 1 - start) / 2;
if (values_count) {
seq = asdl_seq_new(values_count, c->c_arena);
if (!seq)
return NULL;
for (i = start, j = 0; i < NCH(n); i += 2, ++j) {
expression = ast_for_expr(c, CHILD(n, i));
if (!expression)
return NULL;
asdl_seq_SET(seq, j, expression);
}
}
nl = (TYPE(CHILD(n, NCH(n) - 1)) == COMMA) ? false : true;
return Print(dest, seq, nl, LINENO(n), n->n_col_offset, c->c_arena);
}
简单来说就是对接受的每个 test 调用 ast_for_expr，将解析出的表达式放入 seq，表达式结构体太复杂就不放了，最后返回一个 stmt_ty：
stmt_ty
Print(expr_ty dest, asdl_seq * values, bool nl, int lineno, int col_offset,
PyArena *arena)
{
stmt_ty p;
p = (stmt_ty)PyArena_Malloc(arena, sizeof(*p));
if (!p)
return NULL;
p->kind = Print_kind;
p->v.Print.dest = dest;
p->v.Print.values = values;
p->v.Print.nl = nl;
p->lineno = lineno;
p->col_offset = col_offset;
return p;
}
再将这些 stmt 集合起来放入 mod_ty：
mod_ty
Module(asdl_seq * body, PyArena *arena)
{
mod_ty p;
p = (mod_ty)PyArena_Malloc(arena, sizeof(*p));
if (!p)
return NULL;
p->kind = Module_kind;
p->v.Module.body = body;
return p;
}
调用 run_mod 将 mod 编译为 PyCodeObject 并执行：
static PyObject *
run_mod(mod_ty mod, const char *filename, PyObject *globals, PyObject *locals,
PyCompilerFlags *flags, PyArena *arena)
{
PyCodeObject *co;
PyObject *v;
co = PyAST_Compile(mod, filename, flags, arena);
if (co == NULL)
return NULL;
v = PyEval_EvalCode(co, globals, locals);
Py_DECREF(co);
return v;
}
PyCodeObject 实际上是 python 字节码类，除了要执行的字节码还要很多其他信息，比如变量常量等：
/* Bytecode object */
typedef struct {
PyObject_HEAD
int co_argcount; /* #arguments, except *args */
int co_nlocals; /* #local variables */
int co_stacksize; /* #entries needed for evaluation stack */
int co_flags; /* CO_..., see below */
PyObject *co_code; /* instruction opcodes */
PyObject *co_consts; /* list (constants used) */
PyObject *co_names; /* list of strings (names used) */
PyObject *co_varnames; /* tuple of strings (local variable names) */
PyObject *co_freevars; /* tuple of strings (free variable names) */
PyObject *co_cellvars; /* tuple of strings (cell variable names) */
/* The rest doesn't count for hash/cmp */
PyObject *co_filename; /* string (where it was loaded from) */
PyObject *co_name; /* string (name, for reference) */
int co_firstlineno; /* first source line number */
PyObject *co_lnotab; /* string (encoding addr<->lineno mapping) See
Objects/lnotab_notes.txt for details. */
void *co_zombieframe; /* for optimization only (see frameobject.c) */
PyObject *co_weakreflist; /* to support weakrefs to code objects */
} PyCodeObject;
编译 mod 的过程在 compiler_body 函数中，之后会调用 VISIT，展开后则是 compiler_visit_stmt，然后 switch 找到 print 的变异函数 compiler_print：
compiler_print(struct compiler *c, stmt_ty s)
{
int i, n;
bool dest;
assert(s->kind == Print_kind);
n = asdl_seq_LEN(s->v.Print.values);
dest = false;
if (s->v.Print.dest) {
VISIT(c, expr, s->v.Print.dest);
dest = true;
}
for (i = 0; i < n; i++) {
expr_ty e = (expr_ty)asdl_seq_GET(s->v.Print.values, i);
if (dest) {
ADDOP(c, DUP_TOP);
VISIT(c, expr, e);
ADDOP(c, ROT_TWO);
ADDOP(c, PRINT_ITEM_TO);
}
else {
VISIT(c, expr, e);
ADDOP(c, PRINT_ITEM);
}
}
if (s->v.Print.nl) {
if (dest)
ADDOP(c, PRINT_NEWLINE_TO)
else
ADDOP(c, PRINT_NEWLINE)
}
else if (dest)
ADDOP(c, POP_TOP);
return 1;
}
可以看到这里构造了字节码指令，VISIT(c, expr, e) 访问的是要打印的数字 1，这里会添加一个指令 LOAD_CONST，之后就是 PRINT_ITEM 和 PRINT_NEWLINE 以及结束指令。我们可以通过 python 的 dis 模块进行查看：
>>> dis.dis(co)
1 0 LOAD_CONST 0 (1)
3 PRINT_ITEM
4 PRINT_NEWLINE
5 LOAD_CONST 1 (None)
8 RETURN_VALUE
后记
理了一遍 python 的编译分析，可以发现跟 PHP 大同小异。
Orz