武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌.ppt

《武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《武漢理工大學(xué)計(jì)算機(jī)科學(xué)系陳天煌.ppt（41頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

2、n+k#,（續(xù)頁）,LR(0) 表示在每一步分析時(shí)都不用向前輸入符號 LR(1) 表示在每一步分析時(shí)都向前看一個(gè)輸入符號來決定當(dāng) 前的動(dòng)作。 SLR(1) 表示簡單的LR(1)，即只在動(dòng)作不唯一的地方向前看一 個(gè)符號，在動(dòng)作唯一時(shí)則不向前看輸入符號。,6.1 LR分析概論,一 .LR分析器的邏輯結(jié)構(gòu)及工作過程 從邏輯上來說，一個(gè)LR分析器如圖：,,即一個(gè)LR(k)分析器主要由：總控程序，分析棧（狀態(tài)棧和符號棧）輸入隊(duì)列和分析表組成。一般來說所有LR分析器的總控程序基本上是大同小異。只有分析表各不相同。一般主要討論三種不同的分析表的構(gòu)造方法。,第一種稱為規(guī)范LR分析表構(gòu)造法。用此法構(gòu)

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

4、成相應(yīng)的分析動(dòng)作。 表中每一表元素所規(guī)定的動(dòng)作僅能是下列四種動(dòng)作之一：,2.設(shè)在分析中的某一步，分析棧及余留的輸入串為如下格局： S0S1 Sm ai ai+1an #X1 Xm ,（1） ACTIONSm, ai= Sm+1 （移進(jìn)） 表明句柄尚未在棧頂形成，此時(shí)正期待移進(jìn)輸入符號以便形成 句柄。故將當(dāng)前的輸入符號和表元素Sm+1分別壓入棧中，有,（2） ACTIONSm, ai= Rj (歸約） 表明此時(shí)應(yīng)按文法的第j個(gè)產(chǎn)生式A Xm-k+1Xm-k+2 Xm 進(jìn)行歸約。即棧頂符號串Xm-k+1Xm-k+2 Xm已成為當(dāng)前

5、句型的句 柄。所謂按第j個(gè)產(chǎn)生式歸約，就是將分析棧中從頂向下的k個(gè)符 號退棧，然后將文法符號A壓入符號棧中。此時(shí)分析的格局為： S0S1 Sm-k ai ai+1an # # X1 Xm-k A ,然后以（ Sm-k,A)去查狀態(tài)轉(zhuǎn)移表，設(shè)GOTOSm-k,A= Sl ,則將此新狀態(tài)壓入狀態(tài)棧中，則有如下格局： S0S1 Sm-k Sl ai ai+1an # # X1 Xm-k A ,（3） ACTIONSm, ai=acc （接受）,表明當(dāng)前的輸入串已被成功

6、地分析完畢，應(yīng)停止分析器的工作。,其中Z為文法開始符號 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)“為止。對接受狀態(tài)，分析棧的格局為： S0 S # # Z ,例：,有文法GS:1：SaAcBe 2：Ab 3：AAb 4：Bd 其ACTION表和GOTO表為： 考察對輸入串a(chǎn)bbcde# 的分析過程。,,對輸入串a(chǎn)bbcde# 的

7、分析過程為：,,,6.2 LR(0) 分析表的構(gòu)造,為了給出構(gòu)造LR(0)分析表的算法，引出一些術(shù)語： 1、規(guī)范句型的活前綴 前綴：一個(gè)符號串的前綴是指該串的任意首部（包括）。,例如 abc的前綴有： ,a,ab,abc abcd的前綴有：,a,ab,abc,abcd 由此可知，對于符號串 而言，其前綴的數(shù)量為+1。 例：有文法GS:SaAcBe1 Ab2 這里在每條產(chǎn)生式后加上了產(chǎn)生 AAb3 式的序號i當(dāng)進(jìn)行推導(dǎo)時(shí)把序號 Bd4 帶上，以便說明問題。 對輸入串a(chǎn)bbcde進(jìn)行推導(dǎo)如下（最右推導(dǎo)）： S aAcBe1 aAcd

