程序設(shè)計(jì)語(yǔ)言編譯原理第3版課后答案（精編版）

1、.優(yōu)選 .p36-6第二章(1)l( g1) 是 09 組成的數(shù)字串(2)最左推導(dǎo) :nndnddnddddddd0 ddd01dd012 d0127nnddd3d34nndnddddd最右推導(dǎo) :5dd56d568nndn 7nd 7n 27nd 27n 127d1270127nndn 4d 434nndn 8nd 8n 68d 68568p36-7g(s)o n d1|3|5|7| 92|4|6|8|o0| nso| aoaad | np36-8文法：et| et| ettf | t * f | t / ff( e )|i最左推導(dǎo) :eetttftitit *fif *fii *fii *

2、 iett *ff * fi *fi *( e )i *(et )i *(tt )i *(ft )i *(it )i *( if )i *(ii )最右推導(dǎo) :eetet *fet * ief * iei* iti * ifi* iii * ietf * tf *ff *( e )f *(et )f *(ef )f *(ei )f *(ti )f *(fi )f *(ii )i *(ii )語(yǔ)法樹(shù)： /*e+te+te-te+tftt*fe-tftfiffitfifiiifieeeiii+i+ii-i-ii+i*i*/p36-9句子 iiiei 有兩個(gè)語(yǔ)法樹(shù)：sisesiseiiiseiiii

3、eisisiisesiiseiiiieip36-10/*sts | tt( s) | ( )*/p36-11/* l1:sacaaab | abcl2:scc |aba bl3:aa | bbc | bcs a bl4:s a babaab | abb |a | b 0 a1|1b0 | a*/p647(1)第三章習(xí)題參考答案1(0|1)* 101xy01101x12345y1確定化：x1,2,32,32,3,42,3,52,3,4,y0 2,32,32,3,52,32,3,511,2,32,3,42,3,42,3,42,3,4,y2,3,4,001203001101405106111最小化：

4、 0,1,2,3,4,5, 6 0,1,2,3,4,51,3,5 0,1,2,3,4,51,2,4,601 0,1,2,3,4, 5, 6 0,1,2,3,41,3,50 0,1,2,3, 4, 5, 6 0,1,2,31,30,1,2,31,2,4 0,1,02,34,15, 6 0,11 0,1 1,201 2,3 3 2,3401 0, 1, 2,3, 4, 5, 6001200101304105111p648(1)(1 | 0)* 01(2)(1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)( 0 |1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

5、)* (0 | 5) | (0 | 5)(3)0 *1(0 | 10* 1) * | 1* 0(0 | 10* 1) *p6412(a)aa,b01a確定化：00,11a0,10,10b11給狀態(tài)編號(hào)：ab012112203333aa01abbb2b3a最小化： 0,1, 0,1 a 2,3 a2,310,1 b 0,3 2,3 b 23 0,1, 2, 3aabb012ab(b)bba023abaabbaa14a5已經(jīng)確定化了 ,進(jìn)展最小化最小化： 0,1, 0,1 a2, 3,4, 51 0,1 b 2, 4 2, 3,4 ,5 a 1, 3, 0, 5 2,3,4 ,5 b 2, 3,4

6、 ,5 2, 4 a 3, 5 a 1, 0 2 ,4 b 3,5 3,5 b 3, 5 2, 4 0,1,2, 4,3, 5 0,1 a1 0,1 b 2, 4 2, 4 a 1, 0 2 ,4 b 3, 5 3, 5 a 3,5 3,5 b 2, 4bba012abap6414(1)01010(2):(0|10)*xy201x1y0確定化：x,1,y01,y121,y1,y221,y給狀態(tài)編號(hào)：01012112213333001010111230最小化： 0,1, 2, 3 0,1 01 2,3 01,3 0,1 1 2 2, 3 1 3 0,1, 2, 3011101300第四章p811

7、(1) 按照 t,s的順序消除左遞歸g (s)sa | | (t )tstt, st|遞歸子程序： procedure s; beginif sym='a' or sym='' then abvance else if sym='('then beginadvance;t;if sym=')' then advance; else error;end; procedure t; begins;tendelseerrorend; procedure t; beginif sym=','then beginadvanc

