LR 分析法課件

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

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

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

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

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

5、同。一般主要討論三種不同的分析表的構(gòu)造方法。主要討論三種不同的分析表的構(gòu)造方法。 第一種稱為規(guī)范第一種稱為規(guī)范LR分析表構(gòu)造法。用此法構(gòu)造的分析表分析表構(gòu)造法。用此法構(gòu)造的分析表功能最強(qiáng)而且也適合于很多文法，但實(shí)現(xiàn)代價(jià)比較高。功能最強(qiáng)而且也適合于很多文法，但實(shí)現(xiàn)代價(jià)比較高。 第二種稱為簡(jiǎn)單第二種稱為簡(jiǎn)單LR(即即SLR)分析表構(gòu)造法。這是一種比較分析表構(gòu)造法。這是一種比較容易實(shí)現(xiàn)的方法。但容易實(shí)現(xiàn)的方法。但SLR分析表的功能太弱，而且對(duì)某些文法分析表的功能太弱，而且對(duì)某些文法可能根本就構(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ù)程序語(yǔ)言的文法。而且也可以設(shè)法有效的實(shí)現(xiàn)。適用于絕大多數(shù)程序語(yǔ)言的文法。而且也可以設(shè)法有效的實(shí)現(xiàn)。二、二、LR 分析器的分析過(guò)程如下：分析器的分析過(guò)程如下：1.首先將初始狀態(tài)首先將初始狀態(tài) S0及句子的左界限及句子的左界限#分別壓入狀態(tài)棧和符號(hào)棧中。分別壓入狀態(tài)棧和符號(hào)棧中。 則用棧頂狀態(tài)則用棧頂狀態(tài)Sm和當(dāng)前掃描符和當(dāng)前掃描符 ai組成符號(hào)對(duì)（組成符號(hào)對(duì)（ Sm, ai)去查去查分析動(dòng)作表，根據(jù)分析動(dòng)作表，根據(jù)ACTIONSm

7、, ai的指示完成相應(yīng)的分析動(dòng)作。的指示完成相應(yīng)的分析動(dòng)作。表中每一表元素所規(guī)定的動(dòng)作僅能是下列四種動(dòng)作之一：表中每一表元素所規(guī)定的動(dòng)作僅能是下列四種動(dòng)作之一： 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)）表明句柄尚未在棧頂形成，此時(shí)正期待移進(jìn)輸入符號(hào)以便形成表明句柄尚未在棧頂形成，此時(shí)正期待移進(jìn)輸入符號(hào)以便形成句柄。故將當(dāng)前的輸

