1、第七章 LR分析,7.1 LR分析概述 7.2 LR(0)分析 7.3 SLR(1)分析 7.6 使用二義文法,課前思考,復習自頂向下和自底向上語法分析思想的區(qū)別 自底向上分析方法是一種移進-歸約過程 算符優(yōu)先分析法是如何確定可歸約串的？ 什么是規(guī)范推導和規(guī)范歸約？它們之間有什么關系？ 什么是規(guī)范句型？ 什么是規(guī)范句型的句柄？ 移進-歸約過程是當分析的棧頂符號串形成句柄時就采取歸約動作 自底向上分析法的關鍵問題是在分析過程中如何確定句柄。 如何確定一個輸入符號串是否是所給文法的句子?,學習目標,本章將介紹自底向上分析的另一種方法，即LR分析法。 理解LR分析法的基本思想 理解可歸前綴和活前綴概

2、念 理解識別活前綴的有限自動機概念 掌握LR分析器的構造思想和方法 對給定的文法能構造LR(0)、SLR(1)、LALR(1)、LR(1)四種分析器，并能判斷所給文法是四種分析器的哪幾類。 對給定的輸入符號串能用構造的分析器判斷該輸入串是否是所給文法的句子 了解某些二義性文法在LR分析中的應用。,學習指南,LR分析法正是給出一種能根據(jù)當前分析棧中的符號串（通常以狀態(tài)表示）和向右順序查看輸入串的K個(K0)符號就可唯一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約，因而也就能唯一地確定句柄。 LR分析法的歸約過程是規(guī)范推導的逆過程，所以LR分析過程是一種規(guī)范歸約過程。,學習指南（續(xù)）,其中L

