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

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

1、第六章 LR分析法及 分析程序自動構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 1） 第一節(jié) 概述 本章介紹上下文無關(guān)文法的 LR分析方法及分 析程序的自動構(gòu)造 LR：自左至右掃描 ,最右推導(dǎo)的逆過程 一、 LR方法 1.基本思想 在規(guī)范歸約過程中，一方面記住已移進(jìn) 和歸約的整個符號串，另一方面根據(jù)當(dāng)前所 用的產(chǎn)生式推測未來可能碰到的輸入符號 . 第六章 LR分析法及分析程序自動構(gòu)造（ 2） 第一節(jié) 概述 一、 LR方法 2.優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：與其它技術(shù)相比，適應(yīng)文法范圍更廣。能力 更強(qiáng)，識別效率相當(dāng)，尤其在自左向右掃描輸入串 時就能發(fā)現(xiàn)其中錯誤，并能準(zhǔn)確指出出錯位置。 缺點(diǎ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分析器來實(shí)現(xiàn) 總控程序 分析表 輸出帶 第一節(jié) 概述 二、 LR分析器 輸入帶 下 推 棧 第六章 LR分析法及分析程序自動構(gòu)造（ 4） 1、從邏輯上說， LR分析器包括兩部分： 總控程序，或稱為語法分析程序； 分析表 注：后面要學(xué)習(xí)的所有 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)造法，是一種容易實(shí)現(xiàn)又有實(shí)用價(jià) 值的方法，但存在一些文法構(gòu)造不出 SLR分析表 第一節(jié) 概述 三、分析表 第六章 LR分析法及分析程序自動構(gòu)造（ 6） 3、規(guī)

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

5、基本思想是符號人的思維習(xí)慣的， 但實(shí)現(xiàn)有困難，因?yàn)榛?“ 歷史 ” 對未來的 “ 展望 ” 可能存在多種可能。當(dāng)把 “ 歷史 ” 和 “ 展望 ” 材 料綜合在一起時復(fù)雜性就大大增加。如果簡化對 “ 展望 ” 的要求，就可獲得實(shí)際可行的分析算法。 第六章 LR分析法及分析程序自動構(gòu)造（ 8） 6.1 LR分析器 總控程序 分析表 輸出帶 輸入帶 下 推 棧 二、 LR分析器 一個 LR分析器實(shí)際上是帶有下推棧的確定的有限狀 態(tài)自動機(jī)。可將一個 “ 歷史 ” 與這個 “ 歷史 ” 下的展 望信息綜合為抽象的一個狀態(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)，下推棧用于存放在對輸 入串進(jìn)行分析的過程中這些狀態(tài)，由于每個狀態(tài)都 概括了從分

7、析開始到歸約階段的全部 “ 歷史 ” 和 “ 展望 ” 信息，所以棧頂?shù)臓顟B(tài)就可用于決定當(dāng)前 的動作 第六章 LR分析法及分析程序自動構(gòu)造（ 11） 1、下推棧 ： 6.1 LR分析器 二、 LR分析器 sm s0 xm # 狀態(tài)棧 符號棧 下 推 棧 棧頂指針 為了便于了解棧頂狀態(tài)對正規(guī)分析過程的作用，我們 把棧分為兩欄：狀態(tài)欄和符號欄。符號棧僅用于記錄迄 今移進(jìn) -歸約所得到的文法符號，由于它們已經(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表示在當(dāng)前狀態(tài) S下，面臨讀頭下的符號 a所應(yīng) 采取的動作， 注：該動作有四種可能：移進(jìn)，歸約，出錯，接受 3）轉(zhuǎn)向表 (GOTO) GOTOS,X表示：若 XV T，表示在當(dāng)前狀態(tài)下，讀入 X應(yīng)轉(zhuǎn) 向什么狀態(tài)；若 XV N，表示當(dāng)前棧頂句柄歸約成 X后，應(yīng)轉(zhuǎn) 向什么狀態(tài) 注：對終結(jié)符的移進(jìn)動作和轉(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）移進(jìn)

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

