编译原理教程课后习题答案语法分析.pptx

《编译原理教程课后习题答案语法分析.pptx》由会员分享，可在线阅读，更多相关《编译原理教程课后习题答案语法分析.pptx（181页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、(5)在规范归约中，用 来刻画可归约串。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)文法第1页/共181页(8)同心集合并有可能产生新的 冲突。a.归约 b.“移进”/“移进”c.“移进”/“归约”d.“归约”/“归约”【解答】(1)c (2)a (3)c (4)d (5)b (6)b (7)d (8)d3.2 令文法GN为 GN:N

2、D|ND D0|1|2|3|4|5|6|7|8|9(1)GN的语言L(GN)是什么?(2)给出句子0127、34和568的最左推导和最右推导。第2页/共181页【解答】(1)GN的语言L(GN)是非负整数。(2)最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127 NNDN4D434 NNDN8ND8N68D68568第3页/共181页3.3 已知文法GS为SaSb|Sb|b，试证明文法GS为二义文法。【解答】由文法GS：SaSb|Sb|b，对句子aabb

3、bb可对应如图3-1所示的两棵语法树。第4页/共181页图3-1 句子aabbbb对应的两棵不同语法树 第5页/共181页因此，文法GS为二义文法(对句子abbb也可画出两棵不同语法树)。3.4 已知文法GS为SSaS|，试证明文法GS为二义文法。【解答】由文法GS：SSaS|，句子aa的语法树如图3-2所示。第6页/共181页图3-2 句子aa对应的两棵不同的语法树 第7页/共181页由图3-2可知，文法GS为二义文法。3.5 按指定类型，给出语言的文法。(1)L=aibj|ji0的上下文无关文法；(2)字母表=a,b上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；(3)由相同个数a

4、和b组成句子的无二义文法。【解答】(1)由L=aibj|ji0知，所求该语言对应的上下文无关文法首先应有SaSb型产生式，以保证b的个数不少于a的个数；其次，还需有SSb或Sb型的产生式，用以保证b的个数多于a的个数。因此，所求上下文无关文法GS为GS：SaSb|Sb|b第8页/共181页(2)为了构造字母表=a,b上同时只有奇数个a和奇数个b的所有串集合的正规式，我们画出如图3-3所示的DFA，即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B；而由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发经过奇数个a到达终态C。由图3-3可直接得到正规文法GS如下：GS

5、：SaA|bB AaS|bC|b BbS|aC|a CbA|aB|第9页/共181页图3-3 习题3.5的DFA第10页/共181页(3)我们用一个非终结符A代表一个a(即有Aa)，用一个非终结符B代表一个b(即有Bb)；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个B，出现一个b时则相应出现一个A。假定已推导出bA，如果下一步要推导出连续两个b时，则应有bAbbAA。也即为了保证b和A的个数一致，应有AbAA；同理有BaBB。此外，为了保证递归地推出所要求的ab串，应有SaBS和SbAS。由此得到无二义文法GS为 GS：SaBS|bAS|AbAA|a BaBB|b第11页/共18

6、1页3.6 有文法GS:SaAcB|BdAAaB|cBbScA|b(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)写出句子acabcbbdcc的最左推导过程。【解 答】(1)分 别 画 出 对 应 句 型 aAaBcbbdcc和aAcbBdcc的语法树如图3-4的(a)、(b)所示。第12页/共181页图3-4 习题3.6的语法树(a)aAaBcbbdcc;(b)aAcbBdcc 第13页/共181页对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。能否不画出语法树，而直接由定义(即在句

7、型中)寻找满足某个 产 生 式 的 候 选 式 这 样 一 个 最 左 子 串(即 句 柄)呢？例 如，对 句 型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足AAaB右部的子串；与树(a)对照，AaB的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至右找到第一个子串c，这是满足AC右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。第14页/共181页(2)句子acabcbbdcc的最左推导如下：SaAcBaAaBcBacaBcBacabcBacabcbScAa

