编译原理答案.docVIP

第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+m0}。 (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 上面推导中，下