蒋立源编译原理第三版习题与答案

1、2-1设有字母表A严a,b,c,，z, A2 = 0tl,-,9),试回答下列问题:(1) 字母表血上长度为2的符号串有多少个(2) 集合AA含有多少个元素 列出集合AdAQA中的全部长度不大于3的符号串。2-2试分别构造产生下列语言的文法：(1) anbn|nO；(2) alfc n.叫pMO:；(3) aWlnO U cW|n0)；(4) w#wr# we o,l)wr是 v 的逆序排列；(5) 任何不是以0打头的所有奇整数所组成的集合；(6) 所有由偶数个0和偶数个1所组成的符号串的集合。2-3试描述由下列文法所产生的语言的特点:(1)S-1OSOS-aAA-bAA-a(2)S-SSS-

2、1AOA-1A0A (3)S-1AS-BOA-1AA-CBT0B-CC-ICOC- e(4)S-aSSSa2-4试证明文法BbBc|bc CcC|c DaDblabS-AB|DC A-aA a为二义性文法。2-5对于下列的文法SAB|c A-bAla B*aSbic试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全 部短语。2-6化简下列各个文法(1) S-aABS|bCACdA-bAB!cSA!cCC B-bAB cSB C-cS|c(2) S-aABjEA-dDAleC-cABidSDa D-eAETA g(3) S-acIbA A-cBC B-SAC-bC

3、cl2-7消除下列文法中的-产生式(1) S-aASlbA-cS| (2) S-aAAA-bAc|dAe| e2-8消除下列文法中的无用产生式和单产生式(1) S-aBlBCA-aAlc aDb B-DB|C C-b1)7(2) S-SAISB AA-B (S) I ( ) B-S(3) E-E+TlTT-T*EF F-P t F P P- (E) | i第2章习题答案2-1 答：(1) 26*26=676(2) 26*10=260(3) (atb,c,z, a0,al,ta9, aa,az, zz, aOO.aO,zzz,共有 26+26*36+26*36*36=34658 个2-2 解：(

4、1) 对应文法为 G(S) = (S, a,b, S-* | aSb ,S)(2) 对应文法为 G(S) = (S,X,Y, a,b,c, S-aS|X, X-bX Y, Y-cY e ),S)(3) 对应 文法为 G(S) = (S,X,Y, a,b,c,d,#,S-X, S-Y. X-aXb|#,Y-cYdl# ,S)(4) G(S) = (S,W,R, 0,1,#,W0W0I1W1 # ,S)(5) G(S) = (S,A,B,I,J, 0,1,2,3,4,5,6,7,8,9, S-j| IBJ, B_OB|lB e , IJ 2|4|6|8, J-*l|3|5|7 9,S)(6) 对应

5、文法为 S-OA| IB| , A-OS 1C , B-OCllS, C1A|OB2-3 解：(1) 本文法构成的语言集为：L(G) = (10)nabaa0n|n,m0 1,n0) U 1W|1,n0,特点 是具有1T0或l0形式，进一步，可知其具有形式10 n,i心0,且n+m0。)(4) 由L(G) = a2n ,|nl可知，该语言特点是：产生的句子是奇数个a。2-4证明：因为存在句子：abc,它对应两个最右推导：SABAbeabcSDCDeabc所以，本文法具有二义性。2-5 解:句子bbaacb的最右推导为：S AB AaSb Aacb bAacb bbAacb bbaacb 上面推

6、导中，下划线部分为当前句型的句柄。与句子bbaacb相应的语法树为：全部的短语为：第一个a （a）是句子bbaacb相对于非终结符A （A，n）（产生式A-*a）的短语（直 接短语）；ba是句子bbaacb相对于非终结符A的短语;bba是句子bbaacb相对于非终结符A的短语;c是句子bbaacb相对于非终结符S（产生式S-c）的短语（直接短语）；acb是句子bbaacb相对于非终结符B的短语；bJb al aJcb ；是句子bbaacb相对于非终结符S的短语;注：符号的上标是为了描述方便加上去的。2-6 解：（1）因为由非终结符号B推导不出终结符号串，因此B是无用符号，含有B的产生 式Bab