3、R(0)分析器是在分析過程中不需向右查看輸入符號，因而它對文法的限制較大，然而，它是構造其它LR類分析器的基礎。因此，首先應學好LR(0)項目集規(guī)范族構造的基本原理和方法。當K=1時，已能滿足當前絕大多數(shù)高級語言編譯程序?qū)崿F(xiàn)的需要。SLR(1)分析是為學習LR(1)分析做準備，LR(1)項目集族的構造是LALR(1)分析器的構造原理和基礎。LALR(1) 分析器是當前大多數(shù)高級程序設計語言編譯程序所采用的語法分析技術，也是編譯程序語法分析器自動構造工具YACC(將在第13章介紹）的實現(xiàn)基本原理。由此，LR(0)、SLR(1)、LALR(1)、LR(1)四種分析器的構造方法都必須深入理解和掌握。

4、,難 重 點,可歸前綴和子前綴概念 識別活前綴的有限自動機概念 對可歸前綴為規(guī)范歸約的句柄的理解 構造LR(1)項目集族時搜索符的計算 LR分析器的關鍵部分是分析表的構造 對給定的文法能構造LR(0)、SLR(1)、LALR(1)、LR(1)四種分析器 當一個文法能構造出不含移進-歸約或歸約-歸約沖突時的LR(0)/ SLR(1)/ LALR(1)/ LR(1)分析表時，稱這個文法為LR(0) / SLR(1)/ LALR(1)/ LR(1)文法。 對給定的文法能判斷是四種LR類文法的哪幾類 了解某些二義性文法在LR分析中的應用,知識結構,7.1 LR分析概述,LR(K) L 從左至右掃描輸入

5、符號串 R 構造一個最右推導的逆過程 K 向右順序查看輸入串的K個符號 LR(0): 在分析過程中不需向右查看輸入符號。 四種分析器： LR(0)、SLR(1)、LR(1)、LALR(1) SLR(1)和LALR(1)分別是LR(0)和LR(1)的一種改進。,LR(0)分析表 在分析過程中不需向右查看輸入符號。 SLR(1)分析表 簡單LR分析表構造法，是一種容易實現(xiàn)又有實用價值的方法，但存在一些文法構造不出SLR分析表 規(guī)范LR分析表LR(1) 能力最強，但實現(xiàn)代價過高，分析表尺寸太大 LALR分析表 向前看LR分析表構造法，也是一種常用方法,LR方法的基本思想 在規(guī)范歸約過程中，一方面記住

6、已移進和歸約的整個符號串，另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入符號,在規(guī)范歸約中，當一串貌似句柄的符號串呈現(xiàn)于棧頂時，LR分析法根據(jù)三方面的信息找句柄： 歷史：記錄在棧內(nèi)的符號串移進、歸約的歷史情況 展望：預測句柄之后可能出現(xiàn)的信息 現(xiàn)實：讀頭下的符號,注：LR分析法的基本思想是符號化人的思維習慣，但實現(xiàn)有困難，因為基于“歷史”對未來的“展望”可能存在多種可能，當把“歷史”和“展望”材料綜合在一起時復雜性就大大增加。如果簡化對“展望”的要求，就可獲得實際可行的分析算法。,LR分析法的優(yōu)缺點 優(yōu)點：與其他技術相比，適應文法范圍更廣，能力更強，識別效率相當，尤其在自左向右掃描輸入串時就能

7、發(fā)現(xiàn)其中錯誤，并能準確指出出錯位置 缺點：若用手工構造分析程序，工作量太大，且容易出錯，所以必須使用自動產(chǎn)生這種分析程序的產(chǎn)生器 產(chǎn)生器作用 應用產(chǎn)生器產(chǎn)生一大類上下文無關文法的LR分析程序 對二義性文法或難分析的特殊文法，施加一些限制，使之能用LR分析。,LR 分析器模型,總控程序的作用： 查分析表，根據(jù)分析表的內(nèi)容做若干簡單動作，如讀頭后移、入棧、出棧等 注：由于總控程序很簡單，所以產(chǎn)生器的任務就是產(chǎn)生分析表,分析表 狀態(tài)轉(zhuǎn)換表用GOTOSi, XSj 表示，規(guī)定當棧頂狀態(tài)為Si遇到當前文法符號為X時應轉(zhuǎn)向狀態(tài)Sj。 動作表用ACTIONSi, a表示，規(guī)定了棧頂狀態(tài)為Si時遇到輸入符號a

8、應執(zhí)行的動作。動作有4種可能： 移進 歸約 接受acc 報錯,移進 把Sj=GOTOSi，a移入到狀態(tài)棧，把a移入到文法符號棧 歸約 當在棧頂形成句柄為時，則用歸約為相應的非終結符A，即文法中有A的產(chǎn)生式，若的長度為r(即|=r)，則從狀態(tài)棧和文法符號棧中自棧頂向下去掉r個符號，即棧指針SP減去r。并把A移入文法符號棧內(nèi)，Sj=GOTOSi，A移進狀態(tài)棧，其中Si為修改指針后的棧頂狀態(tài)。 接受acc 當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結束即當前輸入符是#，則為分析成功 報錯 當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入串不是該文法能接受的句子,

9、文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進,2） #a bbcde# 移進,4） #aA bcde# 移進,6） #aA cde# 移進,7） #aAc de# 移進,9） #aAcB e# 移進,11） #S # 接受,符號串a(chǎn)bbcde是否是GS的子,對輸入串a(chǎn)bbcde#的移進-歸約分析過程,7.2 LR(0) 分析,LR(0)文法 能力最弱，理論上最重要 存在FA 識別活前綴 識別活前綴的DFA如何構造 （LR(0)項目集規(guī)范族的構造） LR(0)分析表的構造,LR

10、(0)分析表構造的思想和方法是構造其他LR分析表的基礎。,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,11） #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) 02

11、358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移進，將狀態(tài)i和輸入符進棧 ri:歸約，用第i個產(chǎn)生式歸約，同時狀態(tài)棧與符號棧退出相應個符號，并把GOTO表相應狀態(tài)和第i個產(chǎn)生式的左部非終結符入棧。,LR分析算法,置ip指向輸入串w的第一個符號 令S為棧頂狀態(tài) a是ip指向的符號（當前輸入符號）begin(重復開始) if ACTIONSi,a=Sj then begin PUSH j,a(進棧) ip 前進(指向下一輸入符號) end

12、else if ACTIONSi,a=rj (第j條產(chǎn)生式為A),LR分析算法,then begin pop | 項 令當前棧頂狀態(tài)為Sk push GOTOSk,A和A(進棧) end else if ACTIONSi,a=acc then return (成功） else error end (重復結束),LR文法 定義：如果某一文法能夠構造一張分析表，使得表中每一元素至多只有一種明確動作，則該文法稱為LR文法。,7.2.1 可歸前綴和活前綴,字的前綴是指該字的任意首部 例如：字ABC的前綴有、A、AB、ABC 活前綴 指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任意符號,例如：根據(jù)下面的

13、文法識別輸入串a(chǎn)bbcde 1)SaAcBe 2)Ab 3)AAb 4)Bd,若對上例文法GS的每條產(chǎn)生式編上序號用i表示，并加在產(chǎn)生式的尾部，使產(chǎn)生式變?yōu)椋?)SaAcBe12)Ab23)AAb34)Bd4但i不屬產(chǎn)生式的文法符號，對輸入串a(chǎn)bbcde進行推導時把序號也帶入，則最右推導過程為：S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1,它的逆過程,即最左歸約(規(guī)范歸約)則為：ab2b3cd4e1 用產(chǎn)生式(2)歸約 aAb3cd4e1 用產(chǎn)生式(3)歸約 aAcd4e1 用產(chǎn)生式(4)歸約 aAcBe1 用產(chǎn)生式(1)歸約 S,把規(guī)范句型的這種前部分串稱可歸前

