分析表的構(gòu)造(編譯原理)

1、LR（0）分析表的構(gòu)造分析表的構(gòu)造u步驟步驟一：一： 構(gòu)造識別文法活前綴的確定有窮自動機（構(gòu)造識別文法活前綴的確定有窮自動機（DFADFA）u步驟步驟二二： 根據(jù)根據(jù)DFADFA構(gòu)造相應(yīng)的構(gòu)造相應(yīng)的LRLR（0 0）分析表）分析表識別活前綴的確定的有窮自動機識別活前綴的確定的有窮自動機 方法方法1 1：根據(jù)形式定義求出活前綴的正規(guī)表達式，然后由此正根據(jù)形式定義求出活前綴的正規(guī)表達式，然后由此正規(guī)表達式構(gòu)造規(guī)表達式構(gòu)造NFANFA再確定化為再確定化為DFADFA，a，ab，a，aA，aAb， a，aA，aAc，aAcd， a， aA，aAc，aAcB，aAcBe，S 對于一個適用的高級語言的文法

2、，用方法對于一個適用的高級語言的文法，用方法1 1構(gòu)造識別活前綴的構(gòu)造識別活前綴的有限自動機從理論的角度講是很嚴格的，實現(xiàn)起來卻是很復(fù)有限自動機從理論的角度講是很嚴格的，實現(xiàn)起來卻是很復(fù)雜的。雜的。識別活前綴的確定的有窮自動機識別活前綴的確定的有窮自動機 方法方法2 2：求出文法的所有求出文法的所有LRLR（0 0）項目，按一定規(guī)則構(gòu)造識別）項目，按一定規(guī)則構(gòu)造識別活前綴的活前綴的NFANFA再確定化為再確定化為DFADFA例如，文法例如，文法G：E aA|bBA cA| d B cB| d 步驟一：步驟一：用增廣文法表示成用增廣文法表示成文法文法G：SEE aA|bBA cA| d B cB

3、| d 文法文法G的項目有：的項目有：1.SE2.SE 3.E aA4.E aA5.E aA6. A cA7. A cA8. A cA9. A d10. A d 11. E bB12. E bB13. E bB14. B cB15. B cB16. B cB17. B d18. B d 1*1313 2 21313 5 51313 8 813131010131313131313181813131616步驟步驟三：三：初態(tài)（初始項目）初態(tài)（初始項目）句子識別句子識別態(tài)（接受項目）態(tài)（接受項目）句柄識別句柄識別態(tài)（規(guī)約項目）態(tài)（規(guī)約項目）文法文法G的項目有：的項目有：1.SE2.SE 3.E aA

4、4.E aA5.E aA6. A cA7. A cA8. A cA9. A d10. A d 11. E bB12. E bB13. E bB14. B cB15. B cB16. B cB17. B d18. B d 1*1313 2 21313 5 51313 8 813131010131313131313181813131616E34aA67cA9d1112bB1415cB17d步驟四：步驟四：找源自同一產(chǎn)找源自同一產(chǎn)生式的項目，生式的項目，添加狀態(tài)間的添加狀態(tài)間的連線連線文法文法G的項目有：的項目有：1.SE2.SE 3.E aA4.E aA5.E aA6. A cA7. A cA8.

5、 A cA9. A d10. A d 11. E bB12. E bB13. E bB14. B cB15. B cB16. B cB17. B d18. B d 1*1313 2 21313 5 51313 8 813131010131313131313181813131616E34aA67cA9d1112bB1415cB17d步驟四：步驟四：1.1.找待約項目找待約項目2.2.與以其后的非終與以其后的非終結(jié)符作為產(chǎn)生式頭結(jié)符作為產(chǎn)生式頭的圓點在最左的項的圓點在最左的項目，用空弧與之連目，用空弧與之連接接T0= 1, 3, 11T1= 2T2= 4, 6, 9T3= 12, 14, 17T4

