LR 分析法課件

《LR 分析法課件》由會員分享，可在線閱讀，更多相關(guān)《LR 分析法課件（85頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第七章第七章 LR LR 分析法分析法 1965年，年，D.knuth首先提出了首先提出了LR(K)文法及文法及LR(K)分析技術(shù)。分析技術(shù)。 LR(K)分析是指自左向右掃描和自底向上的語法分析，且分析是指自左向右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧中當(dāng)前已移進(jìn)和歸約出的在分析的每一步，只須根據(jù)分析棧中當(dāng)前已移進(jìn)和歸約出的全部文法符號，并至多再向前查看全部文法符號，并至多再向前查看K個輸入符號，就能確定個輸入符號，就能確定相當(dāng)于某一產(chǎn)生式右部符號的句柄是否已在分析棧的頂部形相當(dāng)于某一產(chǎn)生式右部符號的句柄是否已在分析棧的頂部形成。從而也就可以確定所應(yīng)采取的分析動作（是移進(jìn)輸

2、入符號成。從而也就可以確定所應(yīng)采取的分析動作（是移進(jìn)輸入符號還是按某產(chǎn)生式進(jìn)行歸約）。還是按某產(chǎn)生式進(jìn)行歸約）。當(dāng)前掃描到當(dāng)前掃描到Xn+1,向前查看向前查看k個符號，來確定是把個符號，來確定是把Xn+1移進(jìn)棧，還是把移進(jìn)棧，還是把XiXn作為句柄進(jìn)行歸約。作為句柄進(jìn)行歸約。1） 要歸約時，則根據(jù)某產(chǎn)生式要歸約時，則根據(jù)某產(chǎn)生式UXiXi+1Xn進(jìn)行歸約：進(jìn)行歸約： #X1X2Xi-1UXn+1Xn+2Xn+k#例：例：#X1X2Xi Xn Xn+1Xn+2Xn+kXn+k+1#棧頂棧頂（續(xù)頁）（續(xù)頁）LR(0) 表示在每一步分析時都不用向前輸入符號表示在每一步分析時都不用向前輸入符號LR(1

3、) 表示在每一步分析時都向前看一個輸入符號來決定當(dāng)表示在每一步分析時都向前看一個輸入符號來決定當(dāng) 前的動作。前的動作。SLR(1) 表示簡單的表示簡單的LR(1)，即只在動作不唯一的地方向前看，即只在動作不唯一的地方向前看一個符號，在動作唯一時則不向前看輸入符號。一個符號，在動作唯一時則不向前看輸入符號。2） 要移進(jìn)時，即把要移進(jìn)時，即把Xn+1進(jìn)棧，并讀下一符號：進(jìn)棧，并讀下一符號： #X1X2XiXnXn+1 Xn+2Xn+k# 在棧中在棧中當(dāng)前掃描符當(dāng)前掃描符棧頂棧頂7.1 LR7.1 LR分析概論分析概論一一 .LR分析器的邏輯結(jié)構(gòu)及工作過程分析器的邏輯結(jié)構(gòu)及工作過程 從邏輯上來說，一

4、個從邏輯上來說，一個LR分析器如圖分析器如圖7.1 所示。所示。 輸入串輸入串#aia1SpX1#S1S0XmSm總總 控控 程程 序序輸出輸出ACTION 表表GOTO 表表其中其中S棧為狀態(tài)棧棧為狀態(tài)棧 X棧為符號棧棧為符號棧棧棧產(chǎn)生式產(chǎn)生式 表表圖圖7.1 LR分析器的邏輯結(jié)構(gòu)分析器的邏輯結(jié)構(gòu) 即一個即一個LR(k)分析器主要由：總控程序，分析棧（狀態(tài)棧分析器主要由：總控程序，分析棧（狀態(tài)棧和符號棧）輸入隊列和分析表組成。一般來說所有和符號棧）輸入隊列和分析表組成。一般來說所有LR分析器分析器的總控程序基本上是大同小異。只有分析表各不相同。一般的總控程序基本上是大同小異。只有分析表各不相

5、同。一般主要討論三種不同的分析表的構(gòu)造方法。主要討論三種不同的分析表的構(gòu)造方法。 第一種稱為規(guī)范第一種稱為規(guī)范LR分析表構(gòu)造法。用此法構(gòu)造的分析表分析表構(gòu)造法。用此法構(gòu)造的分析表功能最強而且也適合于很多文法，但實現(xiàn)代價比較高。功能最強而且也適合于很多文法，但實現(xiàn)代價比較高。 第二種稱為簡單第二種稱為簡單LR(即即SLR)分析表構(gòu)造法。這是一種比較分析表構(gòu)造法。這是一種比較容易實現(xiàn)的方法。但容易實現(xiàn)的方法。但SLR分析表的功能太弱，而且對某些文法分析表的功能太弱，而且對某些文法可能根本就構(gòu)造不出相應(yīng)的可能根本就構(gòu)造不出相應(yīng)的SLR分析表。分析表。 第三種稱為向前第三種稱為向前LR（即（即LALR

6、）分析表構(gòu)造法。這種方法）分析表構(gòu)造法。這種方法構(gòu)造的分析表功能介于規(guī)范構(gòu)造的分析表功能介于規(guī)范LR分析表分析表SLR分析表之間。這種表分析表之間。這種表適用于絕大多數(shù)程序語言的文法。而且也可以設(shè)法有效的實現(xiàn)。適用于絕大多數(shù)程序語言的文法。而且也可以設(shè)法有效的實現(xiàn)。二、二、LR 分析器的分析過程如下：分析器的分析過程如下：1.首先將初始狀態(tài)首先將初始狀態(tài) S0及句子的左界限及句子的左界限#分別壓入狀態(tài)棧和符號棧中。分別壓入狀態(tài)棧和符號棧中。 則用棧頂狀態(tài)則用棧頂狀態(tài)Sm和當(dāng)前掃描符和當(dāng)前掃描符 ai組成符號對（組成符號對（ Sm, ai)去查去查分析動作表，根據(jù)分析動作表，根據(jù)ACTIONSm

7、, ai的指示完成相應(yīng)的分析動作。的指示完成相應(yīng)的分析動作。表中每一表元素所規(guī)定的動作僅能是下列四種動作之一：表中每一表元素所規(guī)定的動作僅能是下列四種動作之一： S0S1 S2 Sm Sm+1 ai+1 ai+2 an # # X1 X2 Xm ai 2.設(shè)在分析中的某一步，分析棧及余留的輸入串為如下格局：設(shè)在分析中的某一步，分析棧及余留的輸入串為如下格局： S0S1 Sm ai ai+1an #X1 Xm （1） ACTIONSm, ai= Sm+1 （移進(jìn)）（移進(jìn)）表明句柄尚未在棧頂形成，此時正期待移進(jìn)輸入符號以便形成表明句柄尚未在棧頂形成，此時正期待移進(jìn)輸入符號以便形成句柄。故將當(dāng)前的輸

