《編譯原理實(shí)踐及應(yīng)用》第4章LR分析方法

1、LR分析方法分析方法第四章（第四章（3） 本節(jié)要求本節(jié)要求 主要內(nèi)容主要內(nèi)容： LR分析方法及其相關(guān)概念，分析方法及其相關(guān)概念，語法分析器的自動(dòng)生成，各種語法分析中語法分析器的自動(dòng)生成，各種語法分析中的錯(cuò)誤處理的錯(cuò)誤處理 重點(diǎn)掌握：重點(diǎn)掌握：LR分析方法與分析過程，活分析方法與分析過程，活前綴、前綴、LR(0)項(xiàng)目、項(xiàng)目、Closure 和和 go函數(shù)的函數(shù)的定義，項(xiàng)目集規(guī)范族及識(shí)別活前綴的有窮定義，項(xiàng)目集規(guī)范族及識(shí)別活前綴的有窮自動(dòng)機(jī)的構(gòu)造，自動(dòng)機(jī)的構(gòu)造，LR(0)分析表的構(gòu)造，分析表的構(gòu)造，SLR文法及其分析表的構(gòu)造。文法及其分析表的構(gòu)造。LRLR分析概述分析概述 LR分析法分析法：L從左

2、向右掃描輸入串，R構(gòu)造最右推導(dǎo)的逆過程 大多數(shù)用上下文無關(guān)文法描述的高級(jí)語言的語法成分可以用LR分析器來識(shí)別。 LR分析：采用移進(jìn)-歸約分析，嚴(yán)格的規(guī)范歸約。 LR分析分析根據(jù)當(dāng)前分析棧中的符號(hào)串和向右順序查看輸入串的K(K0)個(gè)符號(hào)就可以唯一確定分析的動(dòng)作是移進(jìn)還是歸約。 向前查看0個(gè)符號(hào)，就是LR(0)分析方法，向前查看1個(gè)符號(hào)，就是LR(1)方法。LRLR分析的優(yōu)缺點(diǎn)分析的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 比其他“移進(jìn)-歸約”方法使用廣泛，識(shí)別率高 能用LL(1)分析法分析的所有文法都能使用LR方法來進(jìn)行分析。 LR分析法在掃描輸入串時(shí)就能發(fā)現(xiàn)其中的任何錯(cuò)誤，并能準(zhǔn)確地指出出錯(cuò)位置。 缺點(diǎn)： 手工構(gòu)造分析

3、表工作量太大。必須使用自動(dòng)生成器。 自下而上分析的關(guān)鍵問題是如何確定可歸約串。LR方法是逐步歸約逐步歸約棧頂?shù)目蓺w約串來進(jìn)行語法分析。 在算符優(yōu)先分析中，通過算符的優(yōu)先關(guān)系得到句柄“最左素短語”，LR方法中通過識(shí)別活前綴活前綴而求得。 LR分析方法的基本思想基本思想是：在規(guī)范歸約過程中，一方面記住已移進(jìn)和歸約出的整個(gè)符號(hào)串(歷史)，另一方面又根據(jù)所用產(chǎn)生式推測未來可能碰到的輸入符號(hào)(對(duì)未來的展望)。 當(dāng)某一符號(hào)串類似于句柄出現(xiàn)在棧頂時(shí)，需要根據(jù)已記載的“歷史”、“展望”和“現(xiàn)實(shí)”的輸入符號(hào)三方面的內(nèi)容來決定棧頂?shù)姆?hào)串是否構(gòu)成了真正的句柄，是否需要?dú)w約。 一個(gè)LR分析器的組成見下圖。1 1、L

4、RLR分析方法的邏輯結(jié)構(gòu)分析方法的邏輯結(jié)構(gòu) 一個(gè)一個(gè)LR分析器由分析器由3個(gè)部分組成：個(gè)部分組成： LR分析程序，又分析程序，又稱稱總控程序總控程序。所有的。所有的LR分析器都是相同的。分析器都是相同的。 分析表分析表(分析函數(shù)分析函數(shù))，不同的文法分析表不同，同一個(gè)文法采用的，不同的文法分析表不同，同一個(gè)文法采用的LR分分析器不同時(shí)，分析表也不同，分析表又可分為析器不同時(shí)，分析表也不同，分析表又可分為動(dòng)作表動(dòng)作表(ACTION)和和狀狀態(tài)轉(zhuǎn)換態(tài)轉(zhuǎn)換(GOTO)表表兩個(gè)部分，它們都可用二維數(shù)組表示。兩個(gè)部分，它們都可用二維數(shù)組表示。 分析棧分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出

