《语法分析》PPT课件.ppt

《《语法分析》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《语法分析》PPT课件.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 语法分析和语法分析程序对象：单词流形式的源程序任务：根据语法规则，分析源程序的语法结构，同时进行语法检查输出：语法树假定：先不考虑语义问题常见分析方法：自顶向下()和自底向上():递归下降法,预测分析法(LL分析法):优先分析法,LR分析法 自顶向下自顶向下的语法分析:对已给的输入串对已给的输入串w,试图自试图自上而下地建立一棵语法树上而下地建立一棵语法树;或或者说者说,从从S出发出发,为为w构造一个构造一个最左推导最左推导.若成功若成功,则则w L(G),否则拒绝否则拒绝.一般说来一般说来,在为在为w寻求最左推寻求最左推导的每一步导的每一步,都涉及使用何产都涉及使用何产生式进行替换的

2、问题生式进行替换的问题.最简单最简单的方法是的方法是,逐一逐一试探试探.遗憾的是遗憾的是,逐一试探也不能完逐一试探也不能完全解决问题全解决问题.例如例如,在含有在含有左递左递归归的文法中的文法中,就会出现不能终就会出现不能终止的替换现象止的替换现象.例例:ET|EAT TF|TMF F(E)|i A+|-M*|/(4.1)设设w=i+i*i,每个产生式从每个产生式从左至右试验左至右试验.从从E出发出发:ETF(E)i TMFFMF(E)MF iMF i*F i/F TMFMF TMFMFMF.自顶向下分析方法的特点1.若G有左递归,则分析不能正常进行.因此,分析必须必须先消除文法的左递归先消除

3、文法的左递归;2.分析过程是反复进行试探的过程,因此,难免会出现大量的回溯.特别是当w L(G)时,只有在穷举完所有的试探后才能拒绝w.由于回溯,就需将从出错点到迄今为止已做过的大量工作废弃,显然会大大降低分析的效率降低分析的效率.特别是在语法分析阶段还往往要进行同步的语义分析和处理,这些工作也就白做了.因此,消除回溯消除回溯是 分析分析的另一目标.3.当拒绝w时,只能知道w不是句子,不知出何错及出在何处 消除文法的左递归设文法是已简化的设文法是已简化的.若文若文法含直接左递归式法含直接左递归式:AA|(V+),引入新的非引入新的非终结符终结符A,令其产生令其产生*,则则有有:A A A A|

4、由于由于 不以不以A打头打头,A非左非左递归递归.对对P105的文法的文法(4.1),可可改写为改写为ETE EATE|TFT TMFT|F(E)|i A+|-M*|/一般地一般地,设文法中全部设文法中全部A-A-产产生式为生式为AA 1|A 2|A n|1|m,其中其中,i不以不以A打头打头,则消除直接左递归后则消除直接左递归后的产生式为的产生式为 A1A|mA 及A 1A|nA上述方法可消除直接左递归上述方法可消除直接左递归,但对于但对于间接左递归间接左递归的文法来的文法来说说,需将原文法进行需将原文法进行变换变换后后才适用才适用.例如例如,S Ab|c ASa,可将其变换为可将其变换为S

5、 Sab|c,再使用上述方法再使用上述方法,得得S cSS abS 回溯的消除及LL(1)文法为解决回溯问题为解决回溯问题,我们从句子的我们从句子的最左推导开始讨论最左推导开始讨论.设设G=(VN,VT,P,S)G=(VN,VT,P,S)为一为一CFGCFG,w=aw=a1 1a a2 2aan n是是V VT T上的符号串上的符号串,现现需判明需判明w w是否是是否是L(G)L(G)中的句子中的句子.为此为此,从从S S注意注意,i=1时时,w1=,A=S由假设可知由假设可知,到目前为止到目前为止,w的前的前缀缀w1已匹配已匹配,现在需对现在需对A 进行进行推导推导.对于当前输入符号对于当前

