教育學(xué)第7章LR分析法課件

1、第七章 LR 分析法 1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技術(shù)。 LR(K)分析是指自左向右掃描和自底向上的語(yǔ)法分析，且在分析的每一步，只須根據(jù)分析棧中當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再向前查看K個(gè)輸入符號(hào)，就能確定相當(dāng)于某一產(chǎn)生式右部符號(hào)的句柄是否已在分析棧的頂部形成。從而也就可以確定所應(yīng)采取的分析動(dòng)作（是移進(jìn)輸入符號(hào)還是按某產(chǎn)生式進(jìn)行歸約）。當(dāng)前掃描到Xn+1,向前查看k個(gè)符號(hào)，來(lái)確定是把Xn+1移進(jìn)棧，還是把XiXn作為句柄進(jìn)行歸約。1） 要?dú)w約時(shí)，則根據(jù)某產(chǎn)生式UXiXi+1Xn進(jìn)行歸約： #X1X2Xi-1UXn+1Xn+2Xn+k#例：#X1X

2、2Xi Xn Xn+1Xn+2Xn+kXn+k+1#棧頂?shù)?頁(yè)，共85頁(yè)。（續(xù)頁(yè)）LR(0) 表示在每一步分析時(shí)都不用向前輸入符號(hào)LR(1) 表示在每一步分析時(shí)都向前看一個(gè)輸入符號(hào)來(lái)決定當(dāng) 前的動(dòng)作。SLR(1) 表示簡(jiǎn)單的LR(1)，即只在動(dòng)作不唯一的地方向前看一個(gè)符號(hào)，在動(dòng)作唯一時(shí)則不向前看輸入符號(hào)。2） 要移進(jìn)時(shí)，即把Xn+1進(jìn)棧，并讀下一符號(hào)： #X1X2XiXnXn+1 Xn+2Xn+k# 在棧中當(dāng)前掃描符棧頂?shù)?頁(yè)，共85頁(yè)。7.1 LR分析概論一 .LR分析器的邏輯結(jié)構(gòu)及工作過(guò)程 從邏輯上來(lái)說(shuō)，一個(gè)LR分析器如圖7.1 所示。 輸入串#aia1SpX1#S1S0XmSm總 控 程

3、 序輸出ACTION 表GOTO 表其中S棧為狀態(tài)棧 X棧為符號(hào)棧棧產(chǎn)生式 表圖7.1 LR分析器的邏輯結(jié)構(gòu)第3頁(yè)，共85頁(yè)。 即一個(gè)LR(k)分析器主要由：總控程序，分析棧（狀態(tài)棧和符號(hào)棧）輸入隊(duì)列和分析表組成。一般來(lái)說(shuō)所有LR分析器的總控程序基本上是大同小異。只有分析表各不相同。一般主要討論三種不同的分析表的構(gòu)造方法。 第一種稱(chēng)為規(guī)范LR分析表構(gòu)造法。用此法構(gòu)造的分析表功能最強(qiáng)而且也適合于很多文法，但實(shí)現(xiàn)代價(jià)比較高。 第二種稱(chēng)為簡(jiǎn)單LR(即SLR)分析表構(gòu)造法。這是一種比較容易實(shí)現(xiàn)的方法。但SLR分析表的功能太弱，而且對(duì)某些文法可能根本就構(gòu)造不出相應(yīng)的SLR分析表。 第三種稱(chēng)為向前LR（即

4、LALR）分析表構(gòu)造法。這種方法構(gòu)造的分析表功能介于規(guī)范LR分析表SLR分析表之間。這種表適用于絕大多數(shù)程序語(yǔ)言的文法。而且也可以設(shè)法有效的實(shí)現(xiàn)。第4頁(yè)，共85頁(yè)。二、LR 分析器的分析過(guò)程如下：1.首先將初始狀態(tài) S0及句子的左界限#分別壓入狀態(tài)棧和符號(hào)棧中。 則用棧頂狀態(tài)Sm和當(dāng)前掃描符 ai組成符號(hào)對(duì)（ Sm, ai)去查分析動(dòng)作表，根據(jù)ACTIONSm, ai的指示完成相應(yīng)的分析動(dòng)作。表中每一表元素所規(guī)定的動(dòng)作僅能是下列四種動(dòng)作之一： S0S1 S2 Sm Sm+1 ai+1 ai+2 an # # X1 X2 Xm ai 2.設(shè)在分析中的某一步，分析棧及余留的輸入串為如下格局： S0

5、S1 Sm ai ai+1an #X1 Xm （1） ACTIONSm, ai= Sm+1 （移進(jìn)）表明句柄尚未在棧頂形成，此時(shí)正期待移進(jìn)輸入符號(hào)以便形成句柄。故將當(dāng)前的輸入符號(hào)和表元素Sm+1分別壓入棧中，有第5頁(yè)，共85頁(yè)。（2） ACTIONSm, ai= Rj (歸約） 表明此時(shí)應(yīng)按文法的第j個(gè)產(chǎn)生式A Xm-k+1Xm-k+2 Xm進(jìn)行歸約。即棧頂符號(hào)串Xm-k+1Xm-k+2 Xm已成為當(dāng)前句型的句柄。所謂按第j個(gè)產(chǎn)生式歸約，就是將分析棧中從頂向下的k個(gè)符號(hào)退棧，然后將文法符號(hào)A壓入符號(hào)棧中。此時(shí)分析的格局為： S0S1 Sm-k ai ai+1an # # X1 Xm-k A 然

6、后以（ Sm-k,A)去查狀態(tài)轉(zhuǎn)移表，設(shè)GOTOSm-k,A= Sl ,則將此新?tīng)顟B(tài)壓入狀態(tài)棧中，則有如下格局： S0S1 Sm-k Sl ai ai+1an # # X1 Xm-k A 第6頁(yè)，共85頁(yè)。（3） ACTIONSm, ai=acc （接受） 表明當(dāng)前的輸入串已被成功地分析完畢，應(yīng)停止分析器的工作。其中Z為文法開(kāi)始符號(hào)S為使ACTIONS ，#=acc的 唯一狀態(tài)（接受狀態(tài)）（4） ACTIONSm, ai=ERROR（空白）。 表明當(dāng)前的輸入串中含有錯(cuò)誤，也應(yīng)終止當(dāng)前的分析工作。轉(zhuǎn)出錯(cuò)處理。3. 重復(fù)上述第2步的工作，直到分析棧頂出現(xiàn)“接受狀態(tài)”或“出錯(cuò)狀態(tài)“為止。對(duì)接受狀態(tài)，