8、e;s;tendend;其中 :sym:是輸入串指針ip 所指的符號(hào)advance是:把 ip 調(diào)至下一個(gè)輸入符號(hào)error:是出錯(cuò)診察程序(2)first(s)=a,(first(t)=a,(first( t )=,follow(s)=),# follow(t)=)follow( t )=)a(),#s ttstastststst(t)sttt, st預(yù)測(cè)分析表是 ll(1) 文法p812文法：eteee |tfttt |fpff* f|p(1)( e) | a | b |first(e)=(,a,b,first(e')=+, first(t)=(,a,b,first(t')

9、=(,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)考慮以下產(chǎn)生式:ee|tt|f* f |p( e)| a|bfirst(+e) first()=+ = first(+e) follow(e')=+ #,)=first(t) first()=(,a,

10、b, = first(t) follow(t')=(,a,b,+,),#=first(*f') first( )=* = first(*f') follow(f')=* (,a,b,+,),#=first(e) first(a) first(b) first()= +*()ab#e e' tt'ete 'ete ' ete ' ete 'eeeetttftttttfttttfttttfttt所以 ,該文法式ll(1)文法 . (3)f f'pffppffpffpff ppfbffppfff* fff( e

11、)a(4)procedure e; beginif sym='(' or sym='a' or sym='b' or sym='' then begin t; e' endelse errorend procedure e' beginif sym='+'then begin advance; e endelse if sym<>')' and sym<>'#' then errorend procedure t; beginif sym=&#

12、39;(' or sym='a' or sym='b' or sym='' then begin f; t' endelse errorend procedure t' beginif sym='(' or sym='a' or sym='b' or sym='' then telse if sym='*' then errorend procedure f; beginif sym='(' or sym='a'

13、 or sym='b' or sym='' then begin p; f' endelse errorend procedure f' beginif sym='*'then begin advance; f' endend procedure p; beginif sym='a' or sym='b' or sym='' then advanceelse if sym='(' thenbeginadvance; e;if sym=')' t

14、hen advance else errorend;p813endelse error/*(1) 是，滿足三個(gè)條件。(2) 不是，對(duì)于a 不滿足條件3。(3) 不是， a、 b 均不滿足條件3。(4) 是，滿足三個(gè)條件。*/p133 1第五章eetet * f短語(yǔ) :e+t*f, t*f,直接短語(yǔ) : t*f句柄 : t*fp133 2文法：sa|( t)tt, s|s(1)最左推導(dǎo) :s(t)(t, s)(s, s)(a, s)( a,( t )(a,( t, s)(a,( s,s)(a,( a, s)(a,( a, a)s(t, s)( s,s)( t), s)( t, s), s)( t

15、, s, s), s)( s,s, s), s)( t), s, s), s)( t, s), s, s), s)( s, s), s, s), s)( a, s), s,s), s)( a,a ), s, s), s)( a, a), , s), s)( a, a ), ,( t), ( a, a), ,( a), a)最右推導(dǎo) :s)(a, a), ,( s), s)( a,a ), ,( a), s)s(t )(t , s)( t,( t)( t,( t, s)( t,( t, a)(t ,( s, a)( t,( a, a) ( s,( a,a )(a,( a,a )s(t , s)(

16、t, a)( s,a)( t ), a)( t ,s), a)( t ,( t), a)( t ,( s), a)( t,( a), a)( t ,s,( a), a)( t, ,( a), a)( s, ,( a ), a)( t ), ,( a ), a)(2)( t , s), ,( a ), a)(t, a ), ,( a ), a)(s,a ), ,( a ), a)(a,a ), ,( a ), a)(a,a),(a),a)(t,a),(a),a)(t,s),(a),a)(t),(a),a)(s,(a),a)(t,(a),a)(t,s,(a),a)(t,(a),a)(t,(s),a

17、)(t,(t),a)(t,s),a)(t),a) (s,a)(t,s) (t) s" 移進(jìn) -歸約過(guò)程：步驟棧輸入串動(dòng)作(s,a),(a),a)0#(a,a),(a),a)#預(yù)備1#(a,a),(a),a)# 進(jìn)2#(3#(a,a),(a),a)# 進(jìn)a,a),(a),a)#進(jìn)4#(a,a),(a),a)#進(jìn)5#(s,a),(a),a)#歸6#(t,a),(a),a)#歸7#(t,a),(a),a)#進(jìn)8#(t,a),(a),a)#進(jìn)9#(t,s),(a),a)#歸10#(t),(a),a)#歸11#(t),(a),a)# 進(jìn)12#(s13#(t,(a),a)# 歸,(a),a)#

