LR分析程序及其自動(dòng)構(gòu)造

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

2、 a是ip指向的符號(hào) 重復(fù) begin if ACTIONS,a=Sj then begin PUSH j,a(進(jìn)棧) ip 前進(jìn)(指向下一輸入符號(hào)) end else if ACTIONS,a=rj (第j條產(chǎn)生式為A),分析程序,then begin pop | 項(xiàng) 令當(dāng)前棧頂狀態(tài)為S push GOTOS,A和A(進(jìn)棧) end else if ACTIONs,a=acc then return (成功） else error end.重復(fù) 其中，Sj=GOTOSi,X表示當(dāng)棧頂狀態(tài)為Si遇到當(dāng)前文法符號(hào)為X時(shí)應(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,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn),2） #a bbcde# 移進(jìn),4） #aA bcde# 移進(jìn),6） #aA cde# 移進(jìn),7） #aAc de# 移進(jìn),9） #aAcB e# 移進(jìn),11） #S # 接受,符號(hào)串a(chǎn)bbcde是否是GS的子,對(duì)輸入串a(chǎn)bbcde#的移進(jìn)-規(guī)約分析過程,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de#

5、移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,11） #S # 接受 01 acc,對(duì)輸入串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:移進(jìn)，將狀態(tài)i和輸入符進(jìn)棧 ri:歸約，用第i個(gè)產(chǎn)生式歸約，同時(shí)狀態(tài)棧與符號(hào)棧退出相

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

7、法擴(kuò)充(SS)增加的非終結(jié)符.,R,LR分析需要構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī) 我們可以文法的終結(jié)符和非終結(jié)符都看成有窮自動(dòng)機(jī)的輸入符號(hào)，每次把一個(gè)符號(hào)進(jìn)棧看成已識(shí)別過了該符號(hào)，同時(shí)狀態(tài)進(jìn)行轉(zhuǎn)換，當(dāng)識(shí)別到可歸前綴時(shí)，相當(dāng)于在棧中形成句柄，認(rèn)為達(dá)到了識(shí)別句柄的終態(tài)。,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,11） #S # 接受 01 acc

8、,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,對(duì)輸入串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,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,對(duì)輸入串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,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,對(duì)輸入串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,*,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,11） #S # 接受 01 acc,對(duì)輸入串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)造識(shí)別文法活前綴DFA的三種方法,一、根據(jù)形式定義求出活前綴的正規(guī)表達(dá)式，然后由此正規(guī)表達(dá)式構(gòu)造NFA再確定化為DFA 二、求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)別活前綴的NFA再確定化為DFA 三、使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GOTO(I,X)構(gòu)造文法G的LR(0)的項(xiàng)目集規(guī)范族，

18、再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識(shí)別活前綴的DFA,構(gòu)造LR(0)項(xiàng)目集規(guī)范族,LR(0)項(xiàng)目集規(guī)范族(構(gòu)成識(shí)別一個(gè)文法的活前綴的DFA的狀態(tài)的全體) 。 LR（0）項(xiàng)目或配置（ item or configuration）. -在右端某一位置有圓點(diǎn)的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的一個(gè)活前綴 1.活前綴已含有句柄的全部符號(hào)，表明產(chǎn)生式A的 右部已出現(xiàn)在棧頂 2.活前綴只含句柄的一部分符號(hào)表明A12的右部子串

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

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

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

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

23、4) Ad (5) BcB (7) Bd LR(0) 項(xiàng)目集規(guī)范族（識(shí)別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，令每個(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和GOTO可按如下方法構(gòu)

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

25、為文法G的一張LR(0)表。具有LR(0)表的文法G稱為一個(gè)LR（0）文法。 LR(0)文法是無二義的。,例：（0）SS (1)SrD (2) DD,i (3) Di LR（0）項(xiàng)目 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）項(xiàng)目集規(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中含有移進(jìn)/歸約沖突 文法不是LR(0)的，如何解決？,SLR(1)技術(shù),若 LR(0) 項(xiàng)目集規(guī)范族中有項(xiàng)目集IK含 移進(jìn)/歸約、 歸約/歸約沖突： IK : .A .b , P .