5、棧。，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。狀態(tài)棧：(S0,#)為預(yù)先放到棧中的初始狀態(tài)和符號(hào)。文法符號(hào)：X1X2Xm是目前已移進(jìn)并歸約出的句型部分。其實(shí)它是多余的，已經(jīng)概括到狀態(tài)里。分析器分析器實(shí)際上是一個(gè)帶有先進(jìn)后出棧的確定的有窮自動(dòng)機(jī)。將“歷史”和“展望”綜合成“狀態(tài)”，分析棧用來存放狀態(tài)，狀態(tài)概括了從分析開始直到某一歸約階段的全部歷史和展望資料，不必象算符優(yōu)先分析法中要翻閱棧中的內(nèi)容才能決定是否要進(jìn)行歸約。只需根據(jù)棧頂狀態(tài)和輸入符號(hào)就可以唯一決定下一個(gè)動(dòng)作。 總控程序根據(jù)分析表的內(nèi)容來決定其下一步的總控程序根據(jù)分析表的內(nèi)容來決定其下一步的處理動(dòng)作，分析表是根據(jù)具體的文法按某

6、種規(guī)處理動(dòng)作，分析表是根據(jù)具體的文法按某種規(guī)則構(gòu)造出來的。則構(gòu)造出來的。 LR方法：方法：根據(jù)具體文法的分析表對(duì)輸入串進(jìn)根據(jù)具體文法的分析表對(duì)輸入串進(jìn)行分析處理。行分析處理。 LR分析過程：分析過程：在總控程序的控制下，從左到在總控程序的控制下，從左到右掃描輸入符號(hào)串，根據(jù)分析棧中的狀態(tài)和當(dāng)右掃描輸入符號(hào)串，根據(jù)分析棧中的狀態(tài)和當(dāng)前輸入符號(hào)，按分析表中的內(nèi)容完成相應(yīng)的分前輸入符號(hào)，按分析表中的內(nèi)容完成相應(yīng)的分析工作。析工作。2. 2. 分析表的組成：分析表的組成： 符號(hào)符號(hào)狀態(tài)狀態(tài)a1a2atS0actionS0 , a1 actionS0 , a2actionS0 , atS1actionS

7、1 , a1 actionS1 , a2actionS1 , atSnactionSn , a1 actionSn , a2actionSn , at 表中actionSi,aj，指出如果當(dāng)前棧頂為狀態(tài)Si，輸入符號(hào)為aj時(shí)應(yīng)執(zhí)行的動(dòng)作。其動(dòng)作有四種可能，分別為：移進(jìn)(S)、歸約(r)、接受(acc)、出錯(cuò)(error)。(1) (1) 分析動(dòng)作表分析動(dòng)作表ActionAction是一個(gè)二維數(shù)組是一個(gè)二維數(shù)組 符號(hào)符號(hào)狀態(tài)狀態(tài)x1x2xtS0gotoS0 , x1gotoS0 , x2gotoS0 , xtS1gotoS1 ,x1gotoS1 , x2gotoS1 , xtSngotoSn ,

8、 x1gotoSn , x2gotoSn , xt 表中g(shù)otoSi,xj指出狀態(tài)為Si，遇到Xj時(shí)應(yīng)轉(zhuǎn)到的下一狀態(tài)。顯然：分析表定義了一個(gè)以文法符號(hào)為字母表的顯然：分析表定義了一個(gè)以文法符號(hào)為字母表的DFA (2) 狀態(tài)轉(zhuǎn)換表狀態(tài)轉(zhuǎn)換表goto 也是一個(gè)二維數(shù)組也是一個(gè)二維數(shù)組狀狀態(tài)態(tài)ActionGoToi+*()#E TF0 0S5S41231 1S6acc2 2r2S7r2r23 3r4r4r4r44 4S5S48235 5r6r6r6r66 6S5S4r1937 7S5S4108 8S6S119 9r1S7r1r11010r3r3r3r31111r5r5r5r5ri表示按第i個(gè)產(chǎn)生式進(jìn)

9、行歸約Si表示把當(dāng)前輸入符號(hào)移進(jìn)棧，第i個(gè)狀態(tài)進(jìn)狀態(tài)棧。i表示轉(zhuǎn)第i個(gè)狀態(tài)，即第i個(gè)狀態(tài)進(jìn)狀態(tài)棧?？瞻妆硎痉治鰟?dòng)作出錯(cuò)例：例：LR的的Action和和GoTo表表 (1) E E+T (2) E T (3) T T*F (4) T F (5) F (F) (6) F i產(chǎn)生式產(chǎn)生式的序號(hào)的序號(hào)設(shè)文法為設(shè)文法為GL： 用三元式用三元式: (狀態(tài)棧，符號(hào)棧，輸入符號(hào)串狀態(tài)棧，符號(hào)棧，輸入符號(hào)串) 表示分析過程中狀態(tài)棧，符號(hào)棧，輸入符號(hào)串的變化表示分析過程中狀態(tài)棧，符號(hào)棧，輸入符號(hào)串的變化 初始時(shí)，將狀態(tài)初始時(shí)，將狀態(tài)S0和和#進(jìn)分析棧。三元式為：進(jìn)分析棧。三元式為：(S0, # , a1a2an#

