廣工編譯原理Chapter7老師自己做的

1、第第7 7章章 LR LR分析法分析法7.1 LR分析法概述7.2 LR(0)分析7.3 SLR(1)分析7.4 LR(1)分析7.5 LALR(1)分析7.6 二義性文法7.1 LR7.1 LR分析分析 LR分析方法是當(dāng)前最被廣泛應(yīng)用的無(wú)回溯的“移進(jìn)移進(jìn)- -歸約歸約”方法。 LR(k)分析技術(shù)：這里的“L”是指從左至右掃描輸入符號(hào)串，“R”是指它的歸約過(guò)程是最右推導(dǎo)的逆過(guò)程，即規(guī)范規(guī)范歸約歸約，“k”是指為了作出分析決定而向前看的輸入符號(hào)的個(gè)數(shù)。 LR分析器的構(gòu)造和工作過(guò)程 （此處略）7.1 LR分析分析7.2 LR(0)7.2 LR(0)分析分析LR(0)分析法：能力最弱，理論上最重要

2、活前綴 識(shí)別活前綴的DFA如何構(gòu)造 （LR(0)項(xiàng)目集規(guī)范族的構(gòu)造） LR(0)分析表的構(gòu)造 LR(0)分析法的實(shí)現(xiàn)文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步驟步驟符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # abbcde# 移進(jìn)移進(jìn) 2） #a bbcde# 移進(jìn)移進(jìn)A 3） #ab bcde# 歸約歸約(Ab) 4） #aA bcde# 移進(jìn)移進(jìn)A 5） #aAb cde# 歸約歸約(AAb) 6） #aA cde# 移進(jìn)移進(jìn) 7） #aAc de# 移進(jìn)移進(jìn)B 8） #aAcd e# 歸約歸約(Bd) 9） #aAcB e

3、# 移進(jìn)移進(jìn)11） #S # 接受接受S10） #aAcBe # 歸約歸約(SaAcBe)對(duì)輸入串對(duì)輸入串a(chǎn)bbcde的移進(jìn)的移進(jìn)-規(guī)約分析過(guò)程規(guī)約分析過(guò)程活前綴活前綴G =(Vn,Vt ,P,S)，若有 SA,是的前綴，則稱(chēng)是文法G的活前綴。包含了句柄的活前綴稱(chēng)為可歸前綴。RR*注意：注意：為使文法開(kāi)始符號(hào)不出現(xiàn)在任何產(chǎn)生式的右部，需對(duì)文法進(jìn)行擴(kuò)展，例如：G =（S,a,SSa,Sa,S），擴(kuò)充文法有： G=（S,a,SS, SSa,Sa,S）構(gòu)造識(shí)別活前綴的構(gòu)造識(shí)別活前綴的DFA基本思想：構(gòu)造LR(0)項(xiàng)目集規(guī)范族（構(gòu)成識(shí)別活前綴的DFA的全體狀態(tài)）(1) LR(0)(1) LR(0)項(xiàng)目

4、項(xiàng)目 在文法中每個(gè)產(chǎn)生式的右部的某一個(gè)適當(dāng)位置添加一個(gè)圓點(diǎn)構(gòu)成項(xiàng)目 例： A aBc A.aBc Aa.Bc AaB.c AaBc.項(xiàng)目的含義：圓點(diǎn)的左部表示歸約過(guò)程中已經(jīng)處理的部分；圓點(diǎn)的右部表示待處理的部分。LR(0)項(xiàng)目分類(lèi):根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符或?yàn)榭瞻秧?xiàng)目分為以下幾種：移進(jìn)項(xiàng)目，形如 Aa,a是終結(jié)符, ,V* 待約項(xiàng)目，形如 A B, B是非終結(jié)符歸約項(xiàng)目，形如 A 接受項(xiàng)目，形如 SS, SS 是拓廣文法得到新產(chǎn)生式規(guī)定：A的LR(0)項(xiàng)目只有A 是歸約項(xiàng)目(2) LR(0) (2) LR(0) 項(xiàng)目集的閉包項(xiàng)目集的閉包 若當(dāng)前項(xiàng)目集包含A X項(xiàng)目，該項(xiàng)目

