编译原理第六章-自底向上优先分析法.ppt
1,第六章 自底向上优先分析法,2,自底向上优先分析法慨述简单优先分析算符优先分析,3,6.1 自底向上语法分析概述,如名字如示，自底向上语法分析试图将一个字符串反向归约至开始符号。自底向上语法分析比自上而下语法分析更有效率，对语法的限制更少,4,自底向上语法分析的策略：移进-规约分析；移进就是将一个终结符推进栈归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈移进-归约过程是自顶向下最右推导的逆过程（规范归约）,5,例6.1设文法Gs为:(1)S aAcBe(2)A b(3)A Ab(4)B d对输入串abbcde进行分析，检查该符号串是否是Gs的句子。分析：容易看出对输入串abbcde的最右推导是：SaAcBeaAcdeaAbcdeabbcde由此我们可以构造它的逆过程即归约过程。,6,自底向上分析的关键问题:如何确定句柄。,7,自底向上优先分析法慨述简单优先分析算符优先分析,8,6.2 简单优先分析法,按照文法符号（包括终结符和非终结符）的优先关系确定句柄。,9,6.2.1 优先关系,优先关系X=Y 文法G中存在产生式A.XY.XY 文法G中存在产生式A.BD.，且B.X,D Y.如何确定两个文法符号之间的优先关系？(按定义求优先关系，P96),10,6.2.2 简单优先文法的定义,满足以下条件的文法是简单优先文法（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部,11,6.2.3 简单优先分析法,算法步骤如下：,12,文法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,归约BAa),8）#b(B b#Bb,归约A(B,9）#bA b#A=b,移进,10）#bAb#b#,归约SbAb,11）#S#接受,对输入串b(aa)#的简单优先分析过程,简单优先关系矩阵,13,自底向上优先分析法慨述简单优先分析算符优先分析,14,6.3 算符优先分析法,某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性只考虑算符之间的优先关系来确定句柄,15,6.3.1 直观算符优先分析法,（1）优先级最高，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号（5）#的优先性低于与其相邻的算符,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,算符优先关系表,16,文法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#+#,规约,10）#E+E#,规约,11）#E#接受,对输入串i+i*i的算符优先分析过程,算符优先关系表,17,6.3.2 算符优先文法的定义,定义 设有一文法G，如果G中没有形如A BC的产生式，其中B和C为非终结符，则称G为算符文法(Operator Grammar)也称0G文法.性质1：在算符文法中任何句型都不包含两个相邻的非终结符.(数学归纳法)性质2：如果从Ab或(bA)出现在算符文法的句型中，其中A，b，则中任何含b的短语必含有A。（反证法）,18,算符优先文法的定义（续）,设G是一个不含 产生式的算符文法 a=b G中有形如.Aab或A aBb 的产生式。a b G中有形如.A Bb的产生式,而 B a或B aC（语法子树可以直观的说明算符的优先关系P101）,19,算符优先文法的定义（续）,定义 设有一不含 产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有、和三种关系的一种成立，则称G是一个算符优先文法(Operator Precedence Grammar)即OPG文法。（P101）,20,6.3.3 算符优先关系表的构造,由定义直接构造由关系图法构造算符优先关系表,21,首先引入两个概念FIRSTVT(B)=b|B b或B Cb.对于非终结符B，其往下推导所可能出现的首个算符LASTVT(B)=a|B a或B.aC对于非终结符B，其往下推导所可能出现的最后一个算符,（1）由定义直接构造,22,三种优先关系的计算：1)=关系直接看产生式的右部，若出现了A ab或A aBb,则a=b2)关系求出每个非终结符B的LASTVT(B)若ABb,则aLASTVT(B),ab,23,文法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)=,(,iFIRSTVT(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),24,对以上的优先关系表我们也可以给出一下的算法，这个算法基于一下两条规则：a)若有产生式Aa或A Ba，则 aFIRSTVT(A)，其中A、B为非终结符，a为终结符。b)若aFIRSTVT(B)且有产生式A B则有aFIRSTVT(A)。算法如下：其主程序如下：,25,(P,i)(P,()(F,)(T,*)(E,+)(E,#),26,(F,i)(P,()(F,)(T,*)(E,+)(E,#),27,(T,i)(P,()(F,)(T,*)(E,+)(E,#),28,(E,i)(P,()(F,)(T,*)(E,+)(E,#),29,(P,()(F,)(T,*)(E,+)(E,#),30,(F,()(F,)(T,*)(E,+)(E,#),31,(T,()(F,)(T,*)(E,+)(E,#),32,(E,()(F,)(T,*)(E,+)(E,#),33,(F,)(T,*)(E,+)(E,#),34,(T,)(T,*)(E,+)(E,#),35,(E,)(T,*)(E,+)(E,#),36,(T,*)(E,+)(E,#),37,(E,*)(E,+)(E,#),38,(E,+)(E,#),39,(E,#),40,41,FIRSTVT(E)=#FIRSTVT(E)=+,*,i,(FIRSTVT(T)=*,i,(FIRSTVT(F)=,i,(FIRSTVT(P)=i,(,42,FIRSTVT(E),FIRSTVT(T),FIRSTVT(E),FIRSTVT(F),FIRSTVT(P),#,+,*,(,i,43,FIRSTVT(E),FIRSTVT(T),FIRSTVT(E),FIRSTVT(F),FIRSTVT(P),#,+,*,(,i,44,用下面算法构造文法的优先关系表。,45,（2）由关系图法构造算符优先关系表,定义 设文法G(VN，VT，S，P)是一个上下文无关文法，在v上定义以下关系：A FIRST B 当且仅当存在形如AB的产生式 A LAST B 当且仅当存在形如AB的产生式 B FIRSTTERM b 当且仅当存在形如Bb或BCb的产生式 B LASTTERM a 当且仅当存在形如Ba或 Bac的产生式 X FOLLOWEDBY Y当且仅当存在形如AXY的产生式 X，Y中必须是一个为终结符，另一个为非终结符。A FIRST*B 当且仅当AB或存在一个形如AX1，X1X2，Xn-1Xn,XnB产生式序列。A LAST*B 当且仅当BA或存在一个形如AX1，X1X2，Xn-1Xn，XnB的产生式序列。,46,a,b之间的 关系可写成：构造 关系的关系图：,47,FIRST关系有：E FIRST EE FIRST TT FIRST TT FIRST FF FIRST P,FIRSTTERM关系有：E FIRSTTERM+T FIRSTTERM*F FIRSTTERM P FIRSTTERM(P FIRSTTERM i,终结符在前非终结符在后的相邻关系有：#FOLLOWEDBY E(FOLLOWEDBY E+FOLLOWEDBY T*FOLLOWEDBY F FOLLOWEDBY F,48,终结符在前非终结符在后的相邻关系有：#FOLLOWEDBY E(FOLLOWEDBY E+FOLLOWEDBY T*FOLLOWEDBY F FOLLOWEDBY F,1、有终结符在前非终结符在后的相邻关系的，终结符结点-非终结符结点画一箭弧：,#,E,49,终结符在前非终结符在后的相邻关系有：#FOLLOWEDBY E(FOLLOWEDBY E+FOLLOWEDBY T*FOLLOWEDBY F FOLLOWEDBY F,1、有终结符在前非终结符在后的相邻关系的，终结符结点-非终结符结点画一箭弧：,#,E,(,50,终结符在前非终结符在后的相邻关系有：#FOLLOWEDBY E(FOLLOWEDBY E+FOLLOWEDBY T*FOLLOWEDBY F FOLLOWEDBY F,1、有终结符在前非终结符在后的相邻关系的，终结符结点-非终结符结点画一箭弧：,#,E,(,T,+,51,终结符在前非终结符在后的相邻关系有：#FOLLOWEDBY E(FOLLOWEDBY E+FOLLOWEDBY T*FOLLOWEDBY F FOLLOWEDBY F,1、有终结符在前非终结符在后的相邻关系的，终结符结点-非终结符结点画一箭弧：,#,E,(,T,+,F,*,52,终结符在前非终结符在后的相邻关系有：#FOLLOWEDBY E(FOLLOWEDBY E+FOLLOWEDBY T*FOLLOWEDBY F FOLLOWEDBY F,1、有终结符在前非终结符在后的相邻关系的，终结符结点-非终结符结点画一箭弧：,#,E,(,T,+,F,*,53,FIRSTTERM关系有：E FIRSTTERM+T FIRSTTERM*F FIRSTTERM P FIRSTTERM(P FIRSTTERM i,2、FIRSTTERM关系，非终结符结点-终结符接点画一箭弧：,#,E,(,T,+,F,*,+,54,FIRSTTERM关系有：E FIRSTTERM+T FIRSTTERM*F FIRSTTERM P FIRSTTERM(P FIRSTTERM i,2、FIRSTTERM关系，非终结符结点-终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,55,FIRSTTERM关系有：E FIRSTTERM+T FIRSTTERM*F FIRSTTERM P FIRSTTERM(P FIRSTTERM i,2、FIRSTTERM关系，非终结符结点-终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,56,FIRSTTERM关系有：E FIRSTTERM+T FIRSTTERM*F FIRSTTERM P FIRSTTERM(P FIRSTTERM i,2、FIRSTTERM关系，非终结符结点-终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,P,(,57,FIRSTTERM关系有：E FIRSTTERM+T FIRSTTERM*F FIRSTTERM P FIRSTTERM(P FIRSTTERM i,2、FIRSTTERM关系，非终结符结点-终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,P,(,i,58,FIRST关系有：E FIRST EE FIRST TT FIRST TT FIRST FF FIRST P,3、FIRST关系，左边非终结符结点-右边终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,P,(,i,59,FIRST关系有：E FIRST EE FIRST TT FIRST TT FIRST FF FIRST P,3、FIRST关系，左边非终结符结点-右边终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,P,(,i,60,FIRST关系有：E FIRST EE FIRST TT FIRST TT FIRST FF FIRST P,3、FIRST关系，左边非终结符结点-右边终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,P,(,i,61,FIRST关系有：E FIRST EE FIRST TT FIRST TT FIRST FF FIRST P,3、FIRST关系，左边非终结符结点-右边终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,P,(,i,62,FIRST关系有：E FIRST EE FIRST TT FIRST TT FIRST FF FIRST P,3、FIRST关系，左边非终结符结点-右边终结符接点画一箭弧：,#,E,(,T,+,F,*,+,*,P,(,i,63,a,b之间的 关系可写成：构造 关系的关系图：,64,算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#,若Niai.NjajNj+1为句柄，则有ai-1 ai+1对于算符优先文法，如果aNb(或ab)出现在句型r中若ab，则在r中必含有a而不含b的短语存在若a=b，则在r中含有a的短语必含有b，反之亦然,6.3.4 算符优先分析算法,65,归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的，P110.,66,句型#T+T*F+i#的归约过程,67,为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念定义:设有文法G，其句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语,68,文法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,69,优先函数,优先函数比优先矩阵节省空间 a)当a=b，则令f(a)=g(b)b)当 a b，则令f(a)g(b)优先函数的构造由定义直接构造用关系图构造优先函数,70,（1）由定义直接构造,若已知文法G终结符之间的优先关系，可按如下步骤构造其优先函数f，g。a)对每个终结符aVT(包括#号在内)令f(a)g(a)1，(也可是其它整数)。b)如果ab而f(a)g(b)则令f(a)g(b)+l c)如果ab而f(a)g(b)则令g(b)f(a)+1 d)如果a=b而f(a)g(b)则令Minf(a)，g(b)=maxf(a),g(b)e)重复b)d)直到过程收敛。如果重复过程中有一个值大于2n，则表明该算符优先文法不存在算符优先函数。P113,71,（2）用关系图法构造优先函数,a)对所有终结符a(包括)用有下脚标的fa，ga为结点名，画出2n个结点。b)若aiaj或aiaj则从fai到gaj画一条箭弧。若ai aj或aiaj则从gaj到fai画一条箭弧。c)给每个结点赋一个数此数等于从该结点出发所能到达的结点(包括该结点自身在内)的个数。赋给结点fai的数，就是函数f(ai)的值，赋给gaj的数，就是函数g(aj)的值。d)对构造出的优先函数，按优先关系矩阵检查一遍是否满足优先关系的条件，若不满足时，则在关系图中有回路说明不存在优先函数。P114,72,算符优先分析法的局限性,一般语言的方法很难满足算符优先文法的条件很难避免把错误的句子得到正确的归约,73,作业,6.4练习 p116第1，2题,
