1、1第三章第三章N=D=N=D= 0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9N=ND=NDDN=ND=NDDL=aL=a |a(0|1|3.|9)|a(0|1|3.|9)n n 且且 n=1n=1(0|1|3.|9)(0|1|3.|9)n n 且且 n=1n=1 ab,ab, a an nb bn n n=1n=1第第 6 6 題題. .(1)(1) = = = i i(2)(2) = = = () = ()= ()=(i)=(i)(3)(3) = = * = * =i*i=i*i(4)(4) = + + = + = *+ = *+ = *+ = = i*i+i

2、i*i+i(5)(5) = +=+ = +=i+=i+ = i+i+ = i+(i+() = i+(i+(+)= i+(i+(+) = i+(i+i)i+(i+i)(6)(6) = + = + = + = i+i+ = i+i+* = i+i+* = = i+i*ii+i*i第第 7 7 題題 * *i ii i+ +i i2 + +i ii i* *i i第第 9 9 題題 語法樹語法樹 sss*ss+aaa推導: S=SS*=SS+S*=aa+a*11.11. 推導推導:E=E+T=E+T*F:E=E+T=E+T*F 語法樹語法樹: :EE+TTF*短語短語: : T*FT*F E+T*F

3、E+T*F直接短語直接短語: : T*FT*F句柄句柄: : T*FT*F1212 3 短語：短語： 直接短語：直接短語： 句柄：句柄： 13.(1)13.(1)最左推導：最左推導：S S = ABSABS = aBSaBS =aSBBS=aSBBS = aBBSaBBS = abBSabBS = abbSabbS = abbAaabbAa = abbaaabbaa最右推導：最右推導：S S = ABSABS = ABAaABAa = ABaaABaa = ASBBaaASBBaa = ASBbaaASBbaa = ASbbaaASbbaa = AbbaaAbbaa = a1b1b2a2a3a

4、1b1b2a2a3 (2)(2) 文法：文法：S S ABSABSS S AaAaS S A A a aB B b b (3)(3) 短語：短語：a1a1 , , b1b1 , , b2,b2, a2a2 , , , , bbbb , , aaaa , , abbaa,abbaa, 直接短語：直接短語： a1a1 , , b1b1 , , b2,b2, a2a2 , , , , 句柄：句柄：a1a11414 (1)(1)S S ABABA A aAbaAb | | B B aBbaBb | | (2)(2) S S 1S01S0 S S A A A A 0A10A1 |第四章第四章1.1. 1

5、.1. 構造下列正規式相應的構造下列正規式相應的 DFADFA(1)(1)1(0|1)*1011(0|1)*101NFANFA012311010,14(2)(2) 1(1010*|1(010)*1)*01(1010*|1(010)*1)*0NFANFA42000400001011101010(3)NFA(3)NFA(4)NFA(4)NFA01b36a2bb4ab5b2.2.解：構造解：構造 DFADFA 矩陣表示矩陣表示0 01 1XX0 0ZZXXZZ * *X,ZX,ZYYX,ZX,Z * *X,ZX,ZX,YX,YYYX,YX,Y01a34ba,b2aab5X,YX,YX,Y,ZX,Y,

6、ZXXX,Y,ZX,Y,Z * *X,Y,ZX,Y,ZX,YX,Y其中其中0 0 表示初態，表示初態，* *表示終態表示終態用用 0 0，1 1，2 2，3 3，4 4，5 5 分別代替分別代替 XX ZZ X,ZX,Z YY X,YX,Y X,Y,ZX,Y,Z得得 DFADFA 狀態圖為：狀態圖為：350211400100110103 3解：構造解：構造 DFADFA 矩陣表示矩陣表示構造構造 DFADFA 的矩陣表示的矩陣表示0 01 1SS0 0V,QV,QQ,UQ,UV,QV,QZ,VZ,VQ,UQ,UQ,UQ,UVVQ,U,ZQ,U,ZZ,VZ,V* *ZZZZVVZZQ,U,Z*Q

7、,U,Z*V,ZV,ZQ,U,ZQ,U,ZZZZZZZ其中其中0 0 表示初態，表示初態，* *表示終態表示終態替換后的矩陣替換后的矩陣0 01 10 00 01 12 21 13 32 22 24 45 53 3* *6 66 64 46 65*5*3 35 56 66 66 6構造構造 DFADFA 狀態轉換圖（略）狀態轉換圖（略）4 4 （1 1）解）解構造狀態轉換矩陣：構造狀態轉換矩陣： 6a ab b000*0*0,10,1110,10,1* *0,10,1111100轉換為轉換為a ab b0 0* *1 12 21 1* *1 12 22 20 022，33 00，1122，3a

8、=0,33a=0,32,3,0,12,3,0,10,1a=1,10,1a=1,1 0,1b=2,20,1b=2,2（2 2）解：首先把）解：首先把 M M 的狀態分為兩組：終態組的狀態分為兩組：終態組00，和非終態組，和非終態組11，2 2，3 3，4,54,5 此時此時 G=(G=( 0,0,1,2,3,4,51,2,3,4,5 ) )1,2,3,4,51,2,3,4,5a a=1,3,0,5=1,3,0,51,2,3,4,51,2,3,4,5b b=4,3,2,5=4,3,2,5由于由于44a a=0=0 1,2,3,51,2,3,5a a=1,3,5=1,3,5因此應將因此應將1,2,3

9、,4,51,2,3,4,5劃分為劃分為4,1,2,3,54,1,2,3,5G=(041,2,3,5)G=(041,2,3,5)1,2,3,51,2,3,5a a=1,3,5=1,3,51,2,3,51,2,3,5b b=4,3,2=4,3,2因為因為1,51,5b b=4=4 2323b b=2,3=2,3所以應將所以應將1,2,3,51,2,3,5劃分為劃分為1,52,31,52,3G=(01,52,34)G=(01,52,34)1,51,5a a=1,5=1,5 1,51,5b b=4=4 所以所以1,51,5 不用再劃分不用再劃分2,32,3a a=1,3=1,3 2,32,3b b=3

10、,2=3,2因為因為 22a a=1=1 33a a=3=3 所以所以2,32,3應劃分為應劃分為2323所以化簡后為所以化簡后為 G G（ 0,2,3,4,1,50,2,3,4,1,5）7.7.去除多余產生式后，構造去除多余產生式后，構造 NFANFA 如下如下7SABDQZabbabbbabab確定化，構造確定化，構造 DFADFA 矩陣矩陣a ab bS SA AQ QA AA AB,ZB,ZB,ZB,ZQ QD DQ QQ QD,ZD,ZD DA AB BD,ZD,ZA AD DB BQ QD D變換為變換為a ab b0 00 01 13 31 11 12 22 2* *3 34 4

11、3 33 35 54 41 16 65 5* *1 14 46 63 34 4化簡：化簡：G=(0,1,3,4,6),(2,5)G=(0,1,3,4,6),(2,5)0,1,3,4,6a=1,30,1,3,4,6a=1,30,1,3,4,6b=2,3,4,5,60,1,3,4,6b=2,3,4,5,6所以將所以將0,1,3,4,60,1,3,4,6劃分為劃分為 0,4,61,30,4,61,3G=(0,4,6),(1,3),(2,5)G=(0,4,6),(1,3),(2,5)0,4,6b=3,6,40,4,6b=3,6,4 所以所以 劃分為劃分為0,4,60,4,6G=(0),(4,6),(1

12、,3),(2,5)G=(0),(4,6),(1,3),(2,5)不能再劃分，分別用不能再劃分，分別用 0 0，4 4，1 1，2 2 代表各狀態，構造代表各狀態，構造 DFADFA 狀態轉換圖如下；狀態轉換圖如下；8014a,baabbab28 8代入得代入得 S S = = 0(1S|1)|0(1S|1)| 1(0S|0)1(0S|0) = = 01(S|)01(S|) | | 10(S|)10(S|) = = (01|10)(S|)(01|10)(S|) = = (01|10)S(01|10)S | | (01|10)(01|10) = = (01|10)(01|10)* *(01|10)

13、(01|10)構造構造 NFANFASABZ010110由由 NFANFA 可得正規式為可得正規式為(01|10)(01|10)* *(01|10)=(01|10)(01|10)=(01|10)+ +9.9.狀態轉換函數不是全函數狀態轉換函數不是全函數, ,增加死狀態增加死狀態 8,8, G=(1,2,3,4,5,8),(6,7)G=(1,2,3,4,5,8),(6,7)(1,2,3,4,5,8)(1,2,3,4,5,8)a a=(3,4,8)=(3,4,8) (3,4)(3,4)應分出應分出(1,2,3,4,5,8)(1,2,3,4,5,8)b b=(2,6,7,8)=(2,6,7,8) (

14、1,2,3,4,5,8)(1,2,3,4,5,8)c c=(3,8)=(3,8)(1,2,3,4,5,8)(1,2,3,4,5,8)d d=(3,8)=(3,8)所以應將所以應將(1,2,3,4,5,8)(1,2,3,4,5,8)分為分為(1,2,5,8),(1,2,5,8), (3,4)(3,4)G=(1,2,5,8),(3,4),(6,7)G=(1,2,5,8),(3,4),(6,7)(1,2,5,8)a=(3,4,8)(1,2,5,8)a=(3,4,8) 8 8 應分出應分出(1,2,5,8)b=(2,8)(1,2,5,8)b=(2,8) (1,2,5,8)c=(8)(1,2,5,8)c

15、=(8) (1,2,5,8)d=(8)(1,2,5,8)d=(8) G=(1,2,5),(8),(3,4),(6,7)G=(1,2,5),(8),(3,4),(6,7)(1,2,5)a=(3,4,8)(1,2,5)a=(3,4,8) 5 5 應分出應分出G=(1,2),G=(1,2), (3,4),5,(3,4),5, (6,7)(6,7) ,(8),(8) 去掉死狀態去掉死狀態 8,8,9最終結果為最終結果為 (1,2)(1,2) (3,4)(3,4) 5,(6,7)5,(6,7) 以以 1,3,5,61,3,5,6 代替代替, ,最簡最簡 DFADFA 為為13acbbda56b正規式正規

16、式:b:b* *a(da|c)a(da|c)* *bbbb* *第五章第五章1.1. S-aS-a | | |(|( T T ) )T T - T T , , S S | | S S(a,(a,a)(a,(a,a)S S = ( ( T T ) ) = ( ( T T , , S S ) ) = ( ( S S , , S S ) ) = ( ( a a , , S)S) = ( ( a,a, ( ( T T ) =(a=(a , , ( ( T T , , S S ) ) ) ) = (a(a , , ( ( S S , , S S ) = (a(a , , ( ( a a , , a a

17、) ) ) )S=(T)S=(T) = (T,S)(T,S) = (S,S)(S,S) = ( ( ( ( T T ) ) , , S S ) ) = ( ( ( ( T T , , S S ) ) , , S S ) ) = ( ( ( ( T T , , S S , , S S ) ) , , S S ) ) = ( ( ( ( S S , , S S , , S S ) ) , , S S ) ) = ( ( ( ( ( ( T T ) ) , , S S , , S S ) ) , , S S ) ) = ( ( ( ( ( ( T T , , S S ) ) , , S S , ,

18、S S ) ) , , S S ) ) =(=( ( ( ( ( S S , , S S ) ) , , S S , , S S ) ) , , S S ) ) = ( ( ( ( ( ( a a , , S S ) ) , , S S , , S S ) ) , , S S ) )= ( ( ( ( ( ( a a , , a a ) ) , , S S , , S S ) ) , , S S ) ) = ( ( ( ( ( ( a a , , a a ) ) , , , , S S ) ) , , S S ) ) = ( ( ( ( ( ( a a , , a a ) ) , , , ,

19、( ( T T ) ) ) ) , , S S ) )= ( ( ( ( ( ( a a , , a a ) ) , , , , ( ( S S ) ) ) ) , , S S ) ) = ( ( ( ( ( ( a a , , a a ) ) , , , , ( ( a a ) ) ) ) , , S S ) ) = ( ( ( ( ( ( a a , , a a ) ) , , , , ( ( a a ) ) ) ) , , a a ) )S-aS-a | | |(|( T T ) )T T - T T , , S ST T - S S消除直接左遞歸：消除直接左遞歸：S-aS-a | |

20、|(|( T T ) )T T - S S TTTT - , , S S TT | | SELECTSELECT ( ( S-a)S-a) = = aaSELECTSELECT ( ( S-)S-) = = SELECTSELECT ( ( S-(S-( T T ) ) ) ) = = ( ( SELECTSELECT ( ( T T - S S T)T) = = a a , , , , ( ( SELECTSELECT ( ( TT - , , S S TT ) ) = = , , SELECTSELECT ( ( TT -)-) = = FOLLOWFOLLOW ( ( TT ) ) =

21、= FOLLOWFOLLOW ( ( T T ) ) = = ） 10構造預測分析表構造預測分析表a a ( ( ) ), ,# #S S - a a- - ( ( T T ) )T T- S S TT- S S TT- S S TTTT- , , S S TT分析符號串分析符號串 （ a a , , a a ）# #分析棧分析棧 剩余輸入串剩余輸入串 所用產生式所用產生式 #S#S ( ( a a , , a)a) # # S S - ( ( T T ) )# # ) ) T T ( ( ( ( a a , , a)a) # # ( ( 匹配匹配 # # ) ) T T a a , , a

22、a ) ) # # T T - S S TT# # ) ) TT S S a a , , a a ) ) # # S S - a a# # ) ) TT a a a a , , a a ) ) # # a a 匹配匹配# # ) ) TT ，a)a) # #TT - , , S S TT# # ) ) TT S S , , , , a a ) ) # #, , 匹配匹配# # ) ) TT S S a a ) ) # #S-aS-a# # ) ) TT a aa a ) ) # #a a 匹配匹配# # ) ) TT) ) # #TT -# # ) ) ) # #) )匹配匹配# # #接受接

23、受2.2.E-TEE-TE E-+EE-+E E-E- T-FTT-FT T-TT-T T-T- F-PFF-PF F-*FF-*F F-F- P-(E)P-(E) P-aP-a P-bP-b P-P-非終結符名非終結符名是否是否FIRSTFIRST 集集FOLLOWFOLLOW 集集E E否否 （，（，a a，b b，#， ） EE是是+,+,#， ） T T否否 （，（，a a，b b， ，# #， ） TT是是, （，（，a a，b b， ，# #， ） F F否否 （，（，a a，b b， （，（，a a，b b， ，# #， ） FF是是*,*, （，（，a a，b b， ，# #，

24、 ） P P否否 （，（，a a，b b，*， （，（，a a，b b， ，# #， ） SELECTSELECT（E ETETE ）=FIRST(TE)=FIRST(T)=FIRST(TE)=FIRST(T)= （，（，a a，b b， ）SELECTSELECT（EE+E+E）=+=+SELECTSELECT（EE）=FOLLOW(E)=FOLLOW(E)= #，)SELECTSELECT（T TFTFT ）=FIRST=FIRST（F F）= = （，（，a a，b b，SELECTSELECT（TT TT）=FIRST=FIRST（T T）= = （，（，a a，b b， ）SELEC

25、T(TSELECT(T)=FOLLOW(T)=)=FOLLOW(T)= ，# #，)SELECT(FSELECT(F PF)=FIRST(F)=PF)=FIRST(F)= （，（，a a，b b，SELECT(FSELECT(F*F)=*F)=*11SELECT(FSELECT(F)=FOLLOW(F)=)=FOLLOW(F)= （，（，a a，b b， ，# #， ） 3.3. S-MHS-MH S-aS-a H-LsoH-Lso H-H- K-dMLK-dML K-K- L-eHfL-eHf M-KM-K M-bLMM-bLM FIRSTFIRST ( ( S S ) ) =FIRST(M

26、H)=FIRST(MH)= FIRSTFIRST ( ( M M ) ) FIRSTFIRST ( ( H H ) ) a=a= a,a, d d , , b b , , e e , FIRST(FIRST( H H ) ) = = FIRSTFIRST ( ( L L ) ) = e e , , FIRST(FIRST( K K ) ) = = d d , , FIRST(FIRST( M M ) ) = = FIRSTFIRST ( ( K K ) ) b b = = d d , , b b , FOLLOWFOLLOW ( ( S S ) ) = = # # , , o o FOLLOW

27、FOLLOW ( ( H H ) ) = = FOLLOWFOLLOW ( ( S S ) ) f f = = f f , , # # , , o o FOLLOWFOLLOW ( ( K K ) ) = = FOLLOWFOLLOW ( ( M M ) ) = = e e , , # # , , o o FOLLOWFOLLOW ( ( L L ) ) = FIRSTFIRST ( ( S S ) ) oo FOLLOWFOLLOW ( ( K K ) ) FIRSTFIRST ( ( M M ) ) FOLLOWFOLLOW ( ( M M ) ) = = a,a, d d , , b b

28、 , , e e , , # # , , o o FOLLOWFOLLOW ( ( M M ) ) = FIRSTFIRST ( ( H H ) ) FOLLOWFOLLOW ( ( S S ) ) FIRSTFIRST ( ( L L ) ) = = e e , , # # , , o o SELECTSELECT ( ( S-S- M M H)H) = = ( ( FIRSTFIRST ( ( M M H)H) ) ) FOLLOWFOLLOW ( ( S S ) ) = = ( ( FIRST(FIRST( M M ) ) FIRSTFIRST ( ( H H ) ) ) ) FOLLO

29、WFOLLOW ( ( S S ) ) = = d d , , b b , , e e , , # # , , o o SELECTSELECT ( ( S-S- a a ) ) = = a a SELECTSELECT ( ( H-LH-L S S o o ) ) = = FIRST(LFIRST(L S S o)o) = = e e SELECTSELECT ( ( H H - ) ) = = FOLLOWFOLLOW ( ( H H ) ) = = f f , , # # , , o o SELECTSELECT ( ( K-K- d d M M L L ) ) = = d d SELE

30、CTSELECT ( ( K-K- ) ) = = FOLLOWFOLLOW ( ( K K ) ) = = e e , , # # , , o o SELECTSELECT ( ( L-L- e e H H f f ) ) = = e e SELECTSELECT ( ( M-KM-K ) ) = = ( ( FIRST(FIRST( K K ) ) ) ) FOLLOWFOLLOW ( ( M M ) ) = = dd， e e , , # # , , o o SELECTSELECT ( ( M M - b b L L M M )=)= b b 構造構造 LL(LL( 1 1 ) ) 分

31、析表分析表a ab be ed df fo o# #S S- a a- M M H H- M M H H- M M H H- M M H H- M M H HH H-L-L S S o o-K K- d d M M L L-L L- e e H H f fM M- b b L L M M-K-K-K-K-K-K-K-K4 4 . . 文法含有左公因式，變為文法含有左公因式，變為 S-CS-C $ $ b,b, a a C-C- b b A A b b C-C- a a B B a a A A - b b A A A A b b A-A- a a AA a a A-A- $ $ , , a,a,

32、 b b 12A-A- C C a a , , b b B-aB-a B B B B a a B B - b b BB b b B-B- $ $ , , a a , , b b B-B- C C a,a, b b 5.5. - S S AA BB CC DD EE -F-F S-beginS-begin A A endend S-beginS-begin A A endend beginbegin A-A- B B A-A- B B AA a a , , ifif A-A- A A ; ; B B A-A- ; ; B B AA ; ; A-A- endend B-B- C CB-B- C C

33、 a a B-B- D D B-B- D D ifif C-C- a a C-C- a a a a D-D- E E D-D- E E DD ifif D-D- E E elseelse B B D-D- elseelse B B elseelse D-D- ; , , endend E-E- FCFCE-E- FCFC ifif F-F- ifif b b thenthen F-F- ifif b b thenthen ifif 非終結符是否為空非終結符是否為空S S否否 A A否否 AA是是 B B否否 C C否否 D D否否 DD是是 E E否否 F F否否 FIRST(S)FIRST(

34、S) = = beginbegin FIRST(A)FIRST(A) = = FIRST(B)FIRST(B) FIRST(A)FIRST(A) = = aa , , ifif , , ; ; , , FIRST(A)FIRST(A) = ; ; , , FIRST(B)FIRST(B) = = FIRST(C)FIRST(C) FIRST(D)FIRST(D) = a a , , ifif FIRST(C)FIRST(C) = = aaFIRST(D)FIRST(D) = = FIRSTFIRST（E E）= = ifif FIRSR(D)FIRSR(D) = = elseelse , ,

35、FIRST(E)FIRST(E) = = FIRST(F)FIRST(F) = = ifif FIRST(F)FIRST(F) = = ifif FOLLOW(S)FOLLOW(S) = = # FOLLOW(A)FOLLOW(A) = = endendFOLLOW(A)FOLLOW(A) = = endend FOLLOW(B)FOLLOW(B) = = ; , , endend FOLLOWFOLLOW (C)(C) = = ; , , endend , , elseelse FOLLOW(D)FOLLOW(D) = = ; , , endend FOLLOW(FOLLOW( DD ) )

36、 = = ; ; , , endend FOLLOW(E)FOLLOW(E) = = elseelse , , ; ; endend FOLLOW(F)FOLLOW(F) = = a a 13S S A A AA B B C C D D DD E E F F ifif thenthen elseelse beginbegin endend a a b b ; ; ififthenthenelseelsebeginbeginendenda ab b; ;# #S S-begin-begin A A endendA A- B B AA- B B AAAA- ; ; B B AAB B- D D-

37、C CC C- a aD D- E E DDDD- elseelse B B DD-E E-FC-FC F F-if-if b b thenthen6.6. 1.1.(1)(1) S S - A A | | B B(2)(2) A A - aA|aaA|a(3)B(3)B - bBbB |b|b提取提取 （2 2） ， （3 3）左公因子）左公因子(1)(1) S S - A A | | B B(2)(2) A A - aAaA(3)(3) A-A- A|A|(4)(4) B B - bBbB(5)(5) B-B- B B |2.2.(1)(1) S-ABS-AB(2)(2) A-Ba|A-B

38、a|(3)(3) B-Db|DB-Db|D(4)(4) D-D- d|d|提取（提取（3 3）左公因子）左公因子(1)(1) S-ABS-AB(2)(2) A-Ba|A-Ba|(3)(3) B-DBB-DB(4)(4) B-b|B-b|(5)(5) D-D- d|d|3.3.(1)(1) S-aAaBS-aAaB | | bAbBbAbB(2)(2) A-A- S|S| dbdb(3)(3) B-bB|aB-bB|a144 4(1)(1) S-i|(E)S-i|(E)(2)(2) E-E+S|E-S|SE-E+S|E-S|S提取（提取（2 2）左公因子）左公因子(1)(1) S-i|(E)S-

39、i|(E)(2)(2) E-SEE-SE(3)(3) E-+SE|-SEE-+SE|-SE |5 5(1)(1) S-SaAS-SaA | | bBbB(2)(2) A-aB|cA-aB|c(3)(3) B-Bb|dB-Bb|d消除（消除（1 1）(3)(3)直接左遞歸直接左遞歸(1)(1) S-bBSS-bBS(2)(2) S-aAS|S-aAS|(3)(3) A-aBA-aB | | c c(4)(4) B B - dBdB(5)(5) B-bB|B-bB|6.6.(1)(1) M-MaHM-MaH | | H H(2)(2) H-b(M)H-b(M) | | (M)(M) |b|b消除（

40、消除（1 1）直接左遞歸，提取（）直接左遞歸，提取（2 2）左公因子）左公因子(1)(1) M-M- HMHM(2)(2) M-M- aHMaHM |(3)(3) H-bHH-bH | | ( ( M M ) )(4)(4) H-(M)H-(M) |7.7. (1)(1) 1)1)A-baBA-baB 2)2)A-A-3)3)B-AbbB-Abb4)4)B-aB-a將將 1 1） 、2)2)式代入式代入 3 3）式）式1)1)A-baBA-baB2)2)A-A-3)3)B-baBbbB-baBbb4)4)B-bbB-bb5)5)B-aB-a提取提取 3 3） 、4 4）式左公因子）式左公因子1