8、入符號(hào)和表元素句柄。故將當(dāng)前的輸入符號(hào)和表元素Sm+1分別壓入棧中，有分別壓入棧中，有（2） ACTIONSm, ai= Rj (歸約）歸約） 表明此時(shí)應(yīng)按文法的第表明此時(shí)應(yīng)按文法的第j個(gè)產(chǎn)生式個(gè)產(chǎn)生式A Xm-k+1Xm-k+2 Xm進(jìn)行歸約。即棧頂符號(hào)串進(jìn)行歸約。即棧頂符號(hào)串Xm-k+1Xm-k+2 Xm已成為當(dāng)前句型的句已成為當(dāng)前句型的句柄。所謂按第柄。所謂按第j個(gè)產(chǎn)生式歸約，就是將分析棧中從頂向下的個(gè)產(chǎn)生式歸約，就是將分析棧中從頂向下的k個(gè)符個(gè)符號(hào)退棧，然后將文法符號(hào)號(hào)退棧，然后將文法符號(hào)A壓入符號(hào)棧中。此時(shí)分析的格局為：壓入符號(hào)棧中。此時(shí)分析的格局為： 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為文法開始符號(hào)為文法開始符號(hào)S為使為使ACTIONS ，#=acc的的 唯一狀態(tài)（接受狀態(tài)）唯一狀態(tài)（接受狀態(tài)）（4） AC

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

11、r1r1r4r4r4r4r4r4S9r3r3r3r3r3r37S8r2r2r2r2r2r2S6S53S4acc1S2BAS#dbecaGOTOACTION0123456789 S a A c B e e A b d b圖圖7.2 abbcde# 的語(yǔ)法樹的語(yǔ)法樹對(duì)輸入串對(duì)輸入串a(chǎn)bbcde# 的分析過(guò)程為：的分析過(guò)程為： ACTION GOTO步驟步驟 狀態(tài)棧狀態(tài)棧 符號(hào)棧符號(hào)棧 輸入流輸入流 分析動(dòng)作分析動(dòng)作 下一狀態(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#的分析過(guò)程的分析過(guò)程 LR分析過(guò)程中的性質(zhì)與特點(diǎn)：分析過(guò)程中的性質(zhì)與特點(diǎn)：n棧中的文法符號(hào)串并上剩余的輸入串構(gòu)成一個(gè)右句型（規(guī)范句型）n當(dāng)該右句型的句柄出現(xiàn)在

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

14、其前綴的數(shù)量為+1。例：有文法例：有文法GS:SaAcBe e1 Ab2 這里在每條產(chǎn)生式后加上了產(chǎn)這里在每條產(chǎn)生式后加上了產(chǎn) AAb3 生式的序號(hào)生式的序號(hào)i當(dāng)進(jìn)行推導(dǎo)時(shí)把當(dāng)進(jìn)行推導(dǎo)時(shí)把 Bd4 序號(hào)帶上，以便說(shuō)明問(wèn)題。序號(hào)帶上，以便說(shuō)明問(wèn)題。對(duì)輸入串對(duì)輸入串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其中其中表示歸約符表示歸約符 從歸約的過(guò)程可看出，每次歸約時(shí)，歸約前和歸約后的被從歸約的過(guò)程可看出，每次歸約時(shí)，歸約前和歸約后的被歸約部分與剩余部分合起來(lái)僅構(gòu)成文法的規(guī)范句型，而用哪個(gè)歸約部分與剩余部分合起來(lái)僅構(gòu)成文法的規(guī)范句型，而用哪個(gè)產(chǎn)生式歸約僅取決于當(dāng)前句型的前面部分；產(chǎn)生式歸約僅取決于當(dāng)前句型的前面部分；X1X2Xnp 其中其中Xi為文法的符號(hào)，為文法的符號(hào)，p為第為第p個(gè)產(chǎn)生式序號(hào)。個(gè)產(chǎn)生式序號(hào)。 如上例中每次歸約前句型的前面部分為：如上例中每次歸約前句型的前面部

16、分為： ab2 aAb3 aAcd4 aAcBe e1我們把規(guī)范句型的這種前端部分的串稱為可歸我們把規(guī)范句型的這種前端部分的串稱為可歸前綴。實(shí)際上，它們恰好是符號(hào)棧棧頂形成句前綴。實(shí)際上，它們恰好是符號(hào)棧棧頂形成句柄時(shí)符號(hào)棧中的內(nèi)容。柄時(shí)符號(hào)棧中的內(nèi)容。SaAcBee1Ab2AAb3Bd4 這是因?yàn)橐坏┚湫偷木浔诜?hào)棧頂形成，將會(huì)立即被歸約這是因?yàn)橐坏┚湫偷木浔诜?hào)棧頂形成，將會(huì)立即被歸約之故。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的之故。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的任何符號(hào)）的前綴稱之為任何符號(hào)）的前綴稱之為可歸前綴可歸前綴。 對(duì)各規(guī)范句型有前綴：對(duì)各規(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是多個(gè)規(guī)范句型的前綴，因此我們可進(jìn)是多個(gè)規(guī)范句型的前綴，因此我們可進(jìn)一步一步把形成可歸前綴前和形成可歸前綴時(shí)的所有規(guī)范句型的前綴把形成可歸前綴前和形成可歸前綴時(shí)的所有規(guī)范句型的前綴都稱為都稱為活前綴活前綴。可歸前綴：可歸前綴：是指規(guī)范句型的一個(gè)前綴，這種前綴包含句柄且不是指規(guī)范句型的一個(gè)前綴，這種前綴包含句柄且不含句柄之后的任何符號(hào)。含句柄之后的任何符號(hào)?；钋熬Y：活前綴：

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

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

20、2) A b(3) A Ab(4) B d014235769SabAbcBed8*n每個(gè)狀態(tài)都是活前綴的識(shí)別態(tài)，雙圈狀態(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 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）項(xiàng)目）項(xiàng)目 由上述分析和定義可知，活前綴與句柄間的關(guān)系不外乎下由

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

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

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

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

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

29、動(dòng)機(jī)的基礎(chǔ)。自動(dòng)機(jī)的基礎(chǔ)。3、LR(0)項(xiàng)目的分類：項(xiàng)目的分類：例：考慮文法例：考慮文法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解：求該文法的項(xiàng)目集規(guī)范族解：求該文法的項(xiàng)目集規(guī)范族C：為了方便起見，我們?cè)谏鲜鑫姆ㄖ幸鹨粋€(gè)新的開始符號(hào)為了方便起見，我們?cè)谏鲜鑫姆ㄖ幸鹨粋€(gè)新的開始符號(hào)S,且將且將S S作為第作為第0個(gè)產(chǎn)生式添加到文法個(gè)產(chǎn)生式添加到文法G中，從而得到了所謂中，從而得到了所謂G的拓廣文法的拓廣文法G。顯然。顯然L(G)=L(G)，則對(duì)于文法，則

