Chinaunix首页 | 论坛 | 博客
  • 博客访问: 5327224
  • 博文数量: 671
  • 博客积分: 10010
  • 博客等级: 上将
  • 技术积分: 7310
  • 用 户 组: 普通用户
  • 注册时间: 2006-07-14 09:56
文章分类

全部博文(671)

文章存档

2011年(1)

2010年(2)

2009年(24)

2008年(271)

2007年(319)

2006年(54)

我的朋友

分类: C/C++

2008-09-11 12:33:22

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.inParser/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,然后调用pgenGrammar作为输入,生成graminit.h/graminit.cPGENPython自带的语法分析数据生成的工具,负责分析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一书。为了定义DFAgraminit.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_stated_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和所有的labelG_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出发的所有arcarcs_0_1代表DFA0中从状态1出发的所有arc,依此类推。Arcs_0_0Arc { 2, 1 }代表一条边从状态0开始到状态1Label2(可以在后面查到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"},

...

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

接下来,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条规则/DFA168Label,起始Label256, single_input

Accelerators

Accelerator顾名思义,是用于加速语法分析处理速度的数据。假设不存在accelerator,我们必须枚举每一条边,判断应该走那一条边,而且一旦我们遇到某条边的label是非终结符,将很难迅速判定是否要跳转到该非终结符对应的DFA,而不得不扫描该DFA Firstset,一个一个的比较,这样速度显然很慢。Accelerators在每个state上面都定义了一个数组,对于每个Label都定义了转移的目标状态和DFA,因此只需做一个简单的索引操作就可以确定转移的目标状态和DFA,无需作顺序查找。
可以看到在graminit.c中并没有定义Accelerator的信息,其实Accelerator是在parser初始化的时候运算得来的,具体的实现在acceler.c中。Parser在初始化的时候会检查grammarg_accel是否为0,如果为0,说明Accelerator并没有计算,并调用PyGrammar_AddAcceleratorsGrammar进行处理,计算出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_accel1表明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.     如果该边labelEMPTY,则设置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_lowers_upper中。小于s_lower和大于s_upper的数组位置都是没有初始化过的,因此记录这些为初始化值没有任何意义,只用copys_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:  
Blog:     
http://blog.csdn.net/atfield

发表于 @ 2006年12月24日 00:05:00|评论(2 )|编辑

新一篇: .NET / Rotor 源码研究1 - Building Rotor | 旧一篇: Python源码分析3 – 词法分析器PyTokenizer

评论

#my17521 发表于2007-01-05 14:40:26  IP: 222.209.219.*
太精彩了 顶一下 至今未知在CSDN看到的最后价值和最强的BLOG原创文章
老大一定是高手啊 python分析完了 能分析下 php脚本么 我对脚本非常感兴趣
python和php都是非常不错的脚本 效率也都很高 能了解下原理 帮助很大啊
#ATField 发表于2007-01-06 20:35:02  IP: 124.78.251.*
呵呵,过奖了。目前我初步的计划是分析Python 2.5和Rotor 2.0的实现,因为平时不做Web开发所以暂时没有分析PHP的计划。不过PHP也是非常优秀的脚本语言,其架构一定有其借鉴价值,有机会我一定会把PHP下下来看看,谢谢你的建议。
阅读(956) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~