8、cabcbBdcA acabcbbdcAacabcbbdcc3.7 对于文法GS:S(L)|aS|aLL,S|S(1)画出句型(S,(a)的语法树；(2)写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。【解答】(1)句型(S,(a)的语法树如图3-5所示。第15页/共181页图3-5 句型(S,(a)的语法树 第16页/共181页(2)由图3-5可知：短语：S、a、(a)、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图3-5中相邻终结符之间的优先关系求得，即：#(，(a)#因此，素短语为a。第17页/共181页3.8 下述文法描述了C语言整数变量的声明语

9、句：GD:DTLTint|long|shortLid|L,id(1)改造上述文法，使其接受相同的输入序列，但文法是右递归的；(2)分别用上述文法GD和改造后的文法GD为输入序列int a,b,c构造分析树。第18页/共181页【解答】(1)消除左递归后，文法GD如下：DTLTint|long|shortLidL第19页/共181页图3-6 两种文法为int a,b,c构造的分析树 (a)文法G(D)；(b)文法G(D)第20页/共181页3.9 考虑文法GS:S(T)|a+S|aTT,S|S消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。【解答】消除文法GS的左递

10、归：S(T)|a+S|aTSTT,ST|第21页/共181页提取公共左因子：S(T)|aSS+S|TSTT,ST|改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下：void match(token t)if(lookahead=t)lookahead=nexttoken;else error();第22页/共181页void S()if(lookahead=a)match(a);else if(lookahead=()match();T();第23页/共181页void S()if(lookahead=+)match(+);S();第24页/共181页void T()S();T();

11、void T()if(lookahead=,)match(,);S();T();第25页/共181页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|第26页/共181页来消除左递归。由此，将产生式BBb|d改造为BdBBbB|其次，应通过提取公共左因子的方法来消除GA中的回溯，即将产生式AaABl|a改造为AaAAABl|最后

12、得到改造后的文法为GA：AaAAABl|BdBBbB|第27页/共181页求得：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；第28页/共181页由BdB得FOLLOW(B)FOLLOW(B)，即FOLLOW(B)=l。对AABl来说，FIRST(A)FOLLOW(A)=a#,d=，

13、所以文法GA为所求等价的LL(1)文法。第29页/共181页(2)构造预测分析表的方法如下：对文法GA的每个产生式A执行、步。对每个终结符aFIRST(A)，把A加入到MA,a中，其中为含有首字符a的候选式或为唯一的候选式。若FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A加入到MA,b中。把所有无定义的MA,a标记上“出错”。由此得到GA的预测分析表，见表3-1。第30页/共181页表3-1 预测分析表 第31页/共181页(3)输入串aadl的分析过程见表3-2。第32页/共181页表3-2 输入串aadl的分析过程 第33页/共181页3.11 将下述文法改造为LL(1)

14、文法：GV:VN|NEEV|V+ENi【解答】LL(1)文法的基本条件是不含左递归和回溯(公共左因子)，而文法GV中含有回溯，所以先消除回溯，得到文法GV：G V：VNVV|EEVEE|+ENi第34页/共181页一个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)=#第35页/共181页由VE得FIRST

15、()FOLLOW(E)，即FOLLOW(E)=；由VNV得FIRST(V)FOLLOW(N)，即FOLLOW(N)=；由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)=；第36页/共181页则，对V|E有：FIRST()FIRST(=；对E|+E有：FIRST()FIRST(+)=；对V|E有：FIRST()FOLLOW(V)=#,

16、+=；对E|+E有：FIRST(+)FOLLOW(E)=+=。故文法GV为LL(1)文法。第37页/共181页3.12 对文法GE:EE+T|T TT*P|P Pi(1)构造该文法的优先关系表(不考虑语句括号#)，并指出此文法是否为算符优先文法；(2)构造文法G的优先函数。第38页/共181页【解答】FIRSTVT集构造方法：由Pa或PQa，则aFIRSTVT(P)。若aFIRSTVT(Q)，且PQ，则aFIRSTVT(P)，也即FIRSTVT(Q)FIRSTVT(P)。由得：由EE+得FIRSTVT(E)=+；由TT*得FIRSTVT(T)=*；由Pi得FIRSTVT(P)=i。由 得：由

17、TP得 FIRSTVT(P)FIRSTVT(T)，即 FIRSTVT(T)=*，i；由ET得FIRSTVT(T)FIRSTVT(E)，即FIRSTVT(T)=+，*，i。第39页/共181页LASTVT集构造方法：由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)

18、，即LASTVT(E)=+，*，i。第40页/共181页优先关系表构造方法：对Pab或PaQb，有ab；对PaR而bFIRSTVT(R)，有ab；对PRb而aLASTVT(R)，有ab。解之无。由得：E+T，即+FIRSTVT(T)，有+*，+i；T*P，即*FIRSTVT(P)，有*i。由得：EE+，即LASTVT(E)+，有+，*+，i+；TT*，即LASTVT(T)*，有*，i*。第41页/共181页得到优先关系表见表3-3。由于该文法的任何产生式的右部都不含两个相继并列的非终结符，故属算符文法，且该文法中的任何终结符对(见优先关系表)至多满足、和三种关系之一，因而是算符优先文法。第42

19、页/共181页表3-3 习题3.12的优先关系表 第43页/共181页用关系图构造优先函数的方法是：对所有终结符a用有下脚标的fa、ga为结点名画出全部终结符所对应的结点。若存在优先关系ab或ab，则画一条从fa到ga的有向弧；若ab或ab，则画一条从g b到f a的有向弧。最后，对每个结点都赋一个数，此数等于从该结点出发所能到达的结点(包括出发结点)的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)。用关系图法构造本题的优先函数，如图3-7所示。得到优先函数见表3-4。第44页/共181页图3-7 习题3.12关系图构造 第45页/共181页表3-4 习题3.12的优先函数表 第46

20、页/共181页该优先函数表经检查与优先关系表没有矛盾，故为所求优先函数。也可由定义直接构造优先函数，其方法是：对每个终结符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)。重复上述过程，直到每个终结符的函数值不再变化为止。如果有一个函数值大于2n(n为终结符个数)，则不存在优先函数。优先函数的计算过程如表3-5所示。第47页/共181页 表3-5 优先函数的计算过程表第48页/共181页计算最终收敛，并且计算得出的

21、优先函数与关系图构造得出的优先函数是一样的。3.13 设有文法GS:Sa|b|(A)ASdA|S(1)构造算符优先关系表；(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；(3)给出输入串(adb)#的分析过程。第49页/共181页【解答】(1)先求文法GS的FIRSTVT集和LASTVT集：由Sa|b|(A)得FIRSTVT(S)=a,b,(；由ASd得FIRSTVT(A)=d，又由AS得FIRSTVT(S)FIRSTVT(A)，即FIRSTVT(A)=d,a,b,(；由Sa|b|(A)得LASTVT(S)=a,b,)；第50页/共181页由 AdA得 LASTVT(A

22、)=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(；第51页/共181页 由SA)得LASTVT(A)，即d),a),b),)；由ASd得LASTVT(S)d，即ad,bd,)d；此外，由#S#得#；由#FIRSTVT(S)得#a,#b,#(；由LASTVT(S)#得a

