编译原理 第 5 讲 自底向上优先分析法

第5讲自底向上优先分析法自底向上优先分析概述简单优先分析算符优先分析自底向上分析方法自底向上分析方法，也称移进-归约分析法。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为归约。实现思想：文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde算法应考虑的问题算法是否能够终止？算法是否快速？算法是否能够处理所有的情况？在每一步中如何选择子串进行归约？自下而上语法分析的策略：移进-规约分析；移进就是将一个终结符推进栈归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈移进-归约过程是自顶向下最右推导的逆过程（规范归约，即最左规约）简单优先分析法对一个文法按一定原则求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实际上是一种规范归约。算符优先分析法只规定算符（终结符）之间的优先关系。找到句柄就归约，并不考虑规约到哪个非终结符名，不是规范归约。优先分析法最左素短语简单优先分析法按照文法符号（包括终结符和非终结符）的优先关系确定句柄。优先关系•优先关系–X=Y文法G中存在产生式A→...XY...–XY文法G中存在产生式A→...XB...，且BY...–XY文法G中存在产生式A→...BD...，且B...X,DY...*返回调用如何确定两个文法符号之间的优先关系？简单优先文法的定义满足以下条件的文法是简单优先文法（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部（3）不含空产生式简单优先分析法根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S，算法步骤如下：1.将输入符号串a1a2a3...an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。2.栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1ak为止。3.由句柄ak...ai在文法的产生式中查找右部为ak...ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。4.重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。如何确定优先关系？文法G[S]：(1)S→bAb(2)A→(B|a(3)B→Aa)1.求=关系：由(1)：b=AA=b由(2)：(=B由(3)：A=aa=)查看关系定义SbA(Ba)#Sb=A==(=Ba=)#4.#所有相邻符号，所有相邻符号#3.求关系：由(1)：Bbab)b由(3)：Baaa)a2.求关系：由(1)(2)：b(ba由(2)(3)：(A(((a文法G[S]：(1)S→bAb(2)A→(B|a(3)B→Aa)SbA(Ba)#Sb=A==(=Ba=)#步骤符号栈输入符号串动作1）#b(aa)b##b,移进2）#b(aa)b#b(,移进3）#b(aa)b#(a,移进4）#b(aa)b#aa,归约A→a5）#b(Aa)b#A=a,移进6）#b(Aa)b#a=),移进7）#b(Aa)b#)b,归约B→Aa)8）#b(Bb#Bb,归约A→(B9）#bAb#A=b,移进10）#bAb#b#,归约S→bAb11）#S#接受对输入串b(aa)b#的简单优先分析过程简单优先关系矩阵算符优先分析法某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性只考虑算符之间的优先关系来确定句柄文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i步骤符号栈输入符号串动作1）#i+i*i##i,移进2）#i+i*i##i+,规约3）#E+i*i##+,移进4）#E+i*i#+i,移进5）#E+i*i#+i*,规约6）#E+E*i#+*,移进7）#E+E*i#*i,移进8）#E+E*i#*i#,规约9）#E+E*E#+*#,规约10）#E+E##+#,规约11）#E#接受对输入串i+i*i的算符优先分析过程+-*/()i#+-*/(=)i#=算符优先关系表如何确定算符优先关系？（0）i的优先级最高（1）优先级次于i，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号（5）#的优先性低于与其相邻的算符文法G[E]：E→E+E|E-E|E*E|E/E|EE|(E)|i+-*/()i#+-*/(=)i#=算符优先关系表算符文法的定义定义如果不含空产生式的上下文无关文法G中没有形如U…VW…的产生式，其中V,W∈VN则称G为算符文法（OG）。性质1：在算符文法中任何句型都不包含两个相邻的非终结符.(数学归纳法)性质2：如Vx或xV出现在算符文法的句型中，其中V∈VN,x∈VT,则中任何含x的短语必含有V.（反证法）注：证明的具体步骤见书P100算符优先关系的定义在OG中定义（算符优先关系）(U，V∈VN；x，y∈VT)x=yG中有形如：U…xy…或U…xVy…的产生式。xyG中有形如：U…xW…的产生式，而Wy….或WVy…xyG中有形如：U…Wy…的产生式，而W…x或W…xV规定若Sx…或SVx…则#xS…x或S…xV则x#算符优先文法的定义在OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G为算符优先文法(OPG)。注意：允许bc,cb;不允许bc,bc,b=c结论算符优先文法是无二义的。算符优先关系表的构造由定义直接构造由关系图法构造算符优先关系表FIRSTVT(B)={b|Bb…或BCb...}对于非终结符B，其往下推导所可能出现的首个算符（终结符）LASTVT(B)={a|B…a或B...aC}对于非终结符B，其往下推导所可能出现的最后一个算符（终结符）首先引入两个概念其中：B，C∈VN；a，b∈VT如何计算算符优先关系1)‘=‘关系直接看产生式的右部，若出现了A→…ab…或A→…aBb,则a=b2)’‘关系求出每个非终结符B的FIRSTVT(B)若A→…aB…,则b∈FIRSTVT(B),ab3)’’关系求出每个非终结符B的LASTVT(B)若A→…Bb…,则a∈LASTVT(B),ab文法G[E]：(0)E’→#E#(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF|P(6)P→(E)(7)P→iFIRSTVT(E’)={#}FIRSTVT(E)={+,*,,(,i}FIRSTVT(T)={*,,(,i}FIRSTVT(F)={,(,i}FIRSTVT(P)={(,i}LASTVT(E’)={#}LASTVT(E)={+,*,,),i}LASTVT(T)={*,,),i}LASTVT(F)={,),i}LASTVT(P)={),i}1)‘=’关系由产生式(0)和(6),得#=#，（=）3)‘’关系找形如：A→…Bb…的产生式E#,则LASTVT(E)#E+,则LASTVT(E)+T*,则LASTVT(T)*P,则LASTVT(P)E),则LASTVT(E))2）‘’关系找形如：A→…aB…的产生式#E：则#FIRSTVT(E)+T:则+FIRSTVT(T)*F:则*FIRSTVT(F)F:则FIRSTVT(F)(E:则(FIRSTVT(E)+*()i#+*(=)i#=算符优先分析算法归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的，P110。为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念。算符优先分析句型的性质算符文法的任一句型有如下形式：#N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1为句柄，则有ai-1ai=ai+1=...=aj-1=ajaj+1对于算符优先文法，如果aNb(或ab)出现在句型r中若ab，则在r中必含有b而不含a的短语存在若ab，则在r中必含有a而不含b的短语存在若a=b，则在r中含有a的短语必含有b，反之亦然最左素短语定义文法G[S]的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。素短语可以看作是包含有终结符的直接短语(错误的说法)处于句型最左边的素短语为最左素短语。文法G[E]：(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF|P(6)P→(E)(7)P→i句型#T+T*F+i#其短语有：T+T*F+iT+T*FTT*Fi最左素短语为：T*F句型#N+N*N+i#的归约过程素短语：T*F，i*EET++ETFFTTi句型T+T*F+i的语法树NN++NNi*NNN算符优先分析时语法树的框架算符优先分析法的局限性一般语言的文法很难满足算符优先文法的条件很难避免把错误的句子得到正确的归约算符优先分析法仅适用于表达式的语法分析。