8、入符號和表元素句柄。故將當(dāng)前的輸入符號和表元素Sm+1分別壓入棧中，有分別壓入棧中，有（2） ACTIONSm, ai= Rj (歸約）歸約） 表明此時應(yīng)按文法的第表明此時應(yīng)按文法的第j個產(chǎn)生式個產(chǎn)生式A Xm-k+1Xm-k+2 Xm進(jìn)行歸約。即棧頂符號串進(jìn)行歸約。即棧頂符號串Xm-k+1Xm-k+2 Xm已成為當(dāng)前句型的句已成為當(dāng)前句型的句柄。所謂按第柄。所謂按第j個產(chǎn)生式歸約，就是將分析棧中從頂向下的個產(chǎn)生式歸約，就是將分析棧中從頂向下的k個符個符號退棧，然后將文法符號號退棧，然后將文法符號A壓入符號棧中。此時分析的格局為：壓入符號棧中。此時分析的格局為： S0S1 Sm-k ai ai

9、+1an # # X1 Xm-k A 然后以（然后以（ Sm-k,A)去查狀態(tài)轉(zhuǎn)移表，設(shè)去查狀態(tài)轉(zhuǎn)移表，設(shè)GOTOSm-k,A= Sl ,則將則將此新狀態(tài)壓入狀態(tài)棧中，則有如下格局：此新狀態(tài)壓入狀態(tài)棧中，則有如下格局： S0S1 Sm-k Sl ai ai+1an # # X1 Xm-k A （3） ACTIONSm, ai=acc （接受）（接受） 表明當(dāng)前的輸入串已被成功地分析完畢，應(yīng)停止分析器的工作。表明當(dāng)前的輸入串已被成功地分析完畢，應(yīng)停止分析器的工作。其中其中Z為文法開始符號為文法開始符號S為使為使ACTIONS ，#=acc的的 唯一狀態(tài)（接受狀態(tài)）唯一狀態(tài)（接受狀態(tài)）（4） AC

10、TIONSm, ai=ERROR（空白）。（空白）。 表明當(dāng)前的輸入串中含有錯誤，也應(yīng)終止當(dāng)前的分析工作。表明當(dāng)前的輸入串中含有錯誤，也應(yīng)終止當(dāng)前的分析工作。轉(zhuǎn)出錯處理。轉(zhuǎn)出錯處理。3. 重復(fù)上述第重復(fù)上述第2步的工作，直到分析棧頂出現(xiàn)步的工作，直到分析棧頂出現(xiàn)“接受狀態(tài)接受狀態(tài)”或或“出錯狀態(tài)出錯狀態(tài)“為止。對接受狀態(tài)，分析棧的格局為：為止。對接受狀態(tài)，分析棧的格局為： S0 S # # Z 例：例：有文法有文法GS:1：SaAcBe e 2：Ab 3：AAb 4：Bd其其ACTION表和表和GOTO表表為：為：考察對輸入串考察對輸入串a(chǎn)bbcde# 的的分析過程。分析過程。r1r1r1r1

11、r1r1r4r4r4r4r4r4S9r3r3r3r3r3r37S8r2r2r2r2r2r2S6S53S4acc1S2BAS#dbecaGOTOACTION0123456789 S a A c B e e A b d b圖圖7.2 abbcde# 的語法樹的語法樹對輸入串對輸入串a(chǎn)bbcde# 的分析過程為：的分析過程為： ACTION GOTO步驟步驟 狀態(tài)棧狀態(tài)棧 符號棧符號棧 輸入流輸入流 分析動作分析動作 下一狀態(tài)下一狀態(tài)1 0 # abbcde# S2(0,a)2 02 #a bbcde# S4(2,b)3 024 #ab bcde# r2(4,b) GOTO2,A=34 023 #a

12、A bcde# S6(3,b) 6 023 #aA cde# S5(3,c)5 0236 #aAb cde# r3(6,b) GOTO2,A=37 0235 #aAc de# S8(5,d)8 02358 #aAcd e# r4(8,d) GOTO5,B=79 02357 #aAcB e# S9(7,e)10 023579 #aAcBe # r1(9,#) GOTO0,S=111 01 #S # acc(1,#)圖圖7.3 abbcde#的分析過程的分析過程 LR分析過程中的性質(zhì)與特點：分析過程中的性質(zhì)與特點：n棧中的文法符號串并上剩余的輸入串構(gòu)成一個右句型（規(guī)范句型）n當(dāng)該右句型的句柄出現(xiàn)在

13、棧頂時，歸約，否則，移進(jìn)n棧中的文法符號串是當(dāng)前句型的前綴，該前綴不包含句型句柄后面的符號，稱之為活前綴（Viable Prefixes）7.2 LR(0) 分析表的構(gòu)造分析表的構(gòu)造為了給出構(gòu)造為了給出構(gòu)造LR(0)分析表的算法，引出一些術(shù)語：分析表的算法，引出一些術(shù)語：1、規(guī)范句型的活前綴、規(guī)范句型的活前綴 前綴：前綴：一個符號串的前綴是指該串的任意首部（包括一個符號串的前綴是指該串的任意首部（包括 ）。）。例如例如 abc的前綴有：的前綴有： ,a,ab,abc abcd的前綴有：的前綴有： ,a,ab,abc,abcd 由此可知，對于符號串由此可知，對于符號串 而言，其前綴的數(shù)量為而言，

14、其前綴的數(shù)量為+1。例：有文法例：有文法GS:SaAcBe e1 Ab2 這里在每條產(chǎn)生式后加上了產(chǎn)這里在每條產(chǎn)生式后加上了產(chǎn) AAb3 生式的序號生式的序號i當(dāng)進(jìn)行推導(dǎo)時把當(dāng)進(jìn)行推導(dǎo)時把 Bd4 序號帶上，以便說明問題。序號帶上，以便說明問題。對輸入串對輸入串a(chǎn)bbcde e進(jìn)行推導(dǎo)如下（最右推導(dǎo)）：進(jìn)行推導(dǎo)如下（最右推導(dǎo)）： S aAcBe e1 aAcd4e e1 aAb3cd4e e1 ab2b3cd4e e1由此可知，由此可知，abbcde e是該文法的句子。由于是該文法的句子。由于LR方法是自底向上的方法是自底向上的分析，故應(yīng)采用歸約。分析，故應(yīng)采用歸約。最左歸約為：最左歸約為：

15、ab2b3cd4e e1 用用2式歸約式歸約 aAb3cd4e e1 3 aAcd4e e1 4 aAcBe e1 1 S其中其中表示歸約符表示歸約符 從歸約的過程可看出，每次歸約時，歸約前和歸約后的被從歸約的過程可看出，每次歸約時，歸約前和歸約后的被歸約部分與剩余部分合起來僅構(gòu)成文法的規(guī)范句型，而用哪個歸約部分與剩余部分合起來僅構(gòu)成文法的規(guī)范句型，而用哪個產(chǎn)生式歸約僅取決于當(dāng)前句型的前面部分；產(chǎn)生式歸約僅取決于當(dāng)前句型的前面部分；X1X2Xnp 其中其中Xi為文法的符號，為文法的符號，p為第為第p個產(chǎn)生式序號。個產(chǎn)生式序號。 如上例中每次歸約前句型的前面部分為：如上例中每次歸約前句型的前面部

16、分為： ab2 aAb3 aAcd4 aAcBe e1我們把規(guī)范句型的這種前端部分的串稱為可歸我們把規(guī)范句型的這種前端部分的串稱為可歸前綴。實際上，它們恰好是符號棧棧頂形成句前綴。實際上，它們恰好是符號棧棧頂形成句柄時符號棧中的內(nèi)容。柄時符號棧中的內(nèi)容。SaAcBee1Ab2AAb3Bd4 這是因為一旦句型的句柄在符號棧頂形成，將會立即被歸約這是因為一旦句型的句柄在符號棧頂形成，將會立即被歸約之故。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的之故。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的任何符號）的前綴稱之為任何符號）的前綴稱之為可歸前綴可歸前綴。 對各規(guī)范句型有前綴：對各規(guī)范

17、句型有前綴：ab2b3cd4e1 ,a,abaAb3cd4e1 ,a,aA,aAbaAcd4e1 ,a,aA,aAc,aAcdaAcBe1 ,a,aA,aAc,aAcB,aAcBe可以發(fā)現(xiàn)前綴可以發(fā)現(xiàn)前綴a,ab,aA,aAc是多個規(guī)范句型的前綴，因此我們可進(jìn)是多個規(guī)范句型的前綴，因此我們可進(jìn)一步一步把形成可歸前綴前和形成可歸前綴時的所有規(guī)范句型的前綴把形成可歸前綴前和形成可歸前綴時的所有規(guī)范句型的前綴都稱為都稱為活前綴活前綴?？蓺w前綴：可歸前綴：是指規(guī)范句型的一個前綴，這種前綴包含句柄且不是指規(guī)范句型的一個前綴，這種前綴包含句柄且不含句柄之后的任何符號。含句柄之后的任何符號。活前綴：活前綴：

18、可歸前綴的任意首部。特指在分析過程中對于在棧頂可歸前綴的任意首部。特指在分析過程中對于在棧頂形成句柄之前和恰好形成句柄時，每一步中形成句柄之前和恰好形成句柄時，每一步中符號棧中的那些符符號棧中的那些符號組成的符號串號組成的符號串?；钋熬Y定義：活前綴定義： 在前面例中對輸入串在前面例中對輸入串a(chǎn)bbcde的歸約分析過程中，在規(guī)范歸約的歸約分析過程中，在規(guī)范歸約過程中的任何時候只要已分析過的部分即在符號棧中的符號串均過程中的任何時候只要已分析過的部分即在符號棧中的符號串均為規(guī)范句型的活前綴，它表明輸入串的已被分析過的部分是該文為規(guī)范句型的活前綴，它表明輸入串的已被分析過的部分是該文法某規(guī)范句型的一

19、個正確部分。法某規(guī)范句型的一個正確部分。由此可形式地定義活前綴如下：由此可形式地定義活前綴如下： 定義定義 7.1：若：若S * A 是是 文法文法G中的一個規(guī)范推導(dǎo)，中的一個規(guī)范推導(dǎo)， 如果符號串如果符號串 是是的前綴，則稱的前綴，則稱 是是G的一個活前綴。的一個活前綴。 其中其中 S為為文法開始符號。文法開始符號。 RRLRLR分析分析n分析過程可以看作是識別文法規(guī)范句型活前綴的過程。n只要每一時刻棧中的文法符號串是某規(guī)范句型的活前綴，則說明已分析的部分是正確的n一個文法的規(guī)范句型的所有活前綴構(gòu)成一個語言，而且是正規(guī)語言，可以用一個 DFA 來識別n例子：文法GS：(1) S aAcBe(

20、2) A b(3) A Ab(4) B d014235769SabAbcBed8*n每個狀態(tài)都是活前綴的識別態(tài)，雙圈狀態(tài)是可歸前綴（句柄）識別態(tài)，標(biāo)識了*的狀態(tài)是句子識別態(tài)分析句子的過程可以看作在上面這個 DFA 上運行的過程014235769SabAbcBed8*(1) S aAcBe(2) A b(3) A Ab(4) B dn例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S2014235769SabAbcBed*8n例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S4014235769SabAbcBed8*n例子：步驟棧輸入串ACTIONG

21、OTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R23014235769SabAbcBed8*n例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S6014235769SabAbcBed8*n例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S65#0a2A3b6cde#R33014235769SabAbcBed8*n例子：步驟棧輸入串ACTIONGOTO3#0a2b4bcde#R

22、234#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S5*014235769SabAbcBed8n例子：步驟棧輸入串ACTIONGOTO4#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S8*014235769SabAbcBed8n例子：步驟棧輸入串ACTIONGOTO5#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R47014235769SabAbcBed8*n例子：步驟棧輸入串ACTIONGOTO6#0a2A3cde#S57#0a2A

23、3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S9014235769SabAbcBed8*n例子：步驟棧輸入串ACTIONGOTO7#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R11014235769SabAbcBed8*n例子：步驟棧輸入串ACTIONGOTO8#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R1111#0S1#Acc014235769SabAbcBed8*2、LR（0）項目）項目 由上述分析和定義可知，活前綴與句柄間的關(guān)系不外乎下由

24、上述分析和定義可知，活前綴與句柄間的關(guān)系不外乎下述述 三種情況：三種情況：（1）活前綴中已含有句柄的全部符號（句柄的最后符號就是活前綴中已含有句柄的全部符號（句柄的最后符號就是 活前綴的最后符號）。活前綴的最后符號）。（2）活前綴中只含有句柄的前部分符號（句柄的最左子串活前綴中只含有句柄的前部分符號（句柄的最左子串 為活前綴的最右子串）。為活前綴的最右子串）。（3）活前綴中全然不包含句柄的任何符號?；钋熬Y中全然不包含句柄的任何符號。第一種情況表明：第一種情況表明：此時某一產(chǎn)生式此時某一產(chǎn)生式A的右部的右部已出現(xiàn)在符號已出現(xiàn)在符號棧頂，因此此時相應(yīng)的分析動作應(yīng)當(dāng)是用此產(chǎn)生式進(jìn)行歸約。棧頂，因此此

25、時相應(yīng)的分析動作應(yīng)當(dāng)是用此產(chǎn)生式進(jìn)行歸約。第二種情況表明：第二種情況表明：形如形如A 1 2的產(chǎn)生式的的產(chǎn)生式的 右部子串已在符號棧右部子串已在符號棧棧頂，如棧頂，如 1，正期待著從余留的輸入串中看到能由正期待著從余留的輸入串中看到能由推出的推出的 符號符號串，即期待串，即期待 2 進(jìn)棧以便能進(jìn)行歸約。故此時分析動作是進(jìn)棧以便能進(jìn)行歸約。故此時分析動作是“移進(jìn)移進(jìn)”當(dāng)前輸入符號。當(dāng)前輸入符號。第三種情況則意味著：第三種情況則意味著：期望從余留輸入串中能看到由某產(chǎn)生式期望從余留輸入串中能看到由某產(chǎn)生式A 的右部，即的右部，即 所代表的符號串所代表的符號串(即句柄即句柄) 。所以此時分析的。所以此

26、時分析的動作也是讀輸入符進(jìn)符號棧。動作也是讀輸入符進(jìn)符號棧。 為了刻畫在分析過程中，文法的一個產(chǎn)生式右部符號串有多大為了刻畫在分析過程中，文法的一個產(chǎn)生式右部符號串有多大部分已被識別，我們可在該產(chǎn)生式的右部相應(yīng)位置上加一個圓點部分已被識別，我們可在該產(chǎn)生式的右部相應(yīng)位置上加一個圓點“. .”，來指示位置，標(biāo)明在，來指示位置，標(biāo)明在“. .”前的部分已被識別。如上述三種前的部分已被識別。如上述三種情況，可分別標(biāo)注為：情況，可分別標(biāo)注為：A. .； A 1 . . 2 ; A. . 。 我們把右部某位置上標(biāo)有圓點的產(chǎn)生式稱為相應(yīng)文法的一個我們把右部某位置上標(biāo)有圓點的產(chǎn)生式稱為相應(yīng)文法的一個LR(0

27、)項目。特別地，對形如項目。特別地，對形如A 的產(chǎn)生式，相應(yīng)的的產(chǎn)生式，相應(yīng)的LR(0)項目項目表示為表示為A. .。顯然不同的顯然不同的LR(0)項目，反映了分析過程中符號棧項目，反映了分析過程中符號棧頂?shù)牟煌闆r。頂?shù)牟煌闆r。例如：產(chǎn)生式例如：產(chǎn)生式SaAcBe對應(yīng)有六個項目。對應(yīng)有六個項目。0 S. .aAcBe1 Sa. .AcBe2 SaA. .cBe3 SaAc. .Be4 SaAcB. .e5 SaAcBe. .例如：產(chǎn)生式例如：產(chǎn)生式SaAcBe對應(yīng)有六個項目。對應(yīng)有六個項目。0 S.aAcBe1 Sa.AcBe2 SaA.cBe3 SaAc.Be4 SaAcB.e5 SaA

