1、第七章分析程序及其自動構(gòu)造,7.1LR分析概述 7.2LR (0) 分析 7.3SLR(1) 分析 7.6使用二義文法,7.1分析概述,LR（K） L 從左至右掃描輸入符號串 R 構(gòu)造一個最右推導(dǎo)的逆過程 K 向右順序查看輸入串的K個符號 LR（0）:在分析過程中不需向右查看輸入符號。 四種分析器： LR(0) SLR(1) LR(1) LALR(1) SLR(1)和LALR(1)分別是LR(0)和LR(1)的一種改進。 分析器模型和分析算法,分析器模型,例： GS: S a A c B e 1 A b 2 A Ab 3 B d 4,LR分析算法,置ip指向輸入串w的第一個符號 令S為棧頂狀態(tài)

2、 a是ip指向的符號 重復(fù) begin if ACTIONS,a=Sj then begin PUSH j,a(進棧) ip 前進(指向下一輸入符號) end else if ACTIONS,a=rj (第j條產(chǎn)生式為A),分析程序,then begin pop | 項 令當前棧頂狀態(tài)為S push GOTOS,A和A(進棧) end else if ACTIONs,a=acc then return (成功） else error end.重復(fù) 其中，Sj=GOTOSi,X表示當棧頂狀態(tài)為Si遇到當前文法符號為X時應(yīng)轉(zhuǎn)向狀態(tài)Sj,分析程序,例: GS: S a A c B e 1 A b 2

3、 A Ab 3 B d 4 w=abbcde#,Step states. Syms. The rest of inputaction goto 1 0 # abbcde# s2 2 02 #a bbcde# s4 3 024 #ab bcde# r2 goto(2,A) 4 023 #aA s6 5 0236 #aAb cde# r3 6 023 #aA s5 7 0235 #aAc de# s8 8 02358 #aAcd e# r4 9 02357 #aAcB s9 10 023579 #aAcBe # r1 11 01 #S acc,文法GS：(1) S aAcBe(2) A b(3)

4、A Ab(4) B d,a,b,b,c,d,e,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進,2） #a bbcde# 移進,4） #aA bcde# 移進,6） #aA cde# 移進,7） #aAc de# 移進,9） #aAcB e# 移進,11） #S # 接受,符號串a(chǎn)bbcde是否是GS的子,對輸入串a(chǎn)bbcde#的移進-規(guī)約分析過程,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de#

5、移進 0235 S8,9） #aAcB e# 移進 02357 S9,11） #S # 接受 01 acc,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移進，將狀態(tài)i和輸入符進棧 ri:歸約，用第i個產(chǎn)生式歸約，同時狀態(tài)棧與符號棧退出相

6、應(yīng)個符號，并把GOTO表相應(yīng)狀態(tài)和第i個產(chǎn)生式的左部非終結(jié)符入棧。,構(gòu)造LR分析表的預(yù)備知識,文法 對于一個上下文無關(guān)文法, 如果能夠構(gòu)造一張 LR 分析表, 使得它的每一個入口均是唯一的（Sj,rj,acc,空白），則稱該上下文無關(guān)是LR 文法 活前綴 規(guī)范句型的前綴，若不含句柄以后的任何符號，則稱它為該規(guī)范句型的活前綴。,LR(0) 分析,LR(0)文法 能力最弱，理論上最重要 存在FA 識別活前綴 識別活前綴的DFA如何構(gòu)造 （LR(0)項目集規(guī)范族的構(gòu)造） LR(0)分析表的構(gòu)造,分析,活前綴 G=(Vn,Vt,P,S),若有S A , 是的前綴,則稱是文法G的活前綴. 其中S是對原文

7、法擴充(SS)增加的非終結(jié)符.,R,LR分析需要構(gòu)造識別活前綴的有窮自動機 我們可以文法的終結(jié)符和非終結(jié)符都看成有窮自動機的輸入符號，每次把一個符號進?？闯梢炎R別過了該符號，同時狀態(tài)進行轉(zhuǎn)換，當識別到可歸前綴時，相當于在棧中形成句柄，認為達到了識別句柄的終態(tài)。,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 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 S9,11） #S # 接受 01 acc

8、,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,對輸入串a(chǎn)bbcde#的LR分析過程,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A

9、,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,對輸入串a(chǎn)bbcde#的LR分析過程,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,

10、c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,對輸入串a(chǎn)bbcde#的LR分析過程,3

11、） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)

12、棧,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,

13、b,A,b,c,B,e,d,8,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B

14、,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 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 S9,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,

15、6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 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 S9,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe #

16、歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 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 S9,11） #S # 接受 01 acc,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5）

17、#aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,構(gòu)造識別文法活前綴DFA的三種方法,一、根據(jù)形式定義求出活前綴的正規(guī)表達式，然后由此正規(guī)表達式構(gòu)造NFA再確定化為DFA 二、求出文法的所有項目，按一定規(guī)則構(gòu)造識別活前綴的NFA再確定化為DFA 三、使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GOTO(I,X)構(gòu)造文法G的LR(0)的項目集規(guī)范族，

18、再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識別活前綴的DFA,構(gòu)造LR(0)項目集規(guī)范族,LR(0)項目集規(guī)范族(構(gòu)成識別一個文法的活前綴的DFA的狀態(tài)的全體) 。 LR（0）項目或配置（ item or configuration）. -在右端某一位置有圓點的G的產(chǎn)生式 A xyz A.xyz Ax.yz Axy.z Axyz. 如：SaAd S.aAd Sa .Ad SaA .d SaAd .,活前綴與句柄的關(guān)系：,GS: 若S = A = r是的前綴，則 稱r是G的一個活前綴 1.活前綴已含有句柄的全部符號，表明產(chǎn)生式A的 右部已出現(xiàn)在棧頂 2.活前綴只含句柄的一部分符號表明A12的右部子串

