《編譯第六章》PPT課件.ppt

《《編譯第六章》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《編譯第六章》PPT課件.ppt（142頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第六章 LR分析法及 分析程序自動構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 1） 第一節(jié) 概述 本章介紹上下文無關(guān)文法的 LR分析方法及分 析程序的自動構(gòu)造 LR：自左至右掃描 ,最右推導的逆過程 一、 LR方法 1.基本思想 在規(guī)范歸約過程中，一方面記住已移進 和歸約的整個符號串，另一方面根據(jù)當前所 用的產(chǎn)生式推測未來可能碰到的輸入符號 . 第六章 LR分析法及分析程序自動構(gòu)造（ 2） 第一節(jié) 概述 一、 LR方法 2.優(yōu)缺點 優(yōu)點：與其它技術(shù)相比，適應(yīng)文法范圍更廣。能力 更強，識別效率相當，尤其在自左向右掃描輸入串 時就能發(fā)現(xiàn)其中錯誤，并能準確指出出錯位置。 缺點：若用手工構(gòu)造分析程序

2、，工作量太大，且容 易出錯，所以必須使用自動產(chǎn)生這種分析程序的產(chǎn) 生器。 3.產(chǎn)生器的作用 應(yīng)用產(chǎn)生器產(chǎn)生一大類上下文無關(guān)文法的 LR分析程 序 對二義性文法或難分析的特殊文法，施加一些限制， 使之能用 LR分析。 第六章 LR分析法及分析程序自動構(gòu)造（ 3） LR分析法通過 LR分析器來實現(xiàn) 總控程序 分析表 輸出帶 第一節(jié) 概述 二、 LR分析器 輸入帶 下 推 棧 第六章 LR分析法及分析程序自動構(gòu)造（ 4） 1、從邏輯上說， LR分析器包括兩部分： 總控程序，或稱為語法分析程序； 分析表 注：后面要學習的所有 LR分析器的總控程序都相同。 僅僅是它們的分析表不同 2、總控程序作用： 查

3、分析表，根據(jù)分析表的內(nèi)容做若干簡單動作，如 讀頭后移，入棧出棧等。 注：由于總控程序很簡單，所以產(chǎn)生器的任務(wù)就是 產(chǎn)生分析表 第一節(jié) 概述 二、 LR分析器 第六章 LR分析法及分析程序自動構(gòu)造（ 5） 一個文法的 LR分析器常常對應(yīng)著若干不同分析表， 所有分析表都恰好識別文法所產(chǎn)生的所有語句 本章將討論四種不同分析表構(gòu)造方法 1.LR(0)分析表： 分析能力有限，但這是建立其它 LR分析法的基礎(chǔ)。 2.SLR分析表： 簡單 LR分析表構(gòu)造法，是一種容易實現(xiàn)又有實用價 值的方法，但存在一些文法構(gòu)造不出 SLR分析表 第一節(jié) 概述 三、分析表 第六章 LR分析法及分析程序自動構(gòu)造（ 6） 3、規(guī)

4、范 LR分析表 它能力最強，但實現(xiàn)代價過高，分析表尺寸太大 4、 LALR分析表 向前看 LR分析表構(gòu)造文法，也是一種常用方法 注：實際上， SLR和 LALR分別是對 LR(0)和規(guī)范 LR的 改進 最后，將討論如何使用二義文法構(gòu)造 LR分析器并產(chǎn) 生高效的分析技術(shù) 第一節(jié) 概述 三、分析表 第六章 LR分析法及分析程序自動構(gòu)造（ 7） 6.1 LR分析器 一、 LR分析法的基本思想 在規(guī)范歸約時，當一串貌似句柄的符號串呈現(xiàn)于棧 頂時， LR分析法根據(jù)三方面的信息找句柄： 歷史：記錄在棧內(nèi)的符號串移進，歸約的歷史情況 展望：預(yù)測句柄之后可能出現(xiàn)的信息； 現(xiàn)實：讀頭下的符號 注： LR分析法的

5、基本思想是符號人的思維習慣的， 但實現(xiàn)有困難，因為基于 “ 歷史 ” 對未來的 “ 展望 ” 可能存在多種可能。當把 “ 歷史 ” 和 “ 展望 ” 材 料綜合在一起時復(fù)雜性就大大增加。如果簡化對 “ 展望 ” 的要求，就可獲得實際可行的分析算法。 第六章 LR分析法及分析程序自動構(gòu)造（ 8） 6.1 LR分析器 總控程序 分析表 輸出帶 輸入帶 下 推 棧 二、 LR分析器 一個 LR分析器實際上是帶有下推棧的確定的有限狀 態(tài)自動機?？蓪⒁粋€ “ 歷史 ” 與這個 “ 歷史 ” 下的展 望信息綜合為抽象的一個狀態(tài) 第六章 LR分析法及分析程序自動構(gòu)造（ 9） 1、下推棧： 下推棧用于存放分析

6、輸入串過程中的所有和 “ 歷史 ” 及相應(yīng) “ 展望 ” 信息形成的抽象狀 態(tài) 由于每個狀態(tài)都概括了從分析開始到歸約階 段的全部 “ 歷史 ” 和 “ 展望 ” 信息，所以 LR 分析器的每步動作可由棧頂狀態(tài)和讀頭下符 號唯一確定 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動構(gòu)造（ 10） 1、下推棧： 6.1 LR分析器 二、 LR分析器 sm s0 xm # 狀態(tài)棧 符號棧 下 推 棧 棧頂指針 把一個 “ 歷史 ” 和這個 “ 歷史 ” 下的 “ 展望 ” 信 息綜合為抽象的一個狀態(tài)，下推棧用于存放在對輸 入串進行分析的過程中這些狀態(tài)，由于每個狀態(tài)都 概括了從分