14、綴,分析下列規(guī)范句型的前綴：規(guī)范句型abbcde的前綴：, a, ab規(guī)范句型aAbcde的前綴：, a, aA, aAb規(guī)范句型aAcde的前綴：, a, aA, aAc, aAcd規(guī)范句型aAcBe的前綴：, a, aA, aAc, aAcB, aAcBe,把形成可歸前綴之前包括可歸前綴在內(nèi)所有規(guī)范句型的前綴都稱為活前綴。,活前綴 G=(VN,VT,P,S),若有S A, 是文法G中的一個規(guī)范推導, G是G的拓廣文法, 符號串 是的前綴,則稱是文法G的一個活前綴, 也是G的活前綴。（其中A是一產(chǎn)生式，VT*；、V*） 其中S是對原文法擴充(SS)增加的非終結符.,R,活前綴與句柄的關系：-

15、 活前綴已含有句柄的全部符號，表明產(chǎn)生式A的右部已出現(xiàn)在棧頂。- 活前綴只含句柄的一部分符號如1，表明A12的右部子串1已出現(xiàn)在棧頂，當前期待從輸入串中看到2推出的符號 - 活前綴不含有句柄的任何符號，此時期望產(chǎn)生式A的右部所推出的符號串。,7.2.2 識別活前綴的有限自動機,LR分析需要構造識別活前綴的有窮自動機 我們可以把文法的終結符和非終結符都看成有窮自動機的輸入符號，每次把一個符號進棧看成已識別過了該符號，同時狀態(tài)進行轉(zhuǎn)換，當識別到可歸前綴時，相當于在棧中形成句柄，認為達到了識別句柄的終態(tài)。,用拓廣文法表示成：SS0SaAcBe1Ab2AAb3Bd4,現(xiàn)對句子abbcde的可歸前綴列出

16、：S0ab2aAb3aAcd4aAcBe1,構造識別其活前綴及可歸前綴的有限自動機,識別活前綴的不確定有限自動機,識別活前綴的確定有限自動機,c,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,11） #S # 接受 01 acc,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb c

17、de# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,對輸入串a(chǎn)bbcde#的LR分析過程,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a

18、bbcde# 移進 02 S4,對輸入串a(chǎn)bbcde#的LR分析過程,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbc

19、de# 移進 02 S4,4） #aA bcde# 移進 023 S6,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3

20、,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,步驟,符

21、號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a

22、 bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,對輸入串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 7,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde#

23、 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,對輸入串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 7,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進

24、0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,對輸入串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 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S

25、,a,b,A,b,c,B,e,d,8,*,步驟,符號棧,輸入符號串,動作,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,11） #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 7

26、,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,LR分析需要構造識別活前綴的有限自動機 可歸前綴和活前綴 把規(guī)范句型的前部分串稱可歸前綴 把形成可歸前綴之前包括可歸前綴在內(nèi)所有規(guī)范句型的前綴都稱為活前綴,小結,已經(jīng)有了活前綴如何構造有限自動機？ 我們可以把文法的終結符和非終結符都看成有窮自動機的輸入符號，每次把一個符號進?？闯梢炎R別過了該符號，同時狀態(tài)進行轉(zhuǎn)換，當識別到可歸前綴時，相當于在棧中形成句柄，認為達到了識別句柄的終態(tài)。 對每個可歸前綴都構造有限自動