18、歸14#(t,(a),a)#進(jìn)15#(t,(a),a)#進(jìn)16#(t,s,(a),a)#歸17#(t,(a),a)#歸18#(t,(a),a)#進(jìn)19#(t,(a),a)#進(jìn)20#(t,(a),a)#進(jìn)21#(t,(s),a)#歸22#(t,(t23#(t,(t),a)#),a)#進(jìn)歸24#(t,s),a)#歸25#(t),a)#歸26#(t),a)#進(jìn)27#(s,a)#歸28#(t,a)#歸29#(t,30#(t,aa)#進(jìn))#進(jìn)31#(t,s)#歸32#(t33#(t)#歸進(jìn)34#s#歸p133 3(1) firstvt(s)=a,(firstvt(t)=,a,(lastvt(s)=a,)

19、g6 是算符文法，并且是算符優(yōu)先文法(3)優(yōu)先函數(shù)faffff(),ggaggg(),lastvt(t)=,a,) (2)a(),a>>>>()<<<=><>,<<<>>a(),f44244g555234棧輸入字符串動(dòng)作# a,(a,a)#預(yù)備#(a, (a,a)#進(jìn)#(a#(t, (a,a)#, (a,a)#進(jìn)歸sas789a010112a3s4d56確定化：0,2,5,7,101,2,5,7,8,102,3,5,7,10s1,2,5,7,8,102,5,7,8,102,4,5,7,8,10a2,3,5

20、,7,102,3,5,7,9,102,3,5,7,10a111111b666# t,(a,a) #進(jìn)# t,a,a #進(jìn)# t,a,a #進(jìn)# t,t,a #歸# t,t,a#進(jìn)# t,t,a #進(jìn)# t,t,s #歸# t,t #歸# t,t#進(jìn)# t,s#歸# t#歸# t #進(jìn)# s#歸successp134 5(1)0. ss1.ss 2. sas 3. sa s4. sas5. sb 6. sb7. asa8. asa9. asa10. aa11. aa(2)12,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,9,102,4,5,7,8,102,3

21、,5,7,101162,4,5,7,8,102,5,7,8,102,3,5,7,9,10116116sbsbsasasaasasbaaaaasaaaas3: sa a a s ssssa saaasb5: asa6: asasssa aasb saaass s aaa sasb saaabaasbsabaa0: sss4: sas7: sasasassaassabaabba1: aa2: sbdfa構(gòu)造 lr(0)工程集標(biāo)準(zhǔn)族也可以用go 函數(shù)來(lái)計(jì)算得到。所得到的工程集標(biāo)準(zhǔn)族與上圖中的工程集一樣 :i 0 = ss ， sas， sb， asa， aa go(go(i 0 ， a)=aa= i

22、 1i 0 ， b)=sb= i 2go(i 0 ，s)=ss ， asa， asa， aa ， sas， sb = i 3go(i 0 ， a)=sas ， sas， sb， asa， aa = i 4go(go(i 3 ， a)=aa= i 1i 3 ， b)=sb= i 2go(i 3 ， s)=as a ， sas， sb， asa， aa = i 5go(i 3 ， a)=asa ， sas， sas， sb ， asa， aa = i 6go(i 4 ， a)=aa= i 1.go(i 4 ， b)=sb= i 2go(i 4 ， s)=sas ， asa ， sas， sb， a

23、sa， aa = i 7go(i 4 ， a)=sas ， sas， sb， asa， aa = i 4go(go(i 5 ， a)=aa= i 1i 5 ， b)=sb= i 2go(i 5 ， s)=as a ， sas， sb， asa， aa = i 5go(i 5 ， a)=asa ， sas， sas， sb ， asa， aa = i 6go(i 6 ，a)=aa= i 1go(i 6 ，b)=sb=i 2go(i 6 ，s)=sas ，asa，sas， sb ，asa， aa =i 7go(i 6 ，a)=sas， sas， sb ， asa， aa = i 4go(go(i

24、7 ， a)=aa= i 1i 7 ， b)=sb= i 2go(i 7 ， s)=asa， sas， sb ， asa， aa = i 5go(i 7 ， a)=asa ， sas ， sas， sb， asa， aa = i 6工程集標(biāo)準(zhǔn)族為c=(3) 不是 slr 文法i 1 ， i 2 ， i 3 ， i 4 ， i 5 ， i 6 ， i 7 bbb1：s a a a ssssasaa asb#a/b a/b a/b a/ba/bas5：a s s s aasa as asb saaa/b a/b a/b a/b a/ba/ba8：s s s a aa s asb saaa/b a/