7、析開始到歸約階段的全部 “ 歷史 ” 和 “ 展望 ” 信息，所以棧頂?shù)臓顟B(tài)就可用于決定當前 的動作 第六章 LR分析法及分析程序自動構(gòu)造（ 11） 1、下推棧 ： 6.1 LR分析器 二、 LR分析器 sm s0 xm # 狀態(tài)棧 符號棧 下 推 棧 棧頂指針 為了便于了解棧頂狀態(tài)對正規(guī)分析過程的作用，我們 把棧分為兩欄：狀態(tài)欄和符號欄。符號棧僅用于記錄迄 今移進 -歸約所得到的文法符號，由于它們已經(jīng)被概 括在 “ 狀態(tài) ” 里了，所以對語法分析不起作用。 初始時，狀態(tài)棧放 S0（初態(tài)），符號棧放 “ #” （棧 底符）；棧頂 Sm代表符號棧內(nèi)的符號串 XmXm-1 X1及其展 望信息 第六

8、章 LR分析法及分析程序自動構(gòu)造（ 12） 6.1 LR分析器 二、 LR分析器 2 .分析表 LR分析器的核心是分析表 a1 a2 a n a1 a2 a n A1 A2 A n S0 . . Sk 這張分析表包含兩部分：動作表（ Action)和轉(zhuǎn)向表 (GoTo)， 它們都是二維數(shù)組 Si表示狀態(tài)， ai表示終結(jié)符， Ai表示非終結(jié)符 Action goto 第六章 LR分析法及分析程序自動構(gòu)造（ 13） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4

9、8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 15） 2 .分析表 2）動作表 ACTION ACTIONS,a表示在當前狀態(tài) S下，面臨讀頭下的符號 a所應(yīng) 采取的動作， 注：該動作有四種可能：移進，歸約，出錯，接受 3）轉(zhuǎn)向表 (GOTO) GOTOS,X表示：若 XV T，表示在當前狀態(tài)下，讀入 X應(yīng)轉(zhuǎn) 向什么狀態(tài)；若 XV N，表示當前棧頂句柄歸約成 X后，應(yīng)轉(zhuǎn) 向什么狀態(tài) 注：對終結(jié)符的移進動作和轉(zhuǎn)向動作可

10、以合并在一起填在動 作表中，這樣，轉(zhuǎn)向表可以只保留非終結(jié)符轉(zhuǎn)向部分 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動構(gòu)造（ 14） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 15） 3.總控程序的動作 1）移進

11、 把 (Sm,ai)的下一個狀態(tài) S=GOTO(Sm,ai)連同讀頭下 符號推進棧內(nèi) ,棧頂成為 (S,ai),讀頭前進一格 2）歸約 指用某產(chǎn)生式 A b進行歸約。若 b的長度為 g，則 彈出棧頂?shù)?g個元素，使得棧頂?shù)臓顟B(tài)變成 Sm-g,然后把 （ Sm-g,A)的下一個狀態(tài) S=GOTO(Sm-g,A)連同非終結(jié)符 A一起推進 棧，棧頂變成（ S,A)，讀頭不動。 3）接受 分析成功，退出總控程序 4）報錯 輸入串出錯，調(diào)出相應(yīng)出錯程序 注：不管哪一類分析程序，總控程序的動作都一樣。程序本 身很簡單，按動作表中填的內(nèi)容具體實施而已。 6.1 LR分析器 二、 LR分析器 第六章 LR分析

12、法及分析程序自動構(gòu)造（ 17） 6.1 LR分析器 例：根據(jù)表達式文法的 LR分析表分析輸入串 i*i+i的 LR動作過程 E E+T E T T T*F T F F (E) F i 第六章 LR分析法及分析程序自動構(gòu)造（ 18） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5

13、 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 注：表中符號的含義： Sj shift j,指將讀入符號 a移進棧內(nèi)并轉(zhuǎn)到 j狀 態(tài)，棧頂變成（ j,a); rj reduce j ,按第 j號產(chǎn)生式進行歸約； acc accept,分析成功； 空白格 出錯標志，若填入相應(yīng)出錯處理程序的 編號，便轉(zhuǎn)相應(yīng)程序處理。 分析過程 LR分析器的動作情況也可以描述成機器內(nèi)部的格 局間轉(zhuǎn)換，其格局用三元式表示為（狀態(tài)棧，已歸 約的符號棧，待繼續(xù)分析的輸入串） 6.1 LR分析器 第六章 LR分析法及分析程序自動構(gòu)造（ 16） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S

14、4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 i*i+i # E E+T E T T T*F T F F (E) F i 第六章 LR分析法及分析程序自動構(gòu)造（ 20） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2

15、 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 *i+i # E E+T E T T T*F T F F (E) F i 5 i 5 i 第六章 LR分析法及分析程序自動構(gòu)造（ 21） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r

16、2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 *i+i # E E+T E T T T*F T F F (E) F i 3 F 第六章 LR分析法及分析程序自動構(gòu)造（ 22） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4