23、#,b#,)#。最后得到算符优先关系表，见表3-6。第52页/共181页表3-6 习题3.13的算符优先关系表 第53页/共181页 由表3-6可以看出，任何两个终结符之间至多只满足、三种优先关系之一，故GS为算符优先文法。(2)为求出句型(SdSdS)的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图3-8所示。第54页/共181页图3-8 句型(SdSdS)的语法树 第55页/共181页由图3-8得到：短语：S，SdS，SdSdS，(SdSdS)简单短语(即直接短语)：S句柄(即最左直接短语)：S可以通过分析图3-8的语法树来求素短语和最左素短语，即找出语法树中的所有相邻终结符(中

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

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

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

27、对应的尾。3.15 试证明在算符文法中，任何句型都不包含两个相邻的非终结符。【解答】设文法G=(VT,VN,S,)，其中VT是终结符集；VN是非终结符集；为产生式集合；S是开始符号。第64页/共181页对句型的推导长度n作如下归纳：(1)当n=1时，S，则存在一条产生式S属于，其中a(VTVN)*。由于文法是算符文法，所以中没有两个相邻非终结符，故归纳初始成立。(2)设n=k时结论成立，则对任何k+1步推导所产生的句型必为S其中，、(VTVN)*，UVN，而UV是一条产生式。第65页/共181页由 归 纳 假 设，U是 非 终 结 符，设=12n，=12m，其中i、j(VTVN)(1in-1,

28、2jm)；但n和m必为位于U两侧的终结符。设V=V1V2Vr，由于它是算符文法的一个产生式右部候选式，因此V1V2Vr中不会有相邻的非终结符出现。又因为nV1和Vr1中的n、1为终结符，也即在推导长度为k+1时所产生的句型12nV1V2Vr12m不会出现相邻的非终结符，故n=k+1时结论成立。显然，在或为空时结论也成立。第66页/共181页3.16 给出文法GS:SaSbPPbPcbQc QQaa(1)它是Chomsky哪一型文法？(2)它生成的语言是什么？(3)它是不是算符优先文法？请构造算符优先关系表证实之；(4)文 法 GS消 除 左 递 归、提 取 公 共 左 因 子 后 是 不 是L