5、刻畫(huà)的狀態(tài)是期望移進(jìn)First(X)中的某些符號(hào)， 假如有產(chǎn)生式Xu，那么有項(xiàng)目X.u，這個(gè)項(xiàng)目也是刻畫(huà)期望移進(jìn)First(X)中的某些符號(hào)的情況。 由于這兩個(gè)項(xiàng)目刻畫(huà)的是相同的狀態(tài)，因此，將這兩個(gè)項(xiàng)目合并一個(gè)項(xiàng)目集。構(gòu)造識(shí)別活前綴的構(gòu)造識(shí)別活前綴的DFA(續(xù)續(xù))設(shè)I是文法G的一個(gè)LR(0)項(xiàng)目集合，closure(I)是從I出發(fā)用下面三個(gè)規(guī)則構(gòu)造的項(xiàng)目集: I中每一個(gè)項(xiàng)目都屬于closure(I);若項(xiàng)目ABclosure(I)，且BP 則將B 加進(jìn)closure(I)中; 復(fù)執(zhí)行(2)直到closure(I)不再增大為止。 例 對(duì)拓廣文法GS： (0) SS (1) SaA (2) SbB

6、 (3) AcA (4) Ad (5) BcB (6) Bd I=S.Sclosure(I)=S.S, S.aA, S.bB(3) (3) 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù) 若I是G的一個(gè)LR(0)項(xiàng)目集, XVTVN GO(I,X)=closure(J) 其中，J=AX|當(dāng)AXI ，項(xiàng)目AX稱(chēng)為AX的后繼。構(gòu)造識(shí)別活前綴的構(gòu)造識(shí)別活前綴的DFA(續(xù)續(xù))直觀含義: 它規(guī)定了識(shí)別活前綴的DFA從狀態(tài)I(項(xiàng)目集)出發(fā)，經(jīng)過(guò)X弧所應(yīng)該到達(dá)的狀態(tài)J(項(xiàng)目集) 。例 對(duì)拓廣文法GS： (0) SS (1) SaA (2) SbB (3) AcA (4) Ad (5) BcB (6) Bd I=S.S,S.aA,

7、 S.bBGO(I,a)=Sa.A, A.cA, A.d(4) (4) 計(jì)算計(jì)算LR(0)LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族 C=I C=I0 0，I I1 1, .,I, .,In n Procedure itemsets(G); Begin C := CLOSURE (S.S) Repeat For C 中每一項(xiàng)目集I和每一文法符號(hào)x Do if GO(I,x) 非空且不屬于C Then 把 GO(I,x) 放入C中 Until C 不再增大 End; DFA m= VTVN S , Q 項(xiàng)目集規(guī)范族 ， q0= closure S S , Q , =GO（I,X） ）它識(shí)別文法G的所有活

8、前綴的自動(dòng)機(jī)。構(gòu)造識(shí)別活前綴的構(gòu)造識(shí)別活前綴的DFA(續(xù)續(xù))例：文法GS： (1) SaA (2) SbB (3) AcA (4) Ad (5) BcB (6) Bd 基本思路：1、拓廣文法SS2、構(gòu)造LR(0)項(xiàng)目集規(guī)范族3、由狀態(tài)轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系， 以構(gòu)造識(shí)別活前綴的DFAI I0 0: :S.SS.SS.aAS.aAS.bBS.bBI I1 1: SS.: SS.SI I2 2: :Sa.ASa.AA.cAA.cAA.dA.dabI I3 3: : Sb.BSb.BB.cBB.cBB.d B.d I I4 4:SaA.:SaA.AI5 :Ac.AAc.AA.cAA.cAA.

9、dA.dcI I6 6:A:Ad.d.dI I7 7:SbB.:SbB.BI I8 8: :Bc.BBc.BB.cBB.cBB.dB.dcI I9 9:Bd.:Bd.dI10 :AcA.AcA.AcdI I1111:BcB.:BcB.Bcd問(wèn)題：識(shí)別符號(hào)串a(chǎn)cd是否為文法的合法句子。 (0) SS (1) SaA (2) SbB (3) AcA (4) Ad (5) BcB (6) Bd LR(0)分析表的構(gòu)造分析表的構(gòu)造假定C=I0, I1,，In，令每個(gè)項(xiàng)目集Ik的下標(biāo)k 為分析器的一個(gè)狀態(tài)，因此，G的LR(0)分析表含有狀態(tài)0，1，n。令那個(gè)含有項(xiàng)目SS的Ik的下標(biāo)k為初態(tài)。ACTION

