編譯原理課后習(xí)題答案(陳火旺+第三版)精選.

1、第二章word.P36-6(1)L(Gi)是o9組成的數(shù)字串(2) 最左推導(dǎo) :NNDNDDNDDD DDDD0DDD01DD012D 0127NNDDD3D 34NNDNDDDDD 5DD56D568最右推導(dǎo) :NNDN7ND7 N27ND27N127D1270127NNDN4D4 34NNDN8ND8 N68D68568P36-7G(S)O 1|3|5|7|9N 2|4|6|8|OD 0|NS O|AOA AD|NP36-8文法：E T|E T|E TTF|T*F|T/ FF(E)|i最左推導(dǎo) :EET T T FTiTi T* Fi F* F ii* F i i *iETT*FF*Fi*

2、Fi *(E)i *( ET)i*( TT) i*( F T)i*( iT) i*( i F)i*( i i)最右推導(dǎo)EETET*FET*iEF*iEi*iT i*i F i *i i i*ETF*TF*FF*( E)F*( ET)F *( EF)F *( E i)F *( Ti)F*( F i)F *( ii)i*( ii)語法樹：EETii+i+ii-i-iii+i*i*/P36-9句子iiiei有兩個(gè)語法樹：S iSeS iSei iiSei iiieiS iS iiSeS iiSei iiieiP36-10/*S TS |TT (S)|()*/P36-11/*L1:S ACA aAb

3、| ab C cC |L2:S ABA aA|B bBc|bcL3:S ABA aAb|B aBb|L4:S A| BA 0A1|B 1B0| A*I第三章習(xí)題參考答案P64 - 701(01)*101700231011501101確定化:01X01,2,30001,2,32,32,3,42,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4,Y2,3,4,Y2,3,52,3,4,最小化：012,3,4,5,6012,3,4,5。1,3,50,1,2,3,4,511,2,4®012,3,4, 5,60,1,2,34。1,3,50,1,23,4, 5,60,1,

4、23°1,30,1,2,$1,2,40,1,2,04, $,60,1 0 1 0,1 1 1,22,30 B 2,311 40,1,2,3,4, 5,601 1P64 - 8(1)(1|0)*01 (1|2|3|4|5|6|7|8|9)(0 2|3|4|5|6|7|8|9)*(0|5)|(0|5) 0*1(0|10*1)* |1*0(0|10*1)P64 - 12a確定化:ab00,110,10,11100000給狀態(tài)編號(hào):ab012112203333a最小化：0,1, 2,30,1 a 1 0,1b 2 2,3a 0,32,3b 30,1, 2, 3已經(jīng)確定化了，進(jìn)行最小化最小化:

5、0,1, 2,3,4,50,1a 10,1b 2,42,3,4,5a 1,3,0,52,3,4,5b 2,3,4,52,4a 1,02,4b 3,53,5a 3,53,5b 2,4 0,1, 2,4, 3,50,1a 10,1b 2,42,4a 1,03,5a 3,52,4b 3,53,5b 2,4bba:0確定化:01X,1,Y1,Y21，Y1，Y221，Y0000給狀態(tài)編號(hào):01012112213333最小化：0,1，2,30,10 1 0,11 22,3o 1,32,3i 30,1,2,3P81 - 1(1) 按照T,S的順序消除左遞歸G(S)S aF|(T)T STT ,ST |遞歸子

6、程序：procedure S;beginif sym='a' or sym='人'the n abva neeelse if sym='('the n begi nadvance;T;if sym=')' the n adva nee; else error;endelse erroren d;procedure T;beginS;Ten d;procedure T ;beginif sym=','the n begi nadvanee;S;Tenden d;其中：sym:是輸入串指針I(yè)P所指的符號(hào)advanee:

7、是把IP調(diào)至下一個(gè)輸入符號(hào) error:是出錯(cuò)診察程序FIRST(S)=a,(FIRST(T)=af,(FIRST(T )=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOWT )=)預(yù)測分析表aA()J#SS aS AS (T)Tr T STr T STT STTTT ,ST是LL(1)文法P81 - 2文法：E TEEE|TFTTT |FPFF*F|P (E)|a|b$(1)FIRST(E)=(,a,bfFIRST(E')=+,£ FIRST(T)=(,a,bFIRST(T')=(,a,b,A,£ FIRST(F)=(,a,b,AFIRST(

8、F')=*,£ FIRST(P)=(,a,bfFOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F')=(,a,b,A,+,),#FOLLOW(P)=*,(,a,bf,+,),#考慮下列產(chǎn)生式：E E|TT|F*F |P(E)|A|a|bFIRST(+E) A FIRST( £ )=+ n £ = $FIRST(+E) A FOLLOW(E')=+ A #,)=$FIRST(T) A FIRST( &

9、#163; )=(,a,b,AA £ = $FIRST(T) A FOLLOW(T')=(,a,b,A A +,),#=$FIRST(*F') A FIRST( £ )=* A £ = $FIRST(*F') A FOLLOW(F')=* A (,a,b,A,+,),#=$FIRST(E) A FIRST(a) A FIRST(b) A FIRST(A)= $ 所以,該文法式LL(1)文法.+*()abA#EE TE'E TE'E TE'E TE'E'EEEETT FTT FTT FTT FT

10、T'TT TTT TT TTTTFFPFFPFFPFF PFF'FF *FFFFFFF :PP(E)PaPbP Aprocedure E;beginif sym='(' or sym='a' or sym='b' or sym='人' the n beg in T; E' end else errorendprocedure E：beginif sym='+'the n beg in adva nee; E endelse if sym<>')' and sym&

11、lt;>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='人' the n beg in F; T' end else errorendprocedure T'beginif sym='(' or sym='a' or sym='b' or sym='人' the n Telse if sym='*' then e

12、rrorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='人' the n beg in P; F' end else errorendprocedure F'beginif sym='*'the n beg in adva nee; F' endendprocedure P;beginif sym='a' or sym='b' or sym='A'the n adva n

13、eeelse if sym='(' the nbeginadvanee; E;if sym=')' the n adva nee else error end else erroren d;P81 3/*(1) 是，滿足三個(gè)條件。(2) 不是，對(duì)于A不滿足條件3。(3) 不是，A、B均不滿足條件3。(4) 是，滿足三個(gè)條件。*/第五章P133- 1E E T E T*F短語：E+T*F, T*F,直接短語：T*F 句柄:T*FP133-2文法:(1)最左推導(dǎo):(a,(S,S)(a,(a,S)(a,(a,a)(S,S,S),S)(T),S,S),S)(a,a),S