30、對(duì)于文法G，其，其LR(0)項(xiàng)目為：項(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 . . 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如前所述，由于不同的項(xiàng)目反映了分析過(guò)程中棧頂?shù)牟煌闆r，如前

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

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

33、項(xiàng)目集）來(lái)表示。項(xiàng)目所組成的集合（稱為項(xiàng)目集）來(lái)表示。 下面以上例中的文法為例來(lái)下面以上例中的文法為例來(lái)說(shuō)明構(gòu)造說(shuō)明構(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表示這個(gè)表示這個(gè)DFADFA的初態(tài)，它的初態(tài)，它預(yù)示著整個(gè)分析過(guò)程的開始，并且期待著將預(yù)示著整個(gè)分析過(guò)程的開始，并且期待著將給定的輸入串逐步歸約為文法的開始符號(hào)給定的輸入串逐步歸約為文法的開始符號(hào)SS。或者反過(guò)來(lái)說(shuō)，我們所期待的是，從使用產(chǎn)或者反過(guò)來(lái)說(shuō)，我們所期待的是，從使用產(chǎn)生式生式SSSS開始，能夠逐漸推導(dǎo)出所給

34、定的開始，能夠逐漸推導(dǎo)出所給定的輸入串。因此，我們應(yīng)將項(xiàng)目輸入串。因此，我們應(yīng)將項(xiàng)目S.SS.S列入項(xiàng)列入項(xiàng)目集目集I I0 0之中。換言之，也就是我們正期待將之中。換言之，也就是我們正期待將要掃描的輸入串正好就是能由要掃描的輸入串正好就是能由SS推導(dǎo)出的任推導(dǎo)出的任何終結(jié)符串。何終結(jié)符串。然而，我們不能從輸入串中直然而，我們不能從輸入串中直接讀出非終結(jié)符號(hào)接讀出非終結(jié)符號(hào)S S，因此我們也應(yīng)將項(xiàng)目，因此我們也應(yīng)將項(xià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的項(xiàng)目在圓點(diǎn)之后已都是終結(jié)符了，故的項(xiàng)目在圓點(diǎn)之后已都是終結(jié)符了，故I I0 0已經(jīng)已經(jīng)“封閉封閉”，宣告項(xiàng)目集，宣告項(xiàng)目集I I0 0構(gòu)造結(jié)束。構(gòu)造結(jié)束。 這樣，表示初態(tài)的項(xiàng)目集這樣，表示初態(tài)的項(xiàng)目集I I0 0將由如下項(xiàng)目組成：將由如下項(xiàng)目組成：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)項(xiàng)目項(xiàng)目S.S稱為稱為項(xiàng)目集項(xiàng)目集I I0的基本項(xiàng)目的基本項(xiàng)目，上述從，上述從S. .S出發(fā)構(gòu)造項(xiàng)目集出發(fā)構(gòu)造項(xiàng)目集I I0的過(guò)程，可用一個(gè)對(duì)其基本項(xiàng)目集的過(guò)程，可用一個(gè)對(duì)其基本項(xiàng)目集S . .S的閉包運(yùn)算，即的閉包運(yùn)算，即closure(S. .S)來(lái)表示。來(lái)表示。一般地，設(shè)一般地，設(shè)I為項(xiàng)目集，為項(xiàng)目集，I的閉包的閉包c(diǎn)losure(I)的定義為：的定義為：Closure(I)=IA. . A GK . .A closure

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

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

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

40、中所有形如K .A 的項(xiàng)目之后繼項(xiàng)目的項(xiàng)目之后繼項(xiàng)目K A. 所組成的集合，而所組成的集合，而closure(J)就是項(xiàng)就是項(xiàng)目集目集I（即狀態(tài)（即狀態(tài)I)關(guān)于符號(hào)關(guān)于符號(hào)A的后繼項(xiàng)目集（即后繼狀態(tài)）。的后繼項(xiàng)目集（即后繼狀態(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為文法符號(hào)，為文法符號(hào)，J是是I中所有形如中所有形如K . .A 的項(xiàng)目之后繼項(xiàng)目的項(xiàng)目之后繼項(xiàng)目K A. . 所組成的集合，而所組成的集合，而closure(J)就是項(xiàng)目就是項(xiàng)目集集I（即狀態(tài)（即狀態(tài)I)關(guān)于符號(hào)關(guān)于符號(hào)A的后繼項(xiàng)目集（即后繼狀態(tài)

