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+该边的目标状态。具体编码方式如下:
在第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:
atfield_zhang@hotmail.com
Blog: http://blog.csdn.net/atfield
相关推荐
资源分类:Python库 所属语言:Python 资源全名:anovelmous-grammar-0.1.3.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
编译原理实现词法分析和语法分析C语言源代码,DFA实现词法分析,Grammar递归向下实现语法分析,语义分析;一步到位
python 高级语法,基础语法在我的资源页有,需要的可以去下载。
在HTML语法中,大致上可以分为: 网页架构:主要网页主架构的介绍 分隔标签:也就是所谓的水平线 排版标签:针对标签的属性,可做适当的版面编排 字体标签:教导您设定文字的字体。 文字标签:教导您设定文字的...
Generates mock philosophy based on a context-free grammar
编译原理LR(0)文法分析器 录入合法的LR(0)文法,将输出LR(0)分析表,并可以对输入的句子进行语法分析输出相应语法树。程序中部分算法还很不简洁,有待改进,欢迎朋友与我多多交流。 -compiler theory LR (0) grammar...
四六级英语考试基本的语法--名词、冠词、代词、形容词和副词等等。
基于 Python 的词法和LR(1)文法分析器 ## 总体说明 * 编程语言:Python 2.7.11 * 编程平台:Ubuntu16.04 * 编程环境:sublime * 完成的内容:实现了 3型文法的词法分析器和2 型文法的LR(1)语法分析器。 * 测试文法:一个...
词法分析与语法分析的原始文件扩展: ://www.quut.com/c/ANSI-C-grammar-l-1998.html和 实现了C语言除了struct和指针几乎所有的语法。 运行 环境要求:flex bison g ++ 11 python3 中间代码生成 Windows命令行输入:...
基于flexbison的语法分析C语言实现源码+项目说明.zip 本实验实现该语言的语法检查和分析。在检查语法错误的情形下,报告语法错误,通过语法检查后构建AST, 并输出该AST。 目录结构: ``` ├── README.md 本说明...
omp4j 语法该存储库由Java8和OMP语法组成。 .g4格式的语法位于src/目录中。 可以使用 ANTLR4 将它们编译为.java源代码: * NIX 系统:只需运行./update.sh 其他系统:请阅读。 基本上,必须下载antlr-4.4-complete....
Python入门,好的编译规范,能达到事半功倍的效果!
编译原理实现词法分析和语法分析C++语言源代码,DFA实现词法分析,Grammar递归向下实现语法分析,语义分析;一步到位
[剑桥高级英语语法书第二版].Cambridge.Advanced.Grammar.in.Use.[2nd.edition.2005].pdf part 2 of 3
u grammar语法PPT教案.pptx
该库使您可以通过Python脚本或命令行界面来检测语法错误和拼写错误。 本地和远程服务器 默认情况下, language_tool_python将下载LanguageTool服务器.jar并在后台运行该服务器以在本地检测语法错误。 但是,...
尽管语法没什么好学的,但看一下例句也好……里面有很多例句,概括得也不错。
u grammar语法PPT学习教案.pptx
托业语法本领书_Toeic.Power.Grammar
English Grammar in Use 3rd Edition (4 of 5)