編譯原理_第三版_課后答案

1、編譯 原理 課后題答案第二章P36-6(1)是09組成的數(shù)字串(2)最左推導(dǎo):最右推導(dǎo):P36-7G(S)P36-8文法：最左推導(dǎo):最右推導(dǎo):語(yǔ)法樹(shù)：/*/P36-9句子iiiei有兩個(gè)語(yǔ)法樹(shù)：P36-10/*/P36-11/*L1:L2:L3:L4:*/第三章習(xí)題參考答案P647(1)XY X1234Y5 0 1 1 0 1 1確定化：01X1,2,31,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, 0320 1 01 0 0 1 1 0654 0 1 0 1 1 1最小化： 002 1 1 0

2、0 1 0543 0 1 0 1 1 1P648(1) (2)(3)P6412(a) a10 a,b a確定化：ab00,110,10,1110給狀態(tài)編號(hào)：ab012112203333 a10 a a b b b32 b a最小化： a a210 b b a b(b)032 b b a a b a a b541 b a a a已經(jīng)確定化了,進(jìn)行最小化最小化：021 b b a a b aP6414 (1) 010 1 0(2):YX 2 0 1Y1X 0確定化：01X,1,Y1,Y21,Y1,Y221,Y給狀態(tài)編號(hào)：01012112213333 010 0 1 032 1 1 1 0最小化：

3、0310 1 1 1 0 0第四章P811(1) 按照T,S的順序消除左遞歸遞歸子程序：procedure S;beginif sym=a or sym= then abvanceelse if sym=( then beginadvance;T;if sym=) then advance;else error; endelse errorend;procedure T;beginS;end;procedure ;beginif sym=, then beginadvance;S;endend;其中:sym:是輸入串指針I(yè)P所指的符號(hào) advance:是把IP調(diào)至下一個(gè)輸入符號(hào)error:是出

4、錯(cuò)診察程序(2)FIRST(S)=a,(FIRST(T)=a,(FIRST()=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW()=)預(yù)測(cè)分析表a(),#ST是LL(1)文法P812文法：(1)FIRST(E)=(,a,b,FIRST(E)=+,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,+,),#

5、FOLLOW(P)=*,(,a,b,+,),#(2)考慮下列產(chǎn)生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E)=+#,)=FIRST(T)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#EETTFFP(4)procedure E;beginif sym=( or sym=a or sym=b or sym

6、= then begin T; E end else errorendprocedure E;beginif sym=+ then begin advance; E end else if sym) and sym# then errorendprocedure T;beginif sym=( or sym=a or sym=b or sym= then begin F; T end else errorendprocedure T;beginif sym=( or sym=a or sym=b or sym= then T else if sym=* then errorendprocedu

7、re F;beginif sym=( or sym=a or sym=b or sym= then begin P; F end else errorendprocedure F;beginif sym=* then begin advance; F endendprocedure P;beginif sym=a or sym=b or sym= then advance else if sym=( thenbeginadvance; E;if sym=) then advance else errorendelse errorend;P813/*(1) 是，滿(mǎn)足三個(gè)條件。(2) 不是，對(duì)于A

8、不滿(mǎn)足條件3。(3) 不是，A、B均不滿(mǎn)足條件3。(4) 是，滿(mǎn)足三個(gè)條件。*/第五章P1331短語(yǔ): E+T*F, T*F,直接短語(yǔ): T*F句柄: T*FP1332文法：(1)最左推導(dǎo):最右推導(dǎo):(2)(a,a),(a),a)(S,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)(T,(T),a)(T,S),a)(T),a)(S,a)(T,S)(T)S“移進(jìn)-歸約”過(guò)程：步驟棧輸入串動(dòng)作0#(a,a),(a),a)#預(yù)備1#(a,a),(a),a)#進(jìn)2#(a

9、,a),(a),a)#進(jìn)3#(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#(S,(a),a)#歸13#(T,(a),a)#歸 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

10、#(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#歸P1333(1) FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)(2)a(),a(=,是算符文法，并且是算符優(yōu)先文法(3)優(yōu)先函數(shù)a(),f44244g55523 （4） 棧輸入字符串動(dòng)作#（a,(a,a)）#預(yù)備#(a, (a,a)#進(jìn)#(a, (a,a)#進(jìn)#(t

11、, (a,a)#歸#（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#歸successP1345(1)..1.(2)1987 S A S 11100 a 432 A S d 56確定化：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,101162,3,5,7,102,4,5

