《编译原理第六章-自底向上优先分析法》由会员分享，可在线阅读，更多相关《编译原理第六章-自底向上优先分析法（73页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 自底向上优先分析法自底向上优先分析法1v自底向上优先分析法慨述自底向上优先分析法慨述v简单优先分析简单优先分析v算符优先分析算符优先分析26.1 自底向上语法分析概述自底向上语法分析概述v如名字如示，自底向上语法分析试图将一个字符串反向归约至开始符号。v自底向上语法分析比自上而下语法分析更有效率，对语法的限制更少3v自底向上语法分析的策略：移进语法分析的策略：移进- -规约分析；规约分析；v移进移进就是将一个终结符推进栈就是将一个终结符推进栈v归约归约就是将就是将0 0个或多个符号从栈中弹出，根据个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈产生式将一个非终结符压入栈v移
2、进移进- -归约过程是自顶向下最右推导的逆过程归约过程是自顶向下最右推导的逆过程（规范归约）（规范归约）4例设文法Gs为:(1)S aAcBe(2)A b(3)A Ab(4)B d对输入串abbcde进行分析，检查该符号串是否是Gs的句子。分析：容易看出对输入串abbcde的最右推导是： SaAcBeaAcdeaAbcdeabbcde由此我们可以构造它的逆过程即归约过程。5v自底向上分析的关键问题: 如何确定句柄。6v自底向上优先分析法慨述自底向上优先分析法慨述v简单优先分析简单优先分析v算符优先分析算符优先分析76.2 简单优先分析法简单优先分析法v按照文法符号（包括终结符和非终结符）的优先
3、关系确定句柄。86.2.1 优先关系优先关系v优先关系X=Y 文法G中存在产生式A.XY.XY 文法G中存在产生式A.BD.，且B .X,D Y.v如何确定两个文法符号之间的优先关系？(按定义求优先关系，P96)96.2.2 简单优先文法的定义简单优先文法的定义满足以下条件的文法是简单优先文法（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部106.2.3 简单优先分析法简单优先分析法v算法步骤如下：11文法文法GS：(1) S bAb(2) A (B|a(3) B Aa)步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # b(
4、aa)b# #b,移进移进 2） #b (aa)b# b(,移进移进 3） #b( aa)b# (a,归约归约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#,归约归约SbAb11） #S # 接受接受对输入串b(aa)#的简单优先分析过程简单优先关系矩阵12v自底向上优先分析法慨述自底向上优先分析法慨述v简单优先分析简单优先分析v算符优先分析算符优先分析136.3 6.3 算符优先分析法算符优
5、先分析法v某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性v只考虑算符之间的优先关系来确定句柄146.3.1 直观算符优先分析法直观算符优先分析法（1 1） 优先级最高，右结合优先级最高，右结合（2 2）* *和和/ /优先级次之，左结合优先级次之，左结合（3 3）+ +和和- -优先级最低，左结合优先级最低，左结合（4 4）括号）括号(,)(,)的优先级的优先级大于括号外的运算符，小于括大于括号外的运算符，小于括号内的运算符，内括号的优先号内的运算符，内括号的优先性大于外括号性大于外括号（5 5）# #的优先性低于与其相邻的的
6、优先性低于与其相邻的算符算符文法文法GE：EE+E|E-E|E*E|E/E|E E|(E)|i算符优先关系表15文法文法GE：EE+E|E-E|E*E|E/E|E E|(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+
7、E # #,规约规约11） #E # 接受接受对输入串i+i*i的算符优先分析过程算符优先关系表166.3.2 算符优先文法的定义算符优先文法的定义v定义 设有一文法G，如果G中没有形如A BC的产生式，其中B和C为非终结符，则称G为算符文法(Operator Grammar)也称0G文法.v性质1：在算符文法中任何句型都不包含两个相邻的非终结符.(数学归纳法)v性质2：如果从Ab或(bA)出现在算符文法的句型中，其中A ，b ，则中任何含b的短语必含有A。（反证法）17算符优先文法的定义（续）算符优先文法的定义（续）v设设G是一个不含是一个不含 产生式的算符文法产生式的算符文法v a = b
8、 G中有形如中有形如.Aab或或A aBb 的产生式。的产生式。 v a b G中有形如中有形如.A Bb的产生式的产生式,而而 B a或或B aCv（语法子树可以直观的说明算符的优先关系（语法子树可以直观的说明算符的优先关系P101P101）18算符优先文法的定义（续）算符优先文法的定义（续）v定义 设有一不含 产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有、和三种关系的一种成立，则称G是一个算符优先文法(Operator Precedence Grammar)即OPG文法。（P101）196.3.3 6.3.3 算符优先关系表的构造算符优先关系表的构造v由定义直接构造由定义直
9、接构造v由关系图法构造算符优先关系表由关系图法构造算符优先关系表20v首先引入两个概念首先引入两个概念FIRSTVT(B)=b|B b或或B Cb.v对于非终结符对于非终结符B，其往下推导所可能出现的首个算符，其往下推导所可能出现的首个算符LASTVT(B)=a|B a或或B . aCv对于非终结符对于非终结符B，其往下推导所可能出现的最后一个，其往下推导所可能出现的最后一个算符算符（1 1）由定义直接构造）由定义直接构造21三种优先关系的计算：三种优先关系的计算：1) =关系关系直接看产生式的右部，若出现了直接看产生式的右部，若出现了A ab或或A aBb,则则a=b2)关系关系求出每个非终
10、结符求出每个非终结符B的的FIRSTVT(B)若若AaB,则则 b FIRSTVT(B),a关系关系求出每个非终结符求出每个非终结符B的的LASTVT(B)若若ABb,则则 a LASTVT(B),ab22文法文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FP F|P(6) P(E)(7) PiFIRSTVT(E)=#FIRSTVT(E)=+,*, ,(,iFIRSTVT(T)=*, ,(,iFIRSTVT(F)= ,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*, ,),iLASTVT(T)=*, ,),iLAS
11、TVT(F)= ,),iLASTVT(P)=),i1)=关系关系由产生式由产生式(0)和和(6),得得#=#，（，（=）2）关系关系找形如：找形如：AaB的产生式的产生式#E：则：则#FIRSTVT(E)+T: 则则+FIRSTVT(T) *F: 则则*FIRSTVT(F) F:则则 FIRSTVT(F)(E: 则则 (关系关系找形如：找形如：ABb的产生式的产生式E# ,则则 LASTVT(E)#E+ ,则则 LASTVT(E)+ T* ,则则 LASTVT(T)* P ,则则 LASTVT(P) E) ,则则 LASTVT(E)23对以上的优先关系表我们也可以给出一下的算法，这个算法基于一
12、下两条规则： a)若有产生式Aa或A Ba，则 aFIRSTVT(A)，其中A、B为非终结符，a为终结符。 b)若aFIRSTVT(B)且有产生式A B则有aFIRSTVT(A)。 算法如下： 其主程序如下：24(P, i)(P, ()(F, )(T, *)(E, +)(E, #)25(F, i)(P, ()(F, )(T, *)(E, +)(E, #)26(T, i)(P, ()(F, )(T, *)(E, +)(E, #)27(E, i)(P, ()(F, )(T, *)(E, +)(E, #)28(P, ()(F, )(T, *)(E, +)(E, #)29(F, ()(F, )(T,
13、*)(E, +)(E, #)30(T, ()(F, )(T, *)(E, +)(E, #)31(E, ()(F, )(T, *)(E, +)(E, #)32(F, )(T, *)(E, +)(E, #)33(T, )(T, *)(E, +)(E, #)34(E, )(T, *)(E, +)(E, #)35(T, *)(E, +)(E, #)36(E, *)(E, +)(E, #)37(E, +)(E, #)38(E, #)3940+*i()#EETFP111111111111111FIRSTVT(E) = #FIRSTVT(E) = +, *, , i,(FIRSTVT(T) = *, , i
14、,(FIRSTVT(F) = , i,(FIRSTVT(P) = i,(41FIRSTVT(E)FIRSTVT(T)FIRSTVT(E)FIRSTVT(F)FIRSTVT(P)42FIRSTVT(E)FIRSTVT(T)FIRSTVT(E)FIRSTVT(F)FIRSTVT(P)43用下面算法构造文法的优先关系表。用下面算法构造文法的优先关系表。44（2 2）由关系图法构造算符优先关系表）由关系图法构造算符优先关系表v定义 设文法G(VN，VT，S，P)是一个上下文无关文法，在v上定义以下关系： A FIRST B 当且仅当存在形如AB的产生式 A LAST B 当且仅当存在形如AB的产生式
15、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的产生式序列。45va,b之间的 关系可写成：v构造 关系可写成：构造 关系的关系图：63v算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#,若N
16、iai.NjajNj+1为句柄，则有ai-1 ai+1v对于算符优先文法，如果aNb(或ab)出现在句型r中若ab，则在r中必含有a而不含b的短语存在若a=b，则在r中含有a的短语必含有b，反之亦然6.3.4 算符优先分析算法算符优先分析算法64v归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的，P110.65v句型#T+T*F+i#的归约过程NN+NNi* NNN66v为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念v定义 :设有文法G，其句型的素短语是一个短语，它至少包含一个终结符，
17、且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语67文法文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FP F|P(6) P(E)(7) Pi句型句型#T+T*F+i#其短语有：其短语有：T+T*F+iT+T*FTT*FiEET+ETF* FTTi最左素短语为：最左素短语为：T*F68优先函数v优先函数比优先矩阵节省空间 a)当a = b，则令f(a) = g(b) b)当 a b，则令f(a) g(b)v优先函数的构造由定义直接构造用关系图构造优先函数69（1）由定义直接构造 若已知文法G终结符之间的优先关系，可按如下步骤构造其优先函数f，g。 a
18、)对每个终结符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，则表明该算符优先文法不存在算符优先函数。vP11370（2）用关系图法构造优先函数 a)对所有终结符a(包括)用有下脚标的fa，ga为结点名，画出2n个结点。 b)若aiaj或aiaj则从fai到gaj画一条箭弧。 若ai aj或aiaj则从gaj到fai画一条箭弧。 c)给每个结点赋一个数此数等于从该结点出发所能到达的结点(包括该结点自身在内)的个数。赋给结点fai的数，就是函数f(ai)的值，赋给gaj的数，就是函数g(aj)的值。 d)对构造出的优先函数，按优先关系矩阵检查一遍是否满足优先关系的条件，若不满足时，则在关系图中有回路说明不存在优先函数。 P11471算符优先分析法的局限性v一般语言的方法很难满足算符优先文法的条件v很难避免把错误的句子得到正确的归约72作业v练习 p116v第1，2题73
