《编译原理教程》课后习题答案第三章语法分析.ppt

资源描述

《《编译原理教程》课后习题答案第三章语法分析.ppt》由会员分享，可在线阅读，更多相关《《编译原理教程》课后习题答案第三章语法分析.ppt（182页珍藏版）》请在三一办公上搜索。

1、第三章语法分析,3.1 完成下列选择题：(1)文法G：SxSx|y所识别的语言是。a.xyx b.(xyx)*c.xnyxn(n0)d.x*yx*(2)如果文法G是无二义的，则它的任何句子。a.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导和最右推导必定相同d.可能存在两个不同的最左推导，但它们对应的语法树相同,(3)采用自上而下分析，必须。a.消除左递归 b.消除右递归c.消除回溯 d.提取公共左因子(4)设a、b、c是文法的终结符，且满足优先关系ab和bc，则。a.必有ac b.必有cac.必有ba d.ac都不一定成立,(5)在规范归约中，

2、用来刻画可归约串。a.直接短语 b.句柄 c.最左素短语 d.素短语(6)若a为终结符，则Aa为项目。a.归约 b.移进 c.接受 d.待约(7)若项目集Ik含有A，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“A”动作的一定是。a.LALR文法 b.LR(0)文法 c.LR(1)文法 d.SLR(1)文法,(8)同心集合并有可能产生新的冲突。a.归约 b.“移进”/“移进”c.“移进”/“归约”d.“归约”/“归约”【解答】(1)c(2)a(3)c(4)d(5)b(6)b(7)d(8)d3.2 令文法GN为 GN:ND|ND D0|1|2|3|4|5|6|7|8|9(

3、1)GN的语言L(GN)是什么?(2)给出句子0127、34和568的最左推导和最右推导。,【解答】(1)GN的语言L(GN)是非负整数。(2)最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127 NNDN4D434 NNDN8ND8N68D68568,3.3 已知文法GS为SaSb|Sb|b，试证明文法GS为二义文法。【解答】由文法GS：SaSb|Sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。,图3-1 句子aabbbb对应的两棵不同语法

4、树,因此，文法GS为二义文法(对句子abbb也可画出两棵不同语法树)。3.4 已知文法GS为SSaS|，试证明文法GS为二义文法。【解答】由文法GS：SSaS|，句子aa的语法树如图3-2所示。,图3-2 句子aa对应的两棵不同的语法树,由图3-2可知，文法GS为二义文法。3.5 按指定类型，给出语言的文法。(1)L=aibj|ji0的上下文无关文法；(2)字母表=a,b上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；(3)由相同个数a和b组成句子的无二义文法。【解答】(1)由L=aibj|ji0知，所求该语言对应的上下文无关文法首先应有SaSb型产生式，以保证b的个数不少于a的个数；

7、dcc和aAcbBdcc的语法树如图3-4的(a)、(b)所示。,图3-4 习题3.6的语法树(a)aAaBcbbdcc;(b)aAcbBdcc,对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足AAaB右部的子串；与树(a)对照，AaB的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至