41、)1)A-baBA-baB2)2)A-A-3)3)B-bBB-bB4)4)B-aBbbB-aBbb | | b b5)5)B-aB-a(3)(3)151)1)S-AaS-Aa2)2)S-bS-b3)3)A-SBA-SB4)4)B-abB-ab將將 3 3）式代入）式代入 1 1）式）式1)1)S-SBaS-SBa2)2)S-bS-b3)3)A-SBA-SB4)4)B-abB-ab消除消除 1 1）式直接左遞歸）式直接左遞歸1)1)S-bSS-bS2)2)S-BaSS-BaS |3)3)S-bS-b4)4)A-SBA-SB5)5)B-abB-ab刪除多余產生式刪除多余產生式 4 4）1)1)S-

42、bSS-bS2)2)S-BaSS-BaS |3)3)S-bS-b4)4)B-abB-ab（5 5）1)1)S-AbS-Ab2)2)S-BaS-Ba3)3)A-aAA-aA4)4)A-aA-a5)5)B-aB-a提取提取 3 3） 4 4）左公因子）左公因子1)1)S-AbS-Ab2)2)S-BaS-Ba3)3)A-aAA-aA4)4)A-A- A A |5)5)B-aB-a將將 3 3）代入）代入 1 1） 5 5）代入）代入 2 21)1)S-aAbS-aAb2)2)S-aaS-aa3)3)A-aAA-aA4)4)A-A- A A |5)5)B-aB-a提取提取 1 1） 2 2） 左公因子