12、法及分析程序自動構(gòu)造（ 17） 6.1 LR分析器 例：根據(jù)表達(dá)式文法的 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移進(jìn)棧內(nèi)并轉(zhuǎn)到 j狀 態(tài)，棧頂變成（ j,a); rj reduce j ,按第 j號產(chǎn)生式進(jìn)行歸約； acc accept,分析成功； 空白格 出錯標(biāo)志，若填入相應(yīng)出錯處理程序的 編號，便轉(zhuǎn)相應(yīng)程序處理。 分析過程 LR分析器的動作情況也可以描述成機(jī)器內(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# 移進(jìn) 03 #F *i+i# R6歸約 02 #T *i+i# R4歸約 027 #T* i+i# 移進(jìn) 0275 #T*i +i# 移進(jìn) 02710 #T*F +i# R6歸約 02 #T +i# R3歸約 01 #E +i# R2歸約 016 #E+ i# 移進(jìn) 0165

25、#E+i # 移進(jìn) 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è)計(jì)語言來說，一般都可以用 LR文法 描述 2）和 LL(1)分析法相比， LR分析法適應(yīng) 的文法范圍要廣一些 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動構(gòu)造（ 32） 6.2 LR(0)項(xiàng)目集族和 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的一個有限自動機(jī)，它能識別文 法中的所有活前綴 第六章 LR分析法及分析程序自動構(gòu)造（ 33） 1.活前綴 字的前綴是指該字的任意首部 例如：字 ABC的前綴有 e,A,AB,ABC 活前綴的概念： 指規(guī)范句型的一個前綴，這種前綴不含句柄 之后的任何符號 6.2 LR(0)項(xiàng)目集族和 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） 用最右推導(dǎo)方式來識別，推導(dǎo)時把序號也帶上 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 若用最左歸約的方式進(jìn)行識別，則完全是上面的逆過 程 規(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)活前綴 :活前綴的尾部正好是句柄之 尾，這時可以進(jìn)行歸約，歸約之后又成為另 一句型的活前綴 2）非歸態(tài)活前綴 :句柄尚未形成，需要繼續(xù) 移進(jìn)若干符號之后才能形成句柄 6.2 LR(0)項(xiàng)目 集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動構(gòu)造（ 37） 2.構(gòu)造自動機(jī)識別活前綴 對于一個文法。可以構(gòu)造有限自動機(jī)，它能識別 G 的所有活前綴 由于產(chǎn)生式右部的

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

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

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

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

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

34、多部分已進(jìn)棧，即知道了歷史情況 6）手工構(gòu)造文法的項(xiàng)目集規(guī)范簇很困難 6.2 LR(0)項(xiàng)目集族和 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、這個文法的項(xiàng)目有： 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)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 3. LR(0)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 1）拓廣文法： 增加 S S產(chǎn)生式 ,使文法的開始符 號不出現(xiàn)在任何產(chǎn)生式右部，從而保證有唯一的接受 項(xiàng)目 注：即使原開始符號 S不出現(xiàn)在任何產(chǎn)生式右部， 為了統(tǒng)一起見也要增加該產(chǎn)生式 第六章 LR分析法及分析程序自動構(gòu)造（ 48） 3. LR(0)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 2）定義和構(gòu)造項(xiàng)目集的閉包 設(shè) I是拓廣文法 G的一個項(xiàng)目集，定義和構(gòu)造 I的閉 包 CLOSURE(I) 構(gòu)造文法：

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

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

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