28、cBe. 一個產(chǎn)生式可對應(yīng)的項目的數(shù)量為它的右部符號串長度加一個產(chǎn)生式可對應(yīng)的項目的數(shù)量為它的右部符號串長度加1，值得注意的是對空產(chǎn)生式，即值得注意的是對空產(chǎn)生式，即A僅有項目僅有項目A. . 每個項目的含義與圓點的位置有關(guān)。概括地說，圓點左邊的每個項目的含義與圓點的位置有關(guān)。概括地說，圓點左邊的子串表示在分析過程的某一時刻用該產(chǎn)生式歸約時句柄中已識別子串表示在分析過程的某一時刻用該產(chǎn)生式歸約時句柄中已識別過的部分，圓點右邊的子串表示待識別的部分。過的部分，圓點右邊的子串表示待識別的部分。 文法的全部文法的全部LR(0)項目將是構(gòu)造識別它的所有活前綴的有窮項目將是構(gòu)造識別它的所有活前綴的有窮自

29、動機的基礎(chǔ)。自動機的基礎(chǔ)。3、LR(0)項目的分類：項目的分類：例：考慮文法例：考慮文法GS=(S,A,B, a,b,c,d,P,S),構(gòu)造其分析表：構(gòu)造其分析表：其中其中P: (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d解：求該文法的項目集規(guī)范族解：求該文法的項目集規(guī)范族C：為了方便起見，我們在上述文法中引起一個新的開始符號為了方便起見，我們在上述文法中引起一個新的開始符號S,且將且將S S作為第作為第0個產(chǎn)生式添加到文法個產(chǎn)生式添加到文法G中，從而得到了所謂中，從而得到了所謂G的拓廣文法的拓廣文法G。顯然。顯然L(G)=L(G)，則對于文法，則

30、對于文法G，其，其LR(0)項目為：項目為： 1) S . .S 2) S S. . 3) S. .A 4) SA . . 5) S. .B 6) SB. . 7) A.aAb 8) Aa . .Ab 9) AaA . .b 10) AaAb . . 11) A. .c 12) Ac . . 13) B. .aBd 14) Ba . .Bd 15) BaB . .d 16) BaBd . . 17)B. .d 18) Bd . .G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d如前所述，由于不同的項目反映了分析過程中棧頂?shù)牟煌闆r，如前

