完整word版編譯原理清華大學(xué)第2版課后習(xí)題答案

1、第三章N=D= 0,123,4,5,6,7,8,9N=ND=NDDL=a |a(0|1|3.|9) n 且 n=1(0|1|3.|9) n 且 n=1ab,a nbn n=1第6題.(1) = = = i表達(dá)式 = = = ()= ()= ()=(i)表達(dá)式 = = * = * =i*i表達(dá)式 = + = + = *+= *+ = *+ =i*i+i 表達(dá)式 = +=+ = i+ = i+()= i+(i+(+)因子 +項 =i+ 項 表達(dá)式+項)= i+(i+i)表達(dá)式 = + = + = i+ = i+ 項* = i+* =i+i*i9i第9題語法樹推導(dǎo)：S=SS*=SS+S*=aa+a*

2、11. 推導(dǎo):E=E+T=E+T*F語法樹：E+T*FT*F短語：T*F直接短語:句柄:T*F12.vPOPvMOP短語：vTxFxM OP 直接短語：句柄：13.(1)最左推導(dǎo)：S = ABS = aBS =aSBBS = aBBS= abBS = abbS = abbAa = abbaa最右推導(dǎo)：S = ABS = ABAa = ABaa = ASBBaa= ASBbaa = ASbbaa = Abbaa = a1b1b2a2a3ABS文法：SSAaab短語：a1 , b1 , b2, a2 , , bb , aa , abbaa,直接短語：句柄：a1a1 , b1 , b2, a2 ,1

3、4 (1)SABaAb |aBb |1S0A 0A1 |第四章1. 1.構(gòu)造下列正規(guī)式相應(yīng)的DFA(1) 1(0|1)*101NFA0,1(2) 1(1010*11(010)*1)*0NFAba,b2.解：構(gòu)造DFA矩陣表示01X0ZXZ *X,ZYX,Z*X,ZX,YYX,YX,YX,Y,ZXX,Y,Z*X,Y,ZX,Y其中0表示初態(tài),*表示終態(tài)用 0, 1， 2， 3, 得DFA狀態(tài)圖為:5分別代替 X Z X,ZY X,Y X,Y,Z3.解：構(gòu)造DFA矩陣表示 構(gòu)造DFA的矩陣表示01S0V,QQ,UV,QZ,VQ,UQ,UVQ,U,ZZ,V *ZZVZQ,U,Z *V,ZQ,U,ZZZ