14、,S),S)S (T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)S (T,S)(S,S)(T),S)(T,S),S)(T,S,S),S)(T,S),S, S), S) ( S, S), S,S), S) ( a, S), S,S), S)(a,a)T ,S),S)(a,a)T,(T), S) ( a,a),A ,(S),S)(a,a),A ,(a), S)(a,a)T ,(a), a)最右推導(dǎo):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)(T,a)(S,a)(T),a)(T,S),a)

15、(T,(T), a)(T,(S),a)(T,(a), a) (T,S,(a), a)(T“ ,(a), a) (S" ,(a), a)(T)“ ,(a),a)(T,S)“ ,(a), a)(T,a)",(a),a)(S,a)“ ,(a), a) (a,a)“ ,(a), a)(a,a),A,(a),a)(S0,(a),a)(T, a),A,(a),a) (LSV，(a),a)(TL，A，(a),a)(S，A，(a)，a) (T,A,(a),a)(TS，(a),a)(T,( a),a)(T,( S),a)(T,( T),a)(TS),a)(IL，a)(S，a)(TS)(T)_

16、S“移進(jìn)-歸約”過程:步驟棧輸入串動(dòng)作0#(a,a),A,(a),a)#預(yù)備1#(a,a),A,(a),a)#進(jìn)2#(a,a),A,(a),a)#進(jìn)3#(a,a),A, (a),a)#進(jìn)4#(a,a),A,(a),a)#進(jìn)5#(S,a),A,(a),a)#歸6#(T,a),A,(a),a)#歸7#(T，a),A,(a),a)#進(jìn)8#(T，a),A,(a),a)#進(jìn)9#(T，S),A,(a),a)#歸10#(T),A,(a),a)#歸11#(T),A,(a),a)#進(jìn)12#(S,A,(a),a)#歸13#(T,A,(a),a)#歸14#(T，A,(a),a)#進(jìn)15#(T，a,(a),a)#進(jìn)1

17、6#(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，(T),a)#歸23#(T，(T),a)#進(jìn)24#(T,S),a)#歸25#(T),a)#歸26#(T),a)#進(jìn)27#(S,a)#歸28#(T,a)#歸29#(T,a)#進(jìn)30#(T,a)#進(jìn)31#(T,S)#歸32#(T)#歸33#(T)#進(jìn)34#S#歸P133-3(1)FIRSTVT(S)=a,( FIRSTVT(T)=,a】,( LASTVT(S)=a,) LASTVT(T)=,a】,) aA()5a>

18、;>A>>(<<<=<)>>5<<<>>G6是算符文法，并且是算符優(yōu)先文法(3) 優(yōu)先函數(shù)aA()5f44244g55523(4) 棧#(#(a #(t輸入字符串動(dòng)作(a,(a,a) ) #a, (a,a)#進(jìn),(a,a)#進(jìn),(a,a)#歸預(yù)備# (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