7、分析棧的格局為： S0 S # # Z 第7頁(yè)，共85頁(yè)。例：有文法GS:1：SaAcBe 2：Ab 3：AAb 4：Bd其ACTION表和GOTO表為：考察對(duì)輸入串a(chǎn)bbcde# 的分析過(guò)程。r1r1r1r1r1r1r4r4r4r4r4r4S9r3r3r3r3r3r37S8r2r2r2r2r2r2S6S53S4acc1S2BAS#dbecaGOTOACTION0123456789 S a A c B e A b d b圖7.2 abbcde# 的語(yǔ)法樹(shù)第8頁(yè)，共85頁(yè)。對(duì)輸入串a(chǎn)bbcde# 的分析過(guò)程為： ACTION GOTO步驟 狀態(tài)棧 符號(hào)棧 輸入流 分析動(dòng)作 下一狀態(tài)1 0 # a

8、bbcde# S2(0,a)2 02 #a bbcde# S4(2,b)3 024 #ab bcde# r2(4,b) GOTO2,A=34 023 #aA 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#的分析

9、過(guò)程第9頁(yè)，共85頁(yè)。LR分析過(guò)程中的性質(zhì)與特點(diǎn)：棧中的文法符號(hào)串并上剩余的輸入串構(gòu)成一個(gè)右句型（規(guī)范句型）當(dāng)該右句型的句柄出現(xiàn)在棧頂時(shí)，歸約，否則，移進(jìn)棧中的文法符號(hào)串是當(dāng)前句型的前綴，該前綴不包含句型句柄后面的符號(hào)，稱(chēng)之為活前綴（Viable Prefixes）第10頁(yè)，共85頁(yè)。7.2 LR(0) 分析表的構(gòu)造為了給出構(gòu)造LR(0)分析表的算法，引出一些術(shù)語(yǔ)：1、規(guī)范句型的活前綴 前綴：一個(gè)符號(hào)串的前綴是指該串的任意首部（包括）。例如 abc的前綴有： ,a,ab,abc abcd的前綴有：,a,ab,abc,abcd 由此可知，對(duì)于符號(hào)串 而言，其前綴的數(shù)量為+1。例：有文法GS:Sa

10、AcBe1 Ab2 這里在每條產(chǎn)生式后加上了產(chǎn) AAb3 生式的序號(hào)i當(dāng)進(jìn)行推導(dǎo)時(shí)把 Bd4 序號(hào)帶上，以便說(shuō)明問(wèn)題。對(duì)輸入串a(chǎn)bbcde進(jìn)行推導(dǎo)如下（最右推導(dǎo)）： S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1由此可知，abbcde是該文法的句子。由于LR方法是自底向上的分析，故應(yīng)采用歸約。第11頁(yè)，共85頁(yè)。最左歸約為： ab2b3cd4e1 用2式歸約 aAb3cd4e1 3 aAcd4e1 4 aAcBe1 1 S其中表示歸約符 從歸約的過(guò)程可看出，每次歸約時(shí)，歸約前和歸約后的被歸約部分與剩余部分合起來(lái)僅構(gòu)成文法的規(guī)范句型，而用哪個(gè)產(chǎn)生式歸約僅取決于當(dāng)前句型

11、的前面部分；X1X2Xnp 其中Xi為文法的符號(hào)，p為第p個(gè)產(chǎn)生式序號(hào)。 如上例中每次歸約前句型的前面部分為： ab2 aAb3 aAcd4 aAcBe1我們把規(guī)范句型的這種前端部分的串稱(chēng)為可歸前綴。實(shí)際上，它們恰好是符號(hào)棧棧頂形成句柄時(shí)符號(hào)棧中的內(nèi)容。SaAcBe1Ab2AAb3Bd4第12頁(yè)，共85頁(yè)。 這是因?yàn)橐坏┚湫偷木浔诜?hào)棧頂形成，將會(huì)立即被歸約之故。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的任何符號(hào)）的前綴稱(chēng)之為可歸前綴。 對(duì)各規(guī)范句型有前綴：ab2b3cd4e1 ,a,abaAb3cd4e1 ,a,aA,aAbaAcd4e1 ,a,aA,aAc,aAcdaAcBe1

12、,a,aA,aAc,aAcB,aAcBe可以發(fā)現(xiàn)前綴a,ab,aA,aAc是多個(gè)規(guī)范句型的前綴，因此我們可進(jìn)一步把形成可歸前綴前和形成可歸前綴時(shí)的所有規(guī)范句型的前綴都稱(chēng)為活前綴?？蓺w前綴：是指規(guī)范句型的一個(gè)前綴，這種前綴包含句柄且不含句柄之后的任何符號(hào)?；钋熬Y：可歸前綴的任意首部。特指在分析過(guò)程中對(duì)于在棧頂形成句柄之前和恰好形成句柄時(shí)，每一步中符號(hào)棧中的那些符號(hào)組成的符號(hào)串。第13頁(yè)，共85頁(yè)?；钋熬Y定義： 在前面例中對(duì)輸入串a(chǎn)bbcde的歸約分析過(guò)程中，在規(guī)范歸約過(guò)程中的任何時(shí)候只要已分析過(guò)的部分即在符號(hào)棧中的符號(hào)串均為規(guī)范句型的活前綴，它表明輸入串的已被分析過(guò)的部分是該文法某規(guī)范句型的一個(gè)

13、正確部分。由此可形式地定義活前綴如下： 定義 7.1：若S * A 是 文法G中的一個(gè)規(guī)范推導(dǎo)， 如果符號(hào)串是的前綴，則稱(chēng)是G的一個(gè)活前綴。 其中 S為文法開(kāi)始符號(hào)。 RR第14頁(yè)，共85頁(yè)。LR分析分析過(guò)程可以看作是識(shí)別文法規(guī)范句型活前綴的過(guò)程。只要每一時(shí)刻棧中的文法符號(hào)串是某規(guī)范句型的活前綴，則說(shuō)明已分析的部分是正確的一個(gè)文法的規(guī)范句型的所有活前綴構(gòu)成一個(gè)語(yǔ)言，而且是正規(guī)語(yǔ)言，可以用一個(gè) DFA 來(lái)識(shí)別第15頁(yè)，共85頁(yè)。例子：文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d014235769SabAbcBed8*第16頁(yè)，共85頁(yè)。每個(gè)狀態(tài)都是活前綴的識(shí)別態(tài)，

14、雙圈狀態(tài)是可歸前綴（句柄）識(shí)別態(tài)，標(biāo)識(shí)了*的狀態(tài)是句子識(shí)別態(tài)分析句子的過(guò)程可以看作在上面這個(gè) DFA 上運(yùn)行的過(guò)程014235769SabAbcBed8*(1) S aAcBe(2) A b(3) A Ab(4) B d第17頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S2014235769SabAbcBed*8第18頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S4014235769SabAbcBed8*第19頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43

15、#0a2b4bcde#R23014235769SabAbcBed8*第20頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S6014235769SabAbcBed8*第21頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S65#0a2A3b6cde#R33014235769SabAbcBed8*第22頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO3#0a2b4bcde#R23