10、) 任一時(shí)刻的三元式為：任一時(shí)刻的三元式為：(S0S1Sm, #X1X2Xm, aiai+1an#) 分析器的下一步動(dòng)作是由棧頂狀態(tài)分析器的下一步動(dòng)作是由棧頂狀態(tài)Sm和當(dāng)前面臨的和當(dāng)前面臨的輸入符號(hào)輸入符號(hào)ai唯一確定的。唯一確定的。3 3、LRLR分析過程：分析過程：移進(jìn)：當(dāng)前輸入符號(hào)ai移進(jìn)符號(hào)棧，將action表中指出的狀態(tài)S進(jìn)狀態(tài)棧。 (S0S1SmS, # X1X2Xmai, ai+1an#) 根據(jù)Sm和ai查action表, actionSm, ai有4種情況： 出錯(cuò)：報(bào)告出錯(cuò)信息。三元式的變化過程終止。 接受：分析成功，終止分析。三元式不再變化。 歸約：若產(chǎn)生式A的右端長度為r，

11、則兩個(gè)棧頂?shù)膔個(gè)元素同時(shí)出棧，A進(jìn)符號(hào)棧; 再根據(jù)Sm-r和A查goto表，S=gotoSm-r, A進(jìn)狀態(tài)棧。三元式變?yōu)椋?(S0S1 Sm-r S, # X1X2Xm-rA, aiai+1an #)為了介紹為了介紹LR分析過程，直分析過程，直接給出該文法的分析表，接給出該文法的分析表，以后再介紹如何生成以后再介紹如何生成狀狀態(tài)態(tài)ACTIONGoToi+*()#E TF0 0S5S41231 1S6acc2 2r2S7r2r23 3r4r4r4r44 4S5S48235 5r6r6r6r66 6S5S4r1937 7S5S4108 8S6S119 9r1S7r1r11010r3r3r3r31

12、111r5r5r5r5例：例：LR的具體分析的具體分析過程：過程： (1) E E+T (2) E T (3) T T*F (4) T F (5) F (F) (6) F i設(shè)文法為設(shè)文法為GL：根據(jù)上述分析表，對(duì)輸入串根據(jù)上述分析表，對(duì)輸入串 i * i + i 的分析過程如下：的分析過程如下：序號(hào)序號(hào)狀態(tài)棧狀態(tài)棧符號(hào)棧符號(hào)棧產(chǎn)生式產(chǎn)生式輸入串輸入串說明說明10#i*i+i# 0和和#進(jìn)棧進(jìn)棧205#i*i+i# i和和S5進(jìn)棧進(jìn)棧303#FFi*i+i# i和和S5退棧退棧, F和和S3進(jìn)棧進(jìn)棧402#TTF*i+i# F和和S3退棧退棧, T和和S2進(jìn)棧進(jìn)棧5027#T*i+i# *和和

13、S7進(jìn)棧進(jìn)棧60275#T*i+i# i和和S5進(jìn)棧進(jìn)棧702710#T*FFi+i# i和和S5退棧退棧, F和和S10進(jìn)棧進(jìn)棧802#TTT*F+i# F*T和和S10,7,2退棧退棧, T和和S2進(jìn)棧進(jìn)棧901#EET+i# T和和S2退棧退棧, E和和S1進(jìn)棧進(jìn)棧10016#E+i# +和和S6進(jìn)棧進(jìn)棧110165#E+i# i和和S5進(jìn)棧進(jìn)棧120163#E+FFi# i和和S5退棧退棧, F和和S3進(jìn)棧進(jìn)棧130169#E+TTF# F和和S3退棧退棧, T和和S9進(jìn)棧進(jìn)棧1401#EE E+T# T+E和和S9,6,1退棧退棧, E和和S1進(jìn)棧進(jìn)棧 LR文法：對(duì)一個(gè)文法，如果能夠

14、構(gòu)造一個(gè)分析表，且它的每個(gè)入口均是唯一的 如何構(gòu)造LR分析表？1）基本概念）基本概念 字的字的前綴：前綴：指該字的任意首部。 活前綴：活前綴：規(guī)范句型的一個(gè)前綴，不含句柄之后的任何符號(hào)。在它之后增添一些終結(jié)符號(hào)后，就成為規(guī)范句型。即： 對(duì)于文法G，若 S，Vt* ，稱為活前綴。 在LR分析的過程中，假定輸入串是一個(gè)句子，任何時(shí)候符號(hào)棧里的文法符號(hào)都構(gòu)成活前綴，配上輸入串的剩余部分，就成為規(guī)范句型。 構(gòu)造一個(gè)有窮自動(dòng)機(jī)來識(shí)別文法G的所有活前綴，這樣就可以自動(dòng)生成LR分析表。4 4、LR(0)LR(0)項(xiàng)目集族項(xiàng)目集族* LR(0)項(xiàng)目：項(xiàng)目：在文法G中每個(gè)產(chǎn)生式的右部適當(dāng)位置添加一個(gè)圓點(diǎn)構(gòu)成項(xiàng)目

15、。 例如：產(chǎn)生式 SXYZ 對(duì)應(yīng)有4個(gè)項(xiàng)目： 0 SXYZ 1 SXYZ2 SXYZ 3 SXYZ 產(chǎn)生式產(chǎn)生式A 只對(duì)應(yīng)一個(gè)項(xiàng)目：只對(duì)應(yīng)一個(gè)項(xiàng)目： A 項(xiàng)目項(xiàng)目指明了在分析過程的某時(shí)刻，已看到的產(chǎn)生式部分 項(xiàng)目集：項(xiàng)目集：若干個(gè)項(xiàng)目組成的集合。 例如：對(duì)于上述產(chǎn)生式的4個(gè)項(xiàng)目即構(gòu)成一個(gè)項(xiàng)目集。練練 習(xí)習(xí) 求文法：S aS | bS |a 的LR(0)項(xiàng)目集S aSS bS S aS aS S a S S aS S bS S b S S bS S a S a 后繼符號(hào)有多種，后繼符號(hào)有多種，據(jù)此將項(xiàng)目分為多種：據(jù)此將項(xiàng)目分為多種：移進(jìn)項(xiàng)目：移進(jìn)項(xiàng)目：后繼符號(hào)為終結(jié)符： A a待約項(xiàng)目：待約項(xiàng)目

16、：后繼符號(hào)為非終結(jié)符：A B歸約項(xiàng)目：歸約項(xiàng)目：后繼符號(hào)為空：即圓點(diǎn)在最右邊A (1)接受項(xiàng)目：接受項(xiàng)目：歸約項(xiàng)目的左邊是文法開始符號(hào)S后繼符號(hào)后繼符號(hào)：在項(xiàng)目中緊跟在符號(hào)“”后面的符號(hào)稱為該項(xiàng)目的后繼符號(hào)。 表示下一時(shí)刻遇到的符號(hào)。后繼符號(hào)集：后繼符號(hào)集：項(xiàng)目集中各項(xiàng)目的后繼符號(hào)所組成的集合稱為后繼符號(hào)集。 項(xiàng)目集 EET,Fi的后繼符號(hào)集為,i 寫出文法的所有項(xiàng)目，每個(gè)項(xiàng)目是一個(gè)狀態(tài) 規(guī)定項(xiàng)目1為NFA的唯一初態(tài) 若狀態(tài)i和狀態(tài)j出自同一產(chǎn)生式，而且狀態(tài)j的圓點(diǎn)只落后于狀態(tài)i一個(gè)位置: 若i的圓點(diǎn)后是a，從i到j(luò)畫一條弧，標(biāo)記為a 若i的圓點(diǎn)后是A，則連兩種?。?1)從狀態(tài)i畫弧到所有的A

