第5講--語法分析下

1、CompilerPrinciples1u語法分析概述語法分析概述u自上而下語法分析自上而下語法分析u自下而上語法分析自下而上語法分析CompilerPrinciples2內容提要內容提要v基本問題基本問題vLR分析方法分析方法LR分析器LR分析表規(guī)范LR分析LALR分析二義文法的應用出錯處理分析器的自動生成CompilerPrinciples3 前面已經(jīng)談了自下而上分析的基本思想，就是自左而右地掃描輸入源程序單詞符號串，并逐步進行自下而上的歸約，直至規(guī)約到文法的開始符號；或者說，從樹的末端開始，一步步向上歸約，直至樹根。這種構造樹的過程與我們通常的從根開始構造的方法剛好是一個逆過程，因此這種樹

2、又稱為語法分析樹。1 1. .基本問題基本問題CompilerPrinciples41.歸約與語法分析樹歸約與語法分析樹 上述思想可用如下的一個例子來說明：例 文法 GS: (1)SaAcBe (2)Ab (3)AAb (4)Bd顯然，abbcde是該文法的一個句子，于是可如右構造其語法分析樹：a ab bb bc cd de eA AA AB BS S* *該語法樹的構造的確是一個“自左而右、自下而上”的過程，我們把這一類分析方法統(tǒng)稱為“自下而上”的。CompilerPrinciples52.移進歸約移進歸約 在計算機上模擬以上的語法分析樹的構造過程，可借助于一個符號棧來實現(xiàn)：輸入串：輸入串

3、： abbcde#abbcde#步驟：步驟：動作：動作：符號棧：符號棧：12345678910移進移進a a移進移進b b 歸約歸約b b 移進移進b b 歸約歸約AbAb移進移進c c 移進移進d d歸約歸約d d歸約歸約aAcBeaAcBe移進移進e e歸約產(chǎn)歸約產(chǎn)生式：生式：#a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S(2)(3)(4)(1)CompilerPrinciples6分析方法的基本思想v將待分析的符號串從左向右進行掃描，并將串中符號一個一個地移入棧中，邊移入邊分析；當棧頂符號串形成所給文法的某個產(chǎn)生式右部時就進行一次歸約，即用該產(chǎn)生式的左部非終結

4、符替換相應右部符號串。把棧頂被歸約的這一串符號稱為可歸約串。重復這一過程，若能歸約到文法的識別符號，則該分析的符號串是該文法的句子，否則不是。分析過程中的關鍵問題分析過程中的關鍵問題如何找出棧頂當前可歸約串的問題？包括：如何定義可歸約串？如何識別可歸約串？CompilerPrinciples7 為了尋找可歸約串，先來看兩個定義： (1)短語、直接短語和句柄： 令G是一個文法，S是開始符號，是文法G的一個句型，如果有 S * A且A +， 則稱是句型相對于非終結符A的短語。 特別的，如果有A ，則稱是句型相對于規(guī)則A的直接短語，一個句型的最左直接短語稱為該句型的句柄。CompilerPrinci

5、ples8CompilerPrinciples9v 接下來我們介紹一種強大的自下而上語法分析技術，它可用于大多數(shù)CFG的語法分析，稱為LR分析法。L表示從左至右掃描輸入串，R表示構造一個最右推導的逆過程。v LR分析法比其他的“移進歸約”法更加廣泛，效率也不比它們差；比一般不帶回溯的自上而下分析（如LL(1)分析）也要好一些，而且在自左而右掃描輸入串時就能發(fā)現(xiàn)其中的任何錯誤，并能準確地指出出錯位置。v 當然，要適應一般情況，分析器就得更加復雜。因此，LR分析器的手工構造工作量相當大，一般要借助于自動產(chǎn)生器。2 2.LR.LR分析法分析法CompilerPrinciples10 1.LR分析器

6、(1)概述： 根據(jù)前面的介紹我們知道：自下而上分析的中心思想是“移進歸約”，關鍵問題就是“尋找規(guī)范句型的句柄”。當一貌似句柄的符號串呈現(xiàn)于分析棧頂時，如何確定用哪一個產(chǎn)生式來歸約？這是我們一直未能解決的問題。 仔細分析問題產(chǎn)生的原因，我們會發(fā)現(xiàn)，在分析過程中我們沒有利用到已處理的過程“歷史資料”，也沒有根據(jù)產(chǎn)生式去“瞻望”未來可能遇到的輸入符號，而LR分析法就是在這些方面對“移進歸約”進行改造的。 LRLR分析法的基本思想：根據(jù)分析法的基本思想：根據(jù)“歷史資料歷史資料”、“現(xiàn)實輸入現(xiàn)實輸入符號符號”以及對未來的以及對未來的“展望展望”等三個方面來確定棧頂?shù)姆柕热齻€方面來確定棧頂?shù)姆柺欠駱嫵?/p>

