Python源码分析4 – Grammar文件和语法分析

Grammar文件

前面提到了在Python的源代码目录下面有一个Grammar目录，里面只有一个文件Grammar，以BNF的语法定义了Python的全部语法。拿if语句举例来说：

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

上面的语句可以这样理解，if语句是if关键字+逻辑表达式+ ‘:’+语句块(suite)后面跟上0至多个elif语句并以else语句结束。在最左边的if_stmt表示这一句话定义了if_stmt（非终结符），’:’右边则是if_stmt的具体对应的内容。

1. ‘’引号中的内容是实际的字符串，’if’就代表if这两个字符

2. 一般的标示符代表着非终结符，也就是某个等式的左边，if_stmt, test, suite都是非终结符，可以被扩展为等式右边的序列。

3. ()括号是原子操作符，被括号括起来的被作为单个表达式看待

4. *代表0或多个，比如在if_stmt中的(‘elif’ test ‘:’ suite)*代表一个if语句中可以有0或者多个elif子句

5. +代表1或者多个

但是，这个文件并不只是用来作为参考资料的。实际上，Python运行的时候也需要间接利用到Grammar文件的内容来进行语法分析。

PGEN

在Makefile.pre.in和Parser/grammar.mak中均有类似如下的代码：

##########################################################################

# Grammar

GRAMMAR_H= $(srcdir)/Include/graminit.h

GRAMMAR_C= $(srcdir)/Python/graminit.c

GRAMMAR_INPUT= $(srcdir)/Grammar/Grammar

##########################################################################

# Parser

PGEN= Parser/pgen$(EXE)
POBJS= /

Parser/acceler.o /

Parser/grammar1.o /

Parser/listnode.o /

Parser/node.o /

Parser/parser.o /

Parser/parsetok.o /

Parser/bitset.o /

Parser/metagrammar.o /

Parser/firstsets.o /

Parser/grammar.o /

Parser/pgen.o

PARSER_OBJS= $(POBJS) Parser/myreadline.o Parser/tokenizer.o

PGOBJS= /

Objects/obmalloc.o /

Python/mysnprintf.o /

Parser/tokenizer_pgen.o /

Parser/printgrammar.o /

Parser/pgenmain.o

PGENOBJS= $(PGENMAIN) $(POBJS) $(PGOBJS)

############################################################################

# Special rules for object files

$(GRAMMAR_H) $(GRAMMAR_C): $(PGEN) $(GRAMMAR_INPUT)

-$(PGEN) $(GRAMMAR_INPUT) $(GRAMMAR_H) $(GRAMMAR_C)

$(PGEN): $(PGENOBJS)

$(CC) $(OPT) $(LDFLAGS) $(PGENOBJS) $(LIBS) -o $(PGEN)

这段代码负责生成pgen，然后调用pgen以Grammar作为输入，生成graminit.h/graminit.c。PGEN是Python自带的语法分析数据生成的工具，负责分析Grammar然后生成对应的graminit.c/graminit.h。然后，Python在运行过程中会依赖graminit.c/graminit.h中的数据结构来进行语法分析。PGEN的具体实现不在本文讨论范围中，从略。

Grammar.h

Graminit.c中定义了包括Python所有语法规则的DFA(Deterministic Finite Automaton)，关于DFA请参考Alfred V. Aho等人所著的Compilers: Principles, Techniques, and Tools一书。为了定义DFA，graminit.c引用了位于grammar.h中的一些类型：arc, state, dfa, grammar。

Label定义了从状态转移到另外一个状态所经过的边所对应的符号，可以是非终结符(Non-Terminal)，也可以是终结符(Terminal)。Label一定依附于一条或者多条边。Lb_type代表符号的类型，如终结符NAME，代表一个标示符，或者非终结符stmt，代表一个语句，等等。Lb_str代表具体符号的内容。比如，label (NAME, “if”)表示当parser处于某个状态，如果遇到了’if’这个标示符，则移动另外一个状态。如果label是一个非终结符的话，情况则要复杂一些，需要跳转到该非终结符对应的另外一个DFA，请参看编译器相关书籍。

/* A label of an arc */

typedef struct {

int lb_type;

char *lb_str;

} label;

arc代表DFA中一个状态到另一个状态的弧/边。A_lbl代表arc所对应的Label，而a_arrow记录了arc的目标状态。因为arc是属于某个状态的，因此不用纪录arc的起始状态。

/* An arc from one state to another */

typedef struct {

short a_lbl; /* Label of this arc */

short a_arrow; /* State where this arc goes to */

} arc;

State代表着DFA中的状态节点。每个state记录了从该state出发的边的集合，存放在s_arc中。其他的一些成员s_lower, s_upper, s_accel, s_accept记录了state所对应的Accelerator，其作用会在后面讲述。注意Accelerator信息并没有定义在graminit.c中，而是在运行时计算出来的。

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

DFA结构中记录了起始状态d_initial和所有状态的集合d_state。d_first记录了该DFA所对应的非终结符的firstset，也就是说，当遇到firstset中的终结符的时候，便需要跳转到此DFA中。d_first在后面计算Accelerators的时候会被用到。

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

Grammar代表了Python的整个语法，记录了所有的DFA和所有的label。G_start则是Python语法的起始symbol，一般是single_input。不过实际的起始symbol可以在创建Parser的时候指定，可以是single_input, file_input, eval_input中的一个。

/* A grammar */

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;