16、4#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S5*014235769SabAbcBed8第23頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO4#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S8*014235769SabAbcBed8第24頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO5#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R47014235769SabAbcBed8*第25頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTI

17、ONGOTO6#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S9014235769SabAbcBed8*第26頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO7#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R11014235769SabAbcBed8*第27頁(yè)，共85頁(yè)。例子：步驟棧輸入串ACTIONGOTO8#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R1111#0S1#Acc014235769SabAbcB

18、ed8*第28頁(yè)，共85頁(yè)。2、LR（0）項(xiàng)目 由上述分析和定義可知，活前綴與句柄間的關(guān)系不外乎下述 三種情況：（1）活前綴中已含有句柄的全部符號(hào)（句柄的最后符號(hào)就是 活前綴的最后符號(hào)）。（2）活前綴中只含有句柄的前部分符號(hào)（句柄的最左子串 為活前綴的最右子串）。（3）活前綴中全然不包含句柄的任何符號(hào)。第一種情況表明：此時(shí)某一產(chǎn)生式A的右部已出現(xiàn)在符號(hào)棧頂，因此此時(shí)相應(yīng)的分析動(dòng)作應(yīng)當(dāng)是用此產(chǎn)生式進(jìn)行歸約。第二種情況表明：形如A12的產(chǎn)生式的 右部子串已在符號(hào)棧棧頂，如1，正期待著從余留的輸入串中看到能由推出的 符號(hào)串，即期待2 進(jìn)棧以便能進(jìn)行歸約。故此時(shí)分析動(dòng)作是“移進(jìn)”當(dāng)前輸入符號(hào)。第三種情

19、況則意味著：期望從余留輸入串中能看到由某產(chǎn)生式A的右部，即所代表的符號(hào)串(即句柄) 。所以此時(shí)分析的動(dòng)作也是讀輸入符進(jìn)符號(hào)棧。第29頁(yè)，共85頁(yè)。 為了刻畫(huà)在分析過(guò)程中，文法的一個(gè)產(chǎn)生式右部符號(hào)串有多大部分已被識(shí)別，我們可在該產(chǎn)生式的右部相應(yīng)位置上加一個(gè)圓點(diǎn)“.”，來(lái)指示位置，標(biāo)明在“.”前的部分已被識(shí)別。如上述三種情況，可分別標(biāo)注為：A.； A1 .2 ; A. 。 我們把右部某位置上標(biāo)有圓點(diǎn)的產(chǎn)生式稱(chēng)為相應(yīng)文法的一個(gè)LR(0)項(xiàng)目。特別地，對(duì)形如A 的產(chǎn)生式，相應(yīng)的LR(0)項(xiàng)目表示為A.。顯然不同的LR(0)項(xiàng)目，反映了分析過(guò)程中符號(hào)棧頂?shù)牟煌闆r。例如：產(chǎn)生式SaAcBe對(duì)應(yīng)有六個(gè)項(xiàng)目

20、。0 S.aAcBe1 Sa.AcBe2 SaA.cBe3 SaAc.Be4 SaAcB.e5 SaAcBe.第30頁(yè)，共85頁(yè)。例如：產(chǎn)生式SaAcBe對(duì)應(yīng)有六個(gè)項(xiàng)目。0 S.aAcBe1 Sa.AcBe2 SaA.cBe3 SaAc.Be4 SaAcB.e5 SaAcBe. 一個(gè)產(chǎn)生式可對(duì)應(yīng)的項(xiàng)目的數(shù)量為它的右部符號(hào)串長(zhǎng)度加1，值得注意的是對(duì)空產(chǎn)生式，即A僅有項(xiàng)目A. 每個(gè)項(xiàng)目的含義與圓點(diǎn)的位置有關(guān)。概括地說(shuō)，圓點(diǎn)左邊的子串表示在分析過(guò)程的某一時(shí)刻用該產(chǎn)生式歸約時(shí)句柄中已識(shí)別過(guò)的部分，圓點(diǎn)右邊的子串表示待識(shí)別的部分。 文法的全部LR(0)項(xiàng)目將是構(gòu)造識(shí)別它的所有活前綴的有窮自動(dòng)機(jī)的基礎(chǔ)。第

21、31頁(yè)，共85頁(yè)。3、LR(0)項(xiàng)目的分類(lèi)：例：考慮文法GS=(S,A,B, a,b,c,d,P,S),構(gòu)造其分析表：其中P: (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d解：求該文法的項(xiàng)目集規(guī)范族C：為了方便起見(jiàn)，我們?cè)谏鲜鑫姆ㄖ幸鹨粋€(gè)新的開(kāi)始符號(hào)S,且將S S作為第0個(gè)產(chǎn)生式添加到文法G中，從而得到了所謂G的拓廣文法G。顯然L(G)=L(G)，則對(duì)于文法G，其LR(0)項(xiàng)目為： 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

22、. 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第32頁(yè)，共85頁(yè)。如前所述，由于不同的項(xiàng)目反映了分析過(guò)程中棧頂?shù)牟煌闆r，因此，我們可根據(jù)它們不同的作用，將一個(gè)文法的全部LR(0)項(xiàng)目進(jìn)行分類(lèi)：移進(jìn)項(xiàng)目：A a待約項(xiàng)目：A B歸約項(xiàng)目： A 接受項(xiàng)目： S S 圓點(diǎn)的左部表示分析過(guò)程中的某時(shí)刻用該產(chǎn)生式歸約時(shí)句柄已識(shí)別過(guò)的部分，圓點(diǎn)右部表示待識(shí)別部分第33頁(yè)，共85頁(yè)。4、構(gòu)造識(shí)別活

23、前綴的DFA 在LR方法實(shí)際過(guò)程中，并不是去直接分析符號(hào)棧中的符號(hào)是否已形成句柄，但它給我們一個(gè)啟示，我們可以把終結(jié)符和非終結(jié)符都可看成一個(gè)有限自動(dòng)機(jī)的輸入符號(hào)，每把一個(gè)符號(hào)進(jìn)棧時(shí)看成已識(shí)別過(guò)該符號(hào)，而狀態(tài)進(jìn)行轉(zhuǎn)換（到下一狀態(tài)），當(dāng)識(shí)別到可歸前綴時(shí)相當(dāng)于棧頂已形成了句柄，則認(rèn)為到達(dá)了識(shí)別句柄的終態(tài)。 在作出文法的全部LR(0)項(xiàng)目之后，現(xiàn)在將用它們來(lái)構(gòu)造識(shí)別全部活前綴的DFA。這種DFA中的中每一個(gè)狀態(tài)由若干個(gè)LR(0)項(xiàng)目所組成的集合（稱(chēng)為項(xiàng)目集）來(lái)表示。 下面以上例中的文法為例來(lái)說(shuō)明構(gòu)造DFA的方法。 G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B a