27、機，然后用弧連接加上開始狀態(tài)X，再確定化，就得到識別活前綴的有窮自動機。,活前綴及其可歸前綴如何計算？ 由文法的產(chǎn)生式直接構造識別活前綴和可歸前綴的有限自動機。 可歸前綴在理論上很嚴格的計算方法（感興趣的可參看書面教材7.2.3節(jié)）。,7.2.3 LR(0)項目集規(guī)范族的構造,（1）LR(0)項目 在文法G中每個產(chǎn)生式的右部適當位置添加一個圓點構成項目。 例如，產(chǎn)生式SaAcBe對應有6個項目 0 SaAcBe 1 SaAcBe 2 SaAcBe 3 SaAcBe 4 SaAcBe 5 SaAcBe,（2）構造識別活前綴的NFA,如果把文法的所有產(chǎn)生式的項目都引出，每個項目都為NFA的一個狀態(tài)

28、。 以文法GS為例： SE EaA|bB AcA|d BcB|d,該文法的項目有：,1 SE 10. Ad2 SE 11. EbB3 EaA 12. EbB4 EaA 13. EbB5 EaA 14. BcB6 AcA 15. BcB7 AcA 16. BcB8 AcA 17. Bd9 Ad 18. Bd,SEEaA|bBAcA|dBcB|d,狀態(tài)之間的轉(zhuǎn)換關系確定方法如下： 若i項目為：XX1X2Xi-1XiXn j項目為：XX1X2Xi-1XiXi+1Xni項目和j項目出于同一個產(chǎn)生式，對應于NFA為狀態(tài)j的圓點只落后于狀態(tài)i的圓點一個符號的位置，那么從狀態(tài)i到狀態(tài)j連一條標記為Xi的箭弧

29、。,如果Xi為非終結符，則也會有以它為左部的有關項目及其相應的狀態(tài)，例如，有項目形如：i. XAk. A則從狀態(tài)i畫標記為的箭弧到狀態(tài)k 對于A的所有產(chǎn)生式圓點在最左邊的狀態(tài)都做一條從i狀態(tài)到該狀態(tài)的箭弧，箭弧上標記為,1 SE 10. Ad2 SE 11. EbB3 EaA 12. EbB4 EaA 13. EbB5 EaA 14. BcB6 AcA15. BcB7 AcA 16. BcB8 AcA 17. Bd9 Ad 18. Bd,根據(jù)圓點所在的位置和圓點后是終結符還是非終結符或為空把項目分為以下幾種： 移進項目，形如 A a aVT, , V* 待約項目，形如 A B BVN 歸約項目

30、，形如 A V* 接受項目，形如 S S SVN ，SS為拓廣文法的產(chǎn)生式,(3) LR(0)項目集規(guī)范族的構造,對于構成識別一個文法活前綴的DFA項目集(狀態(tài))的全體稱為這個文法的LR(0)項目集規(guī)范族 若狀態(tài)中包含形如AB的項目，則形如B的項目也在此狀態(tài)內(nèi) 例如：0狀態(tài)中項目集為SE，EaA, EbB,用閉包函數(shù)LOSURE求DFA一個狀態(tài)的項目集 若文法G已拓廣為G，而S為文法G的開始符號，拓廣后增加產(chǎn)生式SS。如果I是G的一個項目集，定義和構造I的閉包CLOSURE(I)如下： 1、I的項目均在CLOSURE(I)中。 2、若AB屬于CLOSURE(I)，則每一形如B 的項目也屬于CL

31、OSURE(I)。 3、重復2直到不出現(xiàn)新的項目為止，即CLOSURE(I)不再擴大。,計算閉包CLOSURE函數(shù),function CLOSURE (I); /* I 是項目集*/ J:= I;repeat for J 中的每個項目A B和產(chǎn)生式B，若B不在J中Do 將 B加到J中 until 再沒有項目加到J中return J;,例如:初態(tài)SE，EaA，EbB EaA求其閉包可得到項目集為EaA, AcA, Ad； EbB求其閉包得到項目集為EbB, BcB, Bd； SE的則不會再增加新的項目,GO (I, X)= CLOSURE(J) ; 其中， I:項目集，X: 文法符號， J=任何