19、,s)#歸# (t)#歸# (t)#進(jìn)# s#歸successP134-5(1)0.SS1.SS2. SAS3.SA S4.SAS 5.Sb6. Sb7.ASA8.AS A9.ASA10.A a11.Aa確定化:SAab0,2,5,7,101,2,5,7,8,102,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,10112,3,5,7,102,4,5,7,8,102,3,5,7,101162,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,9,102,4,5,7,8,102,3,5,7,101162,4,5,7,8,10

20、2,5,7,8,102,3,5,7,9,1011611000060000SAAsAssbAAA7sAsSAAsbSAaAsSASAaSasssSAAsbi aAsbSAa1DFAGO函數(shù)來計(jì)算得到。所得到的項(xiàng)目集規(guī)范族與上圖中的AS, Sb= 13項(xiàng)目集樣：10 = ss，sAS， S b， ASA，A aGO(I o，a)= Aa = IiGO(I o，b)= Sb = 12GO(I o，S)= SS，A S A，ASA，A a，S構(gòu)造LR(O)項(xiàng)目集規(guī)范族也可以用GO（I 0 ， A）=SA S，SAS，Sb， ASA，Aa = I 4GO（I 3 ， a）=Aa=I1GO（I 3 ， b

21、）=Sb=I2GO（I 3 ， S）=AS A ，SAS，Sb， ASA，Aa= I 5GO（I 3 ， A）=ASA ，SA S，SAS， Sb，ASA， Aa= I 6GO（I 4 ， a）=Aa=I1GO（I 4 ， b）=Sb=I2GO（I 4 ， S）=SAS ，AS A ，SAS， Sb，ASA ， Aa = I 7GO（I 4 ， A）=SA S，SAS，Sb， ASA，Aa = I 4GO（I 5 ， a）=Aa=I1GO（I 5 ， b）=Sb=I2GO（I 5 ， S）=AS A ，SAS，Sb， ASA，Aa= I 5GO（I 5， A）=ASA ，SA S，SAS， S

22、b，ASA， Aa= I 6GO（I 6 ， a）=Aa=I1GO（I 6 ， b）=Sb=I2GO（I 6 ， S）=SAS ，AS A ，SAS， Sb，ASA， Aa= I 7GO（I 6， A）=SA S，SAS，Sb， ASA，Aa= I 4GO（I 7， a）=Aa=I1GO（I 7， b）=Sb=I2GO（I 7， S）=AS A ，SAS，Sb， ASA，Aa = I 5GO（I 7， A）=ASA ，SA S，SAS， Sb，ASA ， Aa = I 6項(xiàng)目集規(guī)范族為C= I1 ， I2，I3 ， I 4，I5，I 6， I7不是SLR文法狀態(tài) 3，6，7 有移進(jìn)歸約沖突狀態(tài)