6、输入符号a ai i,若只有一个若只有一个 j j(称为候选式称为候选式)使得从使得从 j j 出发可出发可以推导出一个以以推导出一个以a ai i打头的符号串打头的符号串:而其它的而其它的 k k(k(k j),j),k k 都推导不出都推导不出以以a ai i打头的符号串打头的符号串,则选定产生式则选定产生式A A j j就是唯一可行的推导就是唯一可行的推导,即即w w L(G)L(G)选选A Aj j正确正确;w w L(G)L(G)选任何产生式均不能匹配选任何产生式均不能匹配显然显然,若若P P中产生式能满足上述要求中产生式能满足上述要求,则则回溯可消除回溯可消除为得到为得到w w的剩

7、余部分的剩余部分a ai ia ai+1i+1aan n.由最由最左推导的定义左推导的定义,考虑考虑A A的所有产生式的所有产生式:消除回溯回溯的条件由前面的讨论可知，要实现由前面的讨论可知，要实现无回溯无回溯的的 分析分析,文法必须满足一定的文法必须满足一定的条件条件。为导出这些条件。为导出这些条件,我们定义候选式的我们定义候选式的终结首符集终结首符集FIRST()=a|*a,a VT,V*并约定并约定*时时,FIRST()若对于若对于A-产生式的每个产生式的每个候选式候选式 i(i=1,2,m)都推不出都推不出 ,且且 FIRST(i)互不相交互不相交,则当正扫描的当前输入符号为则当正扫描

8、的当前输入符号为ai FIRST(j)时时,唯一可用于推导的产生式只能是唯一可用于推导的产生式只能是Aj.例如例如,文法文法G1S:SAAAaAb|*,A-产生式有两个产生式有两个候选式候选式,且且FIRST(aAb)=aFIRST(*)=*,两集两集不相交不相交,设输入串为设输入串为aa*bb*,其最左推导为其最左推导为 SAA (a)aAbA (a)aaAbbA(*)aa*bbA (*)aa*bb*(#)注注:上面第每步推导右侧括号内为当前扫描的输入符号上面第每步推导右侧括号内为当前扫描的输入符号,#,#为结束符为结束符.我们得到了一个无回溯的条件我们得到了一个无回溯的条件:FIRST(i

9、)FIRST(j)=消除回溯回溯的条件然而还存在另外一种情况然而还存在另外一种情况,可能存在某个候选式可能存在某个候选式 i i,i i*,即即FIRST(FIRST(i)i)(这样的是唯一的这样的是唯一的(?!)(?!),此时此时,为匹为匹配当前扫描的符号配当前扫描的符号a a就可能有就可能有两种选择两种选择,一是存在某一是存在某 j j,使使 j j推导出以推导出以a a打头的符号串打头的符号串,另一种选择是让另一种选择是让A A推导出推导出 i i,并让并让跟随在跟随在A A后的符号串推导出以后的符号串推导出以a a打头的符号串打头的符号串.若这两种选择都可行若这两种选择都可行,则回溯不

10、可避免则回溯不可避免.因此因此,就必须要求就必须要求当当 i i*时时,跟在跟在A A后的符号串不能推导出其它后的符号串不能推导出其它 j j 所能推所能推导出的首终结符符号串导出的首终结符符号串.为此为此,我们定义我们定义可紧跟在可紧跟在可紧跟在可紧跟在A A A A后的所后的所后的所后的所有终结符之集有终结符之集有终结符之集有终结符之集FOLLOW(A)=a|S#FOLLOW(A)=a|S#FOLLOW(A)=a|S#FOLLOW(A)=a|S#*AaAaAaAa ,a,a,a,a VTVTVTVT#,#,#,#,V*V*V*V*其中其中,当当A A为一句型的尾符号时为一句型的尾符号时,#

11、,#,#,#FOLLOW(A).FOLLOW(A).FOLLOW(A).FOLLOW(A).现在现在,我们可把无回溯的我们可把无回溯的另一条件另一条件描述为描述为:若若 i i*,则则FOLLOW(A)FOLLOW(A)FOLLOW(A)FOLLOW(A)与其它的与其它的 j j j j互不相交互不相交:FOLLOW(A)FOLLOW(A)FOLLOW(A)FOLLOW(A)FIRST(FIRST(FIRST(FIRST(j)=j)=j)=j)=.消除回溯回溯的条件例 SaA|b AcAS|FIRST(cAS)=c FOLLOW(A)FIRST(cAS)=c FOLLOW(A)=FIRST(S

12、)=FIRST(S)#=a,b,#=a,b,#两个集合不相交,故可进行无回溯的分析.设输入串w=aca#w=aca#,其推导过程如下:S#aA#当前输入符a属于FIRST(aA),用SaA推导 acAS#当前输入符c属于FIRST(cAS),用AcAS推导 acS#当前输入符a属于FOLLOW(A),用A推导.acaA#当前输入符a属于FIRST(aA),用SaA推导 aca#当前输入符#属于FOLLOW(A),用A推导,成功。最后最后,我们将消除回溯的条件归纳为我们将消除回溯的条件归纳为,对对G G中每个中每个A A V VT T,A-,A-产生式中任何两产生式中任何两个候选式个候选式 i

