第7章作業(yè)參考答案

1、第章 LR 分析1已知文法AaAd|aAb|判斷該文法是否是SLR(1)文法，若是構造相應分析表，并對輸入串a(chǎn)b#給出分析過程。答案：文法：AaAd|aAb|拓廣文法為G，增加產(chǎn)生式SA若產(chǎn)生式排序為：0 S A1 A aAd2 A aAb3 A 由產(chǎn)生式知：First (S ) = ,aFirst (A ) = ,aFollow(A ) = d,b,#G的LR(0)項目集規(guī)范族及識別活前綴的DFA 如下圖所示：在I0 中：A .aAd 和A .aAb 為移進項目，A .為歸約項目，存在移進-歸約沖突，因此所給文法不是LR(0)文法。在I0、I2 中：Follow(A) a= d，b，# a=

2、所以在I0、I2 中的移進-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。構造的SLR(1)分析表如下：題目1 的SLR(1)分析表對輸入串a(chǎn)b#的分析過程10.判斷下列各題所示文法是否為類方法，若是請說明是LR(0),SLR(1),LALR(1)或LR(1)的哪一種，并構造相應的分析表，若不是請說明理由（）S-aAd|eBd|aBr|eAr A-a B-a答案：）列出擴展文法的產(chǎn)生式列表：(0)S-S(1)S-aAd(2)S-eBd(3)S-aBr(4)S-eAr (5)A-a(6)B-a2） 的LR(0)項目集族及識別活前綴的DFA 如下圖所示：BI0:S-.SS-.aA

3、dS-.eBdS-.aBrS-.eArI1:S-S.I2:S-a.AdS-a.BrA-.aB-.aI3:S-e.BdS-e.ArB-.aA-.aSaeI4:S-aA.dI5:S-aB.rI6:A-a.B-a.ABaI7:S-eB.dI8:S-eA.rAaI9:S-aAd.dI10:S-aBrd.rI11:S-eBd.dI12:S-eAr.r從上圖中看出項目集I6中存在歸約-歸約沖突，所以該文法不是LR(0)文法。下面判斷是否為SLR(1)文法：Follow(S)=#Follow(A)=d,rFollow(B)=d,r對于I6，F(xiàn)ollow(A) Follow(B)= d,r不為，所以項目集I6

4、中的歸約-歸約沖突不能消除，該文法不是SLR(1)文法。下面判斷是否為LR(1)文法，在上面的項目集規(guī)范族中加入搜索符：BI0:S-.S,#S-.aAd,#S-.eBd,#S-.aBr,#S-.eAr,#I1:S-S.,#I2:S-a.Ad,#S-a.Br,#A-.a,dB-.a,rI3:S-e.Bd,#S-e.Ar,#B-.a,dA-.a,rSaeI4:S-aA.d,#I5:S-aB.r,#I6:A-a.,dB-a.,rABaI7:S-eB.d,#I8:S-eA.r,#AaI9:S-aAd.,#dI10:S-aBr.,#rI11:S-eBd.,#dI12:S-eAr. ,#rI13:B-a.

5、,dA-a.,r從上圖可以看出原來存的的歸約-歸約沖突已經(jīng)消除，所以該文法為LR(1)文法。但若合并同心項目集I6和I13，則歸約-歸約沖突又會重現(xiàn)，因此該文法不是LALR(1)文法。3)LR(1)分析表ActionGotoState a e d r # S A B0 S2 S3 11 acc2 S6 4 53 S13 8 74 S95 S106 R5 R67 S118 S129 R110 R311 R212 R413 R6 R511.設文法GS為：S-AS|A-aA|b（1） 證明GS是LR1文法; 擴展文法G為：（0） S-S（1） S-AS（2） S-（3） A-aA（4） A-b的LR

6、(1)項目集族及識別活前綴的DFA 如下圖所示：AbabaI0:S-.S,#S-.AS,#S-.,#A-.aA,a/b/#A-.b, a/b/#I1:S-S.,#SI2:S-A.S,#S-.AS,#S-.,#A-.aA,a/b/#A-.b, a/b/#AI3:A-a.A,a/b/#A-.aA,a/b/#A-.b, a/b/#I4:A-b., a/b/#abI5:S-AS.,#SAI6:A-aA.,a/b/#從上圖中可以看出，每個項目集中均無移進-歸約沖突和歸約-歸約沖突，所以該文法為LR(1)文法。（2） 構造它的LR(1)分析表;ActionGotoState a b # S A 0 S3