24、Bd (6)B d第34頁(yè)，共85頁(yè)。首先我們用I0表示這個(gè)DFA的初態(tài)，它預(yù)示著整個(gè)分析過(guò)程的開(kāi)始，并且期待著將給定的輸入串逐步歸約為文法的開(kāi)始符號(hào)S。或者反過(guò)來(lái)說(shuō)，我們所期待的是，從使用產(chǎn)生式SS開(kāi)始，能夠逐漸推導(dǎo)出所給定的輸入串。因此，我們應(yīng)將項(xiàng)目S.S列入項(xiàng)目集I0之中。換言之，也就是我們正期待將要掃描的輸入串正好就是能由S推導(dǎo)出的任何終結(jié)符串。然而，我們不能從輸入串中直接讀出非終結(jié)符號(hào)S，因此我們也應(yīng)將項(xiàng)目S.A和S.B加入I0中。由于A和B同樣是非終結(jié)符，所以也應(yīng)將A.aAb和A.c和B.aBb, B.d加入I0中。G：(0)SS (1)S A (2)S B (3)A aAb (4

25、)A c (5)B aBd (6)B d 由于最后加入I0的項(xiàng)目在圓點(diǎn)之后已都是終結(jié)符了，故I0已經(jīng)“封閉”，宣告項(xiàng)目集I0構(gòu)造結(jié)束。 這樣，表示初態(tài)的項(xiàng)目集I0將由如下項(xiàng)目組成：I0 : S.S, S.A, S.B, A.aAb, A.c, B.aBd, B.d第35頁(yè)，共85頁(yè)。I0 : S.S, S.A, S.B, A.aAb, A.c, B.aBd, B.d 我們將LR(0)項(xiàng)目S.S稱(chēng)為項(xiàng)目集I0的基本項(xiàng)目，上述從S.S出發(fā)構(gòu)造項(xiàng)目集I0的過(guò)程，可用一個(gè)對(duì)其基本項(xiàng)目集S .S的閉包運(yùn)算，即closure(S.S)來(lái)表示。一般地，設(shè)I為項(xiàng)目集，I的閉包c(diǎn)losure(I)的定義為：Cl

26、osure(I)=IA.AGK .Aclosure(I)V*V*故構(gòu)造closure(I)的算法為：1）I中的每一個(gè)項(xiàng)目都屬于closure(I);2）若形如K.A的項(xiàng)目屬于I，且A是文法的一個(gè)產(chǎn)生式， 則關(guān)于產(chǎn)生式A的任何形如A.的項(xiàng)目也應(yīng)加到closure(I)中 （若它們不在closure(I)中）；3）重復(fù)上述過(guò)程，直至不再有新的項(xiàng)目加入到closure(I)中為 止。 第36頁(yè)，共85頁(yè)。 有了初態(tài)項(xiàng)目集I0之后，我們來(lái)說(shuō)明如何確定從I0可能轉(zhuǎn)移到的下一狀態(tài)。設(shè)A為一文法符號(hào)(AV)，若I0中有圓點(diǎn)位于A左邊的項(xiàng)目K .A(其中可能為)，則當(dāng)分析器從輸入串識(shí)別出(即移進(jìn)或歸約出)文法

27、符號(hào)A后，分析器將進(jìn)入它的下一狀態(tài)。設(shè)此狀態(tài)為Ii ，顯然Ii中必含有全部形如KA .的項(xiàng)目，我們將這樣的項(xiàng)目稱(chēng)為K .A的后繼項(xiàng)目。對(duì)于每一個(gè)文法符號(hào)A，如果存在這樣的后繼項(xiàng)目，則可能不只一個(gè)，設(shè)其組成集合J，則J中的每個(gè)項(xiàng)目都是項(xiàng)目集Ii的基本項(xiàng)目，因此，按照與上面構(gòu)造項(xiàng)目集I0相類(lèi)試的討論，我們有： Ii =closure(J) 為了指明Ii是“I0關(guān)于文法符號(hào)A的后繼狀態(tài)”這一事實(shí)，我們可定義一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)： GO(I0,A)=closure(J) = Ii 其中，I是當(dāng)前狀態(tài)，A為文法符號(hào)，J是I中所有形如K.A的項(xiàng)目之后繼項(xiàng)目KA.所組成的集合，而closure(J)就是項(xiàng)目集I

28、（即狀態(tài)I)關(guān)于符號(hào)A的后繼項(xiàng)目集（即后繼狀態(tài)）。 第37頁(yè)，共85頁(yè)。 狀態(tài)轉(zhuǎn)移函數(shù)： GO(I0,A)=closure(J) = Ii 其中，I是當(dāng)前狀態(tài)，A為文法符號(hào)，J是I中所有形如K.A的項(xiàng)目之后繼項(xiàng)目KA.所組成的集合，而closure(J)就是項(xiàng)目集I（即狀態(tài)I)關(guān)于符號(hào)A的后繼項(xiàng)目集（即后繼狀態(tài)）。即： GO(I,A)=closure(所有形如KA .的項(xiàng)目K .AI) 對(duì)于上例，我們有： I1 =GO(I0,S)=closure(SS.) I1 : SS . ; I2 =GO(I0,A)=closure(SA.) I2 :SA . ; I3 =GO(I0,B)=closure

