《编译原理陈火旺第三版练习答案资料》由会员分享,可在线阅读,更多相关《编译原理陈火旺第三版练习答案资料(28页珍藏版)》请在金锄头文库上搜索。
1、第二章第二章 P-36-6 (1)L(G)是 09 组成的数字串; (2)最左推导: NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568 最右推导: NNDN7ND7N27ND27N127D1270127 NNDN4D434 NNDN8ND8N68D68568 P-36-7 G(S) : (没有考虑正负符号问题) SP|AP P1|3|5|7|9 AAD|N N2|4|6|8|P D0|N 或者: ()SC 13579 P-36-8 G(E) :ET|E+T|E-T TF|T*F|T/F F(E)|i 最左推导: EE+TT+
2、TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i ETT*FF*Fi*Fi*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)i*(i+F)i*(i+i) 最右推导: EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i ETT*FT*(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) 1 本文档由计算机吧【w w w . j s j 8 . c o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! 语
3、法树: E i+i+i E + T E + T T F i F i F i E E+T T F i T* F F i i i+i*i E i-i-i E - T E- T T F i F i F i P-36-9 句子:iiiei 有两个语法树: S iSeS iS i i S i S i S e S i i SiSeSiSeiiiSeiiiiei SiSiiSeSiiSeiiiiei 因此 iiiei 是二义性句子,因此 该文法是二义性的。 P-36-10 STS|T T(S)|() P-36-11P-36-11 L1: G(S): SAC AaAb|ab CcC| L2: G(S): SA
4、B AaA| BbBc|bc L3: G(S): SAB AaAb| BaAb| L4: G(S): S1S0|A A0A1| 或者:SA|B AB A0A1| B1B0|A 2 本文档由计算机吧【w w w . j s j 8 . c o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! 第三章第三章 (1) X Y 1(0|1)*101 0 X 1 Y 1 2 34 5 01 1 1 确定化: 0 1 X 1,2,3 1,2,3 2,3 2,3,4 2,3 2,3 2,3,4 2,3,4 2,3,5 2,3,4
5、 2,3,5 2,3 2,3,4,Y 2,3,4,Y 2,3,5 2,3,4 最小化:0,1,2,3,4,5,6 0,1,2,3,4,50=1,3,5 0,1,2,3,4,51=1,2,4,6 0,1,2,3,4,5,6 0,1,2,3,40=1,3,5 0,1,2,3,4,5,6 0,1,2,30=1,3 0,1,2,31=1,2,4 0,1,2,3,4,5,6 0,10=1 0,11=1,2 2,30=3 2,31=4 0,1,2,3,4,5,6 2 0 3 5 4 1 0 6 1 0 1 1 0 0 0 0 1 0 1 1 1 3 本文档由计算机吧【w w w . j s j 8 . c
6、 o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! 0 2 4 3 1 0 5 1 0 1 1 1 0 0 0 0 1 1 P64-8 (1) (0|1)*01 (2) (1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*(0|5)|(0|5) (3) 0*1(0|10*1)* | 1*0(1|01*0)* P84-12 (a) a 0 1 a,b a 确定化: a b 0 0,1 1 0,1 0,1 1 1 0 给状态编号: a B 0 1 2 1 1 2 2 0 3 3 3
7、3 4 本文档由计算机吧【w w w . j s j 8 . c o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! 0 1 2 3 a a a b b b b a 最小化: 0,1 2,3 0,1a=1,0,1b=2 2,3a=0,3,2,3=3 0,1,2,3 0 a 21 a a b b b (b) 已经确定化,只需最小化: 0,1,2,3,4,5 0,1a = 1 0,1b = 2,4 2,3,4,5a = 1,3,0,5 2,3,4,5b = 2,3,4,5 又:2,4a = 1,0 2,4b = 3,
8、5 3,5a=3,5 3,5b = 2,4 分划为:0,1,2,4,3,5 0,1a = 1 0,1b = 2,4 2,4a = 1,0 2,4b = 3,5 3,5a = 3,5 3,5b = 2,4 所以不能再分 0 a 21 a a b b b 5 本文档由计算机吧【w w w . j s j 8 . c o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! P64-14 正规式: (0|10)* 0 0 1 0 1 还可以: 然后再确定化,最小化,结果应该一样。 P65-15 首先构造 NFA: 0|1 则
9、有:G(f) fA1|B0|C1|C0 CC0|C1|A1|B0 AS1|1 BS0|0 SS0|S1| 或者是确定化,然后最小化: G(C) CC0|C1|A0|B1 A0|B0 B1|A1 fS C 0 A B 1 0 1 0 0 1 1 1 0 0 Y X 1 0 1 0 2 A S C B 0 1 0 1 1 0 0,1 1 6 本文档由计算机吧【w w w . j s j 8 . c o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! 人、狼、羊、白菜: M、W、G、C,表示在左岸,M、W、G、C在右岸
10、,将可能存在的状态中去掉不安全 ,M、W、G、C,M、W、G,C,M、W、C,G, G:表示人和羊过河、:表示人和狼过河、: 状态,剩下: M、W、G、C, M、G、C,W ,C,M、W、G ,G,M、W、C,W,M、G、C, M、G,W、C ,W,C,M、G 箭弧上的标记符:表示人单独过河、,E1.place,E2.place,0) ; emit(:=,E1.place,-,v.place) ; F.quad := nextquad; F.place1 := E2.place; F.place2 := entry(v) ; SF do S1 backpatch(S1.nextlist,F.q
11、uad) ; S.nextlist := merge(F.nextlist,makelist(nextquad) ) ; emit(j=,F.place1,F.place2,0); emit(+,F.place2,1,F.place2) ; emit(j,-,-,F.quad) 24 本文档由计算机吧【w w w . j s j 8 . c o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! 第十章第十章 P306-1: read C A :=0 B := 1 L1: A:=A+B if BC GOTO L2 B
12、 := B +1 GOTO L1 L2: wirte A halt B1 B2 B3 B4 read C A := 0 B := 1 L1: A := A + B if B C GOTO L2 B := B +1 GOTO L1 L2: write A halt P306-2 read A , B F := 1 C := A*A read A , B F := 1 C := A*A D := B*B if C 100 goto L2 halt L2:F := F+1 goto L1 B1 B2 B3 B4 B5 D := B*B if C 100 goto L2 halt L2:F := F+
13、1 goto L1 25 本文档由计算机吧【w w w . j s j 8 . c o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! P306-3 基本块: B1: A := B*C D := B/C E :=A+D F :=2*E G:=B*C H :=G*G F:=H*G L := F M :=L B2: B := 3 D := A+C E :=A*C G:=B*F H:=A+C I:=A*C J:=H+I K:= B*5 L:=K+J M:=L n9 F、L、M 如果只有 G、L、M 在 基本块后还要被引
14、 用,则优化为: n1 n2 2 C n3 * A,Gn4 / D n5 + E n6 n7 F * n8 * H * G :=B*C S1 :=G*G L := S1*G M := L (S1 为临时变量) 如果只有 L 在基本块后 还要被引用, 则优化为: S1 :=B*C S2 :=S1*S1 L := S2*S1 (S1、S2 为临时变量) B n3n2 n4 + D、 Hn5 * n8 + n10 K n9 J + 如果只有 G、L、M 在基本块 后还要被引用,则优化为: G :=3*F S1:=A+C S2:=A*C S3:=S1+S2 L := 15 + S3 (S1、S2、S3 为临时变量) L,M G 3 n1 * n7 n6 E、I如果只有 L 在基本块后还要 被引用,则优化为: S1:=A+C S2:=A*C S3:=S1+S2 L := 15 + S3 (S1、S2、S3 为临时变量) B 15 F AC 26 本文档由计算机吧【w w w . j s j 8 . c o m 】搜集,版权归原作者,不得用于商业活动! 更多计算机考研资料请大家到:w w w . j s j 8 . c o m 下载! P307-4 对一下四元式程序,对其中循环进行循环优化: I :=1 read J,K L: A :=K* I B :=