41、）。的后繼項(xiàng)目集（即后繼狀態(tài)）。即：即： GO(I,A)=closure(所有形如所有形如K A . . 的項(xiàng)目的項(xiàng)目 K . .A I) 對(duì)于上例，我們有：對(duì)于上例，我們有： 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. 此時(shí)，我們求出了此時(shí)，我們求出了I0的全部后繼項(xiàng)目集的全部后繼項(xiàng)目集I1, I2,I3,I4,I5,I6,而而I1, I2,I3,I5,I6均無(wú)后繼項(xiàng)目集，僅均無(wú)后繼項(xiàng)目集，僅I4有后繼項(xiàng)目集：有后繼項(xiàng)目集： 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 這些項(xiàng)目集均不產(chǎn)生新的項(xiàng)目集。另外還有這些項(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 I8 =GO(I7,b)=closure(AaAb.)=AaAb. I10 =GO(I9,b)=closure(BaBd.)=BaBd.此時(shí)此時(shí)I8 ， I10也已無(wú)后繼項(xiàng)目集，故我們已求出文法也已無(wú)后繼項(xiàng)目集，故我們已求出文法GS的全部的全部項(xiàng)目集項(xiàng)目集I0 I10 。 通常

44、我們將這些項(xiàng)目集的全體稱為文法通常我們將這些項(xiàng)目集的全體稱為文法GS的的LR(0)項(xiàng)目集規(guī)范項(xiàng)目集規(guī)范族，并記為族，并記為C=(I0, I1, I10) 于是，我們所要構(gòu)成的識(shí)別文法于是，我們所要構(gòu)成的識(shí)別文法GS的全部活前綴的的全部活前綴的DFA為為 M=(C,V,GO, I0,Z) 其中其中CM的狀態(tài)集，即文法的狀態(tài)集，即文法GS的的LR(0)項(xiàng)目集規(guī)范族項(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ù)的映射函數(shù)，即上面定義的狀態(tài)轉(zhuǎn)移函數(shù)GO； I0M的唯一初態(tài)；的唯一初態(tài)； Z

45、M的終態(tài)集，的終態(tài)集， Z C，為規(guī)范族中所有含有歸約項(xiàng)目的，為規(guī)范族中所有含有歸約項(xiàng)目的 那些項(xiàng)目集。那些項(xiàng)目集。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項(xiàng)目集規(guī)范族項(xiàng)目集規(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 識(shí)別文法識(shí)別文法GS活前綴的活前綴的DFA5、LR(0)分析表的構(gòu)造分析表的構(gòu)造 對(duì)于一個(gè)文法對(duì)于一個(gè)文法G的拓廣文法的拓廣文法G，當(dāng)識(shí)別它的全部活前綴的，當(dāng)識(shí)別它的全部活前綴的DFA作出之后，我們可以據(jù)此構(gòu)造相應(yīng)的作出之后，我們可以據(jù)此構(gòu)造相應(yīng)的LR(0)分析表了。分析表了。 然而，要注意的是，用前述方法所構(gòu)造的每一個(gè)然而，要注意的是，用前述方法所構(gòu)造的每一個(gè)LR(0)項(xiàng)目集項(xiàng)目集實(shí)質(zhì)上表

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

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

49、是移進(jìn)、歸約、它表示當(dāng)前狀態(tài)下所面臨的輸入符號(hào)應(yīng)做的動(dòng)作是移進(jìn)、歸約、接受或出錯(cuò)。另一部分為狀態(tài)轉(zhuǎn)移（接受或出錯(cuò)。另一部分為狀態(tài)轉(zhuǎn)移（GOTO)表，它表示在當(dāng)前狀表，它表示在當(dāng)前狀態(tài)下面臨文法符號(hào)時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài)，相當(dāng)于識(shí)別活前綴的態(tài)下面臨文法符號(hào)時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài)，相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)有限自動(dòng)機(jī)DFA的狀態(tài)轉(zhuǎn)換矩陣。分析表的行標(biāo)為狀態(tài)號(hào)，動(dòng)作的狀態(tài)轉(zhuǎn)換矩陣。分析表的行標(biāo)為狀態(tài)號(hào)，動(dòng)作表的列標(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)作的動(dòng)作和狀態(tài)轉(zhuǎn)移用同一數(shù)組元素把當(dāng)前狀態(tài)下面臨終結(jié)符應(yīng)作的動(dòng)作和狀態(tài)轉(zhuǎn)移用同一數(shù)組元素表示表示，以便節(jié)省存儲(chǔ)空間。，以便節(jié)省存儲(chǔ)空間。 構(gòu)造構(gòu)造LR(0)分析表的算法為：分析表的算法為： (1)對(duì)于每一項(xiàng)目集對(duì)于每一項(xiàng)目集Ii中形如中形如A . .X 的項(xiàng)目，且有的項(xiàng)目，且有GO(Ii,X)=Ij, 若若X為一終結(jié)符號(hào)為一終結(jié)符號(hào) a 時(shí)，則置時(shí)，則置ACTIONi,a=Sj; 若若X為一非終結(jié)符號(hào)時(shí)，則僅置為一非終結(jié)符號(hào)時(shí)，則僅置GOTOi,X=j (2)若若Ii中有歸約項(xiàng)目中有歸約項(xiàng)目A . . ,設(shè)設(shè)A 為文法第為文法第j個(gè)產(chǎn)生式，則對(duì)個(gè)產(chǎn)