17、的狀態(tài)。(2)從狀態(tài)i到j(luò)畫弧，標(biāo)記為A 歸約項(xiàng)目表示結(jié)束狀態(tài)，用雙圈表示2）構(gòu)造）構(gòu)造NFA的方法：的方法： 例：求文法對(duì)應(yīng)的NFAS EE aA | bBA cA | dB cB | d1. S E 2. S E 3. E aA 4. E aA 5. E aA 6. A cA 7. A c A 8. A cA 9. A d 10. A d11. E bB 12. E bB 13. E bB 14. B cB 15. B cB 16. B cB 17. B d 18. B d1) 該文法的項(xiàng)目有：該文法的項(xiàng)目有：識(shí)別活前綴的識(shí)別活前綴的NFA2)畫出NFA LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族

18、的定義：構(gòu)成識(shí)別一個(gè)文法活前綴的DFA的項(xiàng)目集的全體 構(gòu)造方法有兩種： 1)先構(gòu)造NFA，使用第三章的子集法將NFA確定化 2) 直接使用閉包和狀態(tài)轉(zhuǎn)換函數(shù)進(jìn)行計(jì)算5 5、LR(0)LR(0)項(xiàng)目集規(guī)范族的構(gòu)造：項(xiàng)目集規(guī)范族的構(gòu)造：1)1)使用第使用第三三章章的子集法將的子集法將NFANFA確定化，得到確定化，得到一個(gè)識(shí)別該文一個(gè)識(shí)別該文法的確定的有法的確定的有窮自動(dòng)機(jī)，其窮自動(dòng)機(jī)，其每個(gè)狀態(tài)是項(xiàng)每個(gè)狀態(tài)是項(xiàng)目集目集識(shí)別活前綴的識(shí)別活前綴的DFA 一個(gè)項(xiàng)目集I的閉包Closure(I)的計(jì)算：的計(jì)算：(1) I中的任何項(xiàng)目都中的任何項(xiàng)目都 Closure(I)(2) 若若A BClosure(

19、I), 且且B VN ，則對(duì)任何，則對(duì)任何關(guān)于關(guān)于B的產(chǎn)生式：的產(chǎn)生式： B r Closure(I)，r為任意為任意符號(hào)串符號(hào)串(3) 重復(fù)重復(fù)(2)直到直到Closure(I)不再增加為止。不再增加為止。2) LR(0)2) LR(0)項(xiàng)目集規(guī)范族的構(gòu)造：項(xiàng)目集規(guī)范族的構(gòu)造：注意注意：(2)的條件表示所有項(xiàng)目集中右邊為B的狀態(tài)與B 的狀態(tài)是等價(jià)的，因此，只要B 進(jìn)入Closure(I)中, 則所有B的圓點(diǎn)在左邊的項(xiàng)目B 都應(yīng)進(jìn)入同一個(gè)Closure(I)中。例：對(duì)于文法4.6有下列項(xiàng)目：1. S E 2. S E 3. E aA 4. E aA 5. E aA 6. A cA 7. A c