43、左公因子1)1)S-S- aSaS2)2)S-AbS-Ab | | a a3)3)A-aAA-aA4)4)A-A- A A |5)5)B-aB-a刪除多余產生式刪除多余產生式 5 5）161)1)S-S- aSaS2)2)S-AbS-Ab | | a a3)3)A-aAA-aA4)4)A-A- A A |A A AA SS S S將將 3 3）代入）代入 4 4）1)1)S-S- aSaS2)2)S-AbS-Ab | | a a3)3)A-aAA-aA 4)4)A-A- aAaA |將將 4 4）代入）代入 2 2）1)1)S-S- aSaS2)2)S-aAbS-aAb 3)3)S-aS-a

44、4)4)S-bS-b5)5)A-aAA-aA 6)6)A-A- aAaA |對對 2 2）3)3)提取左公因子提取左公因子1)1)S-aSS-aS2)2)S-aSS-aS 3)3)SS -Ab|-Ab|4)4)S-bS-b5)5)A-aAA-aA 6)6)A-A- aAaA |刪除多余產生式刪除多余產生式 5 5）1)1)S-aSS-aS2)2)S-aSS-aS 3)3)SS -Ab|-Ab|4)4)S-bS-b5)5)A-A- aAaA |第六章第六章1 1S S a a | | | | ( ( T T ) )T T T T , , S S | | S S解：解：(1)(1) 增加輔助產生式

