编译原理演示文稿第五章.ppt

1、第五章 自底向上优先分析法,自底向上语法分析概述 简单优先分析 算符优先分析,自下而上语法分析概述,向下而上分析：该类分析方法是从输入符号串开始，查找句柄，并使用规则把它归约成相应的非终结符号。任何自底向上分析的关键，就是要找出这种句柄 。 自下而上语法分析试图将一个字符串反向归约至开始符号。 自下而上语法分析比自上而下语法分析更有效率，对语法的限制更少。,自下而上语法分析概述,自下而上语法分析的策略：移进-归约分析； 移进就是将一个终结符推进栈 归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈 移进-归约过程是自顶向下最右推导的逆过程（规范归约）,自下而上分析一般过程,例：

2、文法G：S cAd A a A ab识别输入串w=cabd是否该文法的句子,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,分析符号串abbcde是否GS的句子,对输入串abbcde#的移进-规约分析过程,上述每一步都是归约当前句型的句柄。且句柄出现在符号栈栈顶，不会在栈中间，上述分析过程并未真正解决句

3、柄的识别问题。例如，对于上面的例子，分析进行到第（5）步，当时栈内符号串为aAb。根据该符号串，我们有规则AAb和规则Ab。那么，符号串Ab和b都是某条规则的右部，故都有可能被判别是句型的句柄。假如我们选择b作为句柄，并把b归约为A，那么，最终就达不到归约到S的目的。因而，我们也就无从得知输入串abbcde是一个句子了。,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc

4、de# 移进,9） #aAcB e# 移进,11） #S # 接受,分析符号串abbcde是否GS的句子,对输入串abbcde#的移进-规约分析过程,算法应考虑的问题,在自底向上分析中，如何寻找确定一个句型的句柄是构造一个自左向右扫描，自底向上分析方法必须要解决的一个问题。 在每一步中如何选择子串进行归约？,短语、直接短语、句柄的定义： 文法GS， S A且A 则称是句型相对于非终结符A的短语。 若有A 则称是句型相对于该规则A 的直接短语。 一个句型的最左直接短语称为该句型的句柄。,短语、直接短语、句柄,简单优先分析法是按照文法符号（终结符和非终结符）的优先关系确定句柄的，因此我们首先介绍任

5、意两个文法符号之间的优先关系是怎样确定的，及如何构造优先关系表。,简单优先分析法,按照文法符号（包括终结符和非终结符）的优先 关系确定句柄。 首先定义优先关系的表示： XY 表示X和Y的优先关系相等。 XY 表示X的优先性比Y的优先性大。 XY 表示X的优先性比Y的优先性小。,这样我们就可以对已知文法对它的任意两个文法符号X,Y按其在句型中可能会出现的相邻关系来确定它们的优先关系。（注意、和数学中的= 、不同） i+i-i i-i+i,优先关系,优先关系 XY 文法G中存在产生式AXY XY 文法G中存在产生式AXB， 且B Y XY 文法G中存在产生式ABD， 且B X,D Y 如何确定两个