20、 A 8. A cA 9. A d 10. A d11. E bB 12. E bB 13. E bB 14. B cB 15. B cB 16. B cB 17. B d 18. B d若項(xiàng)目集I = E aA , 則Closure(I)=E aA , A cA , A d 若項(xiàng)目集I = B cB , 求Closure(I)=？Closure(I) = B cB， B cB， B d 狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)的計(jì)算：的計(jì)算： GO(I,X) = Closure(J) I是一個(gè)項(xiàng)目集，是一個(gè)項(xiàng)目集，X是一個(gè)文法符號(hào)是一個(gè)文法符號(hào)其中其中J = 任何形如任何形如A X 的項(xiàng)目的項(xiàng)目| AX

21、I GO函數(shù)實(shí)際就是檢查I中的每一個(gè)后繼 符號(hào)為X的項(xiàng)目，將這個(gè)圓點(diǎn)向后移動(dòng)一個(gè)位置，得到項(xiàng)目集J，再對(duì)項(xiàng)目集J求閉包。例：對(duì)于上面的例題文法4.6有下列項(xiàng)目1. S E 2. S E 3. E aA 4. E aA 5. E aA 6. A cA 7. A c A 8. A cA 9. A d 10. A d11. E bB 12. E bB 13. E bB 14. B cB 15. B cB 16. B cB 17. B d 18. B d已知已知 I=E aA , A cA , A d 求求go(I,A)和和 go(I,c) go(I,A) = E aA go(I,c) = AcA,

22、A cA , A d 已知已知 I= B cB，B cB，B d 求求go(I,B)和和 go(I,c)go(I,B) = B cB go(I,c) = EcB, B cB , B d 1. 拓廣文法：在原文法GS上增加一個(gè)產(chǎn)生式S S，這是為了得到唯一的接受狀態(tài)S S 2. 設(shè)項(xiàng)目集規(guī)范族C只包含第一個(gè)狀態(tài)S S的閉包，即C = Closure(S S) 3. 利用GO函數(shù)對(duì)C中的每個(gè)項(xiàng)目集和每個(gè)符號(hào)X計(jì)算其下一狀態(tài)，并將下一狀態(tài)GO(I,X)加入到C中，直到C中狀態(tài)數(shù)不再增加 C即為文法G的LR(0) 項(xiàng)目集規(guī)范族LR(0)LR(0)項(xiàng)目集規(guī)范族的構(gòu)造算法：項(xiàng)目集規(guī)范族的構(gòu)造算法：前述的例

23、子中，是已經(jīng)拓廣了的文法1. S E 2. S E 3. E aA 4. E aA 5. E aA 6. A cA 7. A c A 8. A cA 9. A d 10. A d11. E bB 12. E bB 13. E bB 14. B cB 15. B cB 16. B cB 17. B d 18. B d初始時(shí)，設(shè)置 C = Closure( S E ) , 是一個(gè)狀態(tài),即 C = SE, E aA , E bB 再根據(jù)C中的每個(gè)狀態(tài)的go函數(shù)，求出更多的狀態(tài)，直到狀態(tài)數(shù)不再增多為止例：設(shè)文法例：設(shè)文法G為：為：E aA bB A cAd B cBd求該文法的求該文法的LR(0)分析

24、表。分析表。(0) S E (1) E aA (2) E bB (3) A cA (4) A d (5) B cB (6) B d第步第步：拓廣文法，：拓廣文法，并對(duì)產(chǎn)生式給予序號(hào)：并對(duì)產(chǎn)生式給予序號(hào)：第步第步：寫出拓廣后的：寫出拓廣后的文法的項(xiàng)目集：文法的項(xiàng)目集： 1. S E 2. S E 3. E aA 4. E a A 5. E aA 6. E bB 7. E b B 8. E bB 9. A cA 10. A c A 11. A cA 12. A d13. A d 14. B cB 15. B c B 16. B cB 17. B d18. B d 第第3步步：從：從SE開開始始求項(xiàng)