8、右找到第一个子串c，这是满足AC右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。,(2)句子acabcbbdcc的最左推导如下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc3.7 对于文法GS:S(L)|aS|aLL,S|S(1)画出句型(S,(a)的语法树；(2)写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。【解答】(1)句型(S,(a)的语法树如图3-5所示。,图3-5 句型(S,(a)的语法树,(2)由图3-5可知：短语：

9、S、a、(a)、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图3-5中相邻终结符之间的优先关系求得，即：#(，(a)#因此，素短语为a。,3.8 下述文法描述了C语言整数变量的声明语句：GD:DTLTint|long|shortLid|L,id(1)改造上述文法，使其接受相同的输入序列，但文法是右递归的；(2)分别用上述文法GD和改造后的文法GD为输入序列int a,b,c构造分析树。,【解答】(1)消除左递归后，文法GD如下：DTLTint|long|shortLidL,图3-6 两种文法为int a,b,c构造的分析树(a)文法G(D)；(b)文法G(D),3.

11、ookahead=+)match(+);S();,void T()S();T();void T()if(lookahead=,)match(,);S();T();,3.10 已知文法GA:AaABl|aBBb|d(1)试给出与GA等价的LL(1)文法GA；(2)构造GA的LL(1)分析表；(3)给出输入串aadl#的分析过程。【解答】(1)文法GA存在左递归和回溯，故其不是LL(1)文法。要将GA改造为LL(1)文法，首先要消除文法的左递归，即将形如PP|的产生式改造为PPPP|,来消除左递归。由此，将产生式BBb|d改造为BdBBbB|其次，应通过提取公共左因子的方法来消除GA中的回溯，即将

12、产生式AaABl|a改造为AaAAABl|最后得到改造后的文法为GA：AaAAABl|BdBBbB|,求得：FIRST(A)=a FIRST(A)=a,FIRST(B)=d FIRST(B)=b,对文法开始符号A，有FOLLOW(A)=#。由AABl得FIRST(B)FOLLOW(A)，即FOLLOW(A)=#,d；由AABl得FIRST(l)FOLLOW(B)，即FOLLOW(B)=l；由AaA得FOLLOW(A)FOLLOW(A)，即FOLLOW(A)=#,d；,由BdB得FOLLOW(B)FOLLOW(B)，即FOLLOW(B)=l。对AABl来说，FIRST(A)FOLLOW(A)=a

13、#,d=，所以文法GA为所求等价的LL(1)文法。,(2)构造预测分析表的方法如下：对文法GA的每个产生式A执行、步。对每个终结符aFIRST(A)，把A加入到MA,a中，其中为含有首字符a的候选式或为唯一的候选式。若FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A加入到MA,b中。把所有无定义的MA,a标记上“出错”。由此得到GA的预测分析表，见表3-1。,表3-1 预测分析表,(3)输入串aadl的分析过程见表3-2。,表3-2 输入串aadl的分析过程,3.11 将下述文法改造为LL(1)文法：GV:VN|NEEV|V+ENi【解答】LL(1)文法的基本条件是不含左递归和

14、回溯(公共左因子)，而文法GV中含有回溯，所以先消除回溯，得到文法GV：G V：VNVV|EEVEE|+ENi,一个LL(1)文法的充要条件是：对每一个终结符A的任何两个不同产生式A|有下面的条件成立：(1)FIRST()FIRST()=；(2)假若，则有FIRST()FOLLOW(A)=。即求出GV的FIRSTVT和LASTVT集如下：FIRST(N)=FIRST(V)=FIRST(E)=iFIRST(V)=,FIRST(E)=+,FOLLOW(V)=#,由VE得FIRST()FOLLOW(E)，即FOLLOW(E)=；由VNV得FIRST(V)FOLLOW(N)，即FOLLOW(N)=；由

15、EVE得FIRST(E)FOLLOW(V)，即FOLLOW(V)=#,+；由VNV得FOLLOW(V)FOLLOW(V)，即FOLLOW(V)=#,+；由VNV，且V得FOLLOW(V)FOLLOW(N)，即FOLLOW(N)=,#,+；由EVE得FOLLOW(E)FOLLOW(E)，即FOLLOW(E)=；,则，对V|E有：FIRST()FIRST(=；对E|+E有：FIRST()FIRST(+)=；对V|E有：FIRST()FOLLOW(V)=#,+=；对E|+E有：FIRST(+)FOLLOW(E)=+=。故文法GV为LL(1)文法。,3.12 对文法GE:EE+T|T TT*P|P P

16、i(1)构造该文法的优先关系表(不考虑语句括号#)，并指出此文法是否为算符优先文法；(2)构造文法G的优先函数。,【解答】FIRSTVT集构造方法：由Pa或PQa，则aFIRSTVT(P)。若aFIRSTVT(Q)，且PQ，则aFIRSTVT(P)，也即FIRSTVT(Q)FIRSTVT(P)。由得：由EE+得FIRSTVT(E)=+；由TT*得FIRSTVT(T)=*；由Pi得FIRSTVT(P)=i。由得：由TP得FIRSTVT(P)FIRSTVT(T)，即FIRSTVT(T)=*，i；由ET得FIRSTVT(T)FIRSTVT(E)，即FIRSTVT(T)=+，*，i。,LASTVT集构

17、造方法：由Pa或PaQ,则aLASTVT(P)。若aLASTVT(Q)，且PQ，则aLASTVT(P)，也即LASTVT(Q)LASTVT(P)。由得：E+T，得LASTVT(E)=+；T*P，得LASTVT(T)=*；Pi，得LASTVT(P)=i。由得：由TP得LASTVT(P)LASTVT(T)，即LASTVT(T)=*，i；由ET得LASTVT(T)LASTVT(E)，即LASTVT(E)=+，*，i。,优先关系表构造方法：对Pab或PaQb，有ab；对PaR而bFIRSTVT(R)，有ab；对PRb而aLASTVT(R)，有ab。解之无。由得：E+T，即+FIRSTVT(T)，有+*

18、，+i；T*P，即*FIRSTVT(P)，有*i。由得：EE+，即LASTVT(E)+，有+，*+，i+；TT*，即LASTVT(T)*，有*，i*。,得到优先关系表见表3-3。由于该文法的任何产生式的右部都不含两个相继并列的非终结符，故属算符文法，且该文法中的任何终结符对(见优先关系表)至多满足、和三种关系之一，因而是算符优先文法。,表3-3 习题3.12的优先关系表,用关系图构造优先函数的方法是：对所有终结符a用有下脚标的fa、ga为结点名画出全部终结符所对应的结点。若存在优先关系ab或ab，则画一条从fa到ga的有向弧；若ab或ab，则画一条从g b到f a的有向弧。最后，对每个结点都赋

19、一个数，此数等于从该结点出发所能到达的结点(包括出发结点)的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)。用关系图法构造本题的优先函数，如图3-7所示。得到优先函数见表3-4。,图3-7 习题3.12关系图构造,表3-4 习题3.12的优先函数表,该优先函数表经检查与优先关系表没有矛盾，故为所求优先函数。也可由定义直接构造优先函数，其方法是：对每个终结符a，令f(a)=g(a)=1；如果ab，而f(a)g(b)，则令f(a)=g(b)+1；如果ab，而f(a)g(b)，则令g(b)=f(a)+1；如果ab，而f(a)g(b)，则令minf(a),g(b)=maxf(a),g(b)。

20、重复上述过程，直到每个终结符的函数值不再变化为止。如果有一个函数值大于2n(n为终结符个数)，则不存在优先函数。优先函数的计算过程如表3-5所示。,表3-5 优先函数的计算过程表,计算最终收敛，并且计算得出的优先函数与关系图构造得出的优先函数是一样的。3.13 设有文法GS:Sa|b|(A)ASdA|S(1)构造算符优先关系表；(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；(3)给出输入串(adb)#的分析过程。,【解答】(1)先求文法GS的FIRSTVT集和LASTVT集：由Sa|b|(A)得FIRSTVT(S)=a,b,(；由ASd得FIRSTVT(A)=d，又由

21、AS得FIRSTVT(S)FIRSTVT(A)，即FIRSTVT(A)=d,a,b,(；由Sa|b|(A)得LASTVT(S)=a,b,)；,由AdA得LASTVT(A)=d，又由AS得LASTVT(S)LASTVT(A)，即LASTVT(A)=d,a,b,)。构造优先关系表方法如下：对Pab或PaQb，有ab；对PaR而bFIRSTVT(R)，有ab；对PRb而aFIRSTVT(R)，有ab。由此得到：由S(A)得()；由S(A得(FIRSTVT(A)，即(d,(a,(b,(；由AdA得dFIRSTVT(A)，即dd,da,db,d(；,由SA)得LASTVT(A)，即d),a),b),)；

22、由ASd得LASTVT(S)d，即ad,bd,)d；此外，由#S#得#；由#FIRSTVT(S)得#a,#b,#(；由LASTVT(S)#得a#,b#,)#。最后得到算符优先关系表，见表3-6。,表3-6 习题3.13的算符优先关系表,由表3-6可以看出，任何两个终结符之间至多只满足、三种优先关系之一，故GS为算符优先文法。(2)为求出句型(SdSdS)的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图3-8所示。,图3-8 句型(SdSdS)的语法树,由图3-8得到：短语：S，SdS，SdSdS，(SdSdS)简单短语(即直接短语)：S句柄(即最左直接短语)：S可以通过分析图3-8的

23、语法树来求素短语和最左素短语，即找出语法树中的所有相邻终结符(中间可有一个非终结符)之间的优先关系。确定优先关系的原则是：同层的优先关系为；不同层时，层次离树根远者优先级高，层次离树根近者优先级低(恰好验证了优先关系表的构造算法)；在句型两侧加上语句括号“#”，即#，则有#和#，由此我们得到句型(SdSdS)的优先关系如图3-9所示。,图3-9 句型(SdSdS)的优先关系,注意，句型中的素短语具有如下形式：aj-1ajaj+1aiai+1 而最左素短语就是该句型中所找到的最左边的那个素短语，即最左素短语必须具备三个条件：至少包含一个终结符(是否包含非终结符则按短语的要求确定)；除自身外不得包

24、含其他素短语(最小性)；在句型中具有最左性。,因此，由图3-9得到SdS为句型(SdSdS)的素短语，它同时也是该句型的最左素短语。(3)输入串(adb)#的分析过程见表3-7。,表3-7 输入串(adb)#的分析过程,为便于分析，同时给出了(adb)#的语法树，如图3-10所示。,图3-10(adb)的语法树,3.14 在算符优先分析法中，为什么要在找到最左素短语的尾时才返回来确定其对应的头，能否按扫描顺序先找到头后再找到对应的尾，为什么？【解答】设句型的一般形式为N1a1N2a2NnanNn+1。其中，每个ai都是终结符，而Ni则是可有可无的非终结符。对上述句型可以找出该句型中的所有素短语

25、，每个素短语都具有如下形式：aj-1ajaj+1aiai+1,如果某句型得到的优先关系如下：则当从左至右扫描到第一个“”时，再由此从右至左扫描到第一个“”时，它们之间(当然不包含第一个“”前一个终结符和第二个“”后一个终结符)即为最左素短语。,如果由左至右扫描到第一个“”，可以看出这并不一定是最左素短语的开头，因为由它开始并不一定是素短语(在其内部还可能包含其他更小的素短语)，所以，在算符优先分析算法中，只有先找到最左素短语的尾(即“”)，才返回来确定与其对应的头(即“”)；而不能按扫描顺序先找到头然后再找到对应的尾。3.15 试证明在算符文法中，任何句型都不包含两个相邻的非终结符。【解答】设

26、文法G=(VT,VN,S,)，其中VT是终结符集；VN是非终结符集；为产生式集合；S是开始符号。,对句型的推导长度n作如下归纳：(1)当n=1时，S，则存在一条产生式S属于，其中a(VTVN)*。由于文法是算符文法，所以中没有两个相邻非终结符，故归纳初始成立。(2)设n=k时结论成立，则对任何k+1步推导所产生的句型必为S其中，、(VTVN)*，UVN，而UV是一条产生式。,由归纳假设，U是非终结符，设=12n，=12m，其中i、j(VTVN)(1in-1,2jm)；但n和m必为位于U两侧的终结符。设V=V1V2Vr，由于它是算符文法的一个产生式右部候选式，因此V1V2Vr中不会有相邻的非终结

27、符出现。又因为nV1和Vr1中的n、1为终结符，也即在推导长度为k+1时所产生的句型12nV1V2Vr12m不会出现相邻的非终结符，故n=k+1时结论成立。显然，在或为空时结论也成立。,3.16 给出文法GS:SaSbPPbPcbQc QQaa(1)它是Chomsky哪一型文法？(2)它生成的语言是什么？(3)它是不是算符优先文法？请构造算符优先关系表证实之；(4)文法GS消除左递归、提取公共左因子后是不是LL(1)文法？请证实。,【解答】(1)根据Chomsky的定义，对任何形如A的产生式，有AVN，(VTVN)*时为2型文法。而文法GS恰好满足这一要求，故为Chomsky 2型文法。(2)

28、由文法GS可以看出：S推出串的形式是ai P bi(i0)，P推出串的形式是bjQcj(j1)，Q推出串的形式是ak(k1)。因此，文法GS生成的语言是L=aibjakcjbi|i0,j1,k1。,(3)求出文法GS的FIRSTVT集和LASTVT集：FIRSTVT(S)=a,b FIRSTVT(P)=bFIRSTVT(Q)=aLASTVT(S)=b,c LASTVT(P)=cLASTVT(Q)=a构造优先关系表如表3-8所示。由于在优先关系中同时出现了aa和aa以及bb和bb，故文法GS不是算符优先文法。,表3-8 优先关系表,(4)消除文法GS的左递归：SaSb|PPbPc|bQcQaQQ

29、aQ|提取公共左因子后得到文法GS:SaSb|PPbPPPc|QcQaQQaQ|,求每个非终结符的FIRST集和FOLLOW集如下：FIRST(S)=a,b FIRST(P)=bFIRST(P)=a,b FIRST(Q)=aFIRST(Q)=a,FOLLOW(S)=b,#FOLLOW(P)=b,c,#FOLLOW(P)=b,c,#FOLLOW(Q)=cFOLLOW(Q)=c,通过检查GS可以得到：每一个非终结符的所有候选式首符集两两不相交；存在形如A的产生式QaQ|，但有 FIRST(aQ)FOLLOW(Q)=ac=所以文法GS是LL(1)文法。,*3.17 LR分析器与优先关系分析器在识别句

30、柄时的主要异同是什么？【解答】如果SaA且有A，则称是句型相对于非终结符A的短语。特别的，如果有A，则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。规范归约是关于的一个最右推导的逆过程，因此，规范归约也称最左归约。请注意句柄的“最左”特征。,LR分析器用规范归约的方法寻找句柄，其基本思想是：在规范归约的过程中，一方面记住已经归约的字符串，即记住“历史”；另一方面根据所用的产生式推测未来可能碰到的输入字符串，即对未来进行“展望”。当一串貌似句柄的符号串呈现于栈顶时，则可根据历史、展望以及现实的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。事实上

31、，规范归约的中心问题恰恰是如何寻找或确定一个句型的句柄。给出了寻找句柄的不同算法也就给出了不同的规范归约方法，如LR(0)、SLR(1)、LR(1)以及LALR就是在归约方法上进行区别的。,算符优先分析不是规范归约，因为它只考虑了终结符之间的优先关系，而没有考虑非终结符之间的优先关系。此外，算符优先分析比规范归约要快得多，因为算符优先分析跳过了所有单非产生式所对应的归约步骤。这既是算符优先分析的优点，同时也是它的缺点，因为忽略非终结符在归约过程中的作用存在某种危险性，可能导致把本来不成句子的输入串误认为是句子，但这种缺陷容易从技术上加以弥补。为了区别于规范归约，算符优先分析中的“句柄”被称为最

32、左素短语。,3.18 什么是规范句型的活前缀？引进它的意义何在？【解答】在讨论LR分析器时，需要定义一个重要概念，这就是文法的规范句型的“活前缀”。字的前缀是指该字的任意首部，例如，字abc的前缀有、a、ab或abc。所谓活前缀，是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在其右边增添一些终结符号后，就可以使它成为一个规范句型。引入活前缀的意义在于它是构造LR(0)项目集规范族时必须用到的一个重要概念。,对于一个文法G，首先要构造一个NFA，它能识别G的所有活前缀，这个NFA的每个状态即为一个“项目”。文法G每一个产生式的右部添加一个圆点称为G的一个LR(0

33、)项目(简称项目)，可以使用这些项目状态构造一个NFA。我们能够把识别活前缀的NFA确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。构成识别一个文法活前缀的DFA项目集(状态)的全体称为这个文法的LR(0)项目集归范族。,3.19 试构造下述文法的SLR(1)分析表。GS:SbASB|bA AdSa|e BcAa|c【解答】首先将文法GS拓广为GS:GS：(0)SS(1)SbASB(2)SbA,(3)AdSa(4)Ae(5)BcAa(6)Bc构造文法GS的LR(0)项目集规范族如下：I0:SS I5:AeSbASB I6:SbASBSbA BcAa,I1:SS

34、 BcI2:SbASB I7:AdSaSbA I8:SbASBAdSa I9:BcAaAe Bc,I3:SbASB AdSaSbA AeSbASB I10:AdSaSbA I11:BcAaI4:AdSa I12:BcAaSbASBSbA文法GS的DFA如图3-11所示。,图3-11 文法GS的DFA,注意，在比较熟练的情况下，也可以不构造LR(0)项目集规范族而直接画出文法GS的DFA。由于I3和I9既含有移进项目又含有归约项目，故文法GS不是LR(0)文法。我们构造文法GS的FOLLOW集如下：(1)FOLLOW(S)=#；(2)由SAS得FIRST(S)FOLLOW(A)；即FOLLOW(

35、A)=b；由SSB得FIRST(B)FOLLOW(S)；即FOLLOW(S)=c；由ASa得FIRST(a)FOLLOW(S)；即FOLLOW(S)=a,c；,(3)由SS得FOLLOW(S)FOLLOW(S)，即FOLLOW(S)=a,c,#；由SB得FOLLOW(S)FOLLOW(B)，即FOLLOW(B)=a,c,#；由SA得FOLLOW(S)FOLLOW(A)，即FOLLOW(A)=a,b,c,#；对I3有：bFOLLOW(S)=ba,c,#=对I9有：d,eFOLLOW(B)=d,ea,c,#=故文法GS是SLR(1)文法。最后得到SLR(1)分析表见表3-9。,表3-9 SLR(1

36、)分析表,3.20 LR(0)、SLR(1)、LR(1)及LALR有何共同特征？它们的本质区别是什么？【解答】LR(0)、SLR(1)、LR(1)及LALR的共同特征是都用规范归约的方法寻找句柄，即LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。它们的本质区别是寻找句柄的方法不同。如果当前的栈顶状态为归约状态(即有形如A的项目属于栈顶状态)，则：(1)对LR(0)来说，无论现行输入符号是什么，都认为栈顶的符号串为句柄而进行归约。(2)对SLR(1)来说，则对现行输入符号加了一点限制，即该输入符号必须属于允许跟在句柄之后的字符范围内，才认为栈顶的符号串为句柄而进行归约。,(3)对

37、LR(1)来说，对现行输入符号的限制则更加严格，它在该输入符号跟在栈顶符号串后形成一个规范句型的前缀时，才认为栈顶的这个符号串为句柄，从而进行归约。由于要对不同的输入符号进行判断，因此LR(1)的状态数要比LR(0)、SLR(1)多。(4)LALR从本质上讲与LR(1)相同，只不过它把那些栈顶符号串相同但现行输入符号不同(即认为这个相同的栈顶符号串为同心)的判断合一(使状态数又减少到与LR(0)、SLR(1)一样)，只有输入符号跟在栈顶符号串后面形成一规范句型前缀时，才认为栈顶的这个符号串为句柄而进行归约。,对于同心的栈顶符号串而言，由于面对不同的输入符号将形成不同规范句型的前缀，这就给归约带

38、来一些困难；也即，当输入串有误时，LR(1)能够及时地发现错误，而LALR则可能还继续执行一些多余的归约动作，但决不会执行新的移进，即LALR能够像LR(1)一样准确地指出出错的地点。此外，LALR这种同心集的合并有可能带来新的“归约”/“归约”冲突。3.21 请指出图3-12中的LR分析表(a)、(b)、(c)分属LR(0)、SLR(1)和LR(1)中的哪一种，并说明理由。,【解答】我们知道，LR(0)、SLR(1)和LR(1)分析表构造的主要差别是构造算法(2)。其区别如下：(1)对LR(0)分析表来说，若项目A属于Ik(状态)，则对任何终结符a(或结束符#)，置ACTIONk,a为“用产

39、生式A进行归约(A为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则是每个归约状态所在的行全部填满“rj”；并且，同一行的“rj”其下标j相同，而不同行的“rj”其下标j是不一样的。,图3-12 LR分析表,(2)对SLR(1)分析表来说，若项目A属于Ik，则对任何输入符号a，仅当aFOLLOW(A)时置ACTIONk,a为“用产生式A进行归约(A为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则存在某个归约状态所在的行并不全部填满rj，并且不同行的“rj”其下标j不同。(3)对LR(1)来说，若项目A,a属于Ik(状态)，则置ACTIONk,a为“用产生式A进行归

40、约”，简记为“rj”。LR(1)是在SLR(1)状态(项目集)的基础上，通过状态分裂的办法(即分裂成更多的项目集)，使得LR分析器的每个状态能够确切地指出当后跟哪些终结符时才容许把归约为A。例如，假定A,a属于Ik(状态)，则置ACTIONk,a栏目为rj(A为第j个产生式)；而A,b属于Im(状态)，则同样置ACTIONm,b栏目为rj。表现在ACTION子表中，则在不同的行(即不同的状态)里有相同的rj存在。,因此，图3-12(a)的分析表为LR(1)分析表(在不同行有相同的r2存在)；图3-12(b)为LR(0)分析表(有rj的行是每行都填满了rj且同一行rj的j相同，不同行rj的j不同

41、)；而图3-12(c)为LR(0)分析表(存在并不全部填满rj的行，且不同行rj的j不同)。3.22 文法G(S)的产生式集为 S(EtSeS)|(EtS)|i=EE+EF|FF*Fi|i构造文法G的SLR(1)分析表，要求先画出相应的DFA。,【解答】将文法G拓广为文法GS：(0)SS(1)S(EtSeS)(2)S(EtS)(3)Si=E(4)E+EF(5)EF(6)F*Fi(7)Fi,列出LR(0)的所有项目：1.SS 9.S(EtSeS)17.Si=E 25.EF 2.SS 10.S(EtSeS)18.Si=E 26.EF 3.S(EtSeS)11.S(EtS)19.Si=E 27.F*

42、Fi4.S(EtSeS)12.S(EtS)20.Si=E 28.F*Fi,5.S(EtSeS)13.S(EtS)21.E+EF 29.F*Fi6.S(EtSeS)14.S(EtS)22.E+EF 30.F*Fi 7.S(EtSeS)15.S(EtS)23.E+EF 31.Fi 8.S(EtSeS)16.S(EtS)24.E+EF 32.Fi,用_CLOSURE方法构造文法GS的LR(0)项目集规范族：I0:SS I5:S(EtSeS)I13:E+EFS(EtSeS)S(EtS)E+EFS(EtS)I6:S(EtSeS)EFSi=E S(EtSeS)I14:E+EFI1:SS S(EtS)F*F

43、i,I2:S(EtSeS)Si=E FiS(EtS)I7:S(EtSeS)I15:E+EFE+EF I8:S(EtSeS)I16:EFEF I9:S(EtS)I17:F*FiI3:S(EtSeS)I10:Si=E F*FiS(EtS)I11:Si=E Fi,I4:S(EtSeS)E+EF I18:F*FiS(EtS)EF I19:F*FiS(EtSeS)I12:Si=E I20:FiS(EtS)Si=E文法GS的DFA如图3-13所示。,图3-13 习题3.22的DFA,构造SLR(1)分析表必须先求出所有形如“A”的FOLLOW(A)，即由FOLLOW集的构造方法求得GS的FOLLOW集如下

44、：(1)FOLLOW(S)=#；(2)由S(EtSeS)得FIRST(t)FOLLOW(E)，即FOLLOW(E)=t；FIRST(e)FOLLOW(S)，即FOLLOW(S)=e；FIRST()FOLLOW(S)，即FOLLOW(S)=e,)；由F*Fi得FIRST(i)FOLLOW(F)，即FOLLOW(F)=i；由E+EF得FIRST(F)/FOLLOW(E)，即FOLLOW(E)=t,i；,(3)由SS得FOLLOW(S)FOLLOW(S)，即FOLLOW(S)=e,),#；由Si=E得FOLLOW(S)FOLLOW(E)，即FOLLOW(E)=t,i,e,),#；由EF得FOLLOW

45、(E)FOLLOW(F)，即FOLLOW(F)=t,i,e,),#。最后得到SLR(1)分析表，见表3-10。,表3-10 习题3.22的SLR(1)分析表,3.23 为二义文法GT构造一个LR分析表(详细说明构造方法)。其中终结符“，”满足右结合性，终结符“；”满足左结合性，且“，”的优先级高于“；”的优先级。GT:TTAT|bTe|a A,|;【解答】首先将文法GT拓广为文法GS：(0)ST,TTAT(2)TbTe(3)Ta(4)A，(5)A；下面列出LR(0)的所有项目：1ST 5TTAT 9TbTe 13A，2ST 6TTAT 10TbTe 14A，,3TTAT 7TbTe 11Ta

46、15A;4TTAT 8TbTe 12Ta 16A;用_CLOSURE方法构造文法GS的LR(0)项目集规范族，并根据转换函数GO构造出文法GS的DFA，如图3-14所示。,图3-14 习题3.23中文法GS的DFA,已知文法GS为二义文法，故必然存在冲突。逐一检查各状态，得知I8存在“移进”/“归约”冲突(因为TTAT要求归约，而TTAT却要求移进)。在此，LR(0)已不能满足要求，因为LR(0)分析表中的ACTION子表在某归约状态下(即某一行)的所有栏目全被“rj”占满，但由于存在“移进”/“归约”冲突，即在此状态下，有些栏目应填为“Sj”(即归约)。为了减少冲突，最好采用SLR(1)、L

47、R(1)或LALR分析表。这里采用SLR(1)分析表。下面，构造文法GS中非终结符的FIRST集和FOLLOW集如下：FIRST(S)=FIRST(T)=a,b;FIRST(A)=“，”,“；”FOLLOW(S)=#；FOLLOW(T)=“，”,“；”,e,#；FOLLOW(A)=a,b,因为TTAT要求归约，而TTAT要求移进，即对T要求归约而对A要求移进，则有：FOLLOW(T)FIRST(A)=“，”,“；”,e,#“，”,“；”=“，”,“；”也即冲突字符为“，”和“；”。下面分析“，”与“；”的具体情况。因为“，”的优先级高且有右结合，故不论是“，”还是“；”，遇见“，”其后的“，”

48、一定移进；类似地，“；”优先级低且有左结合，则无论是“，”还是“；”，遇见其后的“；”一定归约。由此可得到SLR(1)分析表，见表3-11。,从分析表中可以看到，本应该对在状态8对应ACTION子表中的字符集e,“，”,“，”,#都执行用r1归约，但“，”和“；”存在“移进”/“归约”冲突，由于“，”的优先级高且有右结合，故对应ACTOIN8,“，”栏改为s5，即移进；由于“；”满足左结合性，即应归约，所以ACTION8,“，”栏仍为r1。,表3-11 习题3.23的SLR(1)分析表,注意，如果将条件改为“，”的优先级高且满足左结合，则将无法构造分析表。这是因为“，”在遇见其后的“，”时要求

49、归约；而“；”在遇见其后的“，”时则要求移进；这时ACTION8,“，”栏就无法确定是放“r1”还是放“s5”了。3.24 文法GT及其SLR(1)分析表(见表3-12)如下，给出串bibi的分析过程。GT:(1)TEbH(2)Ed(3)E(4)Hi(5)HHbi(6)H,表3-12 习题3.24的SLR(1)分析表,【解答】对句子bibi，先构造它的语法树，如图3-15所示。,图3-15 句子bibi的语法树,bibi的分析过程参考该语法树进行，见表3-13。,表3-13 bibi的分析过程,3.25 给出文法GS及图3-16所示的LR(1)项目集规范族中的0、1、2、3、4。GS:SS;B

50、|BBBaA|AAb(S),图3-16 习题3.25的部分项目集,【解答】首先求出GS中所有非终结符的FOLLOW集。已知FOLLOW(S)=#；则：由SS得FOLLOW(S)FOLLOW(S)，即FOLLOW(S)=#；由SS;得FOLLOW(S)=#,;；由AS)得FOLLOW(S)=#,;,)；由BBa得FOLLOW(B)=a；,由SB得FOLLOW(S)FOLLOW(B)，即FOLLOW(B)=#,;,),a；由BA得FOLLOW(B)FOLLOW(A)，即FOLLOW(A)=#,;,),a。LR(1)的闭包CLOSURE(I)可按如下方法构造：(1)I的任何项目都属于CLOSURE(

展开阅读全文