17、 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 *i+i # E E+T E T T T*F T F F (E) F i 3 F 第六章 LR分析法及分析程序自動構(gòu)造（ 23） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3

18、5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 *i+i # E E+T E T T T*F T F F (E) F i 2 T 第六章 LR分析法及分析程序自動構(gòu)造（ 24） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6

19、 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 i+i # E E+T E T T T*F T F F (E) F i 2 T 7 * 第六章 LR分析法及分析程序自動構(gòu)造（ 25） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7

20、 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 +i # E E+T E T T T*F T F F (E) F i 2 T 5 i 第六章 LR分析法及分析程序自動構(gòu)造（ 26） 7 * 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10

21、 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 +i # E E+T E T T T*F T F F (E) F i 2 T 7 * 5 i 第六章 LR分析法及分析程序自動構(gòu)造（ 27） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11

22、 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 +i # E E+T E T T T*F T F F (E) F i 2 T 7 * 10 F 第六章 LR分析法及分析程序自動構(gòu)造（ 28） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1

23、 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 +i # E E+T E T T T*F T F F (E) F i 10 F 7 * 2 T 第六章 LR分析法及分析程序自動構(gòu)造（ 29） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r

24、3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構(gòu)造（ 19） 0 # 狀態(tài)、符號棧 +i# E E+T E T T T*F T F F (E) F i 2 T 第六章 LR分析法及分析程序自動構(gòu)造（ 30） 狀態(tài)棧 符號棧 輸入串 動作 0 # i*i+i# 05 #i *i+i# 移進 03 #F *i+i# R6歸約 02 #T *i+i# R4歸約 027 #T* i+i# 移進 0275 #T*i +i# 移進 02710 #T*F +i# R6歸約 02 #T +i# R3歸約 01 #E +i# R2歸約 016 #E+ i# 移進 0165

25、#E+i # 移進 0163 #E+F # R6歸約 0169 #E+T # R4歸約 01 #E # acc 分析成功 第六章 LR分析法及分析程序自動構(gòu)造（ 31） 4、 LR文法 定義：如果某一文法能夠構(gòu)造一張分析表， 使得表中每一元素至多只有一種明確動作， 則該文法稱為 LR文法 注： 1）并非所有 CFG都是 LR文法，但對于多 數(shù)程序設(shè)計語言來說，一般都可以用 LR文法 描述 2）和 LL(1)分析法相比， LR分析法適應(yīng) 的文法范圍要廣一些 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動構(gòu)造（ 32） 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造

26、一、 LR(0)分析表構(gòu)造基本思想 構(gòu)造 LR(0)分析表基本思想： 只根據(jù)歷史信息識別呈現(xiàn)于棧頂?shù)木浔?注： LR(0)分析表構(gòu)造的思想和方法是構(gòu)造 其它 LR分析法的基礎(chǔ) 構(gòu)造 LR(0)分析表基本策略 構(gòu)造文法 G的一個有限自動機，它能識別文 法中的所有活前綴 第六章 LR分析法及分析程序自動構(gòu)造（ 33） 1.活前綴 字的前綴是指該字的任意首部 例如：字 ABC的前綴有 e,A,AB,ABC 活前綴的概念： 指規(guī)范句型的一個前綴，這種前綴不含句柄 之后的任何符號 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 3

27、4） 例如：根據(jù)下面的文法識別輸入串 abbcde 1) S aAcBe 2) A b 3) A Ab 4) B d 為每條產(chǎn)生式的尾部加上用 I表示的產(chǎn)生式序號 1) S aAcBe1 2) A b2 3) A Ab3 4) B d4 第六章 LR分析法及分析程序自動構(gòu)造（ 35） 用最右推導方式來識別，推導時把序號也帶上 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 若用最左歸約的方式進行識別，則完全是上面的逆過 程 規(guī)范句型 abbcde的前綴有： e,a ab 規(guī)范句型 aAbcde的前綴有 : e,a,aA,aAb 規(guī)范句型 aAbcde的前綴有 : e

28、,a,aA,aAc,aAcd 規(guī)范句型 aAbcde的前綴有 : e,a,aA,aAc,aAcB,aAcBe 第六章 LR分析法及分析程序自動構(gòu)造（ 36） 1.活前綴 活前綴有兩種類型： 1）歸態(tài)活前綴 :活前綴的尾部正好是句柄之 尾，這時可以進行歸約，歸約之后又成為另 一句型的活前綴 2）非歸態(tài)活前綴 :句柄尚未形成，需要繼續(xù) 移進若干符號之后才能形成句柄 6.2 LR(0)項目 集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 37） 2.構(gòu)造自動機識別活前綴 對于一個文法?？梢詷?gòu)造有限自動機，它能識別 G 的所有活前綴 由于產(chǎn)生式右部的

29、符號串就是句柄。若某些符號串 都已進棧，則表示它已處于 歸態(tài)活前綴 。若只有部 分進棧，則表示它處于 非歸態(tài)活前綴 。要想知道活 前綴有多大部分進棧了，可以為每個產(chǎn)生式構(gòu)造一 個自動機，由它的狀態(tài)來記住當前情況，此 “ 狀態(tài) ” 稱為 “ 項目 ” ，這些自動機的全體就是能識別所有 活前綴的有限自動機。 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 38） 2.構(gòu)造自動機識別活前綴 1）項目： 在文法的每個產(chǎn)生式右部添加一個圓點，就成為 G 的一個 LR(0)項目（簡稱項目） 注：圓點在產(chǎn)生式中的位置不同則是不同項目