13、i,j j,均满足均满足:(1)FIRST(i)FIRST(j)=(ij 1i,jm)(2)i,j中,至多有一个能推导出;(3)若j*,则FIRST(i)FOLLOW(A)=(i=1,2,m ij)注注:条件条件(2)(2)可省略可省略.即即(1)(1)(2)(2)我们把满足上述条件的文法称为我们把满足上述条件的文法称为LL(1)LL(1)LL(1)LL(1)文法文法文法文法 递归下降分析法递归下降分析法(recursive descent method)的原理是,对于文法的每个非终结符,根据其各候选式的结构,为其建立一个递归的子程序(函数),用于识别该非终结符所表示的语法范畴.例如,产生式E

14、+TE,相应的子程序(函数)为expr_prime()if(match(PLUS)advance();term();expr_prime();程序中,函数match()的功能是,以其实参与当前正扫描的符号进行匹配,若成功则返回1,否则返回0;advance()是读下一单词函数,将所读单词赋给变量变量lookahead;term()函数是与非终结符T相对应的子程序.对于文法的每个非终结符,都建立了子程序后,这组子程序组成了所需的自顶向下语法分析程序.注意注意,由于文法的递归性,子程序一定有递归递归.因此,只能使用允许递归的程序设计语言编写.由于程序有递归,通常,上述方法也称为递归子程序法递归子程

15、序法什么是LL(1)文法一个上下文无关文法若满足下列条件(1)文法不含有左递归;(2)文法的每个非终结符A的各个产生式的first集和Follow集不相交，即满足first(A)follow(A)则称此文法为LL(1)文法。第一个L表示它从左到右扫描输入串，第二个L表示采用最左推导，1表示分析时每次直接推导只需向前察看一个字符。LL（1）分析方法）分析方法预测分析法的分析器由一张预测分析表预测分析法的分析器由一张预测分析表(LL(1)(LL(1)分析表分析表),),一个控制程序一个控制程序(表驱动程表驱动程序序)及一分析栈组成及一分析栈组成控制程序分析表分析表XYZ#分析栈a1 a2 ai a

16、n#输入4 输入是待分析的符号串（单词流），输入是待分析的符号串（单词流），以以#结尾。结尾。4分析表是一二维数组，分析表是一二维数组，M:VNM:VN(VT(VT#)#)(P(P ERR),ERR),MA,aMA,a的值按下述规则确定的值按下述规则确定:对于每个对于每个产生式产生式A A1|1|2|2|m m4(1)(1)若若a a FIRST(FIRST(i),i),则置则置MA,a=“AMA,a=“Ai”;i”;4(2)(2)FIRST(FIRST(i),ai),a FOLLOW(A),FOLLOW(A),置置MA.a=“AMA.a=“Ai”,i”,4(3)(3)除上述两种情况外除上述两

17、种情况外,其它元素均填其它元素均填“ERR”.ERR”.4分析表元素的含义分析表元素的含义:指明当前应用何产生式进指明当前应用何产生式进行推导行推导,或指明输入串出现错误或指明输入串出现错误一、分析器分析器的工作原理的工作原理分析器对输入串的分析在控制程序的控制下进行，步骤如下：分析器对输入串的分析在控制程序的控制下进行，步骤如下：#Sa1 a2 an#2.设在分析的某时刻的分析格局为设在分析的某时刻的分析格局为#X1 X2 Xm-1 Xmai ai+1 an#c此时此时,根据当前栈顶符号根据当前栈顶符号Xm的不同情况的不同情况,分别作如下处理分别作如下处理:(1)Xm VT,且且Xm=ai,

18、则匹配则匹配,将将Xm 顶出栈顶出栈,输入指针输入指针+;否则否则(Xm ai),出错出错;(2)Xm VN 查表查表MXm,ai,若若MXm,ai=“ERR”,则出错则出错;若若MXm,ai=“Xm Y1Y2Yk”,则将则将Xm 出栈出栈,Y1Y2Yk 按逆序压入栈按逆序压入栈,得到格局得到格局1.初始化初始化.首先将首先将#及开始符及开始符S压入压入栈栈,各指针置初值各指针置初值.此时此时,格局为格局为#X1 X2 Xm-1YkYk-1.Y1ai ai+1 an#(3)若若X Xmm=a=ai i=#,=#,则表明输入串已完全得到匹配则表明输入串已完全得到匹配,分析成功分析成功分析成功分析

19、成功,结束结束.预测分析法预测分析法实例考虑文法考虑文法(4.1).各各个个 FIRST集与集与FOLLOW集如右表所集如右表所示示文法文法(4.1)相应的相应的LL(1)LL(1)分析表分析表分析表分析表见右见右注注:在分析表中我们在分析表中我们有意省略了左侧的有意省略了左侧的非终结符非终结符(why?why?).).在在实际的表存储时实际的表存储时,还还可用产生式编号表可用产生式编号表示示对对i+i*i进行预测分析的过程进行预测分析的过程二、构造FIRST集的算法对于对于G G中的每个文法符号中的每个文法符号X X,为求为求FIRST(X),FIRST(X),反复应用如下规则反复应用如下规