29、(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 d第38頁(yè)，共85頁(yè)。I4 : Aa.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. 此時(shí)，我們求出了I0的全部后繼項(xiàng)目集I1, I2,I3,I4,I5,I6,而I1, I2,I3,I5,I6均無(wú)后繼項(xiàng)目集，僅I4有后繼項(xiàng)目集： I7 =GO

30、(I4,A)=closure(AaA.b)=AaA.b I9 =GO(I4,B)=closure(BaB.d)=BaB.d此外，還有： GO(I4,a)=closure(Aa.Ab, Ba.Bd)= I4 GO(I4,c)=closure(Ac.)= I5 GO(I4,d)=closure(Bd.)= I6 這些項(xiàng)目集均不產(chǎn)生新的項(xiàng)目集。另外還有:G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d第39頁(yè)，共85頁(yè)。 I8 =GO(I7,b)=closure(AaAb.)=AaAb. I10 =GO(I9,b)=closure(BaBd.

31、)=BaBd.此時(shí)I8 ， I10也已無(wú)后繼項(xiàng)目集，故我們已求出文法GS的全部項(xiàng)目集I0 I10 。 通常我們將這些項(xiàng)目集的全體稱(chēng)為文法GS的LR(0)項(xiàng)目集規(guī)范族，并記為C=(I0, I1, I10) 于是，我們所要構(gòu)成的識(shí)別文法GS的全部活前綴的DFA為 M=(C,V,GO, I0,Z) 其中CM的狀態(tài)集，即文法GS的LR(0)項(xiàng)目集規(guī)范族, C=(I0, I1, I10); V M的字母表，即V=S,S,A,B,a,b,c,d； GOM的映射函數(shù)，即上面定義的狀態(tài)轉(zhuǎn)移函數(shù)GO； I0M的唯一初態(tài)； ZM的終態(tài)集， ZC，為規(guī)范族中所有含有歸約項(xiàng)目的 那些項(xiàng)目集。第40頁(yè)，共85頁(yè)。DFA

32、: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項(xiàng)目集規(guī)范族第41頁(yè)，共85頁(yè)。DFA:即：I0I1I2I3I4I5I6I7I9I8I10SABacdcdABbdG：(0)SS (1)S A (2)S

33、 B (3)A aAb (4)A c (5)B aBd (6)B da圖7.5 識(shí)別文法GS活前綴的DFA第42頁(yè)，共85頁(yè)。5、LR(0)分析表的構(gòu)造 對(duì)于一個(gè)文法G的拓廣文法G，當(dāng)識(shí)別它的全部活前綴的DFA作出之后，我們可以據(jù)此構(gòu)造相應(yīng)的LR(0)分析表了。 然而，要注意的是，用前述方法所構(gòu)造的每一個(gè)LR(0)項(xiàng)目集實(shí)質(zhì)上表征了在分析過(guò)程中可能出現(xiàn)的一種分析狀態(tài)；再根據(jù)前面對(duì)LR(0)項(xiàng)目的分類(lèi)，項(xiàng)目集中的每一個(gè)項(xiàng)目又與某一種分析動(dòng)作相關(guān)聯(lián)，因此，就要求每一個(gè)項(xiàng)目集中的的諸項(xiàng)目應(yīng)當(dāng)是相容的。所謂相容，是指在一個(gè)項(xiàng)目集中不出現(xiàn)下列的情況：（1）移進(jìn)項(xiàng)目和歸約項(xiàng)目并存，即存在移進(jìn)歸約沖突；（2

34、）多個(gè)歸約項(xiàng)目并存，即存在歸約歸約沖突。 如果一個(gè)文法G滿(mǎn)足上述條件，也就是它的每個(gè)LR(0)項(xiàng)目集中都不含有沖突的項(xiàng)目，則稱(chēng)G為L(zhǎng)R(0)文法。 顯然，只有當(dāng)一個(gè)文法是LR(0)文法時(shí)，才能對(duì)它構(gòu)造不含沖突動(dòng)作的LR(0)分析表來(lái)。第43頁(yè)，共85頁(yè)。 為了方便起見(jiàn)，我們用整數(shù)0，1，2， 表示狀態(tài)I0 , I1, I2, ;分析表的內(nèi)容由兩部分組成，一部分為動(dòng)作(ACTION)表，它表示當(dāng)前狀態(tài)下所面臨的輸入符號(hào)應(yīng)做的動(dòng)作是移進(jìn)、歸約、接受或出錯(cuò)。另一部分為狀態(tài)轉(zhuǎn)移（GOTO)表，它表示在當(dāng)前狀態(tài)下面臨文法符號(hào)時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài)，相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)DFA的狀態(tài)轉(zhuǎn)換矩陣。分析表的

35、行標(biāo)為狀態(tài)號(hào)，動(dòng)作表的列標(biāo)為只包含終結(jié)符和“#”；狀態(tài)轉(zhuǎn)移表的列標(biāo)為非終結(jié)符，而將其有關(guān)終結(jié)符的各列并入到ACTION表的各列中去，也就是把當(dāng)前狀態(tài)下面臨終結(jié)符應(yīng)作的動(dòng)作和狀態(tài)轉(zhuǎn)移用同一數(shù)組元素表示，以便節(jié)省存儲(chǔ)空間。 構(gòu)造LR(0)分析表的算法為： (1)對(duì)于每一項(xiàng)目集Ii中形如A.X的項(xiàng)目，且有GO(Ii,X)=Ij, 若X為一終結(jié)符號(hào) a 時(shí)，則置ACTIONi,a=Sj; 若X為一非終結(jié)符號(hào)時(shí)，則僅置GOTOi,X=j (2)若Ii中有歸約項(xiàng)目A. ,設(shè)A為文法第j個(gè)產(chǎn)生式，則對(duì) 文法的任何終結(jié)符和“#”（均記為a）置ACTIONi,a=Rj第44頁(yè)，共85頁(yè)。(3)若接受項(xiàng)目SS .

36、屬于Ii ,則置ACTIONi,#=acc。(4)在分析表中,凡不能按上述規(guī)則填入信息的元素,均置為“出錯(cuò)”。 如上例可構(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 S8 R3 R3 R3 R3 R3 S1010 R5 R5 R5 R5 R5 構(gòu)造LR(0)分析表的算法為： (1)對(duì)于每一項(xiàng)目集Ii中形如A.X的項(xiàng)目，且有GO(Ii,X)=Ij, 若X為一終結(jié)符號(hào) a 時(shí)，則置ACTI

37、ONi,a=Sj; 若X為一非終結(jié)符號(hào)時(shí)，則僅置GOTOi,X=j (2)若Ii中有歸約項(xiàng)目A. ,設(shè)A為文法第j個(gè)產(chǎn)生式，則對(duì) 文法的任何終結(jié)符和“#”（均記為a）置ACTIONi,a=Rj第45頁(yè)，共85頁(yè)。6、LR(0)分析器的工作過(guò)程 對(duì)于一個(gè)文法構(gòu)造了它的LR(0)分析表就可以在LR分析器的總控程序控制下對(duì)輸入串進(jìn)行分析，即根據(jù)輸入串當(dāng)前符號(hào)a和分析棧棧頂狀態(tài)i查找分析表應(yīng)采取的動(dòng)作，對(duì)狀態(tài)棧和符號(hào)棧進(jìn)行相應(yīng)的操作即移進(jìn)、歸約、接受或報(bào)錯(cuò)。具體為：1）若ACTIONi,a=Sj, aVT,則把a(bǔ)移進(jìn)符號(hào)棧，j移進(jìn)狀態(tài)棧。2）若ACTIONi,a=Rj，aVT或#，則用第j個(gè)產(chǎn)生式歸約

38、。并將兩個(gè)棧的指針減去K(其中K為第j 個(gè)產(chǎn)生式右部的串長(zhǎng)度），并把產(chǎn)生式的左部符號(hào)A壓入符號(hào)棧，同時(shí)用符號(hào)對(duì)（ Si-k,A)去查GOTO表（其中Si-k為狀態(tài)棧當(dāng)前棧頂元素，若GOTOSi-k,A=j,則j壓入狀態(tài)棧，使得兩個(gè)棧內(nèi)的元素一樣多。3）若ACTIONi,a=Acc,（此時(shí)a應(yīng)為“#”號(hào)），則表明分析成功，結(jié)束分析。4）若ACTIONi,a=空白，轉(zhuǎn)出錯(cuò)處理。第46頁(yè)，共85頁(yè)。7.3 SLR(1)分析 因大多數(shù)程序設(shè)計(jì)語(yǔ)言的文法不能滿(mǎn)足LR(0)文法的條件，即使是描述一個(gè)變量這樣簡(jiǎn)單的文法也不是LR(0)文法。因此下面將介紹對(duì)LR(0)規(guī)范族中有沖突的項(xiàng)目集（狀態(tài)）用向前查 看