6、= 6, 7, 9T5= 14, 15, 17T6= 5 T7= 13 T8= 8 T9= 16 T10= 10 T11= 18狀態(tài)狀態(tài)輸入符號輸入符號abcdABET0T2T3 T1T1 T2 T4T10T6 T3 T7T5T11 T4 T4T10T8 T5 T5T11 T9 T6 T7 T8 T9 T10 T11 步驟五：步驟五：運用運用子集法將其確子集法將其確定化定化01313 1 1E 確定化的確定化的DFA1313 6 61313 7 71313 9 913131010131311111313 8 84235abcdAcAdbdcdBc*E2abcdAcAdbdcdBcSEE aAE

7、 bBA cAA cAA dE aAA cAA dSE E bBB cBB dB cBB cBB dA cAA d E aAE bBB d B cB 步驟六：步驟六：把每個子把每個子集所含狀集所含狀態(tài)集對應(yīng)態(tài)集對應(yīng)的項目寫的項目寫在新的狀在新的狀態(tài)中，得態(tài)中，得到識別活到識別活前綴的有前綴的有限自動機限自動機DFA* 使用方法使用方法2 2構(gòu)造識別活前綴的構(gòu)造識別活前綴的DFADFA，需要列出拓廣文法的所有，需要列出拓廣文法的所有項目，按規(guī)定規(guī)則構(gòu)造其項目，按規(guī)定規(guī)則構(gòu)造其NFANFA，然后再確定化為，然后再確定化為DFADFA，這樣做，這樣做確定化的工作量較大。確定化的工作量較大。E2abc

8、dAcAdbdcdBcSEE aAE bBA cAA cAA dE aAA cAA dSE E bBB cBB dB cBB cBB dA cAA d E aAE bBB d B cB* 分析分析使用方法使用方法2 2構(gòu)造識別構(gòu)造識別活前綴的活前綴的DFADFA中每個狀態(tài)中每個狀態(tài)中項目集的構(gòu)成，發(fā)現(xiàn)中項目集的構(gòu)成，發(fā)現(xiàn)如下規(guī)律：如下規(guī)律： 如果狀態(tài)中包含形如如果狀態(tài)中包含形如X X A A 的項目，則形的項目，則形如如A Ar r的項目也在此狀態(tài)的項目也在此狀態(tài)中。中。 因此可以用因此可以用閉包函數(shù)閉包函數(shù)（CLOSURECLOSURE）來求來求DFADFA的的項目集。項目集。方法方法3 3

9、：把增廣文法的第一個項目把增廣文法的第一個項目SS S S作為初態(tài)集的作為初態(tài)集的內(nèi)核項內(nèi)核項，通過求內(nèi)核項的，通過求內(nèi)核項的閉包函數(shù)閉包函數(shù)直接求出直接求出LRLR（0 0）項目）項目集規(guī)范族，再由集規(guī)范族，再由轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到建立狀態(tài)之間的連接關(guān)系得到識別活前綴的識別活前綴的DFADFA第一步：找出第一步：找出內(nèi)核項內(nèi)核項第二步：第二步：通過通過閉包函數(shù)閉包函數(shù)求得求得DFA的項目集的項目集規(guī)范族規(guī)范族第三步：求出各項目集的第三步：求出各項目集的GOTO函數(shù)函數(shù)第四步：第四步：畫出確定的有窮自動機畫出確定的有窮自動機例如，文法例如，文法G：E aA|bBA cA|

10、 d B cB| d 用增廣文法用增廣文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d 文法文法G的內(nèi)核項有：的內(nèi)核項有：SESE E aAE aA A cA A cA A d E bBE bBB cBB cBB d 內(nèi)核項：內(nèi)核項：包括初始項包括初始項SS S S以及圓點不在最左端的所有項以及圓點不在最左端的所有項項目集的閉包項目集的閉包 文法文法G G已表示為增廣文法已表示為增廣文法GG，如果，如果I I是文法是文法GG的一個項目集，的一個項目集，定義和構(gòu)造定義和構(gòu)造I I的閉包的閉包CLOSURECLOSURE（I I）如下：）如下：1 1）一開始，將）一開始

