項目集族和LR(0)分析表的構(gòu)造.ppt

第五章 語法分析,5.1 自下而上分析基本問題 5.2 算符優(yōu)先分析 5.3 LR分析 5.4 YACC,5.3 LR分析,5.3.1 LR分析器 5.3.2 LR(0)項目集族LR(0)分析表的構(gòu)造 5.3.3 SLR分析表的構(gòu)造 5.3.4 規(guī)范LR分析表的構(gòu)造 5.3.5 LALR分析表的構(gòu)造 5.3.6 二義文法的應(yīng)用,5.3.2 LR(0)項目集族LR(0)分析表的構(gòu)造,一、前綴、活前綴 p104 二、構(gòu)造識別文法所有活前綴的DFA p104 三、LR(0)項目集規(guī)范族的構(gòu)造 p106 四、有效項目 p108 五、LR(0)分析表的構(gòu)造 p109,一、前綴、活前綴,前綴 : 符號串的頭 活前綴 : 規(guī)范句型的一個前綴, 這種前綴不包含句柄之后的任何符號. *可歸前綴: 包含句柄的活前綴.,規(guī)范 推導(dǎo) 序列,S =aAcBe =aAcde =aAbcde =abbcde,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe,活前綴,可歸前綴 ab , aAb, aAcd , aAcBe,補(bǔ)充例: 找出句型 #abbcde# 的所有活前綴,G:SaAcBe 1 Ab 2 AAb 3 Bd 4,當(dāng)棧頂出現(xiàn)可歸前綴即可歸約,棧里的文法符號與剩余符號串一起構(gòu)成了規(guī)范句型 棧里的文法符號構(gòu)成活前綴,S =aAcBe =aAcde =aAbcde =abbcde,規(guī)范 推導(dǎo) 序列,#abbcde#的規(guī)范歸約過程,識別句型#abbcde#所有活前綴的DFA,確定化,最小化,G:SaAcBe 1 Ab 2 AAb 3 Bd 4,利用DFA進(jìn)行 移近-歸約分析 (見黑板),G:SaAcBe 1 Ab 2 AAb 3 Bd 4,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,r,acc,S,S,S,S,S,S,GOTO,ACTION,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,1,1,1,1,1,1,LR分析表,DFA的矩陣表示,一個LR分析器實質(zhì)上是一個DFA,小結(jié),識別文法所有活前綴的DFA,LR分析表,LR分析,二、構(gòu)造識別文法所有活前綴的DFA,1. LR(0)項目 2. 構(gòu)造識別文法所有活前綴的DFA 3. LR(0)項目的分類,求出文法所有的活前綴 根據(jù)產(chǎn)生式得出可能出現(xiàn)在棧中的符號串,1. LR(0)項目,在文法G中每個產(chǎn)生式的右部適當(dāng)位置添加一個圓點構(gòu)成項目. 對空產(chǎn)生式A , 僅有項目A,例: 產(chǎn)生式 A XYZ 對應(yīng)的項目有 AXYZ AXYZ AXYZ AXYZ,一個產(chǎn)生式可對應(yīng)的項目個數(shù)是它的右部符號長度加1 每個項目的含義與圓點的位置有關(guān),補(bǔ)充例,對應(yīng)的項目: (1)SaAd (2)S aAd (3)S aAd (4)S aAd (5)Abc (6)A bc (7)A bc,借助項目構(gòu)造識別文法活前綴的DFA,G: S aAd Abc,2. 構(gòu)造識別文法所有活前綴的DFA,1). 文法的每個項目都為NFA的一個狀態(tài) 2). 確定狀態(tài)之間的轉(zhuǎn)換關(guān)系 3). 確定化最小化,例5.8 p105,G: SE EaA|bB AcA|d BcB|d,更正,1SE 2SE 11. EbB 3EaA 12. EbB 4EaA 13. EbB 5EaA 14. BcB 6AcA 15. BcB 7AcA 16. BcB 8AcA 17. Bd 9Ad 18. Bd 10. Ad,文法的項目:,1). 文法的每個項目都為NFA的一個狀態(tài),2). 確定狀態(tài)之間的轉(zhuǎn)換關(guān)系,Xi,XX1X2Xi-1XiXn,XX1X2XiXi+1Xn,XA,A,狀態(tài)i,狀態(tài)j,出自同一產(chǎn)生式,項目1 為初態(tài),P106 NFA,1SE 2SE 3EaA 4EaA 5EaA 6AcA 7AcA 8AcA 9Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd,每個狀態(tài)都為活前綴識別態(tài) 句柄識別態(tài)(可歸前綴識別態(tài)): 圓點在最后的項目,句子識別態(tài),p106,識別一個文法活前綴的DFA,3).確定化 最小化,每個狀態(tài)是一個項目集, 稱作LR(0)項目集 整個狀態(tài)集稱為LR(0)項目集規(guī)范族,3. LR(0)項目的分類,移進(jìn)項目: Aa 分析時把a(bǔ)移進(jìn)符號棧 待約項目: AB 用產(chǎn)生式A的右部歸約時,首先要將B的產(chǎn)生式右部歸約為B, 對A的右部才能繼續(xù)進(jìn)行分析 歸約項目: A 表明一個產(chǎn)生式的右部已分析完，句柄已形成可以歸約 接受項目: SS 表明已分析成功,三、LR(0)項目集規(guī)范族的構(gòu)造,構(gòu)造識別文法活前綴DFA的三種方法 * 求出活前綴的正規(guī)表達(dá)式，然后由此正規(guī)表達(dá)式構(gòu)造NFA, 再確定化為DFA。 求出文法的所有項目，按一定規(guī)則構(gòu)造識別活前綴的NFA, 再確定化為DFA。 通過閉包函數(shù)和轉(zhuǎn)換函數(shù)，直接求出LR(0)項目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識別活前綴的DFA。,1.拓廣文法 2.項目集I的閉包函數(shù) CLOSURE(I) 3.狀態(tài)轉(zhuǎn)換函數(shù) GO(I, X) 4.構(gòu)造文法的LR(0)項目集規(guī)范族,1.拓廣文法,原文法G的開始符號為S, 在G中加SS 后得新的文法G， 則稱 G為原文法G的拓廣文法。 使文法的開始符號不出現(xiàn)在任何產(chǎn)生式右部，當(dāng)棧頂出現(xiàn)S,則分析完成 。 注:即使原開始符號S不出現(xiàn)在任何產(chǎn)生式右部,為了統(tǒng)一起見也要增加該產(chǎn)生式。,2.項目集I的閉包函數(shù) CLOSURE(I),a) I 的項目均在 CLOSURE(I) 中。 b) 若AB屬于CLOSURE(I), 則每一形如 B的項目也屬于CLOSURE(I) c) 重復(fù)b)直到CLOSURE(I)不再擴(kuò)大。,NFA : 狀態(tài)集合I的-閉包 -closure(I),AB,B,補(bǔ)充例,I SE CLOSURE(I) = SE, EaA, EbB ,1SE 2SE 3EaA 4EaA 5EaA 6AcA 7AcA 8AcA 9Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd,1,3,11,3.狀態(tài)轉(zhuǎn)換函數(shù) GO(I, X),GO(I, X) = CLOSURE(J) , X(VNVT) , J = AX| AXI ,X,AX,AX,若狀態(tài)I識別活前綴,則狀態(tài)J識別活前綴X,狀態(tài)I,狀態(tài)J,NFA : 狀態(tài)集合I的a弧轉(zhuǎn)換,補(bǔ)充例,I SE , EaA , EbB GO(I, a) = CLOSURE( EaA ) = EaA , AcA, Ad ,1SE 2SE 3EaA 4EaA 5EaA 6AcA 7AcA 8AcA 9Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd,1,3,11,4,6,9,4.構(gòu)造文法的LR(0)項目集規(guī)范族 C=I0,I1,In,核: 圓點不在產(chǎn)生式右部最左邊的項目稱為核 a) 置項目SS為初態(tài)集的核，然后對核求閉包，CLOSURE(SS）得到初態(tài)的項目集。 b) 對初態(tài)集或其它所構(gòu)造的項目集應(yīng)用轉(zhuǎn)換函數(shù)GO(I，X)=CLOSURE(J)求出新狀態(tài)J的項目集。 c) 重復(fù)b)直到不出現(xiàn)新的項目為止。,算法,Procedure itemsets(G) Begin C:= CLOSURE(SS ) Repeat for C中的每一個I 和每一個X do if GO(I, X)非空且不屬于C then 把GO(I, X)放入C中 until C不再增大 end,p107,初態(tài)的項目集,應(yīng)用狀態(tài)轉(zhuǎn)換函數(shù)得到新的項目集,G: SE EaA|bB AcA|d BcB|d,I0: SE E aA E bB,I8: BcB B cB B d,I3: EbB B cB B d,I2:EaA A cA A d,I1: S E,I5:AcA A cA A d,I10:Ac A,I6:A d,I4:EaA,I7:EbB,I9:B d,I11:BcB,b,E,a,c,c,c,c,d,d,d,d,A,A,B,B,識別文法所有活前綴的DFA LR(0)項目集規(guī)范族 I0,I1, I11,四、有效項目 *,如果存在規(guī)范推導(dǎo) 則項目A12 對活前綴 1 是有效的。 如果2 ，應(yīng)該移進(jìn) 如果2 = ，應(yīng)該用產(chǎn)生式A1歸約,G: SE EaA|bB AcA|d BcB|d,項目集I5對活前綴bc有效,考慮如下規(guī)范推導(dǎo) (1) S E bB bcB (2) S E bB bcB bccB (3) S E bB bcB bcd,圖5.7 p106,識別文法 活前綴的DFA,從初態(tài)出發(fā),經(jīng)讀出活前綴后,而到達(dá)的項目集稱為活前綴的有效項目集,LR分析理論的一條基本定理 p108,在任何時候，分析棧中的活前綴X1X2.Xm的有效項目集正是棧頂狀態(tài)Sm所代表的那個集合。,同一個項目可能對好幾個活前綴都有效,G: SE EaA|bB AcA|d BcB|d,同一個活前綴，可能存在若干個項目對它都是有效的，而且告訴我們應(yīng)做的事情各不相同，相互沖突。 這種沖突通過向前多看幾個輸入符號, 或許能夠獲得解決。,移進(jìn)-歸約沖突 一個項目集中移進(jìn)和歸約項目同時存在： Aa B 歸約-歸約沖突 一個項目集中歸約和歸約項目同時存在: A B,五、LR(0)分析表的構(gòu)造,LR(0)文法,假若一個文法G的拓廣文法G的活前綴識別自動機(jī)中的每個狀態(tài)(項目集)不存在下述情況 既含移進(jìn)項目又含歸約項目 或者含有多個歸約項目 則稱G是一個LR(0)文法。 LR(0)文法規(guī)范族的每個項目集不包含任何沖突項目(移進(jìn)-歸約沖突、歸約-歸約沖突) 。,LR(0)分析表的構(gòu)造,假設(shè)已構(gòu)造出LR(0)項目集規(guī)范族為: C=I0,I1, , In 令包含SS 項目的集合Ik的下標(biāo)k為分析器的初始狀態(tài)。,a) 若項目Aa屬于Ik ,且 GO(Ik, a) = Ij 則置 ACTIONk, a 為Sj b) 若項目A 屬于Ik，則對任何終結(jié)符a 和# 置ACTIONk, a 和ACTIONk, # 為“rj”, j為在文法G中某產(chǎn)生式 A的序號。 c) 若項目 SS 屬于Ik , 則置ACTIONk, #為“acc”/ 接受 d) 若GO(Ik, A)Ij，則置GOTOk,A 為“j“ e) 凡不能用上述方法填入的元素,均填上“報錯標(biāo)志” / “空白”,I0: SE E aA E bB,I8: BcB B cB B d,I3: EbB B cB B d,I2:EaA A cA A d,I1: S