30、注： （ 1）可以把圓點理解為棧內(nèi)外的分界線 （ 2）產(chǎn)生式右部符號串的長度為 n，則可以分解 為 n+1個項目 （ 3）產(chǎn)生式 A e只有一個項目 A 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 39） 2.構(gòu)造自動機識別活前綴 1）項目： 例如，產(chǎn)生式 A XYZ對應(yīng)四個項目 A XYZ, 預(yù)期要歸約的句柄是 XYZ，但都未進棧 A XYZ,預(yù)期要歸約的句柄是 XYZ，但 X進棧 A XYZ,預(yù)期要歸約的句柄是 XYZ，僅 XY進棧 A XYZ,Z處于歸態(tài)活前綴， XYZ可進行歸約，這 個項目就是歸約項目 6.2

31、 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 41） 2.構(gòu)造自動機識別活前綴 2）由項目構(gòu)造 NFA的構(gòu)造方法 （ 1）將文法進行拓廣，保證文法開始符號 S不出 現(xiàn)在任何產(chǎn)生式右部，即增加產(chǎn)生式 S S, 并令 S S作為初態(tài)項目； （ 2）凡圓點右串的最右邊的項目稱終態(tài)項目或 稱歸約項目。而 S S稱為接受項目； 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 40） 2.構(gòu)造自動機識別活前綴 2）由項目構(gòu)造 NFA的構(gòu)造方法 （ 3）設(shè)項目 i為

32、 X X1 .Xi-1Xi Xn,項目 j為 X X1 .XiXi+1 Xn,則從項目畫一弧線射向 j， 標記為 Xi;若 Xi是終結(jié)符，則項目 i稱為移進項目， Xi是非終結(jié)符則稱項目 i為待約項目； （ 4）若項目 i為 X aAb,其中 A是非終結(jié)符，則從 i 項目畫 e弧射向所有 A g的項目， gV * 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 42） 2.構(gòu)造自動機識別活前綴 2）由項目構(gòu)造 NFA的構(gòu)造方法 注： 1）構(gòu)造出的 NFA是包含有 e串的 NFA，可以使用子 集法使之確定化，使之成為一個以

33、項目集為狀態(tài)的 DFA，這個 DFA就是建立 LR分析算法的基礎(chǔ) 2）相應(yīng) DFA的每個狀態(tài)是一個項目集，稱作 LR(0) 項目集，整個狀態(tài)集稱為 LR(0)項目集規(guī)范簇 3）在 DFA的一個狀態(tài)對應(yīng)的項目集內(nèi)，每個項目 是 “ 等價 ” 的，即從期待歸約的角度看相同 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 43） 2.構(gòu)造自動機識別活前綴 2）由項目構(gòu)造 NFA的構(gòu)造方法 注： 4）有一個唯一的初態(tài)和一個唯一的接受 態(tài)，但有若干個歸約態(tài)，表示有若干種活前 綴的識別狀態(tài) 5）狀態(tài)反映了識別句柄的情況，既句柄 的大

34、多部分已進棧，即知道了歷史情況 6）手工構(gòu)造文法的項目集規(guī)范簇很困難 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 44） 例如：有一拓廣的文法 G6.1構(gòu)造識別活前綴的 NFA S E E aA|bB A cA|d B cB|d 解： 1、這個文法的項目有： 1.S E 2.S E 3.E aA 4.E aA 5.E aA 6.A cA 7.A cA 8.A cA 9.A d 10.A d 11.E bB 12.E bB 13.E bB 14.B cB 15.B cB 16.B cB 17.B d 18.B d 第六

35、章 LR分析法及分析程序自動構(gòu)造（ 45） 2.構(gòu)造識別活前綴的 NFA 3 8 6 7 4 9 10 1 5 2 11 15 14 12 1 6 13 1 8 17 e a E e c e A b e d B e c B d e e e e A e 第六章 LR分析法及分析程序自動構(gòu)造（ 46） 確定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 8:A cA 7:E bB 11:B d 9:B cB c c b E c c a B

36、d d B A d A d 第六章 LR分析法及分析程序自動構(gòu)造（ 47） 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項目集規(guī)范族的構(gòu)造 3. LR(0)項目集規(guī)范族的機器構(gòu)造 1）拓廣文法： 增加 S S產(chǎn)生式 ,使文法的開始符 號不出現(xiàn)在任何產(chǎn)生式右部，從而保證有唯一的接受 項目 注：即使原開始符號 S不出現(xiàn)在任何產(chǎn)生式右部， 為了統(tǒng)一起見也要增加該產(chǎn)生式 第六章 LR分析法及分析程序自動構(gòu)造（ 48） 3. LR(0)項目集規(guī)范族的機器構(gòu)造 2）定義和構(gòu)造項目集的閉包 設(shè) I是拓廣文法 G的一個項目集，定義和構(gòu)造 I的閉 包 CLOSURE(I) 構(gòu)造文法：