7、了相對于某一產(chǎn)生式的句柄。是否構成了相對于某一產(chǎn)生式的句柄。它是由Knuth在1965年首先提出的，后經(jīng)Aho等人改造而成。CompilerPrinciples11 一個一個LRLR分析器實際上是一個帶有分析棧的分析器實際上是一個帶有分析棧的DFADFA 前面講過，狀態(tài)的變化可以反映出處理前后的經(jīng)過，因此這兒我們應把“歷史”和“展望”材料都綜合為“狀態(tài)”，存入分析棧，使得任何時候，棧頂都代表了從分析開始以來的全部“歷史”和已推測出的“展望”。這樣一來，在任何時候都可從棧頂來了解一切，棧頂狀態(tài)和現(xiàn)行輸入符號就唯一決定了LR分析器的每一步工作。 棧中每一項內容包括狀態(tài)s和文法符號X兩部分。棧的初始

8、值為(s0,#)。棧頂狀態(tài)為sm，符號串X1X2Xm是至今已移進歸約出的部分。 如下圖所示：CompilerPrinciples12s s0 0s s1 1s sm m# #X X1 1X Xm mLRLR分析器分析器# #a an na ai ia a1 1輸出輸出輸入串輸入串分析棧分析棧分析表分析表LRLR分析器模型圖分析器模型圖ActionActionGotoGotoCompilerPrinciples13 分析表分析表 LR分析器的核心是一張分析表。這張表包括兩部分：“動作”(Action)和“狀態(tài)轉換”(Goto) ，它們都是二維數(shù)組。Actions,a規(guī)定了狀態(tài)s面臨輸入符號a時應

9、該采取什么動作；Gotos,X則指出狀態(tài)s面對文法符號X（終結符或非終結符）時下一狀態(tài)是什么。顯然，Gotos,X定義了一個以文法符號為字母表的DFA。 CompilerPrinciples14 每一項Actions,a所規(guī)定的動作無非是下述四種可能之一：a.移進：把(s,a)的下一狀態(tài)s=Gotos,a和輸入符號a推進棧，下一輸入符號變成現(xiàn)行輸入符號；b.歸約：指用某一產(chǎn)生式A進行歸約。若|r,則把棧頂r個項托出，棧頂狀態(tài)變成sm-r,然后把 (sm-r,A)的下一狀態(tài)s=Gotosm-r,A和A進棧。歸約動作不改變現(xiàn)行輸入符號；（這意味著Xm-r+1 Xm=是一個相對于A的句柄）c.接受：

10、宣布分析成功，停止分析器的工作； d.報錯：報告發(fā)現(xiàn)錯誤，調用出錯處理程序掃描輸入串就可以發(fā)現(xiàn)錯誤位置。CompilerPrinciples15 LR分析器的工作過程： 一個LR分析器的工作過程可以看成是棧里的狀態(tài)序列、已歸約串和輸入串所構成的三元式的變化過程： 初始三元式： (s0, #, a1a2an#) 中間三元式： (s0s1.sm, #X1X2Xm, aiai+1an#) 接受: (s0sk,#X,#) (X為開始符號，而Actionsk,# 為接收) 分析器的下一步動作完全由sm和ai唯一決定，即執(zhí)行Actionsm,ai。經(jīng)執(zhí)行每種可能的動作之后，三元式的變化情形是：Compil

11、erPrinciples16.若actionsm,ai為移進且s=gotosm,ai，則三元式變?yōu)椋?(s(s0 0s s1 1ssm ms, #Xs, #X1 1X X2 2XXm ma ai i, a, ai+1i+1aan n#)#).若actionsm,ai=A，則按產(chǎn)生式A進行歸約，此時三元式變?yōu)椋?(s (s0 0s s1 1ssm-rm-rs s, #X, #X1 1X X2 2XXm-rm-rA, aA, ai ia ai+1i+1aan n#)#) 此處s s=gotos=gotosm-rm-r,A,A，r為的長度，=X=Xm-r+1m-r+1XXm m。.若actionsm

12、,ai為接受，則三元式不再變化，過程終止，分析成功。.若actionsm,ai為報錯，則三元式的變化過程終止，報告錯誤。 LR分析器的工作過程就是一步一步地變換三元式，直至執(zhí)行“接受”或“報錯”為止。再看前面的例子：文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步驟步驟符號棧符號棧輸入符號串輸入符號串動作動作 1） # abbcde# 移進移進 2） #a bbcde# 移進移進A 3） #ab bcde# 歸約歸約(Ab) 4） #aA bcde# 移進移進A 5） #aAb cde# 歸約歸約(AAb) 6） #aA cde# 移進移進

13、 7） #aAc de# 移進移進B 8） # aAcd e# 歸約歸約(Bd) 9） #aAcB e# 移進移進11） #S # 接受接受S10） #aAcBe # 歸約歸約 這是前面講過的對輸入串這是前面講過的對輸入串a(chǎn)bbcde#的移進的移進-規(guī)約分析過規(guī)約分析過程，下面我們來看如何用程，下面我們來看如何用LR分析法來分析該句子分析法來分析該句子步驟步驟 符號棧符號棧 輸入符號串輸入符號串動作動作 1） # abbcde# 移進移進 0 S2 2） #a bbcde# 移進移進 02 S4 4） #aA bcde# 移進移進 023 S6 6） #aA cde# 移進移進 023 S5

14、7） #aAc de# 移進移進 0235 S8 9） #aAcB e# 移進移進 02357 S911） #S # 接受接受 01 acc 對輸入串對輸入串a(chǎn)bbcde#的的LR分析分析過程：過程： 3） #ab bcde# 歸約歸約(Ab) 024 r2 3 5） #aAb cde# 歸約歸約(AAb) 0236 r3 3 8） # aAcd e# 歸約歸約(Bd) 02358 r4 710） #aAcBe # 歸約歸約(SaAcBe) 023579 r1 1狀態(tài)棧狀態(tài)棧ACTIONGOTOS Si i: :移進移進：將將下一下一狀態(tài)狀態(tài)i i和和現(xiàn)行現(xiàn)行輸入符號輸入符號進棧進棧；r ri

15、 i: :歸約：用第歸約：用第i i個產(chǎn)生式歸約個產(chǎn)生式歸約，同時狀態(tài)棧與符號棧退出相，同時狀態(tài)棧與符號棧退出相應的符號，并把應的符號，并把GOTOGOTO表相應狀表相應狀態(tài)和第態(tài)和第i i個產(chǎn)生式的個產(chǎn)生式的左部左部非終非終結符入棧。結符入棧。CompilerPrinciples19 (2) LR文法： 對于一個文法，如果能夠構造出一張分析表，使得它的每個入口均是唯一的，則稱該文法為LR文法。 注意：并非所以上下文無關文法都是LR文法，例： 二義性文法 SiCtS| |iCtSeS 直觀上說，對于一個LR文法，當分析器對輸入串進行自左而右掃描時，一旦句柄呈現(xiàn)于棧頂，就能及時對它進行歸約。 一

16、個LR分析器有時需要“展望”未來的k個輸入符號才能決定應采取什么樣的“移進歸約”決策。于是又有如下定義: 對于文法G，若能用一個每步頂多向前查看k個輸入符號的LR分析器進行分析，則稱之為LR(k)文法。但是對大多數(shù)的程序語言來說，k1就足夠了。因此，我們只研究LR(0)和LR(1)。CompilerPrinciples202. 分析表的構造分析表的構造 (1)LR(0)分析表的構造 首先討論一種只概括“歷史”資料而不包含推測性“展望”材料的分析法LR(0)分析法。我們希望僅由這種簡單狀態(tài)就能識別呈現(xiàn)在棧頂?shù)哪承┚浔?。而LR(0)項目集就是這樣的簡單狀態(tài)。 LR(0)項目集： a.字的前綴：字的

17、任意首部。如abc: a, ab, abc. b.活前綴：規(guī)范句型的一個前綴，它不含句柄之后的任何符號。之所以稱之為活前綴，是因為在其右邊添加一些終結符號后就可以形成規(guī)范句型。CompilerPrinciples21 在LR分析過程中的任何時候，棧里的文法符號（自棧底向上）X1X2Xm應該構成活前綴，把輸入串的剩余部分配上之后即應成為規(guī)范句型。反過來說，只要輸入串的已掃描部分保持可歸約成一個活前綴，那就意味著掃描過的部分沒有錯誤。 這樣來看，如果我們能構造出一個FA，它能識別某文法G的所有活前綴，那么我們就可以通過這個FA來構造G的LR分析表了，為此我們定義“項目” (item) ： Comp

18、ilerPrinciples22 c.LR(0)項目：文法G的每一個產(chǎn)生式的右部添加一個圓點稱為G的一個LR(0)項目（簡稱項目）。 例如，產(chǎn)生式AXYZ對應四個項目： AXYZ AXYZ AXYZ AXYZ 當然，A只對應一個項目：A 。在計算機中，每個項目可用一個整數(shù)對表示：第一個整數(shù)代表產(chǎn)生式編號，第二個指出圓點的位置。 CompilerPrinciples23 實際上，項目反映了分析過程中某時刻我們看到產(chǎn)生式的多大部分。如AXYZ 意味著我們希望能從后面輸入串看到可以從XYZ推導出的符號串。AXYZ意味著我們已經(jīng)從輸入串看到了從X推導出的符號串，并希望能進一步看到YZ推出的符號串。v

19、為了方便，我們把形如A的項目稱為“歸約項目”，開始符號S的歸約項目S稱為“接受”項目。形如Aa的項目，稱為“移進”項目；形如AB的項目則稱為“待約”項目，其中aVT, BVN 。這兒介紹項目是為了以項目作為要構造的FA的狀態(tài)。 CompilerPrinciples24構造識別活前綴的DFA .通過項目構造一個NFA ： a.把項目編號，所有編號構成NFA的狀態(tài)集； b.以開始符號S S所對應的項目S S 為唯一初態(tài) c.若項目i為：XXXX1 1XXi-1i-1X Xi iXXn n而項目j為： XX XX1 1XXi iX Xi+1i+1XXn n ，則從i到j畫一條標記為X Xi i的 弧

20、；若XiVN，則從狀態(tài)i畫弧到所有的Xi 狀態(tài)； d.除初態(tài)外的任何狀態(tài)都認為是終態(tài)（活前綴識別 態(tài)）。 .用子集法把NFA確定化為DFA建立LR分析算法的基礎。 下面我們來看一個例子：CompilerPrinciples25v例例 文法文法GS: (0)S (0)SE (1) EaA (2) EbBE (1) EaA (2) EbB (3)AcA (4) Ad (5) BcB (6) Bd (3)AcA (4) Ad (5) BcB (6) Bd 它的項目有：它的項目有： 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad

21、10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. BdCompilerPrinciples26(1)(1)構造構造NFANFA1 13 311112 24 46 65 57 79 98 810101212171714141515161618181313E Ea aA Ac cA Ad db bB Bc cB Bd dCompilerPrinciples27(2)(2)確定化確定化0: 0: S E EaA EbB2:2:EaA AcA Ad 3:3:EbB BcB Bd 4:4:AcA AcA Ad 5:5:Bc

22、B BcB Bd E Eb ba ac cc cA Ad dd dA AB Bd dd dB B1:1:SE8:8:AcA10: 10: Ad6: 6: EaA7:7:EbB11: 11: Bd9:9:BcBc cc cCompilerPrinciples28v下面我們來一起做一個練習：E - E + TE - TT - T * FT - FF - ( E )F - id構造這個文法的識別活前綴的自動機，并試著構造其分析表。CompilerPrinciples29v DFA的項目集的全體稱為文法GS的LR(0)項目集規(guī)范族；也就是說：構成識別一個文法G的活前綴的DFA的項目集的全體，稱為G的L

23、R(0)項目集規(guī)范族。這樣一來，如果我們都能構造出LR(0)項目集規(guī)范族的話，就可以直接構造識別文法的活前綴的DFA了。下面我們就簡單談一下通過構造LR(0)項目集規(guī)范族來構造DFA的方法。 LR(0)項目集規(guī)范族的構造建立DFA的另一方法 a.為使“接受狀態(tài)”唯一且易于識別，構造文法G的拓廣文法G: 引進一個新的初態(tài)S VN=VNS , VT=VT , P=PSS 很顯然，L(G)=L(G)。CompilerPrinciples30 b. 定義項目集定義項目集I I的閉包的閉包CLOSURE(I):CLOSURE(I): .I .I的任何項目都屬于的任何項目都屬于CLOSURE(I)CLOS

24、URE(I)； . .若若AB屬于屬于CLOSURE(I)CLOSURE(I)，那么，對任何，那么，對任何關于關于B的產(chǎn)生式的產(chǎn)生式B，項目，項目B也屬于也屬于CLOSURE(I)CLOSURE(I)； . .重復執(zhí)行上述步驟直至重復執(zhí)行上述步驟直至CLOSURE(I)CLOSURE(I)不再增大不再增大為止；為止； c. 定義狀態(tài)轉換函數(shù)定義狀態(tài)轉換函數(shù)GO: 對于項目集對于項目集I I和文法符號和文法符號X X(V(VN NVVT T),GO(I,X)=),GO(I,X)=CLOSURE(J),CLOSURE(J),其中其中: : J= J=任何形如任何形如AX的項目的項目AXII 也就是

25、說，也就是說，J J是由是由I I中那些中那些X X左邊有圓點的項目，左邊有圓點的項目，把圓點右移一個位置所得的項目的集合。把圓點右移一個位置所得的項目的集合。 CompilerPrinciples31 d. 通過閉包和狀態(tài)轉換函數(shù)，則我們很容易就可以求出G的LR(0)項目集規(guī)范族： PROCEDURE ITEMSETS(G); BEGIN C:= CLOSURE( SS ) ; REPEAT FORFOR C中的每個項目集I和G中的每個符號X DODO IFIF GO(I,X)非空且不屬于C THENTHEN 把GO(I,X)放入C族中 UNTIL C不再增大 END (詳見參考書)Comp

26、ilerPrinciples32 有效項目 我們希望從識別文法的活前綴的DFA建立LR分析器，因此需要研究這個DFA的每個項目集（狀態(tài)）中的項目的不同作用。 a.a.若有規(guī)范推導S*A12 ( (VT*) ) ，則稱項目A1 12 2對活前綴1 1是有效的。 直觀上說，若歸約項目A1對活前綴1是有效的，則是說應把1歸約為A;若若A12對活前綴1是有效的，則說明句柄尚未形成，故應移進。 對每個活前綴r，都可以構造它的有效項目集。這個集合剛好就是從DFA的初態(tài)出發(fā)，經(jīng)讀出r后而到達的那個項目集。CompilerPrinciples33 b.定理： 任何時候分析棧中的活前綴X X1 1X X2 2X

27、Xm m的有效項目集正是棧頂狀態(tài)Sm所代表的那個項目集。 這是LR分析理論的一條基本定理。實際上，棧頂?shù)捻椖考顟B(tài)）體現(xiàn)了棧里的一切有用信息。 這兒需要指出的是，對同一活前綴，有可能存在若干項目對它都是有效的，而且要做的事情各不相同，互相沖突。這種沖突通過向前多看幾個輸入符號，或許可以解決。但是對于非LR文法，這種沖突是無法解決的。關于這點，以后再詳細介紹。 下面再來看一下前面那個例子:CompilerPrinciples34v例：例：文法文法GS: SE EaA EbBE EaA EbB AcA Ad BcB Bd AcA Ad BcB Bd 識別其活前綴的識別其活前綴的DFADFA的一部

28、分如下圖所示：的一部分如下圖所示： 我們說我們說bcbc是一個活前綴，是一個活前綴，DFADFA從從0 0狀態(tài)開始讀出狀態(tài)開始讀出bcbc后后到達到達5 5狀態(tài)，這個狀態(tài)集對狀態(tài)，這個狀態(tài)集對bcbc是有效的。是有效的。0: 0: SE EaA EbB3:3:EbB BcB Bd 5:5:BcB BcB Bd 7:7:EbB11:11:Bd9:9:BcBb bc cB Bd dd dB Bc cCompilerPrinciples35 LR(0)LR(0)文法的定義文法的定義： 若一個文法G的拓廣文法G的活前綴識別自動機中的每個狀態(tài)不存在下述情況： a.既含移進項目又含歸約項目； b.含有多個

29、歸約項目 則稱G是一個LR(0)文法。 也就是說，LR(0)文法規(guī)范族的每個項目集不包含任何沖突項目。 LR(0)LR(0)分析表的構造：分析表的構造： 現(xiàn)在我們通過DFA來構造LR(0)分析表，也就是通過項目集規(guī)范族C=I0,I1,In和函數(shù)GO，使用如下算法來構造：CompilerPrinciples36v 我們用每個項目集我們用每個項目集I Ik k的下標的下標k k作為分析器的狀態(tài)。特別地，作為分析器的狀態(tài)。特別地，令含有令含有SS的項目集的項目集I Ik k的下標的下標k k作為初態(tài)。于是如下構造子作為初態(tài)。于是如下構造子表表ActionAction、GotoGoto： . .若項目

30、若項目Aa I Ik k且且GO(IGO(Ik k,a)=I,a)=Ij j,a,aVT, 則置則置ActionActionk,ak,a為為“把把(j,a)(j,a)移進棧移進?！?，簡記為，簡記為“s sj j”； . .若項目若項目A I Ik k，那么對任意，那么對任意a aVT(或或#)，置置 ActionActionk,ak,a為為“用產(chǎn)生式用產(chǎn)生式A進行歸約進行歸約”，簡記為，簡記為 “ “r rj j”；( (設設A是文法是文法G的第的第j j個產(chǎn)生式個產(chǎn)生式) ) . .若項目若項目SS I Ik k，則置，則置ActionActionk,#k,#為為“接受接受”，簡記為，簡記為

31、 “acc”； . .若若GO(IGO(Ik k,A)=I,A)=Ij j，A AVN,則則GotoGotok,A=k,A=j j； . .分析表中凡不能用上述分析表中凡不能用上述4 4規(guī)則填入信息的空白格均置規(guī)則填入信息的空白格均置“報報 錯標志錯標志”； CompilerPrinciples37例上述文法例上述文法 GGS 其其LR(0)LR(0)分析表如右分析表如右: :(0) S(0) SE E (1) EaA (1) EaA (2) EbB(2) EbB(3) AcA (3) AcA (4) Ad (4) Ad (5) BcB(5) BcB(6) Bd(6) BdCompilerPr

32、inciples38 (2)SLR分析 問題的提出：LR(0)分析要求條件很苛刻，即使是定義算術表達式這樣的簡單文法，要想使識別其活前綴的DFA的每個狀態(tài)都不含沖突項目也不可能。因此，有必要研究一種帶帶一點一點“展望展望”材料材料的LR分析法，也就是要檢查一下下一個輸入符號。 例如，I=Xbb,A,A,B,B ，第一個項目為移進項目，第二、三項是歸約項目。到底應該采取哪種動作是不清楚的。如果我們分析一下該文法中所有含A,B的句型，考察Follow(A)和Follow(B)，若Follow(A) Follow(B)=且且都不含有都不含有b，則問題就解決了。當狀態(tài)I面臨輸入a時，我們就可以采取如下

33、的“移進歸約”策略： .若a=b,則移進； .若aFollow(A),則用A來歸約；來歸約； .若aFollow(B),則用B來歸約；來歸約； .此外，報錯。CompilerPrinciples39一般而言，若一般而言，若LR(0)LR(0)規(guī)范族的一個項目集規(guī)范族的一個項目集I I中含有中含有m m個移進項目和個移進項目和n n個歸約項目：個歸約項目： I= A I= A1 1aa1 11 1, , A A2 2aa2 22 2.A Am maam mm m, , B B1 1,B,B2 2,.B,.Bn n ， 若集合：若集合： a a1 1,a,a2 2, ,.a am m Follow

34、(BFollow(B1 1) ).Follow(BFollow(Bn n)=)=，則則通過查看現(xiàn)行輸入符號通過查看現(xiàn)行輸入符號a a屬于哪個集合就可以解決屬于哪個集合就可以解決問題。問題。 .若若a=aa=ai i (i=1,2,m) , (i=1,2,m) ,則移進；則移進； . .若若a aFollow(Bi) (i=1,2,n),(i=1,2,n),則用則用Bi來來 歸約；歸約； . .此外，報錯。此外，報錯。 這種方法稱為這種方法稱為SLR(1)SLR(1)解決法解決法。CompilerPrinciples40 SLR分析表的構造 這個構造算法與LR(0)分析表的構造算法基本類似，只有

35、些許改動之處：若項目A Ik，那么對任意aVT且aFollow(A)，置Actionk,a為“用產(chǎn)生式A進行歸約”，簡記為“r rj j”； （詳見參考書） 按照上述算法構造出的分析表，如果不含多重入口，則稱之為G的SLR分析表；G稱為一個SLR(1)文法，使用SLR分析表的分析器稱為SLR分析器。每個SLR文法都是無二義的，但也存在許多無二義文法不是SLR(1)的,因為沒有足夠多的“展望”信息。 （例見參考書）CompilerPrinciples41 (3)規(guī)范LR分析法 前面我們定義LR(0)項目時，并沒有牽扯到任何“展望”信息。只要DFA的某狀態(tài)中含有歸約項目A，那么當棧頂出現(xiàn)串時，我們

36、就能用A進行歸約。現(xiàn)在我們想使每個狀態(tài)含有較多的“展望”信息，這將有助于克服動作沖突和無效歸約。為此，我們對項目重新定義： LR(k)項目：形如A,a1a2.ak的項目。 其中，A是一個LR(0)項目，每個aiVT。而a1a2.ak稱為該LR(k)項目的向前搜索串（展望串）。類似的，A, a1a2.ak稱為LR(k)歸約項目，而AX, a1a2.ak或者是LR(k)移進項目(XVT)，或者是LR(k)待約項目(XVN)。CompilerPrinciples42v 可以想到，向前搜索串只是對LR(k)歸約項目有意義，而對任何移進或待約沒有作用。由于對大多數(shù)程序語言的語法來說，一般向前搜索一個符號

37、就可以確定“移進”或“歸約”，因此，我們只對k1的情況感興趣。 有效項目有效項目：一個LR(1)項目A,a對于活前綴=是有效的，如果存在： S* *A A 其中a是的第一個符號,或者 =, a=# 。 例例 考慮文法：SBB BaBb 它有一個規(guī)范推導S* *aaBabaaaBab, ,我們看到項目BaB,a對于活前綴=aaa是有效的。因為，=aa,A=B, =ab,=a,=b。同樣，項目BaB,#對于活前綴Baa是有效的。 R RR RR RR RCompilerPrinciples43 構造有效的LR(1)項目集族思想同LR(0)項目規(guī)范集族 a.a.構造有效構造有效LR(1)LR(1)項

38、目集的閉包項目集的閉包：設I是一個項目集, .I的任何項目CLOSURE(I)； .若項目AB,aCLOSURE(I), B是一個產(chǎn)生式，則對于任何終結符bFIRST(a),B,b CLOSURE(I)； .重復步驟，直至CLOSURE(I)不再增大為止 。CompilerPrinciples44CompilerPrinciples45c.c.文法文法G G 的的LR(1)LR(1)項目集族項目集族C C的構造算法的構造算法： PROCEDURE ITEMSETS(GPROCEDURE ITEMSETS(G );); BEGIN BEGIN C:= CLOSURE( S C:= CLOSURE

39、( S S,# ) ;S,# ) ; REPEAT REPEAT FOR C FOR C中的每個項目集中的每個項目集I I和和G G 中的每個符中的每個符 號號X DOX DO IF GO(I,X) IF GO(I,X)非空且不屬于非空且不屬于C THENC THEN 把把GO(I,X)GO(I,X)放入放入C C族中族中 UNTIL CUNTIL C不再增大不再增大 ENDENDCompilerPrinciples46 規(guī)范規(guī)范LR(1)LR(1)分析表的構造分析表的構造與與LR(0)LR(0)基本上一樣：基本上一樣：.若項目若項目 Aa,b I Ik k且且GO(IGO(Ik k,a)=I

40、,a)=Ij j,a,aVT, 則置則置Actionk,aActionk,a為為 “ “s sj j”；.若若 A ,aI Ik k，則置，則置Actionk,aActionk,a為為 “ “r rj j”；.若若 S S ,#I Ik k，則置，則置Actionk,#Actionk,#為為 “acc”；.若若GO(IGO(Ik k,A)=I,A)=Ij j，A AVN,則則GotoGotok,A=k,A=j j；.分析表中凡不能用上述分析表中凡不能用上述4 4規(guī)則填入信息的空白格均置規(guī)則填入信息的空白格均置“報錯標志報錯標志”； 按照上述算法構造出的分析表，如果不含多重入口，則稱之為G的LR

41、(1)分析表；G稱為一個LR(1)文法，使用這種分析表的分析器稱為規(guī)范的LR(1)分析器。顯然，每個SLR(1)文法都是LR(1)文法。CompilerPrinciples47 (4)LALR分析表的構造（向前分析表的構造（向前LR） 前面介紹的SLR分析和規(guī)范LR分析都是通過“展望”信息來解決沖突的，但出發(fā)點不完全一樣。前者僅對歸約項才向前搜索，而后者是任何時候都向前搜索，顯然SLR(1)分析表的狀態(tài)要比LR(1)分析表少一些。像早期的Algol語言的SLR(1)分析表只要幾百個狀態(tài)，而其LR(1)分析表卻要幾千個狀態(tài)。因此，用SLR分析更經(jīng)濟。但我們知道，LR (1)分析的能力要比SLR(

42、1)強很多。 于是，就有了這兩者的一種折衷：LALR分析法。就狀態(tài)數(shù)來說， LALR分析表同于SLR，因而也比規(guī)范LR分析表小得多；就功能來說，LALR要比SLR強，比規(guī)范LR分析要差。CompilerPrinciples48v 從自動機的角度來看，LALR似乎有點像把LR分析法最小狀態(tài)化，其思想就是通過合并那些僅僅搜索符號串不同而其余完全相同的項目集。當然這樣一來，ACTION表肯定要做相應的變動，但GO函數(shù)是無需變動的，因為它自身就會隨項目集的變化而變化。為此，我們提出“同心”的概念： 兩個LR(1)項目集是同心的：除去搜索符號串之后，這兩個LR(1)項目集是完全相同的。實際上，一個心就是

43、一個LR(0)項目集。 我們知道，一個LR(1)文法的LR(1)項目集族是不存在沖突的，那么經(jīng)過合并之后，會不會出現(xiàn)新的沖突呢？有可能！CompilerPrinciples49 a.同心合并不會導致同心合并不會導致“移進歸約移進歸約”沖突沖突。 因為如果存在這種沖突，則意味著對于當前的輸入符號a，合并后的項目集中有一個項目A ,a要求歸約動作，而另一項目B a,b 要求把a移進，這兩個項目既然同處于合并后的一個集合之中，這就意味著在合并之前，必有某個c使得A ,a和和B a,c 同處于合并前的某個集合中，這樣一來就說明了原來的LR(1)項目集中就已有“移進歸約”沖突了，顯然與我們的假設相矛盾。

44、因此，我們說同心集的合并決不會導致“移進歸約”沖突。 CompilerPrinciples50 b.同心集合并可能導致新的同心集合并可能導致新的“歸約歸約歸約歸約”沖突。沖突。 例如，考慮文法G： (0) SS (1) SaAdbBdaBebAe (2) Ac (3) Bc 可以驗證G是一個LR(1)文法。在G的LR(1)項目集族C中，對活前綴ac有效的項目集為： AcAc ,d ,d, BcBc ,e ,e，對活前綴bc有效的項目集為：AcAc ,e ,e, BcBc ,d ,d。顯然這兩個項目集同心且不含沖突。然而，同心集合并后則變成新項目集：AcAc ,d/e ,d/e, BcBc ,d

45、/e ,d/e。如此一來，當面臨d,e時就不知道該用AcAc還是BcBc來歸約，也就是有了“歸約歸約”沖突。CompilerPrinciples51 LALRLALR分析表的構造分析表的構造 基本思想：先構造基本思想：先構造LR(1)LR(1)項目集族，再合項目集族，再合并同心集。并同心集。 這兒要求： a.LR(1)項目集族不存在沖突； b.合并后的集族不含“歸約歸約”沖 突。 這個算法的步驟不再詳細列出，請查閱參考書。CompilerPrinciples52v 對于正確的輸入串，LR和LALR分析器工作基本一致，但有錯誤時，LALR可能比LR多做些不必要的規(guī)約，但是不會移進更多的符號，這就

46、保證了能準確地指出錯誤的位置，這一點與LR(1)是等效的。v 用同心合并來構造LALR分析表，雖簡單明了，但太費存儲空間。為此，人們又提出另一種構造LALR分析表的方法：造核法。v 關于項目集的核：一個項目集的核是此集中所有圓點不在最左邊的項目組成的，但初態(tài)項目集的核有且只有S S S,#S,#項目。CompilerPrinciples53CompilerPrinciples54 (5)二義文法的應用二義文法的應用 通過前面的介紹，我們知道二義文法產(chǎn)生的分析表都含有多重入口，因此給我們的分析帶來很多麻煩。人們已經(jīng)證明：任何二任何二義文法都不是義文法都不是LR文法，因而也決不是文法，因而也決不是

47、SLR或或LALR文法文法。 但是二義文法也不是一無是處，某些二義文法還是非常有用的。例如： G1: EE+EE*E(E)i G2: EE+TT TT*FF F(E)iCompilerPrinciples55 G1與G2相比，有兩個明顯的好處 .如果要改變算符的優(yōu)先關系或結合規(guī)則，G1不需做任何變動； .G1的分析表狀態(tài)數(shù)比G2少，因為后者的單非產(chǎn)生式要占用不少狀態(tài)； 既然二義文法有這樣的好處，我們就要想辦法利用它。這里我們就探討一下如何使用LR分析法的基本思想，附加一些條件，來分析二義文法所定義的語言。 我們以文法G1為例來說明問題。它的LR(0)項目集規(guī)范族如下圖所示：CompilerPr

48、inciples56I I0 0:E EEE EE+E EE+E EE EE* *E E E(E) E(E) Ei EiI I1 1:E EEE EE+E EE+E EE EE* *E EI I4 4:EE+E:EE+E EE+E EE+E EE EE* *E E E(E) E(E) Ei EiI I3 3:Ei:EiI I2 2:E(E):E(E) EE+E EE+E EE EE* *E E E(E) E(E) Ei EiI I7 7:E EE+EE+E EE+E EE+E EE EE* *E EI I5 5:E EE E* *EE EE+E EE+E EE EE* *E E E(E) E(

49、E) Ei EiI I8 8:E EE E* *EE EE+E EE+E EE EE* *E EI I6 6:E(E):E(E) EE+E EE+E EE EE* *E EI I9 9:E(E):E(E)E E+ +i i( ( (i iE E* *i iE E+ +E E* *i i( (* *) )+ +* *+ +CompilerPrinciples57v 從圖中可以看到，在狀態(tài)I1時，EE要求接受，而EE+E,EE*E要求移進，這種沖突可以使用SLR方法予以解決查看FOLLOW(E)。(= ?)(= ?)v 再看狀態(tài)I7,EE+E要求規(guī)約，而EE+E, EE*E要求移進+或*，這個沖突

50、卻不是SLR方法能夠解決的。 ( ? ) 這種沖突只有借助于其他條件才能得到解決，也就是要使用算符優(yōu)先級和結合規(guī)則的有關信息了。 下面來看個例子：CompilerPrinciples58 考慮輸入串i+i*i，在處理了i+i之后，分析器進入狀態(tài)I7,這時分析棧的內容為#0E1+4E7,剩余輸入串為*i#。此時就產(chǎn)生了問題：到底是執(zhí)行r1還是s5呢？ 假定*的優(yōu)先級比+高，則就應該把*移進棧，也就是執(zhí)行s5。拓廣文法拓廣文法G: G: (0)EE (0)EE (1)EE+E(1)EE+E(2)E(2)EE E* *E E(3)E(3)E(E)(E)(4)E(4)Ei ii+i*i# 同樣對于i+

51、i+i，棧到達#0E1+4E7時，根據(jù)+左結合性質，應該先規(guī)約后進棧。把這些問題都解決了之后，我們就可以構造分析表了。CompilerPrinciples59文法文法GG對應的對應的LRLR分析表分析表CompilerPrinciples60 (6)LR分析中的出錯處理分析中的出錯處理 在LR分析過程中，出現(xiàn)下列情況：輸入情況既不能移進棧頂，棧頂也不能規(guī)約，就意味著發(fā)現(xiàn)了語法錯誤，應該調用相應的出錯處理子程序。 處理的方法分為兩類：第一類多半使用插入、刪除或修改的方法，試圖消除錯誤；如果不可能采用這種方法，則采用第二類方法：檢查到某一個不合適的短語，它不能與任一非終結符可能推導出的符號串相匹配

52、，則將其當作非法語句跳過。也就是說，分析器試圖將錯誤局部化，以便能夠繼續(xù)分析工作。 CompilerPrinciples61短語級錯誤恢復：將語法錯誤局部化。v思想：LR分析器在訪問Action表時，若遇到一個出錯表項，就立即報告錯誤。它不會把出錯點的符號進棧。因此，假定本該由某個A推導出的串含有語法錯誤，則發(fā)現(xiàn)錯誤時，該串的一部分已經(jīng)進棧，剩余部分仍在輸入串中。分析器試圖從棧中退出一些符號，并跳過若干輸入符號，然后恢復正常的分析過程。v恢復策略：從棧頂開始退棧，退出若干個狀態(tài)和文法符號，直至找到某個狀態(tài)s，有Gotos,A=s，把s進棧；然后丟棄若干個輸入符號，直到找到A的一個合法后繼符號a

53、為止，將其置為當前輸入符號。v實現(xiàn)：檢查LR分析表的每個出錯項，并根據(jù)語言的使用情況確定最可能出現(xiàn)的錯誤，然后為該表項編寫一個適當?shù)腻e誤恢復例程，來修復棧頂。 CompilerPrinciples62文法文法GG對應的對應的LRLR分析表（包含出錯處理子程序）分析表（包含出錯處理子程序）CompilerPrinciples63v上表中各個錯誤處理子程序的工作是：e1 將一個假想的i進棧，把3狀態(tài)置為棧頂狀態(tài) 錯誤信息：“缺少運算對象”e2 刪除當前輸入符號 ) 錯誤信息：“右括號不配對”e3 將一個假想的+進棧，把4狀態(tài)置為棧頂狀 態(tài)，錯誤信息：“缺少操作符”e4 把 ）進棧，把9狀態(tài)置為棧頂

54、狀態(tài) 錯誤信息：“缺少 ）”CompilerPrinciples64 (7)分析表的自動產(chǎn)生分析表的自動產(chǎn)生 這一節(jié)我們來介紹另一個編譯程序編寫系統(tǒng)YACCYet Another Compiler Compiler。它是美國Bell實驗室的S.C.Johnson等人在1974年研制開發(fā)的。該系統(tǒng)可以根據(jù)用戶提供的文法（可能二義的）和算符優(yōu)先級、結合性等輔助信息，自動產(chǎn)生出LALR分析表。當然，若文法是LALR(1)的，就無需輔助信息，否則，輔助信息必不可少。 CompilerPrinciples65 終結符和產(chǎn)生式的優(yōu)先級 YACC解決沖突的方法是給每個產(chǎn)生式和終結符都賦以一定的優(yōu)先級。若A不

55、特別賦以優(yōu)先級，則認為該產(chǎn)生式與出現(xiàn)在串的最右終結符優(yōu)先級相同。顯然在不涉及沖突時也就沒必要管這些優(yōu)先級了，一旦面臨輸入符號a時發(fā)生了“移進-規(guī)約”沖突，則必須比較a與A的優(yōu)先級。 例：文法G: SiSeSiSa 顯然，該文法類似于if-then-else結構，它的LR(0)項目集族如下圖：CompilerPrinciples66v 在上圖中可以清楚地看到，I4狀態(tài)存在移進-規(guī)約沖突。按照通常的習慣，else應與最近的一個then相結合，因此當if C then S呈現(xiàn)于棧頂并面臨else時，應該移進。于是我們就規(guī)定e的優(yōu)先級高于i，則SiS的優(yōu)先級就低于e，分析器在I4時就會執(zhí)行移進，沖突也就