23、 3：FOL LOW('S )=# 不包含 a,b狀態(tài) 6： FOLLOW(S)=#,a,b 包含 a,b, ；移進(jìn)歸約沖突無法消解狀態(tài)7： FOLLOW(A)=a,b包含a,b ;移進(jìn)歸約沖突消解所以不是SLR文法。(4) 構(gòu)造例如 LR(1) 項(xiàng)目集規(guī)范族見下圖：對(duì)于狀態(tài)5，因?yàn)榘?xiàng)目A AS a/b，所以遇到搜索符號(hào)a或b時(shí)，應(yīng)該用A AS 歸約。又因?yàn)闋顟B(tài) 5包含項(xiàng)目A a a/b，所以遇到搜索符號(hào) a時(shí)，應(yīng)該移進(jìn)。因此 存在“移進(jìn) -歸約”矛盾，所以這個(gè)文法不是 LR(1) 文法。S/*第六章會(huì)有點(diǎn)難第六章P164 5(1)E E1 + T if (El.type = in

24、 t) a nd (type = int ) then E.type := int else E.type := realETE.type:=T.typeTnum.num T.type := realTnum T.type := intP164-7SL1|L2S.val:=L1.val+(L2.val/2L2.length »SLS.val:=L.valLL1BL.val:=2*L1.val + B.val;L.le ngth:=L1.le ngth+1LBL.val:=B.c;L.le ngth :=1B0B.c:=0B1B.c:=1*/第七章P217- 1a*(-b+c) a+b

25、*(c+d/e) -a+b*(-c+d)abc+* abcde/+*+ abcd+*+A(C D)ACD(AB) ( C D)ABCD(AB) (CD E)ABCDEif (x+y)*z =0 then (a+b)f c else <af b f c xy+z*0= ab+c f abc¥或 xy+z*0= P1 jez ab+cf P2 jump abc ffP1 P2P217- 3-(a+b)*(c+d)-(a+b+c) 的 三元式序列 :(1) +, a, b(2) , (1), -(3) +, c, d(4) *, (2), (3)(5) +, a, b(6) +, (

26、5), c(7) -, (4), (6) 間接三元式序列 :(1) +, a, b(2) , (1), -(3) +, c, d(4) *, (2), (3)(5) +, (1), c(6) -, (4), (5) 間接碼表：(1)(2)(3)(4)(1)(5)(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自下而上分析過程中把賦值句翻譯成四元式的步驟:A:=B*(-C+D)步驟輸入串棧PLACE四

27、元式(1)A:=B*(-C+D)(2):=B*(-C+D)iA(3)B*(-C+D)i:=A-(4)*(-C+D)i:=iA-B(5)*(-C+D)i:=EA-B(6)*(-C+D) i:=E(7)(-C+D)i:=E*(8)-C+D)i:=E*(9)C+D)i:=E*(-(10)+D)i:=E*(-i(11)+D)i:=E*(-E(12)+D)i:=E*(E(13)D)i:=E*(E+(14)i:=E*(E+i(15)i:=E*(E+E(16)i:=E(E(17)i:=E*(E)(18)i:=E+E(19)i:=E產(chǎn)生的四元式：(,C,-,(+, T ,D,1(*,B, T2 (:=, T

28、,3T)1T12) ,T)3 ,A)A-BA-B-A-B-A-B-A-B-CA-B-C(,C,-, T )1A-B- T1A-B- T -1A-B- T -DA-B-T -D1(+, T1,D,T)2A-B-T2A-B-T-2A-B- T(*,B,T,T)223A-T(:=,T ,-,A)33(20) AP218- 5/*寬度為w = 4則設(shè) A ： 10*20 ，B、C、D：20， T1:= i * 20T1:=T1+jT2:=A -84T3:=4*T1Tn:=T2T3/這一步是多余的T4:= i + jT5:=B-4T6:=4*T4T7:=T5T6T8:= i * 20T8:=T8+jT9

29、:=A -84T10:=4*T8T11:=T9T10T12:= i + jT13:=D -4T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C-4T18:=4*T16T19:=T17T18T20:=T7+T19Tn:=T20 *P218- 6100. (jnz, A, -, 0)101. (j, -, -, 102)102. (jnz, B, -, 104)103. (j, -, -, 0)104. (jnz, C, -, 103)105. (j, -, -, 106)假鏈鏈?zhǔn)渍骀滄準(zhǔn)?06. (jnz, D, -, 104) -107. (j, -, -, 10

30、0) - 假鏈： 106,104 ， 103 真鏈： 107,100P218-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)11

31、3.(j, -, -, 109)114.(j, -, - 100)P219- 12/*(1)MAXINT - 5MAXINT - 4MAXINT - 3MAXINT - 2MAXINT - 1MAXINT(2)翻譯模式方法1：for E1 :=:E2 to E3 do SSF do MS!F For I : E1 to E2I idMS F do MS!backpatch(S1.nextlist,nextquad);backpatch(F.truelist,M.quad);emit(F.place := ' F.place +' 1);emit( j , ' F.pla

32、ce , ' F.end, ' M.quad);S.n extlist := F.falselist;F For I : E! to E2F.falselist:= makelist(nextquad);emit( ' j>, ' El.place ', ' E2.place ' ,0 '); emit(I.Place := ' El.place);F.truelist := makelist (n extquad); emit( j,-,-,-');F.place := I.place;F.e nd :=

33、E2.place;I idp:=lookup(id. name);if p <> nil the nI.place := pelse errorMM.quad := nextquad*/方法2:St for id:=E1 to E2 do S1St F S1Ft for id:=E1 to E2 doF forid : E1toE2do,'INITIAL);,'FINAL);'FINAL 'p);INITIAL=NEWTEMP; emit( ' :=， E1.PLACE , FINAL=NEWTEMP;emit( ' :=， E2.P

34、LACE , p:= n extquad+2;emit( 'j , ' INITIALF.n extlist:=makelist (n extquad);emit( j,');F.place:=lookup(id. name);if F.placenil the nemit(F.place' := ' INITIAL)F.quad:=n extquad;F.fi nal:=FINAL;S FS1backpatch(S1. nextlist, n extquad)p:=n extquad+2;emit( 'j , ' F.place , ' F.final ' , ' p );S.n extlist := merge(F. nextlist, makelist (n extquad); emit( ' j,');emit( ' succ， F.place-， F.place);emit( ' j, , , ' F.quad);第九章P270-9(1)傳名即當(dāng)過程調(diào)用時(shí)，其作用相當(dāng)于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)處，但必須將其中出現(xiàn)的任一形式參數(shù)都代之以相應(yīng)的實(shí)在參數(shù)