8、4e1 aAb3cd4e1 ab2b3cd4e1 由此可知，abbcde是該文法的句子。由于LR方法是自底向上的 分析，故應(yīng)采用歸約。,最左歸約為： ab2b3cd4e1 用2式歸約, aAb3cd4e1 3, aAcd4e1 4, aAcBe1 1, S,其中表示歸約符,從歸約的過程可看出，每次歸約時(shí)，歸約前和歸約后的被 歸約部分與剩余部分合起來僅構(gòu)成文法的規(guī)范句型，而用哪個(gè) 產(chǎn)生式歸約僅取決于當(dāng)前句型的前面部分；X1X2Xnp 其中Xi為文法的符號，p為第p個(gè)產(chǎn)生式序號。 如上例中每次歸約前句型的前面部分為： ab2 aAb3 aAcd4 acA

9、Be1,我們把規(guī)范句型的這種前端部分的串稱為可歸前綴。實(shí)際上，它們恰好是符號棧棧頂形成句柄時(shí)符號棧中的內(nèi)容。,SaAcBe1 Ab2 AAb3 Bd4,這是因?yàn)橐坏┚湫偷木浔诜枟ｍ斝纬桑瑢?huì)立即被歸約 之故。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的 任何符號）的前綴稱之為可歸前綴。 對各規(guī)范句型有前綴：,ab2b3cd4e1 ,a,ab aAb3cd4e1 ,a,aA,aAb aAcd4e1 ,a,aA,aAc,aAcd aAcBe1 ,a,aA,aAc,aAcB,aAcBe,可以發(fā)現(xiàn)前綴a,ab,aA,aAc是多

10、個(gè)規(guī)范句型的前綴，因此我們可進(jìn) 一步把形成可歸前綴前和形成可歸前綴時(shí)的所有規(guī)范句型的前綴 都稱為活前綴。,可歸前綴：是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之 后的任何符號。,活前綴：可歸前綴的任意首部。特指在分析過程中對于在棧頂 形成句柄之前和恰好形成句柄時(shí)，每一步中符號棧中的那些符號組成的符號串。,,,活前綴定義：,在前面例中對輸入串a(chǎn)bbcde的歸約分析過程中，在規(guī)范歸約過程 中的任何時(shí)候只要已分析過的部分即在符號棧中的符號串均為規(guī)范 句型的活前綴，它表明輸入串的已被分析過的部分是該文法某規(guī) 范句型的一個(gè)正確部分。,2、LR（0）項(xiàng)目,由上述分析和定義可知，活前綴與句柄間的關(guān)系不外乎下述

11、 三種情況：（1）活前綴中已含有句柄的全部符號（句柄的最后符號就是 活前綴的最后符號）。（2）活前綴中只含有句柄的前部分符號（句柄的最左子串 為活前綴的最右子串）。 （3）活前綴中全然不包含句柄的任何符號。,第一種情況表明：此時(shí)某一產(chǎn)生式A的右部已出現(xiàn)在符號 棧頂，因此此時(shí)相應(yīng)的分析動(dòng)作應(yīng)當(dāng)是用此產(chǎn)生式進(jìn)行歸約。 第二種情況表明：形如A12的產(chǎn)生式的 右部子串已在符號棧棧頂，如1，正期待著從余留的輸入串中看到能由推出的 符號串，即期待2 進(jìn)棧以便能進(jìn)行歸約。故此時(shí)分析動(dòng)作是“移進(jìn)”當(dāng)前輸入符號。 第三種情況則意味著：期望從余留輸入串中能看到由某產(chǎn)生式 A的右部，即所代表的符號串(即句柄

12、) 。所以此時(shí)分析的動(dòng)作也是讀輸入符進(jìn)符號棧。,,為了刻畫在分析過程中，文法的一個(gè)產(chǎn)生式右部符號串有多大 部分已被識(shí)別，我們可在該產(chǎn)生式的右部相應(yīng)位置上加一個(gè)圓點(diǎn) “.”，來指示位置，標(biāo)明在“.”前的部分已被識(shí)別。如上述三種情況，可分別標(biāo)注為：A.； A1 .2 ; A. 。 我們把右部某位置上標(biāo)有圓點(diǎn)的產(chǎn)生式稱為相應(yīng)文法的一個(gè) LR(0)項(xiàng)目。特別地，對形如A 的產(chǎn)生式，相應(yīng)的LR(0)項(xiàng)目， A. 顯然不同的LR(0)項(xiàng)目，反映了分析過程中符號棧頂?shù)牟煌闆r。,例如：產(chǎn)生式SaAcBe對應(yīng)有六個(gè)項(xiàng)目。,0 S.aAcBe 1 Sa.AcBe 2 SaA.cBe 3