32、形如AX的項目|AX I 若狀態(tài)I識別活前綴，則狀態(tài)J識別活前綴X。圓點不在產(chǎn)生式右部最左邊的項目稱為核，但開始狀態(tài)拓廣文法的第一個項目SS除外。,轉(zhuǎn)換函數(shù),新狀態(tài)的初始項目即圓點移動后的項目稱為核 用GO(I，X)轉(zhuǎn)換函數(shù)得到的J為轉(zhuǎn)向后狀態(tài)所含項目集的核 例中AaA和BbB都為核，對核求閉包就為新狀態(tài)的項目集 核可能是一個或若干個項目組成,使用閉包函數(shù)(CLOSURE)和轉(zhuǎn)換函數(shù)(GO(I, X)構造文法G的LR(0)項目集規(guī)范族，步驟如下：a) 置項目SS為初態(tài)集的核，然后對核求閉包，CLOSURE(SS)得到初態(tài)的項目集。b) 對初態(tài)集或其它所構造的項目集應用轉(zhuǎn)換函數(shù)GO(I, X)=

33、CLOSURE(J)求出新狀態(tài)J的項目集。c) 重復b)直到不出現(xiàn)新的項目為止。,計算GO函數(shù)和LR(0)項目集規(guī)范族,C=I0 ，I1 , . In Procedure itemsets(G); Begin C:= CLOSURE (SS) Repeat For C 中每一項目集I和每一文法符號x Do if GO(I, x) 非空且不屬于C Then 把 GO(I, x) 放入C中 Until C 不再增大 End;,注：1）此算法是迭代算法，置了C的初態(tài)（初態(tài)僅包含第一個項目集）后，每經(jīng)過一次FOR語句，就擴大一次C中的項目集數(shù)，直到項目集數(shù)不再增加為止 2）此算法是從I0開始，按該項目

34、集內(nèi)的項目順序依次求出所有后繼項目集。由這樣一層一層向下生成的所有項目集的方法避免了項目集的遺漏 3）若在項目集中存在A項目，不應再做GO函數(shù)轉(zhuǎn)向其他項目集，因為A和A是同一項目，都是A項目，它本身是歸約項目，不存在后繼項目。 4）由這個項目集規(guī)范族C中各個狀態(tài)及狀態(tài)轉(zhuǎn)換函數(shù)GO，可構造一張識別活前綴的DFA圖。,求出文法的所有項目，按一定規(guī)則構造識別活前綴的NFA再確定化為DFA。 把拓廣文法的第一個項目SS作為初態(tài)集的核，通過求核的閉包和轉(zhuǎn)換函數(shù)，求出LR(0)項目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關系得到識別活前綴的DFA。,LR(0)項目集規(guī)范族的項目類型分為四種： 移進項目、歸

35、約項目、待約項目、接受項目 一個項目集中可能包含以上四種不同的項目，但是一個項目集中不能有下列情況存在：a) 移進和歸約項目同時存在（移進-歸約沖突）：形如：AaBb) 歸約和歸約項目同時存在（歸約-歸約沖突）：形如：AB,對一個文法的LR(0)項目集規(guī)范族不存在移進-歸約，或歸約-歸約沖突時，稱這個文法為LR(0)文法,以文法GS為例： SE EaA|bB AcA|d BcB|d,1 SE 10. Ad2 SE 11. EbB3 EaA 12. EbB4 EaA 13. EbB5 EaA 14. BcB6 AcA15. BcB7 AcA 16. BcB8 AcA 17. Bd9 Ad 18.

36、 Bd,小練習：,對例：6.1 GS拓廣為:SSSaAcBe AbAAb Bd1）直接由產(chǎn)生式用CLOSURE，GO 函數(shù)計算LR(0)項目集的閉包和LR(0)項目集規(guī)范族2）構造識別活前綴的DFA,（4）LR(0)分析表的構造,LR(0)分析表的構造算法如下：,假定C=I0, I1,，In，令每個項目集Ik的下標k為分析器的一個狀態(tài)，因此，G的LR(0)分析表含有狀態(tài)0，1，n。令那個含有項目SS的Ik的下標k為初態(tài)。ACTION和GOTO可按如下方法構造： 若項目Aa屬于Ik且GO (Ik, a)=Ij, a為終結符，則置ACTIONk, a=Sj，表示為把狀態(tài)j和符號a移進棧; 若項目A

