第6章 自底向上优先分析法(精品)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章,自底向上优先分析,方法,教学要求：,掌握算符优先分析法的关系表的构造以及分析过程，了解简单优先分折法。,教学重点,：归约，算符优先表构造。,从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。,工作方式：“移进归约”方式。,自底向上分析法的基本思想,分析程序模型,1,）初态时栈内仅有栈底符“”，读头指针在最左单词符号上。,2,）语法分析程序执行的动作：,a,）,移进 读入一个单词并压入栈内，读头后移；,b,）,归约 检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；,c,）,识别成功 移进归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；,d,）,识别失败,语法分析程序,语法表,a+b#,输出带,#,例如：,有文法如下,（,1,）,S,aAcBe,（,2,）,A,b,（,3,）,A,Ab,（,4,）,B,d,问：语句,abbcde,是不是该文法的合法语句？,成功,11,接受,2,3,4,1,S,10,归约,aAcBe,9,移进,2,3,4,e,aAcB,8,归约,e,aAc,d,7,移进,de,aAc,6,移进,2,3,cde,aA,5,归约,cde,a,Ab,4,移进,2,bcde,aA,3,归约,bcde,a,b,2,移进,bbcde,a,1,移进,abbcde,0,动作,输出带,输入串,栈,步骤,移进归约的分析过程,GS:,（,1,）,S,aAcBe,（,2,）,A b,（,3,）,A,Ab,（,4,）,B d,遇到的问题：,（,1,）如何找出进行直接归约的简单短语？,（,2,）找出的简单短语应直接归约到哪一个非终结符？,关键：,确定,句柄,.,常用的,分析方法,:,优先分析和,LR,分析,6.1,自底向上优先分析法概述,分类,:,1,、,简单优先分析：,对一个文法按一定原则求出所有符号即终结符号和非终结符号之间的优先关系,按照这种关系确定归约过程中的句柄,.,特点,:,准确、规范，但分析效率底，使用价值不大,.,2,、,算符优先分析：,只规定算符（终结符号）之间的优先关系，不考虑非终结符号之间的优先关系，只要找到句柄就归约，不考虑归约到那个非终结符号。,特点：,不是规范归约，分析速度快，特别适合于表达式的分析,.,一、基本思想,1,、自下而上归约,2,、规定算符,(,更一般地说，指终结符,),的优先级及结合规则，以使得分析过程唯一,3,、比较相邻两个算符而决定动作,注：,1),关键是对所有,算符,定义某种优先关系,2),算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法,6.3,算符优先分析方法,i+i-i*(i+i),归约过程如下：,i+i-i*(i+i),设算量级别最高，最先归约,；,E+i-i*(i+i),E+E-i*(i+i),，,同级，先归约左边“”,E-i*(i+i),E-E*(i+i),，*,不同级，先归约右边“*”,E-E*(E+i),先,括号内，后括号外,E-E*(E+E),归约括号内,E-E*(E),归约括号对,E-E*E,先归约“*”,E-E,后归约“,-”,E,结束（接受,）,例：,E,E+E|E-E|E*E|E/E|(E)|i,一、算符文法的定义,1,、给定上下文无关文法,G,，若,G,中所有产生式右部都不包含两个相继的非终结符，则,G,为,算符文法,。,注：算符文法保证了两个运算符之间只有一个操作数。,2,、算符优先文法定义,设,G,是一个不包含空串产生式的算符文法，并设,a,b,V,T,;,P,Q,R V,N,定义关系,：,1)a b,当且仅当,G,中含有形如,P,ab,产生式，或者,P,aQb,产生式,；,若,G,中任何终结符序偶,（,a,b,）,至多满足上述关系之一,，,则称,G,为算符优先文法,。,2)a b,当且仅当,G,中含有形如,P,aR,的产生式,，,其中,R,b,或,R,Qb,;,=,+,=,+,3)a b,当且仅当,G,中有形如,P,Rb,产生式,，,其中,R a,，,或,R ,aQ,.,=,+,=,+,用,语法树来理解更直观,a,b,A,a b,a B ,b,A,P,B b,A,P,a,a b,a b,注意,E,E *E,E +E,E *E,E,E +E,+,*,表达式文法：,E,E+E|E*E|(,E)|i,是算符文法，但不是算符优先文法。,两个算符之间的优先关系是有序的，允许有,a b,b a,同时存在，而不允许有,a b,，,a b,a b,三种情况之两种同时存在。,+*,1,、,各非终结符,P,的首终结符集和尾终结符集,定义：,首终结符集,FIRSTVT(P)=,a|P,a,或,P,Qa,，,a,V,T,;P,Q V,N,尾终结符集,LASTVT(P)=,a|P,a,或,P ,aQ,，,a,V,T,;P,Q V,N,三,、算符优先文法及优先表的构造,注：有了这两个集合，就可通过检查每个产生式的每个候选式，确定满足关系 和 的所有终结符序偶。,=,+,=,+,=,+,=,+,2,、构造,首终结符集和尾终结符集,算法,1),构造集合,FIRSTVT(P),的算法,根据,FIRSTVT(P),的定义，按下面的规则来构造：,(1),若有产生式,P,a,或,P,Qa,，,则,a,FIRSTVT(P),(2),若,a,FIRSTVT(Q),，,且有产生式,P,Q,，,则,a,FIRSTVT(P),2),构造,LASTVT(P),的算法。,根据,LASTVT,的定义，按下面的规则来构造：,(1),若有产生式,P,a,或,P,aQ,，,则,a,LASTVT(P,),(2),若,a,LASTVT,(Q,),，,且有产生式,P,Q,，,则,a,LASTVT(P,),3),构造算符优先表的算法,FOR,每条产生式,P,X,1,X,2,X,n,DO,FOR(i=1,i=n-1,i+),if X,i,和,X,i+1,均为终结符,then,置,X,i,X,i+1,;,if i#E#,1.EE+T|T,2.T T*F|F,3.F PF|P,4.P(E)|i,5),优先关系表,+*,i ()#,+,*,i,(,),#,1,、,最左素短语,在算符优先分析中，可归约的短语不再称为句柄，而称为,最左素短语,。,素短语：,至少含有一个终结符，且除它自身外不再包含其他素短语的短语。,最左素短语：,最左边的素短语。,四、算符优先分析方法,例如：考虑非二义的表达式文法,G(E),：,E E+T|T T T*F|F,F(E)|i,句型,T+T*F+i#,的素短语是什么,？,E,E T,E +T F,T T *F,i,由定义可知，,素短语有：,T*F,i,最左素短语：,T*F,算符优先文法句型（括在两个,#,号之间）的一般形式：,#N,1,a,1,N,2,a,2,N,n,a,n,N,n+1,#,其中每个,a,j,都是终结符，,N,i,是可有可无的非终结符。,一个算符优先文法,G,的任何句型的最左素短语是满足如下条件的最左子串：,N,j,a,j,N,i,a,i,N,i+1,a,j-1,a,i+1,根据这个最左素短语的定义可以构造算符优先分析算法。,输入：一个输入符号串,w,和一张优先关系表。,输出：若,w,是一个句子，输出一棵分析树基架，否则输出一个错误信息。,方法：分别置放,#,到栈中和,w#,到输入缓冲器中，并执行如下所示的程序。,2,、算符优先分析算法,置,ip,使之指向,w#,的第一个符号,；,repeat if#,在栈顶上并且,ip,指向,#then returnelse begin,令,a,是栈中最靠顶上的终结符号,并且令,b,是,ip,所指向的符号,if ab then/*,归约,*,/repeat,从栈中弹出符号,until,栈顶终结符号与最近弹出的符号之间有,关系成立,else error()end,例：根据下面文法及其算符优先表，按通用算符优先分析的算法分析语句,if b then i else i#,。,Sif,E,b,then E else E EE+T|T,TT*F|F,Fi,E,b,b,解：,1,）,求各非终结符的首终结符集和尾终结符集。为了考虑语句的开始和结束符号,“”，,对文法拓广，加一个产生式,S,S,FIRSTVT(S)=if LASTVT(S)=else,+,*,i,FIRSTVT(E)=+,*,i LASTVT(E)=+,*,i,FIRSTVT(T)=*,i LASTVT(T)=*,i,FIRSTVT(F)=i LASTVT(F)=i,FIRSTVT(,E,b,)=b,LASTVT(,E,b,)=b,2),填写算符优先表,#,b,i,*,+,else,then,if,#,b,i,*,+,else,then,if,右,左,成功,归约,#,#N,10,对,i,归约,#,#if N then N else N,9,移进,#,#if N then N else i,8,移进,i#,#if N then N else,7,对,i,归约,else i#,#if N then N,6,移进,else i#,#if N then i,5,移进,i else i#,#if N then,4,then i else i#,#if N,3,0,动作,输入串,关系,下推栈,步骤,接受,#,if b then i else i#,移进,1,#if,b then i else i#,移进,2,#if b,then i else i#,对,b,归约,5,、算符优先分析的优缺点,优点：,1),算符优先文法适用范围比简单优先文法大得多，许多程序设计语言都可以用它来分析。算符优先分析优先表构造简单，甚至可以用手工构造。,2),算符优先分析比规范归约要快得多，因为它跳过了许多单非终结符的归约。,这既是优点，也是缺点。,缺点：,1),由于忽略了非终结符在归约中的作用，所以它可能会把本来不成为句子的输入串误认为是句子。,2),有些文法不满足算符优先文法，必须先改写，有些甚至无法改写。事实上，许多符号对之间不存在优先关系。同时，若终结符数目多，优先表可能会占有太多空间。,