37、A.I的任何項目都屬于 CLOSURE(I); B.若 A aBb屬于 CLOSURE(I),B是非終結(jié)符 ,那 么，對于任何關(guān)于 B的產(chǎn)生式 B g,項目 B g也屬于 CLOSURE(I); C.重復(fù)執(zhí)行步驟 B,直到 CLOSURE(I)不再擴大為止 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 49） 3. LR(0)項目集規(guī)范族的機器構(gòu)造 3）狀態(tài)轉(zhuǎn)換函數(shù) GO GO(I,X)定義為 CLOSURE(J),其中 I,J都是項目 集， X(V NV T), J=任何形如 A aXb的項目 |A aXbI

38、 注：其含義是對于任意項目集 I,由于 I中有 A aXb項目， J中有 A aXb項目，表 示識別活前綴又移進一個符號 X 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 50） 3. LR(0)項目集規(guī)范族的機器構(gòu)造 4)構(gòu)造 LR(0)項目集規(guī)范族的算法 過程如下： C=CLOSURE(S S) /*初態(tài)項目集 */ DO for (對 C中每個項目集 I和 G中每個文法符號 X) IF ( GO(I,X)非空且不屬于 C) 把 GO(I,X)加入 C中 WHILE C 仍然在擴大 注：其中 C是集合，用于

39、存放全部項目集 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 51） 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 注： 1）此算法是迭代算法。置了 C的初態(tài)（初態(tài)僅 包含第一個項目集）后，每經(jīng)過一次 FOR語句。就 擴大一次 C中的項目集數(shù)，直到項目集數(shù)不再增加 為止。 2）此算法是從 I0開始，按該項目集內(nèi)的項目順序依 次求出所有后繼項目集，由這樣一層一層向下生成 的所有項目集的方法避免了項目集的遺漏。 3）若在項目集中存在 A e，不應(yīng)再做 GO函數(shù)轉(zhuǎn) 向其它項目集，因為 A e和 A e是同一項

40、 目，都是 A 項目，它本身是歸約項目，不存在 后繼項目。 4）由這個項目集規(guī)范族 C中各個狀態(tài)及狀態(tài)函數(shù) GO 可構(gòu)造一張識別活前綴的 DFA圖。 第六章 LR分析法及分析程序自動構(gòu)造（ 52） 例如：有一拓廣的文法 G6.1構(gòu)造識別活前綴的 NFA S E E aA|bB A cA|d B cB|d 解： 1、這個文法的項目有： 1.S E 2.S E 3.E aA 4.E aA 5.E aA 6.A cA 7.A cA 8.A cA 9.A d 10.A d 11.E bB 12.E bB 13.E bB 14.B cB 15.B cB 16.B cB 17.B d 18.B d 第六章

41、 LR分析法及分析程序自動構(gòu)造（ 45） 3. LR(0)項目集規(guī)范族的機器構(gòu)造 2）定義和構(gòu)造項目集的閉包 設(shè) I是拓廣文法 G的一個項目集，定義和構(gòu)造 I的閉 包 CLOSURE(I) 構(gòu)造文法： A.I的任何項目都屬于 CLOSURE(I); B.若 A aBb屬于 CLOSURE(I),B是非終結(jié)符 ,那 么，對于任何關(guān)于 B的產(chǎn)生式 B g,項目 B g也屬于 CLOSURE(I); C.重復(fù)執(zhí)行步驟 B,直到 CLOSURE(I)不再擴大為止 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 49） 0

42、:S E E aA E bB 第六章 LR分析法及分析程序自動構(gòu)造（ 67） 0:S E E aA E bB 2: E aA A cA A dc 1:S E 3:E bB B cB B d a E b 第六章 LR分析法及分析程序自動構(gòu)造（ 68） 0:S E E aA E bB 2: E aA A cA A d 1:S E 3:E bB B cB B d a E b 4:A cA A cA A d 10:A d 6:E aA c d A 第六章 LR分析法及分析程序 自動構(gòu)造（ 69） 1:S E 0:S E E aA E bB 4:A cA A cA E d 2: E aA A cA E

43、dc 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 7:E bB 11:B d c b E c a d B A d 第六章 LR分析法及分析程序自動構(gòu)造（ 70） 確定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 7:E bB 11:B d 9:B cB c c b E c a B d d B A d 第六章 LR分析法及分析程序自動構(gòu)造（ 71） 確定化后 1:S E 0:S E E a

44、A E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 8:A cA 7:E bB 11:B d 9:B cB c c b E c c a B d d B A d A 第六章 LR分析法及分析程序自動構(gòu)造（ 72） 3 8 6 7 4 9 10 1 5 2 11 15 14 12 1 6 13 1 8 17 e a E e c e A b e d B e c B d e e e e A e 第六章 LR分析法及分析程序自動構(gòu)造（ 46） 1、 構(gòu)造 LR(0)分析表 設(shè) C=I0

45、,I1 .In,以各項目集 Ik（ k=0, .n) 的 k作為狀態(tài) 符號，并以包含 S S的項目集作為初始狀態(tài)，同時將 G 文法的產(chǎn)生式進行編號，然后按下列步驟填寫 ACTION表和 GOTO表； 1）若項目 A aab 屬于 Ik的狀態(tài)且 GO(Ik,a)=Ij;a為終結(jié)符， 則置 ACTIONk,a=sj;即移進 a，并轉(zhuǎn)向 Ij狀態(tài)。 2）若項目 A aI k,則對任何終結(jié)符 a（包括語句結(jié) 束符 #），置 ACTIONk,a=rj;即根據(jù) j號產(chǎn)生式進行 歸約。 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 二、 LR(0)分析表的構(gòu)造算法 第六章 LR分析法及分析程序自動構(gòu)

