编译原理_05自底向上的语法分析方法

1第6章自底向上优先分析法2主要内容6.1自底向上优先分析概述6.3算符优先分析法3课题：自底向上分析方法、算符优先文法目的要求：1.理解自底向上的语法分析方法的基本思想；2.掌握算符文法、算符优先文法的定义和性质教学重点：1.优先分析法的基本思想和术语；2.算符文法、算符优先文法的定义和性质教学难点：算符优先关系的定义教学课时：2教学方法：多媒体教学教学内容和步骤：（如下）第十二讲4自底向上分析方法，也称移进归约分析法实现思想（是推导的逆过程）：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功。自底向上分析方法的基本思想5例1：文法:SaAcBeAbAAbBd输入串abbcde#分析最右推导：SaAcBeaAcdeaAbcdeabbcde规约分析过程如下：6步骤符号栈输入符号串动作1#abbcde#移进2#abbcde#移进3#abbcde#归约A→b4#aAbcde#移进5#aAbcde#归约A→Ab6#aAcde#移进7#aAcde#移进8#aAcde#归约B→b9#aAcBe#移进10#aAcBe#规约S→aAcBe11#S#接受7上述的每一步规约可以构造一颗语法树：AbBdAAbbSAbbaceBdA8问题的提出：①在构造语法树的过程中，何时规约？当句柄出现在栈顶符号串中就可以规约。②如何知道在栈顶符号串中已经形成句柄？通过自底向上的分析算法来解释（优先关系）9优先分析法又可分简单优先分析法和算符优先分析法。①简单优先分析法（规范归约）－对文法按一定原则求出所有文法符号间的优先关系；②算法优先分析法（不规范归约）－规定算符之间的优先关系）6.1自底向上优先分析法概述106.3算符优先分析法•算符优先优先分析法只规定算符（终结符）之间的优先关系。在归约过程中只要找到句柄就归约，不必考虑归约到哪个非终结符，因此不是规范归约。特点：速度快，特别适合于表达式的分析•通过算符之间的优先关系来确定句柄11先看一个例题：例.已知文法G[E]：E→E+EE→E*EE→i输入串i+i*i，归约过程如下12步骤符号栈输入符号串优先关系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#接受动作13分析可知：若只从移进—归约的角度来考虑，在第6步时栈顶已出现了句柄E+E，可以进行归约了，但是明显是错误的，因为这样就不符合算术运算规律。所以对于表达式，我们可以人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性。14算符文法定义：•设有一文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法(或称OG文法)。•即任何一个产生式中都不包含两个非终结符相邻的情况，就是算符文法。15性质1：在算符文法中任何句型都不包含两个相邻的非终结符。性质2：如果Ab或（bA）出现在算符文法的句型中，其中AVN，bVT，则中任何含b的短语必含有A。（含b的短语必含A，含A的短语不一定含b）16算符优先关系的定义：•设G是一个算符文法，a和b是任意两个终结符，A，B，C是非终结符，算符优先关系如下：(1)a=b当且仅当G中含有形如A→…ab…或A→…aBb…的产生式;(2)ab当且仅当G中含有形如A→…aB…的产生式，且Bb…或BCb…；(3)ab当且仅当G中含有形如A→…Bb…的产生式，且B…a或B…aC。＋＋＋＋17算符优先文法的定义：设有一不含产生式的算符文法G，如果对任意两个终结符a，b之间至多只有=，和三种关系的一种成立，则称G是一个算符优先文法(也称OPG文法)。即ab，ab，ab只有一种成立，但允许ab，ba同时存在。18例：已知表达式文法G[E]：E→E+E|E*E|(E)|i证明G[E]不是OPG文法。证明如下：因为：E→E+E，EE*E则有+*又因为：E→E*E,EE+E则有+*所以不是算符优先文法。＋＋19自底向上分析方法，也称移进归约分析法，是推导的逆过程。算法优先分析法（不规范归约）－规定算符之间的优先关系）文法符号之间的优先关系有三种：大于、小于和等于。算符优先文法(也称OPG文法)，它是一个算符文法，不含产生式，且对任意两个终结符a，b之间至多只有=，和三种关系的一种成立。教学总结20教材P122练习:2(1)，3(1)作业21课题：算符优先关系表和算符优先分析法目的要求：1.掌握算符优先关系表的构造方法；3.掌握算符优先分析法及其局限性教学重点：1.符优先关系表的构造2.算符优先分析法的实现；教学难点：算符优先关系表的构造教学课时：2教学方法：多媒体教学教学内容和步骤：（如下）第十三讲22三、算符优先关系表用表格形式来表示各终结符号的优先关系，这种表称为优先关系表。构造优先关系表的方法：①按照定义来构造②按关系图来构造•首先引入两个概念：firstVT集合lastVT集合first(B)={b|Bb…或BCb…}lastVT(B)={a|B…a或B…aC}++++231)=关系直接看产生式的右部，若出现了A→…ab…或A→…aBb，则a=b2)关系求出每个非终结符B的FIRSTVT(B)若A→…aB…，则b∈FIRSTVT(B)，ab3)关系求出每个非终结符B的LASTVT(B)若A→…Bb…，则a∈LASTVT(B)，ab三种算符优先关系的计算：24例：已知文法如下，计算优先关系E’→#E#E→E+TE→TT→T*FT→FF→P↑FF→PP→（E）P→i25解:(1)先求firstVT和lastVT集first(E’)={#}first(E)={+,*,↑,(,i}first(T)={*,↑,(,i}first(F)={↑,(,i}first(P)={(,i}lastVT(E’)={#}lastVT(E)={+,*,↑,),i}lastVT(T)={*,↑,),i}lastVT(F)={),↑,i}lastVT(P)={i,)}26(2)求=关系E’→#E##=#P→(E)(=)(3)求关系E’→#E#则#first(E)所以#+,#*,#↑,#(，#i27E’→E+T则+first(T)所以+*,+↑,+(,+iT→T*F则*first(F)所以*↑,*(,*iF→P↑F则↑first(F)所以↑↑,↑(,↑iP→（E)则（first(E)所以(+,(*,(↑,((,(i28(4)求关系E’→#E#则lastVT(E)#所以+#,*#，↑#,)#,i#E→E+T则lastVT(E)+所以++,*+,↑+,)+,i+T→T*F则lastVT(T)*所以**,↑*,i*,)*F→P↑F则lastVT(P)↑所以i↑,)↑P→(E)则lastVT(E))所以+),*),↑),i),))29算符优先关系表+*↑i()#+*↑i(=)#=30算符优先分析算法：•归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的.•为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念31•算符文法的任一句型有如下形式：#N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1为句柄，则有ai-1ai=ai=...=aj-1=ajai+1•对于算符优先文法，若句型r中含有aNb(或ab)若ab，则在r中必有含b而不含a的短语存在若ab，则在r中必有含a而不含b的短语存在若a=b，则在r中含有a的短语必含有b，反之亦然32最左素短语：定义：设有文法G[S]，其中句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。例：文法G[E]:E→E+T|TT→T*F|FF→P↑F|PP→（E）|i句型#T+T*F+i#的语法树如下：33EET+E+TFTT*FPi根据语法树可知：句型#T+T*F+i#的短语有：T；T*F；T+T*F；i；T+T*F+i.34根据素短语的定义可知：i和T*F为素短语。其中：T+T*F(含其他T*F素短语)和T+T*F+i不是素短语。T*F为最左素短语。六、算符优先分析法的局限性35算符优先关系表是指用表格形式来表示各终结符号的优先关系的表。为分析算符之间的优先关系，引入两个概念：firstVT集合和lastVT集合：对于非终结符B，有firstVT(B)={b|Bb…或BCb…}lastVT(B)={a|B…a或B…aC}为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念。算符优先分析法只适用于对表达式的分析，其特点是分析速度快。教学总结36教材P122练习:4作业