40、 目，都是 A 項(xiàng)目，它本身是歸約項(xiàng)目，不存在 后繼項(xiàng)目。 4）由這個項(xiàng)目集規(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、這個文法的項(xiàng)目有： 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)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 2）定義和構(gòu)造項(xiàng)目集的閉包 設(shè) I是拓廣文法 G的一個項(xiàng)目集，定義和構(gòu)造 I的閉 包 CLOSURE(I) 構(gòu)造文法： A.I的任何項(xiàng)目都屬于 CLOSURE(I); B.若 A aBb屬于 CLOSURE(I),B是非終結(jié)符 ,那 么，對于任何關(guān)于 B的產(chǎn)生式 B g,項(xiàng)目 B g也屬于 CLOSURE(I); C.重復(fù)執(zhí)行步驟 B,直到 CLOSURE(I)不再擴(kuò)大為止 6.2 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項(xiàng)目集規(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,以各項(xiàng)目集 Ik（ k=0, .n) 的 k作為狀態(tài) 符號，并以包含 S S的項(xiàng)目集作為初始狀態(tài)，同時將 G 文法的產(chǎn)生式進(jìn)行編號，然后按下列步驟填寫 ACTION表和 GOTO表； 1）若項(xiàng)目 A aab 屬于 Ik的狀態(tài)且 GO(Ik,a)=Ij;a為終結(jié)符， 則置 ACTIONk,a=sj;即移進(jìn) a，并轉(zhuǎn)向 Ij狀態(tài)。 2）若項(xiàng)目 A aI k,則對任何終結(jié)符 a（包括語句結(jié) 束符 #），置 ACTIONk,a=rj;即根據(jù) j號產(chǎn)生式進(jìn)行 歸約。 6.2 LR(0)項(xiàng)目集族和 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）若項(xiàng)目 S S屬于 Ik，則置 ACTIONk,#=accept,簡寫 acc； 4）若 GO(Ik,A)=Ij,A是非終結(jié)符，則置 GOTOk,A=j； 5）分析表中凡不能用

47、步驟 1至 4填入信息的空白項(xiàng)， 均置上出錯標(biāo)志。 6.2 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 二、 LR(0)分析表的構(gòu)造算法 第六章 LR分析法及分析程序自動構(gòu)造（ 55） 2.LR(0)文法 定義：若文法 G按上面算法構(gòu)造出來的分析表 不包含多重定義項(xiàng)，則該文法 G是 LR(0)文法。 注： 1）這說明 LR(0)文法的每個項(xiàng)目集中不 包含有任何沖突項(xiàng)目 2） LR(0)文法的能力很弱，沒有使用價(jià) 值，但可以利用它的構(gòu)造算法來構(gòu)造出其它 LR分析表。 6.2 LR(0)項(xiàng)目集族和 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)項(xiàng)目集規(guī)范族中含有如下一個項(xiàng) 目集（狀態(tài)） I : I=X d bb /*移進(jìn)項(xiàng)目 */ A a /*歸約項(xiàng)目 */ B a /*歸約項(xiàng)目 */ 這三個項(xiàng)目告訴我們應(yīng)做的動作各不相同，出現(xiàn)了移 進(jìn) 歸約沖突和歸約 歸約沖突。這個文法一定不是 LR(0)文法 第六章 LR分析法及分析程序自動構(gòu)造（ 59） 6.3 SLR分析表的構(gòu)造 SLR是的一種改進(jìn)，它在歸約時除了考慮歷史情況 之外還考慮了一點(diǎn)現(xiàn)實(shí)。 一、消除沖突 1、一個有沖突的項(xiàng)目集?？梢愿鶕?jù)讀頭下符號的 不同來消除沖突。 一般而言，對于任何形如 I=X d bb, A a, B a 的 LR(0)項(xiàng)目

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

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

52、； 4）若 GO(Ik,A)=Ij， A是非終結(jié)符，則 GoTok,A=j； 5）分析表中凡不能用步驟 1至 4填入信息的空白項(xiàng)， 均置上 “ 出錯標(biāo)志 ” 。 注： 1）若文法按上面算法構(gòu)造出來的分析表不包含 多重定義項(xiàng)，則該文法 G是 SLR文法。 2）二義文法決不是 LR文法 3） SLR分析法包含的展望信息是體現(xiàn)在利用了 Follow(A)信息，可以解決 “ 歸約 歸約 ” 沖突。 4） SLR分析法沒有包含足夠的展望信息，不能完 全解決 “ 移進(jìn) 歸約 ” 沖突，需要改進(jìn)。 第六章 LR分析法及分析程序自動構(gòu)造（ 85） 例如：試構(gòu)造表達(dá)式文法 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)項(xiàng)目集規(guī)范族的算法 ,求得 G(E)文法 得項(xiàng)目集族如下圖 : 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分析表時要注意項(xiàng)目集族中 I1,I2,I9 三個項(xiàng)目集 ,其中含有沖突 : I1:S E I2:E T I9:E E+T E E+T T T*F T T*F 根據(jù)原來的文法分別求 S ,E的 Follow集 ,按 SLR方法進(jìn)行分析 ,得 第六章 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)項(xiàng)目集規(guī)范族的算法 ,求得 G(S

56、)文法得 項(xiàng)目集族如下圖 : 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分析表的方法中 ,若項(xiàng)目集 Ik中含有 A a,那么在狀態(tài) K時 ,只要面臨輸入符號 aFOLLOW(A), 就確定采用 A a產(chǎn)生式進(jìn)行歸約 .但 是在某種情況下 ,當(dāng)狀態(tài) k呈現(xiàn)于棧頂時 ,棧里的符號 串所構(gòu)成的活前綴 ba未必允許把 a規(guī)約成 A.因?yàn)榭赡?沒有一個規(guī)范句型含有前綴 bA.因此此時用 A a產(chǎn) 生式進(jì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)項(xiàng)目添加展望信息 ,即添加句柄之后可 能跟的終結(jié)符 ,因?yàn)檫@些終結(jié)符確實(shí)

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

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