25、b a/b a/ba/baasas3：0：s s ss asb#/a/b #/a/b3：aaa/b優(yōu)選 .狀態(tài) 3， 6，7 有移進(jìn)歸約沖突狀態(tài) 3： follow(s )=#不包含 a,b狀態(tài) 6： follow(s)=#,a,b包含 a,b,；移進(jìn)歸約沖突無(wú)法消解狀態(tài) 7： follow(a)=a,b包含 a,b；移進(jìn)歸約沖突消解所以不是slr 文法。(4) 構(gòu)造例如lr(1) 工程集標(biāo)準(zhǔn)族見(jiàn)以下列圖：對(duì)于狀態(tài) 5，因?yàn)榘こ?aasa / b ，所以遇到搜索符號(hào)a或 b 時(shí)，應(yīng)該用 aas歸約。 又因?yàn)闋顟B(tài)5 包含工程 aaa/ b ，所以遇到搜索符號(hào)a 時(shí)， 應(yīng)該移進(jìn)。 因此存在&q

26、uot; 移進(jìn)-歸約矛盾，所以這個(gè)文法不是lr(1)文法。asa6：a a a ss9：sasaa asba/ba/b a/bsb4：ss aaassab# / a/bsaa/b a/ba/ba/ba/bsabaasb2：s s s aaas asb saa#/a/b #/a/b #/a/b a/ba/b7：s asa a ssas sa saa asb# / a/ba/ba/b a/b a/ba/bb10：sba/baa5：aaaaasaasa/ba/bsbba/b第六章/*第六章會(huì)有點(diǎn)難p164 5(1)ee1 t if (e1.type = int) and (t.type = int

27、) then e.type := intelse e.type := realete.type := t.type tnum.num t.type := realtnumt.type := int (2)p164 7ssl1|l2ls.val:=l1.val+(l2.val/2l 2.length )s.val:=l.valll1bl.val:=2*l1.val + b.val;l.length:=l1.length+1優(yōu)選 .lbl.val:=b.c;l.length :=1b0b.c:=0b1b.c:=1*/p217 1a*(-b+c)abc+*第七章a+b*(c+d/e)abcde/+*

28、+-a+b*(-c+d)abcd+*+a(cd ) acd( ab)(cd) abc d( ab)(cde) abcd eif(x+y)*z =0then(a+b) celsea b cxy+z*0= ab+c abc￥ 或 xy+z*0= p1 jez ab+c p2 jump abcp1p2p217 3-(a+b)*(c+d)-(a+b+c) 的三元式序列 :(1)+, a, b(2), (1), -(3)+, c, d (4)*, (2), (3)(5)+, a, b (6)+, (5), c (7)-, (4), (6)間接三元式序列:三元式表：(1)+, a, b(2), (1),

