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

2-1设有字母表A1={a,b,c,…,z}，A2={0,1,…,9}，试回答下列问题：(1)字母表A1上长度为2的符号串有多少个？(2)集合A1A2含有多少个元素？(3)列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。2-2试分别构造产生下列语言的文法：（1）{anbn|n≥0}；（2）{anbmcp|n,m,p≥0}；（3）{an#bn|n≥0}∪{cn#dn|n≥0}；（4）{w#wr#|w∈{0,1}*,wr是w的逆序排列}；（5）任何不是以0打头的所有奇整数所组成的集合；（6）所有由偶数个0和偶数个1所组成的符号串的集合。2-3试描述由下列文法所产生的语言的特点：（1）S→10S0S→aAA→bAA→a（2）S→SSS→1A0A→1A0A→ε（3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε（4）S→aSSS→a2-4试证明文法S→AB|DCA→aA|aB→bBc|bcC→cC|cD→aDb|ab为二义性文法。2-5对于下列的文法S→AB|cA→bA|aB→aSb|c试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。2-6化简下列各个文法(1)S→aABS|bCACdA→bAB|cSA|cCCB→bAB|cSBC→cS|c(2)S→aAB|EA→dDA|eB→bE|fC→cAB|dSD|aD→eAE→fA|g(3)S→ac|bAA→cBCB→SAC→bC|d2-7消除下列文法中的ε-产生式(1)S→aAS|bA→cS|ε(2)S→aAAA→bAc|dAe|ε2-8消除下列文法中的无用产生式和单产生式(1)S→aB|BCA→aA|c|aDbB→DB|CC→bD→B(2)S→SA|SB|AA→B|(S)|()B→[S]|[](3)E→E+T|TT→T*F|FF→P↑F|PP→(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},{S→aS|X,X→bX|Y,Y→cY|ε},S)(3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb|#,Y→cYd|#},S)(4)G(S)=({S,W,R},{0,1,#},{S→W#,W→0W0|1W1|#},S)(5)G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8,J→1|3|5|7|9},S)(6)对应文法为S→0A|1B|ε，A→0S|1C，B→0C|1S，C→1A|0B2-3解：(1)本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。(2)L(G)={1n0n|n≥0}+，该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同的连续的0。(3)本文法构成的语言集为：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特点是具有1p1n0n或1n0n0q形式，进一步，可知其具有形式{1n0m|n,m≥0,且n+m0}。(4)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。2-4证明：因为存在句子：abc，它对应两个最右推导：SABAbcabcSDCDcabc所以，本文法具有二义性。2-5解：句子bbaacb的最右推导为：SABAaSbAacbbAacbbbAacbbbaacb上面推导中，下划线部分为当前句型的句柄。与句子bbaacb相应的语法树为：全部的短语为：第一个a（a(1)）是句子bbaacb相对于非终结符A(A(1))(产生式A→a）的短语（直接短语）；b(1)a(1)是句子bbaacb相对于非终结符A(2)的短语；b(2)b(1)a(1)是句子bbaacb相对于非终结符A(3)的短语；c是句子bbaacb相对于非终结符S(1)（产生式S→c）的短语（直接短语）；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的产生式B→Bab,B→cSB,S→aABS和A→bAB都是无用产生式，应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为S→bCACdA→cSA|cCCC→cS|c(2)因为由文法的开始符号推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式C→cAB|dSD|a都是无用产生式，也应予以删除。因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为S→aAB|EA→dDA|eB→fD→eAE→fA|g(3)因为由非终结符号A,B推导不出终结符号串，因此A,B是无用符号，删除含有A,B的产生式S→Ba,A→cBC和B→SA后得到文法G′[S]:S→acC→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|bA→cS(2)对于G，我们可得到W={A}；再按如下步骤得到产生式集P′：对于产生式S→aAA，将产生式S→aAA及S→Aa和S→a放入P′；对于产生式A→bAc，将产生式A→bAc及A→bc放入P′；对于产生式A→dAe，将产生式A→dAe及A→de放入P′。于是得到消除ε-产生式后的文法为：S→aAA|aA|aA→bAc|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′中：S→aB|BCA→aA|c|aDbB→DBC→b因为C∈W(B)，故将C的所有非单产生式的右部作为B-产生式的右部添加到P′中：B→b因为B∈W(D)，故将B的所有非单产生式的右部作为D-产生式的右部添加到P′中：D→DB因为C∈W(D)，故将C的所有非单产生式的右部作为D-产生式的右部添加到P′中：D→b由此得到消除单产生式后的文法如下：S→aB|BCA→aA|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)={B}然后按如下步骤得到产生式集P′：将P中的所有非单产生式添加到P′中：S→SA|SBA→(S)|()B→[S]|[]因为A∈W(S)，故将A的所有非单产生式的右部作为S-产生式的右部添加到P′中：S→(S)|()因为B∈W(S)，故将B的所有非单产生式的右部作为S-产生式的右部添加到P′中：S→[S]|[]因为B∈W(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)={F,P},W(P)={P}然后按如下步骤得到产生式集P′：将P中的所有非单产生式添加到P′中：E→E+TT→T*FF→P↑FP→(E)|i因为T,F,P∈W(E)，故将T,F,P的所有非单产生式的右部作为E-产生式的右部添加到P′中：E→T*FE→P↑FE→(E)|i因为F,P∈W(T)，故将F,P的所有非单产生式的右部作为T-产生式的右部添加到P′中：T→P↑FT→(E)|i因为P∈W(F)，故将P的所有非单产生式的右部作为F-产生式的右部添加到P′中：F→(E)|i由此得到消除单产生式后的文法如下：E→E+T|T*F|P↑F|(E)|iT→T*F|P↑F|(E)|iF→P↑F|(E)|iP→(E)|i