29、L(1)文法？请证实。第67页/共181页【解答】(1)根据Chomsky的定义，对任何形如A的产生式，有AVN，(VTVN)*时为2型文法。而文法GS恰好满足这一要求，故为Chomsky 2型文法。(2)由 文 法 GS可 以 看 出：S推 出 串 的 形 式 是 ai P bi(i0)，P推出串的形式是bjQcj(j1)，Q推出串的形式是ak(k1)。因此，文法GS生成的语言是L=aibjakcjbi|i0,j1,k1。第68页/共181页(3)求出文法GS的FIRSTVT集和LASTVT集：FIRSTVT(S)=a,b FIRSTVT(P)=bFIRSTVT(Q)=aLASTVT(S)=

30、b,c LASTVT(P)=cLASTVT(Q)=a构造优先关系表如表3-8所示。由于在优先关系中同时出现了aa和aa以及bb和bb，故文法GS不是算符优先文法。第69页/共181页表3-8 优先关系表 第70页/共181页(4)消除文法GS的左递归：SaSb|PPbPc|bQcQaQQaQ|提取公共左因子后得到文法GS:SaSb|PPbPPPc|QcQaQQaQ|第71页/共181页求每个非终结符的FIRST集和FOLLOW集如下：FIRST(S)=a,bFIRST(P)=bFIRST(P)=a,bFIRST(Q)=aFIRST(Q)=a,FOLLOW(S)=b,#FOLLOW(P)=b,c

31、,#FOLLOW(P)=b,c,#FOLLOW(Q)=cFOLLOW(Q)=c第72页/共181页通过检查GS可以得到：每一个非终结符的所有候选式首符集两两不相交；存在形如A的产生式QaQ|，但有FIRST(aQ)FOLLOW(Q)=ac=所以文法GS是LL(1)文法。第73页/共181页*3.17LR分析器与优先关系分析器在识别句柄时的主要异同是什么？【解答】如果SaA且有A，则称是句型相对于非终结符A的短语。特别的，如果有A，则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。规范归约是关于的一个最右推导的逆过程，因此，规范归约也称最左归约。请注意句柄的“最左”特征。