20、则,直到集合不再增大直到集合不再增大:(1)if (X X V VT T)FIRST(X)=X;(2)if(X X V VNN)if(XaP aVT)aFIRST(X);if(XP)FIRST(X);(3)if(X XY Y1 1Y Y2 2YYk k P P)if(Y1 1VN)FIRST(Y1 1)-FIRST(X);for(1 j k-1)if(YjVNFIRST(Yj j)FIRST(Yj)-FIRST(X);if(for(1 j k):FIRST(Yj)FIRST(X);V*,V*,=X1X2Xn,=X1X2Xn,求求FIRST(FIRST()类似于求类似于求X XY1Y2YkY1Y

21、2Yk,略略.构造构造FOLLOW集的算法集的算法FOLLOW:VFOLLOW:VFOLLOW:VFOLLOW:VN N N NV V V VT T T T#,反复使用如下规则,直到不再增大:1.#1.#FOLLOW(S);FOLLOW(S);2.if(A2.if(ABBP)FIRST(P)FIRST()-)-FOLLOW(B);FOLLOW(B);3.if(A3.if(ABB P)P)(A(ABB FIRST(FIRST()FOLLOW(A)FOLLOW(A)FOLLOW(B);FOLLOW(B);算法的证明:对于1.,由定义直接得到;对于2.,由于A是有用符号,则必存在含A的句型:S S*

22、A A B B BaBa (a (a FIRST(FIRST(););对于3.,类似地,S S*A A BB ,显然,FIRST(FIRST()FOLLOW(A),FOLLOW(A),并且,FIRST(FIRST()FOLLOW(B).FOLLOW(B).证毕/构造构造FIRST集和集和FOLLOW集的例子集的例子我们以文法我们以文法(4.1)(4.1)为例为例,计算相应的计算相应的FIRSTFIRST集和集和FOLLOWFOLLOW集集.1.求所有VNVN符的FIRSTFIRST集.利用规则规则(2),有 FIRST(MM)=*,/*,/,FIRST(A A)=+,-+,-FIRST(F F

23、)=(,i(,i;再利用规则规则(3),有FIRST(TT)=FIRST(MM)=*,/,*,/,FIRST(T T)=FIRST(F F)=(,i(,i,FIRST(EE)=FIRST(A A)=+,-,+,-,FIRST(E E)=FIRST(T T)=(,i(,i2.求FOLLOWFOLLOW集(1)由规则规则(1),#FOLLOW(E E),再由产生式F F(E),(E),)FOLLOW(E E),从而,FOLLOW(E E)=),#),#(2)由规则规则(3)及产生式E ETETE可知FOLLOW(E E)FOLLOW(EE),即有 FOLLOW(E)=),#),#(3)(3)由规则

24、由规则(2)(2)及产生式及产生式EEEEATEATEATEATE有有 FIRST(E)-FIRST(E)-FIRST(E)-FIRST(E)-FOLLOW(T);FOLLOW(T);FOLLOW(T);FOLLOW(T);再再由规则由规则(3)(3)及及E E E ETETETETE和和EEEE*有有 FOLLOW(FOLLOW(E E E E)FOLLOW(FOLLOW(T T T T)即即FOLLOW(FOLLOW(T T T T)=)=+,-+,-+,-+,-),#),#),#),#=+,-,),#+,-,),#+,-,),#+,-,),#(4)(4)由规则由规则(3)(3)有有T T

25、 T TFTFTFTFT有有FOLLOW(FOLLOW(T T T T)FOLLOW(FOLLOW(TTTT),),即即FOLLOW(FOLLOW(TTTT)=)=+,-,),#+,-,),#+,-,),#+,-,),#(5)(5)由规则由规则(2)(2)及及TTTTMFTMFTMFTMFT,有有 FIRST(FIRST(TTTT)-)-FOLLOW(FOLLOW(F F F F),),再由规则再由规则(3)(3)及及TTTTMFTMFTMFTMFT和和TTTT*,有有FOLLOW(FOLLOW(TTTT)FOLLOW(FOLLOW(F F F F),),从而从而,FOLLOW(FOLLOW(

26、F F F F)=)=*,/*,/*,/*,/+,-,),#+,-,),#+,-,),#+,-,),#=+,-,*,/,),#+,-,*,/,),#+,-,*,/,),#+,-,*,/,),#(6)(6)由规则由规则(2)(2)及及EEEEATE,T ATE,T ATE,T ATE,T MFTMFTMFTMFT,有有 FIRST(FIRST(T T T T)FOLLOW(FOLLOW(A A A A),),FIRST(FIRST(F F F F)FOLLOW(FOLLOW(M M M M),),故有故有 FOLLOW(FOLLOW(A A A A)=)=(,i(,i(,i(,i,FOLLOW(

27、,FOLLOW(M M M M)=)=(,i(,i(,i(,i.最终所得的最终所得的FIRSTFIRSTFIRSTFIRST集和集和FOLLOWFOLLOWFOLLOWFOLLOW集结果集结果,见见P119 P119 求求FIRST,FOLLOW集例子集例子(续续)三、预测分析表预测分析表的构造对已给的LL(1)文法,在得到各文法符号的FIRSTFIRST集和FOLLOWFOLLOW集之后,就可容易地构造出预测分析表预测分析表预测分析表预测分析表(也称LL(1)LL(1)分析表分析表分析表分析表).在实际的表存储结构中,矩阵中每个元素并非真正存储的是产生式产生式,而是其右部的逆序右部的逆序(也

28、可以是产生式序号序号),这样便于分析时使用,并节省了内存空间.造表的算法造表的算法 在A VN所在行,a VT所在列,MA,a的填写方法如下:(1)if(AP and aFIRST()MA,a=A;(2)if(*(FIRST()and aFOLLOW(A)MA,a=A;(3)Otherwise,MA,a=ERR.文法文法(4.1)的LL(1)分析表分析表见P119表表4-24.1.5 某些非LL(1)文法的改造对于对于LL(1)LL(1)文法而言文法而言,我们总能构造出相应的预测分析表我们总能构造出相应的预测分析表,且表中决且表中决不会含有多重定义的元素不会含有多重定义的元素.然而对于然而对于

29、非非LL(1)LL(1)文法文法,它们不满足它们不满足LL(1)LL(1)文法文法的条件的条件,尽管仍可为其尽管仍可为其建立预测分析表建立预测分析表,但表中必然会出现但表中必然会出现多重定义多重定义的的元素元素(why?)why?)例如例如,文法文法GS:SabB ASC|BAA|BAbA CB|FIRST(S)=a FIRST(A)=a,b,FIRST(B)=a,b FIRST(C)=a,b,cFOLLOW(S)=FOLLOW(A)=FOLLOW(B)=FOLLOW(C)=a,b,c,#,由造表规则,有 MA,a=ASC,A,同理,MB,b=ABAA,A.可见可见非非LL(1)LL(1)文法

30、文法所造之表中所造之表中,必有冲突元素必有冲突元素.事实上事实上,是否有冲突是否有冲突元素也是判别一文法是否是元素也是判别一文法是否是LL(1)LL(1)文法文法的方法之一的方法之一.对于某些对于某些非非LL(1)LL(1)文法文法而言而言,通过通过消除左递归消除左递归,反复反复提取左因子提取左因子等方等方法法,有时是可以将其改造成有时是可以将其改造成LL(1)LL(1)文法文法的的.某些非LL(1)文法的改造(续)提取左因子提取左因子提取左因子提取左因子当文法中含有形如 A1|2|m 的产生式时,可将其改写为:AA A1|2|m 若诸候选式1,2,m 中的一部分仍含有左因子,则再进行提取工作

31、,如此等等.这样,就可能可能得到一个LL(1)文法.例如,EE+T|T T(E)|a(E)|a经改造后可得文法ETE E+TE|TaT|(E)T(E)|这是一个LL(1)文法.应当指出,并非并非所有的文法都能改造为LL(1)文法.例如,文法GS:SAU|BRAaAU|bBaBR|bUcRd 文法中S的两个候选式AU及BR的FIRST集相交,G是非LL(1)的.为提取左因子,先将S产生式中的A,B用其右部替换,得:SaAUU|bU|aBRR|bR,经提取左因子,得S S aS|bS”aS|bS”SSAUU|BRR S”AUU|BRR S”U|R AU|R A 显然它仍不是LL(1)文法关于LL(

32、1)的一些结论能由LL(1)文法产生的语言称为LL(1)语言.它们已被证明具有许多重要特性,主要有:(1)任何LL(1)文法都是无二义性的无二义性的;(2)左递归文法左递归文法是非LL(1)的;(3)存在一种算法,它能判定任意文法是否为判定任意文法是否为LL(1)的的;(4)存在一种算法,它能判定任意两个判定任意两个LL(1)文法是否文法是否等价等价;(5)CFLCFL是否是LL(1)语言是不可判定不可判定的;(6)非LL(1)语言是存在的.若在分析过程中,每步向前扫描k个符号来确定选用的产生式,此分析方法称为是LL(k)分析.自底向上自底向上的语法分析的语法分析自底向上自底向上自底向上自底向

33、上()的语法分析是从给定的符号串出发,试图逐步将它们归约为文法的开始符号.的语法分析的语法分析的语法分析的语法分析采用的是最左最左最左最左(规范规范规范规范)归约归约归约归约本节中介绍两种 分析分析分析分析方法,即优先分析优先分析法和LRLR分分析法析法;分析分析分析分析也需要一个分析栈用于存放分析过程中所得的文法符号,开始时,先将#入栈,然后逐步地将输入符号移进栈,当句柄句柄句柄句柄在栈顶形成时,则进行归归归归约约约约,否则移进移进移进移进下一符号.在分析的每一步,分析动作分析动作分析动作分析动作都是由当前栈里的内容和扫描到的符号确定的当前栈里的内容和扫描到的符号确定的当前栈里的内容和扫描到

34、的符号确定的当前栈里的内容和扫描到的符号确定的.分析动作有:移进移进移进移进,归约归约归约归约,报错报错报错报错,接受接受接受接受.文法文法:SAB|c AbA|a BaSb|c,输入为输入为bbaacb自底向上自底向上语法分析的例子语法分析的例子关于自底向上分析关于自底向上分析分析过程是最左归约最左归约最左归约最左归约的(规范的规范的规范的规范的);注意,在分析过程中,一旦句柄句柄句柄句柄在栈顶形成,则立即归约归约;有时栈顶栈顶栈顶栈顶出现了某产生式的右部产生式的右部,但它不一定不一定不一定不一定是句句句句柄柄柄柄(如前例中第七步,栈顶的a不是句柄);从分析过程可容易地建立一棵语法树语法树语

35、法树语法树,可用作语法语法语法语法分析的输出分析的输出分析的输出分析的输出.建立树的方法见P125.算符优先分析法算符优先分析是一种自底向上的分析方法算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄。算符优先分析算符文法定义算符文法定义:一个上下无关文法G,如果它的任一个产生式的右部都不含有两个相邻的非终结符，即不含有P.QR.(P,Q,R属于非终结符),则G是一个算符文法算符文法 相邻：若S ab或S aQb，则称a，b相邻算符优先关系：其中算符优先关系：其中A,B属于VN，a,b属于VT1.a

36、 b：当且仅当G中有P.ab.或P.aBb.则称a,b同等规约（同一句柄里（同一句柄里的符号）的符号）2.a b：当且仅当G中有P.aA.的产生式,且A b.或A Bb.则称a后于b规约（寻找句柄的头）（寻找句柄的头）3.a b：当且仅当G 中有P.Ab.的产生式,且A=.a或A=.aB则称a先于b规约（寻找句柄的尾）（寻找句柄的尾）算符优先文法的定义+以上三种关系也可由下列语法树来说明：(a)中为或为B，这样a,b在同一句柄中同时归约所以优先级相同。(b)中为或为C。a,b不在同一句柄中，b先归约，所以a的优先级低于b。(c)为或为A，a、b不在同一句柄中，a先归约，所以a的优先性大于b。例

37、：EE+E|E*E|(E)|i 证明不是OPG文法。因为：EE+E，EE*E 则有+*又因为：EE*E,EE+E 则有+*所以不是算符优先文法。3.算符优先文法算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有 ,中的一种成立,则G为一算符优先文法符优先文法。算符优先关系表的构造 用表格(矩阵)形式来表示各终结符号的优先关系，这种表称为优先表(矩阵)。在优先表中，空白部分是一种错误关系相同的终结符之间的优先关系不一定是如果有a b,不一定有b a(不具传递性)，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。a,b之间未必有优先关系(,)构造

38、关系表前我们先介绍FIRSTVT和LASTVTFIRSTVT集和LASTVT集 定义：设文法GS(VN，VT，P，S)不含产生式，且任何产生式右部都不含有两个相继（并列）的非终结符，AVN，则FIRSTVT(A)=a|Aa或AQa，aVT，Q VNLASTVT(A)=a|Aa或 AaQ，aVT，Q VNFIRSTVT集和LASTVT集FIRSTVT集和LASTVT集可采用以下算法求得：（1）求FIRSTVT(A)集的算法令FIRSTVT(A)若 文 法 中 有 形 如 Aa或 AQa的 规 则，则aFIRSTVT(A)；若 文 法 中 有 形 如 AQ的 规 则，则 FIRSTVT(Q)FIR

39、STVT(A)。（2）求LASTVT(A)集的算法令LASTVT(A)若 文 法 中 有 形 如 Aa或 AaQ的 规 则，则aLASTVT(A)；若 文 法 中 有 形 如 AQ的 规 则，则 FIRSTVT(Q)LASTVT(A)。1、构造每个非终结符的FIRSTVT和LASTVT集。2、1）若产生式右部有.aA.的形式,则对于每个bFIRSTVT(A)都有a b(优先集)2）若产生式右部有.Ab的形式,则对于每个aLASTVT(A)集,都有a b 3）若产生是形如：Aab 或 AaBb形式，则有a b3、1)#FIRSTVT(S)2)LASTVT(S)#3)#算符优先关系表的构造 Fir

40、stVTLastVTE+,*,(,i+,*,),iT*,(,i*,),iF(,i),iE T|E+T T F|T*F F i|(E)+*()i#+*()i#E+T|TT-T*F|FF-(E)|i句型T+T*F+i的语法树如图：EET+E+TFTT*FPi根据语法树可知：句型#T+T*F+i#的短语短语有：T 相对非终结符E的短语T*F 相对非终结符T的短语T+T*F 相对非终结符E的短语i 相对非终结符P、F、T的短语T+T*F+i 相对非终结符E的短语根据素短语素短语的定义可知：i和T*F为素短语。其中：T+T*F (含T*F素短语)、T+T*F+i(含T*F素短语)和 T(不含终结符)也不

41、是素短语T*F为最左素短语最左素短语。3.算符优先分析过程：(根据最左素短语的定义)句型的一般形式:#N1a1N2a2.NnanNn+1#(ai为终结符,Ni为可有可无的非终结符)从左向右扫描各符号,依次查看算符优先矩阵,直至找到满足ai ai+1的终结符为止,一直移进.再从ai开始往左扫描,直至找到满足关系aj-1 aj的终结符为止,进行归约。此时,形如:Njaj Nj+1aj+1.NiaiNi+1的子串即为最左素短语，应被归约。分析过程的结束：分析栈中为#S，输入串为#把#入栈,读一符号i,因为#+,所以归约:F-i因#+,所以+入栈 因+*,所以归约:F-i因+*,所以*入栈 因*#,所

42、以归约:F-i因*#,所以归约:T-F*F因+#,所以归约:E-T+F分析成功求i+i*i的算符优先分析过程栈栈 输入缓冲区输入缓冲区#i+i*i#i+i*i#i +i*i#+i*i#F +i*i#+i*i#F+i*i#i*i#F+i *i#*i#F+F *i#*i#F+F*i#i#F+F*i#F+F*F#F+T#E#算符优先分析的算法算符优先分析的算法(续续)关于算符优先分析的若干结论关于算符优先分析的若干结论按算符优先分析算符优先分析算符优先分析算符优先分析所确定的归约子串恰好是当前句型的最左素短最左素短最左素短最左素短语语语语(证明略);算符优先分析算符优先分析算符优先分析算符优先分析是自底向上自底向上自底向上自底向上的,但并不是规范归约规范归约,因此,每步所得句型不是规范句型规范句型;由于分析过程中只考虑两个相邻VVT T符之间的关系,VVNN符无关紧要,所以归约所得的VVNN符可任意命名;分析所得的语法树语法树不是真正意义上的语法树语法树,而是其分枝构架分枝构架分枝构架分枝构架,它省略了单产生式的归约过程;分析算法可容易地形式化:引入一分析栈,先将#压入栈,分析时总是用栈顶符栈顶符与当前扫描符当前扫描符进行比较,遇时回头查找最左素短语最左素短语最左素短语最左素短语,归约之;若两个符号无关系,则报错报错.若栈顶为开始符S S,扫描符为#,成功成功.