《编译原理课后习题答案(参考)》由会员分享，可在线阅读，更多相关《编译原理课后习题答案(参考)（23页珍藏版）》请在金锄头文库上搜索。
1、1第 2 章参考答案：1，2，3：解答：略！4. 解答：A： B： C： D： 5. 解答：用 E 表示 ，T 表示 ，F 表示，上述文法可以写为：E T | E+TT F | T*FF (E) | i最左推导：E=E+T=E+T+T=T+T+T=F+T+T=i+T+T=i+F+T=i+i+T=i+i+F=i+i+iE=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i最右推导：E=E+T=E+F=E+i=E+T+i=E+F+i=E+i+i=T+i+i=F+i+i=i+i+iE=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i =i+i
2、*ii+i+i 和 i+i*i 的语法树如下图所示。i+i+i、i+i*i 的语法树6. 解答：(1) 终结符号为：or,and,not,(,),true,false非终结符号为：bexpr,bterm,bfactor开始符号为：bexpr(2) 句子 not(true or false)的语法树为：27. 解答：(1) 把 anbnci 分成 anbn 和 ci 两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S ABA aAb|abB cB|(2) 令 S 为开始符号，产生的 w 中 a 的个数恰好比 b 多一个，令 E 为一个非终结符号，产生含相同个数的 a 和 b 的所有
3、串，则产生式如下： S aE|Ea|bSS|SbS|SSbE aEbE|bEaE|(3) 设文法开始符号为 S，产生的 w 中满足|a| |b| 2|a|。因此，可想到 S 有如下的产生式 （其中 B 产生 1 到 2 个 b）： S aSBS|BSaSB b|bb(4) 解法一：S 奇数头 整数 奇数尾| 奇数头 奇数尾| 奇数尾 奇数尾 1|3|5|7|9奇数头 2|4|6|8| 奇数尾 整数 整数 数字|数字数字 0|奇数头解法二：文法 G=(S,A,B,C,D,0,1,2,3,4,5,6,7,8,9,P,S)SAB | BAAC | DB1|3|5|7|9D2|4|6|8|BC0|D(
4、5) 文法 G=(N,S,N,M,D,0,1,2,3,4,5,6,7,8,9 ,S,P)SN0 | N53NMD|M1|2|3|4|5|6|7|8|9DD0 | DM |(6) GS：SaSa | bSb | cSc | a | b | c |8. 解答：(1) 句子 abab 有如下两个不同的最左推导：S = aSbS = abS =abaSbS = ababS = ababS = aSbS = abSaSbS = abaSbS = ababS = abab所以此文法是二义性的。(2) 句子 abab 的两个相应的最右推导：S = aSbS = aSbaSbS = aSbaSb = aSba
5、b = ababS = aSbS = aSb = abSaSb = abSab = abab(3) 句子 abab 的两棵分析树： (a) (b)(4) 此文法产生的语言是：在a，b上由相同个数的 a 和 b 组成的字符串。9，10：解答：略！第 3 章习题解答：1. 解答：(1) (2) (3) (4) (5) (6) 2. 分析有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现在映射：QV T q 是单值函数，也就是说，对任何状态 qQ 和输入字符串 aV T， (q,a)唯一确定下一个状态。显然，本题给出的是一个确定的有限自动机，它的状态转换图是 C 中的。它所接
6、受的语言可以用正则表达式表示为 00(0|1)*，表示的含义为由两个 0 开始的后跟任意个（包含 0 个）0 或 1 组成的符号串的集合。 2. 解答：A: B: C: D: E: 3，4解答：略！5解答：46解答：(1) (0|1)*01(2) (1|2|9)(0|1|2|9)*| )(0|5)(3) (0|1)*(011)(0|1)*(4) 1*|1*0(0|10)*(1|) (5) a*b*c*z*(6) (0|10*1)*1(7) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*(8) 分析 设 S 是符合要求的串，|S|=2k+1 (k0） 。则 SS
7、 10|S21，|S 1|=2k (k0） ，|S 2|=2k (k0） 。且 S1是0,1上的串，含有奇数个 0 和奇数个 1。S2是0,1上的串，含有偶数个 0 和偶数个 1。考虑有一个自动机 M1接受 S1，那么自动机 M1如下：和 L(M1)等价的正规式，即 S1为：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*类似的考虑有一个自动机 M2接受 S2，那么自动机 M2如下：和 L(M2)等价的正规式，即 S2为：(00|11)|(01|10)(00|11)*(01|10)*因此，S 为：(00|11)|(01|10)(00|11)*(01|
8、10)*(01|10)(00|11)*0|(00|11)|(01|10)(00|11)*(01|10)*17解答：(1) 以 0 开头并且以 0 结尾的，由 0 和 1 组成的符号串。(2) |0,1 *(3) 由 0 和 1 组成的符号串，且从右边开始数第 3 位为 0。(4) 含 3 个 1 的由 0 和 1 组成的符号串。 |0,1 +，且 中含有 3 个 1 (5) 包含偶数个 0 和 1 的二进制串，即 |0,1 *，且 中有偶数个 0 和 1 8. 解答：0 1Q0*Q1Q2Q3Q2Q3Q0Q1Q1Q0Q3Q259. 解答：(1) DFA M=(0，1，q 0，q 1，q 2，q
9、0，q 2， )其中定义如下: (q0，0)=q 1 (q0，1)=q 0 (q1，0)=q 2 (q1，1)=q 0 (q2，0)=q 2 (q2，1)=q 0状态转换图为：(2) 正规式: 1 *01*01*01* DFA M=(0，1，q 0，q 1，q 2，q 3，q 0，q 3，) ，其中 定义如下： (q0，0)=q 1 (q0，1)=q 0 (q1，0)=q 2 (q1，1)=q 1 (q2，0)=q 3 (q2，1)=q 2 (q3，1)=q 3 状态转换图为：10. 解答：(1) DFA M=(0，1，q 0，q 1，q 2，q 3，q 0，q 3， )，其中定义如下： (q
10、0，0)=q 1 (q0，1)=q 2 (q1，0)=q 1 (q1，1)=q 3 (q2，0)=q 3 (q2，1)=q 1状态转换图为：6(2) DFA M=(0，1，q 0，q 0，q 0， )，其中定义如下: (q0，0)=q 0 (q0，1)=q 0状态转换图为：11 解答：(1) (a|b)*a(a|b) 求出 NFA M:确定化，得到 DFA M:化简: 在第步中求出的 DFA M 中没有等价状态，因此它就是最小化的 DFA M。(2) (a)b)*a(a|b)(a|b) 求 NFA M： 确定化，得到 DFA M：化简，在第步中求出的 DFA M 中没有等价状态，因此它已经是最
11、小化的 DFA M了。12.解答：对应的 NFA 为：7增加状态 X、Y，再确定化：I Ia Ibx,5 A,T,Y A,T,Y A,T,Y BB B,T,YB,T,Y T,YT,Y 得到的 DFA 为：最小化：该自动机已经是最小化的 DFA 了。13解答：其中 a 代表 1 元硬币，b 代表 5 角硬币14解答：正规式为：(0|1) *(00|01) 化简：(0|1) *0(0|1)不确定的有穷自动机为：确定化，并最小化得到：8正规文法为：S1S | 0AA0B | 0 | 1C | 1B0B | 0 | 1C | 1C1S | 0A15.解答： 正规式： (dd*:| )dd*(.dd*|
12、 )，d 代表 az 的字母 NFA 为： DFA 为：16.解答：词法分析器对源程序采取非常局部的观点，因此象 C 语言的语句fi (a = f (x) ) 中，词法分析器把 fi 当作一个普通的标识符交给编译的后续阶段，而不会把它看成是关键字 if 的拼写错。PASCAL 语言要求作为实型常量的小数点后面必须有数字，如果程序中出现小数点后面没有数字情况，它由词法分析器报错。17. 解答：此时编译器认为/* then part return qelse/* else part */是程序的注释，因此它不可能再发现 else 前面的语法错误。分析 这是注释用配对括号表示时的一个问题。注释是在词
13、法分析时忽略的，而词法分析器对程序采取非常局部的观点。当进入第一个注释后，词法分析器忽略输入符号，一直到出现注释的右括号为止，由于第一个注释缺少右括号，所以词法分析器在读到第二个注释的右括号时，才认为第一个注释处理结束。为克服这个问题，后来的语言一般都不用配对括号来表示注释。例如 Ada 语言的注释9始于双连字符（-） ，随行的结束而终止。如果用 Ada 语言的注释格式，那么上面函数应写成long gcd(p,q)long p,q;if (p%q = 0)- then part return qelse- else part return gcd(q, p%q);18. 解答：略！第 4 章习
14、题 解答：1，2，3，4 解答 略！5. 解答：(1) (2) (3) (4) (5) (6) (7) (8)6. 解答：(1)A： B： C： D： E：(2)A： B： C： D： E：7.解答：(1) 消除给定文法中的左递归，并提取公因子：bexprbterm or bterm btermbfactor and bfactor bfactornot bfactor | (bexpr) | true |false (2) 用类 C 语言写出其递归分析程序: void bexpr();bterm();WHILE(lookahead =or) match (or);bterm();void bterm();bfactor();WHILE(lookahead =and)match (and);bfactor();void bfactor();if (llokahead=not) then match (not);bfactor();else if(lookahead=() then match ();bexpr();match();else if(lookahead =true) then