32、第74页/共181页LR分析器用规范归约的方法寻找句柄，其基本思想是：在规范归约的过程中，一方面记住已经归约的字符串，即记住“历史”；另一方面根据所用的产生式推测未来可能碰到的输入字符串，即对未来进行“展望”。当一串貌似句柄的符号串呈现于栈顶时，则可根据历史、展望以及现实的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。事实上，规范归约的中心问题恰恰是如何寻找或确定一个句型的句柄。给出了寻找句柄的不同算法也就给出了不同的规范归约方法，如LR(0)、SLR(1)、LR(1)以及LALR就是在归约方法上进行区别的。第75页/共181页算符优先分析不是规范归约，因为它只考虑了

33、终结符之间的优先关系，而没有考虑非终结符之间的优先关系。此外，算符优先分析比规范归约要快得多，因为算符优先分析跳过了所有单非产生式所对应的归约步骤。这既是算符优先分析的优点，同时也是它的缺点，因为忽略非终结符在归约过程中的作用存在某种危险性，可能导致把本来不成句子的输入串误认为是句子，但这种缺陷容易从技术上加以弥补。为了区别于规范归约，算符优先分析中的“句柄”被称为最左素短语。第76页/共181页3.18 什么是规范句型的活前缀？引进它的意义何在？【解答】在讨论LR分析器时，需要定义一个重要概念，这就是文法的规范句型的“活前缀”。字的前缀是指该字的任意首部，例如，字abc的前缀有、a、ab或a

34、bc。所谓活前缀，是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在其右边增添一些终结符号后，就可以使它成为一个规范句型。引入活前缀的意义在于它是构造LR(0)项目集规范族时必须用到的一个重要概念。第77页/共181页对于一个文法G，首先要构造一个NFA，它能识别G的所有活前缀，这个NFA的每个状态即为一个“项目”。文法G每一个产生式的右部添加一个圆点称为G的一个LR(0)项目(简称项目)，可以使用这些项目状态构造一个NFA。我们能够把识别活前缀的NFA确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。构成识别一个文法活前缀的DF

35、A项目集(状态)的全体称为这个文法的LR(0)项目集归范族。第78页/共181页3.19 试构造下述文法的SLR(1)分析表。GS:SbASB|bA AdSa|e BcAa|c【解答】首先将文法GS拓广为GS:GS：(0)SS(1)SbASB(2)SbA第79页/共181页(3)AdSa(4)Ae(5)BcAa(6)Bc构造文法GS的LR(0)项目集规范族如下：I0:SS I5:AeSbASB I6:SbASBSbA BcAa第80页/共181页I1:SS BcI2:SbASB I7:AdSaSbA I8:SbASBAdSa I9:BcAaAe Bc第81页/共181页I3:SbASB AdS

36、aSbA AeSbASB I10:AdSaSbA I11:BcAaI4:AdSa I12:BcAaSbASBSbA文法GS的DFA如图3-11所示。第82页/共181页图3-11 文法GS的DFA 第83页/共181页注意，在比较熟练的情况下，也可以不构造LR(0)项目集规范族而直接画出文法GS的DFA。由于I3和I9既含有移进项目又含有归约项目，故文法GS不是LR(0)文法。我们构造文法GS的FOLLOW集如下：(1)FOLLOW(S)=#；(2)由 SAS得 FIRST(S)FOLLOW(A)；即FOLLOW(A)=b；由SSB得FIRST(B)FOLLOW(S)；即FOLLOW(S)=c

