编译原理答案.doc

第2章 习题 2-1 设有字母表A1 =a,b,c,z，A2 =0,1,9，试回答下列问题：(1) 字母表A1上长度为2的符号串有多少个？ (2) 集合A1A2含有多少个元素？(3) 列出集合A1(A1A2)*中的全部长度不大于3的符号串。2-2 试分别构造产生下列语言的文法：（1）anbn|n0；（2）anbmcp|n,m,p0；（3）an#bn|n0cn#dn|n0；（4）w#wr# | w0,1*,wr是w的逆序排列 ；（5）任何不是以0打头的所有奇整数所组成的集合；（6）所有由偶数个0和偶数个1所组成的符号串的集合。2-3 试描述由下列文法所产生的语言的特点：（1）S10S0 SaA AbA Aa （2）SSS S1A0 A1A0 A（3）S1A SB0 A1A AC BB0 BC C1C0 C（4）SaSS Sa2-4 试证明文法 SAB|DC AaA|a BbBc|bc CcC|c DaDb|ab为二义性文法。2-5 对于下列的文法SAB|c AbA|a BaSb|c试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。2-6 化简下列各个文法(1) SaABS|bCACd AbAB|cSA|cCC BbAB|cSB CcS|c(2) SaAB|E AdDA|e BbE|f CcAB|dSD|a DeA EfA|g(3) Sac|bA AcBC BSA CbC|d2-7 消除下列文法中的-产生式(1) SaAS|b AcS|(2) SaAA AbAc|dAe|2-8 消除下列文法中的无用产生式和单产生式(1) SaB|BC AaA|c|aDb BDB|C Cb DB(2) SSA|SB|A AB|(S)|( ) BS| (3) EE+T|T TT*F|F FPF|P P(E)|i第2章 习题答2-1 答：(1) 26*26=676(2) 26*10=260(3) a,b,c,.,z, a0,a1,.,a9, aa,.,az,.,zz, a00,a01,.,zzz,共有26+26*36+26*36*36=34658个2-2 解：(1) 对应文法为G(S)=(S,a,b, S| aSb ,S) (2) 对应文法为G(S)=(S,X,Y,a,b,c,SaS|X, XbX|Y, YcY| ,S)(3)对应文法为G(S)=(S,X,Y,a,b,c,d,#, SX, SY, XaXb|#, YcYd|# ,S)(4)G(S)=(S,W,R,0,1,#, SW#, W0W0|1W1|# ,S)(5)G(S)=(S,A,B,I,J,0,1,2,3,4,5,6,7,8,9,SJ|IBJ, B0B|IB|, IJ|2|4|6|8, J1|3|5|7|9,S)(6)对应文法为 S0A|1B|，A0S|1C ， B0C|1S， C1A|0B2-3 解：(1) 本文法构成的语言集为：L(G)=(10)nabma0n|n,m0。(2) L(G)=1n0n |n0+，该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同的连续的0。(3) 本文法构成的语言集为：L(G)=1p1n0n|p1,n01n0n0q|q1,n0，特点是具有1p1n0n 或1n0n0q形式，进一步，可知其具有形式1n0m|n,m0,且n+m0。(4)由L(G)=a2n-1|n1可知，该语言特点是：产生的句子是奇数个a。2-4 证明：因为存在句子：abc，它对应两个最右推导：S AB Abc abcS DC Dc abc所以，本文法具有二义性。2-5 解：句子bbaacb的最右推导为：S AB AaSb Aacb bAacb bbAacb bbaacb上面推导中，下划线部分为当前句型的句柄。与句子bbaacb相应的语法树为：全部的短语为：第一个a（a(1)）是句子bbaacb相对于非终结符A (A(1) (产生式Aa）的短语（直接短语）；b(1)a(1)是句子bbaacb相对于非终结符A(2)的短语；b(2)b(1)a(1)是句子bbaacb相对于非终结符A(3)的短语；c是句子bbaacb相对于非终结符S(1)（产生式Sc）的短语（直接短语）；a(2)cb(3)是句子bbaacb相对于非终结符B的短语；b(2)b(1)a(1)a(2)cb(3)是句子bbaacb相对于非终结符S(2)的短语；注：符号的上标是为了描述方便加上去的。2-6 解：(1) 因为由非终结符号B推导不出终结符号串，因此B是无用符号，含有B的产生式BBab,BcSB, SaABS和AbAB都是无用产生式，应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为SbCACd AcSA|cCC CcS|c(2) 因为由文法的开始符号推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式CcAB|dSD|a都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为SaAB|E AdDA|e Bf DeA EfA|g(3) 因为由非终结符号A,B推导不出终结符号串，因此A,B是无用符号，删除含有A,B的产生式SBa, AcBC和BSA后得到文法GS: Sac CbC|d又因为由文法GS的开始符号S推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式CbC|d都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法GS为 Sac2-7 解：(1) 对于G，我们可得到W=A；再按如下步骤得到产生式集P：对于产生式SaAS，将产生式SaAS及SaS放入P；对于产生式Sb，直接将产生式Sb放入P；对于产生式AcS，将产生式AcS放入P。于是得到消除-产生式后的文法为：SaAS|aS|b AcS(2) 对于G，我们可得到W=A；再按如下步骤得到产生式集P：对于产生式SaAA，将产生式SaAA及SAa和Sa放入P；对于产生式AbAc，将产生式AbAc及Abc放入P；对于产生式AdAe，将产生式AdAe及Ade放入P。于是得到消除-产生式后的文法为：SaAA|aA|a AbAc|bc|dAe|de2-8 解：(1) 首先求出如下集合W(S)=S, W(A)=A, W(B)=B,C, W(C)=C, W(D)=D,B,C然后按如下步骤得到产生式集P：将P中的所有非单产生式添加到P中：SaB|BC AaA|c|aDb BDB Cb因为CW(B)，故将C的所有非单产生式的右部作为B-产生式的右部添加到P中：Bb因为BW(D)，故将B的所有非单产生式的右部作为D-产生式的右部添加到P中：DDB因为CW(D)，故将C的所有非单产生式的右部作为D-产生式的右部添加到P中：Db由此得到消除单产生式后的文法如下：SaB|BCAaA|c|aDbBDB|bCbDb|DB因为由文法的开始符号推导不出含有非终结符号A的句型，因此A是无用符号，含有A的产生式AaA|c|aDb都是无用产生式，应予以删除。于是得到消除无用产生式和单产生式后的文法如下：SaB|BCBDB|bCbDb|DB(2) 首先求出如下集合W(S)=S,A,B, W(A)=A,B, W(B)=B然后按如下步骤得到产生式集P：将P中的所有非单产生式添加到P中：SSA|SB A(S)|( ) BS| 因为AW(S)，故将A的所有非单产生式的右部作为S-产生式的右部添加到P中：S(S)|( ) 因为BW(S)，故将B的所有非单产生式的右部作为S-产生式的右部添加到P中：SS| 因为BW(A)，故将B的所有非单产生式的右部作为A-产生式的右部添加到P中：AS| 由此得到消除单产生式后的文法如下：SSA|SB|(S)|( )|S| A(S)|( )|S| BS| (3) 首先求出如下集合W(E)=E,T,F,P, W(T)=T,F,P, W(F)=F,P, W(P)=P然后按如下步骤得到产生式集P：将P中的所有非单产生式添加到P中：EE+T TT*F FPF P(E)|i因为T,F,PW(E)，故将T,F,P的所有非单产生式的右部作为E-产生式的右部添加到P中：ET*F EPF E(E)|i 因为F,PW(T)，故将F,P的所有非单产生式的右部作为T-产生式的右部添加到P中：TPF T(E)|i 因为PW(F)，故将P的所有非单产生式的右部作为F-产生式的右部添加到P中：F(E)|i由此得到消除单产生式后的文法如下：EE+T|T*F|PF|(E)|iTT*F|PF|(E)|i FPF|(E)|i P(E)|i 第3章 习题 3-1 试构造一右线性文法，使得它与如下的文法等价SAB AUT UaU|a DbT|b BcB|c 并根据所得的右线性文法，构造出相应的状态转换图。3-2 对于如题图3-2所示的状态转换图 (1) 写出相应的右线性文法；(2) 指出它接受的最短输入串；(3) 任意列出它接受的另外4个输入串；(4) 任意列出它拒绝接受的4个输入串。3-3 对于如下的状态转换矩阵：(1) 分别画出相应的状态转换图；(2) 写出相应的3型文法；(3) 用自然语言描述它们所识别的输入串的特征。3-4 将如下的NFA确定化和最小化：3-5 将如题图3-5所示的具有动作的NFA确定化。题图3-5 具有动作的NFA 3-6 设有文法GS：SaA AaA|bB BbB|cC|c CcC|c试用正规式描述它所产生的语言。 3-7 分别构造与如下正规式相应的NFA。(1) (0* |1)(1* 0)*(2) b|a(aa*b)*b 3-8 构造与正规式(a|b)*(aa|bb)(a|b)*相应的DFA。第3章 习题答案3-1 解：根据文法知其产生的语言是:LG=ambnci| m,n,i1可以构造与原文法等价的右线性文法:SaA AaA|bB BbB|cC|c CcC|c其状态转换图如下:3-2 解:(1) 其对应的右线性文法是GA:A 0D B0A|1C C0A|1F|1D0B|1C E0B|1C F1A|0E|0(2) 最短输入串为011(3) 任意接受的四个输入串为：0110,0011,000011,00110(4) 任意拒绝接受的输入串为： 0111，1011，1100，10013-3 解:(1) 相应的状态转换图为：(2) 相应的3型文法为：() SaA|bS AaA|bB|b BaB|bB|a|b() SaA|bB|a AbA|aC|a|b BaB|bC|b CaC|bC|a|b() SaA|bB|b AaB|bA|a BaB|bB|a|b () SbS|aA AaC|bB|a BaB|bC|b CaC|bC|a|b(3) 用自然语言描述的输入串的特征为：() 以任意个(包括0个)b开头，中间有任意个（大于1）a，跟一个b，还可以有一个由a,b组成的任意字符串。() 以a打头，中间有任意个（包括0个）b,再跟a,最后由一个a,b所组成的任意串结尾；或者以b打头，中间有任意个（包括0个）a,再跟b,最后由一个a,b所组成的任意串结尾。() 以a打头，后跟任意个（包括0个）b ，再跟a，最后由一个a,b所组成的任意串结尾；或者以b打头，由一个a,b所组成的任意串结尾。() 以任意个（包括0个）b开头,中间跟aa，最后由一个a,b所组成的任意串结尾；或者以任意个（包括0个）b开头，中间跟ab后，再接任意个（包括0个）a，再接b，最后由一个a,b所组成的任意串结尾。3-4 解：(1) 将NFA M确定化后得DFA M，其状态转换矩阵如答案图3-4-(1)之(a)所示，给各状态重新命名，即令： S=1, S,A=2, A,B=3, B=4且由于3及4的组成中均含有M的终态B，故3和4组成了DFA M的终态集Z。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-4-(1)之(b)及(c)所示。现将DFA M最小化：()初始分划由两个子集组成，即0:1,2, 3,4()为得到下一分划，考察子集1,2。因为2b =33,4但 1b =故1和2可区分，于是便得到下一分划1: 1, 2, 3,4()又因10 ，再考虑3,4，因为3b =33,4而 4b =故3和4可区分，从而又得到2: 1, 2, 3, 4此时子集已全部分裂，故最小化的过程宣告结束，M即为状态数最小的DFA。(2) 将NFA M确定化后得DFA M，其状态转换矩阵如答案图3-4-(2)之(a)所示，给各状态重新命名，即令： S=1, A=2, B,C=3且由于3的组成中含有M的终态C，故3为DFA M的终态。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-4-(2)之(b)及(c)所示。现将DFA M最小化：()初始分划由两个子集组成，即0:1,2, 3()为得到下一分划，考察子集1,2。因为2b =21,2但 1b =故1和2可区分，于是便得到下一分划1: 1, 2, 3此时子集已全部分裂，故最小化的过程宣告结束，M即为状态数最小的DFA。(3) 将NFA M确定化后得DFA M，其状态转换矩阵如答案图3-4-(3)之(a)所示，给各状态重新命名，即令： S=1, A=2, S,B=3且由于3的组成中含有M的终态B，故3为DFA M的终态。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-4-(3)之(b)及(c)所示。现将DFA M最小化：()初始分划由两个子集组成，即0:1,2, 3()为得到下一分划，考察子集1,2。因为2b =3但 1b =故1和2可区分，于是便得到下一分划1: 1, 2, 3此时子集已全部分裂，故最小化的过程宣告结束，M即为状态数最小的DFA。(4) 将NFA M确定化后得DFA M，其状态转换矩阵如答案图3-4-(4)之(a)所示，给各状态重新命名，即令： A=1, B,C=2, B=3, C=4且由于2和4的组成中含有M的终态C，故2和4组成了DFA M的终态集Z。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-4-(4)之(b)及(c)所示。 现将DFA M最小化：()初始分划由两个子集组成，即0:1,3, 2,4()为得到下一分划，考察子集1,3。因为1a =22,4但 3a =11,3故1和3可区分，于是便得到下一分划1: 1, 3, 2,4()又因10，再考虑2,4，因为2a =4a =1, 2b =4b =4所以2和4不可区分，故子集S,B已不能再分裂。此时2 =1 ，子集分裂的过程宣告结束。() 现选择状态2作为2,4的代表，将状态4从状态转换图中删去，并将原来引至4的矢线都引至2，这样，我们就得到了最小化后的DFA M如答案图3-4-(4)之(d)所示。3-5 解：(1) 将具有动作的NFA M确定化后得DFA M，其状态转换矩阵如答案图3-5-(1)之(a)所示，给各状态重新命名，即令： S,B,C=1, A=2, B,C =3, C=4且由于1,3和4的组成中均含有M的终态C，故1,3和4组成了DFA M的终态集Z。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-5-(1)之(b)及(c)所示。(2) 将具有动作的NFA M确定化后得DFA M，其状态转换矩阵如答案图3-5-(2)之(a)所示，给各状态重新命名，即令： S=1, Z=2, R,U =3, S,X=4, R,U,Y=5, S,U,X=6, S,Z=7, R,U,Y,Z=8且由于2,7和8的组成中均含有M的终态Z，故2,7和8组成了DFA M的终态集Z。于是，所构造之DFA M的状态转换矩阵和状态转换图如答案图3-5-(2)之(b)及(c)所示。3-6 解：首先将文法写成方程组：(1)S=aA (2)A=aA+bB (3)B=bB+cC+c (4)C=cC+c 将(4)代入(3)，得： (5)B=bB+C 由论断3.1，方程(4)的解为:C=c*c将上式代入(5)，得： B=bB+c*c由论断3.1，得：B=b*c*c将上式代入(2)，得： A=aA+b*bc*c由论断3.1，得： A=a*b*bc*c将上式代入(1)，得：S=a*ab*bc*c即文法所产生的语言可用正规式a*ab*bc*c表示。3-7 解：(1) 构造与正规式(0* |1)(1* 0)*相应的NFA的步骤如答案图3-7-(1)所示：（2) 构造与正规式 b|a(aa*b)*b 相应的NFA的步骤如答案图3-7-(2)所示：答案图3-7-(2) 正规式 b|a(aa*b)*b 的NFA3-8 解：首先，构造与正规式(a|b)*(aa|bb)(a|b)*相应的NFA M，其构造步骤如答案图3-8(a)所示：其次，将答案图3-8(a)所示的具有动作的NFA M确定化后得到DFA M，其状态转换矩阵如答案图3-8(b)所示，给各状态重新命名，即令： S,3,1=S, 3,1,5=A, 3,1,6 =B, 3,1,5,2,4,Z=C, 3,1,6,2,4,Z=D, 3,1,6,4,Z=E, 3,1,5,4,Z=F且由于C,D,E和F的组成中均含有NFA M的终态Z，故C,D,E和F组成了DFA M的终态集Z。于是，将NFA M确定化后所得DFA M的状态转换矩阵和状态转换图如答案图3-8(c)及(d)所示。(e) 对DFA M最小化后所得的DFA M的状态转换图答案图3-8 最后，将所得DFA M最小化：()初始分划由两个子集组成，即0:S,A,B, C,D,E,F()为得到下一分划，考察子集S,A,B。因为S,Ba =AS,A,B但 Aa =CC,D,E,F故S,B和A可区分，于是便得到下一分划1: S,B, A, C,D,E,F()因1 0 ，考虑S,B，因为Sb =BS,B但 Bb =DC,D,E,F故S和B可区分，于是便得到下一分划2: S, B, A, C,D,E,F() 又因2 1 ，再考虑C,D,E,F，因为Ca =Fa =C, Cb =Fb =E所以C和F等价；同理可得D和E等价。又因为Ca =C, Da =F, Cb =E, Db =D而C和F等价，D和E等价，所以C和D也等价，故C,D,E,F这4个状态等价。此时3 =2 ，子集分裂的过程宣告结束。()现选择状态C作为C,D,E,F的代表，将状态D,E,F从状态转换图中删去，并将原来引至D,E,F的矢线都引至C，这样，我们就得到了最小化后的DFA M如答案图3-8(e)所示,此DFA M即为所求的与正规式(a|b)*(aa|bb)(a|b)*相应的DFA。第4章 习题1 4-1 消除下列文法的左递归性。(1)SSA|A ASB|B|(S)|( ) BS| (2) SAS|b ASA|a(3) S(T)|a| TS|T,S4-2 对于如下文法，求各候选式的FIRST集和各非终结符号的FOLLOW集。 SaAB|bA| AaAb| BbB| 4-3 验证下列文法是否为LL(1)文法。(1) SAB|CDa Aab|c BdE|CeC| DfD|f EdE|(2) SaABbCD| AASd| BSAc|eC| CSf|Cg| DaBD|4-4 对于如下的文法GS：SSb|Ab|b AAa|a(1) 构造一个与G等价的LL(1)文法GS；(2) 对于GS，构造相应的LL(1)分析表；(3) 利用LL(1)分析法判断符号串aabb是否是文法GS的合法句子。 4-5 设已给文法SSaB|bB AS|a BAc(1) 构造一个与G等价的LL(1)文法GS；(2) 对于GS，构造相应的LL(1)分析表；(3) 利用LL(1)分析法判断符号串bacabc是否是文法GS的合法句子。第4章 习题答案4-1 解： (1) 文法GS中的S，A都是间接左递归的非终结符号。将A产生式的右部代入产生式 SA中，得到与原文法等价的文法GS： SSA|SB|B|(S)|( ) ASB|B|(S)|( ) BS| 文法GS中的S是直接左递归的非终结符号，则消除S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：SBS|(S)S|( )S SAS|BS|ASB|B|(S)|( ) BS| (2) 文法GS中的S，A都是间接左递归的非终结符号。将A产生式代入产生式 SAS中，得到与原文法等价的文法GS： SSAS|aS|b ASA|a文法GS中的S是直接左递归的非终结符号，则消除S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：SaSS|bS SASS|ASA|a(3) 文法GS中的T是直接左递归的非终结符号。则消除T产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：S(T)|a| TSTT,ST|4-2 解： 文法GS的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-2所示。答案表4-2 文法GS的各个FIRST集和FOLLOW集产 生 式FIRSTFOLLOWSaABSbASab#AaAbA a b,# BbB Bb#4-3 解：(1) 因为D产生式的两个候选式fD和f的FIRST集交集为f,不为空，所以该文法不是LL(1)的。(2) 因为文法中含有左递归的非终结符号A，故此文法具有左递归性，不是LL(1)的。4-4 解： (1) 文法中含有直接左递归的非终结符号S和A，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：SAbS|bS SbS| AaA AaA| 文法GS的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-4-(1)所示:答案表4-4-(1) 文法GS的各个FIRST集和FOLLOW集产 生 式FIRSTFOLLOWSAbSSbSab#SbSSb#AaAab AaA Aab下面来验证文法GS是否是LL(1)文法。对于文法GS，因为有：对于产生式SAbS|bS，有FIRST(AbS)FIRST(bS)=ab=；对于产生式SbS|，有FIRST(bS)FOLLOW(S)=b#=；对于产生式AaA|，有FIRST(aA)FOLLOW(A)=ab=；所以文法GS即为所求的与G等价的LL(1)文法。(2) 文法GS的LL(1)分析表如答案表4-4-(2)所示:答案表4-4-(2) 文法GS的LL(1)分析表ab#SSAbSSbSSSbSSAAaA4-4-(2)AAaAA(3) 对符号串aabb进行LL(1)分析的过程如答案表4-4-(3)所示。答案表4-4-(3) 对aabb进行LL(1)分析的过程步骤分析栈余留输入串所用产生式1#Saabb# SAbS2 #SbAaabb# AaA3#SbAaaabb# 4#SbAabb# AaA5#SbAaabb# 6#SbAbb# A7#Sbbb# 8#Sb# SbS9#Sbb# 10#S# S11# # 分析成功 因为分析成功，所以符号串aabb是文法GS的合法句子。4-5 解： (1) 文法中含有直接左递归的非终结符号S，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：SbBS SaBS| AS|a BAc 文法GS的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-5-(1)所示:答案表4-5-(1) 文法GS的各个FIRST集和FOLLOW集产 生 式FIRSTFOLLOWSbBSb#,cSaBSSa#,cAS Aabac BAca,b #,a,c下面来验证文法GS是否是LL(1)文法。对于文法GS，因为有：对于产生式SaBS|，有FIRST(aBS)FOLLOW(S)=a#,c=；对于产生式AS|a，有FIRST(S)FIRST(a)=ba=；所以文法GS即为所求的与G等价的LL(1)文法。(2) 文法GS的LL(1)分析表如答案表4-5-(2)所示:答案表4-5-(2) 文法GS的LL(1)分析表abc#SSbBSSSaBSSSAAaASBBAcBAc (3) 对符号串bacabc进行LL(1)分析的过程如答案表4-5-(3)所示。答案表4-5-(3) 对bacabc进行LL(1)分析的过程 步骤分析栈余留输入串所用产生式1#Sbacabc# SbBS2 #SBbbacabc# 3 #SBacabc# BAc4#ScAacabc# Aa5 #Scaacabc# 6#Sccabc# 7#Sabc# SaBS8#SBaabc# 9#SBbc# BAc10#ScAbc# AS11#ScSbc# SbBS12#ScSBbbc# 13#ScSB c# 分析失败 因为LL(1)分析表中B行c列元素为空，即为“出错”，故分析失败，所以符号串bacabc不是文法GS的合法句子。第五章 习题5-1 设有文法GS： SA/ AaAAS/(1) 找出部分符号序偶间的简单优先关系。(2) 验证GS不是简单优先文法。 5-2 对于算符文法GS：SE EE-TT TT*FF F-PP P(E)i(1) 找出部分终结符号序偶间的算符优先关系。(2) 验证GS不是算符优先文法。5-3 设有文法GE：EE1 E1E1+T1|T1 T1T TT*F|F F(E)|i 其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i）进行简单优先分析的过程。题图5-3 文法GE的简单优先矩阵5-4 设有文法GE：EE+T|TTT*F|FF(E)|i其相应的算符优先矩阵如题图5-4所示。试给出对符号串（i+i）进行算符优先分析的过程。(i*+)#(i*+)#题图5-4 文法GE的算符优先矩阵5-5 对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(0)分析表，并判断哪些是LR(0)文法。(1) SaSbaScab(2) SaSSbaSSSc(3) SA AAba5-6 下列文法是否是SLR(1)文法？若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。(1) SSabbR RSa(2) SaSABBA AaAB Bb(3) SaAbB AcAd BcBdd5-7 对如下的文法分别构造LR(0)及SLR(1)分析表，并比较两者的异同。 ScAdb AASca 5-8 对于文法GS:SA ABA BaBb (1) 构造LR(1)分析表；(2) 给出用LR(1)分析表对输入符号串abab的分析过程。5-9 对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。 (1) SA AAB BaBb (2) SaSaa第4章 习题答案2 5-1 解：(1) 由文法的产生式和如答案图5-1(a)所示的句型Aa的语法树，可得G中的部分优先关系如答案图5-1(b)所示。(2) 由答案图5-1(b)可知，在符号A和/之间，即存在等于关系，又存在低于关系，故文法GS不是简单优先文法。 5-2 解：(1) 由文法GS的产生式可直接看出：（ = ）此外，再考察句型P(E)和i*(T*F)的语法树 (见答案图5-2(a)及(b)。由答案图5-2(a)可得： , , ( 由答案图5-2(b)可得： i * , * ( , ( * , * ） (2) 由答案图5-2(a)可知，在终结符号和之间，存在两种算符优先关系： , 故文法GS不是算符优先文法。5-3 解：对符号串(i+i)进行简单优先分析的过程如答案表5-3所示。因为分析成功，所以符号串(i+i)是文法GE的合法句子。答案表5-3 符号串(i+i)的简单优先分析过程步骤分析栈关系当前符号余留输入串句柄所用产生式0#低于（i+i)# 1#(低于i+i)# 2#(i优于+i)# iFi3#(F优于+i)# FTF4#(T优于+i)# TT1T5#(T1优于+i)# T1E1T16#(E1等于+i)# 7#(E1+低于i)# 8#(E1+i优于)# iFi9#(E1+F优于)# FTF10#(E1+T优于)# TT1T 11#(E1+T1优于)# E1+T1E1E1+T1 12#(E1优于)# E1EE1 13#(E等于)# 14#(E)优于#(E)F(E) 15#F优于#FTF16#T优于#TT1T17#T1优于#T1E1T1 18#E1优于#E1EE1 19#E优于#分析成功5-4 解：对符号串(i+i)进行算符优先分析的过程如答案表5-4所示。 因为分析成功，所以符号串(i+i)是文法GE的合法句子。句子(i+i)及其分析过程中所得句型的语法树如答案图5-4所示。答案表5-4 符号串（i+i)的算符优先分析过程步骤分析栈当前栈顶终结符号优先关系当前输入符号余留输入串最左素短语0#（i+i)# 1#(（i+i)# 2#(ii+i)# i3#(F(+i)# 4#(F+i)# 5#(F+ii)# i6#(F+F+)# F+F7#(E()# 8#(E)#(E) 9#F#分析成功 5-5 解：(1) 在文法GS中引入一个新的开始符号S，且将SS作为第0个产生式添加到文法G中，从而得到G的拓广文法GS：0.SS 2.SaSc1.SaSb 3.Sab识别文法GS全部可归前缀的DFA如答案图5-5-(1)所示。因为文法GS的每个LR(0)项目集中都不含冲突项目，所以文法GS是LR(0)文法，故可构造出不含冲突动作的LR(0)分析表如答案表5-5-(1)所示。答案表5-5-(1) 文法GS的LR(0)分析表状态ACTIONGOTOabc#S0123456s2 s2r3 r1r2 s4s5r3r1 r2s6r3r1r2accr3r1r213(2) 在文法GS中引入一个新的开始符号S，且将SS作为第0个产生式添加到文法G中，从而得到G的拓广文法GS：0.SS 2.SaSSS 1.SaSSb 3.Sc识别文法GS全部可归前缀的DFA如答案图5-5-(2)所示。因为文法GS的每个LR(0)项目集中都不含冲突项目，所以文法GS是LR(0)文法，故可构造出不含冲突动作的LR(0)分析表如答案表5-5-(2)所示。答案表5-5-(2) 文法GS的LR(0)分析表状态ACTIONGOTOabc#S01234567s2 s2 r3s2 s2r1r2 r3r1 r2s3s3 r3s3s3r1r2accr3r1r21457(3) 在文法GS中引入一个新的开始符号S，且将SS作为第0个产生式添加到文法G中，从而得到G的拓