31、所述，由于不同的項目反映了分析過程中棧頂?shù)牟煌闆r，因此，我們可根據(jù)它們不同的作用，將一個文法的全部因此，我們可根據(jù)它們不同的作用，將一個文法的全部LR(0)項目項目進(jìn)行分類：進(jìn)行分類：n移進(jìn)項目：A an待約項目：A Bn歸約項目： A n接受項目： S S 圓點的左部表示分析過程中的某時刻用該產(chǎn)生式歸約時句柄已識別過的部分，圓點右部表示待識別部分4、構(gòu)造識別活前綴的、構(gòu)造識別活前綴的DFA 在在LR方法實際過程中，并不是去直接分析符號棧中的符號方法實際過程中，并不是去直接分析符號棧中的符號是否已形成句柄，但它給我們一個啟示，我們可以把是否已形成句柄，但它給我們一個啟示，我們可以把終結(jié)符和非

32、終結(jié)符和非終結(jié)符終結(jié)符都可看成一個有限自動機的都可看成一個有限自動機的輸入符號輸入符號，每把一個符號進(jìn)棧，每把一個符號進(jìn)棧時看成已識別過該符號，而狀態(tài)進(jìn)行轉(zhuǎn)換（到下一狀態(tài)），當(dāng)識時看成已識別過該符號，而狀態(tài)進(jìn)行轉(zhuǎn)換（到下一狀態(tài)），當(dāng)識別到可歸前綴時相當(dāng)于棧頂已形成了句柄，則認(rèn)為到達(dá)了識別句別到可歸前綴時相當(dāng)于棧頂已形成了句柄，則認(rèn)為到達(dá)了識別句柄的柄的終態(tài)終態(tài)。 在作出文法的全部在作出文法的全部LR(0)項目之后，現(xiàn)在將用它們來構(gòu)造識別項目之后，現(xiàn)在將用它們來構(gòu)造識別全部活前綴的全部活前綴的DFA。這種。這種DFA中的中每一個狀態(tài)由若干個中的中每一個狀態(tài)由若干個LR(0)項目所組成的集合（稱為

33、項目集）來表示。項目所組成的集合（稱為項目集）來表示。 下面以上例中的文法為例來下面以上例中的文法為例來說明構(gòu)造說明構(gòu)造DFA的方法。的方法。 G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d首先我們用首先我們用I I0 0表示這個表示這個DFADFA的初態(tài)，它的初態(tài)，它預(yù)示著整個分析過程的開始，并且期待著將預(yù)示著整個分析過程的開始，并且期待著將給定的輸入串逐步歸約為文法的開始符號給定的輸入串逐步歸約為文法的開始符號SS?；蛘叻催^來說，我們所期待的是，從使用產(chǎn)或者反過來說，我們所期待的是，從使用產(chǎn)生式生式SSSS開始，能夠逐漸推導(dǎo)出所給

34、定的開始，能夠逐漸推導(dǎo)出所給定的輸入串。因此，我們應(yīng)將項目輸入串。因此，我們應(yīng)將項目S.SS.S列入項列入項目集目集I I0 0之中。換言之，也就是我們正期待將之中。換言之，也就是我們正期待將要掃描的輸入串正好就是能由要掃描的輸入串正好就是能由SS推導(dǎo)出的任推導(dǎo)出的任何終結(jié)符串。何終結(jié)符串。然而，我們不能從輸入串中直然而，我們不能從輸入串中直接讀出非終結(jié)符號接讀出非終結(jié)符號S S，因此我們也應(yīng)將項目，因此我們也應(yīng)將項目S.AS.A和和S.BS.B加入加入I I0 0中。由于中。由于A A和和B B同樣是非同樣是非終結(jié)符，所以也應(yīng)將終結(jié)符，所以也應(yīng)將A.aAbA.aAb和和A.cA.c和和B.a