51、生式，則對(duì) 文法的任何終結(jié)符和文法的任何終結(jié)符和“#”（均記為（均記為a）置）置ACTIONi,a=Rj(3)若接受項(xiàng)目若接受項(xiàng)目SS . .屬于屬于Ii ,則置則置ACTIONi,#=acc。(4)在分析表中在分析表中,凡不能按上述規(guī)則填入信息的元素凡不能按上述規(guī)則填入信息的元素,均置為均置為“出錯(cuò)出錯(cuò)”。 如上例可構(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)對(duì)于每一項(xiàng)目集對(duì)于每一項(xiàng)目集Ii中形如中形如A . .X 的項(xiàng)目，且有的項(xiàng)目，且有GO(Ii,X)=Ij, 若若X為一終結(jié)符號(hào)為一終結(jié)符號(hào) a 時(shí)，則置時(shí)，則置ACTIONi,a=Sj; 若若X為一非終結(jié)符號(hào)時(shí)，則僅置為一非終結(jié)符號(hào)時(shí)，則僅置GOTOi,X=j (2)若若Ii中有歸約項(xiàng)目中有歸約項(xiàng)目A . . ,設(shè)設(shè)A 為文法第為文法第j個(gè)產(chǎn)生式，則對(duì)個(gè)產(chǎn)生式，則對(duì) 文法的任何終結(jié)符和文法的任何終結(jié)符和“#”（均記為（均記為a）置）置ACTIONi,a=Rj6

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

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

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