46、造（ 54） 確定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 8:A cA 7:E bB 11:B d 9:B cB c c b E c c a B d d B A d A d 第六章 LR分析法及分析程序自動構(gòu)造（ 47） 1、 構(gòu)造 LR(0)分析表 3）若項目 S S屬于 Ik，則置 ACTIONk,#=accept,簡寫 acc； 4）若 GO(Ik,A)=Ij,A是非終結(jié)符，則置 GOTOk,A=j； 5）分析表中凡不能用

47、步驟 1至 4填入信息的空白項， 均置上出錯標志。 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 二、 LR(0)分析表的構(gòu)造算法 第六章 LR分析法及分析程序自動構(gòu)造（ 55） 2.LR(0)文法 定義：若文法 G按上面算法構(gòu)造出來的分析表 不包含多重定義項，則該文法 G是 LR(0)文法。 注： 1）這說明 LR(0)文法的每個項目集中不 包含有任何沖突項目 2） LR(0)文法的能力很弱，沒有使用價 值，但可以利用它的構(gòu)造算法來構(gòu)造出其它 LR分析表。 6.2 LR(0)項目集族和 LR(0)分析表的構(gòu)造 二、 LR(0)分析表的構(gòu)造算法 第六章 LR分析法及分析程序自動構(gòu)造（

48、56） 例如：下面的文法是 LR(0)文法，但對這個文法的 各個產(chǎn)生式給予編號并寫成： 0.S E 1.E aA 2.E bB 3.A cA 4.A d 5.B cB 6.B d 第六章 LR分析法及分析程序自動構(gòu)造（ 57） 確定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 8:A cA 7:E bB 11:B d 9:B cB c c b E c c a B d d B A d A d 第六章 LR分析法及分析程序自動構(gòu)造（ 47

49、） 例如：下面文法 G的 LR(0)項目集規(guī)范族中含有如下一個項 目集（狀態(tài)） I : I=X d bb /*移進項目 */ A a /*歸約項目 */ B a /*歸約項目 */ 這三個項目告訴我們應(yīng)做的動作各不相同，出現(xiàn)了移 進 歸約沖突和歸約 歸約沖突。這個文法一定不是 LR(0)文法 第六章 LR分析法及分析程序自動構(gòu)造（ 59） 6.3 SLR分析表的構(gòu)造 SLR是的一種改進，它在歸約時除了考慮歷史情況 之外還考慮了一點現(xiàn)實。 一、消除沖突 1、一個有沖突的項目集?？梢愿鶕?jù)讀頭下符號的 不同來消除沖突。 一般而言，對于任何形如 I=X d bb, A a, B a 的 LR(0)項目

50、集，若 Follow(A) Follow(B)= 且 b Follow(A)， b Follow(B),則可以根據(jù)當前讀頭下符號 a來消除 沖突，即在構(gòu)造分析表的算法中做一些改變 第六章 LR分析法及分析程序自動構(gòu)造（ 60） 6.3 SLR分析表的構(gòu)造 一、消除沖突 1)若當前輸入符 a=b,做移進 ; 2)若當前輸入符 aFollow(A), 按 A a產(chǎn) 生式歸約； 3)若當前輸入符 aFollow(B), 按 B a產(chǎn) 生式歸約； 4)其他，報錯。 二、構(gòu)造 SLR分析表的算法 設(shè) C=I0,I1, .In以各項目集 Ik(k=0, .n)作的 k為狀態(tài)序號，并以 S S包含的項目集作

51、為初始 狀態(tài)，同時將產(chǎn)生式進行編號，然后按下列步驟填 寫 ACTION表和 GOTO表： 1）若項目 A aab屬于 Ik狀態(tài)且 Go(Ik,a)=Ij， a為 終結(jié)符，則置 ACTIONk,a=Sj；即：移進 a，并轉(zhuǎn)向 Ij狀態(tài)。 2）若項目 A a IK。則對任何終結(jié)符 a Follow(A) ，置 ACTIONk,a=rj；其中 j為產(chǎn)生 式 A a的編號，即根據(jù) j號產(chǎn)生式 A a進行歸 約 第六章 LR分析法及分析程序自動構(gòu)造（ 84） 6.3 SLR分析表的構(gòu)造 6.3 SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 3）若項目 S S屬于 Ik，則 ACTIONk,#=acc

52、； 4）若 GO(Ik,A)=Ij， A是非終結(jié)符，則 GoTok,A=j； 5）分析表中凡不能用步驟 1至 4填入信息的空白項， 均置上 “ 出錯標志 ” 。 注： 1）若文法按上面算法構(gòu)造出來的分析表不包含 多重定義項，則該文法 G是 SLR文法。 2）二義文法決不是 LR文法 3） SLR分析法包含的展望信息是體現(xiàn)在利用了 Follow(A)信息，可以解決 “ 歸約 歸約 ” 沖突。 4） SLR分析法沒有包含足夠的展望信息，不能完 全解決 “ 移進 歸約 ” 沖突，需要改進。 第六章 LR分析法及分析程序自動構(gòu)造（ 85） 例如：試構(gòu)造表達式文法 G(E)的 SLR分析表 0.S E

