自底向上优先分析法ppt课件

编译原理编译原理第第6 6章章 自底向上优先分析法自底向上优先分析法 自底向上优先分析概述 简单优先分析 算符优先分析编译原理编译原理自底向上分析方法自底向上分析方法 自底向上分析方法，也称移进-归约分析法。实现思想：对输入符号串自左向右进展扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串构成某个句型的句柄时，该句型对应某产生式的右部，就用该产生式的左部非终结符替代相应右部的文法符号串，这称为归约。反复这一过程直到归约到栈中只剩文法的开场符号时那么为分析胜利，也就确认输入串是文法的句子。S10#aAcBe#归约归约(SaAcBe)文法文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1#abbcde#移进移进 2#a bbcde#移进移进A 3#ab bcde#归约归约(Ab)4#aA bcde#移进移进A 5#aAb cde#归约归约(AAb)6#aA cde#移进移进 7#aAc de#移进移进B 8#aAcd e#归约归约(Bd)9#aAcB e#移进移进11#S#接受接受分析符号串分析符号串abbcdeabbcde能否为能否为GSGS的句子？的句子？对输入串abbcde#的移进-规约分析过程SaAcBe aAcde aAbcde abbcde编译原理编译原理算法应思索的问题算法应思索的问题 算法能否可以终止？算法能否可以终止？算法能否快速？算法能否快速？算法能否可以处置一切的情况？算法能否可以处置一切的情况？在每一步中如何选择子串进展归约？在每一步中如何选择子串进展归约？编译原理编译原理自下而上语法分析的战略：移进自下而上语法分析的战略：移进-规约分析。规约分析。移进就是将一个终结符推进栈。移进就是将一个终结符推进栈。归约就是将归约就是将0 0个或多个符号从栈中弹出，根个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈。据产生式将一个非终结符压入栈。移进移进-归约过程是自顶向下最右推导的逆过归约过程是自顶向下最右推导的逆过程规范归约。程规范归约。编译原理编译原理 简单优先分析法 对一个文法按一定原那么求出该文法一切符号终结符和非终结符之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实践上是一种规范归约。算符优先分析法 只规定算符终结符之间的优先关系。找到句柄就归约，不是规范归约。优先分析法优先分析法编译原理编译原理简单优先分析法简单优先分析法 按照文法符号包括终结符和非终结符 的优先关系确定句柄。编译原理编译原理文法文法GSGS：(1)S bAb(1)S bAb(2)A (B|a(2)A (B|a(3)B Aa)(3)B Aa)SbA(Ba)#Sb=A=(=a=)#步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1#b(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)#的简单优先分析过程简单优先关系矩阵编译原理编译原理优先关系优先关系优先关系优先关系X=Y 文法文法G中存在产生式中存在产生式A.XY.XY 文法文法G中存在产生式中存在产生式A.BD.，且且B .X,D Y.如何确定两个文法符号之间的优先关系？如何确定两个文法符号之间的优先关系？*编译原理编译原理简单优先文法的定义简单优先文法的定义 满足以下条件的文法是简单优先文法1在文法符号集V中，恣意两个符号之间最多只需一种优先关系成立。2在文法中恣意两个产生式没有一样的右部。3不含空产生式。编译原理编译原理简单优先分析法简单优先分析法根据知优先文法构造相应优先关系矩阵，并将文法的产生式保管，设置符号栈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.求求关系：关系：由由(1)(2)：b(ba由由(2)(3)：(A (关系：关系：由由(1)：Bb ab)b由由(3)：Ba aa)a4.#SbA(Ba)#Sb=A=(=a=)#编译原理编译原理算符优先分析法算符优先分析法 某些文法具有“算符特性 表达式运算符优先级、结合性 人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性 只思索算符之间的优先关系来确定句柄编译原理编译原理文法文法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+ii+i*i i的算符优先分析过程的算符优先分析过程+-*/()i#+-*/(=i#-*/(=i#=算符优先关系表算符优先关系表编译原理编译原理算符文法的定义算符文法的定义 定义定义 假设不含空产生式的上下文无关文法假设不含空产生式的上下文无关文法 G G 中没有形如中没有形如 U UVWVW的产生式，其中的产生式，其中V,WVNV,WVN那么称那么称G G 为算符文法为算符文法OGOG。性质性质1 1：在算符文法中任何句型都不包含两个：在算符文法中任何句型都不包含两个相邻的非终结符相邻的非终结符.(.(数学归纳法数学归纳法)性质性质2 2：如：如 Vx Vx 或或 xV xV 出如今算符文法的句型出如今算符文法的句型 中，其中中，其中VVN,xVT,VVN,xVT,那么那么 中任何含中任何含 x x 的短语必含有的短语必含有V.V.反证法反证法编译原理编译原理算符优先关系的定义算符优先关系的定义在在OGOG中中 定义定义 算符优先关系算符优先关系x=y Gx=y G中有形如中有形如.U.Uxyxy或或U U xVy.xVy.的产的产生式。生式。x y Gx y Gxy G中有形如中有形如.U.U Wy Wy的产生式的产生式,而而 W xW x或或W xVW xV规定规定 假设假设 S x S x或或S Vx S Vx 那么那么#x#x#编译原理编译原理算符优先文法的定义算符优先文法的定义 在 OG文法 G 中，假设恣意两个终结符间至多有一种算符优先关系存在，那么称G 为算符优先文法(OPG)。留意：允许bc,cb;不允许bc,bc,b=c 结论：算符优先文法是无二义的。编译原理编译原理算符优先关系表的构造算符优先关系表的构造由定义直接构造由定义直接构造由关系图法构造算符优先关系表由关系图法构造算符优先关系表编译原理编译原理 首先引入两个概念首先引入两个概念 FIRSTVT(B)=b|B bFIRSTVT(B)=b|B b或或B Cb.B Cb.对对于非终结符于非终结符B B，其往下推导所能够出现的首个，其往下推导所能够出现的首个算符。算符。LASTVT(B)=a|B aLASTVT(B)=a|B a或或B .aCB .aC对对于非终结符于非终结符B B，其往下推导所能够出现的最后，其往下推导所能够出现的最后一个算符。一个算符。编译原理编译原理如何计算算符优先关系如何计算算符优先关系1)=关系关系直接看产生式的右部，假设出现了直接看产生式的右部，假设出现了A ab或或A aBb,那么那么a=b。2)关系关系求出每个非终结符求出每个非终结符B的的FIRSTVT(B)，假设假设AaB,那么那么bFIRSTVT(B),那么那么a关系关系求出每个非终结符求出每个非终结符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)PiFIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i+-*/()i#+-*/(=i#=1)=关系关系由产生式由产生式(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)编译原理编译原理算符优先分析算法算符优先分析算法 归约过程中，只思索终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的，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 的句型的素短语是一个短语，它至少包含一个终结符，且除本身外不再包含其他素短语。处于句型最左边的素短语为最左素短语。编译原理编译原理文法文法GEGE：(1)EE+T(1)EE+T(2)ET(2)ET(3)TT(3)TT*F F(4)TF(4)TF(5)FP(5)FPF|PF|P(6)P(E)(6)P(E)(7)Pi(7)Pi句型句型#T+T*F+i#其短语有：其短语有：T+T*F+iT+T*FTT*FiEET+ETF*FTTi最左素短语为：最左素短语为：T*F句型#N+N*N+i#的归约过程NN+NNi*NNN编译原理编译原理优先函数优先函数 优先函数比优先矩阵节省空间 当发生错误时不能准确指出出错位置 如：i+ii*i#，两个相邻i不存在优先关系，但优先函数存在，会归约成N+NN.而发现错误。优先函数的构造 由定义直接构造 用关系图构造优先函数编译原理编译原理算符优先分析法的局限性算符优先分析法的局限性 普通言语的方法很难满足算符优先文法的条件。很难防止把错误的句子得到正确的归约。