4、Z其中0表示初態(tài)，*表示終態(tài)替換后的矩陣010012132245*366465*35666構(gòu)造DFA狀態(tài)轉(zhuǎn)換圖(略)4. (1 )解構(gòu)造狀態(tài)轉(zhuǎn)換矩陣:ab00*0,110,1 *0,1110轉(zhuǎn)換為ab0*121*12202 , 3 0 , 12 , 3a=0,32,3,0,10,1a=1,1 0,1b=2,2(2)解：首先把M的狀態(tài)分為兩組：終態(tài)組0,和非終態(tài)組1 , 2, 3,4,5 此時G=( 0,1,2,3,4,5)1,234,5a=1,3,0,51,234,5b=4,3,2,5由于4 a=0 1,2,3,5 a=1,3,5因此應(yīng)將1,2,3,4,5 劃分為4,1,2,3,5G=(041

5、,2,3,5)1,2,3,5 a=1,3,51,2,3,5 b=4,3,2因為1,5 b=4 23 b=2,3所以應(yīng)將1,2,3,5戈y分為1,52,3b=4 所以1,5 不用再劃分b=3,2 a=3所以2,30,2,3,4,1,5G=(01,52,34)1,5 a=1,5 1,52,3 a=1,3 2,3應(yīng)劃分為23)因為2 a=1 3所以化簡后為G=(確定化，構(gòu)造 DFA矩陣abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD變換為ab00131122*34335416*514634化簡：G=(0,1,3,4,6),(2,5)0,1,3,4,6a=1,30,1,3,4,6b=2,

6、3,4,5,6所以將0,134,6戈y分為0,4,61,3G=(0,4,6),(1,3),(2,5)0,4,6b=3,6,4所以劃分為0,4,6G=(0),(4,6),(1,3),(2,5)不能再劃分，分別用 0, 4, 1 , 2代表各狀態(tài)，構(gòu)造DFA狀態(tài)轉(zhuǎn)換圖如下;ab&代入得S = 0(1S|1)| 1(0S|0)=01(S| s) | 10(S|=(01|10)(S| s)=(01|10)S | (01|10)=(01|10)(01|10)+9.狀態(tài)轉(zhuǎn)換函數(shù)不是全函數(shù)，增加死狀態(tài)8,G=(1,2,3,4,5,8),(6,7)(1,2,3,4,5,8)(1,2,3,4,5,8)(1,2,

7、3,4,5,8)(1.2.3.4.5.8)a=(3,4,8)(3,4)b=(2,6,7,8) c=(3,8)d=(3,8)應(yīng)分出所以應(yīng)彳將(1,2,3,4,5,8)G=(1,2,5,8),(3,4),(6,7)(1.2.5.8) a=(3,4,8)8(1.2.5.8) b=(2,8)(1.2.5.8) c=(8)(1.2.5.8) d=(8)G=(1,2,5),(8),(3,4),(6,7)(1,2,5)a=(3,4,8) 5應(yīng)分出應(yīng)分出G=(1,2), (3,4),5, (6,7) ,(8) 去掉死狀態(tài)最終結(jié)果為以1,3,5,6代替,最簡DFA為b(1,2) (3,4) 5,(6,7)第五章

8、1.11S-a | A |( T )T - T , S | S(a,(a,a)=S = ( T ) = ( T , S ) = ( S , S ) = ( a , S) = ( a, ( T ) =(a , ( T , S ) ) = (a , ( S , S ) = (a , ( a , a ) S=(T) = (T,S) = (S,S) = ( ( T) , S )= ( ( T , S ), S ) = ( ( T , S , S ) , S ) =( (S,S ,S),S)= (T ) , S , S ) , S )=( ( T ,S ) , S , S ) ,S ) =( ( ( S

9、 , S ) , S , S ) , S) =( (a,S ),S,S) , S )= (a , a ) , S , S ) , S) = ( ( a ,a ) , a , S ) , S ) = ( ( ( a , a ) , a , ( T ) ) ,S )= (a , a ) , A , ( S ) ) ,S )= ( ( a , a ) , a ,( a ) ) , S ) = ( ( ( a , a ) , a ,( a ), a)S-a | A 1( T )T - T , ST - S消除直接左遞歸:S-a | A |( T )T - S T T- , S Tl ESELECT (

10、 S-a) = aSELECT ( S-A) = ASELECT ( S-( T ) ) = (SELECT ( T - S T ) = a , a , (SELECT ( T - , S T) = ,SELECT ( T - E ) = FOLLOW ( T ) = FOLLOW ( T ) = ) 構(gòu)造預(yù)測分析表aA()J#S- a- A- (T )T- S T - S T - S T T- E- ,S T 分析符號串 （a,a ） #分析棧剩余輸入串所用產(chǎn)生式#S(a , a) #S - ( T )# ) T (a , a) #（匹配# ) Ta , a ) #T - S T # ) T

11、Sa , a ) #S - a# ) Taa , a ) #a匹配# ) T，a) #T- , S T# )S ,a ) #,匹配# ) TSa ) #S-a# ) Taa ) #a匹配# ) T)#T-E# )#）匹配#接受2.E-TE E-+EE- E T-FT T-T T- EF-PF F-*F F- EP-(E)P-aP-bP- A非終結(jié)符名是否= FIRST 集FOLLOW 集E否 (, a, b, N#,) E是+, #,) T否 (, a, b, N+ , #,) T是 ,(, a, b, N+ , #,) F否 (, a, b, N (, a, b, N，+, # ,) F是*

12、, ( , a , b , N, +, # ,) P否 (, a, b, N*, ( , a , b , N, #, ) (,a, b, N)SELECTSELECTSELECT SELECT SELECT(E TE)(E， +E )(E )(T FT (T T )=FIRST(TE )=FIRST(T)= =+=FOLLOW(E )= # , =FIRST ( F) = (, =FIRST (T) = (,)a, b, a, b,NN )SELECT(T SELECT(F SELECT(F SELECT(F PF )=FIRST(F)= (,*F )=* )=FOLLOW(F )= )=FO

13、LLOW(T )= +, #, )a, b, N(,a, b, N，+, #,)3. S-MHFIRST ( S ) =FIRST(MH)= FIRST ( M )FIRST( H ) = FIRST ( L )FIRST( K ) = d , E FIRST( M ) = FIRST ( K )S-a H-Lso H- EK-dML K- EI-eHfM-K M-bLMU FIRST ( H ) U E U a= a, d , b , e , E E = e , E d,b, E15FOLLOW ( S ) = # , o FOLLOW ( H ) = FOLLOW ( S )FOLLOW

14、( K ) = FOLLOW ( M )=FOLLOW ( L ) = FIRST ( S )- E U o U FOLLOW ( K )U FIRST ( M )- E U FOLLOW ( M )U FOLLOW ( S ) = e , # , o =a, d , b , e , # , o FOLLOW ( M ) = FIRST ( H )- E U FIRST ( L )- E -E ) U FOLLOW ( S )FIRST ( H )- E ) U FOLLOW ( S )SELECT ( S- M H) = ( FIRST ( M H)=(FIRST( M ) U= d , b

15、 , e , # , o SELECT ( S- a ) = a SELECT ( H-L S o ) = FIRST(L S o) = e SELECT ( H - E ) = FOLLOW ( H ) = f , # , o SELECT ( K- d M L ) = d SELECT ( K- E ) = FOLLOW ( K )= e , # , o SELECT ( l_- e H f ) = e SELECT ( M-K ) = ( FIRST( K )- E ) U FOLLOW ( M )= d , e , # , o abedfo#S- a- M H- M H- M H- M

16、 H- M HH-L S o- E- E- EK- E- d M L- E- EL- e H fM- b L M-K-K-K-KSELECT ( M - b L M )= b 構(gòu)造LL( 1 )分析表4.文法含有左公因式，變?yōu)镾-C $ b, a C- b A b C- a B a A - b A A b A- a A a A E $ , a, b A- C a , b B-a B B a B - b B b B- E $ , a , b B- C a, b 5. -S如果語句 E -FS-beg in A endA- BA- A ; B A B C D begi n A endA- B A

17、A- ; B A A- E begin a , if ; end B- CB- CB- DB- DC- aD- ED- E else BE- FCC- aD- E D D - else BD- EE- FCF- if b thenF- if b then if a if else ; , end if if 非終結(jié)符是否為空S否 A-否 A 是B-否 C-否 D-否 D 是 E-否 F-否FIRST(S) = begi n FIRST(A) = FIRST(B) FIRST(A = ; , E FIRST(B) = FIRST(C)FIRST(C) = aFIRST(D) = FIRSTFIR

18、SR(D = else ,U FIRST(A U E = a , if , ; , EU FIRST(D) = a , if (E) = if E FIRST(E) = FIRST(F) = if FIRST(F) = if FOLLOW(S) = # S A AB C D D E FFOLLOW(A) = e nd FOLLOW(A ) = end FOLLOW(B) = ; , end FOLLOW (C) = ; , end , else FOLLOW(D) = ; , end FOLLOW( D = ; , end FOLLOW(E) = else , ; end FOLLOW(F)

19、= a ifthe nelsebeginendabJ#S-begi n A endA- B A - B A，A - E- ;BA，B- D- CC- aD- E D D - else BD，- E- EE-FCF-if b the nif the n else begi n enda b ;6. 1.(1) S - A | B A - aA|a(3)B - bB |b提取 (2) , ( 3)左公因子(1) S - A | B A - aA A 4 A| E B - bB (4)7. (1)19 B B | E2.(1) S-AB(2) A-Ba| E(3) B-Db|D(4) D- d|E

20、提取( 3)左公因子(1) S-AB(2) A-Ba| E(3) B-DB (4) B-b|E(5) D- d|E3.(1) S-aAaB | bAbB(2) A- S| db(3) B-bB|a4(1) S-i|(E)(2) E-E+S|E-S|S 提取( 2)左公因子(1)(2)(3)5S-i|(E)E-SEE -+SE |-SE | E(1)(2)(3)消除( 1) (3)直接左遞歸(1)(2)(3)(4)(5)S-SaA | bBA-aB|cB-Bb|dS-bBS S-aAS |E A-aB | c B - dB B -bB |E6.(1) M-MaH | H(2) H-b(M) |

21、(M) |b消除( 1)直接左遞歸，提取( 2)左公因子(1)(2)(3)M- HM M - aHM |EH-bH |( M )H -(M) | E1)2)3)4)將 1)、 2)式代入 3)式1)2)3)4)5)提取A-baBA- E B-AbbB-aA-baBA- EB-baBbbB-bbB-a3)、 4)式左公因子1)2)3)4)5)A-baBA- EB-bB B - aBbb | bB-a(3)1)2)3)4)S-Aa S-b A-SBB-ab將 3 )式代入 1)式1)2)3)4)消除 1 )式直接左遞歸S-SBaS-b A-SBB-ab1)2)3)4)5)S-bS S-BaS| E

