第6章 自底向上优先分析法.ppt

第六章自底向上优先分析方法,教学要求：掌握算符优先分析法的关系表的构造以及分析过程，了解简单优先分折法。教学重点：算符优先表构造及算符优先分析法。,从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。工作方式：“移进归约”方式。,自底向上分析法的基本思想,分析程序模型,1）初态时栈内仅有栈底符“”，读头指针在最左单词符号上。2）语法分析程序执行的动作：a）移进读入一个单词并压入栈内，读头后移；b）归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；c）识别成功移进归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；d）识别失败,例如：,有文法如下（1）SaAcBe（2）Ab（3）AAb（4）Bd问：语句abbcde是不是该文法的合法语句？,移进归约的分析过程,GS:（1）SaAcBe（2）Ab（3）AAb（4）Bd,遇到的问题：（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结束（接受）,例：EE+E|E-E|E*E|E/E|(E)|i,一、算符文法的定义,1、给定上下文无关文法G，若G中所有产生式右部都不包含两个相继的非终结符，则G为算符文法。注：算符文法保证了两个运算符之间只有一个操作数。,2、算符优先文法定义,设G是一个不包含空串产生式的算符文法，并设a,bVT;P,Q,RVN,定义关系：,1)ab当且仅当G中含有形如Pab产生式，或者PaQb产生式；,若G中任何终结符序偶（a,b）至多满足上述关系之一，则称G为算符优先文法。,2)ab当且仅当G中含有形如PaR的产生式，其中Rb,或RQb;,3)ab当且仅当G中有形如PRb产生式，其中Ra，或RaQ.,用语法树来理解更直观,ab,ab,注意,表达式文法：EE+E|E*E|(E)|i是算符文法，但不是算符优先文法。,两个算符之间的优先关系是有序的，允许有ab,ba同时存在，而不允许有ab，ab,ab三种情况之两种同时存在。,1、各非终结符P的首终结符集和尾终结符集定义：首终结符集FIRSTVT(P)=a|Pa或PQa，aVT;P,QVN尾终结符集LASTVT(P)=a|Pa或PaQ，aVT;P,QVN,三、算符优先文法及优先表的构造,注：有了这两个集合，就可通过检查每个产生式的每个候选式，确定满足关系和的所有终结符序偶。,2、构造首终结符集和尾终结符集算法1)构造集合FIRSTVT(P)的算法根据FIRSTVT(P)的定义，按下面的规则来构造：(1)若有产生式Pa或PQa，则aFIRSTVT(P)(2)若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P),2)构造LASTVT(P)的算法。根据LASTVT的定义，按下面的规则来构造：(1)若有产生式Pa或PaQ，则aLASTVT(P)(2)若aLASTVT(Q)，且有产生式PQ，则aLASTVT(P),3)构造算符优先表的算法FOR每条产生式PX1X2XnDOFOR(i=1,i=n-1,i+)ifXi和Xi+1均为终结符then置XiXi+1;ifi#E#1.EE+T|T2.TT*F|F3.FPF|P4.P(E)|i,5)优先关系表+*i()#+*i()#,1、最左素短语在算符优先分析中，可归约的短语不再称为句柄，而称为最左素短语。素短语：至少含有一个终结符，且除它自身外不再包含其他素短语的短语。最左素短语：最左边的素短语。,四、算符优先分析方法,例如：考虑非二义的表达式文法G(E)：EE+T|TTT*F|FF(E)|i句型T+T*F+i#的素短语是什么？,由定义可知，素短语有：T*F,i最左素短语：T*F,一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串：NjajNiaiNi+1,aj-1ai+1根据这个最左素短语的定义可以构造算符优先分析算法。,输入：一个输入符号串w和一张优先关系表。输出：若w是一个句子，输出一棵分析树基架，否则输出一个错误信息。方法：分别置放#到栈中和w#到输入缓冲器中，并执行如下所示的程序。,2、算符优先分析算法,置ip,使之指向w#的第一个符号；repeatif#在栈顶上并且ip指向#thenreturnelsebegin令a是栈中最靠顶上的终结符号并且令b是ip所指向的符号ifabthen/*归约*/repeat从栈中弹出符号until栈顶终结符号与最近弹出的符号之间有关系成立elseerror()end,例：根据下面文法及其算符优先表，按通用算符优先分析的算法分析语句ifbthenielsei#。SifEbthenEelseEEE+T|TTT*F|FFiEbb,解：1）求各非终结符的首终结符集和尾终结符集。为了考虑语句的开始和结束符号“”，对文法拓广，加一个产生式SSFIRSTVT(S)=ifLASTVT(S)=else,+,*,iFIRSTVT(E)=+,*,iLASTVT(E)=+,*,iFIRSTVT(T)=*,iLASTVT(T)=*,iFIRSTVT(F)=iLASTVT(F)=iFIRSTVT(Eb)=bLASTVT(Eb)=b2)填写算符优先表,成功,归约,#,#N,10,对i归约,#,#ifNthenNelseN,9,移进,#,#ifNthenNelsei,8,移进,i#,#ifNthenNelse,7,对i归约,elsei#,#ifNthenN,6,移进,elsei#,#ifNtheni,5,移进,ielsei#,#ifNthen,4,thenielsei#,#ifN,3,0,动作,输入串,关系,下推栈,步骤,接受,#,ifbthenielsei#,移进,1,#if,bthenielsei#,移进,2,#ifb,thenielsei#,对b归约,5、算符优先分析的优缺点,优点：1)算符优先文法适用范围比简单优先文法大得多，许多程序设计语言都可以用它来分析。算符优先分析优先表构造简单，甚至可以用手工构造。2)算符优先分析比规