19、1已出現(xiàn)在棧頂，期待從輸入串中看到2推出的符號 3. 活前綴不含有句柄的任何符號，此時期望A的右部所推出的符號串,R,活前綴,與句柄 ,與 LR(0)項目,為刻劃這種分析過程中的文法G的每一個產(chǎn)生式的右部符號已有多大一部分被識別（出現(xiàn)在棧頂）的情況，分別用標有圓點的產(chǎn)生式來指示位置。 A刻劃產(chǎn)生式A的 右部已出現(xiàn)在棧頂 A12 刻劃A12的右部子串1已出現(xiàn)在棧頂，期待從輸入串中看到2推出的符號 A 刻劃沒有句柄的任何符號在棧頂，此時期望A的右部所推出的符號串 對于A的LR(0)項目只有A,LR(0)項目,根據(jù)圓點所在的位置和圓點后是終結(jié)符還是非終結(jié)符或為空把項目分為以下幾種： 移進項目，形如

20、A a a是終結(jié)符, , V* 以下同 待約項目，形如 A B 歸約項目，形如 A 接受項目，形如 S S A的LR(0)項目只有A 是歸約項目 作用？,LR(0)項目集規(guī)范族,定義1：如果存在一個規(guī)范推導(dǎo) S ,我們說項目 對活前綴 是有效的。 定義2：若項目 對活前綴 是有效的，且 是一個產(chǎn)生式，則項目 對 也是有效的。 定義3：文法G的某個活前綴r的所有有效項目組成的集合成為r的有效項目集，文法G的所有有效項目集組成的集合稱為G的LR（0）項目集規(guī)范族。,LR（0） 項目集的閉包LOSURE,若當前處于A XYZ刻劃的情況，期望移進 First(Y)中的某些符號，假如有產(chǎn)生式 Y u |

21、 w . 那么Y u和Y w這兩個項目便是刻劃期望移進 First(Y)中的某些符號的情況. A XYZ Y u Y w 這三個項目對應(yīng)移進歸約分析的同一個狀態(tài),這三個項目構(gòu)成一個項目集, 對應(yīng)每個項目集，分析表將有一個狀態(tài).,構(gòu)造識別活前綴的DFA,用閉包函數(shù)LOSURE求DFA一個狀態(tài)的項目集 若文法G已拓廣為G，而S為文法G的開始符號，拓廣后增加產(chǎn)生式SS。如果I是G的一個項目集，定義和構(gòu)造I的閉包CLOSURE（I）如下： 1、I的項目均在CLOSURE（I）中。 2、若 屬于CLOSURE（I）。則每一形如 的項目也屬于CLOSURE（I）。 3、重復(fù)2直到不出現(xiàn)新的項目為止。即CL

22、OSURE（I）不再擴大。 轉(zhuǎn)換函數(shù) GO (I,x)= CLOSURE(J) ; 其中， I:項目集，x: 文法符號， J=任何形如A x. 的項目|A .x I,LR(0)項目集規(guī)范族,計算LR（0）項目集規(guī)范族 C=I0 ，I1 , . In 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;,例：文法G: （0）SE (1) EaA (2) EbB (3) AcA (

23、4) Ad (5) BcB (7) Bd LR(0) 項目集規(guī)范族（識別G的活前綴的DFA)： I0: SE I1: SE I2: EaA EaA A.cA EbB Ad,I3: EbB I4: Ac.A I5: BcB BcB AcA BcB Bd A .d Bd I6 : EaA I7 : EbB I8: AcA I9: BcB I10: Ad I11: BcB DFA,LR(0)分析表的構(gòu)造,假定C=I0, I1,，In，令每個項目集Ik的下標k為分析器的一個狀態(tài)，因此，G 的LR(0)分析表含有狀態(tài)0，1，n。令那個含有項目SS的Ik的下標k為初態(tài)。ACTION和GOTO可按如下方法構(gòu)

24、造： 若項目Aa屬于Ik且GO (Ik, a)= Ij, a為終結(jié)符，則置ACTIONk, a為“把狀態(tài)j和符號a移進?！保営洖椤皊j”; 若項目A屬于Ik, 那么，對任何終結(jié)符a, 置ACTIONk, a為“用產(chǎn)生式A進行規(guī)約”，簡記為“rj”;其中，假定A為文法G的第j個產(chǎn)生式； 若項目SS屬于Ik, 則置ACTIONk, #為“接受”，簡記為“acc”; 若GO (Ik, A)= Ij, A為非終結(jié)符，則置GOTO(k, A)=j; 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯標志”。,按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它

25、為文法G的一張LR(0)表。具有LR(0)表的文法G稱為一個LR（0）文法。 LR(0)文法是無二義的。,例：（0）SS (1)SrD (2) DD,i (3) Di LR（0）項目 1. SS 2. SS 3. SrD 4. SrD 5. SrD 6. DD,i 7. DD,i 8. DD,i 9. DD,i 10. Di 11. Di,例：（0）SS (1)SrD (2) DD,i (3) Di LR（0）項目集規(guī)范族 I0: SS I3: Sr D Sr D DD，i I1: SS I4: Di I2: SrD I5: DD，i DD ，i I6: DD，i Di 其中I3中含有移進/歸約沖突 文法不是LR(0)的，如何解決？,SLR(1)技術(shù),若 LR(0) 項目集規(guī)范族中有項目集IK含 移進/歸約、 歸約/歸約沖突： IK : .A .b , P .