22、S-bA-SBB-ab刪除多余產(chǎn)生式 4)1)2)3)4)S-bS S-BaS| ES-bB-ab(5)1)2)3)4)5)S-AbS-BaA-aAA-aB-a提取 3) 4)左公因子1)2)3)4)5)S-Ab S-BaA-aA A- A | EB-a將 3 )代入 1) 5 )代入 2S-aAbS-aaA-aA A- A | EB-a1)2)3)4)5)提取 1) 2) 左公因子1)2)3)4)5)S- aS S-Ab | a A-aA A- A | E B-a刪除多余產(chǎn)生式 5)S- aS S-Ab | a A-aA A- A | E A S S1)2)3)4)A將 3 )代入 4)1)

23、2)3)4)S- aS S-A b | a A-aA A - aA E將 4 )代入 2)1)2)3)4)5)6)S- aS S-aAb S-a S-bA-aA A- aA|E對 2) 3)提取左公因子1)2)3)4)5)S-aS S-aS S-A b| ES-b A-aA A- aA|E刪除多余產(chǎn)生式 5)S-aS S-aS S-A b| E1)2)6)3)214) S-b5) A - aA E第六章a | A 1( T )T , S | S解：求 FIRSTVT 集FIRSTVT (S) = #FIRSTVT (S)FIRSTVT (T) 求LASTVT集LASTVT (S(1)增加輔助產(chǎn)