6、文法符号之间的优先关系？,文法GS： SbAb A(B|a BAa） 根据上面、关系的定义，由文法的产生式可求得文法符号之间的优先关系如下： （1）求关系：由SbAb,A(B,BAa) 可得： bA,Ab,( B,Aa,a),优先关系,（2）求关系： 由SbAb,且A (B，A a) 可得： b(，ba 由A（B且B （B，B a；B A， 可得：（,（a ,（A,SbAb A(B|a BAa）,（3）求关系： 由SbAb且A ),A B,A a 可得：)b,ab,Bb 由BAa）且A ），A a，A B 可得：)a,aa,Ba,SbAb A(B|a BAa）,为了表示简洁明了我们也可以把文法

7、符号之间的关系用矩阵表示，称作优先关系矩阵 。,优先关系矩阵,矩阵中元素要么只有一种关系，要么为空，元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系，在分析过程中若遇到这种相邻关系出现，则为出错，也就可以肯定输入符号串不是该文法的句子。 #号用来表示语句括号，#号的优先级所有符号，所有符号的优先级 #号，当然这里仅对与#号有相邻关系的文法符号而言 。,优先关系矩阵,优先关系矩阵,文法GS：(1) S bAb(2) A (B|a(3) B Aa),步骤,符号栈,输入符号串,动作,1） # b(aa)b# #b,移进,2） #b (aa)b# b(,移进,3） #b( aa)b# (a,

8、移进,4） #b(a a)b# aa,归约Aa,5） #b(A a)b# A=a,移进,6） #b(Aa )b# a=),移进,7） #b(Aa) b# )b,归约BAa),8） #b(B b# Bb,归约A(B,9） #bA b# A=b,移进,10） #bAb # b#,归约SbAb,11） #S # 接受,对输入串b(aa)b#的简单优先分析过程,简单优先关系矩阵,算符优先分析法就是仿照算术式的四则运算过程而设计的一种语法分析方法。实际上，该方法在一开始就是为了分析和翻译程序语言中的表达式而设计的。这种方法首先是要规定运算符之间（更一般说是终结符号之间）的优先关系和结合性质，然后就利用这

9、种关系，用比较相邻运算符的优先顺序来确定句型的“句柄”和进行归约 。,算符优先分析法,有文法：GE： E=E+E|E-E|E*E|E/E|（E）|i 这是一个二义性的文法，它的句子往往有不同的规范推导，因而就有不同的规范归约（句型的句柄未必是唯一的）。 例如： i+i-i*(i+i)， 就有两种不同的规范推导和规范归约。所以，归约过程中句型的句柄不唯一。,GE：E=E+E|E-E|E*E|E/E|（E）|i i+i-i *（i+i） 我们按正常的四则运算法则，即规定乘除运算符的优先级高于加减运算符；同级运算符是左边的运算符的优先级高于右边的；有括号时，先括号内后括号外；另外，因i是一个基本的运

10、算对象（属终结符号），因此，我们要先算一算它，然后进行别的运算，故规定i的优先级高于其他运算符 。,GE：E=E+E|E-E|E*E|E/E|（E）|i （1）i+i-i *（i+i） （2）E+i-i *（i+i） （3）E+E-i *（i+i） （4）E-i *（i+i） （5）E-E *（i+i） （6）E-E *（E+i） （7）E-E *（E+E） （8）E-E *（E） （9）E-E *E （10）E-E （11）E,在上述的整个归约过程中，起决定作用的是相邻两个终结符的优先关系，所以应用算符优先分析法自底向上地分析句子，解决了两个问题，即： （1）可以只根据相邻运算符的优先关系，

11、就能方便地并且唯一地确定归约的“句柄”； （2）可以用来分析二义性文法所产生的语言。,上述文法虽是二义性的（存在不同的规范归），但用算符优先法分析其句子时，其归约过程是唯一的。我们所规定的运算符之间的优先顺序和左结合的原则，就是避免二义性的充分条件。,直观算符优先分析法,通常在算术表达式求值过程中，运算次序是先乘除后加减，这说明了乘除运算的优先级高于加减运算的优先级，乘除为同一优先级但运算符在前边的先做，同样加减运算也是如此，这也说明了运算的次序只与运算符有关，而与运算对象无关，因而直观算符优先分析法的关键是对一个给定文法G，人为地规定其算符的优先顺序，即给出优先级别和同一级别中的结合性质。,

12、算符间的优先关系表示与前面介绍的优先关系的表示类似，其规定如下： ab 表示a的优先性低于b。 ab 表示a的优先性等于b，即与b相同。 ab 表示a的优先性高于b。,算符间的优先关系,但必须注意，这三个关系和数学中的是不同的，它们是有序的。也就是若有ab，不一定有ba，ab成立不一定有ba。例如：通常表达式中运算符的优先关系有+-，但没有-+成立，（）成立但没有）（成立。,如何确定算符优先关系,（1）i的优先级最高优先级次于i，右结合 （2）*和/优先级次之，左结合 （3）+和-优先级最低，左结合 （4）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号 （5

13、）#的优先性低于与其相邻的算符,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,直观算符优先关系表,很显然所给表达式文法显然是二义性文法，但我们认为直观地给出运算符之间的优先关系且这种优先关系是唯一的。,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,直观算符优先关系表,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,步骤,符号栈,输入符号串,动作,1） # i+i*i# #i,移进,2） #i +i*i# #+,规约,3） #E +i*i# #+,移进,4） #E+ i*i# +i,移进,5） #E+i *i# +*,规约,6） #E+E *i# +

14、*,移进,7） #E+E* i# *i,移进,8） #E+E*i # *#,规约,9） #E+E*E # +#,规约,10） #E+E # #,规约,11） #E # 接受,对输入串i+i*i的算符优先分析过程,算符优先关系表,直观算符优先分析法,算符文法,定义：如果不含空产生式的上下文无关文法 G 中没有形如 UVW的产生式，其中V,WVN，则称G 为算符文法（OG）。 性质1：在算符文法中任何句型都不包含两个相邻的非终结符。 性质2：如 Vx 或 xV 出现在算符文法的 句型 中，其中VVN,xVT, 则 中任何 含 x 的短语必含有V。,定义： 设G是一个算符文法，a和b是任意两个终结符

15、，A、B、C是非终结符，算符优先关系、定义如下：,算符文法的优先关系,（1）ab 当且仅当G中含有形如Aab或 AaBb的产生式。 （2）ab 当且仅当G中含有形如AaB的产 生式，且B b或B Cb （3）ab 当且仅当G中含有形如ABb的产 生式，且B a或B aC,ab 当且仅当G中含有形如Aab或 AaBb的产生式 ab 当且仅当G中含有形如AaB的产 生式，且B b或B Cb ab 当且仅当G中含有形如ABb的产 生式，且B a或B aC,算符文法的优先关系,算符优先文法,设有一不含产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有、和三种关系的一种成立，则称G一个算符优先

16、文法。（Operator Precedence Grammar）即OPG文法。 注意：允许bc,cb;不允许bc,bc,bc,EE+E|E*E|(E)|i不是算符优先文法。 因为对算符+、*来说，由EE+E和E E*E 可有+*， 又可由EE*E和E E+E得+*， 这样+、*的优先关系不唯一，所以该表达式的文法仅是算符文法而不是算符优先文法。,算符优先关系表的构造,由定义直接构造,算符优先关系表的构造,首先引入两个概念 FIRSTVT(B)=b|B b或B Cb 对于非终结符B，其往下推导所可能出现的首个算符 LASTVT(B)=a|B a或B aC 对于非终结符B，其往下推导所可能出现的最

17、后一个算符,算符优先关系,1) 关系 直接看产生式的右部，若出现了A ab或A aBb,则a b 2) 关系 求出每个非终结符B的FIRSTVT(B) 若AaB,则bFIRSTVT(B),a b 3) 关系 求出每个非终结符B的LASTVT(B) 若ABb,则aLASTVT(B),a b,文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,1) 关系由产生式(0)和(6),得#，（）,文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,FI