13、 SaAc.Be 4 SaAcB.e 5 SaAcBe.,例如：產(chǎn)生式SaAcBe對應(yīng)有六個(gè)項(xiàng)目。,0 S.aAcBe 1 Sa.AcBe 2 SaA.cBe 3 SaAc.Be 4 SaAcB.e 5 SaAcBe.,一個(gè)產(chǎn)生式可對應(yīng)的項(xiàng)目的數(shù)量為它的右部符號串長度加1，值得注意的是對空產(chǎn)生式，即A僅有項(xiàng)目A. 每個(gè)項(xiàng)目的含義與圓點(diǎn)的位置有關(guān)。概括地說，圓點(diǎn)左邊的子串表示在分析過程的某一時(shí)刻用該產(chǎn)生式歸約時(shí)句柄中已識(shí)別過的部分，圓點(diǎn)右邊的子串表示待識(shí)別的部分。 文法的全部LR(0)項(xiàng)目將是構(gòu)造識(shí)別它的所有活前綴的有窮自動(dòng)機(jī)的基礎(chǔ)。,3、LR(0)項(xiàng)目的分類：,例：考慮文法GS=(S,A

14、,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： 為了方便起見，我們在上述文法中引起一個(gè)新的開始符號S, 且將S S作為第0個(gè)產(chǎn)生式添加到文法G中，從而得到了所謂 G的拓廣文法G。顯然L(G)=L(G)，則對于文法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 . 11)

15、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)目反映了分析過程中棧頂?shù)牟煌闆r，,因此，我們可根據(jù)它們不同的作用，將一個(gè)文法的全部LR(0)項(xiàng)目 進(jìn)行分類： 對于形如A. 的項(xiàng)目，因?yàn)樗砻饔也糠柎殉霈F(xiàn)在棧頂，此 時(shí)相應(yīng)的分析動(dòng)作應(yīng)當(dāng)是按此產(chǎn)生式進(jìn)行歸約，故我們將此種項(xiàng)目 稱為歸約項(xiàng)目。上例中的項(xiàng)目2) ,4),6),10),12

16、),16),18)均是歸約項(xiàng)目。 其中項(xiàng)目2)顯然僅用于分析過程中的最后一次歸約，它表明整個(gè)分 析過程已成功地完成，所以我們特別地將它稱為接受項(xiàng)目。對于拓 廣文法而言，接受項(xiàng)目是唯一的。由此可看出到我們?yōu)槭裁匆紫?將文法拓廣的原因。 對于形如A. X 的項(xiàng)目（其中 可以是 ），根據(jù)前面的討論 可知，當(dāng)X為終結(jié)符時(shí)，相應(yīng)的分析動(dòng)作應(yīng)將當(dāng)前的輸入符號移入 棧中，故我們將此種項(xiàng)目稱為移進(jìn)項(xiàng)目。上例中的項(xiàng)目7) ,9), 11), 13) ,15) ,17)就都是移進(jìn)項(xiàng)目； 當(dāng)X為非終結(jié)符時(shí)，由于我們期待著從余留的輸入符中進(jìn)行歸 約后而得到X，因此將此類項(xiàng)目稱為待約項(xiàng)目。上例中的1), 3),

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

18、示這個(gè)DFA的初態(tài)，它預(yù)示著整個(gè)分析過程的開始，并且期待著將給定的輸入串逐步歸約為文法的開始符號S?；蛘叻催^來說，我們所期待的是，從使用產(chǎn)生式SS開始，能夠逐漸推導(dǎo)出所給定的輸入串。因此，我們應(yīng)將項(xiàng)目S.S列入項(xiàng)目集I0 之中。換言之，也就是我們正期待將要掃描的輸入串正好就是能由S推導(dǎo)出的任何終結(jié)符串。然而，我們不能從輸入串中直接讀出非終結(jié)符號S，因此我們也應(yīng)將項(xiàng)目S.A和S.B加入I0中。由于A 和B同樣是非終結(jié)符，所以也應(yīng)將A.aAb和A.c和B.aBb, B.d加入I0中。由于最后加入I0的項(xiàng)目在圓點(diǎn)之后已都是終結(jié)符 了，故I0已經(jīng)“封閉”，宣告項(xiàng)目集I0構(gòu)造結(jié)束。這樣，表示初態(tài)的 項(xiàng)目

