廣工編譯原理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分析方法是當前最被廣泛應用的無回溯的“移進移進- -歸約歸約”方法。 LR(k)分析技術：這里的“L”是指從左至右掃描輸入符號串，“R”是指它的歸約過程是最右推導的逆過程，即規(guī)范規(guī)范歸約歸約，“k”是指為了作出分析決定而向前看的輸入符號的個數。 LR分析器的構造和工作過程 （此處略）7.1 LR分析分析7.2 LR(0)7.2 LR(0)分析分析LR(0)分析法：能力最弱，理論上最重要

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

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

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

5、刻畫的狀態(tài)是期望移進First(X)中的某些符號， 假如有產生式Xu，那么有項目X.u，這個項目也是刻畫期望移進First(X)中的某些符號的情況。 由于這兩個項目刻畫的是相同的狀態(tài)，因此，將這兩個項目合并一個項目集。構造識別活前綴的構造識別活前綴的DFA(續(xù)續(xù))設I是文法G的一個LR(0)項目集合，closure(I)是從I出發(fā)用下面三個規(guī)則構造的項目集: I中每一個項目都屬于closure(I);若項目ABclosure(I)，且BP 則將B 加進closure(I)中; 復執(zhí)行(2)直到closure(I)不再增大為止。 例 對拓廣文法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)轉移函數狀態(tài)轉移函數 若I是G的一個LR(0)項目集, XVTVN GO(I,X)=closure(J) 其中，J=AX|當AXI ，項目AX稱為AX的后繼。構造識別活前綴的構造識別活前綴的DFA(續(xù)續(xù))直觀含義: 它規(guī)定了識別活前綴的DFA從狀態(tài)I(項目集)出發(fā)，經過X弧所應該到達的狀態(tài)J(項目集) 。例 對拓廣文法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) 計算計算LR(0)LR(0)項目集規(guī)范族項目集規(guī)范族 C=I C=I0 0，I I1 1, .,I, .,In n Procedure itemsets(G); Begin C := CLOSURE (S.S) Repeat For C 中每一項目集I和每一文法符號x Do if GO(I,x) 非空且不屬于C Then 把 GO(I,x) 放入C中 Until C 不再增大 End; DFA m= VTVN S , Q 項目集規(guī)范族 ， q0= closure S S , Q , =GO（I,X） ）它識別文法G的所有活

8、前綴的自動機。構造識別活前綴的構造識別活前綴的DFA(續(xù)續(xù))例：文法GS： (1) SaA (2) SbB (3) AcA (4) Ad (5) BcB (6) Bd 基本思路：1、拓廣文法SS2、構造LR(0)項目集規(guī)范族3、由狀態(tài)轉換函數建立狀態(tài)之間的連接關系， 以構造識別活前綴的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問題：識別符號串acd是否為文法的合法句子。 (0) SS (1) SaA (2) SbB (3) AcA (4) Ad (5) BcB (6) Bd LR(0)分析表的構造分析表的構造假定C=I0, I1,，In，令每個項目集Ik的下標k 為分析器的一個狀態(tài)，因此，G的LR(0)分析表含有狀態(tài)0，1，n。令那個含有項目SS的Ik的下標k為初態(tài)。ACTION

10、和GOTO可按如下方法構造：1 若項目A.a屬于Ik且GO (Ik, a)= Ij, a為終結符，則置ACTIONk, a為“Sj”，表示狀態(tài)k遇上a后轉向狀態(tài)j;2 若項目A屬于Ik, 那么，對任何終結符a, 置ACTIONk, a為“rj”，表示當前“用產生式A進行歸約”;其中，假定A為文法G的第j個產生式；3 若項目SS屬于Ik, 則置ACTIONk, #為“acc” ，表示“可接受”; 4 若GO (Ik, A)= Ij, A為非終結符，則置GOTO(k, A)為“j”;5 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯標志”。 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 按上述算法構造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法G的一張LR(0)表。具有LR(0)表的文法G稱為LR(0)LR(0)文法。文法。 或對于一個文法的LR(0)的項目集規(guī)范族中不存在移進/歸約、歸約/歸約沖突，稱這個

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

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