45、增加輔助產生式 SSS S求求 FIRSTVTFIRSTVT 集集FIRSTVTFIRSTVT（SS ） #FIRSTVTFIRSTVT（S S） aa ( ( a a ( ( FIRSTVTFIRSTVT (T)(T) , FIRSTVT(FIRSTVT( S S ) ) = = , , a a ( ( 求求 LASTVTLASTVT 集集LASTVTLASTVT（SS ） # # LASTVTLASTVT（S S） a a )LASTVTLASTVT (T)(T) , , a a )17(2)(2)算符優先關系表算符優先關系表a a( () ), ,# #a a( (=, ,# #=因為任

46、意兩終結符之間至多只有一種優先關系成立，所以是算符優先文法因為任意兩終結符之間至多只有一種優先關系成立，所以是算符優先文法 (3)(3) a a ( () ), ,# #F F 1 1 1 1 1 1 1 1 1 1 1 1g g 1 1 1 1 1 1 1 1 1 1 1 1f f2 22 2 1 13 32 2 1 1g g2 22 2 2 21 1 2 2 1 1f f3 33 3 1 13 33 3 1 1g g4 44 4 4 41 1 2 2 1 1f f3 33 3 1 13 33 3 1 1g g4 44 4 4 41 1 2 2 1 1(4)(4) 棧棧 優先關系優先關系 當