11、，將I I中的各個項加入到中的各個項加入到CLOSURECLOSURE（I I）中）中2 2）若）若項目項目X X A 屬于屬于CLOSURECLOSURE（I I），那么形如，那么形如A Ar的項的項目也要加入到目也要加入到CLOSURECLOSURE（I I）中。）中。3 3）不斷應(yīng)用規(guī)則）不斷應(yīng)用規(guī)則2 2），直到?jīng)]有新的項目可以加入到），直到?jīng)]有新的項目可以加入到CLOSURECLOSURE（I I）中為止。）中為止。例如，文法例如，文法G：E aA|bBA cA| d B cB| d 用增廣文法用增廣文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d 文法文

12、法G的內(nèi)核項有：的內(nèi)核項有：SESE E aAE aA A cA A cA A d E bBE bBB cBB cBB d 例如，文法例如，文法G：E aA|bBA cA| d B cB| d 用增廣文法用增廣文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d SE的閉包為：的閉包為：SEE aAE bBE aA的閉包為：的閉包為：E aAA cAA d 例如，文法例如，文法G：E aA|bBA cA| d B cB| d 用增廣文法用增廣文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d A cA的閉包為：的閉包為：A cA A cAA d

13、 B cB的閉包為：的閉包為：B cB B cBB d E bB的閉包為：的閉包為：E bB B cBB d 例如，文法例如，文法G：E aA|bBA cA| d B cB| d 用增廣文法用增廣文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d I0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 通過閉包函數(shù)求得通過閉包函數(shù)求得DFA的項目集的項目集規(guī)范族規(guī)范族I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I

14、11： B d 轉(zhuǎn)換函數(shù)（轉(zhuǎn)換函數(shù)（GOTOGOTO函數(shù)）函數(shù)） 轉(zhuǎn)換函數(shù)的定義如下：轉(zhuǎn)換函數(shù)的定義如下：GOTO(I,X)=closure(J) GOTO(I,X)=closure(J) 其中：其中：I I是是G G的一個的一個LR(0)LR(0)項目集項目集X X為一個文法符號為一個文法符號, X, X VVT TVVN N J=J=當當AAXX I I時時, ,任意形如任意形如AXAX的項目的項目 即即GOTO (I,X)GOTO (I,X)為為I I中所有形如中所有形如AAXX的項目所對應(yīng)的項的項目所對應(yīng)的項目目AXAX的集合的閉包的集合的閉包I0： SE E aA E bBI4： A

15、 cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通過閉包函數(shù)求得通過閉包函數(shù)求得DFA的項目集的項目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d I0=S E, EaA, EbB1）GOTO GOTO (I0, E)= closure(J)=closure(SE)= SE = I12）GOTO GOTO (I0, a)= closure(J)=closure(EaA) = EaA, AcA, Ad )=I23）GOTO GOTO (I0

16、, b)= closure(J)=closure (E b.B) =E b B, B cB, B d= I3I0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通過閉包函數(shù)求得通過閉包函數(shù)求得DFA的項目集的項目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d I2=E aA， A cA，A d1） GOTO GOTO(I2, A)= closure(J)=closure(E aA ) = E aA =

17、 I62） GOTOGOTO(I2, c)= closure(J)=closure(A c A ) =A c A ，A cA，A d =I43） GOTO GOTO(I2, d)= closure(J)=closure (A d ) =A d = I10I0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通過閉包函數(shù)求得通過閉包函數(shù)求得DFA的項目集的項目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d

18、 I3=E bB，B cB，B d1）GOTO GOTO (I3, B)= closure(J)=closure(E bB ) = E bB = I72） GOTO GOTO (I3, c)= closure(J)=closure(B c B ) =B c B ，B cB，B d =I53）GOTO GOTO (I3, d)= closure(J)=closure (B d ) =B d = I11I0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通過閉