29、-(3)+, c, d (4)*, (2), (3) (5)+, (1), c (6)-, (4), (5) 間接碼表：(1)(2)(3)(4)(1)(5) (5)(6) (6)四元式序列 :(1)+, a, b,t1(2),t1 , -, t2(3)+, c, d,t3(4)*,t2 ,t3 , t4(5)+, a, b,t5(6)+,t5 , c, t6(7)-,t4 ,t6 , t7p218 4自下而上分析過(guò)程中把賦值句翻譯成四元式的步驟:a:=b*(-c+d)步驟輸入串棧place四元式(1)a:=b*(-c+d)(2):=b*(-c+d)ia(3)b*(-c+d)i:=a-(4)*(

30、-c+d)i:=ia-b(5)*(-c+d)i:=ea-b(6)*(-c+d)i:=ea-b(7)(-c+d)i:=e*a-b-(8)-c+d)i:=e*(a-b-(9)c+d)i:=e*(-a-b-(10)+d)i:=e*(-ia-b-c(11) +d)i:=e*(-ea-b-c(,c,-, t )1(12) +d)i:=e*(ea-b- t1(13) d)i:=e*(e+ a-b-t -1(14) )i:=e*(e+ia-b- t -d1(15)i:=e*(e+ea-b- t1(16)i:=e(ea-b- t2-d(+, t1,d, t )2(17)i:=e*(e)a-b- t -2(18

31、) i:=e+ea-b- t2(*,b, t2, t )3(19) i:=ea- t3產(chǎn)生的四元式：(:=, t3(20) a,-,a)(,c,-, t )1(+, t1,d, t )2(*,b, t2, t )3(:=, t3,-,a)p218 5/*設(shè) a ： 10*20， b、c、d ： 20，寬度為w 4 那么t1:= i * 20 t1:=t1+jt2:=a 84 t3:=4*t1tn:=t2t3/ 這一步是多余的t4:= i + j t5:=b 4 t6:=4*t4 t7:=t5t6 t8:= i * 20 t8:=t8+j t9:=a 84 t10:=4*t8 t11:=t9t1

32、0 t12:= i + j t13:=d 4 t14:=4*t12t15:= t13t14t16:=t11+t15 t17:=c 4 t18:=4*t16t19:=t17t18 t20:=t7+t19 tn:=t20*/p218 6100. (jnz, a, -, 0)101.(j, -, -, 102)102.(jnz, b, -, 104)103.(j, -, -, 0)104.(jnz, c, -, 103)105.(j, -, -, 106)106.(jnz, d, -, 104)-假鏈鏈?zhǔn)?07.(j, -, -, 100)-真鏈鏈?zhǔn)准冁湥?106,104， 103真鏈： 107,1

33、00p218 7100. (j<, a, c, 102)101.(j, -, -, 0)102.(j<, b, d, 104)103.(j, -, -, 101)104.(j=, a, 1 , 106)105.(j, -, -, 109)106.(+, c, 1 , t1)107.(:=, t1, -, c)108.(j, -, -,100)109.(j , a, d, 111)110.(j, -, -, 100)111.(+, a, 2 , t2)112.(:=, t2, -, a)113.(j, -, -, 109)114.(j, -, - 100)p219 12/* (1)m

34、axint5maxint4maxint3maxint2maxint1maxint(2)翻譯模式方法 1：for e1 := e2 to e3 do ssf do ms1ffor i :iidme1 to e2sf do ms1backpatch(s1.nextlist,nextquad);backpatch(f.truelist,m.quad); emit(f.place := f.place + 1);emit( j, f.place ,f.end ,m.quad);s.nextlist := f.falselist;ffor i :e1 to e 2f.falselist:= makeli

35、st(nextquad);emit( j>, e1.place , e2.place ,0 ); emit(i.place := e1.place);f.truelist := makelist(nextquad);.iidemit( j,-,-,- ); f.place := i.place; f.end := e2.place;p:=lookup(); if p <> nil theni. place := p else errormm.quad := nextquad*/方法 2：s for id:=e1 to e2 do s1 s f s1f for i

36、d:=e1 to e2 dofforid :e1toe 2 do initial=newtemp;emit( :=， e1.place ， -， initial); final=newtemp;emit( :=， e2.place ， -， final);p:= nextquad+2;emit(j, initial , final , p);f.nextlist:=makelist(nextquad); emit( j, , ); f.place:=lookup();if f.placenil thenemit(f.place := initial) f.quad:=nextqu

37、ad;f.final:=final;sfs1backpatch(s1.nextlist, nextquad) p:=nextquad+2;emit(j, f.place , f.final , p ); s.nextlist := merge(f.nextlist, makelist(nextquad); emit( j, , );emit( succ， f.place ， -， f.place);emit( j, , f.quad);第九章優(yōu)選 .p270 9(1) 傳名即當(dāng)過(guò)程調(diào)用時(shí)， 其作用相當(dāng)于把被調(diào)用段的過(guò)程體抄到調(diào)用出現(xiàn)處，但必須將其中出現(xiàn)的任一形式參數(shù)都代之以相應(yīng)的實(shí)在參數(shù)。a:=2;b:=3;a:=a+1;a:=a+(a+b);printa;a=9(2) 傳地址即當(dāng)程序控制轉(zhuǎn)入被調(diào)用段后，被調(diào)用段首先把實(shí)在參數(shù)抄進(jìn)相應(yīng)的形式參數(shù)的形式單元中，過(guò)