《编译原理(第3版)课本习题答案》由会员分享，可在线阅读，更多相关《编译原理(第3版)课本习题答案（7页珍藏版）》请在金锄头文库上搜索。
1、1第二章 高级语言及其语法描述6 （1）L（G 6）=0,1,2,.,9 +（2）最左推导：N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127N=ND=DD=3D=34N=ND=NDD=DDD=5DD=56D=568最右推导：N=ND =N7=ND7=N27=ND27=N127=D127=0127N=ND=N4=D4=34N=ND=N8=ND8=N68=D68=5687 【答案】：SABC | AC | CA1|2|3|4|5|6|7|8|9BBB|0|1|2|3|4|5|6|7|8|9C1|3|5|7|98 （1）最左推导：E=E+T=T+T=F+T=i+T=i+T
2、*F=i+F*F=i+i*F=i+i*iE=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+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i=i+i*iE=T=T*F=T*(E)=T*(E+T)=T*(E+F)=T*(E+i)=T*(T+i)=T*(F+i)=T*(i+i)=F*(i+i)=i*(i+i)(2)9证明：该文法存在一个句子 iiiei 有两棵不同语法分析树，如下所示，因此该文法是二义的。E+ TTFiEE + TFiFiE+ TFiET * FiFiT
3、E- TTFiEE - TFiFiSS ei Si SSiiSei SiSiSi210.【答案】无二义文法为： 11. 【答案】第 3 章 词法分析7构造下列正规式相应的 DFA：(1) 1(0|1)*101解：（1）构造 NFA：0X1 5 2 Y0,113 411（2）确定化：构造状态转换矩阵如下： 重命名：I I0 I1X - 1,5,21,5,2 5,2 5,3,25,2 5,2 5,3,25,3,2 5,4,2 5,3,25,4,2 5,2 5,Y,3,25,Y,3,2 5,4,2 5,3,2(3)化简 (4)化简之后的状态表 分组0,1,2,3,4 5考察0,1,2,3,4 0=2
4、,4 0,1,2,3,41=1,3,5 分化为：0,1,2,3、4、5再考察：0,1,2,3 0=2,4 分化为：0,1,2,、3、4、5再考察：0,1,2 0=2 0,1,21=1,3 分化为：0、1,2,、3、4、5(5)画出状态转换图：S 0 10 - 11 2 32 2 33 4 34 2 55 4 3S 0 10 - 11 1 22 3 23 1 44 3 2G1:SABAaAb|abBcB|G2:SABAaA|BbBc|bcG3:SAAAaAb|G4:S1S0|AA0A1|STS|TT(S)|()30 1 210130104101(3) 0*10*10*10*解：（1）构造 NFA
5、：（2）确定化：构造状态转换矩阵如下： 重命名：I I0 I1X,7,1 7,1 2,8,37,1 7,1 2,8,32,8,3 8,3 4,9,58,3 8,3 4,9,54,9,5 9,5 6,10,Y9,5 9,5 6,10,Y6,10,Y 10,Y -10,Y 10,Y -(3)化简 如上表所示：0,1、2,3、4,5、6,7化简后的状态表为：（4）最简 DFA 状态转换图0 1 2 31 110 00 08 （1） （0|1） *01S 0 10 1 21 1 22 3 43 3 44 5 65 5 66 7 -7 7 -S 0 10 0 11 1 22 2 33 3 -11 X 7
6、 1 2 Y8 3 4 9 5 6 101 0 0 0 04（2）=0，1，2，3，4，5，6，7，8，9(1|2|3|4|5|6|7|8|9） *(0|5)|（0|5）（3）1 *0(01*0)1) *0 *1(10*1)0) *（4）a *b*c*.z*(5) (x0 )(x1 ) (x2 ).(x9 ) =0,1,.,9其中 x0 xi- x 0,., xi-1 i=1,.,9(6) (x0 )y0(x1 )y1 (x2 )y2.(x9 )y9其中 x0 xi- x 0,., xi-1 i=1,.,9如果 ym ,则 yn= (m=0,.,9) (n=0,1,.,m-1,m+1,.,9)
7、其中 y0,.,y9 ,0,1,.,9(7) b*(aab) *9（1）正规式（0|1） *（010） （0|1） * NFA:0,1 0,10 1X 1 2 Y3 4 5 60 构造状态转换矩阵： 重命名： 最小化 化简后的状态表分组：0,1,2,3、4,5,6,7 考察：0,1,2,3 0=1,4 分化为 0,1,2、3、4,5,6,7再考察：0,1,2 0=1 0,1,21=2,3 分化为 0,2、1、3 、 4,5,6,7再考察：4,5,6,7 0=4,5 4,5,6,71=6,7 分化为 0,2、1、3 、 4,5,6,7再重新命名为：0,20、11、32、4,5,6,73I I0
8、I1X,1,2 1,3,2 1,21,3,2 1,3,2 1,4,21,2 1,3,2 1,21,4,2 1,5,3,2,6,Y 1,2|1,5,3,2,6,Y 1,3,6,2,Y 1,4,6,2,Y1,3,6,2,Y 1,3,6,2,Y 1,4,6,2,Y 1,4,6,2,Y 1,5,3,2,6,Y 1,6,2,Y1,6,2,Y 1,3,6,2,Y 1,6,2,YS 0 10 1 21 1 32 1 23 4 24 5 65 5 66 4 77 5 7S 0 10 1 01 1 22 3 03 3 35最小化后的状态转换图为：0011 201 010，13（2）正规式 1*（011111）*
9、1* 或 1*（0111*）*1* NFA: 101 1X 1 2 3 Y4 56 7 81 1构造状态转换矩阵： 重命名： 最小化 化简后的状态表分组：0,1,2,4,5,6,7、 3 考察：0,1,2,4,5,6,7 0=1 0,1,2,4,5,6,71=2,3,4,6,7 分化为 0,2,4,5,6,7、1、3再重新命名为：0,2,4,5,6,70、11、32最小化后的状态转换图为：12I I0 I1X,1,2,3,4,5,Y 3,4,5,Y 1,6,5,2,3,4,Y3,4,5,Y 3,4,5,Y 6,5,Y1,2,3,4,5,6,Y 3,4,5,Y 1,6,5,7,2,3,4,Y,8
10、6,5,Y 5,7,Y,8,3,41,2,3,4,5,6,7,8,Y 3,4,5,Y 1,6,5,7,8,2,3,4,Y 3,4,5,7,8,Y 3,4,5,Y 6,5,8,Y,3,43,4,5,6,8,Y 3,4,5,Y 6,5,7,8,Y,3,4 3,4,5,6,7,8,Y 3,4,5,Y 6,5,7,8,Y,3,4 S 0 10 1 21 1 32 1 43 - 54 1 45 1 66 1 77 1 7S 0 10 1 01 1 22 - 01210011016（a） aaa,bX 10Y构造状态转换矩阵： 重命名：I Ia IbX,0,Y 0,1,Y 10,1,Y 0,1,Y 11
11、0,Y 0,Y 0,1,Y 1化简： 重命名后的状态表：分化为：0,1,3、2 考察：0,1,3a = 1 0,1,3b = 2 分化为：0,1,3、2画出确定化后的有限自动机： 最小化的有限自动机： ababab120 3a（b）最少化：首先分为终态集和非终态集：0，1 、2，3，4，50，1a=10，1b=2，42，3，4，5a=1，3，0，5 可分为2，4 和3，52，4b=3，53，5b=2，4形成划分：0，12，43 ，5最少化后的 DFA：S a b0 1 21 1 22 3 3 1 2S a b0 0 11 0 aab1070a1 2babab14每个 1 都有 0 直接跟在右边：（10|0） *1010015画出 NFA：SBA0,1 10C1F1000,10,1等价的左线性正规文法：FA1|B0|C0|C1S0|1|S0|S1A1|S1B0|S0CA1|B0|C0|C1
