编译原理(第二版)第6章 自底向上优先分析法

第六章自底向上优先分析方法•教学要求：掌握算符优先分析法的关系表的构造以及分析过程，了解简单优先分折法。•教学重点：归约，算符优先表构造。•从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。•工作方式：“移进－归约”方式。自底向上分析法的基本思想分析程序模型1）初态时栈内仅有栈底符“＃”，读头指针在最左单词符号上。2）语法分析程序执行的动作：a）移进读入一个单词并压入栈内，读头后移；b）归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；c）识别成功移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；d）识别失败语法分析程序语法表a+b……#输出带#例如：有文法如下（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d问：语句abbcde是不是该文法的合法语句？成功11接受2,3,4,1＃＃S10归约＃＃aAcBe9移进2,3,4e＃＃aAcB8归约e＃＃aAcd7移进de＃＃aAc6移进2,3cde＃＃aA5归约cde＃＃aAb4移进2bcde＃＃aA3归约bcde＃＃ab2移进bbcde＃＃a1移进abbcde＃＃0动作输出带输入串栈步骤移进归约的分析过程G[S]:（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d遇到的问题：（1）如何找出进行直接归约的简单短语？（2）找出的简单短语应直接归约到哪一个非终结符？关键：确定句柄.常用的分析方法:优先分析和LR分析6.1自底向上优先分析法概述•分类:1、简单优先分析：对一个文法按一定原则求出所有符号即终结符号和非终结符号之间的优先关系,按照这种关系确定归约过程中的句柄.特点:准确、规范，但分析效率底，使用价值不大.2、算符优先分析：只规定算符（终结符号）之间的优先关系，不考虑非终结符号之间的优先关系，只要找到句柄就归约，不考虑归约到那个非终结符号。特点：不是规范归约，分析速度快，特别适合于表达式的分析.一、基本思想1、自下而上归约2、规定算符(更一般地说，指终结符)的优先级及结合规则，以使得分析过程唯一3、比较相邻两个算符而决定动作注：1)关键是对所有算符定义某种优先关系2)算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法6.3算符优先分析方法i+i-i*(i+i)归约过程如下：i+i-i*(i+i)设算量级别最高，最先归约；E+i-i*(i+i)E+E-i*(i+i)＋，－同级，先归约左边“＋”E-i*(i+i)E-E*(i+i)－，*不同级，先归约右边“*”E-E*(E+i)先括号内，后括号外E-E*(E+E)归约括号内E-E*(E)归约括号对E-E*E先归约“*”E-E后归约“-”E结束（接受）例：EE+E|E-E|E*E|E/E|(E)|i一、算符文法的定义1、给定上下文无关文法G，若G中所有产生式右部都不包含两个相继的非终结符，则G为算符文法。注：算符文法保证了两个运算符之间只有一个操作数。2、算符优先文法定义设G是一个不包含空串产生式的算符文法，并设a,bVT;P,Q,RVN,定义关系：1)ab当且仅当G中含有形如P…ab…产生式，或者P…aQb…产生式；若G中任何终结符序偶（a,b）至多满足上述关系之一，则称G为算符优先文法。2)ab当且仅当G中含有形如P…aR…的产生式，其中Rb…,或RQb…;=+=+3)ab当且仅当G中有形如P…Rb…产生式，其中R…a，或R…aQ.=+=+＞·•用语法树来理解更直观…ab…Aab…aB…b…AP…Bb…AP…aabab＞·注意EE*EE+EE*EEE+E+*•表达式文法：EE+E|E*E|(E)|i是算符文法，但不是算符优先文法。•两个算符之间的优先关系是有序的，允许有ab,ba同时存在，而不允许有ab，ab,ab三种情况之两种同时存在。+*＞·＞·＞·＞·1、各非终结符P的首终结符集和尾终结符集定义：首终结符集FIRSTVT(P)={a|Pa…或PQa…，aVT;P,QVN}尾终结符集LASTVT(P)={a|P…a或P…aQ，aVT;P,QVN}三、算符优先文法及优先表的构造注：有了这两个集合，就可通过检查每个产生式的每个候选式，确定满足关系和的所有终结符序偶。=+=+=+=+2、构造首终结符集和尾终结符集算法1)构造集合FIRSTVT(P)的算法根据FIRSTVT(P)的定义，按下面的规则来构造：(1)若有产生式P→a…或P→Qa…，则aFIRSTVT(P)(2)若aFIRSTVT(Q)，且有产生式P→Q…，则aFIRSTVT(P)2)构造LASTVT(P)的算法。根据LASTVT的定义，按下面的规则来构造：(1)若有产生式P→…a或P→…aQ，则aLASTVT(P)(2)若aLASTVT(Q)，且有产生式P→…Q，则aLASTVT(P)3)构造算符优先表的算法FOR每条产生式P→X1X2…XnDOFOR(i=1,i=n-1,i++){ifXi和Xi+1均为终结符then置XiXi+1;ifi=n-2andXi和Xi+2均为终结符andXi+1为非终结符then置XiXi+2;ifXi为终结符而Xi+1为非终结符thenforFIRSTVT(Xi+1)中的每个aDO{置Xia}ifXi为非终结符而Xi+1为终结符thenforLASTVT(Xi)中的每个aDO{置aXi+1}}注:如果文法G按此算法构造出的优先表没有重定义项，则文法G是个算符优先文法。[例]考虑下面文法：0.E’→#E#1.E→E+T|T2.T→T*F|F3.F→PF|P4.P→(E)|i构造优先关系表•解：1)关系：##，（）•2）计算每个非终结符的FIRSTVT和LASTVT集合FIRSTVT(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}LASTVT(E’)={#}LASTVT(E)={+，*，，)，i}LASTVT(T)={*，，)，i}LASTVT(F)={，)，i}LASTVT(P)={)，i}3)关系：对表达式文法中终结符在前，非终结符在后的相邻符号对有：#E，+T,*F,F,(E终结符FIRSTVT(非终结符)4)关系：对表达式文法中终结符在后，非终结符在前的相邻符号对有：E#，E+,T*,P,E)LASTVT(非终结符)终结符FIRSTVT(E’)={#}FIRSTVT(E)={+，*，，（，i}FIRSTVT(T)={*，，（，i}FIRSTVT(F)={，（，i}FIRSTVT(P)={（，i}0.E’-#E#1.EE+T|T2.TT*F|F3.FPF|P4.P(E)|i5)优先关系表+*i()#+*i()#1、最左素短语在算符优先分析中，可归约的短语不再称为句柄，而称为最左素短语。素短语：至少含有一个终结符，且除它自身外不再包含其他素短语的短语。最左素短语：最左边的素短语。四、算符优先分析方法例如：考虑非二义的表达式文法G(E)：EE+T|TTT*F|FF(E)|i句型＃T+T*F+i#的素短语是什么？EE＋TE+TFTT*Fi由定义可知，素短语有：T*F,i最左素短语：T*F一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串：Njaj…NiaiNi+1,aj-1·ajaj=aj+1,…,ai-1=·aiai·ai+1根据这个最左素短语的定义可以构造算符优先分析算法。输入：一个输入符号串w和一张优先关系表。输出：若w是一个句子，输出一棵分析树基架，否则输出一个错误信息。方法：分别置放#到栈中和w#到输入缓冲器中，并执行如下所示的程序。2、算符优先分析算法置ip,使之指向w#的第一个符号；repeatif#在栈顶上并且ip指向#thenreturnelsebegin令a是栈中最靠顶上的终结符号并且令b是ip所指向的符号ifa·borabthenbegin把b推入栈中；使ip前进到下一个符号；end；elseifa·bthen/*归约*/repeat从栈中弹出符号until栈顶终结符号与最近弹出的符号之间有·关系成立elseerror()end例：根据下面文法及其算符优先表，按通用算符优先分析的算法分析语句ifbthenielsei#。S→ifEbthenEelseEE→E+T|TT→T*F|FF→iEb→b解：1）求各非终结符的首终结符集和尾终结符集。为了考虑语句的开始和结束符号“＃”，对文法拓广，加一个产生式S′＃S＃FIRSTVT(S)={if}LASTVT(S)={else,+,*,i}FIRSTVT(E)={+,*,i}LASTVT(E)={+,*,i}FIRSTVT(T)={*,i}LASTVT(T)={*,i}FIRSTVT(F)={i}LASTVT(F)={i}FIRSTVT(Eb)={b}LASTVT(Eb)={b}2)填写算符优先表#bi*+elsethenif#bi*+elsethenif右左成功归约##N10对i归约##ifNthenNelseN9移进##ifNthenNelsei8移进i##ifNthenNelse7对i归约elsei##ifNthenN6移进elsei##ifNtheni5移进ielsei##ifNthen4thenielsei##ifN30动作输入串关系下推栈步骤接受#ifbthenielsei#移进1#ifbthenielsei#移进2#ifbthenielsei#对b归约5、算符优先分析的优缺点优点：1)算符优先文法适用范围比简单优先文法大得多，许多程序设计语言都可以用它来分析。算符优先分析优先表构造简单，甚至可以用手工构造。2)算符优先分析比规范归约要快得多，因为它跳过了许多单非终结符的归约。这既是优点，也是缺点。缺点：1)由于忽略了非终结符在归约中的作用，所以它可能会把本来不成为句子的输入串误认为是句子。2)有些文法不满足算符优先文法，必须先改写，有些甚至无法改写。事实上，许多符号对之间不存在优先关系。同时，若终结符数目多，优先表可能会占有太多空间。