7、,B-*cSB, S-aABS和A-bAB都是无用产生式，应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为S-bCACd A-cSAlcCC C-cS|c（2）因为由文法的开始符号推导不出含有非终结符号C的句型，因此C是无用符号, 含有C的产生式C-cAB|dSD a都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为SaABlE A-dDAle B-*f D-eA E-fA g）（3）因为由非终结符号A.B推导不出终结符号串，因此A.B是无用符号，删除含有A.B的产生式S-Ba. A-cBC和B-SA后得到文法G S：S-*a

8、c C*bC | d又因为由文法G S的开始符号S推导不出含有非终结符号C的句型，因此C是无 用符号，含有C的产生式C-*bC d都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法G S为S-*ac2-7 解：(1) 对于G,我们可得到W= A；再按如下步骤得到产生式集P ：对于产生式S-aAS,将产生式S-aAS及S-*aS放入P；对于产生式S-b,直接将产生式S-b放入P；对于产生式A-cS,将产生式A-cS放入P。于是得到消除-产生式后的文法为：S-aAS|aS|b A-cS(2) 对于G,我们可得到W= A；再按如下步骤得到产生式集P ：对于产生

9、式S-aAA,将产生式S-aAA及S-Aa和S-a放入P；对于产生式A-bAc,将产生式A-bAc及A-bc放入P；对于产生式A-*dAe,将产生式A-*dAe及A-*de放入P。于是得到消除产生式后的文法为：SaAA |aA|a AbAc be I dAe I de2-8 解:(1)首先求出如下集合W(S) = S), W(A) = (A), W(B) = B,C, W(C) = C, W(D) = (D,B,C然后按如下步骤得到产生式集p :将P中的所有非单产生式添加到P中：SaBlBC AaAlciaDb B-DB C-b因为CGW(B),故将C的所有非单产生式的右部作为B-产生式的右部

10、添加到P中:B-b因为BGW(D),故将B的所有非单产生式的右部作为D-产生式的右部添加到P中:D-DB因为CGW(D),故将C的所有非单产生式的右部作为D-产生式的右部添加到P中:D-b由此得到消除单产生式后的文法如下：S-aB|BCAaA|c aDbB-DB|bC-bD-b DB因为由文法的开始符号推导不出含有非终结符号A的句型，因此A是无用符号，含 有A的产生式A-*aA|c aDb都是无用产生式，应予以删除。(于是得到消除无用产生式和单产生式后的文法如下：S-aB|BCB-DB|bC-bD-b DB(2)首先求出如下集合W(S) = S,A,B, W(A) = A,B, W(B) =

11、B然后按如下步骤得到产生式集P :将P中的所有非单产生式添加到P中：S-SAlSB A- (S) | ( )B-S|因为AGW(S),故将A的所有非单产生式的右部作为S-产生式的右部添加到P中：S-(S)|()因为BGW(S),故将B的所有非单产生式的右部作为S-产生式的右部添加到P中:S-S|因为BWW(A),故将B的所有非单产生式的右部作为A-产生式的右部添加到P中:A-S|由此得到消除单产生式后的文法如下：S-SA|SB|(S) |( ) S | A- (S) | ( )|S|B-S|(3) 首先求出如下集合W(E) = E,T,F,P, W(T) = T,F,P, W(F) = FtP, W(P) = (P然后按如下步骤得到产生式集P :将P中的所有非单产生式添加到P中：E-E+T T-T*F F-PfF P(E) i因为T,F,PWW(E),故将T,F,P的所有非单产生式的右部作为E-产生式的右部添加 到P中：E-T*F E-P t F E-* (E) I i因为F,P