19、包函數(shù)求得通過閉包函數(shù)求得DFA的項目集的項目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d I4=A cA，A cA， A d1）GOTO GOTO (I4, A)= closure(J)=closure(A cA ) = A cA = I82） GOTO GOTO (I4, c)= closure(J)=closure(A c A ) =A cA，A cA，A d =I43）GOTO GOTO (I4, d)= closure(J)=closure (A d ) =A d = I10I0： SE E aA E bBI4： A cA A

20、 cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通過閉包函數(shù)求得通過閉包函數(shù)求得DFA的項目集的項目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d I5=B cB，B cB，B d1）GOTO GOTO (I5, B)= closure(J)=closure(B cB ) = B cB = I92） GOTO GOTO (I5, c)= closure(J)=closure(B c B) =B cB，B cB，B d =I53）GOTO GOTO

21、(I5, d)= closure(J)=closure (B d ) =B d = I11 由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識別活前綴的得到識別活前綴的DFAI0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通過閉包函數(shù)求得通過閉包函數(shù)求得DFA的項目集的項目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d GOTOGOTO(I0, E)= I1 GOTO GOTO

22、 (I0, a)=I2 GOTO GOTO (I0, b)= I3GOTOGOTO(I2, A)= I6 GOTO GOTO (I2, c)=I4 GOTO GOTO (I2, d)= I10GOTOGOTO(I3, B)= I7 GOTO GOTO (I3, c)= I5 GOTO GOTO (I3, d)= I11GOTOGOTO(I4, A)= I8 GOTO GOTO (I4, c)= I4 GOTO GOTO (I4, d)= I10GOTOGOTO(I5, B)= I9 GOTO GOTO (I5, c)= I5 GOTO GOTO (I5, d)= I11EabcdAcAdBdc

23、dBcI0I4I2I1I3I5I8I10I6I7I11I9 得到識別活前綴的得到識別活前綴的DFAE2abcdAcAdBdcdBcSEE aAE bBA cAA cAA dE aAA cAA dSE E bBB cBB dB cBB cBB dA cAA d E aAE bBB d B cB 得到識別活前綴的得到識別活前綴的DFA*識別活前綴的確定的有窮自動機 方法方法1 1：根據(jù)形式定義求出活前綴的正規(guī)表達式，然后由此正根據(jù)形式定義求出活前綴的正規(guī)表達式，然后由此正規(guī)表達式構(gòu)造規(guī)表達式構(gòu)造NFANFA再確定化為再確定化為DFADFA 方法方法2 2：求出文法的所有求出文法的所有LRLR（0

24、0）項目，按一定規(guī)則構(gòu)造識別）項目，按一定規(guī)則構(gòu)造識別活前綴的活前綴的NFANFA再確定化為再確定化為DFADFA 方法方法3 3：把增廣文法的第一個項目把增廣文法的第一個項目SS S S作為初態(tài)集的核，作為初態(tài)集的核，通過求核的閉包函數(shù)直接求出通過求核的閉包函數(shù)直接求出LRLR（0 0）項目集規(guī)范族，再由轉(zhuǎn)）項目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識別活前綴的換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識別活前綴的DFADFA 方法方法1 1較嚴格確切，方法較嚴格確切，方法2 2和方法和方法3 3較直觀較直觀改進的方法：改進的方法：方法方法2+2+方法方法3 3思路：思路：u把增廣文法的第一個把增廣文法的第一個項目項目SS S S作為初態(tài)作為初態(tài)集的核集的核u對每讀入對每讀入一個符號后一個符號后產(chǎn)生的新的項目集進產(chǎn)生的新的項目集進行閉包運算行閉包運算u直至該項目集內(nèi)的所直至該項目集內(nèi)的所有項目均為規(guī)約項