编译原理:句型分析和有关文法实用的说明

句型分析:

自上而下的分析方法:

从开始符出发,试图推导给定的字符串,


自下而上的分析方法:

推导的逆过程,从符号串开始试图将其规约为开始符。


最左推导:

每次推导都施加在句型最左边的语法变量上

最右推导:

每次推导都施加在句型最右边的语法变量上

最右推导称为规范推导,右句型称为规范句型;

语法树:直接的描述一个句型或句子的语法结构,是一个有向树,满足如下条件:

1.每个结点都有标记x∈V,

2.根标记为S(开始符);

3.若x有后继,则x∈Vn;

4.A有k个后继,则依次为x1,x2....xk;

文法的二义性:

描述一个句子的文法不是唯一的

对一个句子的分析应该是唯一的

如果一个句子存在两颗语法书,则是该句子二义性的

如果一个文法包含二义性的句子,则该文法是二义性的,否则该文法是无二义性的。


短语和句柄:

短语定义:


设G[Z]是给定文法,  w=xuy∈V+,为该文法的句型,如果满足下面两个条件:


① Z  xUy;


② U  u;


 则称句型xuy 中的子串u是句型xuy的短语。


直接短语定义:


设G[Z]是给定文法,  w=xuy∈V+,为该文法的句型,如果满足下面两个条件:


① Z  xUy;


② U Þ u;


 则称句型xuy 中的子串u是句型xuy的简单短语(或直接短语)。


直观理解:短语是前面句型中的某个非终结符所能推出的符号串。


句柄定义:


任一句型的最左简单短语称为该句型的句柄。


 






用语法树求短语、简单短语和句柄的方法是:


1)每个句型都有一棵语法树;


2)每棵语法树的叶(从左到右)组成一句型;


3)每个子树 的叶(从左到右)组成一短语;


4)每个简单子树 的叶(从左到右)组成一简单短语;


5)最左简单子树 的叶(从左到右)组成一句柄。






版权声明:本文为Mr_Ming_原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。