35、Bb, B.dB.aBb, B.d加入加入I I0 0中。中。G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d 由于最后加入由于最后加入I I0 0的項目在圓點之后已都是終結(jié)符了，故的項目在圓點之后已都是終結(jié)符了，故I I0 0已經(jīng)已經(jīng)“封閉封閉”，宣告項目集，宣告項目集I I0 0構(gòu)造結(jié)束。構(gòu)造結(jié)束。 這樣，表示初態(tài)的項目集這樣，表示初態(tài)的項目集I I0 0將由如下項目組成：將由如下項目組成：I I0 : S.S, S.A, S.B, A.aAb, A.c, 0 : S.S, S.A, S.B, A.aAb, A.c, B.aBd,

36、B.d B.aBd, B.dI I0 : S. .S, S. .A, S. .B, A. .aAb, A. .c, B. .aBd, B. .d 我們將我們將LR(0)項目項目S.S稱為稱為項目集項目集I I0的基本項目的基本項目，上述從，上述從S. .S出發(fā)構(gòu)造項目集出發(fā)構(gòu)造項目集I I0的過程，可用一個對其基本項目集的過程，可用一個對其基本項目集S . .S的閉包運算，即的閉包運算，即closure(S. .S)來表示。來表示。一般地，設(shè)一般地，設(shè)I為項目集，為項目集，I的閉包的閉包closure(I)的定義為：的定義為：Closure(I)=IA. . A GK . .A closure

37、(I) V* V*故構(gòu)造故構(gòu)造closure(I)的算法為：的算法為：1）I中的每一個項目都屬于中的每一個項目都屬于closure(I);2）若形如）若形如K . .A 的項目屬于的項目屬于I，且，且A 是文法的一個產(chǎn)生式，是文法的一個產(chǎn)生式， 則關(guān)于產(chǎn)生式則關(guān)于產(chǎn)生式A的任何形如的任何形如A. . 的項目也應(yīng)加到的項目也應(yīng)加到closure(I)中中 （若它們不在（若它們不在closure(I)中）；中）；3）重復(fù)上述過程，直至不再有新的項目加入到）重復(fù)上述過程，直至不再有新的項目加入到closure(I)中為中為 止。止。 有了初態(tài)項目集有了初態(tài)項目集I0之后，我們來說明如何確定從之后，我

38、們來說明如何確定從I0可能轉(zhuǎn)移可能轉(zhuǎn)移到的下一狀態(tài)。設(shè)到的下一狀態(tài)。設(shè)A為一文法符號為一文法符號(AV)，若，若I0中有圓點位于中有圓點位于A左邊的項目左邊的項目K . .A (其中其中 可能為可能為 )，則當(dāng)分析器從輸入串識，則當(dāng)分析器從輸入串識別出別出(即移進(jìn)或歸約出即移進(jìn)或歸約出)文法符號文法符號A后，分析器將進(jìn)入它的下一狀后，分析器將進(jìn)入它的下一狀態(tài)。設(shè)此狀態(tài)為態(tài)。設(shè)此狀態(tài)為Ii ，顯然，顯然Ii中必含有全部形如中必含有全部形如K A . . 的項目，的項目，我們將這樣的項目稱為我們將這樣的項目稱為K . .A 的的后繼項目后繼項目。對于每一個文法。對于每一個文法符號符號A，如果存在這

39、樣的后繼項目，則可能不只一個，設(shè)其組成，如果存在這樣的后繼項目，則可能不只一個，設(shè)其組成集合集合J，則，則J中的每個項目都是項目集中的每個項目都是項目集Ii的基本項目，因此，按照的基本項目，因此，按照與上面構(gòu)造項目集與上面構(gòu)造項目集I0相類試的討論，我們有：相類試的討論，我們有： Ii =closure(J) 為了指明為了指明Ii是是“I0關(guān)于文法符號關(guān)于文法符號A的后繼狀態(tài)的后繼狀態(tài)”這一事實，這一事實，我們可定義一個狀態(tài)轉(zhuǎn)移函數(shù)：我們可定義一個狀態(tài)轉(zhuǎn)移函數(shù)： GO(I0,A)=closure(J) = Ii 其中，其中，I是當(dāng)前狀態(tài)，是當(dāng)前狀態(tài)，A為文法符號，為文法符號，J是是I中所有形如

40、中所有形如K .A 的項目之后繼項目的項目之后繼項目K A. 所組成的集合，而所組成的集合，而closure(J)就是項就是項目集目集I（即狀態(tài)（即狀態(tài)I)關(guān)于符號關(guān)于符號A的后繼項目集（即后繼狀態(tài)）。的后繼項目集（即后繼狀態(tài)）。 狀態(tài)轉(zhuǎn)移函數(shù)：狀態(tài)轉(zhuǎn)移函數(shù)： GO(I0,A)=closure(J) = Ii 其中，其中，I是當(dāng)前狀態(tài)，是當(dāng)前狀態(tài)，A為文法符號，為文法符號，J是是I中所有形如中所有形如K . .A 的項目之后繼項目的項目之后繼項目K A. . 所組成的集合，而所組成的集合，而closure(J)就是項目就是項目集集I（即狀態(tài)（即狀態(tài)I)關(guān)于符號關(guān)于符號A的后繼項目集（即后繼狀態(tài)

41、）。的后繼項目集（即后繼狀態(tài)）。即：即： GO(I,A)=closure(所有形如所有形如K A . . 的項目的項目 K . .A I) 對于上例，我們有：對于上例，我們有： I1 =GO(I0,S)=closure(SS.) I1 : SS . ; I2 =GO(I0,A)=closure(SA.) I2 :SA . ; I3 =GO(I0,B)=closure(SB.) I3 : SB . ; I4 =GO(I0,a)=closure(Aa . Ab,Ba . Bd)G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B dI4 : Aa.

42、Ab Ba.Bd A.aAb B.aBd A.c B.d I5=GO(I0,c)=closure(Ac.) I5 : Ac. I6=GO(I0,d)=closure(Bd.) I6 :Bd. 此時，我們求出了此時，我們求出了I0的全部后繼項目集的全部后繼項目集I1, I2,I3,I4,I5,I6,而而I1, I2,I3,I5,I6均無后繼項目集，僅均無后繼項目集，僅I4有后繼項目集：有后繼項目集： I7 =GO(I4,A)=closure(AaA.b)=AaA.b I9 =GO(I4,B)=closure(BaB.d)=BaB.d此外，還有：此外，還有： GO(I4,a)=closure(Aa

43、.Ab, Ba.Bd)= I4 GO(I4,c)=closure(Ac.)= I5 GO(I4,d)=closure(Bd.)= I6 這些項目集均不產(chǎn)生新的項目集。另外還有這些項目集均不產(chǎn)生新的項目集。另外還有:G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d I8 =GO(I7,b)=closure(AaAb.)=AaAb. I10 =GO(I9,b)=closure(BaBd.)=BaBd.此時此時I8 ， I10也已無后繼項目集，故我們已求出文法也已無后繼項目集，故我們已求出文法GS的全部的全部項目集項目集I0 I10 。 通常

