编译原理 第二章习题答案

第二章 文法和语言p48 4、6（6）、11、 12（2）（6）、18（2）4 证明文法G=（{E,O}，{(，)，+，*，v ，d}，P ，E ）是二义的,其中P 为 E → EOE | (E) | v | d O → + | * 证明：因为E=〉 EOE =〉EOEOE =〉EOEOv =〉EOE+v=〉EOv+v =〉E*v+v =〉v*v+v ， 句子v*v+v 有两棵不同的语法树所以文法G 是二义的。

问题：1）只有文字说明，比如v*v+v 有两棵语法树，但没有画出语法树或者最左（最右）推导过程2）给出的是不同句子（v*v+d v+v*d ）的语法树 6、已知文法G ：EEEE OO v*v+ vE EE E O O v+v* v〈表达式〉∷=〈项〉|〈表达式〉+〈项〉〈项〉∷=〈因子〉|〈项〉*〈因子〉〈因子〉∷=（〈表达式〉）| i试给出下述表达式的推导及语法树（6）i+i*i推导过程：〈表达式〉=〉〈表达式〉+〈项〉E=〉E+T =〉〈表达式〉+〈项〉*〈因子〉=〉E+ T*F=〉〈表达式〉+〈项〉* i =〉E+ T*i=〉〈表达式〉+ 〈因子〉* i =〉E+F*i=〉〈表达式〉+ i* i =〉E+i*i=〉〈项〉+ i* i =〉T +i*i=〉〈因子〉+ i* i =〉F +i*i=〉i +i*i =〉i +i*i 共8步推导语法树：〈表达式〉+〈因子〉〈项〉i 〈因子〉i〈项〉〈项〉〈因子〉i*11、一个上下文无关文法生成句子abbaa的推导树如下：（1）给出该句子相应的最左推导和最右推导（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有短语、简单短语、句柄。

（1）最左推导：S=〉ABS=〉aBS=〉aSBBS=〉aBBS=〉abBS=〉abbS =〉abbAa=〉abbaa最右推导：S =〉ABS=〉ABAa=〉ABaa=〉ASBBaa=〉ASBbaa=〉ASbbaa=〉Abbaa=〉abbaa（2）该文法的产生式集合P可能有下列元素：S→ABS | Aa|εA→a B→SBB|b（3）因为字符串中的各字符有相对的位置关系，为了能相互区别，给相同的字符标上不同的数字。

第二章 高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。

（2） 优先顺序为↑，+，*，同级优先采用右结合。

解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为 N →D|NDD →0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L （G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。

解：（1）L （G6）=｛a|a ∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N ＝＞ND ＝＞ NDD ＝＞ NDDD ＝＞ DDDD ＝＞ 0DDD ＝＞ 01DD ＝＞ 012D ＝＞ 0127 N ＝＞ ND ＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N ＝＞ ND ＝＞ DD ＝＞ 3D ＝＞ 34 N ＝＞ ND ＝＞ N4＝＞ D4 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →1|3|5|7|9, M →MB|1|2|3|4|5|6|7|8|9 B →0|1|2|3|4|5|6|7|8|9 8. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。

第二章 词法分析2.1 完成下列选择题：(1) 词法分析器的输出结果是。

a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值(2) 正规式M1和M2等价是指。

a. M1和M2的状态数相等b. M1和M2的有向边条数相等c. M1和M2所识别的语言集相等d. M1和M2状态数和有向边条数相等(3) DFA M(见图2-1)接受的字集为。

a. 以0开头的二进制数组成的集合b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合d. 含偶数个0的二进制数组成的集合【解答】(1) c (2) c (3) d图2-1 习题2.1的DFA M2.2 什么是扫描器？扫描器的功能是什么？【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。

每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下：f(x,a)={x,y} f {x,b}={y}f(y,a)=Φ f{y,b}={x,y}试构造相应的确定有限自动机M ′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题2.3的NFA M 用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

表2-2 状态转换矩阵将图2-3所示的DFA M ′最小化。

第2章习题解答1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2.文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D……D3.已知文法G[S]:Sf dAB Af aA|a B|bB问：相应的正规式是什么？G[S]能否改写成为等价的正规文法? [答案]正规式是daa*b* ；相应的正规文法为(由自动机化简来):G[S]:S —dA A —a|aB B —aB|a|b|bC C —bC|b也可为(观察得来):G[S]:S —dA A —a|aA|aB B —bB| &4.已知文法G[Z]:Z->aZb|ab写出L(G[Z])的全部元素。

[答案]Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={a n b n|n>=1}5.给出语言｛a n b n c1 n>=1,m>=0｝的上下文无关文法。

［分析］本题难度不大，主要是考上下文无关文法的基本概念。

上下文无关文法的基本定义是：A-> B ,A € Vn ,B€( VnU Vt) *,注意关键问题是保证a n b n的成立，即“ a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。

［答案］构造上下文无关文法如下：S->AB|AA->aAb|abB->Bc|c［扩展］凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。

基本思路是这样的：要求符合a n b n c m，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而c m做为另一个单位，初步产生式就应写为S->AB,其中A推出a n b n，B推出c m。

第二章3.何谓“标志符”，何谓“名字”，两者的区别是什么答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。

4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值。

（1）优先顺序（从高到低）为+、*和↑，同级优先采用左结合。

（2）优先顺序为↑、+、*，同级优先采用右结合。

答：（1）1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256（2）1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=86.令文法G6为N-〉D|NDD-〉0|1|2|3|4|5|6|7|8|9（1）G6的语言L（G6）是什么（2）给出句子0127、34、568的最左推导和最右推导。

答：（1）由0到9的数字所组成的长度至少为1的字符串。

即：L（G6）={d n|n≧1,d∈{0,1,…,9}}（2）0127的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 0127的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127（其他略）7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。

答：G（S）：S->+N|-NN->ABC|CC->1|3|5|7|9A->C|2|4|6|8B->BB|0|A|ε［注］：可以有其他答案。

［常见的错误］：N->2N+1原因在于没有理解形式语言的表示法，而使用了数学表达式。

8.令文法为E->T|E+T|E-TT->F|T*F|T/FF->(E)|i(1)给出i+i*i、i*(i+i)的最左推导和最右推导。

(2)给出i+i+i、i+i*i和i-i-i的语法树，并给出短语，简单短语和句柄。

第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）{a n b n|n≥0}；（2）{a n b m c p|n,m,p≥0}；（3）{a n#b n|n≥0}∪{c n#d n|n≥0}；（4）{w#w r# | w∈{0,1}*,w r是w的逆序排列 }；（5）任何不是以0打头的所有奇整数所组成的集合；（6）所有由偶数个0和偶数个1所组成的符号串的集合。

2-3 试描述由下列文法所产生的语言的特点：（1）S→10S0S→aA A→bA A→a（2）S→SS S→1A0A→1A0A→ε（3）S→1A S→B0A→1A A→CB→B0B→C C→1C0C→ε（4）S→aSS S→a2-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|fC→c AB|dSD|a D→eA E→fA|g(3) S→ac|bA A→c BC B→SA C→bC|d2-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|0B2-3 解：(1) 本文法构成的语言集为：L(G)={(10)n ab m a0n|n,m≥0}。