39、一個(gè)（輸入）符號(hào)的辦法進(jìn)行處理，以解決沖突。這種分析方法因?yàn)橹粚?duì)有沖突的狀態(tài)才向前查看一個(gè)符號(hào)，以確定做什么動(dòng)作，故稱(chēng)這種分析方法為簡(jiǎn)單的LR(1)分析法，用SLR(1)表示。 假定有一個(gè)LR(0)規(guī)范族中含有如下項(xiàng)目集(狀態(tài))I: I=X.b,A., B.其中,為符號(hào)串，bVT, 顯然I中含有移進(jìn)歸約和歸約歸約沖突。那么只要在所有含有A或B的句型中，直接跟在A或B后面的可能終結(jié)符集合FOLLOW(A)和FOLLOW(B)互不相交，且都不包含b,即只要滿(mǎn)足： FOLLOW(A)FOLLOW(B)=FOLLOW(A)b=FOLLOW(B)b=即：FOLLOW(A)FOLLOW(B)b =第47頁(yè)

40、，共85頁(yè)。 那么，當(dāng)在狀態(tài)I面臨某輸入符號(hào)為a時(shí)，則動(dòng)作可由下述規(guī)定決策：1）若a = b,則移進(jìn)。2）若a FOLLOW(A),則用產(chǎn)生式A歸約。3）若a FOLLOW(B),則用產(chǎn)生式B歸約。 一般地，對(duì)于LR(0)規(guī)范族的一個(gè)項(xiàng)目集I可能含有多個(gè)移進(jìn)項(xiàng)目和多個(gè)歸約項(xiàng)目，我們可假設(shè)項(xiàng)目集I中有m個(gè)移進(jìn)項(xiàng)目： A11. b11, A2 2. b22, , Am m. bmm;同時(shí)含有n個(gè)歸約項(xiàng)目：B11. , B2 2. , Bn n. ,只要集合b1, b2,bm和FOLLOW(B1),FOLLOW(B2),FOLLOW(Bn)兩兩交集都為空，則我們?nèi)钥捎蒙鲜鰵w則來(lái)解決沖突： 1）若ab

41、1, b2,bm,則移進(jìn)。 2）若aFOLLOW(Bi),i=1,n,則用Bi i進(jìn)行歸約。 3）此外，則報(bào)錯(cuò)。第48頁(yè)，共85頁(yè)。所以，我們只須把構(gòu)造LR(0)分析表算法中的規(guī)則(2)，即：(2)若Ii中有歸約項(xiàng)目A. ,設(shè)A為文法第j個(gè)產(chǎn)生式，則對(duì) 文法的任何終結(jié)符和“#”（均記為a）置ACTIONi,a=Rj 。修改為：即：(1)對(duì)于每一項(xiàng)目集Ii中形如A.X的項(xiàng)目，且有GO(Ii,X)=Ij, 若X為一終結(jié)符號(hào)a時(shí)，則置ACTIONI,a=Sj; 若X為一非終結(jié)符號(hào)時(shí)，則僅置GOTOi,X=j；(2)若歸約項(xiàng)目A.屬于Ii,設(shè)A為文法第j個(gè)行產(chǎn)生式，則對(duì)任何屬于FOLLOW(A)的輸入

42、符號(hào)a,置ACTIONi,a=Rj；(3)若接受項(xiàng)目S S.屬于Ii ,則置ACTIONi,#=acc。(4) 在分析表,凡不能按上述規(guī)則填入信息的元素,均置為“出錯(cuò)”。（2）若歸約項(xiàng)目A.屬于Ii,設(shè)A為文法第j個(gè)行產(chǎn)生式，則對(duì)任何屬于FOLLOW(A)的輸入符號(hào)a,置ACTIONi,a=Rj 。其余的規(guī)則不變，就得到了構(gòu)造SLR(1)分析表的算法。第49頁(yè)，共85頁(yè)。例如： 有算術(shù)表達(dá)式文法GE,構(gòu)造其LR(0)項(xiàng)目規(guī)范簇和SLR(1)分析表。GE: EE+TT TT*FF F(E) i解：1、拓廣文法為GS :(0) SEEE+TETTT*FTFF(E)Fi第50頁(yè)，共85頁(yè)。2、再求識(shí)

