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

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

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

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

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

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

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

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

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

8、章 LR分析法及分析程序自動(dòng)構(gòu)造（ 12） 6.1 LR分析器 二、 LR分析器 2 .分析表 LR分析器的核心是分析表 a1 a2 a n a1 a2 a n A1 A2 A n S0 . . Sk 這張分析表包含兩部分：動(dòng)作表（ Action)和轉(zhuǎn)向表 (GoTo)， 它們都是二維數(shù)組 Si表示狀態(tài)， ai表示終結(jié)符， Ai表示非終結(jié)符 Action goto 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 15） 2 .分析表 2）動(dòng)作表 ACTION ACTIONS,a表示在當(dāng)前狀態(tài) S下，面臨讀頭下的符號(hào) a所應(yīng) 采取的動(dòng)作， 注：該動(dòng)作有四種可能：移進(jìn)，歸約，出錯(cuò)，接受 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) 注：對(duì)終結(jié)符的移進(jìn)動(dòng)作和轉(zhuǎn)向動(dòng)作可

10、以合并在一起填在動(dòng) 作表中，這樣，轉(zhuǎn)向表可以只保留非終結(jié)符轉(zhuǎn)向部分 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 15） 3.總控程序的動(dòng)作 1）移進(jìn)

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

12、法及分析程序自動(dòng)構(gòu)造（ 17） 6.1 LR分析器 例：根據(jù)表達(dá)式文法的 LR分析表分析輸入串 i*i+i的 LR動(dòng)作過(guò)程 E E+T E T T T*F T F F (E) F i 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 注：表中符號(hào)的含義： Sj shift j,指將讀入符號(hào) a移進(jìn)棧內(nèi)并轉(zhuǎn)到 j狀 態(tài)，棧頂變成（ j,a); rj reduce j ,按第 j號(hào)產(chǎn)生式進(jìn)行歸約； acc accept,分析成功； 空白格 出錯(cuò)標(biāo)志，若填入相應(yīng)出錯(cuò)處理程序的 編號(hào)，便轉(zhuǎn)相應(yīng)程序處理。 分析過(guò)程 LR分析器的動(dòng)作情況也可以描述成機(jī)器內(nèi)部的格 局間轉(zhuǎn)換，其格局用三元式表示為（狀態(tài)棧，已歸 約的符號(hào)棧，待繼續(xù)分析的輸入串） 6.1 LR分析器 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 i*i+i # E E+T E T T T*F T F F (E) F i 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 *i+i # E E+T E T T T*F T F F (E) F i 5 i 5 i 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 *i+i # E E+T E T T T*F T F F (E) F i 3 F 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 *i+i # E E+T E T T T*F T F F (E) F i 3 F 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 *i+i # E E+T E T T T*F T F F (E) F i 2 T 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 i+i # E E+T E T T T*F T F F (E) F i 2 T 7 * 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 +i # E E+T E T T T*F T F F (E) F i 2 T 5 i 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 +i # E E+T E T T T*F T F F (E) F i 2 T 7 * 5 i 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 +i # E E+T E T T T*F T F F (E) F i 2 T 7 * 10 F 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 +i # E E+T E T T T*F T F F (E) F i 10 F 7 * 2 T 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 19） 0 # 狀態(tài)、符號(hào)棧 +i# E E+T E T T T*F T F F (E) F i 2 T 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 30） 狀態(tài)棧 符號(hào)棧 輸入串 動(dòng)作 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分析法及分析程序自動(dòng)構(gòu)造（ 31） 4、 LR文法 定義：如果某一文法能夠構(gòu)造一張分析表， 使得表中每一元素至多只有一種明確動(dòng)作， 則該文法稱為 LR文法 注： 1）并非所有 CFG都是 LR文法，但對(duì)于多 數(shù)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，一般都可以用 LR文法 描述 2）和 LL(1)分析法相比， LR分析法適應(yīng) 的文法范圍要廣一些 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 32） 6.2 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造

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