10、和GOTO可按如下方法構(gòu)造：1 若項(xiàng)目A.a屬于Ik且GO (Ik, a)= Ij, a為終結(jié)符，則置ACTIONk, a為“Sj”，表示狀態(tài)k遇上a后轉(zhuǎn)向狀態(tài)j;2 若項(xiàng)目A屬于Ik, 那么，對(duì)任何終結(jié)符a, 置ACTIONk, a為“rj”，表示當(dāng)前“用產(chǎn)生式A進(jìn)行歸約”;其中，假定A為文法G的第j個(gè)產(chǎn)生式；3 若項(xiàng)目SS屬于Ik, 則置ACTIONk, #為“acc” ，表示“可接受”; 4 若GO (Ik, A)= Ij, A為非終結(jié)符，則置GOTO(k, A)為“j”;5 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯(cuò)標(biāo)志”。 action goto 狀態(tài) a b c d #

11、 S A B 0 1 2 3 4 5 6 7 8 9 10 11 s2 s3 acc s5 s6 s8 s9 r1 r1 r1 r1 r1 s5 s6 r4 r4 r4 r4 r4 r2 r2 r2 r2 r2 s8 s9 r6 r6 r6 r6 r6 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 1 4 7 10 11 按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱(chēng)它為文法G的一張LR(0)表。具有LR(0)表的文法G稱(chēng)為L(zhǎng)R(0)LR(0)文法。文法。 或?qū)τ谝粋€(gè)文法的LR(0)的項(xiàng)目集規(guī)范族中不存在移進(jìn)/歸約、歸約/歸約沖突，稱(chēng)這個(gè)

12、文法G為L(zhǎng)R(0)LR(0)文法。文法。LR分析分析器模型器模型總控程序outputInput#SiXiS1X1S0 #棧狀態(tài)文法符號(hào)ACTION GOTOLR分析表產(chǎn)生式表LR分析程序分析程序 初始化：初始化：狀態(tài)棧為0，文法符號(hào)棧中只有終止符號(hào)#，輸入隊(duì)列中有輸入符號(hào)串 w#； 設(shè)置 ip 指向 w# 的第一個(gè)符號(hào) 重復(fù) begin 令i是狀態(tài)棧頂元素，a是ip所指向的符號(hào) if ACTIONi,a=Sj /移進(jìn)移進(jìn) then begin PUSH j,a (進(jìn)狀態(tài)棧和文法符號(hào)棧) ip 前進(jìn)(指向下一輸入符號(hào)) endelse if ACTIONi,a=rj (第j條產(chǎn)生式為A) /歸約

13、歸約LR分析程序分析程序then begin (第j條產(chǎn)生式為A) pop | 項(xiàng) 令當(dāng)前狀態(tài)棧頂值為i push GOTOi,A和A(進(jìn)棧)endelse if ACTIONi,a=acc /接受接受 then return (成功） else if ACTIONi,a=空白 /錯(cuò)誤錯(cuò)誤 then errorend.重復(fù)LR分析程序分析程序例例 GS: S GS: S aAcBeaAcBe A A b b A A AbAb B B d d識(shí)別識(shí)別abbcdeabbcde是否為文法的句子是否為文法的句子步驟步驟 符號(hào)棧符號(hào)棧 輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # abbcde# 移進(jìn)移進(jìn) 0

14、 S2 2） #a bbcde# 移進(jìn)移進(jìn) 02 S4 4） #aA bcde# 移進(jìn)移進(jìn) 023 S6 6） #aA cde# 移進(jìn)移進(jìn) 023 S5 7） #aAc de# 移進(jìn)移進(jìn) 0235 S8 9） #aAcB e# 移進(jìn)移進(jìn) 02357 S911） #S # 接受接受 01 acc對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過(guò)程分析過(guò)程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3 5） #aAb cde# 歸約歸約(AAb) 0236 r3 3 8） #aAcd e# 歸約歸約(Bd) 02358 r4 710） #aAcBe # 歸約歸約(SaAcBe) 0235

15、79 r1 1ACTION GOTO a c e b d # S A B 0 S2 1 1 acc 2 S4 3 3 S5 S6 4 r2 r2 r2 r2 r2 r2 5 S8 7 6 r3 r3 r3 r3 r3 r3 7 S9 8 r4 r4 r4 r4 r4 r4 9 r1 r1 r1 r1 r1 r1 狀態(tài)棧狀態(tài)棧ACTIONGOTO文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dSi:移進(jìn)，將狀態(tài)移進(jìn)，將狀態(tài)i和和輸入符輸入符進(jìn)棧進(jìn)棧ri:歸約，用第歸約，用第i個(gè)產(chǎn)生式歸約，同個(gè)產(chǎn)生式歸約，同時(shí)狀態(tài)棧與符號(hào)棧退出相應(yīng)個(gè)符時(shí)狀態(tài)棧與符號(hào)棧退出相應(yīng)個(gè)符號(hào)

16、，并把號(hào)，并把GOTO表相應(yīng)狀態(tài)和第表相應(yīng)狀態(tài)和第i個(gè)產(chǎn)生式的個(gè)產(chǎn)生式的左部非終結(jié)非終結(jié)符入棧。符入棧。例例, ,已知拓廣文法已知拓廣文法GSGS: (0) S (0) SS (1) SrDS (1) SrD (2) DD,i (3) Di (2) DD,i (3) DiI I0 0: :S.S.S SS.rDS.rDI I1 1: : SS.SS.S Sr rI I2 2: : Sr.DSr.DD.D,iD.D,iD.i D.i I I4 4:D:Di.i.i iI I3 3: :SrD.SrD.DD.,iDD.,iD DI I5 5:DD,.i:DD,.i,iI I6 6:DD,i.:DD

17、,i.問(wèn)題：?jiǎn)栴}：其中其中I I3 3中含有移進(jìn)中含有移進(jìn)/ /歸約沖突歸約沖突, ,文法不是文法不是LR(0)LR(0)的，如何解決？的，如何解決？action goto 狀態(tài) r , i # S D 0 1 2 3 4 5 6 s2 acc s4 r1 r1,s5 r1 r1 r3 r3 r3 r3 s6 r2 r2 r2 r2 1 3 7.3 SLR(1)分析分析解決沖突的思路：這里僅僅憑LR(0) 項(xiàng)目本身的信息已經(jīng)無(wú)法解決項(xiàng)目之間的沖突，需要向前查看一個(gè)符號(hào)，再來(lái)決定到底是采取移進(jìn)動(dòng)作還是歸約動(dòng)作。主要解決方法如下： 如果一個(gè)LR(0)項(xiàng)目集規(guī)范族中含有如下的項(xiàng)目集II= X b,