43、別G的全部活前綴的DFA（即LR(0)的項(xiàng)目集規(guī)范簇）：I0: S.E GO(I0,E)=I1 E.E+T GO(I0,E)=I1 E.T GO(I0,T)=I2 T.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.第51頁(yè)，共85頁(yè)。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(I

44、4,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 GO(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).第52頁(yè)，共85頁(yè)。DFA:I0

45、: 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 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 識(shí)別文法GS活前綴的DFA第53頁(yè)，共85頁(yè)。3、解決沖突 可以看到，項(xiàng)目I1， I2， I9中都同時(shí)包含有移進(jìn)項(xiàng)目和歸

46、約項(xiàng)目。存在移進(jìn)歸約沖突，因而該文法不屬于LR(0)文法，故不能構(gòu)造LR(0)分析表。 FOLLOW(S)= # FOLLOW(E)= +，)，# FOLLOW(T)= +，*，)，# FOLLOW(F)= +，*，)，# 現(xiàn)在分別考慮上述三個(gè)沖突項(xiàng)目中的沖突是否能用SLR(1)方法解決。 在I1中，由于FOLLOW(S)=#).而SE.是唯一的接受項(xiàng)目，所以當(dāng)且僅當(dāng)遇到句子的結(jié)束符“#”號(hào)時(shí)才被接受,又因#+=，故I1中的沖突可解決。 對(duì)于I2,因FOLLOW(E)=+,),#*=,因此當(dāng)面臨輸入符號(hào)為“+”，“ ）”或“#”號(hào)時(shí)，則用產(chǎn)生式ET歸約。當(dāng)面臨輸入符為“*”時(shí)，則移進(jìn)；其它情況

47、則報(bào)錯(cuò)。 對(duì)于I9,與I2類(lèi)似，當(dāng)面臨輸入符號(hào)為“+”，“）”或“#”時(shí)，則用產(chǎn)生式EE+T歸約；當(dāng)面臨輸入符號(hào)為“*”時(shí)，則移進(jìn)，其余情況報(bào)錯(cuò)。第54頁(yè)，共85頁(yè)。4、構(gòu)造SLR(1)分析表對(duì)于上述三個(gè)沖突項(xiàng)目等均可用SLR(1)方法解決沖突。因此該文法是SLR(1)文法。我們可造成其相應(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

48、 R3 R311 R5 R5 R5 R5第55頁(yè)，共85頁(yè)。下面給定輸入串i+i*i #，使用上述SLR(1)分析進(jìn)行分析：步 狀態(tài)棧 符號(hào)棧 輸入串 ACTION GOTO1 0 # i+i*i # S52 05 #i +i*i # R6 3 3 03 #F +i*i # R4 24 02 #T +i*i # R2 1 5 01 #E +i*i # S66 016 #E+ i*i # S57 0165 #E+i *i # R6 38 0163 #E+T *i # R4 99 0169 #E+T *i # S710 01697 #E+T* i # S511 016975 #E+T*i # R6

49、 1012 0169710 #E+T*F # R3 913 0169 #E+T # R1 114 01 #E # acc第56頁(yè)，共85頁(yè)。本 章 作 業(yè)P165：題1，題2(1) 第57頁(yè)，共85頁(yè)。7.4 LR(1) 分析 本節(jié)介紹比SLR(1)功能更強(qiáng)的LR(1)分析法。例7.4:有下列文法G,構(gòu)造構(gòu)造識(shí)別文法G的識(shí)別活前綴的有限自動(dòng)機(jī)。(0) SS(1) SaAd(2) SbAc(3) Saec(4) Sbed (5) Ae我們首先用SS作為初態(tài)集的項(xiàng)目，然后用閉包函數(shù)和轉(zhuǎn)換函數(shù)構(gòu)造識(shí)別文法G的識(shí)別活前綴的有限自動(dòng)機(jī)DFA如圖7.7所示。第58頁(yè)，共85頁(yè)。圖 7.7 LR(0)識(shí)別G

50、的活前綴的DFA第59頁(yè)，共85頁(yè)。如圖7.7所示，可以發(fā)現(xiàn)在項(xiàng)目集I5和I7中存在移進(jìn)和歸約沖突。I5：SaecI7：SbedAe Ae而歸約項(xiàng)目左部非終結(jié)符的FOLLOW(A)=c,d在I5中，F(xiàn)OLLOW(A)c=c,dc在I7中，F(xiàn)OLLOW(A) d=c,dd因此I5，I7中沖突不能用SLR(1)方法解決。只能考慮用下面將要介紹的LR(1)方法解決。 第60頁(yè)，共85頁(yè)。由于用SLR(1)方法解決動(dòng)作沖突時(shí)，對(duì)于歸約項(xiàng)目A，只要當(dāng)前面臨輸入符為aFOLLOW(A)時(shí)，就確定采用產(chǎn)生式A進(jìn)行歸約，但是如果棧中的符號(hào)串為，歸約后變?yōu)锳，再移進(jìn)當(dāng)前符a，則棧里變?yōu)锳a，而實(shí)際上Aa未必為文

51、法規(guī)范句型的活前綴。 現(xiàn)在我們?cè)倏磮D7.7在I5，I7項(xiàng)目集中的移進(jìn)-歸約沖突，不能用SLR(1)方法解決的原因如下：I5： Saec 因 AeRRRS SaAdaedRRS Saec(0) S S(1) SaAd(2) SbAc(3) Saec(4) Sbed(5) Ae 這兩個(gè)最右推導(dǎo)已包括了活前綴為a的所有句型，因此，不難看出對(duì)活前綴ae來(lái)說(shuō)，當(dāng)面臨輸入符號(hào)為c時(shí)應(yīng)移進(jìn)，面臨d時(shí)應(yīng)用產(chǎn)生式Ae歸約。因?yàn)?RRS SaAc第61頁(yè)，共85頁(yè)。這說(shuō)明從S出發(fā)不能用最右推導(dǎo)（規(guī)范推導(dǎo)）推出aAc句型，所以aAc不是該文法的規(guī)范句型。回顧LR分析過(guò)程，若輸入符號(hào)串是所給文法的句子，那么分析過(guò)程的

52、任何時(shí)刻在文法符號(hào)棧中的符號(hào)和剩余的輸入串符號(hào)合起來(lái)總是構(gòu)成該文法的規(guī)范句型。 這也說(shuō)明了并不是FOLLOW(A)的每個(gè)元素在含A的所有句型中在A的后面都會(huì)出現(xiàn)，例中d只在規(guī)范句型aAd中A的后面出現(xiàn)，因此面臨輸入符為d才應(yīng)歸約。再看在I7中。I7： Sbed 而 AeRRRSS bAc bec(0) S S(1) SaAd(2) SbAc(3) Saec(4) Sbed(5) AeRRS Sbed 這兩個(gè)最右推導(dǎo)，包含了活前綴為b的所有句型，因此FOLLOW(A)中的c只能跟在句型bAc中A的后面，這樣在I7中當(dāng)面臨輸入符為c時(shí)才能歸約，根據(jù)項(xiàng)目集的構(gòu)造原理有：第62頁(yè)，共85頁(yè)。若AB項(xiàng)目

53、集I，則B(B為一產(chǎn)生式)也包含在I中。不妨考慮，把FIRST()作為用產(chǎn)生式B歸約的搜索符，稱(chēng)為向前搜索符，作為歸約時(shí)查看的符號(hào)集合，用以代替SLR(1)分析中的FOLLOW集，把此搜索符號(hào)的集合也放在相應(yīng)項(xiàng)目的后面，這種處理方法即為L(zhǎng)R(1)方法。 其原因是：一個(gè)非終結(jié)符號(hào)的FOLLOW集合，包含了所有含該非終結(jié)符的任一句型中在該非終結(jié)符后的向前搜索符集合。如在項(xiàng)目集I中有項(xiàng)目：AB， B。當(dāng)分析經(jīng)過(guò)若干步后在項(xiàng)目集J中含有項(xiàng)目B需要用產(chǎn)生式B歸約，這時(shí)向前查看的符號(hào)集合是FIRST()，而FIRST() FOLLOW（B）。第63頁(yè)，共85頁(yè)。7.4.1 LR(1)項(xiàng)目集族的構(gòu)造 一個(gè)L

54、R(1)項(xiàng)目可以看成兩個(gè)部分組成，一部分和LR(0)項(xiàng)目相同部分我們稱(chēng)它為心，另一部分為向前搜索符集合。如讓SS，#屬于初始項(xiàng)目集中，把#號(hào)作為向前搜索符，表示活前綴為(若是有關(guān)S產(chǎn)生式的某一右部)要?dú)w約成S時(shí)，必須面臨輸入符為#號(hào)才行。因此對(duì)初始項(xiàng)目SS，#求閉包后再用轉(zhuǎn)換函數(shù)逐步求出整個(gè)文法的LR(1)項(xiàng)目集族。具體構(gòu)造步驟如下： (1) 構(gòu)造LR(1)項(xiàng)目集的閉包函數(shù)。a) 項(xiàng)目集I的任何項(xiàng)目都屬于CLOSURE(I)；b) 若有項(xiàng)目AB,a屬于CLOSURE(I)，B是文法中的產(chǎn)生式，V*，bFIRST(a)，則B,b也屬于CLOSURE(I)中。c) 重復(fù)b)直到CLOSURE(I)

