編譯原理課后習(xí)題

1、第二章P36-6(1)是09組成的數(shù)字串(2)最左推導(dǎo):最右推導(dǎo):P36-7G(S)P36-8文法：最左推導(dǎo):最右推導(dǎo):語(yǔ)法樹(shù)：/*P36-11/*L1:L2:L3:L4:*/9、對(duì)下面情況給出DFA及正規(guī)表達(dá)式：(1）0,1上的含有子串010的所有串。正規(guī)式：(0 | 1)* 010 (0 | 1)* (2） 0,1上不含子串010的所有串。正規(guī)式：1*(0|11*1)* 1*( 0 | 11)*1* 1*0*1* (0 | 11)*(0 | 1)10. 一個(gè)人帶著狼、山羊、白菜在一條河的左岸。狀態(tài) 左岸 右岸 0 人，羊，狼，菜 NULL 1 狼，菜 人，羊 2 人，狼，菜 羊 3 狼 人

2、，羊，菜 4 人，羊，狼 菜 5 羊 人，狼，菜 6 人，羊 狼，菜 7 NULL 人，羊，狼，菜 P6412(a) a10 a,b a確定化：ab00,110,10,1110給狀態(tài)編號(hào)：ab012112203333 a10 a a b b b32 b a最小化：210 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 aP811(1) 按照T,S的順序消除左遞歸遞歸子程序：procedure S;beginif sym=a or sym= then abvanceelse if sym=( then b

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

4、(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)考慮下列產(chǎn)生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FO

5、LLOW(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= then begin T; E end else errorendprocedure E;beginif sym=+ then begin advance; E end else if sym) and sym# t

6、hen 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 errorendprocedure F;beginif sym=( or sym=a or sym=b or sym= then begin P; F end else errorendprocedure F;beginif sym=* then b

7、egin 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;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,

8、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,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)#

9、歸 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,(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

10、,)LASTVT(T)=,a,)(2)a(),a(=,是算符文法，并且是算符優(yōu)先文法P1345(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

11、,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(，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