第6章自底向上优先分析法.ppt

《第6章自底向上优先分析法.ppt》由会员分享，可在线阅读，更多相关《第6章自底向上优先分析法.ppt（27页珍藏版）》请在三一办公上搜索。

1、第6章 自底向上优先分析法,自底向上优先分析概述 简单优先分析 算符优先分析,返回目录,自底向上分析方法,自底向上分析方法，也称移进-归约分析法。实现思想：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句型对应某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。,文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1）#abbcde

2、#移进,2）#a bbcde#移进,4）#aA bcde#移进,6）#aA cde#移进,7）#aAc de#移进,9）#aAcB e#移进,11）#S#接受,分析符号串abbcde是否为GS的句子？,对输入串abbcde#的移进-规约分析过程,算法应考虑的问题,算法是否能够终止？算法是否快速？算法是否能够处理所有的情况？在每一步中如何选择子串进行归约？,自下而上语法分析的策略：移进-规约分析。移进就是将一个终结符推进栈。归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈。移进-归约过程是自顶向下最右推导的逆过程（规范归约）。,简单优先分析法 对一个文法按一定原则求出该文法所有

3、符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实际上是一种规范归约。算符优先分析法 只规定算符（终结符）之间的优先关系。找到句柄就归约，不是规范归约。,优先分析法,简单优先分析法,按照文法符号（包括终结符和非终结符）的优先关系确定句柄。,文法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,移进,4）#b(a a)b#aa,归约Aa,5）#b(A a)b#A=a,移进,6）#b(Aa)b#a=),移进,7）#b(Aa)b#)b,归约B

4、Aa),8）#b(B b#Bb,归约A(B,9）#bA b#A=b,移进,10）#bAb#b#,归约SbAb,11）#S#接受,对输入串b(aa)#的简单优先分析过程,简单优先关系矩阵,优先关系,优先关系X=Y 文法G中存在产生式A.XY.XY 文法G中存在产生式A.BD.，且B.X,D Y.如何确定两个文法符号之间的优先关系？,返回调用,简单优先文法的定义,满足以下条件的文法是简单优先文法（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部。（3）不含空产生式。,简单优先分析法,根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存

5、，设置符号栈S，算法步骤如下：将输入符号串a1a2a3.an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1ak为止。由句柄ak.ai在文法的产生式中查找右部为ak.ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。,如何确定优先关系？,文法GS：(1)S bAb(2)A(B|a(3)B Aa),1.求=关系：由(1)：b=A A=b由(2)：(=B由(3)：A=a a=)2.求关

6、系：由(1)：Bb ab)b由(3)：Ba aa)a4.#,查看关系定义,算符优先分析法,某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性只考虑算符之间的优先关系来确定句柄,文法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#+*,移进,7）#E+E*i#*i,移进,8）#E+E*i#*#,规约,9）#E+E*E#+#,规约,1

7、0）#E+E#,规约,11）#E#接受,对输入串i+i*i的算符优先分析过程,算符优先关系表,如何确定算符优先关系？,i的优先级最高优先级次于i，右结合*和/优先级次之，左结合+和-优先级最低，左结合括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号#的优先性低于与其相邻的算符,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,算符优先关系表,算符文法的定义,定义 如果不含空产生式的上下文无关文法 G 中没有形如 UVW的产生式，其中V,WVN则称G 为算符文法（OG）。性质1：在算符文法中任何句型都不包含两个相邻的非终结符.(数学归纳法)性质2：如

8、 Vx 或 xV 出现在算符文法的句型 中，其中VVN,xVT,则 中任何含 x 的短语必含有V.（反证法）,算符优先关系的定义,在OG中 定义（算符优先关系）x=y G中有形如.Uxy或U xVy.的产生式。x y G中有形如.U Wy的产生式,而 W x或W xV规定 若 S x或S Vx 则#,算符优先文法的定义,在 OG文法 G 中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。注意：允许bc,cb;不允许bc,bc,b=c 结论：算符优先文法是无二义的。,算符优先关系表的构造,由定义直接构造由关系图法构造算符优先关系表,首先引入两个概念FIRSTVT

9、(B)=b|B b或B Cb.对于非终结符B，其往下推导所可能出现的首个算符。LASTVT(B)=a|B a或B.aC对于非终结符B，其往下推导所可能出现的最后一个算符。,如何计算算符优先关系,1)=关系直接看产生式的右部，若出现了A ab或A aBb,则a=b。2)关系求出每个非终结符B的LASTVT(B)，若ABb,则aLASTVT(B),则ab。,文法GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FPF|P(6)P(E)(7)Pi,FIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRS

10、TVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i,1)=关系由产生式(0)和(6),得#=#，（=）2）关系找形如：AaB的产生式#E：则#FIRSTVT(E)+T:则+FIRSTVT(T)*F:则*FIRSTVT(F)F:则 FIRSTVT(F)(E:则(FIRSTVT(E),3)关系找形如：ABb的产生式E#,则 LASTVT(E)#E+,则 LASTVT(E)+T*,则 LASTVT(T)*P,则 LASTVT(P)E),则 LASTVT(E),算符优先分析算法,归约过程中，只

11、考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的，P110.为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念。,最左素短语,算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#,若Niai.NjajNj+1为句柄，则有 ai-1 ai+1对于算符优先文法，如果aNb(或ab)出现在句型r中若ab，则在r中必含有a而不含b的短语存在。若a=b，则在r中含有a的短语必含有b，反之亦然。定义 cfg G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最

12、左边的素短语为最左素短语。,文法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,E,E,T,+,+,E,T,F,*,F,T,T,i,最左素短语为：T*F,句型#N+N*N+i#的归约过程,N,N,+,+,N,N,i,*,N,N,N,优先函数,优先函数比优先矩阵节省空间当发生错误时不能准确指出出错位置如：i+ii*i#，两个相邻i不存在优先关系，但优先函数存在，会归约成N+NN.而发现错误。优先函数的构造由定义直接构造用关系图构造优先函数,算符优先分析法的局限性,一般语言的方法很难满足算符优先文法的条件。很难避免把错误的句子得到正确的归约。,