《第6章 自底向上优先分析法.ppt》由会员分享，可在线阅读，更多相关《第6章 自底向上优先分析法.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第6章章 自底向上优先分析法自底向上优先分析法自底向上优先分析概述自底向上优先分析概述简单优先分析简单优先分析算符优先分析算符优先分析6.1 自底向上分析方法自底向上分析方法自底向上分析方法，也称自底向上分析方法，也称移进移进-归约归约分析法。分析法。实现思想：实现思想：对输入符号串自左向右进行扫描，并对输入符号串自左向右进行扫描，并将输入符逐将输入符逐将输入符逐将输入符逐个移入一个后进先出栈中个移入一个后进先出栈中个移入一个后进先出栈中个移入一个后进先出栈中，边移入边分析，边移入边分析，一旦一旦一旦一旦栈顶符号串形成某个句型的句柄时，栈顶符号串形成某个句型的句柄时，栈顶符号串形成某个句型的
2、句柄时，栈顶符号串形成某个句型的句柄时，（该句型对（该句型对应某产生式的右部），应某产生式的右部），就用就用就用就用该产生式的该产生式的左部左部左部左部非终非终结符结符代替代替代替代替相应右部的文法符号串，这称为相应右部的文法符号串，这称为归约归约归约归约。重复这一过程直到归约到栈中只剩文法的开始符重复这一过程直到归约到栈中只剩文法的开始符重复这一过程直到归约到栈中只剩文法的开始符重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功号时则为分析成功号时则为分析成功号时则为分析成功，也就确认输入串是文法的句，也就确认输入串是文法的句子。子。文法文法GS：(1)S aAcBe(2)A b(3
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#接受接受S10）#aAcBe#归约归约(SaAcBe)分析符号串abbcde是否GS的句子对输入串abbcde#的移进-规约分析过程SaAcBe aAcde aAbcde abbcde算法应考虑
4、的问题算法应考虑的问题算法是否能够终止？算法是否能够终止？算法是否快速？算法是否快速？算法是否能够处理所有的情况？算法是否能够处理所有的情况？在每一步中如何选择子串进行归约？在每一步中如何选择子串进行归约？这一方法简单明了这一方法简单明了这一方法简单明了这一方法简单明了,不断地进行移进规约不断地进行移进规约不断地进行移进规约不断地进行移进规约,关键是确定当前句型的关键是确定当前句型的关键是确定当前句型的关键是确定当前句型的句柄句柄句柄句柄.自下而上语法分析的策略：移进自下而上语法分析的策略：移进-规约分析；规约分析；移进移进就是将一个终结符推进栈就是将一个终结符推进栈归约归约就是将就是将0 0
5、个或多个符号从栈中弹出，根据产生个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈式将一个非终结符压入栈移进移进-归约过程是自顶向下最右推导的逆过程（规归约过程是自顶向下最右推导的逆过程（规范归约）范归约）6.1 优先分析法优先分析法简单优先分析法简单优先分析法对一个文法按一定原则求出该文法所有符号（终结符对一个文法按一定原则求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实际上是一种规范归约。约过程中的句柄，它的归约实际上是一种规范归约。算符优先分析法算符优先分析法只规定算符（终结符）之间的优先
6、关系。找到句柄就只规定算符（终结符）之间的优先关系。找到句柄就归约，不是规范归约。归约，不是规范归约。6.2 简单优先分析法简单优先分析法按照文法符号（包括终结符和非终结符）的按照文法符号（包括终结符和非终结符）的优先关系确定句柄。优先关系确定句柄。文法文法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,归约归约Aa 5）#b(A a)b#A=a,移进移进 6）#b(Aa )b#a=),移进移进 7）#b(Aa)b#)b,归约归约BAa)8
7、）#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 1）在文法符号集）在文法符号
8、集V V中，任意两个符号之间最中，任意两个符号之间最多只有一种优先关系成立。多只有一种优先关系成立。（2 2）在文法中任意两个产生式没有相同的右部）在文法中任意两个产生式没有相同的右部（3 3）不含空产生式）不含空产生式6.2 简单优先分析法简单优先分析法根据已知优先文法构造相应优先关系矩阵，并将文根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈法的产生式保存，设置符号栈S，算法步骤如下：算法步骤如下：1.将输入符号串将输入符号串a1a2a3.an#依次逐个存入符号栈依次逐个存入符号栈S中，中，直到遇到栈顶符号直到遇到栈顶符号ai的优先性大于下一个待输入符的优先性大于下一
9、个待输入符号号aj时为止。时为止。2.栈顶当前符号栈顶当前符号ai为句柄尾，由此向左在栈中找句柄为句柄尾，由此向左在栈中找句柄的头符号的头符号ak，即找到即找到ak-1ak为止。为止。3.由句柄由句柄ak.ai在文法的产生式中查找右部为在文法的产生式中查找右部为ak.ai的的产生式，若找到则用相应左部代替句柄，若找不到产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。则为出错，这时可断定输入串不是该文法的句子。4.重复上述三步，直到归约完输入符号串，栈中只剩重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。文法的开始符号为止。如何确定优先关系
10、的例子如何确定优先关系的例子文法文法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.#查看关系定义6.3算符优先分析法算符优先分析法某些文法具有某些文法具有“算符算符”特性特性表达式运算符（优先级、结合性）表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性和同一级别的结合性只考
11、虑算符之间的优先关系来确定句柄只考虑算符之间的优先关系来确定句柄文法文法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+E#,规约规约11）#E#接受接受对输入串对输入串i+ii+i*i*i的算符优先分析过程的算符优先分析
12、过程算符优先关系表如何确定算符优先关系？如何确定算符优先关系？（0 0）i i的优先级最高的优先级最高（1 1）优先级次于优先级次于i i，右结合右结合（2 2）*和和/优先级次之，左结合优先级次之，左结合（3 3）+和和-优先级最低，左结合优先级最低，左结合（4 4）括号）括号(,)的优先级大于括的优先级大于括号外的运算符，小于括号内的运算符，号外的运算符，小于括号内的运算符，内括号的优先性大于外括号内括号的优先性大于外括号（5 5）#的优先性低于与其相邻的算符的优先性低于与其相邻的算符文法文法GE：EE+E|E-E|E*E|E/E|E E|(E)|i算符优先关系表算符文法的定义算符文法的定
13、义定义定义 如果不含空产生式的上下文无关文法如果不含空产生式的上下文无关文法 G G 中中没有形如没有形如 U UVWVW的产生式，其中的产生式，其中V,WVV,WVN N则称则称G G 为算符文法（为算符文法（OGOG）。）。性质性质1 1：在算符文法中任何句型都不包含两个相邻在算符文法中任何句型都不包含两个相邻的非终结符的非终结符.性质性质2 2：如如 VxVx 或或 xVxV 出现在算符文法的句型出现在算符文法的句型 中，其中中，其中VVVVN N,xV,xVT T,则则 中任何含中任何含 x x 的短语必的短语必含有含有V.V.算符优先关系的定义算符优先关系的定义在在OG中中 定义定义
14、 （算符优先关系）（算符优先关系）x=y G中有形如中有形如.Uxy或或U xVy.的产生式。的产生式。x y G中有形如中有形如.U Wy的产生式的产生式,而而 W x或或W xV规定规定 若若 S x或或 S Vx 则则#算符优先文法的定义算符优先文法的定义在在 OG文法文法 G 中，若任意两个终结符间中，若任意两个终结符间至多至多有一种有一种算符优先关系存在，则称算符优先关系存在，则称G 为算符优为算符优先文法先文法(OPG)。注意：允许注意：允许bc,cb;不允许不允许bc,bc,b=c 结论结论 算符优先文法是无二义的。算符优先文法是无二义的。可以证明文法可以证明文法GE：EE+E|
15、E-E|E*E|E/E|E E|(E)|I具有二义性具有二义性.怎么证明怎么证明,请同学们思考请同学们思考.算符优先关系表的构造算符优先关系表的构造由定义直接构造由定义直接构造由关系图法构造算符优先关系表由关系图法构造算符优先关系表首先引入两个概念首先引入两个概念FIRSTVT(B)=b|B b或或B Cb.对于非终结符对于非终结符B，其往下推导所可能出现的首个其往下推导所可能出现的首个算符算符LASTVT(B)=a|B a或或B .aC对于非终结符对于非终结符B，其往下推导所可能出现的最后其往下推导所可能出现的最后一个算符一个算符由定义直接构造由定义直接构造如何计算算符优先关系如何计算算符优
16、先关系1)=关系关系直接看产生式的右部，若出现了直接看产生式的右部，若出现了A ab或或A aBb,则则a=b2)关系关系求出每个非终结符求出每个非终结符B的的FIRSTVT(B)若若AaB,则则 b FIRSTVT(B),a关系关系求出每个非终结符求出每个非终结符B的的LASTVT(B)若若ABb,则则 a LASTVT(B),ab文法文法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)=(
17、,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(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(
18、E)算符优先分析算法算符优先分析算法归约过程中，只考虑终结符之间的优先关系归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的法的规约过程与规范归约是不同的.为解决在算符优先分析过程中如何寻找句柄，为解决在算符优先分析过程中如何寻找句柄，引进引进最左素短语最左素短语的概念的概念最左素短语最左素短语算符文法的任一句型有如下形式：算符文法的任一句型有如下形式：#N N1 1a a1 1N N2 2a a2 2.N.Nn na an
19、nN Nn+1n+1#,若若N Ni ia ai i.N.Nj ja aj jN Nj+1j+1为句为句柄，则有柄，则有a ai-1i-1 a ai+1i+1对于算符优先文法，如果对于算符优先文法，如果aNbaNb(或或abab)出现在句型出现在句型r r中中若若ababab，则在则在r r中必含有中必含有a a而不含而不含b b的短语存在的短语存在若若a=ba=b，则在则在r r中含有中含有a a的短语必含有的短语必含有b b，反之亦然反之亦然定义定义 cfgcfg G G 的句型的素短语是一个短语，它的句型的素短语是一个短语，它至至少包含一个终结符少包含一个终结符，且除自身外，且除自身外不
20、再包含其他素短不再包含其他素短语语。处于句型最左边的素短语为。处于句型最左边的素短语为最左素短语最左素短语文法文法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*F句型#N+N*N+i#的归约过程在实际分析过程中不必考虑非终结符名是T还是F或是E，而只要知道是非终结符即可，具体在表达式文法中的T还是F或是E都为运算对象。上述句型#T+T*F+i#的归约过程由于去掉了单非终结符ET，TF的归约，所以得不到真正的语法
21、树，而只是构造出语法树的框架。NN+NNi*NNN(3)算符优先分析归约过程的算法算符优先分析归约过程的算法自底向上的算符优先分析法，也为自左向右归自底向上的算符优先分析法，也为自左向右归约，我们已经知道它不是规范归约。规范归约的关约，我们已经知道它不是规范归约。规范归约的关键问题是如何寻找当前句型的句柄，而算符优先分键问题是如何寻找当前句型的句柄，而算符优先分析归约的关键是如何找最左素短语。最左素短语析归约的关键是如何找最左素短语。最左素短语 NiaiNi+1ai+1 ajNj+1 应满足：应满足：ai-1=aiai=ai+1 =ajaj aj+1算符优先分析法的例子算符优先分析法的例子对于
22、算符优先文法对于算符优先文法EE+T|T TT*F|F F(E)|I 句型句型i+(i+i)*i的识别过程如下：的识别过程如下：步骤步骤句型句型关系关系最左素短语最左素短语 归约符号归约符号1#i+(i+i)*i#i+i F2#F+(i+i)*i#+(i+i F3#F+(F+i)*i#+(+i)i F4#F+(F+F)*i#+(+)F+F E5#F+(E)*i#+()(E)F6#F+F*i#+*i#i F7#F+F*F#+*#F*F T8#F+T#+#F+T E9#E#接受作业作业:1、阅读、阅读P121例题例题12、做、做P122 1、(1)(2)(4)3、优先函数优先函数优先函数比优先矩阵
23、节省空间优先函数比优先矩阵节省空间当发生错误时不能准确指出出错位置当发生错误时不能准确指出出错位置如：如：i+ii*i#，两个相邻两个相邻i不存在优先关系，但优先不存在优先关系，但优先函数存在，会归约成函数存在，会归约成N+NN.而发现错误。而发现错误。优先函数的构造优先函数的构造由定义直接构造由定义直接构造用关系图构造优先函数用关系图构造优先函数算符优先分析法的局限性算符优先分析法的局限性一般语言的方法很难满足算符优先文法的条一般语言的方法很难满足算符优先文法的条件件很难避免把错误的句子得到正确的归约很难避免把错误的句子得到正确的归约6.2.5 算符优先分析法的局限性算符优先分析法的局限性 由于算符优先分析法去掉了单非终结符之间的归约，由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取一些尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确检查措施，但仍难完全避免把错误的句子得到正确的归约。例如，下述文法是一个算符优先文法，的归约。例如，下述文法是一个算符优先文法，其产生式为：其产生式为：SS;D|DDD(T)|HHa|(S)TT+S|S其中其中VNS，D，T，H，VT；,(,),a,+，S为开始符号。为开始符号。对应的算符优先关系矩阵见表对应的算符优先关系矩阵见表6.14