蒋立源 编译原理第三版第二章 习题与答案(修改后)
第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）{ab|n≥0}； （2）{abc|n,m,p≥0}；
（3）{a#b|n≥0}∪{c#d|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的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。
1 / 71 / 7
n
n
n
n
n
mpn
n
蒋立源 编译原理第三版第二章 习题与答案(修改后)
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)
2 / 72 / 7
蒋立源 编译原理第三版第二章 习题与答案(修改后)
(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}。
(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相应的语法树为：
pn
n
n
n
q
n
m
pnn
nn
q
3 / 73 / 7
蒋立源 编译原理第三版第二章 习题与答案(修改后)