44、我們將這些項目集的全體稱為文法通常我們將這些項目集的全體稱為文法GS的的LR(0)項目集規(guī)范項目集規(guī)范族，并記為族，并記為C=(I0, I1, I10) 于是，我們所要構(gòu)成的識別文法于是，我們所要構(gòu)成的識別文法GS的全部活前綴的的全部活前綴的DFA為為 M=(C,V,GO, I0,Z) 其中其中CM的狀態(tài)集，即文法的狀態(tài)集，即文法GS的的LR(0)項目集規(guī)范族項目集規(guī)范族, C=(I0, I1, I10); V M的字母表，即的字母表，即V=S,S,A,B,a,b,c,d； GOM的映射函數(shù)，即上面定義的狀態(tài)轉(zhuǎn)移函數(shù)的映射函數(shù)，即上面定義的狀態(tài)轉(zhuǎn)移函數(shù)GO； I0M的唯一初態(tài)；的唯一初態(tài)； Z

45、M的終態(tài)集，的終態(tài)集， Z C，為規(guī)范族中所有含有歸約項目的，為規(guī)范族中所有含有歸約項目的 那些項目集。那些項目集。DFA:I0 : S.S S.A S.B A.aAb A.c B.aBd B.dI1 :SS.I2 :SA.I3 :SB.I4 :Aa.Ab Aa.Bd A.aAb A.c B.aBd B.dI8 :A aAb.I7 :A aA.bI9 :B aB.dI10 :B aBd.I5 :Ac.I6 :Bd.ABdbcd dacSABaG：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d圖圖7.4 文法文法GS項目集規(guī)范族項目集規(guī)范族

46、DFA:即：即：I0I1I2I3I4I5I6I7I9I8I10SABacdcdABbdG：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B da圖圖7.5 識別文法識別文法GS活前綴的活前綴的DFA5、LR(0)分析表的構(gòu)造分析表的構(gòu)造 對于一個文法對于一個文法G的拓廣文法的拓廣文法G，當(dāng)識別它的全部活前綴的，當(dāng)識別它的全部活前綴的DFA作出之后，我們可以據(jù)此構(gòu)造相應(yīng)的作出之后，我們可以據(jù)此構(gòu)造相應(yīng)的LR(0)分析表了。分析表了。 然而，要注意的是，用前述方法所構(gòu)造的每一個然而，要注意的是，用前述方法所構(gòu)造的每一個LR(0)項目集項目集實質(zhì)上表

47、征了在分析過程中可能出現(xiàn)的一種分析狀態(tài)；再根據(jù)前實質(zhì)上表征了在分析過程中可能出現(xiàn)的一種分析狀態(tài)；再根據(jù)前面對面對LR(0)項目的分類，項目集中的每一個項目又與某一種分析項目的分類，項目集中的每一個項目又與某一種分析動作相關(guān)聯(lián)，因此，就要求每一個項目集中的的諸項目應(yīng)當(dāng)是相動作相關(guān)聯(lián)，因此，就要求每一個項目集中的的諸項目應(yīng)當(dāng)是相容的。所謂相容，是指在一個項目集中不出現(xiàn)下列的情況：容的。所謂相容，是指在一個項目集中不出現(xiàn)下列的情況：（1）移進(jìn)項目和歸約項目并存，即存在移進(jìn)）移進(jìn)項目和歸約項目并存，即存在移進(jìn)歸約沖突；歸約沖突；（2）多個歸約項目并存，即存在歸約）多個歸約項目并存，即存在歸約歸約沖突。

48、歸約沖突。 如果一個文法如果一個文法G滿足上述條件，也就是它的每個滿足上述條件，也就是它的每個LR(0)項目集項目集中都不含有沖突的項目，則稱中都不含有沖突的項目，則稱G為為LR(0)文法。文法。 顯然，只有當(dāng)一個文法是顯然，只有當(dāng)一個文法是LR(0)文法時，才能對它構(gòu)造不含沖文法時，才能對它構(gòu)造不含沖突動作的突動作的LR(0)分析表來。分析表來。 為了方便起見，我們用整數(shù)為了方便起見，我們用整數(shù)0，1，2， 表示狀態(tài)表示狀態(tài)I0 , I1, I2, ;分析表的內(nèi)容由兩部分組成，一部分為動作分析表的內(nèi)容由兩部分組成，一部分為動作(ACTION)表，表，它表示當(dāng)前狀態(tài)下所面臨的輸入符號應(yīng)做的動作

49、是移進(jìn)、歸約、它表示當(dāng)前狀態(tài)下所面臨的輸入符號應(yīng)做的動作是移進(jìn)、歸約、接受或出錯。另一部分為狀態(tài)轉(zhuǎn)移（接受或出錯。另一部分為狀態(tài)轉(zhuǎn)移（GOTO)表，它表示在當(dāng)前狀表，它表示在當(dāng)前狀態(tài)下面臨文法符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài)，相當(dāng)于識別活前綴的態(tài)下面臨文法符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài)，相當(dāng)于識別活前綴的有限自動機有限自動機DFA的狀態(tài)轉(zhuǎn)換矩陣。分析表的行標(biāo)為狀態(tài)號，動作的狀態(tài)轉(zhuǎn)換矩陣。分析表的行標(biāo)為狀態(tài)號，動作表的列標(biāo)為只包含終結(jié)符和表的列標(biāo)為只包含終結(jié)符和“#”；狀態(tài)轉(zhuǎn)移表的列標(biāo)為；狀態(tài)轉(zhuǎn)移表的列標(biāo)為非終結(jié)符非終結(jié)符，而將其有關(guān)終結(jié)符的各列并入到而將其有關(guān)終結(jié)符的各列并入到ACTION表的各列中去，也就

50、是表的各列中去，也就是把當(dāng)前狀態(tài)下面臨終結(jié)符應(yīng)作的動作和狀態(tài)轉(zhuǎn)移用同一數(shù)組元素把當(dāng)前狀態(tài)下面臨終結(jié)符應(yīng)作的動作和狀態(tài)轉(zhuǎn)移用同一數(shù)組元素表示表示，以便節(jié)省存儲空間。，以便節(jié)省存儲空間。 構(gòu)造構(gòu)造LR(0)分析表的算法為：分析表的算法為： (1)對于每一項目集對于每一項目集Ii中形如中形如A . .X 的項目，且有的項目，且有GO(Ii,X)=Ij, 若若X為一終結(jié)符號為一終結(jié)符號 a 時，則置時，則置ACTIONi,a=Sj; 若若X為一非終結(jié)符號時，則僅置為一非終結(jié)符號時，則僅置GOTOi,X=j (2)若若Ii中有歸約項目中有歸約項目A . . ,設(shè)設(shè)A 為文法第為文法第j個產(chǎn)生式，則對個產(chǎn)