24、生式S # S#=aA=，u(= a A ( FIRSTVT( S ) = , a= # A )A )aA()J#a A ( = J # =LASTVT (S) = aLASTVT (T) = , a 算符優(yōu)先關(guān)系表因為任意兩終結(jié)符之間至多只有一種優(yōu)先關(guān)系成立，所以是算符優(yōu)先文法(3)優(yōu)先關(guān)系 ( = a + # =因為任意兩終結(jié)符之間至多只有一種優(yōu)先關(guān)系成立，所以是算符優(yōu)先文法(2)句型 a(T+S);H;(S)的短語有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H 直接短語有：a T+S H (S)句柄： a素短語：a T+S (S)最左素短語：a分析

25、a; ( a+ a)優(yōu)先關(guān)系當(dāng)前符號剩余輸入串移進(jìn)或規(guī)約#(a + a)#規(guī)約# T (a + a)#移進(jìn)# T; (a + a)#移進(jìn)# T;(+a)#規(guī)約# T; (T +a)#移進(jìn)# T; (T+)#規(guī)約# T; (T+ T )#規(guī)約# T; (T=)#移進(jìn)# T; (T) #規(guī)約# T; T #規(guī)約# T=#接受分析 a; ( a+ a)優(yōu)先關(guān)系當(dāng)前符號剩余輸入串移進(jìn)或規(guī)約#(#( a#( T#( T+#( T+ a#( T+ T#( T#( T)# Ta)#a + a) #移進(jìn)+ a )#移進(jìn)a )#規(guī)約)#移進(jìn))#移進(jìn)#規(guī)約#規(guī)約#移進(jìn)規(guī)約接受a(4)不能用最右推導(dǎo)推導(dǎo)出上面的兩個