18、A 存在移進(jìn)-規(guī)約沖突,但是若FOLLOW(A) b = ，沖突便可以解決7.3 SLR(1)分析（續(xù)）分析（續(xù)）I=X b, A 當(dāng)在狀態(tài)I面臨符號(hào)a時(shí)：1、對(duì) a=b 則actionI,b= closure( X b. )移進(jìn)2、對(duì) aFOLLOW (A) 則 action I,a= 用 A歸約 這種解決方法是比較簡(jiǎn)單的，因此稱(chēng)作SLR(1)分析，此構(gòu)造的分析表，稱(chēng)作SLR(1)分析表。假定C=I0,I1,，In，令每個(gè)項(xiàng)目集Ik的下標(biāo)k為分析器的一個(gè)狀態(tài)，因此，G的SLR分析表含有狀態(tài)0,1，,n。令那個(gè)含有項(xiàng)目SS的Ik的下標(biāo)k為初態(tài)。函數(shù)ACTION和GOTO可按如下方法構(gòu)造：1 若

19、項(xiàng)目Aa屬于Ik且GO (Ik, a)= Ij, a為終結(jié)符，則置ACTIONk, a為“Sj”;2 2 若項(xiàng)目若項(xiàng)目AA屬于屬于I Ik k, ,那么，對(duì)任何輸入符號(hào)那么，對(duì)任何輸入符號(hào)a,a, aFOLLOW(A), aFOLLOW(A),置置ACTIONk, aACTIONk, a為為“r“rj j”,”,表示表示“用用產(chǎn)生式產(chǎn)生式AA進(jìn)行歸約進(jìn)行歸約”，其中，假定，其中，假定AA為文法為文法GG的第的第j j個(gè)產(chǎn)生式；個(gè)產(chǎn)生式；SLR(1)分析表的構(gòu)造分析表的構(gòu)造3 若項(xiàng)目SS屬于Ik, 則置ACTIONk, #為 “acc”,表示“可接受”;4 若GO(Ik, A)=Ij, A為非終

20、結(jié)符，則置GOTO(k, A)=j; 5 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯(cuò)標(biāo)志”。SLR分析表的構(gòu)造（續(xù)）分析表的構(gòu)造（續(xù)） 按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱(chēng)它為文法G的一張改進(jìn)SLR(1)分析表。具有SLR(1)分析表的文法G稱(chēng)為一個(gè)SLR(1)文法。 SLR(1)分析法中的數(shù)字1的意思是，在分析過(guò)程中頂多只要向前看一個(gè)符號(hào)。SLR分析表的構(gòu)造（續(xù)）分析表的構(gòu)造（續(xù)）例：文法GS: (0) SS (1) SrD (2) DD,i (3) DiI I2 2: : Sr.DSr.DD.D,iD.D,iD.i D.i I