53、1.E E+T 2.E T 3.T T*F 4.T F 5. F (E) 6.F i 解 :按照求 LR(0)項目集規(guī)范族的算法 ,求得 G(E)文法 得項目集族如下圖 : 6.3 SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 第六章 LR分析法及分析程序自動構(gòu)造（ 86） I5:F i I0:S E E E+T E T T T*F T F F (E) F i I2:E T T T*F I1:S E E E+T I4:F (E) E E+T E T T T*F T F F (E) F i I3:T F I6:E E+T T T*F T F F (E) F i I10:T TF I7:T T

54、*F F (E) F i I9:E E+T T T*F I8:F (E) E E+T I11:F (E) i i ( F T I2 ( I4 T T E ) E F * F i ( I5 I3 I5 i + ( 第六章 LR分析法及分析程序自動構(gòu)造（ 87） F * 6.3 SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 構(gòu)造 SLR分析表時要注意項目集族中 I1,I2,I9 三個項目集 ,其中含有沖突 : I1:S E I2:E T I9:E E+T E E+T T T*F T T*F 根據(jù)原來的文法分別求 S ,E的 Follow集 ,按 SLR方法進行分析 ,得 第六章 LR分析法及分

55、析程序自動構(gòu)造（ 88） 狀態(tài) ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 S7 r1 r1 10 r3 r3 r3 r3 第六章 LR分析法及分析程序自動構(gòu)造（ 89） 例：一個非 SLR文法的例子 ,有如下文法 : 1.S S 1.S L=R 3.S R 4.L *R 5.L i 6. R L 按照求 LR(0)項目集規(guī)范族的算法 ,求得 G(S

56、)文法得 項目集族如下圖 : 6.3 SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 第六章 LR分析法及分析程序自動構(gòu)造（ 90） 5:L i 0:S S S L=R S R L *R L I R L 3:S R 4: L *R R L L i L i 6:S L=R R L L *R L i 8:R L 7:L *R 2:S L=R R L 1:S S 9:S L=R = i S * * i R i * L L R R 第六章 LR分析法及分析程序自動構(gòu)造（ 91） L 狀態(tài) ACTION GOTO = i * # S L R 0 S5 S4 1 2 3 1 acc 2 S6/ r6 r

57、6 3 r3 4 S5 S4 8 7 5 r5 r5 6 S5 S4 8 9 7 r4 r4 8 r6 r6 9 r2 第六章 LR分析法及分析程序自動構(gòu)造（ 69） 一 在構(gòu)造 SLR分析表的方法中 ,若項目集 Ik中含有 A a,那么在狀態(tài) K時 ,只要面臨輸入符號 aFOLLOW(A), 就確定采用 A a產(chǎn)生式進行歸約 .但 是在某種情況下 ,當狀態(tài) k呈現(xiàn)于棧頂時 ,棧里的符號 串所構(gòu)成的活前綴 ba未必允許把 a規(guī)約成 A.因為可能 沒有一個規(guī)范句型含有前綴 bA.因此此時用 A a產(chǎn) 生式進行歸約未必有效 . -我們可以從上例中看到這個問題 6.4 規(guī)范 LR分析表的構(gòu)造 對 S

58、LR分析的思考 第六章 LR分析法及分析程序自動構(gòu)造（ 93） 5:L i 0:S S S L=R S R L *R L I R L 3:S R 4: L *R R L L i L i 6:S L=R R L L *R L i 8:R L 7:L *R 2:S L=R R L 1:S S 9:S L=R = i S * * i R i * L L R R 第六章 LR分析法及分析程序自動構(gòu)造（ 91） L 6.4 規(guī)范 LR分析表的構(gòu)造 結(jié)論 : 一由此看出 ,并非隨符都出現(xiàn)在規(guī)范句型中 . 對策 : 一給每個 LR(0)項目添加展望信息 ,即添加句柄之后可 能跟的終結(jié)符 ,因為這些終結(jié)符確實

59、是規(guī)范句型中 跟在句炳之后的 .這就是 LR(1)的方法 . 可能引起的問題 一故 ,LR(1)項目是對 LR(0)項目的分裂 ,若文法中終結(jié) 符的數(shù)目為 n,則每個 LR(0)項目都可以分裂成 n個 LR(1)項目 .這可能會引起分析表的膨脹 . 第六章 LR分析法及分析程序自動構(gòu)造（ 95） 6.4 規(guī)范 LR分析表的構(gòu)造 一、相關(guān)定義 1、 LR(1)項目：形如（ A ab,a)的二元式稱為 LR(1)項目，其中， A ab是文法的一個產(chǎn)生式， a是終結(jié)符，稱為搜索符。 1） LR(1)項目是對 LR(0)項目的分裂，若文法中終結(jié) 符的數(shù)目為 n，則每個 LR(0)項目可以分裂成 n個

60、LR(1)項目。 2）（ A ab,a)的含義：預(yù)期當棧頂句柄 ab形成 后，在讀頭下讀到 a，此時 a在棧內(nèi)， b還未入棧， 那它展望了句柄后的一個符號。 第六章 LR分析法及分析程序自動構(gòu)造（ 72） 6.4 規(guī)范 LR分析表的構(gòu)造 一、相關(guān)定義 2、有效項目： 一若存在規(guī)范推導 S dAw dabw,其中 da 稱規(guī)范句型 dabw的活前綴（記作 g),aFirst( w), 則 LR(1)項目（ A ab,a)對于活前綴 g是有效的， 如果 aFirst （ w),即使 aFollow(A), 項目（ A ab,a)也是無效的。 注： 1）規(guī)范 LR分析法僅考慮有效的 LR(1)項目，