47、前符號當前符號 剩余輸入串剩余輸入串 移進或規約移進或規約 ( ( a,a)#a,a)# 移進移進( ( , ,a)#a)# 規約規約(T(T , , a)#a)# 移進移進(T(T， ) ) # #規約規約(T,T(T,T) )# # 規約規約(T(T = ) )# # 移進移進(T)(T) 規約規約T T=接受接受4.4.擴展后的文法擴展后的文法S#S#S#S# SS;GSS;G SGSG GG(T)GG(T) GHGH HaHa H(S)H(S)TT+STT+S TSTS（1 1）FIRSTVT(S)=;FIRSTVT(G)FIRSTVT(S)=;FIRSTVT(G) = = ; , ,

48、 a a , , ( ( FIRSTVT(G)=FIRSTVT(G)= ( ( FIRSTVT(H)FIRSTVT(H) = = aa , , ( ( FIRSTCT(H)=aFIRSTCT(H)=a , , ( ( 18FIRSTVT(T)FIRSTVT(T) = = + FIRSTVT(S)FIRSTVT(S) = = + , , ; ; , , a a , , ( ( LASTVT(S)LASTVT(S) = = ; LASTVT(G)LASTVT(G) = = ; ; , , a a , , )LASTVT(G)LASTVT(G) = = ) LASTVT(H)LASTVT(H) =

49、= a a , , )LASTVT(H)LASTVT(H) = = a,a, )LASTVT(T)LASTVT(T) = = + LASTVT(S)LASTVT(S) = = + , , ; ; , , a a , , ) ) 構造算符優先關系表構造算符優先關系表; ;( () )a a+ +# #；( (a a+ +# #因為任意兩終結符之間至多只有一種優先關系成立，所以是算符優先文法因為任意兩終結符之間至多只有一種優先關系成立，所以是算符優先文法（2 2） 句型句型 a(T+S);H;(S)a(T+S);H;(S)的的短語有：短語有：a(T+S);H;(S)a(T+S);H;(S) a(T

50、+S);Ha(T+S);H a(T+S)a(T+S) a a T+ST+S (S)(S) H H 直接短語有直接短語有: : a a T+ST+S H H (S)(S)句柄：句柄： a a素短語：素短語：a a T+ST+S (S)(S) 最左素短語：最左素短語：a a(3)(3)分析分析 a a；（；（a aa a） 棧棧優先關系優先關系當前符號當前符號剩余輸入串剩余輸入串移進或規約移進或規約a aT TT T；T T；（；（T T；（；（a aT T；（；（T TT T；（；（T TT T；（；（T Ta aT T；（；（T TT TT T；（；（T TT T；（；（T T）T T；T T

51、T Ta a；（a aa a）；（；（a aa a）（a aa a）（a aa a）a aa a）a a）a a）a a）移進移進規約規約移進移進移進移進移進移進規約規約移進移進移進移進規約規約規約規約移進移進規約規約規約規約接受接受分析分析 a a；（；（a aa a）棧棧優先關系優先關系當前符號當前符號剩余輸入串剩余輸入串移進或規約移進或規約19（a a（T T（T T（T Ta a（T TT T（T T（T T）T T( (aa a）a aa a）a a）a a） a a）移進移進移進移進規約規約移進移進移進移進規約規約規約規約移進移進規約規約接受接受（4 4）不能用最右推導推導出上面的

52、兩個句子。不能用最右推導推導出上面的兩個句子。第七章第七章1 1、已知文法：、已知文法： A A aAd|aAb|aAd|aAb|判斷該文法是否是判斷該文法是否是 SLRSLR（1 1）文法，若是構造相應分析表，并對輸入串）文法，若是構造相應分析表，并對輸入串 ab#ab#給出分析過程。給出分析過程。解：解：(0) A A(1) A aAd(2) A aAb(3) A 構造該文法的活前綴 DFA：I0： A A A aAdA aAbA 由上圖可知該文法是 SLR（1）文法。構造 SLR（1）的分析表：ACTIONACTIONGOTOGOTO狀態狀態a ad db b# #A A0 0S2S2R

53、3R3R3R3R3R31 11 1accacc2 2S2S2R3R3R3R3R3R33 33 3S4S4S5S54 4R1R1R1R1R1R15 5R2R2R2R2R2R2輸入串 ab#的分析過程：步驟步驟狀態棧狀態棧符號棧符號棧輸入串輸入串ACTIONACTIONGOTOGOTO1 10#ab#S22 202#ab#R333 3023#aAb#S5a a204 40235#aAb#R215 501#A#acc3 3、考慮文法：、考慮文法：S S AS|bAS|b ASA|aASA|a(1)(1)列出這個文法的所有列出這個文法的所有 LRLR（0 0）項目）項目(2)(2)按（按（1 1）列出

54、的項目構造識別這個文法活前綴的）列出的項目構造識別這個文法活前綴的 NFANFA，把這個，把這個 NFANFA 確定化為確定化為 DFADFA，說明這個，說明這個 DFADFA的所有狀態全體構成這個文法的的所有狀態全體構成這個文法的 LRLR（0 0）規范族。）規范族。(3)(3)這個文法是這個文法是 SLRSLR 的嗎若是，構造出它的的嗎若是，構造出它的 SLRSLR 分析表。分析表。(4)(4)這個文法是這個文法是 LALRLALR 或或 LRLR（1 1）的嗎）的嗎解：解：（0）SS (1)SAS (2)Sb (3)ASA (4)Aa (1)列出所有 LR（0）項目： SS Sb Aa

55、S S Sb Aa S AS ASA S AS ASA S AS ASA (3)構造該文法的活前綴 NFA：I0：SSS ASS bA SAA aI1：S SA SAA SAA aS ASS bS SI3：A SAS ASS ASS bA SAA aI5：S ASA SAA SAA aS ASS bI2：S ASS ASS bA SAA aI4：A SAA SAA aS ASS bI6：S bI7：A aA AA AS SA AA AS SA AS SA AS SS Sb ba ab bb bb bb ba aa aa aa aa ab b由上可知：I1 I3 I5 中存在著移進和歸約沖突在

56、I1中含項目：S S 歸約項 Follow(S)=#A a 移進項 Follow(S)a=21S b 移進項 Follow(S)b=在 I3中含項目：A SA 歸約項 Follow(A)=a,bS b 移進項 Follow(A) bA a 移進項 Follow(A) a在 I5中含項目：S AS 歸約項 Follow(S)=#,a,bA a 移進項 Follow(S) aS b 移進項 Follow(S) b由此可知，I3、I5 的移進與歸約沖突不能解決，所以這個文法不是 SLR（1）文法。（4）做 LR（1）項目集規范族 由上可知該文法不是 LR（1）文法，也不是 LALR（1）文法。5 5

57、、一個類、一個類 ALGOLALGOL 的文法如下：的文法如下： StatementBlock; Blockheadbeginbegin d dBlock;dhead;d SS endendI1： S S ,# A SA ,a/bA SA ,a/bA a ,a/bS AS ,a/bS b ,a/bI0： SS ，#S AS ，a/b/#S b ,a/b/#A SA ,a/bA a ,a/bI2：S AS ,a/b/#S AS ,a/b/#S b ,a/b/#A SA ,a/bA a ,a/bI3：S b ,a/b/#I4：A a ,a/b/#I5：(I1-A-)A SA ,a/bS AS ,a

58、/bS AS ,a/bS b ,a/bA SA ,a/bA a ,a/bI6：(I1-S-)A SA ,a/bA SA ,a/bA a ,a/bS AS ,a/bS b ,a/bI7：(I2-S-)S AS ,a/b/#A SA ,a/b/#A SA ,a/bA a ,a/bS AS ,a/bS b ,a/b22 S;S; CompoundStatementbeginbegin 試構造其試構造其 LRLR（0 0）分析表。）分析表。解：解：設=A =B =C =D =EAB AC BD；E Dbegin d DD;d Es end Es;E Cbegin E(0)A A (1) AB (2)A

59、C (3)BD;E (4) Dbegin d (5) DD;d (6) Es end (7) Es;E (8) Cbegin E構造該文法的活前綴 DFA：I0： AA ABACBD；ECbegin EDbegin dDD;dI4： BD；EDD；dI5：Cbegin EDbegin d ES endES;EI13：ES；EESendES；EI14：ES；EI11：DD； dI10：BD； EI1：A AI2：ABI3：ACI8：Cbegin EI9：Dbegin dA AD DbeginbeginB BC CE Ed dE E；d dS SS S；E EI112：ES endendend構造

60、 LR（0）分析表：ACTIONACTIONGOTOGOTO狀狀態態beginbegin；d dS Sendend# #A AB BC CD DE E0 0S5S51 12 23 34 41 1accacc2 2R1R1R1R1R1R1R1R1R1R1R1R1I6：BD；EDD；d ES endES;ES SI7：ESendES；E233 3R2R2R2R2R2R2R2R2R2R2R2R24 4S6S65 5S9S9S7S78 86 6S11S11S7S710107 7S13S13S12S128 8R8R8R8R8R8R8R8R8R8R8R8R89 9R4R4R4R4R4R4R4R4R4R4R