编译原理陈火旺第三版练习答案资料

《编译原理陈火旺第三版练习答案资料》由会员分享，可在线阅读，更多相关《编译原理陈火旺第三版练习答案资料（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 ：=