61、在 LR(1)項(xiàng)目中有效的項(xiàng)目并不多。 2）對于多數(shù)程序設(shè)計(jì)語言，向前展望一個符 號就是足以決定歸約與否，所以只研究 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)項(xiàng)目集規(guī)范族的算法，求得 G(S)文法 得項(xiàng)目集族，其中某狀態(tài)中發(fā)生移進(jìn) -歸約沖突： Ix:S aec A e 由于規(guī)范推導(dǎo)為： S S aAd aed S S aec 第六章 LR分析法及分析程序自動構(gòu)造（ 98） 這兩個最右推導(dǎo)中已包含了活前綴為 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)項(xiàng)目集規(guī)范族的算法 1、函數(shù) CLOSURE(I)I的項(xiàng)目集 (1)I的任何項(xiàng)目都屬于 CLOSURE(I); (2)若項(xiàng)目 (A aBb,a)屬于 CLOSURE(I),B g是 一個產(chǎn)生式，那么對于 FIRST(ba)中的每個終結(jié)符 b， 如果 (B g,b)原來不在 CLO

63、SURE(I)中，則把它 加進(jìn)去； (3)重復(fù)步驟 (2)直到 CLOSURE(I)不再擴(kuò)大為止。 注：因?yàn)?(A aBb,a)屬于 CLOSURE(I),那么 (B g,b)當(dāng)然也屬于 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)的項(xiàng)目集規(guī)范族的算法 2、 GO函數(shù) 令 I是一個項(xiàng)目集， X是文法符號，函數(shù) GO(I,X)定義為 GO(I,X)=CLOSURE(J) -其中 J=任何形如（ A aXb,a)的項(xiàng)目 (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)項(xiàng)目集族 C的算法 PROC ITEMSETLR1 C=CLOSURE (S S,#); DO FOR C中的每個項(xiàng)目集 I和 G的每個文法符號 X IF GO(I,X)非空且不屬于 C 把 GO(I,X)加入 C中； WHILE C 依然擴(kuò)大； 第六章 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)項(xiàng)目集規(guī)范族的算法

65、 ,求 G(S)文法的項(xiàng) 目集族 解 :1、求初態(tài)項(xiàng)目集 I0:從（ S S ,#)項(xiàng)目開始 求閉包 得： 第六章 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ù)，對該項(xiàng)目集內(nèi)得各項(xiàng)目求后繼項(xiàng)目集， 然后再對新求的項(xiàng)目集重復(fù)上面的過程，直到項(xiàng)目集不再 增加為止。 第六章 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,以各項(xiàng)目集 Ik(k=0,1, .n)的下標(biāo) k為分 析表中的狀態(tài)，并以包含（ S S,#)的項(xiàng)目的狀態(tài)為分析 表初態(tài)。按下列步驟填寫 ACTION表和 GOTO表： 1）若項(xiàng)目（ A aab,b)屬于 Ik，且 GO(Ik,a)=Ij,a為終結(jié)符， 則置 ACTIONk,a=Sj;即：移進(jìn) a,并轉(zhuǎn)向 Ij狀態(tài)。 2）若項(xiàng)目（ A a,a) I k,則置 ACTIONk,a=rj;其中 j為 產(chǎn)生式 A a的編號，即根據(jù) j號產(chǎn)生式 A a進(jìn)行歸約 第六