21、 I0 0: :S.S.S SS.rDS.rDI I1 1: : SS.SS.S Sr rI I4 4:D:Di.i.i iI I3 3: :SrD.SrD.DD.,iDD.,iD DI I5 5:DD,.i:DD,.i,iI I6 6:DD,i.:DD,i.action goto 狀態(tài) r , i # S D 0 1 2 3 4 5 6 s2 acc s4 r1 r1,s5 r1 r1 r3 r3 r3 r3 s6 r2 r2 r2 r2 1 3 I3 = SrD. , DD.,I Follow(S)= # I3:FOLLOW(S),=因此可用SLR(1)方法 s5 r1 r3 r3 r2

22、r2例, 已知拓廣文法GS(0) S S (1) S L=R (2) S R (3) L *R (4) L id (5) R LI I1 1I I0 0I I3 3I I2 2I I6 6I I9 9I I8 8I I7 7I I5 5I I4 4startstartS SR RL Lidid* *= =ididididL LL LR R* * *R RI I0 0= S= S.S, .S, S S.L=R, S.L=R, S.R, .R, L L. .* *R, LR, L.id, .id, R R.L .L 處在狀態(tài) 2時(shí)，試圖構(gòu)建句子有兩條路：1. S L = R 2. S R L SL

23、RSLR（1 1）的局限的局限問(wèn)題分析：?jiǎn)栴}分析：follow 集包含了在任何句型中跟在R后的符號(hào)但沒(méi)有嚴(yán)格地指出在一個(gè)特定的推導(dǎo)里哪些符號(hào)跟在R后。所以需要擴(kuò)充狀態(tài)以包含更多的信息。7.4 LR(1)分析法分析法基本思想:如果存在規(guī)范推導(dǎo) S Aw w 當(dāng)且僅當(dāng)當(dāng)前輸入的符號(hào)為aFirst(w#)時(shí)，才能用產(chǎn)生式A進(jìn)行歸約。 因此，在LR(1)方法中重新定義項(xiàng)目,使每個(gè)項(xiàng)目附帶一個(gè)向前搜索符。*RR A.，a A.：核，為L(zhǎng)R(0)項(xiàng)目； a：向前搜索符，要么是一個(gè)終結(jié)符，要么是輸入結(jié)束標(biāo)記#。 向前搜索符(lookahead)只對(duì)歸約項(xiàng)目起作用 A ., a 意味著處在符號(hào)棧棧頂形成句柄，

24、當(dāng)且僅當(dāng)下一個(gè)輸入符是a時(shí)才能進(jìn)行歸約。 如果有多個(gè)向前搜索符，比如a,b,c時(shí)，可寫(xiě)作: A u., a/b/c LR(1)項(xiàng)目( 配置）的一般形式：構(gòu)造構(gòu)造LR(1)項(xiàng)目集項(xiàng)目集規(guī)范族規(guī)范族Closure(I)Closure(I)按如下方式構(gòu)造(I為L(zhǎng)R(1)項(xiàng)目集)：1、I的任何項(xiàng)目屬closure(I)；2、若A X，aclosure(I)， Xu是一產(chǎn)生式，那么對(duì)于FIRST(a)中的每個(gè)終結(jié)符b， 如果X.u,b不在 closure(I)中，則把它加進(jìn)去；3、重復(fù)（2），直至closure(I)不再增大。GOGO函數(shù)函數(shù)按如下方式構(gòu)造：若I是一個(gè)項(xiàng)目集，X是一個(gè)文法符號(hào)GO(I,

25、X)= closure(J) 其中 J= 任何形如AX.,a的項(xiàng)目A.X,aILR(1)項(xiàng)目規(guī)范族C的構(gòu)造算法類(lèi)同LR(0)的，只是初始時(shí)： C= closure(S.S,#)C= closure(S.S,#)例：已知文法GS如下 (1)SBB (2)BaB (3)Bb 基本思路：1、拓廣文法：SS2、構(gòu)造LR(1)項(xiàng)目集規(guī)范族3、由狀態(tài)轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系，以構(gòu)造識(shí)別活前綴的DFAI0:S S,# S BB,# B aB,a/b B b,a/b I1:S S,#I2:S BB,# B aB,#B b,# I5:S BB,#I6:B aB,# B aB,#B b,# I3:B aB,

26、a/b B aB,a/b B b,a/b I4:B b,a/bI7:B b,#I9:B aB,#I8:B aB,a/bsBBabbbBBaaaLR(1)項(xiàng)目集和轉(zhuǎn)換函數(shù)bGSGS：(0)S(0)S S (1) S (1)S S BB (2)B BB (2)BaB (3)B aB (3)B b b規(guī)范的規(guī)范的LR(1)分析表的構(gòu)造分析表的構(gòu)造定義： 與LR(0)分析表構(gòu)造不同的，當(dāng)狀態(tài)Ik中包含歸約項(xiàng)目A,a時(shí)，則 ACTIONk, a為“rj”,其中，假定A為文法G的第j個(gè)產(chǎn)生式；按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱(chēng)它為文法G的一張規(guī)范的LR

27、(1)分析表。具有規(guī)范的LR(1)表的文法G稱(chēng)為一個(gè)LR(1)文法。LR(1)文法滿足下面兩個(gè)條件1 如果一個(gè)項(xiàng)目集里有項(xiàng)目A uxv, a，x是終結(jié)符，那就不會(huì)有項(xiàng)目B u,x 2 項(xiàng)目集里所有歸約項(xiàng)目的向前搜索符不相交，即不能同時(shí)含有項(xiàng)目A u,a 和B v,a 0 S3 S4 1 2 1 acc 2 S6 S7 5 3 S3 S4 8 4 r3 r3 5 r1 6 S6 S7 9 7 r3 8 r2 r2 9 r2LR(1)分析表ab#SBACTIONGOTO狀態(tài)文法GS：(0) S S (1)S BB (2)BaB (3)B b例：GS (0)SS (1)SL=R (2)SR (3)L

28、*R (4)Li (5)RL 判斷文法是否是LR(1)文法？LR(1)項(xiàng)目集及轉(zhuǎn)換函數(shù)LI1:SS ,#I5:Li ,=/#I7:L*R ,=/#I8:RL ,=/#I9:SL=R ,#I3:SR ,#I12:Li ,#I10:RL ,#I13:L*R ,#I0:S S,# S L=R,# S R,# L *R,=/#L i,=/# R L,# I4: L *R,=/# R L,=/#L i,=/# L *R,=/#I6:S L= R,# R L,# L *R,# L i,# I11:L * R,# R L,# L *R,# L i,# I2:S L =R,# R L,# sR=LRii*ii

29、RLRL*結(jié)論:1.不能用SLR(1)方法解決，但能用LR(1)，因 此LR(1)比SLR(1)分析能力強(qiáng)；2.每個(gè)SLR(1)文法都是LR(1)文法的，一個(gè)文法的LR(1)分析器比其SLR(1)分析器的狀態(tài)要多。LALR(lookahead LR )基本思想：合并同心集同心集 I3:B a B,a/b B aB,a/b B b,a/b I6: B a B,# B aB,#B b,# I4:B b,a/bI7:B b,#I8:B aB,a/bI9:B aB,#LALR(1)分析法分析法I4和I7I8和I9I36:B a B,a/b/# B aB,a/b/# B b,a/b/# I3和I6I0:

30、S S,# S BB,# B aB,a/b B b,a/b I1:S S,#I2:S B B,# B aB,#B b,# I5:S BB,#I6:B a B,# B aB,#B b,# I3:B a B,a/b B aB,a/b B b,a/b I4:B b,a/bI7:B b,#I9:B aB,#I8:B aB,a/bsBBabbbBBaaaLR(1)項(xiàng)目集和轉(zhuǎn)換函數(shù)bGSGS：(0)S(0)S S (1) S (1)S S BB (2)B BB (2)BaB (3)B aB (3)B b b判斷文法是否為判斷文法是否為L(zhǎng)R(1)LR(1)文法和文法和LALR(1)LALR(1)文法。文法。合并同心集同心集I3和I6、I4和I7 、I8和I9 ，得到新項(xiàng)目集I36、I47和I89合并同心集同心集I3和I6 I4和I7 I8和I9 ，得到新項(xiàng)目集I36、I47和I89I0:S S,# S BB,# B aB,a/b B b,a/b I1:S S,#I2:S B B,# B aB,#B b,# I5:S BB,#I36:B a B,a/b/# B aB,a/b/# B b,a/b/# I47:B b,a/b/#I89:B aB,a/b/#sBBabbbBaaGSGS：(0)S(0)S S (1) S (1)S S BB (2