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

>

2-1 设有字母表A1 ={a,b,c,…,z}，A2 ={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个 (2) 集合A1A2含有多少个元素

(3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。

2-2 试分别构造产生下列语言的文法： （1）{ab|n≥0}；

{

nn

（2）{abc|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所组成的符号串的集合。

n

mp

2-3 试描述由下列文法所产生的语言的特点： （1）S→10S0 S→aA A→bA A→a

\\

（2）S→SS S→1A0 A→1A0 A→ε （3）S→1A S→B0 A→1A A→C

B→B0 B→C C→1C0 C→ε （4）S→aSS S→a

2-4 试证明文法

S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab 为二义性文法。

)

2-5 对于下列的文法

S→AB|c A→bA|a B→aSb|c

试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。

2-6 化简下列各个文法

(1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c (2) S→aAB|E A→dDA|e B→bE|f

￥

C→cAB|dSD|a D→eA E→fA|g

(3) S→ac|bA A→cBC B→SA C→bC|d

2-7 消除下列文法中的ε-产生式 (1) S→aAS|b A→cS|ε (2) S→aAA A→bAc|dAe|ε

2-8 消除下列文法中的无用产生式和单产生式

—

(1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B (2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ] (3) E→E+T|T T→T*F|F F→P↑F|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},{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|0B

2-3 解：

(1) 本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。

(2) L(G)={1n0n |n≥0}+，该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同的连续的0。

(3) 本文法构成的语言集为：L(G)={110|p≥1,n≥0}∪{100|q≥1,n≥0}，特点是具有110 或100形式，进一步，可知其具有形式{10|n,m≥0,且n+m>0}。

)

pnnnnq

pnnnnqnm

(4)由L(G)={a|n≥1}可知，该语言特点是：产生的句子是奇数个a。

2n-1

2-4 证明：

因为存在句子：abc，它对应两个最右推导：

S S

AB Abc abc DC Dc abc

所以，本文法具有二义性。

:

2-5 解：

句子bbaacb的最右推导为：

S AB AaSb Aacb bAacb bbAacb bbaacb

上面推导中，下划线部分为当前句型的句柄。

与句子bbaacb相应的语法树为：

]

全部的短语为：

第一个a（a）是句子bbaacb相对于非终结符A (A) (产生式A→a）的短语（直接短语）；

ba是句子bbaacb相对于非终结符A的短语； 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)的短语； 注：符号的上标是为了描述方便加上去的。

.

(1)(1)

(1)(1)(2)

2-6 解：

(1) 因为由非终结符号B推导不出终结符号串，因此B是无用符号，含有B的产生式B→Bab,B→cSB, S→aABS和A→bAB都是无用产生式，应予以删除。

因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为

S→bCACd A→cSA|cCC C→cS|c

(2) 因为由文法的开始符号推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式C→cAB|dSD|a都是无用产生式，也应予以删除。

因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为

S→aAB|E A→dDA|e B→f D→eA E→fA|g

)

(3) 因为由非终结符号A,B推导不出终结符号串，因此A,B是无用符号，删除含有

A,B的产生式S→Ba, A→cBC和B→SA后得到文法G′[S]:

S→ac C→bC|d

又因为由文法G′[S]的开始符号S推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式C→bC|d都是无用产生式，也应予以删除。

因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法G〞[S]为 S→ac

2-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′： 对于产生式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|a A→bAc|bc|dAe|de

2-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|BC A→aA|c|aDb B→DB C→b