25、目集規(guī)范族求項(xiàng)目集規(guī)范族由 S0 = S E知：知：Closure(S0) = S E,E aA, E bB 由此初值CClosure(S0)再根據(jù)GO函數(shù)計(jì)算后繼狀態(tài)由此表明顯看出：由此表明顯看出：Go(狀態(tài)，后繼符號(hào)狀態(tài)，后繼符號(hào))后繼狀態(tài)后繼狀態(tài)當(dāng)不出現(xiàn)新的狀態(tài)時(shí)，得到當(dāng)不出現(xiàn)新的狀態(tài)時(shí)，得到LR(0)LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族LR(0)LR(0)項(xiàng)目項(xiàng)目集規(guī)范族也集規(guī)范族也可以用表格可以用表格的形式表示的形式表示狀態(tài)狀態(tài)項(xiàng)目集項(xiàng)目集后繼符號(hào)后繼符號(hào)后繼狀態(tài)后繼狀態(tài)S0 S E E aA E bB EabS1S2S3S1 S E #接受態(tài)接受態(tài)S2 Ea A A cA A d A

26、cdS6S4S10S3 EbB B cB B d BcdS7S5S11S4 A c A A cA A d AcdS8S4S10S5 Bc B B cB B dBcdS9S5S11S6 EaA #歸約歸約S7 EbB #歸約歸約S8 A cA #歸約歸約S9 BcB #歸約歸約S10 Ad #歸約歸約S11 Bd #歸約歸約算法描述：算法描述：PROCEDURE itemsets(G);C := CLOSURE( S S ) ;do for C中的每個(gè)項(xiàng)目集I和每個(gè)文法符號(hào)X do if GO(I,X)非空且不屬于C 把GO(I,X) 加入C中; 在I和GO(I，X)之間畫標(biāo)記為X的弧;whil

27、e( C 的元素再增加)有效項(xiàng)目有效項(xiàng)目：項(xiàng)目A1.2對(duì)活前綴=1是有效的條件是：存在規(guī)范推導(dǎo)S Aw12w 根據(jù)定義可知，若歸約項(xiàng)目A1 對(duì)活前綴1是有效的，則應(yīng)把符號(hào)串1歸約為A，即把活前綴1 變?yōu)锳 若移進(jìn)項(xiàng)目A1 2對(duì)活前綴1是有效的，則知，句柄尚為形成，下一步動(dòng)作應(yīng)是移進(jìn) 一個(gè)活前綴的有效項(xiàng)目集有效項(xiàng)目集就是從構(gòu)造的DFA的初態(tài)出發(fā)，經(jīng)讀取后而能到達(dá)的那個(gè)項(xiàng)目集(狀態(tài))。ie.分析棧中的活前綴X1X2Xm的有效項(xiàng)目集是棧頂狀態(tài)Sm所代表的狀態(tài)* 若文法G = ( Vt, Vn, S, )，則識(shí)別識(shí)別G的項(xiàng)目集的項(xiàng)目集規(guī)范族的自動(dòng)機(jī)規(guī)范族的自動(dòng)機(jī)為DFA M = ( =VtVn，Q=G

28、的LR(0)項(xiàng)目集規(guī)范族, q0=closure(S S)，F(xiàn)=所有含歸約項(xiàng)目的有效項(xiàng)目集組成的集合，=go ) LR(0)文法：文法：若一個(gè)文法若一個(gè)文法G的拓廣文法的拓廣文法G的活前的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)不存在下述情況：綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)不存在下述情況： 既含移進(jìn)又含歸約的項(xiàng)目；既含移進(jìn)又含歸約的項(xiàng)目； 含有多個(gè)歸約項(xiàng)目。含有多個(gè)歸約項(xiàng)目。 對(duì)對(duì)LR(0)文法可以直接從它的項(xiàng)目集規(guī)范族文法可以直接從它的項(xiàng)目集規(guī)范族C和和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)構(gòu)造出活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)構(gòu)造出LR分分析表析表6 6、LR(0)LR(0)分析表的構(gòu)造分析表的構(gòu)造 設(shè)有文法設(shè)有文法

29、G，則從，則從LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族構(gòu)造構(gòu)造分析表分析表的的方法方法為：為： 對(duì)于對(duì)于A XIk，GO (Ik,X)=Ij 若若X Vt，則置，則置actionk,X=Sj ,即把即把(j,a)移進(jìn)棧移進(jìn)棧 若若X Vn，則置，則置gotoIk,X=j 對(duì)于對(duì)于A Ik ，則對(duì)所有的，則對(duì)所有的x Vt和和# ，均置，均置actionk,x=rj (設(shè)設(shè)A 是第是第j個(gè)產(chǎn)生式個(gè)產(chǎn)生式)，即用，即用A 歸約歸約 若若S S Ik，則置，則置actionk,#=acc，即接受即接受 其他均置出錯(cuò)。其他均置出錯(cuò)。狀狀態(tài)態(tài)ACTIONGOTOabcd#E A BS0S2S31S1accS2