51、生式，則對 文法的任何終結(jié)符和文法的任何終結(jié)符和“#”（均記為（均記為a）置）置ACTIONi,a=Rj(3)若接受項目若接受項目SS . .屬于屬于Ii ,則置則置ACTIONi,#=acc。(4)在分析表中在分析表中,凡不能按上述規(guī)則填入信息的元素凡不能按上述規(guī)則填入信息的元素,均置為均置為“出錯出錯”。 如上例可構(gòu)造分析表為：如上例可構(gòu)造分析表為： ACTION GOTO a b c d # S A B0 S4 S5 S6 1 2 3 Acc R1 R1 R1 R1 R1 R2 R2 R2 R2 R2 S4 S5 S6 7 9 R4 R4 R4 R4 R4 R6 R6 R6 R6 R6

52、S8 R3 R3 R3 R3 R3 S1010 R5 R5 R5 R5 R5 構(gòu)造構(gòu)造LR(0)分析表的算法為：分析表的算法為： (1)對于每一項目集對于每一項目集Ii中形如中形如A . .X 的項目，且有的項目，且有GO(Ii,X)=Ij, 若若X為一終結(jié)符號為一終結(jié)符號 a 時，則置時，則置ACTIONi,a=Sj; 若若X為一非終結(jié)符號時，則僅置為一非終結(jié)符號時，則僅置GOTOi,X=j (2)若若Ii中有歸約項目中有歸約項目A . . ,設(shè)設(shè)A 為文法第為文法第j個產(chǎn)生式，則對個產(chǎn)生式，則對 文法的任何終結(jié)符和文法的任何終結(jié)符和“#”（均記為（均記為a）置）置ACTIONi,a=Rj6

53、、LR(0)分析器的工作過程分析器的工作過程 對于一個文法構(gòu)造了它的對于一個文法構(gòu)造了它的LR(0)分析表就可以在分析表就可以在LR分析器的總分析器的總控程序控制下對輸入串進(jìn)行分析，即控程序控制下對輸入串進(jìn)行分析，即根據(jù)輸入串當(dāng)前符號根據(jù)輸入串當(dāng)前符號a和分析和分析棧棧頂狀態(tài)棧棧頂狀態(tài)i查找分析表應(yīng)采取的動作查找分析表應(yīng)采取的動作，對狀態(tài)棧和符號棧進(jìn)行相，對狀態(tài)棧和符號棧進(jìn)行相應(yīng)的操作即應(yīng)的操作即移進(jìn)、歸約、接受或報錯移進(jìn)、歸約、接受或報錯。具體為：。具體為：1）若）若ACTIONi,a=Sj, aVT,則把則把a移進(jìn)移進(jìn)符號棧，符號棧，j移進(jìn)移進(jìn)狀態(tài)棧。狀態(tài)棧。2）若）若ACTIONi,a=

54、Rj，aVT或或#，則用第，則用第j個產(chǎn)生式個產(chǎn)生式歸約歸約。并將。并將兩個棧的指針減去兩個棧的指針減去K(其中其中K為第為第j 個產(chǎn)生式右部的串長度個產(chǎn)生式右部的串長度），并），并把產(chǎn)生式的左部符號把產(chǎn)生式的左部符號A壓入符號棧，同時用符號對（壓入符號棧，同時用符號對（ Si-k,A)去查去查GOTO表（其中表（其中Si-k為狀態(tài)棧當(dāng)前棧頂元素，若為狀態(tài)棧當(dāng)前棧頂元素，若GOTOSi-k,A=j,則則j壓入狀態(tài)棧，壓入狀態(tài)棧，使得兩個棧內(nèi)的元素一樣多使得兩個棧內(nèi)的元素一樣多。3）若）若ACTIONi,a=Acc,（此時（此時a應(yīng)為應(yīng)為“#”號），則表明號），則表明分析成功分析成功，結(jié)束分析。

55、結(jié)束分析。4）若）若ACTIONi,a=空白，轉(zhuǎn)空白，轉(zhuǎn)出錯處理出錯處理。7.3 SLR(1)分析分析 因大多數(shù)程序設(shè)計語言的文法不能滿足因大多數(shù)程序設(shè)計語言的文法不能滿足LR(0)文法的條件，即文法的條件，即使是描述一個變量這樣簡單的文法也不是使是描述一個變量這樣簡單的文法也不是LR(0)文法。因此下面文法。因此下面將介紹對將介紹對LR(0)規(guī)范族中有沖突的項目集（狀態(tài)）用向前查規(guī)范族中有沖突的項目集（狀態(tài)）用向前查 看一看一個（輸入）符號的辦法進(jìn)行處理，以解決沖突。這種分析方法個（輸入）符號的辦法進(jìn)行處理，以解決沖突。這種分析方法因為只對有沖突的狀態(tài)才向前查看一個符號，以確定做什么動作因為

56、只對有沖突的狀態(tài)才向前查看一個符號，以確定做什么動作，故稱這種分析方法為簡單的，故稱這種分析方法為簡單的LR(1)分析法，用分析法，用SLR(1)表示。表示。 假定有一個假定有一個LR(0)規(guī)范族中含有如下項目集規(guī)范族中含有如下項目集(狀態(tài)狀態(tài))I: I=X . .b ,A . ., B . .其中其中 , , , 為符號串，為符號串，bVT, 顯然顯然I中含有移進(jìn)中含有移進(jìn)歸約和歸約歸約和歸約歸約沖突。那么只要在所有歸約沖突。那么只要在所有含有含有A或或B的句型中，直接跟在的句型中，直接跟在A或或B后面的可能終結(jié)符集合后面的可能終結(jié)符集合FOLLOW(A)和和FOLLOW(B)互不相交，且都

57、不包含互不相交，且都不包含b,即只要滿即只要滿足：足： FOLLOW(A)FOLLOW(B)=FOLLOW(A)b=FOLLOW(B)b=即：即：FOLLOW(A)FOLLOW(B)b = 那么，當(dāng)在狀態(tài)那么，當(dāng)在狀態(tài)I面臨某輸入符號為面臨某輸入符號為a時，則動作可由下述規(guī)定時，則動作可由下述規(guī)定決策：決策：1）若）若a = b,則移進(jìn)。則移進(jìn)。2）若）若a FOLLOW(A),則用產(chǎn)生式則用產(chǎn)生式A 歸約。歸約。3）若）若a FOLLOW(B),則用產(chǎn)生式則用產(chǎn)生式B 歸約。歸約。 一般地，對于一般地，對于LR(0)規(guī)范族的一個項目集規(guī)范族的一個項目集I可能含有多個移進(jìn)項可能含有多個移進(jìn)項目

58、和多個歸約項目，我們可假設(shè)項目集目和多個歸約項目，我們可假設(shè)項目集I中有中有m個移進(jìn)項目：個移進(jìn)項目： A1 1. b1 1, A2 2. b2 2, , Am m. bm m;同時含同時含有有n個歸約項目：個歸約項目：B1 1. , B2 2. , Bn n. ,只要集合只要集合b1, b2,bm和和FOLLOW(B1),FOLLOW(B2),FOLLOW(Bn)兩兩交集都為空，則我們?nèi)钥捎蒙鲜鰵w則來解決沖突：兩兩交集都為空，則我們?nèi)钥捎蒙鲜鰵w則來解決沖突： 1）若）若ab1, b2,bm,則移進(jìn)。則移進(jìn)。 2）若）若aFOLLOW(Bi),i=1,n,則用則用Bi i進(jìn)行歸約。進(jìn)行歸約。