18、RSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,i,2） 关系找形如：AaB的产生式#E：则# FIRSTVT(E)+T: 则+ FIRSTVT(T) *F: 则* FIRSTVT(F)F:则 FIRSTVT(F)(E: 则 ( FIRSTVT(E),FIRSTVT(B)=b|B b 或B Cb,文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,LASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=

19、*,),iLASTVT(F)=,),iLASTVT(P)=),i,3)关系找形如：ABb的产生式E# ,则 LASTVT(E) #E+ ,则 LASTVT(E) + T* ,则 LASTVT(T) * P ,则 LASTVT(P) E) ,则 LASTVT(E) ),LASTVT(B)=a|B a 或B aC,文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,算符优先分析算法,算符优先分析法仍然是一种自底向上的分析算法，但不是严格从左到右的。在每一步分析中，它将识别和归约那些所谓的最左素短语。归约过程中，只考虑终结

20、符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的。 为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念。,定义 ： 文法 G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。 处于句型最左边的素短语为最左素短语。,句型的素短语,文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,句型#T+T*F+i#其短语有：T+T*F+iT+T*FTT*Fi,最左素短语为：T*F,句型#N+N*N+i#的归约过程,算符文法的任一句型有

21、如下形式：#N1a1N2a2.NnanNn+1# 定理: 一个OPG句型的最左素短语是满足下列条件的最左子串Niai.NjajNj+1，ai-1 ai ai+1 . aj-1 aj aj+1 出现在aj右端或ai左端的非终结符号一定属于这个素短语。,算符优先分析算法,对于算符优先文法如果aNb(或ab)出现在句型r中 若a b，则在r中必含有b而不含a的短语存在 若a b，则在r中必含有a而不含b的短语存在 若a b，则在r中含有a的短语必含有b反之亦然 由语法树和最左素短语的定义可以明显看出，下面归约过程，每次所归约的当前句型的最左子串也就是句型的最左素短语 。,文法GE：(1) EE+T(

22、2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,句型#T+T*F+i#,最左素短语为：T*F,在上述分析中，虽然指出了每个素短语所应归约的非终结符号。但是请注意，在查找所应归约的最左素短语的过程中，我们没有用到非终结符号。算符优先文法在归约过程中只考虑终结符之间的优先关系确定句柄，而与非终结符无关。,算符优先分析算法,分析时，只需知道把当前“句柄”归约为某一非终结符，不必知道该非终结符的名字是什么。因此，在符号栈中放不放相应的非终结符号，对分析过程中寻找最左素短语是毫无影响的。故我们可以取任意的名字来代替它们设立一个栈（运算对象栈）来存放它们。 现在，就可以来分析OPG文法的句子了。该算法所遵循的原则是：每次归约均是归约当前句型的最左素短语。,算符优先文法的句子分析过程i*(i+i) 用算符优先分析法进行分析,优先函数,在实际上，实现算符优先分析法时，一般不用文法的优先关系矩阵，而是用两个优先函数f和g。 对算符之间的优先关系，用优先矩阵表示，这样需占用大量的内存空间，当文法有n个非终结符时，就需要有(n+1)2个内存单元（终结符和#号）。因而，在实际应用中往往用优先函数来代替优先矩阵表示优先关系。,它对具有n个终结符的文法，只需2(n+1)个单元