37、；由ASa得FIRST(a)FOLLOW(S)；即FOLLOW(S)=a,c；第84页/共181页(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。第85页/共181页表3-9 SLR(1)分析表第86页/共181页3.20 LR(

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

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

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

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

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

43、的r2存在)；图3-12(b)为LR(0)分析表(有rj的行是每行都填满了rj且同一行rj的j相同，不同行rj的j不同)；而图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。第93页/共181页【解答】将文法G拓广为文法GS：(0)SS(1)S(EtSeS)(2)S(EtS)(3)Si=E(4)E+EF(5)EF(6)F*Fi(7)Fi第94页/共181页 列出LR(0)的所有项目：1.SS 9.S(EtSe

44、S)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*Fi4.S(EtSeS)12.S(EtS)20.Si=E 28.F*Fi 第95页/共181页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第96页/共181页用_CLOSURE方法构造文法GS的LR(0)项目集规范族：I

45、0: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*Fi第97页/共181页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第98页/共181页I4:S(EtSeS)E+EF I18:F*FiS(EtS)EF I19:F*FiS(EtSeS)I12:Si=

46、E I20:FiS(EtS)Si=E文法GS的DFA如图3-13所示。第99页/共181页图3-13 习题3.22的DFA 第100页/共181页构造SLR(1)分析表必须先求出所有形如“A”的FOLLOW(A)，即由FOLLOW集的构造方法求得GS的FOLLOW集如下：(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+

47、EF得FIRST(F)/FOLLOW(E)，即FOLLOW(E)=t,i；第101页/共181页(3)由 SS得 FOLLOW(S)FOLLOW(S)，即FOLLOW(S)=e,),#；由Si=E得FOLLOW(S)FOLLOW(E)，即FOLLOW(E)=t,i,e,),#；由EF得FOLLOW(E)FOLLOW(F)，即FOLLOW(F)=t,i,e,),#。最后得到SLR(1)分析表，见表3-10。第102页/共181页表3-10 习题3.22的SLR(1)分析表 第103页/共181页3.23 为二义文法GT构造一个LR分析表(详细说明构造方法)。其中终结符“，”满足右结合性，终结符“

48、；”满足左结合性，且“，”的优先级高于“；”的优先级。GT:TTAT|bTe|a A,|;【解答】首先将文法GT拓广为文法GS：(0)ST第104页/共181页(1)TTAT(2)TbTe(3)Ta(4)A，(5)A；下面列出LR(0)的所有项目：1ST 5TTAT 9TbTe 13A，2ST 6TTAT 10TbTe 14A，第105页/共181页3TTAT 7TbTe 11Ta 15A;4TTAT 8TbTe 12Ta 16A;用_CLOSURE方法构造文法GS的LR(0)项目集规范族，并根据转换函数GO构造出文法GS的DFA，如图3-14所示。第106页/共181页图3-14 习题3.2

49、3中文法GS的DFA 第107页/共181页已知文法GS为二义文法，故必然存在冲突。逐一检查各状态，得知I8存在“移进”/“归约”冲突(因为TTAT要求归约，而TTAT却要求移进)。在此，LR(0)已不能满足要求，因为LR(0)分析表中的ACTION子表在某归约状态下(即某一行)的所有栏目全被“rj”占满，但由于存在“移进”/“归约”冲突，即在此状态下，有些栏目应填为“Sj”(即归约)。为了减少冲突，最好采用SLR(1)、LR(1)或LALR分析表。这里采用SLR(1)分析表。下面，构造文法GS中非终结符的FIRST集和FOLLOW集如下：FIRST(S)=FIRST(T)=a,b;FIRST

50、(A)=“，”,“；”FOLLOW(S)=#；FOLLOW(T)=“，”,“；”,e,#；FOLLOW(A)=a,b第108页/共181页因为TTAT要求归约，而TTAT要求移进，即对T要求归约而对A要求移进，则有：FOLLOW(T)FIRST(A)=“，”,“；”,e,#“，”,“；”=“，”,“；”也即冲突字符为“，”和“；”。下面分析“，”与“；”的具体情况。因为“，”的优先级高且有右结合，故不论是“，”还是“；”，遇见“，”其后的“，”一定移进；类似地，“；”优先级低且有左结合，则无论是“，”还是“；”，遇见其后的“；”一定归约。由此可得到SLR(1)分析表，见表3-11。第109页/