55、不再增大為止。 第64頁(yè)，共85頁(yè)。(2) 轉(zhuǎn)換函數(shù)的構(gòu)造 LR(1)轉(zhuǎn)換函數(shù)的構(gòu)造與LR(0)的相似，GO(I,X)CLOSURE(J)其中I是LR(1)的項(xiàng)目集，X是文法符號(hào)：J=任何形如AX,a的項(xiàng)目|AX,aI現(xiàn)給出直接由產(chǎn)生式構(gòu)造識(shí)別活前綴的DFA的LR（1）項(xiàng)目集的閉包CLOSURE的算法：function CLOSURE (I)； /* I是項(xiàng)目集*/ J:= I；repeat 對(duì)J中的每個(gè)項(xiàng)目AB,a和產(chǎn)生式 B； ，V*；b FIRST(a), 若B，b不在J中Do 將B，b加到J中 until 再?zèng)]有項(xiàng)目加到J中return J； 第65頁(yè)，共85頁(yè)。對(duì)項(xiàng)目AB,a，計(jì)算B

56、的向前搜索符時(shí)，應(yīng)為FIRST(a)，這是因?yàn)閂*，即可能為，而a是用產(chǎn)生式AB歸約時(shí)的向前搜索符，而現(xiàn)在為，就等于用AB歸約，向前搜索符為a，那么用AB歸約前，必須先用產(chǎn)生式B歸約成B，因此，B的向前搜索符時(shí)也應(yīng)為a。對(duì)文法G的LR(1)項(xiàng)目集族的構(gòu)造仍以SS,#為初態(tài)集的初始項(xiàng)目，然后對(duì)其求閉包和轉(zhuǎn)換函數(shù)，直到項(xiàng)目集不再增大。 也就是對(duì)狀態(tài)I經(jīng)過(guò)符號(hào)X后轉(zhuǎn)向狀態(tài)J，求出J的基本項(xiàng)目后，對(duì)基本項(xiàng)目求閉包即為CLOSURE(J)?，F(xiàn)在我們可以對(duì)上面7.4例中不能用SLR(1)方法解決I5，I7中移進(jìn)-歸約沖突的文法構(gòu)造它的LR(1)項(xiàng)目集規(guī)范族如下：第66頁(yè)，共85頁(yè)。I0：SS,# SaAd

57、,# SbAc,# Saec,#Sbed,#I1：SS,#I2：SaAd,#Saec,# Ae,dI3：SbAc,# Sbed,# Ae,cI4： SaAd,#I5： Saec,# Ae,d I6： SbAc,# I7： Sbed,# Ae,c I8： SaAd,# I9： Saec,# I10：SbAc,# I11：Sbed,# (0) S S(1) SaAd(2) SbAc(3) Saec(4) Sbed(5) Ae第67頁(yè)，共85頁(yè)。這樣LR(1)方法構(gòu)造的項(xiàng)目集規(guī)范族在項(xiàng)目集I5和I7中的移進(jìn)-歸約沖突，由于歸約項(xiàng)目的搜索符集合與移進(jìn)項(xiàng)目的待移進(jìn)符號(hào)不相交，所以在I5中，當(dāng)面臨輸入符為

58、d時(shí)歸約，為c時(shí)移進(jìn)，而在I7中則當(dāng)面臨輸入符為c時(shí)歸約，為d時(shí)移進(jìn)，沖突已全部可以解決，因此該文法為L(zhǎng)R(1)文法。 第68頁(yè)，共85頁(yè)。7.4.2 LR(1)分析表的構(gòu)造 由于一個(gè)LR(1)項(xiàng)目可以看成兩個(gè)部分組成，一部分和LR(0)項(xiàng)目相同部分我們稱(chēng)它為心，另一部分為向前搜索符集合，因而LR(1)分析表的構(gòu)造與LR(0)分析表的構(gòu)造大部分相同，僅對(duì)歸約項(xiàng)目的歸約動(dòng)作取決于該歸約項(xiàng)目的向前搜索符集，只有當(dāng)面臨輸入符屬于向前搜索符的集合，才做歸約動(dòng)作，其它情況均出錯(cuò)。具體構(gòu)造過(guò)程如下：若已構(gòu)造出某文法的LR(1)項(xiàng)目集族C。CI0,I1,In，其中Ik的k為分析器的狀態(tài)，則動(dòng)作ACTION表

59、和狀態(tài)轉(zhuǎn)換GOTO表構(gòu)造方法如下： 第69頁(yè)，共85頁(yè)。(1) 若項(xiàng)目Aa,b屬于Ik，且GO（Ik,a）=Ij，其中aVT,則置ACTIONk,a=Sj。其Sj的含義是把輸入符號(hào)a和狀態(tài)j分別移入文法符號(hào)棧和狀態(tài)棧。(2) 若項(xiàng)目A,a屬于Ik，則置ACTIONk,a= rj 其中aVT，rj 的含義為把當(dāng)前棧頂符號(hào)串歸約為A(即用產(chǎn)生式A歸約)。j為在文法中對(duì)產(chǎn)生式A的編號(hào)。(3) 若項(xiàng)目SS，#屬于Ik，則置ACTIONk，#acc，表示接受。(4) 若GO(Ik，A)Ij，其中AVN，則置GOTOk,Aj。表示轉(zhuǎn)入j狀態(tài)，置當(dāng)前文法符號(hào)棧頂為A，狀態(tài)棧頂為j。(5) 凡不能用規(guī)則(1)

60、(4)填入分析表中的元素，均置“報(bào)錯(cuò)標(biāo)志”。我們用“空白”表示之。 LR(1)分析表的構(gòu)造除 (2) 外，其余同LR(0)或SLR(1)。即 若項(xiàng)目A,a屬于Ik，則置ACTIONk,a= rj。也就是歸約時(shí)向前查看的符號(hào)為向前搜索符。 第70頁(yè)，共85頁(yè)。根據(jù)上述規(guī)則，我們對(duì)7.4例中文法的LR(1)項(xiàng)目集族構(gòu)造其相應(yīng)的LR(1)分析表如表7.10。 狀態(tài)ACTIONGOTOabcde#SA01234567891011 S2S3.S9S10r5.S8r5.S11.S5S7.acc.r1r3r2r41. 46表 7.10 LR(1)分析表 第71頁(yè)，共85頁(yè)。由表7.10可以看出對(duì)LR(1)的