編譯原理第三版答案.doc

第二章P36-6(1)是09組成的數(shù)字串(2)最左推導:最右推導:P36-7G(S)P36-8文法：最左推導:最右推導:語法樹：/*/P36-9句子iiiei有兩個語法樹：P36-10/*/P36-11/*L1:L2:L3:L4:*/第三章習題參考答案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 0 1 0543 0 1 0 1 1 1P648(1) (2)(3)P6412(a) a10 a,b a確定化：ab00,110,10,1110給狀態(tài)編號：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已經確定化了,進行最小化最小化：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)編號：01012112213333 010 0 1 032 1 1 1 0最小化： 0310 1 1 1 0 0第四章P811(1) 按照T,S的順序消除左遞歸(2)FIRST(S)=a,(FIRST(T)=a,(FIRST()=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW()=)預測分析表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,+,),#FOLLOW(P)=*,(,a,b,+,),#(2)考慮下列產生式: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#EETTFFPP813/*(1) 是，滿足三個條件。(2) 不是，對于A不滿足條件3。(3) 不是，A、B均不滿足條件3。(4) 是，滿足三個條件。*/第五章P1331短語: E+T*F, T*F,直接短語: T*F句柄: T*FP1332文法：(1)最左推導:最右推導:(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“移進-歸約”過程：步驟棧輸入串動作0#(a,a),(a),a)#預備1#(a,a),(a),a)#進2#(a,a),(a),a)#進3#(a,a),(a),a)#進4#(a,a),(a),a)#進5#(S,a),(a),a)#歸6#(T,a),(a),a)#歸 7#(T,a),(a),a)#進8#(T,a),(a),a)#進9#(T,S),(a),a)#歸10#(T),(a),a)#歸11#(T),(a),a)#進12#(S,(a),a)#歸13#(T,(a),a)#歸 14#(T,(a),a)#進15#(T,(a),a)#進16#(T,S,(a),a)#歸17#(T,(a),a)#歸18#(T,(a),a)#進19#(T,(a),a)#進20#(T,(a),a)#進21#(T,(S),a)#歸22#(T,(T),a)#歸23#(T,(T),a)#進24#(T,S),a)#歸25#(T),a)#歸26#(T),a)#進27#(S,a)#歸28#(T,a)#歸29#(T,a)#進30#(T,a)#進31#(T,S)#歸32#(T)#歸33#(T)#進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） 棧輸入字符串動作#（a,(a,a)）#預備#(a, (a,a)#進#(a, (a,a)#進#(t, (a,a)#歸#（t,(a,a)）#進#（t,（a,a）#進#（t,（a,a）#進#（t,（t,a）#歸#（t,（t,a）#進#（t,（t,a）#進#（t,（t,s）#歸#（t,（t）#歸#（t,（t）#進#（t,s）#歸#（t）#歸#（t）#進# s#歸successP1345(1)0.1.2.3.4.5.6.7.8.9.10.11.(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,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構造LR(0)項目集規(guī)范族也可以用GO函數(shù)來計算得到。所得到的項目集規(guī)范族與上圖中的項目集一樣:=，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)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=GO(，a)= =GO(，b)= =GO(，S)= ，=GO(，A)= ，=項目集規(guī)范族為C=，第六章/*第六章會有點難P1645(1)EE1T if (E1.type = int) and (T.type = int )then E.type := intelse E.type := realETE.type := T.typeTnum.num T.type := realTnumT.type := int(2)P1647SL1|L2S.val:=L1.val+(L2.