61、在 LR(1)項目中有效的項目并不多。 2）對于多數(shù)程序設(shè)計語言，向前展望一個符 號就是足以決定歸約與否，所以只研究 LR(1). 第六章 LR分析法及分析程序自動構(gòu)造（ 97） 例：對非 SLR文法的例子。有如下文法： -1.S S 2.S aAd -3.S bAc 4.S aec -5.S bed 6.A e 按照求 LR(0)項目集規(guī)范族的算法，求得 G(S)文法 得項目集族，其中某狀態(tài)中發(fā)生移進 -歸約沖突： Ix:S aec A e 由于規(guī)范推導為： S S aAd aed S S aec 第六章 LR分析法及分析程序自動構(gòu)造（ 98） 這兩個最右推導中已包含了活前綴為 ae的所 有

62、句型，可見 “ aAc”決不會是規(guī)范句型，即： 歸約成非終結(jié)符 “ A”之后。其后決不會跟 “ c”. 故：雖然 Follow(A)=c,d,但是（ A e,c) 對活前綴 ae是無效的，僅（ A e,d)是有 效的。 第六章 LR分析法及分析程序自動構(gòu)造（ 99） 6.4 規(guī)范 LR分析表的構(gòu)造 二、構(gòu)造 LR(1)項目集規(guī)范族的算法 1、函數(shù) CLOSURE(I)I的項目集 (1)I的任何項目都屬于 CLOSURE(I); (2)若項目 (A aBb,a)屬于 CLOSURE(I),B g是 一個產(chǎn)生式，那么對于 FIRST(ba)中的每個終結(jié)符 b， 如果 (B g,b)原來不在 CLO

63、SURE(I)中，則把它 加進去； (3)重復(fù)步驟 (2)直到 CLOSURE(I)不再擴大為止。 注：因為 (A aBb,a)屬于 CLOSURE(I),那么 (B g,b)當然也屬于 CLOSURE(I),其中 b必定是跟在 B后面的終結(jié)符，即 bFirst( ba).若 b=e,則 b=a 第六章 LR分析法及分析程序自動構(gòu)造（ 100） 6.4 規(guī)范 LR分析表的構(gòu)造 二、構(gòu)造 LR(1)的項目集規(guī)范族的算法 2、 GO函數(shù) 令 I是一個項目集， X是文法符號，函數(shù) GO(I,X)定義為 GO(I,X)=CLOSURE(J) -其中 J=任何形如（ A aXb,a)的項目 (A aXb

64、,a) I 注：在執(zhí)行轉(zhuǎn)換函數(shù) GO時，搜索符并不改變。 第六章 LR分析法及分析程序自動構(gòu)造（ 101） 6.4 規(guī)范 LR分析表的構(gòu)造 3、構(gòu)造拓廣文法的 LR(1)項目集族 C的算法 PROC ITEMSETLR1 C=CLOSURE (S S,#); DO FOR C中的每個項目集 I和 G的每個文法符號 X IF GO(I,X)非空且不屬于 C 把 GO(I,X)加入 C中； WHILE C 依然擴大； 第六章 LR分析法及分析程序自動構(gòu)造（ 102） 例：有如下文法： 1.S S 2.S L=R 3.S R 4.L *R 5.L i 6.R L 按照求 LR(1)項目集規(guī)范族的算法

65、 ,求 G(S)文法的項 目集族 解 :1、求初態(tài)項目集 I0:從（ S S ,#)項目開始 求閉包 得： 第六章 LR分析法及分析程序自動構(gòu)造（ 103） I0初態(tài) S S,# S L=R,# S R,# L *R,= L i,= R L,# L *R,# L i,# I0初態(tài) S S,# S L=R,# S R,# L *R,=|# L i,=|# R L,# 縮寫為 2、接著利用 GO函數(shù)，對該項目集內(nèi)得各項目求后繼項目集， 然后再對新求的項目集重復(fù)上面的過程，直到項目集不再 增加為止。 第六章 LR分析法及分析程序自動構(gòu)造（ 104） 5:L i,=|# 0 S S, S L=R,#

66、S R,# L *R,=|# L i,=|# R L,# 3:S R,# 4: L *R,=|# R L,# L i, =|# L i, =|# 6:S L=R,# R L,# L *R,=|# L i, =|# 8:R L,# 7:L *R, =|# 2:S L=R,# R L,# 1:S S ,# 9:S L=R,# = i S * * i R i * L L R R 第六章 LR分析法及分析程序自動構(gòu)造（ 91） L I10 I12 6.4 規(guī)范 LR分析表的構(gòu)造 三、構(gòu)造 LR(1)分析表的算法 設(shè) C=I0,I1, .In,以各項目集 Ik(k=0,1, .n)的下標 k為分 析表中的狀態(tài)，并以包含（ S S,#)的項目的狀態(tài)為分析 表初態(tài)。按下列步驟填寫 ACTION表和 GOTO表： 1）若項目（ A aab,b)屬于 Ik，且 GO(Ik,a)=Ij,a為終結(jié)符， 則置 ACTIONk,a=Sj;即：移進 a,并轉(zhuǎn)向 Ij狀態(tài)。 2）若項目（ A a,a) I k,則置 ACTIONk,a=rj;其中 j為 產(chǎn)生式 A a的編號，即根據(jù) j號產(chǎn)生式 A a進行歸約 第六