7、S4 R2 1 21 acc2 S3 S4 R2 5 23 S3 S4 64 R4 R4 R45 R16 R3 R3 R3（3） 給出輸入符號串a(chǎn)bab#的分析過程。序號狀態(tài)棧符號棧輸入緩沖區(qū)動作10#abab#S3,移進203#abab#S4,移進3034#abab#R4,歸約 A-b4036#aAab#R3,歸約 A-aA502#Aab#S3,移進6023#Aab#S4,移進70234#Aab#R4,歸約 A-b80236#AaA#R3,歸約 A-aA9022#AA#R2,歸約 S-100225#AAS#R1,歸約 S-AS11025#AS#R1,歸約 S-AS1201#S#acc 成功1

8、5.已知文法為：S-a|(T)T-T,S|S(1) 構造它的LR(0)，LALR(1)，LR(1)分析表; 擴展文法G為：（0） S-S（1） S-a（2） S-（3） S-(T)（4） T-T,S（5） T-S1)LR(0)項目集族及識別活前綴的DFA 如下圖所示：(a)(Sa,STI0:S-.SS-.aS-.S-.(T)I1:S-S.SI2:S-a.I4:S-(.T)T-.T,ST-.SS-.aS-.S-.(T)(I7:S-(T).I3:S-.I6:T-S.,I8:T-T, .SS-.aS-.S-.(T)I9:T-T, S.aI5:S-(T.)T-T.,SLR(0)分析表:ActionGo

9、toState a （ ） ， # S T 0 S2 S3 S4 11 acc2 R1 R1 R1 R1 R1 R13 R2 R2 R2 R2 R2 R24 S2 S3 S4 6 55 S7 S86 R5 R5 R5 R5 R5 R57 R3 R3 R3 R3 R3 R38 S2 S3 S4 99 R4 R4 R4 R4 R4 R42) LR(1)項目集族及識別活前綴的DFA 如下圖所示：),a(S(aSa,STI0:S-.S,#S-.a,#S-.,#S-.(T),#I1:S-S.,#SI2:S-a.,#I4:S-(.T),#T-.T,S,)/,T-.S,)/,S-.a,)/,S-., )/,

10、S-.(T), )/,(I10:S-(T) .,#)I3:S-.,#I6:T-S.,)/,I11:T-T, .S, )/,S-.a, )/,S-., )/,S-.(T), )/,I13:T-T, S., )/,aI7:S-a., )/,I8:S-.,)/,I9:S-(.T),)/,T-.T,S,)/,T-.S, )/,S-.a, )/,S-., )/,S-.(T), )/,I5:S-(T.),#T-T.,S,)/,I12:S-(T.), )/,T-T.,S,)/,TI14:S-(T) .,)/,圖中“,”為文法符號。說明：對于I4中的項目T-.T,S和T-.S，先由項目S-(.T),#推出擴展

11、項目的搜索符為“)”，再由T-.T,S,) 擴展出新的搜索符“,”，合并后的搜索符為“)/,”。LR(1)分析表:ActionGotoState a （ ） ， # S T 0 S2 S3 S4 11 acc2 R13 R24 S7 S8 S9 6 55 S10 S116 R5 R57 R1 R18 R2 R29 S7 S8 S9 6 1210 R3 11 S7 S8 S9 1312 S14 S1113 R4 R414 R3 R3LALR(1)分析表需將上面DFA中的同心項目（同底色）的項目集合并后考慮，將狀態(tài)數(shù)大的合并入狀態(tài)數(shù)小的項目集中，在此不再另畫圖。 LALR(1)分析表:Action