27、4） 例如：根據(jù)下面的文法識(shí)別輸入串 abbcde 1) S aAcBe 2) A b 3) A Ab 4) B d 為每條產(chǎn)生式的尾部加上用 I表示的產(chǎn)生式序號(hào) 1) S aAcBe1 2) A b2 3) A Ab3 4) B d4 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 35） 用最右推導(dǎo)方式來(lái)識(shí)別，推導(dǎo)時(shí)把序號(hào)也帶上 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 若用最左歸約的方式進(jìn)行識(shí)別，則完全是上面的逆過(guò) 程 規(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分析法及分析程序自動(dòng)構(gòu)造（ 36） 1.活前綴 活前綴有兩種類型： 1）歸態(tài)活前綴 :活前綴的尾部正好是句柄之 尾，這時(shí)可以進(jìn)行歸約，歸約之后又成為另 一句型的活前綴 2）非歸態(tài)活前綴 :句柄尚未形成，需要繼續(xù) 移進(jìn)若干符號(hào)之后才能形成句柄 6.2 LR(0)項(xiàng)目 集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 37） 2.構(gòu)造自動(dòng)機(jī)識(shí)別活前綴 對(duì)于一個(gè)文法?？梢詷?gòu)造有限自動(dòng)機(jī)，它能識(shí)別 G 的所有活前綴 由于產(chǎn)生式右部的

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

30、注： （ 1）可以把圓點(diǎn)理解為棧內(nèi)外的分界線 （ 2）產(chǎn)生式右部符號(hào)串的長(zhǎng)度為 n，則可以分解 為 n+1個(gè)項(xiàng)目 （ 3）產(chǎn)生式 A e只有一個(gè)項(xiàng)目 A 6.2 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 39） 2.構(gòu)造自動(dòng)機(jī)識(shí)別活前綴 1）項(xiàng)目： 例如，產(chǎn)生式 A XYZ對(duì)應(yīng)四個(gè)項(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)行歸約，這 個(gè)項(xiàng)目就是歸約項(xiàng)目 6.2

31、 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 41） 2.構(gòu)造自動(dòng)機(jī)識(shí)別活前綴 2）由項(xiàng)目構(gòu)造 NFA的構(gòu)造方法 （ 1）將文法進(jìn)行拓廣，保證文法開始符號(hào) 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分析法及分析程序自動(dòng)構(gòu)造（ 40） 2.構(gòu)造自動(dòng)機(jī)識(shí)別活前綴 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分析法及分析程序自動(dòng)構(gòu)造（ 42） 2.構(gòu)造自動(dòng)機(jī)識(shí)別活前綴 2）由項(xiàng)目構(gòu)造 NFA的構(gòu)造方法 注： 1）構(gòu)造出的 NFA是包含有 e串的 NFA，可以使用子 集法使之確定化，使之成為一個(gè)以

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

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