56、只對(duì)有沖突的狀態(tài)才向前查看一個(gè)符號(hào)，以確定做什么動(dòng)作，故稱這種分析方法為簡(jiǎn)單的，故稱這種分析方法為簡(jiǎn)單的LR(1)分析法，用分析法，用SLR(1)表示。表示。 假定有一個(gè)假定有一個(gè)LR(0)規(guī)范族中含有如下項(xiàng)目集規(guī)范族中含有如下項(xiàng)目集(狀態(tài)狀態(tài))I: I=X . .b ,A . ., B . .其中其中 , , , 為符號(hào)串，為符號(hào)串，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面臨某輸入符號(hào)為面臨某輸入符號(hào)為a時(shí)，則動(dòng)作可由下述規(guī)定時(shí)，則動(dòng)作可由下述規(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 歸約。歸約。 一般地，對(duì)于一般地，對(duì)于LR(0)規(guī)范族的一個(gè)項(xiàng)目集規(guī)范族的一個(gè)項(xiàng)目集I可能含有多個(gè)移進(jìn)項(xiàng)可能含有多個(gè)移進(jìn)項(xiàng)目

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

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

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

61、Rj 。其余的規(guī)則不變，就得到了構(gòu)造其余的規(guī)則不變，就得到了構(gòu)造SLR(1)分析表的算法。分析表的算法。例如：例如： 有算術(shù)表達(dá)式文法有算術(shù)表達(dá)式文法GE,構(gòu)造其構(gòu)造其LR(0)項(xiàng)目規(guī)范簇項(xiàng)目規(guī)范簇和和SLR(1)分析表。分析表。GE: EE+T T TT*F F F(E) i解：解：1、拓廣文法、拓廣文法為為GS :(0) SEEE+TETTT*FTFF(E)(1) Fi2、再求識(shí)別、再求識(shí)別G的全部活前綴的的全部活前綴的DFA（即（即LR(0)的項(xiàng)目集規(guī)范簇）：的項(xiàng)目集規(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 識(shí)別文法識(shí)別文法GS活前綴的活前綴的DFA3、解決沖突、解決沖突 可以看到，項(xiàng)目可以看到，項(xiàng)目I1， I2， I9中都同時(shí)包含有移進(jìn)項(xiàng)目和歸約中都同時(shí)包含有移進(jìn)項(xiàng)目和歸約項(xiàng)目。存在移進(jìn)項(xiàng)目。存在移進(jìn)歸約沖突，因而該文法不屬于歸約沖突，因而該文法不屬于LR(0)文法，故不文法，故不能構(gòu)造能構(gòu)造LR(0)分析表。分析表。 FOL

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

66、 ）”或或“#”號(hào)時(shí)，則用產(chǎn)生式號(hào)時(shí)，則用產(chǎn)生式ET歸約。當(dāng)面臨輸入歸約。當(dāng)面臨輸入符為符為“*”時(shí)，則移進(jìn)；其它情況則報(bào)錯(cuò)。時(shí)，則移進(jìn)；其它情況則報(bào)錯(cuò)。 對(duì)于對(duì)于I9,與與I2類似，當(dāng)面臨輸入符號(hào)為類似，當(dāng)面臨輸入符號(hào)為“+”，“）”或或“#”時(shí)，時(shí)，則用產(chǎn)生式則用產(chǎn)生式EE+T歸約；當(dāng)面臨輸入符號(hào)為歸約；當(dāng)面臨輸入符號(hào)為“*”時(shí)，則移進(jìn)，時(shí)，則移進(jìn)，其余情況報(bào)錯(cuò)。其余情況報(bào)錯(cuò)。4、構(gòu)造、構(gòu)造SLR(1)分析表分析表對(duì)于上述三個(gè)沖突項(xiàng)目等均可用對(duì)于上述三個(gè)沖突項(xiàng)目等均可用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 #