12、GotoState a （ ） ， # S T 0 S2 S3 S4 11 acc2 R1 R1 R13 R2 R2 R24 S2 S3 S4 6 55 S10 S116 R5 R510 R3 R3 R3 11 S2 S3 S4 1313 R4 R4(2) 給出對輸入符號串(a#和(a,a#的分析過程;1) 對輸入符號串(a#的分析過程用LR(0)分析表序號狀態(tài)棧符號棧輸入緩沖區(qū)動作10#(a#S4,移進204#(a#S2,移進3042#(a#R1,歸約 S-a4046#(S#R5,歸約 T-S5045#(T#出錯用LR(1)分析表序號狀態(tài)棧符號棧輸入緩沖區(qū)動作10#(a#S4,移進204#(

13、a#S7,移進3047#(a#錯誤用LALR(1)分析表序號狀態(tài)棧符號棧輸入緩沖區(qū)動作10#(a#S4,移進204#(a#S2,移進3042#(a#R1,歸約 S-a4046#(S#錯誤2) 對輸入符號串(a,a#的分析過程用LR(0)分析表序號狀態(tài)棧符號棧輸入緩沖區(qū)動作10#(a,a#S4,移進204#(a,a#S2,移進3042#(a,a#R1,歸約 S-a4046#(S,a#R5,歸約 T-S5045#(T,a#S8,移進60458#(T,a#S2,移進704582#(T,a#R1,歸約 S-a804589#(T,S#R4,歸約 T-T,S9045#(T#出錯用LR(1)分析表序號狀態(tài)棧

14、符號棧輸入緩沖區(qū)動作10#(a,a#S4,移進204#(a,a#S7,移進3047#(a,a#R1,歸約 S-a4046#(S,a#R5,歸約 T-S5045#(T,a#S11,移進6045(11)#(T,a#S7,移進7045(11)7#(T,a#出錯用LALR(1)分析表序號狀態(tài)棧符號棧輸入緩沖區(qū)動作10#(a,a#S4,移進204#(a,a#S2,移進3042#(a,a#R1,歸約 S-a4046#(S,a#R5,歸約 T-S5045#(T,a#S11,移進6045(11)#(T,a#S2,移進7045(11)2#(T,a#R1,歸約 S-a8045(11)(13)#(T,S#出錯(3)

15、 說明（1）中三種分析表發(fā)現(xiàn)錯誤的時刻和輸入串的出錯位置有何區(qū)別。見（2），由此二例說明，對于錯誤分析，LR(1)的效率最高，LALR(1)次之，LR(0)最差。補充題：GS 文法如下，求其LR分析表 1. SAaDC 2. CCba 3. Cba 4. DA 5. DBa 6. Ab 7. Bb答：擴展文法G為： 0. SS1. SAaDC 2. CCba 3. Cba 4. DA 5. DBa 6. Ab 7. Bb答:1)首先判斷是否為LR(0)方法：aabCADSaBbbAaI0:S-.SS-.AaDCA.b I1:S-S.I2:S-A.aDCI3:Ab. bI4:S-Aa.DCD.A

16、D.BaA.bB.bI7:DB.aI5:S-AaD.CC.CbaC.baI6:DA.I8:Ab.Bb.I9:S-AaDC.CC.baI10:Cb.aI11:DBa.I12:CCb.aI13:CCba.I14:Cba.由上圖中可以看到I8中存在歸約-歸約沖突，I9中存在移進-歸約沖突，所以該文法不是LR(0)文法2)再判斷是否為SLR(1)文法：Follow(S)=#Follow(A)=a,bFollow(B)=aFollow(C)=b,#Follow(D)=b2對于I8，F(xiàn)ollow(A) Follow(B)=a,不為空，因此該文法不是SLR(1)文法。3)判斷是否為LR(1)文法：aI14:Cba.,#/bI10:Cb.a,#/bI5:S-AaD.C,#C.Cba,#/bC.ba,#/bbbCI4:S-Aa.DC,#D.A,bD.Ba,bA.b,bB.b,aI1:S-S.,#I0:S-.S,#S-.AaDC,#A.b,aSI9:S-AaDC.,#CC.ba,#/baI2:S-A.aDC,#ADAI6:DA.,bbI3:Ab.,abBI12:CCb.a,#/bI7:DB.a,bI8:A