59、3）此外，則報錯。）此外，則報錯。所以，我們只須把構(gòu)造所以，我們只須把構(gòu)造LR(0)分析表算法中的規(guī)則分析表算法中的規(guī)則(2)，即：，即：(2)若若Ii中有歸約項目中有歸約項目A . . ,設(shè)設(shè)A 為文法第為文法第j個產(chǎn)生式，則對個產(chǎn)生式，則對 文法的任何終結(jié)符和文法的任何終結(jié)符和“#”（均記為（均記為a）置）置ACTIONi,a=Rj 。修改為修改為：即：即：(1)對于每一項目集對于每一項目集Ii中形如中形如A.X的項目，且有的項目，且有GO(Ii,X)=Ij, 若若X為一終結(jié)符號為一終結(jié)符號a時，則置時，則置ACTIONI,a=Sj; 若若X為一非終結(jié)符號時，則僅置為一非終結(jié)符號時，則僅置

60、GOTOi,X=j；(2)若歸約項目若歸約項目A .屬于屬于Ii,設(shè)設(shè)A 為文法第為文法第j個行產(chǎn)生式，則個行產(chǎn)生式，則對任何屬于對任何屬于FOLLOW(A)的輸入符號的輸入符號a,置置ACTIONi,a=Rj；(3)若接受項目若接受項目S S.屬于屬于Ii ,則置則置ACTIONi,#=acc。(4) 在分析表在分析表,凡不能按上述規(guī)則填入信息的元素凡不能按上述規(guī)則填入信息的元素,均置為均置為“出出錯錯”。（2）若歸約項目）若歸約項目A .屬于屬于Ii,設(shè)設(shè)A 為文法第為文法第j個行產(chǎn)生式，則個行產(chǎn)生式，則對任何屬于對任何屬于FOLLOW(A)的輸入符號的輸入符號a,置置ACTIONi,a=

61、Rj 。其余的規(guī)則不變，就得到了構(gòu)造其余的規(guī)則不變，就得到了構(gòu)造SLR(1)分析表的算法。分析表的算法。例如：例如： 有算術(shù)表達(dá)式文法有算術(shù)表達(dá)式文法GE,構(gòu)造其構(gòu)造其LR(0)項目規(guī)范簇項目規(guī)范簇和和SLR(1)分析表。分析表。GE: EE+T T TT*F F F(E) i解：解：1、拓廣文法、拓廣文法為為GS :(0) SEEE+TETTT*FTFF(E)(1) Fi2、再求識別、再求識別G的全部活前綴的的全部活前綴的DFA（即（即LR(0)的項目集規(guī)范簇）：的項目集規(guī)范簇）：I0: S.E GO(I0,E)=I1 E.E+T GO(I0,E)=I1 E.T GO(I0,T)=I2 T.

62、T*F GO(I0,T)=I2 T.F GO(I0,F)=I3 F.(E) GO(I0,( )=I4 F.i GO(I0,i )=I5I1: SE. EE.+T GO(I1,+)=I6I2: ET. TT.*F GO(I2,*)=I7I3: TF.I4: F(.E) GO(I4,E)=I8 E.E+T GO(I4,E)=I8 E.T GO(I4,T)=I2 T.T*F GO(I4,T)=I2 T.F GO(I4,F)=I3 F.(E) GO(I4,( )=I4 F.i GO(I4,i)=I5I5: Fi.I6: EE+.T GO(I6,T)=I9 T.T*F GO(I6,T)=I9 T.F G

63、O(I6,F)=I3 F.(E) GO(I6,( )=I4 F.i GO(I6,i)=I5I7: TT*.F GO(I7,F)=I10 F.(E) GO(I7,( )=I4 F.i GO(I7,i )=I5I8: F(E.) GO(I8,) )=I11 EE.+T GO(I8,+)=I6I9: EE+T. TT.*F GO(I9,)=I7I10: TT*F.I11: F(E).DFA:I0: S.E E.E+T E.T T.T*F T.F F.(E) F.iI2: ET. TT.*FI5: Fi.I1: SE. EE.+TI3: TF.I4: F(.E) E.E+T E.T T.T*F T.F

64、 F.(E) F.iI7: TT*.F F.(E) F.iI6: EE+.T T.T*F T.F F.(E) F.iI8: F(E.) EE.+TI11: F(E).I9: EE+T . TT.*FI10: TT*F.i*EF(TiiiT+)*F(+F(E(FT圖圖7.6 識別文法識別文法GS活前綴的活前綴的DFA3、解決沖突、解決沖突 可以看到，項目可以看到，項目I1， I2， I9中都同時包含有移進(jìn)項目和歸約中都同時包含有移進(jìn)項目和歸約項目。存在移進(jìn)項目。存在移進(jìn)歸約沖突，因而該文法不屬于歸約沖突，因而該文法不屬于LR(0)文法，故不文法，故不能構(gòu)造能構(gòu)造LR(0)分析表。分析表。 FOL

65、LOW(S)= # FOLLOW(E)= +，)，# FOLLOW(T)= +，*，)，# FOLLOW(F)= +，*，)，# 現(xiàn)在分別考慮上述三個沖突項目中的沖突是否能用現(xiàn)在分別考慮上述三個沖突項目中的沖突是否能用SLR(1)方法方法解決。解決。 在在I1中，由于中，由于FOLLOW(S)=#).而而SE.是唯一的接受項目，是唯一的接受項目，所以當(dāng)且僅當(dāng)遇到句子的結(jié)束符所以當(dāng)且僅當(dāng)遇到句子的結(jié)束符“#”號時才被接受號時才被接受,又因又因#+=，故，故I1中的沖突可解決。中的沖突可解決。 對于對于I2,因因FOLLOW(E)=+,),#*=,因此當(dāng)面臨輸入符號為因此當(dāng)面臨輸入符號為“+”，“

66、 ）”或或“#”號時，則用產(chǎn)生式號時，則用產(chǎn)生式ET歸約。當(dāng)面臨輸入歸約。當(dāng)面臨輸入符為符為“*”時，則移進(jìn)；其它情況則報錯。時，則移進(jìn)；其它情況則報錯。 對于對于I9,與與I2類似，當(dāng)面臨輸入符號為類似，當(dāng)面臨輸入符號為“+”，“）”或或“#”時，時，則用產(chǎn)生式則用產(chǎn)生式EE+T歸約；當(dāng)面臨輸入符號為歸約；當(dāng)面臨輸入符號為“*”時，則移進(jìn)，時，則移進(jìn)，其余情況報錯。其余情況報錯。4、構(gòu)造、構(gòu)造SLR(1)分析表分析表對于上述三個沖突項目等均可用對于上述三個沖突項目等均可用SLR(1)方法解決沖突。因此該方法解決沖突。因此該文法是文法是SLR(1)文法。我們可造成其相應(yīng)的文法。我們可造成其相應(yīng)的SLR(1)分析表為：分析表為： i + * （ ） # E T F0 S5 S4 1 2 31 S6 acc2 R2 S7 R2 R23 R4 R4 R4 R44 S5 S4 8 2 35 R6 R6 R6 R66 S5 S4 9 37 S5 S4 108 S6 S11 9 R1 S7 R1 R110 R3 R3 R3 R311 R5 R5 R5 R5下面給定輸入串下面給定輸入串i+i*i #