14、 S2 2） #a bbcde# 移進移進 02 S4 4） #aA bcde# 移進移進 023 S6 6） #aA cde# 移進移進 023 S5 7） #aAc de# 移進移進 0235 S8 9） #aAcB e# 移進移進 02357 S911） #S # 接受接受 01 acc對輸入串對輸入串abbcde#的的LR分析過程分析過程 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:移進，將狀態(tài)移進，將狀態(tài)i和和輸入符輸入符進棧進棧ri:歸約，用第歸約，用第i個產生式歸約，同個產生式歸約，同時狀態(tài)棧與符號棧退出相應個符時狀態(tài)棧與符號棧退出相應個符號

16、，并把號，并把GOTO表相應狀態(tài)和第表相應狀態(tài)和第i個產生式的個產生式的左部非終結非終結符入棧。符入棧。例例, ,已知拓廣文法已知拓廣文法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.問題：問題：其中其中I I3 3中含有移進中含有移進/ /歸約沖突歸約沖突, ,文法不是文法不是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) 項目本身的信息已經無法解決項目之間的沖突，需要向前查看一個符號，再來決定到底是采取移進動作還是歸約動作。主要解決方法如下： 如果一個LR(0)項目集規(guī)范族中含有如下的項目集II= X b,

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

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

20、結符，則置GOTO(k, A)=j; 5 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯標志”。SLR分析表的構造（續(xù)）分析表的構造（續(xù)） 按上述算法構造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法G的一張改進SLR(1)分析表。具有SLR(1)分析表的文法G稱為一個SLR(1)文法。 SLR(1)分析法中的數字1的意思是，在分析過程中頂多只要向前看一個符號。SLR分析表的構造（續(xù)）分析表的構造（續(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時，試圖構建句子有兩條路：1. S L = R 2. S R L SL

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

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

25、X)= closure(J) 其中 J= 任何形如AX.,a的項目A.X,aILR(1)項目規(guī)范族C的構造算法類同LR(0)的，只是初始時： C= closure(S.S,#)C= closure(S.S,#)例：已知文法GS如下 (1)SBB (2)BaB (3)Bb 基本思路：1、拓廣文法：SS2、構造LR(1)項目集規(guī)范族3、由狀態(tài)轉換函數建立狀態(tài)之間的連接關系，以構造識別活前綴的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)項目集和轉換函數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)分析表的構造分析表的構造定義： 與LR(0)分析表構造不同的，當狀態(tài)Ik中包含歸約項目A,a時，則 ACTIONk, a為“rj”,其中，假定A為文法G的第j個產生式；按上述算法構造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法G的一張規(guī)范的LR

27、(1)分析表。具有規(guī)范的LR(1)表的文法G稱為一個LR(1)文法。LR(1)文法滿足下面兩個條件1 如果一個項目集里有項目A uxv, a，x是終結符，那就不會有項目B u,x 2 項目集里所有歸約項目的向前搜索符不相交，即不能同時含有項目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)項目集及轉換函數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*結論:1.不能用SLR(1)方法解決，但能用LR(1)，因 此LR(1)比SLR(1)分析能力強；2.每個SLR(1)文法都是LR(1)文法的，一個文法的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)項目集和轉換函數bGSGS：(0)S(0)S S (1) S (1)S S BB (2)B BB (2)BaB (3)B aB (3)B b b判斷文法是否為判斷文法是否為LR(1)LR(1)文法和文法和LALR(1)LALR(1)文法。文法。合并同心集同心集I3和I6、I4和I7 、I8和I9 ，得到新項目集I36、I47和I89合并同心集同心集I3和I6 I4和I7 I8和I9 ，得到新項目集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