12、,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,102,5,7,8,102,3,5,7,9,10116116 A S3:5:6: S A a b S a A S b S A b a A4:0:7: A S b a a b b a2:1: DFA構(gòu)造LR(0)項(xiàng)目集規(guī)范族也可以用GO函數(shù)來(lái)計(jì)算得到。所得到的項(xiàng)目集規(guī)范族與上圖中的項(xiàng)目集一樣:=，GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(

13、，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=項(xiàng)目集規(guī)范族為C=，(3)不是SLR文法狀態(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)歸約沖突消解

14、所以不是SLR文法。(4) 構(gòu)造例如LR(1)項(xiàng)目集規(guī)范族見(jiàn)下圖：對(duì)于狀態(tài)5，因?yàn)榘?xiàng)目，所以遇到搜索符號(hào)a或b時(shí)，應(yīng)該用歸約。又因?yàn)闋顟B(tài)5包含項(xiàng)目，所以遇到搜索符號(hào)a時(shí)，應(yīng)該移進(jìn)。因此存在“移進(jìn)-歸約”矛盾，所以這個(gè)文法不是LR(1)文法。 b b b8：1：5： A A A S a a S3： S a S3：0： a a A a A6：9： 4： S b S A b a a S b b7：2：10： S b A A5：第六章/*第六章會(huì)有點(diǎn)難P1645(1)EE1T if (E1.type = int) and (T.type = int )then E.type := intelse

15、E.type := realETE.type := T.typeTnum.num T.type := realTnumT.type := int(2)P1647SL1|L2S.val:=L1.val+(L2.val/2)SLS.val:=L.valLL1BL.val:=2*L1.val + B.val; L.length:=L1.length+1LBL.val:=B.c; L.length :=1B0 B.c:=0B1B.c:=1*/第七章P2171a*(-b+c)abc+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)abcd+*+if (x+y)*z =0 then (a+

16、b)c else abcxy+z*0= ab+cabc ￥或 xy+z*0= P1 jez ab+c P2 jump abc P1 P2P2173-(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), -(3) +, c, d(4) *, (2), (3)(5) +, (1), c(6) -, (4), (5)間接碼表：(1)(2)(3)(4)(1)(5

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

18、(10)+D) i:=E*(-iA-B-C(11)+D) i:=E*(-EA-B-C(,C,-, )(12)+D) i:=E*(EA-B-(13)D) i:=E*(E+A-B-(14) i:=E*(E+iA-B-D(15)i:=E*(E+EA-B-D(+,D,)(16)i:=E(EA-B-(17)i:=E*(E)A-B-(18)i:=E+EA-B-(*,B,)(19)i:=EA-(:=,-,A)(20) A產(chǎn)生的四元式：(,C,-, )(+,D,)(*,B,)(:=,-,A)P2185/*設(shè)A ：10*20，B、C、D：20，寬度為w4 則T1:= i * 20T1:=T1+jT2:=A84T

19、3:=4*T1Tn:=T2T3 /這一步是多余的T4:= i + jT5:=B4T6:=4*T4T7:=T5T6T8:= i * 20T8:=T8+jT9:=A84T10:=4*T8T11:=T9T10T12:= i + jT13:=D4T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C4T18:=4*T16T19:=T17T18T20:=T7+T19Tn:=T20*/P2186100. (jnz, A, -, 0)101. (j, -, -, 102)102. (jnz, B, -, 104)103. (j, -, -, 0)104. (jnz, C, -, 1

20、03)105. (j, -, -, 106)106. (jnz, D, -, 104) -假鏈鏈?zhǔn)?07. (j, -, -, 100) -真鏈鏈?zhǔn)准冁湥?06,104，103真鏈：107,100P2187100. (j, A, C, 102)101. (j, -, -, 0)102. (j,E1.place ,E2.place ,0);emit(I.Place :=E1.place);F.truelist := makelist(nextquad);emit(j,-,-,-);F.place := I.place;F.end := E2.place;p:=lookup(); i

21、f p nil thenI.place := pelse error M.quad := nextquad*/方法2：S for id:=E1 to E2 do S1S F S1F for id:=E1 to E2 do doINITIAL=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

22、();if F.placenil thenemit(F.place := INITIAL)F.quad:=nextquad;F.final:=FINAL;backpatch(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);第九章P2709(1) 傳名即當(dāng)過(guò)程調(diào)用時(shí)，其作用相當(dāng)于把被

23、調(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); print A; A=9 (2) 傳地址即當(dāng)程序控制轉(zhuǎn)入被調(diào)用段后，被調(diào)用段首先把實(shí)在參數(shù)抄進(jìn)相應(yīng)的形式參數(shù)的形式單元中，過(guò)程體對(duì)形參的任何引用或賦值都被處理成對(duì)形式單元的間接訪問(wèn)。當(dāng)被調(diào)用段工作完畢返回時(shí)，形式單元（都是指示器）所指的實(shí)參單元就持有所希望的值。A:=2;B:=3;T:=A+B把T,A,A的地址抄進(jìn)已知單元J1,J2,J3x:J1;y:=J2;z:=J3 /把實(shí)參地址抄進(jìn)形式單元，且J2=J3Y:=y+1 Z:=z+x / Y：對(duì)y的間接訪問(wèn) Z：對(duì)z的間接訪問(wèn)print AA=8(3) 得結(jié)果每個(gè)形參均對(duì)應(yīng)兩個(gè)單元，第一個(gè)存放實(shí)參地址，第二個(gè)存放實(shí)參值，在過(guò)程體中對(duì)形參的任何引用或賦值都看成是對(duì)它的第二個(gè)單元的直接訪問(wèn)，但在過(guò)程工作完畢返回前必須把第二個(gè)單元的內(nèi)容放到第一個(gè)單元所指的那個(gè)實(shí)參單元中A:=2;B:=3;T