26、句子。第七章1已知文法:A 7 aAd|aAb| Eab#給出分析過程。判斷該文法是否是 SLR( 1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串 解：(0) A(1)AA構(gòu)造該文法的活前綴 DFA狀態(tài)ACTIONGOTOadb#A0S2R3R3R311acc2S2R3R3R333S4S54R1R1R15R2R2R2輸入串a(chǎn)b#的分析過程：步驟狀態(tài)棧符號棧輸入串ACTIONGOTO10#ab#S2202#ab#R333023#aAb#S540235#aAb#R21501#A#acc由上圖可知該文法是 SLR (1) 構(gòu)造SLR (1)的分析表：文法。3、考慮文法:S T AS|b(1)(2)解:A

27、TSA|a列出這個文法的所有 LR( 0)項目按(1)列出的項目構(gòu)造識別這個文法活前綴的NFA把這個NFA確定化為DFA說明這個 DFA規(guī)范族。SLR分析表。的所有狀態(tài)全體構(gòu)成這個文法的 LR ( 0) 這個文法是SLR的嗎？若是，構(gòu)造出它的 這個文法是 LALR或LR (1)的嗎？(0) St S(1)列出所有STS(1)S T AS (2)S T b (3)A LR (0)項目：ST SA (4)A T aT S TAST b TSAT S AT SA-構(gòu)造該文法的活前綴NFA在I1中含項目：ST S 歸約項Follow(S)=#ATa移進(jìn)項Follow(S)n a=STb移進(jìn)項Follo

28、w(S)n b=在13中含項目：AT SA-歸約項Follow(A)=a,bSTb移進(jìn)項Follow(A)n bATa移進(jìn)項Follow(A)n a*在15中含項目：ST AS-歸約項Follow(S)=#,a,bATa移進(jìn)項Follow(S)n aSTb移進(jìn)項Follow(S)n b r由上可知：I1I3 I5中存在著移進(jìn)和歸約沖突SLR (1)文法。由此可知，13、15的移進(jìn)與歸約沖突不能解決，所以這個文法不是(4)做LR( 1)項目集規(guī)范族Io:S- S , #S - AS , a/b/#S -今 b ,a/b/#A -今 SA ,a/bA -T a ,a/bI1:St S ,# TS-

29、 A ,a/b-SA ,a/b-a ,a/b-AS ,a/b-b ,a/bI2 :ST A S ,a/b/#SAS ,a/b/#ST b ,a/b/#AT SA ,a/bAT a ,a/bI3：S 7 b ,a/b/#I4：A 7 a ,a/b/#I5： (li-A-)ASl6： (l1-S-)A 7 S A ,a/bA 7. SA ,a/bA 7. a ,a/bS 7. AS ,a/bS 7 b ,a/bl7： (I 2-S-)SA7 AS-,a/b/#7 S A ,a/b/# 7 SA ,a/b 7 a ,a/b 7 AS ,a/b 7 b ,a/b7SA- ,a/b7 A S ,a/bA

