《编译原理第三版课后习题解答--修订编选》由会员分享，可在线阅读，更多相关《编译原理第三版课后习题解答--修订编选（27页珍藏版）》请在金锄头文库上搜索。
1、第二章习题解答第二章习题解答 P36-6P36-6 (1) 是 09 组成的数字串 L G() 1 (2) 最左推导: 568565 343 0127012010 DDDDDDNDDNDN DDDNDN DDDDDDDDDDNDDDNDDNDN 最右推导: NNDNNDNNDND NNDND NNDNNDND 7727271271270127 4434 886868568 P36-7P36-7 G(S) O NO DN SO AO AAD N 1357 9 2 4 68 0 | | | | | | | | | | | P36-8P36-8 文法： ET ET ET TF TF TF FE i
2、| |*|/ ( )| 最左推导: EETTTFTiTiTFiFFiiFii i ETTFFFiFiEiETiTTiFT iiTiiFiii * *()*()*()*() *()*()*() 最右推导: EETETFET iEF iEi iTi iFi iii i ETF TFFFEFETFEFFEi FTiFFiFiiiii * *()*()*()*() *()*()*()*() 语法树：/* E EF TE+ T F F T + i i i E EF TE- T F F T - i i i E E F T+ T F F T i i i * i+i+ii-i-ii+i*i */ P36-9P
3、36-9 句子 iiiei 有两个语法树： SiSeSiSeiiiSeiiiiei SiSiiSeSiiSeiiiiei P36-10P36-10 /* )( | )( | ST TTSS */ P36-11P36-11 /* L1: | | cCC abaAbA ACS L2: bcbBcB aAA ABS | | L3: | | aBbB aAbA ABS L4: ABB AA BAS |01 |10 | */ 第三章习题参考答案第三章习题参考答案 P647P647 (1) 1 01 101( | )* 0 1 1 0 1 1 确定化： 01 X1,2,3 1,2,32,32,3,4 2,
4、32,32,3,4 2,3,42,3,52,3,4 2,3,52,32,3,4,Y 2,3,4,Y2,3,52,3,4, 0 1 0 0 0 1 1 0 0 1 0 1 1 1 最小化： X1234Y5 XY 6 0 1 23 54 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 012 34 56 012 34 5135012 34 512 4 6 012 3456 012 34135 012 3456 012 31 01 0 0 3012 312 4 012 3 45
5、6 0110112 2 332 34 012 3456 1 01 01 , , , , , , , , , , , , , , , , , , , , , 0 1 0 0 1 0 0 1 0 1 1 1 P648P648 (1) 01)0|1 ( * (2) )5|0( | )5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1 ( * (3) * ) 110|0(01|) 110|0( 10 P6412P6412 (a) a a,b a 确定化： ab 00,11 0,10,11 10 5 0 1 2 43 01 给状态编号： ab 012 112 203
6、333 a a a b b b b a 最小化： , , , , , , , , , , , 012 3 011012 2 30 32 33 0123 ab ab a a b b a b (b) b b a a b a a b b a a a 已经确定化了,进行最小化 01 23 0 12 023 145 最小化： , , , , , 0 12 3 4 5 0 110 12 4 2 3 4 51 3 0 52 3 4 52 3 4 5 2 41 02 43 5 3 53 53 52 4 0 12 43 5 0 110 12 4 2 4 , , , , , , , , , , , , , , ,
7、 , , , , , , , , , , , , , , , , , ab ab ab ab ab a , , , , , , , 1 02 43 5 3 53 53 52 4 b ab b b a a b a P6414P6414 (1) 0 1 0 (2): ( |)*010 0 1 0 确定化： 01 X,1,Y1,Y2 012 01 YX YX 2 1 1,Y1,Y2 21,Y 给状态编号： 01 012 112 213 333 0 0 1 0 1 1 1 0 最小化： , , , , , , , , , , , 0 12 3 0 110 12 2 31 32 33 0 123 01
8、01 0 1 1 1 0 0 第四章第四章 P811P811 (1) 按照 T,S 的顺序消除左递归 |, )( | )( TST TST TaS SG 递归子程序： procedure S; begin if sym=a or sym= then abvance else if sym=( 0 2 1 3 013 then begin advance;T; if sym=) then advance; else error; end else error end; procedure T; begin S;T end; procedure T; begin if sym=, then beg
9、in advance; S;T end end; 其中: sym:是输入串指针 IP 所指的符号 advance:是把 IP 调至下一个输入符号 error:是出错诊察程序 (2) FIRST(S)=a,( FIRST(T)=a,( FIRST(T)=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOW(T)=) 预测分析表 a(),# SSaS ST ( ) TTSTTSTTST T T TST, 是 LL(1)文法 P812P812 文法： | )( |* | | baEP FF FPF TT TFT EE ETE (1) FIRST(E)=(,a,b, FIRST(E)=
10、+, FIRST(T)=(,a,b, FIRST(T)=(,a,b, FIRST(F)=(,a,b, FIRST(F)=*, FIRST(P)=(,a,b, FOLLOW(E)=#,) FOLLOW(E)=#,) FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=(,a,b,+,),# FOLLOW(F)=(,a,b,+,),# FOLLOW(P)=*,(,a,b,+,),# (2) 考虑下列产生式: EE TT FF PEa b | | *| ()| | FIRST(+E)FIRST()=+= FIRST(+E)FOLLOW(E)=+#,)= FIRST(T
11、)FIRST()=(,a,b,= FIRST(T)FOLLOW(T)=(,a,b,+,),#= FIRST(*F)FIRST()=*= FIRST(*F)FOLLOW(F)=*(,a,b,+,),#= FIRST(E)FIRST(a) FIRST(b) FIRST()= 所以,该文法式 LL(1)文法. (3) +*()ab# EETEETE ETE ETE E EE E E TTFT TFTTFTTFT T T TT T TT TT TT T F FPFFPF FPF FPF F F FF* F F F F F F PPE ()PaPbP (4) procedure E; begin if
12、sym=( or sym=a or sym=b or sym= then begin T; E end else error end procedure E; begin if sym=+ then begin advance; E end else if sym) and sym# then error end procedure T; begin if sym=( or sym=a or sym=b or sym= then begin F; T end else error end procedure T; begin if sym=( or sym=a or sym=b or sym= then T else if sym=* then error end procedure F; begin if sy