37、A.I的任何項(xiàng)目都屬于 CLOSURE(I); B.若 A aBb屬于 CLOSURE(I),B是非終結(jié)符 ,那 么，對(duì)于任何關(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分析法及分析程序自動(dòng)構(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、 注：其含義是對(duì)于任意項(xiàng)目集 I,由于 I中有 A aXb項(xiàng)目， J中有 A aXb項(xiàng)目，表 示識(shí)別活前綴又移進(jìn)一個(gè)符號(hào) X 6.2 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 50） 3. LR(0)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 4)構(gòu)造 LR(0)項(xiàng)目集規(guī)范族的算法 過(guò)程如下： C=CLOSURE(S S) /*初態(tài)項(xiàng)目集 */ DO for (對(duì) C中每個(gè)項(xiàng)目集 I和 G中每個(gè)文法符號(hào) 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分析法及分析程序自動(dòng)構(gòu)造（ 51） 6.2 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 注： 1）此算法是迭代算法。置了 C的初態(tài)（初態(tài)僅 包含第一個(gè)項(xiàng)目集）后，每經(jīng)過(guò)一次 FOR語(yǔ)句。就 擴(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）由這個(gè)項(xiàng)目集規(guī)范族 C中各個(gè)狀態(tài)及狀態(tài)函數(shù) GO 可構(gòu)造一張識(shí)別活前綴的 DFA圖。 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 52） 例如：有一拓廣的文法 G6.1構(gòu)造識(shí)別活前綴的 NFA S E E aA|bB A cA|d B cB|d 解： 1、這個(gè)文法的項(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分析法及分析程序自動(dòng)構(gòu)造（ 45） 3. LR(0)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 2）定義和構(gòu)造項(xiàng)目集的閉包 設(shè) I是拓廣文法 G的一個(gè)項(xiàng)目集，定義和構(gòu)造 I的閉 包 CLOSURE(I) 構(gòu)造文法： A.I的任何項(xiàng)目都屬于 CLOSURE(I); B.若 A aBb屬于 CLOSURE(I),B是非終結(jié)符 ,那 么，對(duì)于任何關(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分析法及分析程序自動(dòng)構(gòu)造（ 49） 0

42、:S E E aA E bB 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(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分析法及分析程序 自動(dòng)構(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分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 46） 1、 構(gòu)造 LR(0)分析表 設(shè) C=I0

45、,I1 .In,以各項(xiàng)目集 Ik（ k=0, .n) 的 k作為狀態(tài) 符號(hào)，并以包含 S S的項(xiàng)目集作為初始狀態(tài)，同時(shí)將 G 文法的產(chǎn)生式進(jìn)行編號(hào)，然后按下列步驟填寫 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,則對(duì)任何終結(jié)符 a（包括語(yǔ)句結(jié) 束符 #），置 ACTIONk,a=rj;即根據(jù) j號(hào)產(chǎn)生式進(jìn)行 歸約。 6.2 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 二、 LR(0)分析表的構(gòu)造算法 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 47） 1、 構(gòu)造 LR(0)分析表 3）若項(xiàng)目 S S屬于 Ik，則置 ACTIONk,#=accept,簡(jiǎn)寫 acc； 4）若 GO(Ik,A)=Ij,A是非終結(jié)符，則置 GOTOk,A=j； 5）分析表中凡不能用

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

48、56） 例如：下面的文法是 LR(0)文法，但對(duì)這個(gè)文法的 各個(gè)產(chǎn)生式給予編號(hào)并寫成： 0.S E 1.E aA 2.E bB 3.A cA 4.A d 5.B cB 6.B d 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 47

49、） 例如：下面文法 G的 LR(0)項(xiàng)目集規(guī)范族中含有如下一個(gè)項(xiàng) 目集（狀態(tài)） I : I=X d bb /*移進(jìn)項(xiàng)目 */ A a /*歸約項(xiàng)目 */ B a /*歸約項(xiàng)目 */ 這三個(gè)項(xiàng)目告訴我們應(yīng)做的動(dòng)作各不相同，出現(xiàn)了移 進(jìn) 歸約沖突和歸約 歸約沖突。這個(gè)文法一定不是 LR(0)文法 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 59） 6.3 SLR分析表的構(gòu)造 SLR是的一種改進(jìn)，它在歸約時(shí)除了考慮歷史情況 之外還考慮了一點(diǎn)現(xiàn)實(shí)。 一、消除沖突 1、一個(gè)有沖突的項(xiàng)目集。可以根據(jù)讀頭下符號(hào)的 不同來(lái)消除沖突。 一般而言，對(duì)于任何形如 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)前讀頭下符號(hào) a來(lái)消除 沖突，即在構(gòu)造分析表的算法中做一些改變 第六章 LR分析法及分析程序自動(dòng)構(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)錯(cuò)。 二、構(gòu)造 SLR分析表的算法 設(shè) C=I0,I1, .In以各項(xiàng)目集 Ik(k=0, .n)作的 k為狀態(tài)序號(hào)，并以 S S包含的項(xiàng)目集作

51、為初始 狀態(tài)，同時(shí)將產(chǎn)生式進(jìn)行編號(hào)，然后按下列步驟填 寫 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。則對(duì)任何終結(jié)符 a Follow(A) ，置 ACTIONk,a=rj；其中 j為產(chǎn)生 式 A a的編號(hào)，即根據(jù) j號(hào)產(chǎn)生式 A a進(jìn)行歸 約 第六章 LR分析法及分析程序自動(dòng)構(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)， 均置上 “ 出錯(cuò)標(biāo)志 ” 。 注： 1）若文法按上面算法構(gòu)造出來(lái)的分析表不包含 多重定義項(xiàng)，則該文法 G是 SLR文法。 2）二義文法決不是 LR文法 3） SLR分析法包含的展望信息是體現(xiàn)在利用了 Follow(A)信息，可以解決 “ 歸約 歸約 ” 沖突。 4） SLR分析法沒有包含足夠的展望信息，不能完 全解決 “ 移進(jìn) 歸約 ” 沖突，需要改進(jìn)。 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 87） F * 6.3 SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 構(gòu)造 SLR分析表時(shí)要注意項(xiàng)目集族中 I1,I2,I9 三個(gè)項(xiàng)目集 ,其中含有沖突 : I1:S E I2:E T I9:E E+T E E+T T T*F T T*F 根據(jù)原來(lái)的文法分別求 S ,E的 Follow集 ,按 SLR方法進(jìn)行分析 ,得 第六章 LR分析法及分

55、析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 89） 例：一個(gè)非 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分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 69） 一 在構(gòu)造 SLR分析表的方法中 ,若項(xiàng)目集 Ik中含有 A a,那么在狀態(tài) K時(shí) ,只要面臨輸入符號(hào) aFOLLOW(A), 就確定采用 A a產(chǎn)生式進(jìn)行歸約 .但 是在某種情況下 ,當(dāng)狀態(tài) k呈現(xiàn)于棧頂時(shí) ,棧里的符號(hào) 串所構(gòu)成的活前綴 ba未必允許把 a規(guī)約成 A.因?yàn)榭赡?沒有一個(gè)規(guī)范句型含有前綴 bA.因此此時(shí)用 A a產(chǎn) 生式進(jìn)行歸約未必有效 . -我們可以從上例中看到這個(gè)問題 6.4 規(guī)范 LR分析表的構(gòu)造 對(duì) S

58、LR分析的思考 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(gòu)造（ 91） L 6.4 規(guī)范 LR分析表的構(gòu)造 結(jié)論 : 一由此看出 ,并非隨符都出現(xiàn)在規(guī)范句型中 . 對(duì)策 : 一給每個(gè) LR(0)項(xiàng)目添加展望信息 ,即添加句柄之后可 能跟的終結(jié)符 ,因?yàn)檫@些終結(jié)符確實(shí)

59、是規(guī)范句型中 跟在句炳之后的 .這就是 LR(1)的方法 . 可能引起的問題 一故 ,LR(1)項(xiàng)目是對(duì) LR(0)項(xiàng)目的分裂 ,若文法中終結(jié) 符的數(shù)目為 n,則每個(gè) LR(0)項(xiàng)目都可以分裂成 n個(gè) LR(1)項(xiàng)目 .這可能會(huì)引起分析表的膨脹 . 第六章 LR分析法及分析程序自動(dòng)構(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是文法的一個(gè)產(chǎn)生式， a是終結(jié)符，稱為搜索符。 1） LR(1)項(xiàng)目是對(duì) LR(0)項(xiàng)目的分裂，若文法中終結(jié) 符的數(shù)目為 n，則每個(gè) LR(0)項(xiàng)目可以分裂成 n個(gè)

60、LR(1)項(xiàng)目。 2）（ A ab,a)的含義：預(yù)期當(dāng)棧頂句柄 ab形成 后，在讀頭下讀到 a，此時(shí) a在棧內(nèi)， b還未入棧， 那它展望了句柄后的一個(gè)符號(hào)。 第六章 LR分析法及分析程序自動(dòng)構(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)對(duì)于活前綴 g是有效的， 如果 aFirst （ w),即使 aFollow(A), 項(xiàng)目（ A ab,a)也是無(wú)效的。 注： 1）規(guī)范 LR分析法僅考慮有效的 LR(1)項(xiàng)目，

61、在 LR(1)項(xiàng)目中有效的項(xiàng)目并不多。 2）對(duì)于多數(shù)程序設(shè)計(jì)語(yǔ)言，向前展望一個(gè)符 號(hào)就是足以決定歸約與否，所以只研究 LR(1). 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 97） 例：對(duì)非 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分析法及分析程序自動(dòng)構(gòu)造（ 98） 這兩個(gè)最右推導(dǎo)中已包含了活前綴為 ae的所 有

62、句型，可見 “ aAc”決不會(huì)是規(guī)范句型，即： 歸約成非終結(jié)符 “ A”之后。其后決不會(huì)跟 “ c”. 故：雖然 Follow(A)=c,d,但是（ A e,c) 對(duì)活前綴 ae是無(wú)效的，僅（ A e,d)是有 效的。 第六章 LR分析法及分析程序自動(dòng)構(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是 一個(gè)產(chǎn)生式，那么對(duì)于 FIRST(ba)中的每個(gè)終結(jié)符 b， 如果 (B g,b)原來(lái)不在 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分析法及分析程序自動(dòng)構(gòu)造（ 100） 6.4 規(guī)范 LR分析表的構(gòu)造 二、構(gòu)造 LR(1)的項(xiàng)目集規(guī)范族的算法 2、 GO函數(shù) 令 I是一個(gè)項(xiàng)目集， X是文法符號(hào)，函數(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時(shí)，搜索符并不改變。 第六章 LR分析法及分析程序自動(dòng)構(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中的每個(gè)項(xiàng)目集 I和 G的每個(gè)文法符號(hào) X IF GO(I,X)非空且不屬于 C 把 GO(I,X)加入 C中； WHILE C 依然擴(kuò)大； 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(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ù)，對(duì)該項(xiàng)目集內(nèi)得各項(xiàng)目求后繼項(xiàng)目集， 然后再對(duì)新求的項(xiàng)目集重復(fù)上面的過(guò)程，直到項(xiàng)目集不再 增加為止。 第六章 LR分析法及分析程序自動(dòng)構(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分析法及分析程序自動(dòng)構(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的編號(hào)，即根據(jù) j號(hào)產(chǎn)生式 A a進(jìn)行歸約 第六