19、集I0將由如下項(xiàng)目組成： I0 : S.S, S.A, S.B, A.aAb, A.c, B.aBd, B.d 我們將LR(0)項(xiàng)目S.S稱為項(xiàng)目集I0的基本項(xiàng)目，上述從S.S出發(fā)構(gòu)造項(xiàng)目集I0的過程，可用一個(gè)對其基本項(xiàng)目集S .S的閉包運(yùn)算，即closure(S.S)來表示。,一般地，設(shè)I為項(xiàng)目集，I的閉包c(diǎn)losure(I)的定義為：,Closure(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)加到

20、closure(I)中（若 它們不在closure(I)中）； 3）重復(fù)上述過程，直至不再有新的項(xiàng)目加入到closure(I)中為止。,有了初態(tài)項(xiàng)目集I0之后，我們來說明如何確定從I0可能轉(zhuǎn)移到 的下一狀態(tài)。設(shè)A為一文法符號(AV)，若I0中有圓點(diǎn)位于A左邊 的項(xiàng)目K .A(其中可能為)，則當(dāng)分析器從輸入串識(shí)別出(即 移進(jìn)或歸約出)文法符號A后，分析器將進(jìn)入它的下一狀態(tài)。設(shè)此 狀態(tài)為Ii ，顯然Ii中必含有全部形如KA .的項(xiàng)目，我們將這樣 的項(xiàng)目稱為K .A的后繼項(xiàng)目。對于每一個(gè)文法符號A，如果 存在這樣的后繼項(xiàng)目，則可能不只一個(gè)，設(shè)其組成集合J，則J中的 每個(gè)項(xiàng)目都是項(xiàng)目集Ii的基本項(xiàng)目，

21、因此，按照與上面構(gòu)造項(xiàng)目集 I0相類試的討論，我們有： Ii =closure(J),為了指明Ii是“I0關(guān)于文法符號A的后繼狀態(tài)”這一事實(shí)，我們 可定義一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)：GO(I,A)=closure(J) 其中，I是當(dāng)前狀態(tài)，A為文法符號，J是I中所有形如K.A 的項(xiàng)目之后繼項(xiàng)目KA.所組成的集合，而closure(J)就是項(xiàng)目 集I（即狀態(tài)I)關(guān)于符號A的后繼項(xiàng)目集（即后繼狀態(tài)）。,即： GO(I,A)=closure(所有形如KA .的項(xiàng)目K .AI),對于上例，我們有： I1 =GO(I0,S)=closure(SS.) I1 : SS.; I2 =GO(I0,A)=clos

22、ure(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 d,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,I

23、3,I4,I5,I6,而I1, I2,I3, I5,I6均無后繼項(xiàng)目集，僅I4有后繼項(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.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,I

24、8 =GO(I7,b)=closure(AaAb.)=AaAb. I10 =GO(I9,b)=closure(BaBd.)=BaBd. 此時(shí)I8 ， I10也已無后繼項(xiàng)目集，故我們已求出文法GS的全部 項(xiàng)目集I0 I10 。 通常我們將這些項(xià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ī)范族I0 I10 V M的字母表，即V=S,S,A,B,a,b,c,d； GOM的映射函數(shù)，即上面定義的狀態(tài)轉(zhuǎn)移函數(shù)G

25、O； I0M的唯一初態(tài)； ZM的終態(tài)集， ZC為規(guī)范族中所有含有歸約項(xiàng)目的 那些項(xiàng)目集。,DFA:,G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d,DFA:,即：,G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d,4、LR(0)分析表的構(gòu)造,對于一個(gè)文法G的拓廣文法G，當(dāng)識(shí)別它的全部活前綴的DFA 作出之后，我們可以據(jù)此構(gòu)造相應(yīng)的LR(0)分析表了。 然而，要注意的是，用前述方法所構(gòu)造的每一個(gè)LR(0)項(xiàng)目集 實(shí)

26、質(zhì)上表征了在分析過程中可能出現(xiàn)的一種分析狀態(tài)；再根據(jù)前 面對LR(0)項(xiàng)目的分類，項(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）多個(gè)歸約項(xiàng)目并存，即存在歸約歸約沖突。 如果一個(gè)文法G滿足上述條件，也就是它的每個(gè)LR(0)項(xiàng)目集 中都不含有沖突的項(xiàng)目，則稱G為LR(0)文法。 顯然，只有當(dāng)一個(gè)文法是LR(0)文法時(shí)，才能對它構(gòu)造不含沖 突動(dòng)作的LR(0)分析表來。,為了方便起見，我們用整數(shù)0，1，2， 表示狀態(tài)I0 , I1, I2,

27、 ;分析表的內(nèi)容由兩部分組成，一部分為動(dòng)作(ACTION)表，它表示當(dāng)前狀態(tài)下所面臨的輸入符號應(yīng)做的動(dòng)作是移進(jìn)、歸約、接受或出錯(cuò)。另一部分為狀態(tài)轉(zhuǎn)移（GOTO)表，它表示在當(dāng)前狀態(tài)下面臨文法符號時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài)，相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)DFA的狀態(tài)轉(zhuǎn)換矩陣。分析表的行標(biāo)為狀態(tài)號，動(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)對于每一項(xiàng)目集Ii中形如A.X的項(xiàng)目，且有GO(Ii,X)=Ij,