Graminit.c & Graminit.h

Graminit.c中定义了Python运行时刻进行语法分析所需要的静态数据（部分数据，主要是Accelerator，会在运行时计算出来），按照如下的顺序：

static arc arcs_0_0[3] = {

{2, 1},

{3, 1},

{4, 2},

};

static arc arcs_0_1[1] = {

{0, 1},

};

static arc arcs_0_2[1] = {

{2, 1},

};

static state states_0[3] = {

{3, arcs_0_0},

{1, arcs_0_1},

{1, arcs_0_2},

};

Arc_0_0代表DFA0中从状态0出发的所有arc，arcs_0_1代表DFA0中从状态1出发的所有arc，依此类推。Arcs_0_0中Arc { 2, 1 }代表一条边从状态0开始到状态1，Label为2（可以在后面查到label2代表NEWLINE，即换行符）。States_0记录了DFA0中所有的状态节点上面的所有边。

当定义完所有的DFA的状态和边的信息之后，接下来定义了所有的DFA的数组：

static dfa dfas[84] = {

{256, "single_input", 0, 3, states_0,

"/004/050/014/000/000/000/000/025/074/005/023/310/011/020/004/000/300/020/222/006/201"},

{257, "file_input", 0, 2, states_1,

"/204/050/014/000/000/000/000/025/074/005/023/310/011/020/004/000/300/020/222/006/201"},

...

拿第一个元素举例，256在graminit.h中可以查到代表single_input，也就是交互模式下单条语句。初始状态为0，共有3个状态，对应的状态和边的信息存在states_0中，最后的一个很长的字符串代表了该非终结符的firstset，每个字节对应着label的ID。

接下来，graminit.c定义了所有的Labels：

static label labels[168] = {

{0, "EMPTY"},

{256, 0},

{4, 0},

{267, 0},

...

{ 0, “EMPTY” }是一条特殊的边，表示该状态是accept状态，代表DFA的结束。{ 256, 0 } 则代表该label对应的是符号256，也就是single_input，无对应字符串描述。由于每个关键字在语法中是直接出现的，因此在Label中定义了每个关键字。

最后，定义了grammar：

grammar _PyParser_Grammar = {

84,

dfas,

{168, labels},

256

};

可以看到，整个Python2.5的语法共有84条规则/DFA，168个Label，起始Label为256, single_input。

Accelerators

Accelerator顾名思义，是用于加速语法分析处理速度的数据。假设不存在accelerator，我们必须枚举每一条边，判断应该走那一条边，而且一旦我们遇到某条边的label是非终结符，将很难迅速判定是否要跳转到该非终结符对应的DFA，而不得不扫描该DFA 的Firstset，一个一个的比较，这样速度显然很慢。Accelerators在每个state上面都定义了一个数组，对于每个Label都定义了转移的目标状态和DFA，因此只需做一个简单的索引操作就可以确定转移的目标状态和DFA，无需作顺序查找。
可以看到在graminit.c中并没有定义Accelerator的信息，其实Accelerator是在parser初始化的时候运算得来的，具体的实现在acceler.c中。Parser在初始化的时候会检查grammar中g_accel是否为0，如果为0，说明Accelerator并没有计算，并调用PyGrammar_AddAccelerators对Grammar进行处理，计算出Accelerator的信息。否则直接跳过不做处理。PyGrammar_AddAccelerators的实现如下：

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;

}

非常直接，依次调用fixdfa处理每个DFA然后设置g_accel为1表明Accelerator已经计算完毕。

Fixdfa也只是对于每个state进行处理：

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);

}

主要的实现在fixstate中。fixstate首先负责给accel分配一块内存，大小和Labels的个数相等，然后初始化为-1（每次都分配内存有些慢，其实静态数组就够了）

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;

接下来，fixstate对该状态的每一条边进行处理，分3种情况：

1. 如果该条边的Label是终结符（一般字符串），则直接设置accel[lbl] = a->arrow，即目标状态，这种情况下，不会进入到另外一个DFA

2. 如果该条边Label为非终结符（由ISNONTERMINAL判断，如果type > NT_OFFSET则说明是非终结符），则找到对应的DFA，对于firstset中的每个label ibit设置accel[ibit] = 目标DFA+该边的目标状态。具体编码方式如下：

DFA ID

1

目标状态，7bit

在第8位上的1是为了和终结符的情况作区分。

3. 如果该边label为EMPTY，则设置s_accept=1表明该状态为结束状态。

代码如下：

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)) { /*[Yi] >= NT_OFFSET? */

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) | /* [Yi] target_dfa, 1, final_state */

((type - NT_OFFSET) << 8);

}

}

}

else if (lbl == EMPTY)

s->s_accept = 1;

else if (lbl >= 0 && lbl < nl)

accel[lbl] = a->a_arrow;

}

最后，计算出accel数组中的最小边界和最大边界，放到s_lower和s_upper中。小于s_lower和大于s_upper的数组位置都是没有初始化过的，因此记录这些为初始化值没有任何意义，只用copy在s_lower & s_upper之间的内容即可。一旦要作索引操作的时候要减去s_lower。

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);

}

当Python生成了graminit.c/graminit.h，运行时计算出Accelerators之后，Python便可以依赖 PyParser进行语法分析了。下一篇将介绍PyParser的实现。

作者: ATField
E-Mail: [e-mail]
Blog: http://blog.csdn.net/atfield