




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、編譯原理作業(yè)參考答案 - 17 -第七章 LR分析法第1題 已知文法AaAd|aAb| 判斷該文法是否是SLR(1)文法,若是構(gòu)造相應(yīng)分析表,并對輸入串a(chǎn)b#給出分析過程。文法: AaAd|aAb| 拓廣文法為G,增加產(chǎn)生式SA若產(chǎn)生式排序為:0 S' A 1 A aAd2 A aAb3 A 由產(chǎn)生式知: First (S' ) = ,aFirst (A ) = ,aFollow(S' ) = # Follow(A ) = d,b,#G的LR(0)項目集族及識別活前綴的DFA如下圖所示: 在I0中:A .aAd和A .aAb為移進(jìn)項目,A .為歸約項目,存在移進(jìn)-歸約沖
2、突,因此所給文法不是LR(0)文法。在I0、I2中:Follow(A) a= d,b,# a=所以在I0、I2中的移進(jìn)-歸約沖突可以由Follow集解決,所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下: 題目1的SLR(1)分析表 狀態(tài)(State)ActionGoto ad b #A012345S2r3r3r3 accS2r3r3r3S4S5r1r1r1 r2r2r21.3題目1對輸入串a(chǎn)b#的分析過程狀態(tài)棧(state stack) 文法符號棧 剩余輸入串(input left)動作(action)Goto00 20 2 30 2 350 1#a#aA#aAb#Aab#
3、.b#.b#.#.#.S2r3(A )S5r2(A aAb)acc 3 1分析成功,說明輸入串a(chǎn)b是題目1文法的句子第2題若有定義二進(jìn)制數(shù)的文法如下:SL.L|L LLB|BB0|1 (1) 試為該文法構(gòu)造LR分析表,并說明屬哪類LR分析表。(2) 給出輸入串101.110的分析過程。解:文法: SL.L|L LLB|BB0|1 拓廣文法為G,增加產(chǎn)生式SS若產(chǎn)生式排序為:0 S' S 1 S L.L 2 S L 3 L LB 4 L B5 B 06 B 1 由產(chǎn)生式知: First (S' ) = 0,1First (S ) = 0,1 First (L ) = 0,1Fir
4、st (B ) = 0,1Follow(S' ) = # Follow(S ) = #Follow(L ) = .,0,1,#Follow(B ) = .,0,1,#G的LR(0)項目集族及識別活前綴的DFA如下圖所示: 在I2中:B .0和 B .1為移進(jìn)項目,S L.為歸約項目,存在移進(jìn)-歸約沖突,因此所給文法不是LR(0)文法。在I2、I8中:Follow(s) 0,1= # 0,1=所以在I2 、I8中的移進(jìn)-歸約沖突可以由Follow集解決,所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下:題目2的SLR(1)分析表 狀態(tài)(State)ActionGoto
5、· 01 #SLB012345678S4S5 accS6S4S5r2r4r4r4r4r5r5r5r5r6r6r6r6S4S5r3r3r3r3S4S5r1123.7.83. 7題目2對輸入串101.110#的分析過程狀態(tài)棧(state stack) 文法符號棧剩余輸入串(input left)動作(action)00 50 30 20 2 40 2 70 2 0 2 50 2 70 2 0 2 60 2 6 5 0 2 6 3 0 2 6 8 0 2 6 8 50 2 6 8 70 2 6 80 2 6 8 40 2 6 8 70 1#1#B#L#L0#LB#L#L1#LB#L#L.#
6、L.1#L.B#L.L#L.L1#L.LB#L.L#L.L0#L.LB#S101.110#.01.110#.01.110#.01.110#.1.110#.1.110#.1.110#.110#.110#.110#.110#.10#.10#.10#.0#.0#.0#.#.#.#.ShiftReduce by :B 1Reduce by :S LBShiftReduce by :B 0Reduce by :S LBShiftReduce by :B 1Reduce by :S LBShiftShiftReduce by :B 1Reduce by :S BShiftReduce by :B 1Red
7、uce by :S LBShiftReduce by :B 0Reduce by :S L.L分析成功,說明輸入串101.110是題目2文法的句子。3考慮文法:SàAS|b AàSA|a(1) 列出該文法所有的LR(0)項目。(2) 按(1)列出的項目構(gòu)造識別這個文法活前綴的NFA,把這個NFA確定化為DFA,說明這個DFA的所有狀態(tài)全體構(gòu)成這個文法的LR(0)規(guī)范族。(3) 此文法是SLR(1)的嗎?,若是,構(gòu)造他的SLR分析表(4) 這個文法是LALR或LR(1)的嗎?解:(1) 構(gòu)造增廣文法,SàS文法的LR(0)項目有:1. Sà.S2. S
8、224;S.3. Sà.AS4. SàA.S5. SàAS.6. Sà.b7. Sàb.8. Aà.SA9. AàS.A10. AàSA.11. Aà.a12. Aàa.(2)所產(chǎn)生的NFA略。由規(guī)則構(gòu)造所需的DFA:I5:AàS.AAà.SAAàa.Sà.ASSàb.I1:SàS.AàS.AAà.SAAà.aSà.ASSà.b S S A b aI7:AàSA.Sà
9、A.SSà.ASSà.bAà.SAAà.a a AI0:Sà.SSà.ASSà.bAà.SAAà.aI2:Aàa. aa bI3:Sàb. b S bAI6:SàAS.AàS.AAà.SAAà.aSà.ASSà.bI4:SàA.SSà.ASSà.bAà.SAAà.a abA A S S則LR(0)項目集規(guī)范族為:CI0,I1,I2,I3,I4,I5,I6,I7(3)可以看到I1
10、,I6,I7存在著移進(jìn)歸約的沖突。沖突是不能用SLR(1)的方法來解決。比如I6:對于狀態(tài)SàAS. 和Sà.bFollow(S)=#,a,b與b相交不為空。所以以上文法不是SLR(1)文法。(4)為驗證該文法是否為LALR或LR(1)的,構(gòu)造LR(1)項目集。對于I5,產(chǎn)生了移進(jìn)歸約矛盾,所以這個文法不是LR(1)文法。于是也不是LALR文法。第6題文法:SUTa|Tb TS|Sc|dUUS|e 拓廣文法為G',增加產(chǎn)生式S'S若產(chǎn)生式排序為:0 S' S1 S UTa 2 S Tb 3 T S 4 T Sc5 T d 6 U US 7 U e 由
11、產(chǎn)生式知: First (S' ) = d,eFirst (S ) = d,eFirst (U ) = e First (T ) = d,eFollow(S' ) = # Follow(S ) = a,b,c,d,e,#Follow(U ) = d,e Follow(T ) = a,b G的LR(0)項目集族及識別活前綴的DFA如下圖所示: 在I1中:S' S.為接受項目,T S. 為歸約項目,T S.c為移進(jìn)項目,存在接受-歸約和移進(jìn)-歸約沖突,因此所給文法不是LR(0)文法。 在I1中: Follow(S') Follow(T)= # a ,b=Follow
12、(T) c= a ,b c=在I8中:Follow(U) Follow(T) c=d,e a ,b c=所以在I1中的接受-歸約和移進(jìn)-歸約沖突與I8中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下:題目3的SLR(1)分析表 狀態(tài)(State)ActionGoto a b c d e#SUT012345678910 S5S4r3r3S6AccS5S4S9.r7r7r5r5. r4r4.S10S9.r3r3.S6r6r6. r2r2.r2r2r2r2r1r1.r1r1r1r1123.827 第8題文法: SàA
13、#ABaBb|DbDa BD 證明該文法是LR(1)但不是SLR(1)。解:若產(chǎn)生式排序為:0 S'A#1 A BaBb 2 A DbDa 3 B 4 D 由產(chǎn)生式知: First (S' ) = a,b First (A ) = a,bFirst (B ) = First (D ) = Follow(S' ) = #Follow(A ) = # Follow(B ) = a,bFollow(D ) = a,bG的LR(1)項目集族及識別活前綴的DFA如下圖所示: 在I0中:B .,a和T .,b為歸約項目,但它們的搜索符不同,若當(dāng)前輸入符為a時用產(chǎn)生式B 歸約,為b時
14、用產(chǎn)生式D 歸約,所以該文法是LR(1)文法。若不看搜索符,在I0中項目B .和T .為歸約-歸約沖突,而Follow(B ) Follow(D ) = a,b a,b,沖突不能用Follow集解決,所以該文法不是SLR(1)文法。構(gòu)造的LR(1)分析表如下:題目4的LR(1)分析表 StateActionGoto a.b.#ABD0123456789r3r4. AccS4.S5r3r4.S8S9.r1r2123.67 10判斷下列各題所示文法是否為LR類文法,若是請說明是LR(0)、SLR(1)、LALR(1)或LR(1)的哪一種,并構(gòu)造相應(yīng)分析表()SàAB A
15、4;aBa| BàbAb|(3)SàaAd|eBd|aBr|eAr Aàa Bàa(5) AàaB| BàAb|a (6) Sà(SR|a Rà.SR|)(1)解:對于該文法構(gòu)造LR(0)項目規(guī)范族:I0:Sà.SI1:SàS.I3:Aàa.BaI5:Bàb.AbI6:AàaB.a Sà.ABI2:SàA.BBà.bAbAà.aBaI7:AàaBa.Aà.aBaBà.bAbBà.A
16、24;.I8:BàbA.bA->.Bà.I4:SàAB.I9:BàbAb.可見存在著移進(jìn)歸約沖突,這個文法不是LR(0)文法??紤]用SLR(1)來解決問題:構(gòu)造SLR(1)分析表,發(fā)現(xiàn)該文法是SLR(1)文法。狀態(tài)ACTIONGOTOab#SAB0s3r3r3121acc2r5S5r543r5S5r564r15S3r3r386S77r2r28S99r4r4(3)解:先構(gòu)造該文法的LR(0)項目集規(guī)范族:I0:Sà.SI1:SàS.I3:Sàe.BdI5:SàaB.rI9:SàaAd.Sà.
17、AdI2:Sàa.AdBà.aI6:Aàa.I10:SàaBr.Sà.eBdSàa.BrSàe.ArBàa.I11:SàeBd.Sà.aBrAà.aAà.aI7:SàeB.dI12:SàeAr.Sà.eArBà.aI4:SàaA.dI8:SàeA.r該文法存在著歸約-歸約沖突,所以不是LR(0)文法。對于狀態(tài)I6:Aàa.Bàa.Follow(A)=drFollow(B)=dr兩個集合相交不為空,
18、所以該文法也不是SLR(1)文法。構(gòu)造該文法的LR(1)文法可得該文法是LR(1)的。I0:SàS,#I2:Sàa.Ad,#I4:SàaA.d,#I10: SàaAd.,#Sà.aAd,#Sàa.Br,#I5:SàaB.r,#I11: SàaBr.,#Sà.eBd,#Aà.a,dI6:Aàa.,dI12: SàeBd.,#Sà.aBr,#Bà.a,rBàb.,rI13: SàeAr.,#Sà.eAr,#I3:Sàe.
19、Bd,#I7:SàeB.d,#I1:SàS.,#Sàe.Ar,#I8:SàeA.r,#Bà.a,dI9:Bàa.,dAà.a,rAàa.,r構(gòu)造LR(1)分析表(略)。(5)解:構(gòu)造LR(0)的分析表:I0:Sà.AI3:S->aB.I6:B->AB.Aà.aBI4:B->A.bAà.I5:B->a.I1:S->A.A->a.BI2:S->a.BB->.AbB->.AbB->.aB->.aA->.aBA->.
20、aBA->.A->.可以看到存在著移進(jìn)歸約的沖突,不是LR(0)文法。在I0中Follow(A)與相交不為空。所以也不為SLR(1)文法。構(gòu)造該文法的LR(1)項目集規(guī)范族:I0:S->.A,#I4:B->A.b,#I9:B->a.,bA->.aB,#I5:B->a.,#A->a.B,bA->.,#A->a.B,bB->.Ab,bI1:S->A.,#B->.Ab,bB->.a,bI2:A->a.B,#B->.a,bA->.aB,bB->.Ab,#,B->.aB,bA->.,b
21、B->.a,#A->.aB,bI10:B->AB.,bA->.aB,bI6:B->Ab.,#A->.,bI7:A->aB.,bI3:A->aB.,#I8:B->A.b,b其中存在沖突,所以文法也不是LR(1)文法。(6)解:將文法拓廣后得:(0) Sà S(1) Sà(SR(2) Sà a (3) Rà.SR(4) Rà)構(gòu)造LR(0)的項目集規(guī)范族:一個文法是LR(0)文法一定也是SLR(1)文法,也是LR(1)文法。但反之則不一定成立。 I0: SàS Sà(SRS&
22、#224;aI1: SàSI2: Sà(SRSà(SRSàaI4: Sà aI6: Rà.SRSà(SRSàaI7: Rà)I3: Sà(SRRà.SRRà)SRS.(S(aI5: Sà (SR.)I9: Rà.SR(I8: Rà.SRRà.SRRà)aa.)I0I9無沖突項目,所以此文法是LR(0)文法。構(gòu)造其LR(1)的DFA(構(gòu)造過程中,在建立好初態(tài)集后,立即產(chǎn)生所有新狀態(tài)的核集合,然后再逐步擴(kuò)充):狀態(tài)核集合項目集 (
23、核集合 + 閉包增加項目)I0SS,#SàS,# Sà(SR,#Sàa,#I1SàS,#SàS,#I2Sà(SR,#Sà(SR, #Sà(SR, ./)Sàa, ./)I3Sàa,#Sàa,#I4Sà(SR, #Sà(SR, #Rà.SR, #Rà), #I5Sà(SR, ./)Sà(SR, ./)Sà(SR, ./) -à I5Sàa, ./) -à I6I6Sàa, ./)
24、Sàa, ./)I7Sà(SR, #Sà(SR, #I8Rà.SR, #Rà.SR, #Sà(SR, ./) -à I5Sàa, ./) -à I6I9Rà), #Rà), #I10Sà(SR, ./)Sà(SR, ./)Rà.SR, ./)Rà), ./)I11Rà.SR, #Rà.SR, #Rà.SR, # -àI8Rà), # -àI9I12Sà(SR, ./)S
25、4;(SR, ./)I13Rà.SR, ./)Rà.SR, ./)Sà(SR, ./) -à I5Sàa, ./) -à I6I14Rà), ./)Rà), ./)I15Rà.SR, #Rà.SR, #I16Rà.SR, ./)Rà.SR, ./)Rà.SR, ./) -àI13Rà), ./) -àI14I17Rà.SR, ./)Rà.SR, ./)無移進(jìn)-規(guī)約沖突和規(guī)約-規(guī)約沖突,此文法是LR(1)文法。對同心集
26、合并,得LALR(1)項目集規(guī)范族:狀態(tài)核集合項目集 (核集合 + 閉包增加項目)I0SS,#SàS,# Sà(SR,#Sàa,#I1SàS,#SàS,#I2,5Sà(SR,#Sà(SR, ./)/#Sà(SR, ./)Sàa, ./)I3,6Sàa,#Sàa,./)/#I4,10Sà(SR, #Sà(SR, ./)/#Rà.SR, #Rà), #I7,12Sà(SR, #Sà(SR, ./)/#I8,13Rà.SR
27、, #Rà.SR, ./)/#Sà(SR, ./) -à I5Sàa, ./) -à I6I9,14Rà), #Rà), ./)/#I11,16Rà.SR, #Rà.SR,./)/#Rà.SR, # -àI8Rà), # -àI9I15,17Rà.SR, #Rà.SR, ./)/#同心集合并后無沖突,其項目集的個數(shù)與LR(0)相同,此文法是LALR(1)文法。11. 設(shè)文法GS為:SàAS| AàaA|b(1) 證明GS是LR
28、(1)文法(2) 構(gòu)造出它的LR(1)分析表(3) 給出輸入符號串a(chǎn)bab#的分析過程一個文法不是SLR(1)時,不能證明它是LR(1)的解:將文法改寫為拓廣文法: (0) SS (1) SàAS (2) Sà (3) AàaA (4) Aàb 構(gòu)造其LR(1)項目集規(guī)范族:狀態(tài)核集合項目集 (核集合 + 閉包增加項目)I0SS,#SàS,# SàAS,#Sà,#AàaA, a/b/#Aàb, a/b/#I1SàS,#SàS,#I2SàAS,#SàAS,#S
29、4;AS,# -àI2Sà,#AàaA, a/b/# -àI3Aàb, a/b/# -àI4I3AàaA, a/b/#AàaA, a/b/#AàaA, a/b/# -àI3Aàb, a/b/# -àI4I4Aàb, a/b/#Aàb, a/b/#I5SàAS,#SàAS,#I6AàaA, a/b/#AàaA, a/b/#LR(1)分析表:狀態(tài)ACTIONGOTOab#SA0S3S4r2121acc2S3S4r2523
30、S3S464r4r4r45r16r3r3r3對abab#的分析過程:步驟狀態(tài)棧符號棧輸入串ACTIONGOTO10#abab#S3203#abab#S43034#abab#r464036#aAab#r35502#Aab#S36023#Aab#S470234#Aab#r480236#AaA#r329022#AA#r25100225#AAS#r1511025#AS#r111201#S#acc第15題:已知文法為: Sàa|Ù|(T) TàT,S|S (1) 構(gòu)造它的LR(0)、LALR(1),LR(1)分析表(2) 給出對輸入符號長(a#和(a,a#的分析過程(3)說
31、明(1)中三種分析表發(fā)現(xiàn)錯誤的時刻和輸入串的出錯位置有何區(qū)別。解:構(gòu)造該文法的LR(0)項目集規(guī)范集:I0:Sà.SI2:Sàa.I5:Sà(T.)I9:TàT,S.Sà.aI3:Sà.TàT.,SSà.I4:Sà(.T)I6:TàS.Sà.(T)Tà.T,SI7:Sà(T).I1:SàS.Tà.SI8:TàT,.SSà.aSà.aSà.Sà.Sà.(T)Sà(T)構(gòu)造LR(0
32、)分析表:狀態(tài)ACTIONGOTOa(),#ST0S2S3S411acc2r2r2r2r2r2r23r3r3r3r3r3r34S2S3S4655S8S76r6r6r6r6r6r67r4r4r4r4r4r48S2S3S499r5r5r5r5r5r5構(gòu)造LR(1)規(guī)范集族:I0:Sà.S,#I2:Sàa.,#I5:Sà(T.),#I9:TàT,S.,)Sà.a,#I3:Sà.,#TàT.,S,)I10:S->a.,)Sà.,#I4:Sà(.T),#I6:TàS.,)I11:S->.,)Sà.(T),#Tà.T,S,)I7:Sà(T).,#I12:S->(.T),)I1:SàS.,#Tà.S,)I8:TàT,.S,)T->.T,S,)Sà.a,)Sà.a,)T->.S,)Sà.,)Sà.,)S->.a,)Sà.(T),)Sà(T),)S->.,I13:S->(T.),)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 保險代理業(yè)務(wù)風(fēng)險管理考核試卷
- 女性健康管理考核試卷
- 搜索引擎的智能糾錯功能考核試卷
- 壓力容器在物流系統(tǒng)中的故障預(yù)測與維護(hù)系統(tǒng)構(gòu)建考核試卷
- 刀具材料抗粘附性研究考核試卷
- 機(jī)械式停車設(shè)備維護(hù)保養(yǎng)規(guī)范
- 機(jī)械產(chǎn)業(yè)鏈優(yōu)化
- 企業(yè)安全生產(chǎn)培訓(xùn)工作總結(jié)
- 婚戀教育主題班會課件
- 沈陽市第120中學(xué)2024-2025學(xué)年高二下學(xué)期第三次質(zhì)量監(jiān)測政治試卷(含答案)
- 《文旅服務(wù)信息資源分類及編碼規(guī)范》
- 預(yù)防慢性病與健康生活指南
- 電解鋅車間管理制度
- 2025至2030中國水果行業(yè)市場發(fā)展分析及發(fā)展前景與投資報告
- 航空業(yè)飛機(jī)維護(hù)與檢查標(biāo)準(zhǔn)
- 高級保育考試試題及答案
- 二年級上冊勞動技術(shù)課課件
- 2025年行政法與行政訴訟考試試題及答案
- 2025常州工學(xué)院輔導(dǎo)員考試試題及答案
- 2025春季學(xué)期國開電大專科《經(jīng)濟(jì)學(xué)基礎(chǔ)》一平臺在線形考(形考任務(wù)1至4)試題及答案
- 2025年4月自考02324離散數(shù)學(xué)答案含評分參考
評論
0/150
提交評論