28、 若X為一終結(jié)符號 a 時(shí)，則置ACTIONi,a=Sj; 若X為一非終結(jié)符號時(shí)，則僅置GOTOi,X=j (2)若Ii中有歸約項(xiàng)目A. ,設(shè)A為文法第j個(gè)產(chǎn)生式，則對 文法的任何終結(jié)符和“#”（均記為a）置ACTIONi,a=Rj,(3)若接受項(xiàng)目SS .屬于Ii ,則置ACTIONi,#=acc。 (4)在分析表中,凡不能按上述規(guī)則填入信息的元素,均置為“出錯(cuò)”。 如上例可構(gòu)造分析表為：,ACTION GOTO a b c d # S A B 0 S4 S5 S6 1 2 3 Acc

29、 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 S10 10 R5 R5 R5 R5 R5,5、LR(0)分析器的工作過程,對于一個(gè)文法構(gòu)造了它的LR(0)分析表就可以在LR分析器的總 控程序控制下對輸入串進(jìn)行分析，即根據(jù)輸入串當(dāng)前符號a和分析 棧棧頂狀態(tài)i查找分析表應(yīng)采取的動(dòng)作，對狀態(tài)棧和符號棧進(jìn)行相 應(yīng)的操作即移進(jìn)、歸約、接受或報(bào)錯(cuò)。具

30、體為： 1）若ACTIONi,a=Sj, aVT,則把a(bǔ)移進(jìn)符號棧，j移進(jìn)狀態(tài)棧。 2）若ACTIONi,a=Rj，aVT或#，則用第j個(gè)產(chǎn)生式歸約。并將 兩個(gè)棧的指針減去K(其中K為第j 個(gè)產(chǎn)生式右部的串長度），并 把產(chǎn)生式的左部符號A壓入符號棧，同時(shí)用符號對（ 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)為“#”號），則表明分析成功， 結(jié)束分析。 4）若ACTIONi,a=空白，轉(zhuǎn)出錯(cuò)處理。,6.3 SLR(1)分析,因大多數(shù)程序設(shè)計(jì)語言的文法不能滿足

31、LR(0)文法的條件，即 使是描述一個(gè)變量這樣簡單的文法也不是LR(0)文法。因此下面 將介紹對LR(0)規(guī)范族中有沖突的項(xiàng)目集（狀態(tài)）用向前查 看一 個(gè)（輸入）符號的辦法進(jìn)行處理，以解決沖突。這種分析方法 因?yàn)橹粚τ袥_突的狀態(tài)才向前查看一個(gè)符號，以確定做什么動(dòng)作 ，故稱這種分析方法為簡單的LR(1)分析法，用SLR(1)表示。 假定有一個(gè)LR(0)規(guī)范族中含有如下項(xiàng)目集(狀態(tài))I: I=X.b,A., B.其中,,,為符號串，bVT, 顯然I中含有移進(jìn)歸約和歸約歸約沖突。那么只要在所有 含有A或B的句型中，直接跟在A或B后面的可能終結(jié)符集合 FOLLOW(A)和FOLLOW(B)互不

32、相交，且都不包含b,即只要滿足：,即：FOLLOW(A)FOLLOW(B)b =,那么，當(dāng)在狀態(tài)I面臨某輸入符號為a時(shí)，則動(dòng)作可由下述規(guī)定決策： 1）若a = b,則移進(jìn)。 2）若a FOLLOW(A),則用產(chǎn)生式A歸約。 3）若a FOLLOW(B),則用產(chǎn)生式B歸約。 一般地，對于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)