30、S4S106S3S5S117S4S4S108S5S5S119S6r1r1r1r1r1S7r2r2r2r2r2S8r3r3r3r3r3S9r5r5r5r5r5S10r4r4r4r4r4S11r6r6r6r6r6求前述例題求前述例題中的中的LR(0)分析表分析表(0) S E (1) E aA (2) E bB (3) A cA (4) A d (5) B cB (6) B d練練 習(xí)習(xí) 給定文法：S aS | bS |c (1) 構(gòu)造的LR(0)項(xiàng)目集規(guī)范族， (2) 構(gòu)造識(shí)別該文法所產(chǎn)生的活前綴的DFA (3) 該文法是否是LR(0)的，若是，構(gòu)造LR(0)分析表(0)S S(1)S aS(2

31、)S bS (3)S c一一.拓廣文法拓廣文法1. S S 2. S S 3. S aS 4. S a S 5. S aS6. S bS 7. S b S 8. SbS9. S c 10. S c 二二.寫出所有的項(xiàng)目寫出所有的項(xiàng)目三三.求項(xiàng)目集規(guī)范族求項(xiàng)目集規(guī)范族狀狀態(tài)態(tài)項(xiàng)目集項(xiàng)目集后繼符號(hào)后繼符號(hào) 后繼狀態(tài)后繼狀態(tài)S0 S S S aS E bS S c SabcS1S2S5S3S1 S S #接受態(tài)接受態(tài)S2 Sa S S aS S bS S c SabcS4S2S5S3S3 S c #歸約歸約S4 S aS #歸約歸約S5 Sb S S aS S bS S c SabcS6S2S5S3

32、S6 EbS #歸約歸約項(xiàng)目集規(guī)范族也可以項(xiàng)目集規(guī)范族也可以用表格表示用表格表示025SSScccabab1463每個(gè)項(xiàng)目集中的各個(gè)項(xiàng)目不沖突,則是LR(0)文法。四四.構(gòu)造構(gòu)造LR(0)分析表分析表狀狀態(tài)態(tài)ACTIONGOTOabc#SS0S2S5S31S1accS2S2S5S34S3r3r3r3r3S4r1r1r1r1S5S2S5S36S6r2r2r2r2(0)S S(1)S aS(2)S bS (3)S c非非LR(0)LR(0)文法文法 項(xiàng)目集規(guī)范族中I1，I2，I9中存在移進(jìn)-歸約沖突，不能構(gòu)造LR(0)分析表考查文法 ：（0）SE（1）EE+T（2）ET（3）TT*F（4）TF（5

33、）F(E)（6）Fi 只有當(dāng)一個(gè)文法G是LR(0)文法，即G的每一個(gè)狀態(tài)不出現(xiàn)沖突時(shí)，才能構(gòu)造出LR(0)分析表。 由于大多數(shù)實(shí)用的程序設(shè)計(jì)語言的文法不能滿足LR(0) 文法的條件，因此使用向前查看一個(gè)符號(hào)的辦法來處理沖突。 只對(duì)有沖突的狀態(tài)向前查看一個(gè)符號(hào)，即查看follow集，以確定做哪個(gè)動(dòng)作，這種分析方法為簡單的LR分析法，用SLR表示。 如果每個(gè)項(xiàng)目都附上k個(gè)終結(jié)符號(hào)，表示要對(duì)它進(jìn)行歸約時(shí)，后續(xù)的k個(gè)輸入符號(hào)與這k個(gè)符號(hào)相同時(shí)，才能對(duì)棧頂進(jìn)行歸約。這就是LR(k)分析。SLRSLR分析方法分析方法SLR(1)沖突的解決辦法 若一個(gè)項(xiàng)目集中同時(shí)含有移進(jìn)和歸約項(xiàng)目，出現(xiàn)了沖突。 解決沖突的

34、條件：移進(jìn)符號(hào)集合b, Follow(A), follow(B)兩兩不相交。 解決的辦法：當(dāng)面臨的輸入符號(hào)為a： 當(dāng)a 移進(jìn)符合 b，則應(yīng)移進(jìn)； 當(dāng)a follow(A)，則用產(chǎn)生式A 進(jìn)行歸約； 當(dāng)a follow(B)，則用產(chǎn)生式B進(jìn)行歸約。I = XbA A B (0) SE (1) E E+T (2) E T (3) T T*F (4) T F (5) F (F) (6) F i移進(jìn)-歸約沖突沖突的解決方法： 在I1中，F(xiàn)ollow(S)=#，#+，因此I1中的沖突可解決。 解決方法：當(dāng)且僅當(dāng)遇到句子的結(jié)束符“#”號(hào)時(shí)， 使用SE進(jìn)行歸約，句子被接受；當(dāng)遇到“+”時(shí)，移進(jìn)；當(dāng)面臨其他輸