37、屬于Ik, 那么，對任何終結符a（包括#）, 置ACTIONk, a=rj ，表示為第j個產(chǎn)生式（A）進行歸約; 若項目SS屬于Ik, 則置ACTIONk, #為“接受”，簡記為“acc” 若GO (Ik, A)= Ij, A為非終結符，則置GOTO(k, A)=j; 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯標志”。,按上述算法構造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法G的一張LR(0)表。具有LR(0)表的文法G稱為一個LR(0)文法。 LR(0)文法是無二義的。,若對文法G：(0) SE (1) EaA (2) EbB (3) Ac

38、A(4) Ad (5) BcB (6) Bd 請按上述算法構造這個文法的LR(0)分析表,1 SE 10. Ad2 SE 11. EbB3 EaA 12. EbB4 EaA 13. EbB5 EaA 14. BcB6 AcA15. BcB7 AcA 16. BcB8 AcA 17. Bd9 Ad 18. Bd,(5) LR(0)分析器的工作過程,1) 若ACTIONS, a= Sj，a為終結符，則把a移入符號棧，j移入狀態(tài)棧。2) 若ACTIONS, a= rj，a為終結符或#號，則用第j個產(chǎn)生式歸約，并將兩個棧的指針減去k，其中k為第j個產(chǎn)生式右部的符號串長度，這時當前面臨符號為第j個產(chǎn)生式

39、左部的非終結符。3) 若ACTIONS, a=acc，a應為#號，則為接受，表示分析成功。4) 若GOTOS, A=j，A為非終結符，表明前一動作是用關于A的產(chǎn)生式歸約的，當前面臨非終結符A應移入符號棧，j移入狀態(tài)棧。對于終結符的GOTOS, a已和ACTIONS, a重合。5) 若ACTIONS, a=空白，則轉(zhuǎn)向出錯處理。,對輸入串bccd#的LR(0)分析過程,7.3 SLR(1)分析,實型變量說明文法為例：實型變量說明 real標識符表標識符表標識符表，i標識符表i,將該文法縮寫后并拓廣為G如下：(0) SS(1) SrD(2) DD,i(3) Di,識別文法G活前綴的DFA,實數(shù)說明

40、文法的LR(0)分析表,實數(shù)說明文法的SLR(1)分析表,SLR是LR(0)的一種改進，它在歸約時除了考慮歷史情況之外還考慮了一點現(xiàn)實,若一個LR(0)規(guī)范族中含有如下的項目集(狀態(tài))II=Xb, A, B也就是在該項目集中含有移進-歸約沖突和歸約-歸約沖突。其中, 為文法符號串，b為終結符。那么只要在所有含有A或B的句型中，直接跟在A或B后的可能終結符的集合即FOLLOW(A)和FOLLOW(B)互不相交，且都不包含b，也就是只要滿足FOLLOW(A)FOLLOW(B)= FOLLOW(A)b= FOLLOW(B)b= ,那么，當在狀態(tài)I時面臨某輸入符號為a時，則動作可由以下規(guī)定決策：1)

41、若a=b，則移進。2) 若aFOLLOW(A)，則用產(chǎn)生式A進行歸約。3) 若aFOLLOW(B)，則用產(chǎn)生式B進行歸約。4) 此外，報錯。,通常對于LR(0)規(guī)范族的一個項目集I中，可能含有多個移進項目和多個歸約項目，可假設項目集I(狀態(tài))中有m個移進項目：A11a11，A22a22，, Ammamm；同時含有n個歸約項目為：B11，B22，,Bnn。只要集合a1，a2，, am和FOLLOW(B1)，F(xiàn)OLLOW(B2)，F(xiàn)OLLOW(Bn）兩兩交集都為空，就可用上述規(guī)則解決沖突，即考查當前輸入符號決定動作。1) 若aa1，a2，, am，則移進。2) 若aFOLLOW(Bi)，i=1,2n，則用Bii進行歸約。3) 此外，報錯。,如果對于一個文法的LR(0)項目集規(guī)范族的某些項目集或LR(0)分析表中所含有的動作沖突都能用上述方法解決，則稱這個文法是SLR(1)文法，所構造的分析表為SLR(1)分析表，使用SLR(1)分析表的分析器稱為SLR(1)分析器。,例如，構造算術表達式文法的LR(0)項目集規(guī)范族，然后分析它是LR(0)文法還是SLR(1)文法，現(xiàn)將表達式文法拓廣如下：(0) SE(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi,識別該文法活前綴的有限自動機,I1： SEEE+T,I2： ETTT*F,I9： EE+T T