33、,,FOLLOW(Bn) 兩兩交集都為空，則我們?nèi)钥捎蒙鲜鰵w則來解決沖突： 1）若ab1, b2,,bm,則移進(jìn)。 2）若aFOLLOW(Bi),i=1,,n,則用Bi i進(jìn)行歸約。 3）此外，則報(bào)錯(cuò)。,所以，我們只須把構(gòu)造LR(0)分析表算法中的規(guī)則(2)，即： (2)若Ii中有歸約項(xiàng)目A. ,設(shè)A為文法第j個(gè)產(chǎn)生式，則對 文法的任何終結(jié)符和“#”（均記為a）置ACTIONi,a=Rj 。 修改為：,即： (1)對于每一項(xiàng)目集Ii中形如A.X的項(xiàng)目，且有GO(Ii,X)=Ij, 若X為一終結(jié)符號a時(shí)，則置ACTIONI,a=S; 若X為一非終結(jié)符號時(shí)，則僅置GOTOi,X=j； (2)

34、若歸約項(xiàng)目A.屬于Ii,設(shè)A為文法第j個(gè)行產(chǎn)生式，則 對任何屬于FOLLOW(A)的輸入符號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)生式，則對任何屬于FOLLOW(A)的輸入符號a,置ACTIONi,a=Rj 。 其余的規(guī)則不變，就得到了構(gòu)造SLR(1)分析表的算法。,例如： 有算術(shù)表達(dá)式文法GE,構(gòu)造其LR(0)項(xiàng)目規(guī)范簇和SLR(1)分析表。GE: EE+TT TT*FF F(E) i,解：1、拓廣文法

35、為GS : (0) SE EE+T ET TT*F TF F(E) Fi,2、再求識(shí)別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,I1: SE. EE.+T GO(I1,+)=I6,I2: ET. TT.*F GO(I2,*)=I7,I3: TF.,I4: F(.E) GO(I4

36、,E)=I8 E.E+T GO(I4,E)=I8 E.T GO(I4,T)=I2 T.T*F GO(I4,F)=I2 T.F GO(I4,F)=I3 F.(E) GO(I4,( )=I4 F.i GO(I4,i)=I5,I5: 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)=I5,,I7: TT*.F GO(I7,F)=I10 F.(E) GO(I7,( )=I4

37、 F.i GO(I7,i )=I5,I8: F(E.) GO(I8,) )=I11 EE.+T GO(I8,+)=I6,I9: EE+T. TT.*F GO(I9,)=I7,I10: TT*F.,I11: F(E).,DFA:,3、解決沖突,可以看到，項(xiàng)目I1， I2， I9中都同時(shí)包含有移進(jìn)項(xiàng)目和歸約項(xiàng)目。存在移進(jìn)歸約沖突，因而該文法不屬于LR(0)文法，故不能構(gòu)造LR(0)分析表。 FOLLOW(S)= # FOLLOW(E)= +，)，# FOLLOW(T)= +，*，)，# FOLLOW(F)= +，*，)，# 現(xiàn)在分別考慮上述三個(gè)沖突項(xiàng)目中的沖突

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

39、)文法。我們可造成其相應(yīng)的SLR(1)分析表為：,下面給定輸入串i+i*i #，使用上述SLR(1)分析進(jìn)行分析：,步 狀態(tài)棧 符號棧 輸入串 ACTION GOTO,,1 0 # i+i*i # S5,2 05 #i +i*i # R6 3,3 03 #F +i*i # R4 2,4 02 #T +i*i # R2 1,5 01 #E +i*i # S6,6 016 #E+ i*i # S5,7 0

40、165 #E+i *i # R6 3,8 0163 #E+T *i # R4 9,9 0169 #E+T *i # S7,10 01697 #E+T* i # S5,11 016975 #E+T*i # R6 10,12 0169710 #E+T*F # R3 9,13 0169 #E+T # R1 1,14 01 #E # acc,LR分析器:,LR分析器是一個(gè)確定的下推自動(dòng)機(jī)。作為LR分析器的核心的 分析表由兩個(gè)子表組成：分析動(dòng)作表ACTION和狀態(tài)轉(zhuǎn)移表 GOTO. 一個(gè)LR分析器如圖：,