35、入符號(hào)時(shí)，出錯(cuò)。SEE E+T 在I2中，F(xiàn)ollow(E)=#,),+Follow(E)*=+,),#*，所以I2的沖突可以解決 解決方法：如果當(dāng)前輸入符號(hào)為#, ), +時(shí)，就使用ET進(jìn)行歸約；如果當(dāng)前輸入符號(hào)為*時(shí)，就移進(jìn)；當(dāng)面臨其他輸入符號(hào)時(shí)，出錯(cuò)。ETTT*F 在I9中，F(xiàn)ollow(E)*=+,),#*，因此I9中的沖突可解決 解決方法：面臨的輸入符為+，)或#時(shí)，用產(chǎn)生式EE+T進(jìn)行歸約；當(dāng)面臨輸入符為*時(shí)，移進(jìn)；面臨其它符號(hào)則報(bào)錯(cuò)。 EE+TTT*F SLR(1)SLR(1)分析表的構(gòu)造算法分析表的構(gòu)造算法 設(shè)有文法設(shè)有文法G，則，則SLR(1)分析表的分析表的構(gòu)造方法構(gòu)造方法

36、為：為： 對(duì)于對(duì)于A XIk，GOTO(Ik,X)=Ij 若若X Vt，則置，則置actionk,X=Sj ,即把即把(j,a)移進(jìn)棧移進(jìn)棧 若若X Vn，則置，則置gotoIk,X=j 對(duì)于對(duì)于A Ik ，則對(duì)所有的則對(duì)所有的x，x follow(A) ，則置則置actionk,x=rj (設(shè)設(shè)A 是第是第j個(gè)產(chǎn)生式個(gè)產(chǎn)生式)，即用，即用A 歸約歸約 若若S S Ik，則置，則置actionk,#=acc，即接受即接受 其他均置出錯(cuò)。其他均置出錯(cuò)。如果分析表的每個(gè)入口不含多重定義，則稱為SLR表，文法G稱為SLR(1)文法。例：下述文法例：下述文法的的SLRSLR分析表分析表狀狀態(tài)態(tài)ACTI

37、ONGoToi+*()#E TF0 0S5S41231 1S6acc2 2r2S7r2r23 3r4r4r4r44 4S5S48235 5r6r6r6r66 6S5S4r1937 7S5S4108 8S6S119 9r1S7r1r11010r3r3r3r31111r5r5r5r5 (0) SE (1) E E+T (2) E T (3) T T*F (4) T F (5) F (F) (6) F iSLR不能解決的問題 拓廣文法G為：（0）SS（1）SaAd（2）SbAc（3）Saec（4）Sbed（5）Ae 得到項(xiàng)目集規(guī)范族項(xiàng)目集I5和I7中的沖突，不能用SLR(1)方法解決。Follow(

38、A)=c，d LR(1)分析 LR(0)項(xiàng)目項(xiàng)目：為A,a1a2ak，A是一個(gè)LR(0)項(xiàng)目，aiVT*。 a1a2ak稱為它的向前搜索字符串向前搜索字符串 。 一個(gè)項(xiàng)目集的閉包閉包Closure(I)：（1）將I中的所有項(xiàng)目都加入Closure(I)。（2）若項(xiàng)目AB,aClosure(I)，B是一個(gè)產(chǎn)生式，那么對(duì)于任何bFirst(a)，如果B,b原來不在Closure(I)中，則把它加進(jìn)去。重復(fù)執(zhí)行該過程，直到Closure(I)不再增大為止。 I是一個(gè)項(xiàng)目集，X是一個(gè)文法符號(hào)，則轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)GO(I,X)定義為：GO(I,X) = Closure(J)，J=任何形如AX,a的項(xiàng)目

39、| AX,aI。 構(gòu)造構(gòu)造LR(1)LR(1)項(xiàng)目集規(guī)范族及識(shí)別活項(xiàng)目集規(guī)范族及識(shí)別活前綴的前綴的DFADFA（1）C:=Closure (S S,#);（2）重復(fù)執(zhí)行(3)的動(dòng)作，直到C不再增大;（3）FOR C中的每個(gè)項(xiàng)目集I和G的每個(gè)符號(hào)X DO IF GO(I,X)非空且不屬于C 把GO(I,X)加入C中; 在I和Go(I,X)之間畫標(biāo)記為X的弧線; 上面的例子的上面的例子的LR(1)LR(1)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族LR(1)LR(1)分析表的構(gòu)造分析表的構(gòu)造 （1）若項(xiàng)目Aa,bIk，且GO(Ik,a)=Ij，其中aVT，則置actionk,a=Sj。即把輸入符號(hào)a和狀態(tài)j分別移入文法符號(hào)棧和狀態(tài)棧。（2）若項(xiàng)目A,aIk，其中aVT，則置actionk,a=rj，即用產(chǎn)生式A進(jìn)