30、S ,a/b b ,a/bSA ,a/b a ,a/b由上可知該文法不是 LR ( 1)文法，也不是 LALR( 1)文法。5、一個類ALGOL的文法如下: 7 7 7 ; vBlock head宀 begin d vBlock head ;d 7 s end 7 S; 7 begin試構(gòu)造其LR (0)分析表。解：設(shè) =A =B =C=D =EE 7s；E C 7 begin EA7 Ba 7 C B 7 D； E D 7 begin d D 7 D;d E 7 s end(0)A 7 A (1) A7 B (2)A7 C (3)B7 D;E begin d D 7 D;d (6) E7 s

31、 end (7) E 7 s;E (8) C 7 begin E構(gòu)造該文法的活前綴DFA狀態(tài)ACTIONGOTObegin;dSend#ABCDE0S512341acc2R1R1R1R1R1R13R2R2R2R2R2R24S65S9S786S11S7107S13S128R8R8R8R8R8R89R4R4R4R4R4R410R3R3R3R3R3R311R5R5R5R5R5R512R6R6R6R6R6R613S71414R7R7R7R7R7rR76、文法 G= (U，T，S，a,b,c,d,e,P,S )其中 P 為:St UTa|Tb T S|Sc|d U US|eLR (1),說明理由。(1)

32、 判斷 G是 LR (0) , SLR (1), LALR (1)還是(2) 構(gòu)造相應(yīng)的分析表。解：(0) St S (1)S t UTat Tb (3)Tt Sc (5)T t dQU tus (7)U t e產(chǎn)生移進(jìn)一規(guī)約喝規(guī)約-規(guī)約沖突Follow(U)=d,e Follow(T)=a,bI0 : s-s s UTa S-Tb U-us U - e T - S T-Sc TI1:SS-TS- c(11產(chǎn)生移進(jìn)規(guī)約沖突，但Follow(s)n c= e可以用SLR (1)解決)I2: Su-Ta UU - S S -UTa S-TbU - us U - e T-S TI3: ST.b14:

33、 Ue -I5:Td -I6:TScI7:SUT-a ST- bI8:Uus-TS- T S - c首先做LR ( 0)分析:-d-Sc T d可以用SLR( 1)的方法解決19: SUTa-I10: S Tb 所以該文法是 SLR (1)文法，也是 LALR( 1)文法，LR( 1)文法。構(gòu)造SLR ( 1)分析表: 狀態(tài) IACTIONGOTOabcde#SUT0S12S111231S6acc2S5S48273S104R7R75R5R56R4R47S9S108R3R3S6R6R69R1R1R1R110R2R2R2R2證明下面文法不是 LR ( 0)但是SLR (1)。B T aAc|a|a

34、AbSt a a t Ab|bBa證明：(0) St S(1)ST A (2)A T Ab (3)A t bBa (4)B t aAc(6)B構(gòu)造該文法的活前綴DFA在12項目集中含有：S7A -A7A- b在14項目集中含有：B7a A7 bBa 在19項目集中有B aAb AAb Follow(B)文法的沖突項可以用SLR ( 1)歸約項 移進(jìn)項歸約項移進(jìn)項規(guī)約項規(guī)約項nFollow(S)=# Follow(S)n b=Follow(B)=a Follow(B)n b=Follow(B)=a Follow(A)=b,c,# Follow(A)= 文法來解決，所以該文法是SLR(1)文法，不是LR(0)文法。11、設(shè)文法GS為: S(1)(2)(3) 解：7 AS| E A 7aA|b證明GS是LR (1)文法； 構(gòu)造它的LR