编译原理第二章 习题与答案(修改后)

第2章 习题

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→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)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特点是具有1p1n0n 或1n0n0q形式，进一步，可知其具有形式{1n0m|n,m≥0,且n+m>0}。

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

2-4 证明：

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

S ? AB ? Abc ? abc S ? DC ? Dc ? abc

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

2-5 解：

句子bbaacb的最右推导为：

S ? AB ? AaSb ? Aacb ? bAacb ? bbAacb ? bbaacb

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

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

,

S(2)A(3)Bb (2)A (2)a (2)S(1)b (3)cb (1)A (1)a (1)答案图2-5

全部的短语为：

第一个a（a）是句子bbaacb相对于非终结符A (A) (产生式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→bCACd A→cSA|cCC C→cS|c

(1)

(1)