編譯原理：第7章 自底向上語法分析-LR分析

1、第7章 自底向上語法分析- LR分析主要內(nèi)容 預(yù)備知識(shí):自底向上語法分析概述7.1 LR分析器概述7.2 LR(0)分析7.3 SLR(1)分析*7.4 LR(1)分析 1 LR(k)分析是指自左向右掃描和自底向上的語法分析。這里的“L”是指從左至右掃描輸入符號(hào)串，“R”是指構(gòu)造一個(gè)最右推導(dǎo)的逆過程，“k”是指為了作出分析決定而向前看的輸入符號(hào)的個(gè)數(shù)。 LR分析方法是當(dāng)前最廣義的無回溯的“移進(jìn)- 歸約”方法。根據(jù)棧中的符號(hào)串和向右順序查看輸入串的k(k0)個(gè)符號(hào)，就能唯一確定分析器的動(dòng)作是移進(jìn)還是歸約，以及用哪個(gè)產(chǎn)生式進(jìn)行歸約。 LR(k)分析技術(shù)是knuth于1965年首先提出來的。序2獲獎(jiǎng)

2、: 馮諾伊曼獎(jiǎng)（1995） 圖靈獎(jiǎng)（1974） 京都獎(jiǎng)（Kyoto Prize） (1996) 著名成就: 計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) TeX、 METAFONT KnuthMorrisPratt算法 Knuth-Bendix completion algorithm MMIX 3 1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技術(shù)。 LR(K)分析，只須根據(jù)分析棧中當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再向前查看K個(gè)輸入符號(hào)，就能確定相當(dāng)于某一產(chǎn)生式右部符號(hào)的句柄是否已在分析棧的頂部形成。從而也就可以確定所應(yīng)采取的分析動(dòng)作（是移進(jìn)輸入符號(hào)還是按某產(chǎn)生式進(jìn)行歸約）。當(dāng)前掃描到Xn

3、+1，向前查看k個(gè)符號(hào)，來確定是把Xn+1移進(jìn)棧，還是把XiXn作為句柄進(jìn)行歸約。1） 要?dú)w約時(shí)，則根據(jù)某產(chǎn)生式UXiXi+1Xn進(jìn)行歸約： #X1X2Xi-1UXn+1Xn+2Xn+k#例：#X1X2Xi Xn Xn+1Xn+2Xn+kXn+k+1#棧頂2） 要移進(jìn)時(shí)，即把Xn+1進(jìn)棧，并讀下一符號(hào)： #X1X2XiXnXn+1 Xn+2Xn+k# 在棧中當(dāng)前掃描符棧頂4優(yōu)點(diǎn)： 適用范圍廣；分析速度快；報(bào)錯(cuò)準(zhǔn)確。 構(gòu)造分析器的工作量很大，不大可能手工構(gòu)造。 軟件工具yacc Yet Another Compiler Compiler, Bell,1974.LR(0) 表示在每一步分析時(shí)都不用

4、向前看輸入符號(hào)LR(1) 表示在每一步分析時(shí)都向前看一個(gè)輸入符號(hào)來決定當(dāng)前的動(dòng)作。SLR(1) 表示簡(jiǎn)單的LR(1)。（僅在需要?dú)w約時(shí)向前看一個(gè)符號(hào)，以保證本次歸約是正確的）LALR（1）：也稱向前LR分析法，可在LR(1)分析法的 基礎(chǔ)上實(shí)現(xiàn)。該方法的分析能力介于SLR(1)和LR(1)之間。 5LR分析器也是PDA的特例 (帶有下推棧的FA)。 一個(gè)輸入、一個(gè)輸出、一個(gè)棧、一個(gè)驅(qū)動(dòng)程序和一張分析表。預(yù)備知識(shí):自底向上語法分析概述6預(yù)備知識(shí):自底向上語法分析概述 所謂自底向上分析方法就是從輸入串開始，逐步進(jìn)行歸約，直到歸約到文法的開始符號(hào)；或者說，從語法樹的末端開始，步步向上歸約，直到根結(jié)點(diǎn)

5、。 自底向上語法分析的實(shí)質(zhì)是一種移進(jìn)-歸約分析法，其基本思想是： 對(duì)輸入串從左向右掃描，并逐個(gè)移進(jìn)棧中。邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的可歸約串（它對(duì)應(yīng)某產(chǎn)生式右部），就用該產(chǎn)生式左部的非終極符代替它，完成了一步歸約。 重復(fù)這一過程直至歸約到棧中只剩右界符#和文法的開始符號(hào)為止，此時(shí)表示分析成功，否則報(bào)錯(cuò)。71.規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約 規(guī)范推導(dǎo)就是最右推導(dǎo)，而通過規(guī)范推導(dǎo)能得到的句型就是規(guī)范句型(右句型)。注意，并非所有句型都是規(guī)范句型。 (思考：CFG中，每個(gè)句子、句型是否都有規(guī)范推導(dǎo)？) 規(guī)范歸約也稱為最左歸約，是規(guī)范推導(dǎo)的逆過程，即在分析的每一步，將當(dāng)前句型的句柄（LR分

6、析法中的可歸約串）歸約成相應(yīng)的非終結(jié)符號(hào)。 預(yù)備知識(shí):自底向上語法分析概述8 2.自底向上分析方法的一般過程及特征 自底向上分析方法，也可稱為移進(jìn)歸約法。LR分析是一種規(guī)范歸約（確定的自底向上分析），它的一般過程是： 對(duì)輸入串從左向右掃描，并逐個(gè)移進(jìn)棧中，當(dāng)棧頂符號(hào)串形成一個(gè)句柄(即為某條規(guī)則的右部)時(shí)，就進(jìn)行一次歸約，即把棧頂構(gòu)成句柄的那個(gè)符號(hào)串用相應(yīng)規(guī)則左部的非終結(jié)符號(hào)來代替。 接著再檢查棧頂是否又出現(xiàn)了新的句柄，若出現(xiàn)新的句柄，就再進(jìn)行歸約；若沒有形成新的句柄，則再?gòu)妮斎敕?hào)串移進(jìn)新的符號(hào)，如此繼續(xù)直到整個(gè)輸入符號(hào)串處理完畢。 最終如果棧里只有文法開始符號(hào)，則所分析的輸入符號(hào)串為合法的句

7、子，報(bào)告成功；否則，輸入串是不合法的符號(hào)串，報(bào)告錯(cuò)誤。預(yù)備知識(shí):自底向上語法分析概述9自底向上分析的關(guān)鍵：如何精確定義可歸約串并識(shí)別對(duì)可歸約串(p23)的不同定義形成不同的自下而上分析方法：1.在規(guī)范歸約分析法中，是用句柄來刻畫可歸約串(LR, 簡(jiǎn)單優(yōu)先分析)2.在算符優(yōu)先分析法中，是用最左素短語來刻畫可歸約串根據(jù)識(shí)別可歸約串的不同方法，也形成不同的自下而上分析法。簡(jiǎn)單優(yōu)先分析法和LR分析法都是規(guī)范歸約分析法（句柄可歸約串），但它們識(shí)別句柄的方法不同：1.LR分析法是根據(jù)歷史、現(xiàn)實(shí)、展望三者信息來確定棧頂符號(hào)串是否形成句柄2.簡(jiǎn)單優(yōu)先分析法是根據(jù)文法符號(hào)之間的優(yōu)先關(guān)系來確定句柄。10 預(yù)備知識(shí)

8、:自底向上語法分析概述例 有文法GS： (1) SaAcBe (2) Ab (3) AAb (4) Bd試分析符號(hào)串a(chǎn)bbcde是否為該文法的句子。 解：從文法的開始符號(hào)進(jìn)行規(guī)范推導(dǎo)，依次使用1、4、3、2規(guī)則.S =aAcBe =aAcde =aAbcde=abbcde 1 4 3 2從符號(hào)串開始，向上歸約，如果最終能夠規(guī)約到文法的開始符號(hào)S，則可以說明該輸入符號(hào)串是這個(gè)文法的句子。其歸約過程如圖所示。 SeBcAaA bdb(a) b歸約為ASeBcAaA bd(b)Ab歸約為ASeBcAad(c)d歸約為BSeBcAa(d) aAcBe歸約為SS(e)11步驟 符號(hào)棧 輸入符號(hào)串 動(dòng)作

9、123456789101112 #a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#S abbcde#bbcde#bcde#bcde#cde#cde#de#e#e# 開始狀態(tài)進(jìn)棧進(jìn)棧用Ab歸約進(jìn)棧用AAb歸約進(jìn)棧進(jìn)棧用Bd歸約進(jìn)棧用SaAcBe歸約接受 輸入串 abbcde的分析過程 通過上述分析可看出，每次歸約的句柄都出現(xiàn)在符號(hào)棧的棧頂，不會(huì)出現(xiàn)在棧的中間，因?yàn)槲覀兊乃惴ㄊ亲宰笙蛴覓呙栎斎敕?hào)串，進(jìn)行的是最左歸約。 12步驟 符號(hào)棧 輸入符號(hào)串 動(dòng)作 123456789101112 #a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#S abb

10、cde#bbcde#bcde#bcde#cde#cde#de#e#e# 開始狀態(tài)進(jìn)棧進(jìn)棧用Ab歸約進(jìn)棧用AAb歸約進(jìn)棧進(jìn)棧用Bd歸約進(jìn)棧用SaAcBe歸約接受 輸入串 abbcde的分析過程 從自底向上分析的一般過程可看出:如何尋找或確定一個(gè)句型的可歸約串，是構(gòu)造一個(gè)自左向右掃描、自底向上分析方法必須要解決的一個(gè)關(guān)鍵問題。最常用的自底向上的分析方法有算符優(yōu)先方法和LR分析方法，算符優(yōu)先方法僅適用于算符文法，而LR分析方法應(yīng)用比較普遍。本章重點(diǎn)介紹LR分析方法。 在LR分析中， 我們把右句型中的可歸約串稱為該句型的句柄。13預(yù)備知識(shí)：自底向上語法分析概述3.句柄的概念 設(shè)是文法G的一個(gè)句型，S是

11、文法G的開始符號(hào)。如果有S* A , 且 A+ ，則稱是句型關(guān)于非終極符 A 的短語。 特別地，如果有A ，則稱是句型關(guān)于非終極符A（或A）的直接短語。 一個(gè)句型的最左直接短語稱為該句型的句柄。 非二義性的文法，它的每個(gè)右句型有唯一的句柄。 14 一棵分析樹中一個(gè)特有的結(jié)點(diǎn)連同它的全部后裔，連接這些后裔的邊以及這些結(jié)點(diǎn)的標(biāo)記。SAbSaSbaAaa 子樹 梯形中為一棵子樹。短語：一棵子樹的所有葉子自左至右排列起來15短語：一棵子樹的所有葉子自左至右排列起來形成 一個(gè)相對(duì)于子樹根的短語。直接短語：僅有父子兩代的一棵子樹，它的所有葉 子自左至右排列起來所形成的符號(hào)串。句柄：一個(gè)句型的分析樹中最左最

12、下那棵只有父子 兩代的子樹的所有葉子的自左至右排列。 用子樹解釋短語，直接短語，句柄:16例 ，有文法GS： (1) SaAcBe (2) Ab (3) AAb (4) Bd找出句型abbcde的所有短語，并指出直接短語和句柄。SeBcAaA bdbabbcde的短語： b，bb，d，abbcde abbcde的直接短語： b，dabbcde的句柄： b17例 ，有文法GS： (1) SaAcBe (2) Ab (3) AAb (4) Bd試分析符號(hào)串a(chǎn)bbcde是否為該文法的句子。 SeBcAaA bdb(a) b歸約為ASeBcAaA bd(b)Ab歸約為ASeBcAad(c)d歸約為BS

13、eBcAa(d) aAcBe歸約為SS(e)句型abbcde的歸約過程：18句型 E+E*i的句柄： i EE+EE*Ei 求句型 E+E*i 的短語、直接短語和句柄。句型 E+E*i 的短語: i, E*i, E+E*i句型 E+E*i的直接短語 :i19預(yù)備知識(shí)：自底向上語法分析概述4. LR分析法 LR分析法適用的范圍大，對(duì)文法的要求低，無須消除左遞歸，也無須消除左公共因子。除二義性文法外，絕大多數(shù)上下文無關(guān)文法描述的程序設(shè)計(jì)語言都可用LR語法分析器予以識(shí)別。目前大多數(shù)編譯程序的語法分析器都采用這種分析方法. LR（k）的含義L：從左(L)向右掃描輸入串。R：自下而上地建立該輸入串的最右

14、(R)推導(dǎo)(規(guī)范推導(dǎo)) 。k：在決定分析動(dòng)作時(shí)，向前看的符號(hào)個(gè)數(shù)。 在分析的每一步，只須根據(jù)分析棧已移進(jìn)和歸約出的全部文法符號(hào)，并至多向前看k個(gè)輸入符號(hào)，即能確立相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已形成，從而確定當(dāng)前的動(dòng)作是移進(jìn)，還是歸約。LR(k)文法是非歧義文法中能夠進(jìn)行確定的自底向上分析的最大文法類207.1 LR分析器概述LR分析器組成：(1)總控程序：適用于所有LR分析器(2)分析表 動(dòng)作表 f(S,a):狀態(tài)S遇到輸入符號(hào)a的動(dòng)作 狀態(tài)轉(zhuǎn)換表 g(S,X):狀態(tài)S遇到XVN, 應(yīng)進(jìn) 入的下一狀態(tài)(3)分析棧 文法符號(hào)棧 Xi 狀態(tài)棧 Si工作原理：任一時(shí)刻， 棧頂狀態(tài)Sm 當(dāng)前輸入

15、符號(hào)a 決定其下一步動(dòng)作 f(Sm, a)21LR分析器的邏輯結(jié)構(gòu) 輸入符號(hào)串 一個(gè)分析棧 一個(gè)有窮的控制系統(tǒng)（分析表和總控程序）a1a2an有窮的控制系統(tǒng)： 分析表(動(dòng)作表、轉(zhuǎn)換狀態(tài)表) 總控程序 SmXmS1X1S0#狀態(tài)棧符號(hào)棧分析棧輸出歸約的規(guī)則序列或語法樹7.1 LR分析器概述22 7.1 LR分析器概述 1.LR分析器的邏輯結(jié)構(gòu) a1a2an有窮的控制系統(tǒng)： 分析表(動(dòng)作表、轉(zhuǎn)換狀態(tài)表) 總控程序 SmXmS1X1S0#狀態(tài)棧符號(hào)棧分析棧輸出歸約的規(guī)則序列或語法樹其中，輸入符號(hào)串就是等待分析的符號(hào)串。分析棧有兩部分：一個(gè)是符號(hào)棧，另一個(gè)是狀態(tài)棧。控制系統(tǒng)包括一個(gè)分析表和一個(gè)總控程序

16、。對(duì)于不同的文法來說，分析表各有不同，但總控程序都是一樣的。LR分析器的工作過程就是在總控程序的控制下，從左到右掃描輸入符號(hào)串，根據(jù)分析棧中的符號(hào)和狀態(tài)以及當(dāng)前的輸入符號(hào)，查閱分析表并按分析表的指示完成相應(yīng)的分析動(dòng)作，直到符號(hào)棧中出現(xiàn)開始符號(hào)。 23文法符號(hào)棧Xi存儲(chǔ)的是移進(jìn)或歸約的文法符號(hào)，可以是終極符或非終極符。 狀態(tài)棧Si 存儲(chǔ)的是以狀態(tài)號(hào)表示的狀態(tài)。SmXmS1X1S0#狀態(tài)棧符號(hào)棧分析棧2. 分析棧的構(gòu)成243. LR狀態(tài)棧的狀態(tài) 在分析的每一步，將文法符號(hào)棧中存放的全部文法符號(hào)用狀態(tài)來刻畫，顯示了從分析開始到目前為止的整個(gè)歷程。初始時(shí)刻，狀態(tài)棧為S0，表示符號(hào)棧只有#。當(dāng)狀態(tài)棧的內(nèi)

17、部為S0S1Sm時(shí)，則棧頂狀態(tài)Sm刻畫了符號(hào)棧中從開始到目前為止已有的文法符號(hào)為 #X1Xm 若輸入符號(hào)串被完全分析成功，則符號(hào)棧為#S（S為文法的開始符號(hào)），狀態(tài)棧為S0Si，其中Si 為棧頂狀態(tài)，ACTION(Si , #)=acc。254. LR分析表的構(gòu)成 LR分析表是LR分析器的核心部分，它由兩部分組成，一是動(dòng)作部分ACTION表，二是狀態(tài)轉(zhuǎn)換部分GOTO表。表中S1、S2、Sm為分析器的各個(gè)狀態(tài)；a1、a2、an為文法的全部終結(jié)符號(hào)及右界符#；A1、A2、Ak為文法的非終結(jié)符號(hào)。 狀態(tài) 動(dòng)作表ACTION 狀態(tài)轉(zhuǎn)換表GOTO a1a2#A1A2AkS1S2.Sm在分析表的動(dòng)作部分:

18、 ACTIONSi，aj表示當(dāng)分析狀態(tài)棧的棧頂為Si，輸入符號(hào)為aj時(shí)應(yīng)執(zhí)行的動(dòng)作；而在分析表的狀態(tài)轉(zhuǎn)換部分: GOTOSi，Aj表示當(dāng)前狀態(tài)Si下而符號(hào)棧頂為非終結(jié)符號(hào)Aj后應(yīng)移入狀態(tài)棧的下一狀態(tài)。 26LR分析器工作原理分析表的動(dòng)作有下列四種： 1. 移進(jìn) f(Sm, a)=Si 把a(bǔ)移入符號(hào)棧頂 把狀態(tài)i壓入狀態(tài)棧頂2. 歸約 f(Sm, a)=ri 從狀態(tài)棧和符號(hào)棧各彈出n個(gè) 用G的第i條規(guī)則 符號(hào)，即Sm-n為棧頂狀態(tài) A歸約 將A移入文法符號(hào)棧， | |=n Si=g (Sm-n , A)壓入狀態(tài)棧頂 輸出用于歸約的規(guī)則或其編號(hào)， 不讀下一輸入符號(hào) 27分析表的動(dòng)作有下列四種：3.

19、接受 f(Sm, #)=acc當(dāng)輸入符號(hào)串到達(dá)右界符#時(shí)，且符號(hào)棧只有#S,S為文法的開始符號(hào)。則分析成功結(jié)束，接受輸入符號(hào)串并結(jié)束分析。結(jié)果：輸出帶上給出了右分析序列（最右推導(dǎo)所用規(guī)則的逆序列）4.報(bào)錯(cuò) f(Sm, a)=err在狀態(tài)棧的棧頂狀態(tài)為Sm時(shí)，如果輸入符號(hào)為不應(yīng)該遇到的符號(hào)時(shí)，即ACTION Sm，a=空白，則報(bào)錯(cuò)，說明輸入符號(hào)串有語法錯(cuò)誤28LR分析器的關(guān)鍵就是構(gòu)造分析表。下表給出了文法G： 1) SS(S) 2) S的分析表。 狀態(tài) ACTION GOTO () # S0R2R2R211S2ACC2R2R2R233S2S44R1R1R1利用給定的分析表, 給出符號(hào)串 ( )

20、的分析過程。29輸入串()#的分析過程步驟 狀態(tài)棧 符號(hào)棧 輸入串 f g 0 0 # ()# r2 1 1 01 #S ()# S2 2 012 #S( ()# r2 3 3 0123 #S(S ()# S2 4 01232 #S(S( )# r2 3 5 012323 #S(S(S )# S4 6 0123234 #S(S(S) )# r1 3 7 0123 #S(S )# s4 1 8 01234 #S(S) # r1 1 9 01 #S # acc 30步驟 狀態(tài)棧 符號(hào)棧 輸入符號(hào)串 ACTION GOTO 10#()#R21201#S()#S23012#S()#R2340123#S

21、(S()#S2501232#S(S()#R23678910012323012323401230123401#S(S(S#S(S(S)#S(S#S(S)#S)#)#)#S4R1S4R1ACC31符號(hào)串 ()的分析過程 fg( ) #S0r2 r2 r211s2 err accerr2r2 r2 r233s2 s4 errerr4r1 r1 r1err (1) SS(S) ( 2) S31例題討論GS： SS(S) S對(duì)串()#進(jìn)行規(guī)約（依據(jù)LR分析表）LR分析器：通過把讀過的符號(hào)壓入棧中，開始運(yùn)行（1）符號(hào)棧頂出現(xiàn)句柄，用相應(yīng)規(guī)則A 歸約，即用A代替（2）繼續(xù)把輸入符號(hào)壓入棧頂，直到棧頂出現(xiàn)句柄

22、時(shí)，再歸約。反復(fù)進(jìn)行，直到出現(xiàn)錯(cuò)誤，或最終歸約為S。32構(gòu)造LR分析表。下表給出了文法G： 1) A(A) 2) Aa的分析表。 狀態(tài) ACTION GOTO () a# A0S2S311ACC2S2S343R2R2R2R24S55R1R1R1R1利用給定的分析表, 給出符號(hào)串 (a) 的分析過程。33步驟 狀態(tài)棧 符號(hào)棧 輸入符號(hào)串 ACTION GOTO 說明 10#(a)#S2開始時(shí)，0入狀態(tài)棧，#入符號(hào)棧. S2代表2入狀態(tài)棧，(入符號(hào)棧。 202#(a)#S3S3代表3入狀態(tài)棧，a入符號(hào)棧。 3023#(a)#R24R2，用Aa 歸約，a 出符號(hào)棧、A入符號(hào)棧，3出狀態(tài)棧、2為棧頂，

23、查GOTO表,4入狀態(tài)棧。 4024#(A)#S5S5代表5入狀態(tài)棧，)入符號(hào)棧。 50245#(A)#R11R1，用A(A) 歸約，(A)出符號(hào)棧、A入符號(hào)棧，245出狀態(tài)棧、0為棧頂，查GOTO表,1入狀態(tài)棧。 601#A#ACCEPT輸入符號(hào)為#，查動(dòng)作表為ACCEPT，接受。 符號(hào)串 (a)的分析過程 34文法G： 1) A(A) 2) Aa狀態(tài) ACTION GOTO () a# A0S2S311ACC2S2S343R2R2R2R24S55R1R1R1R1步驟 狀態(tài)棧 符號(hào)棧 輸入符號(hào)串 ACTION GOTO 說明 10#(a)#S2移進(jìn)202#(a)#S3移進(jìn)3023#(a)#R

24、24用Aa 歸約4024#(A)#S5移進(jìn)50245#(A)#R11用A(A) 歸約601#A#ACC接受。 LR分析過程355. LR分析器總控程序 輸入：LR分析表、分析棧、輸入串輸出：若輸入串是合法的，輸出最右推導(dǎo)所用規(guī)則的逆序列，否則報(bào)錯(cuò)。初始化；/分析棧只有狀態(tài)棧S，其棧頂狀態(tài)為S0； /分析表已建立； / Pa指向輸入串的第一個(gè)符號(hào),輸入符號(hào)用a代表。while ( ACTIONSi,a!=acc) / a是Pa指向的符號(hào)，Si是分析棧的棧頂狀態(tài)if (ACTION Si,a=error) error;else if (ACTION Si,a=Sk) /移進(jìn) 狀態(tài)k壓入狀態(tài)棧； 推

25、進(jìn)Pa指向下一個(gè)輸入符號(hào)；else if (ACTION Si,a= ri)/用第i個(gè)規(guī)則A 規(guī)約,|=n從分析棧彈出=n個(gè)狀態(tài)；/新棧頂狀態(tài)為Si-nGOTO Si-n,A壓入棧； / GOTO Si-n, A是下一個(gè)新狀態(tài)輸出產(chǎn)生式 A； 367.2 LR（0）分析法 LR(0)分析器是LR分析方法中最簡(jiǎn)單的一種，在確定分析動(dòng)作時(shí)，不需要向前查看任何符號(hào)。 只有很少的文法可以構(gòu)造出無二義性的LR(0)分析表，LR(0)分析法是SLR(1)分析法和LR(1)分析法的基礎(chǔ)。 為了進(jìn)行LR(0)分析，首先需要對(duì)文法進(jìn)行拓廣，目的是使文法只有一個(gè)以開始符號(hào)作為左部的產(chǎn)生式，從而使構(gòu)造出來的分析器有

26、唯一的接受狀態(tài)。拓廣后的文法稱為拓廣文法.37一 活前綴、拓廣文法、LR（0）項(xiàng)目 1拓廣文法 拓廣文法是在原文法的基礎(chǔ)上，引入新的開始符號(hào)S及規(guī)則 SS（S為原文法開始符號(hào)），使得S為單一規(guī)則的左部。 例,對(duì)下列文法G進(jìn)行拓廣 ET|E+T|ET Ti|(E)解：引入一個(gè)新的開始符號(hào)E ，使得文法的開始符號(hào)所在的規(guī)則唯一，這樣得到拓廣文法如下： EE ET|E+T|ET Ti|(E) 7.2 LR（0）分析法38一 活前綴、拓廣文法、LR（0）項(xiàng)目 2活前綴 對(duì)于一個(gè)規(guī)范句型來說，其活前綴定義如下： 設(shè)是一個(gè)規(guī)范句型，其中表示句柄， Vt*，如果 =u1u2uk，那么稱符號(hào)串u1u2ui(其

27、中1ik)是句型的活前綴。 u1u2uk稱為可歸約活前綴。 在LR分析過程中，如果輸入符號(hào)串沒有語法錯(cuò)誤，則在分析的每一步:壓入符號(hào)棧中的符號(hào)串一定是某一規(guī)范句型的活前綴;并與剩余的輸入符號(hào)串(未讀部分)一起構(gòu)成所給文法的一個(gè)規(guī)范句型。 當(dāng)符號(hào)棧頂形成句柄，即符號(hào)棧的內(nèi)容為可歸約活前綴時(shí)，句柄就會(huì)立即被歸約。所以說，LR分析就是逐步在符號(hào)棧中產(chǎn)生可歸前綴，再進(jìn)行歸約的過程。 活前綴不能包含句柄右邊的符號(hào)。7.2 LR（0）分析法39 例，有文法GET|E+T|E-T，Ti|(E)，找規(guī)范句型 E+(i-i)的活前綴和可歸前綴。解：首先畫出E+(i-i)的語法樹如圖所示， =E+(i-i)可找出

28、第一個(gè)i是句柄， =E+(i =-i)因此活前綴為： 、E、E+、E+(、E+(i 其中：E+(i是可歸前綴。 ET+E）E（T-ETii一 活前綴、拓廣文法、LR（0）項(xiàng)目40414243LR分析法的引入44 3活前綴與句柄的關(guān)系(3種) 活前綴含有句柄的全部符號(hào) 對(duì)形如A的產(chǎn)生式，右部已全部出現(xiàn)在棧頂，說明已識(shí)別出的全部（用A 表示）。分析動(dòng)作應(yīng)是歸約?；钋熬Y只含有部分句柄的符號(hào)。對(duì)形如A12的產(chǎn)生式，其右部子串1已出現(xiàn)在棧頂，說明1已被識(shí)別出，期待著從余留輸入串看到句柄的其余部分（用A1 2 表示）。分析動(dòng)作應(yīng)是移進(jìn)。 活前綴不含句柄的任何符號(hào)。對(duì)形如A的產(chǎn)生式，期望著從余留符號(hào)串看到可

29、歸約到A的符號(hào)串（用A 表示）。分析動(dòng)作應(yīng)是移進(jìn)。一 活前綴、拓廣文法、LR（0）項(xiàng)目45一 活前綴、拓廣文法、LR（0）項(xiàng)目 一個(gè)LR分析器的工作過程，實(shí)質(zhì)上是一個(gè)逐步產(chǎn)生（或識(shí)別）所給文法的規(guī)范句型的活前綴的過程。 活前綴的識(shí)別是通過構(gòu)造關(guān)于LR（0）項(xiàng)目的DFA來實(shí)現(xiàn)，該DFA最終用于構(gòu)造相應(yīng)的LR分析表。46 一 活前綴、拓廣文法、LR（0）項(xiàng)目 4LR(0)項(xiàng)目 在文法G中每個(gè)產(chǎn)生式右部適當(dāng)位置添加一個(gè)圓點(diǎn)，用來刻畫產(chǎn)生式右部符號(hào)串已有多大一部分被識(shí)別(被看到）。 對(duì)某個(gè)文法G來說，如果A12為G的一條規(guī)則，那么，對(duì)規(guī)則的右部加上一個(gè)圓點(diǎn)，就成為一個(gè)項(xiàng)目。其形式為：A12 圓點(diǎn)是表示

30、項(xiàng)目的一種標(biāo)記，也就是說，如果一條規(guī)則的右部標(biāo)有圓點(diǎn)，那么它就是項(xiàng)目。一般情況下，因?yàn)閳A點(diǎn)的位置不同。一條規(guī)則可以有幾個(gè)項(xiàng)目。47一 活前綴、拓廣文法、LR（0）項(xiàng)目 例：已知文法GA：A(A)|a，求LR（0）項(xiàng)目。解： 增廣文法： (拓廣文法)（0） AA（1） A(A)（2） AaLR（0）項(xiàng)目： A A AA A(A) A(A) A(A) A(A) Aa Aa 48一 活前綴、拓廣文法、LR（0）項(xiàng)目 5LR(0)項(xiàng)目類型 移進(jìn)項(xiàng)目 (不完全項(xiàng)目) Ab b VT歸約項(xiàng)目 (完全項(xiàng)目)A ( VNVT)*待歸約項(xiàng)目AB B VN該項(xiàng)目意味著，首先要將B的產(chǎn)生式右部(讀入)歸約為B，才能

31、將A的右部繼續(xù)分析下去。接受項(xiàng)目 (開始符號(hào)的歸約項(xiàng)目) SS 49二 識(shí)別活前綴的有窮自動(dòng)機(jī) 在LR實(shí)際分析過程中，并不直接分析符號(hào)棧中的符號(hào)是否形成句柄，我們可以把文法中的符號(hào)都看成是有窮自動(dòng)機(jī)的輸入符號(hào)，每當(dāng)一個(gè)符號(hào)進(jìn)棧時(shí)表示已經(jīng)識(shí)別了該符號(hào)，并進(jìn)行狀態(tài)轉(zhuǎn)換；當(dāng)識(shí)別出可歸前綴時(shí)，相當(dāng)于在棧中形成句柄，則認(rèn)為到達(dá)了識(shí)別句柄的狀態(tài)。根據(jù)活前綴與LR(0)項(xiàng)目的對(duì)應(yīng)關(guān)系，把LR(0)項(xiàng)目作為有窮自動(dòng)機(jī)的狀態(tài)，就能得到識(shí)別活前綴的有窮自動(dòng)機(jī)。 50為了構(gòu)造LR(0)分析表，首先從原理上給出其構(gòu)造的方法。 1其本思想首先構(gòu)造LR（0）項(xiàng)目的NFA，由NFA構(gòu)造DFA，由DFA轉(zhuǎn)化為L(zhǎng)R（0）分析表

32、。其中LR（0）項(xiàng)目作為NFA的狀態(tài)，用來保持有關(guān)移進(jìn)-歸約過程的信息。二 識(shí)別活前綴的有窮自動(dòng)機(jī) 51二 識(shí)別活前綴的有窮自動(dòng)機(jī) 2LR（0）項(xiàng)目的NFA轉(zhuǎn)換規(guī)則 xVT時(shí)，轉(zhuǎn)換規(guī)則AxAxx代表移進(jìn)動(dòng)作 xVN時(shí)，轉(zhuǎn)換規(guī)則Axx.xx.Ax該規(guī)則表明，只有從剩余符號(hào)串中看到了可從x推出的全部符號(hào)，狀態(tài)A.x才可經(jīng)x弧進(jìn)入狀態(tài)Ax.。 52二 識(shí)別活前綴的有窮自動(dòng)機(jī) 2LR（0）項(xiàng)目的NFA轉(zhuǎn)換規(guī)則 NFA的開始狀態(tài)和接受態(tài)S.SS S.開始狀態(tài)接受狀態(tài)任何形如A 項(xiàng)目稱為句柄識(shí)別態(tài)。 NFA的任何狀態(tài)又稱為活前綴識(shí)別態(tài)。53 例 GS: SS(S) | 其拓廣文法為：0. SS 1. SS

33、(S) 2. SLR(0)項(xiàng)目有： S.S SS. S.S(S) SS.(S) SS(.S) SS(S.) S(S(S). S. 用這些項(xiàng)目作為狀態(tài)，構(gòu)造NFA如下：S13S485672S)S()確定化 DFA MS()0 1382,41 245382 5384,63 4653874 7DFA的每一個(gè)狀態(tài)包含了若干項(xiàng)目，即項(xiàng)目集。54直接構(gòu)造識(shí)別活前綴的DFA（詳見7.2.3）把拓廣文法的第一個(gè)項(xiàng)目S.S作為初始狀態(tài)集的核，通過求核的閉包和轉(zhuǎn)換函數(shù)，求出LR(0)項(xiàng)目集規(guī)范族，直接構(gòu)造識(shí)別活前綴的DFAI0 = closure (S.S) = S.S, S.S(S),

34、 S.I1 = GOTO(I0, S) = SS., SS.(S)I2 = GOTO(I1, () = SS(.S), S.S(S), S.I3 = GOTO(I2, S) = SS（S.）， SS .(S)I4= GOTO(I3, ）) = SS（S）.I0: S.SS.S(S) S.I1: SS. SS .(S) I2: SS(. S) S.S(S) S.I3: SS（S.） SS .(S) I4:SS(S). S()DFA:S55 二 識(shí)別活前綴的有窮自動(dòng)機(jī) 例： 構(gòu)造A(A)|a 的LR(0)項(xiàng)目的NFA和DFAA.AAA.A.(A) A.aAAa .aA (.A)A (A.)A (A

35、).(A)狀態(tài)項(xiàng)目集a ( )A0A.A A.aA.(A)Aa.A(.A) A.aA.(A)AA.1AA.2Aa.3A(.A) A.aA.(A)Aa.A(.A) A.aA.(A)A(A.)4A(A.)A(A).5A(A).A.A AA.A.aAa.A.(A）A(.A）A(A.)A(A).56 二 識(shí)別活前綴的有窮自動(dòng)機(jī) 例： 構(gòu)造A(A)|a 的LR(0)項(xiàng)目的NFA和DFA狀態(tài)項(xiàng)目集a ( )A0A.A A.aA.(A)Aa.A(.A) A.aA.(A)AA.1AA.2Aa.3A(.A) A.aA.(A)Aa.A(.A) A.aA.(A)A(A.)4A(A.)A(A).5A(A).A.A A

36、.aA.(A)A(.A) A.(A) A.aAA.Aa.A(A.)A(A).Aaa(A)57下面針對(duì)輸入串（a），說明LR分析法是如何根據(jù)識(shí)別活前綴的DFA進(jìn)行工作的。為了便于理解其工作過程，DFA 如圖所示：從初態(tài)0出發(fā)，讀入“（”進(jìn)入狀態(tài)3。在狀態(tài)3讀入“（”進(jìn)入狀態(tài)3。在狀態(tài)3讀入a進(jìn)入狀態(tài)2。活前綴分別是（、（、（a 。因狀態(tài)2中的項(xiàng)目Aa.是一個(gè)歸約項(xiàng)目，說明活前綴“（a”中句柄已形成，此時(shí)應(yīng)將句柄“a”按Aa歸約為A，并按Aa的右部符號(hào)串a(chǎn)標(biāo)記的路徑退回到狀態(tài)3。由于已經(jīng)看到從A推出的全部符號(hào)，從狀態(tài)3 經(jīng)A弧進(jìn)入狀態(tài)4。由于狀態(tài)4是一個(gè)移進(jìn)狀態(tài)，表明活前綴“（A”中句柄尚未形成，

37、移進(jìn)“）”進(jìn)入狀態(tài)5。狀態(tài)5是句柄接受態(tài)，應(yīng)將活前綴“（A）”中的句柄“（A）”歸約為A，并按A（A）的右部符號(hào)串標(biāo)記的路徑回到狀態(tài)3。由于已經(jīng)看到了從A推出的全部符號(hào)，從狀態(tài)3經(jīng)A弧進(jìn)入狀態(tài)4。在狀態(tài)4，經(jīng)移進(jìn)“）”，進(jìn)入狀態(tài)5。此時(shí)活前綴“（A）”中已形成句柄，按A（A）歸約為A，并按A（A）的右部符號(hào)串標(biāo)記的路徑退回到0態(tài)。由于在0態(tài)已經(jīng)看到從A推出的全部符號(hào)，經(jīng)A弧進(jìn)入狀態(tài)1。在狀態(tài)1中，句柄已形成，按AA歸約，說明句子（a）已成功歸約為A。 A.A A.aA.(A)A(.A) A.(A) A.aAA.Aa.A(A.)A(A).Aaa(A)A(.A) A.(A) A.aA0：1：2：3

38、：3：45aA (A) | a二 識(shí)別活前綴的有窮自動(dòng)機(jī) 58識(shí)別活前綴的有窮自動(dòng)機(jī)構(gòu)造LR（0）項(xiàng)目集規(guī)范族構(gòu)造DFA (直接法) 從實(shí)用角度出發(fā)，本節(jié)給出了構(gòu)造LR（O）分析表的另一種方法。即利用LR（O）項(xiàng)目集規(guī)范族直接得到DFA。DFA的每一個(gè)狀態(tài)是由若干LR（O）項(xiàng)目所組成的集合（稱為L(zhǎng)R（O）項(xiàng)目集）。定義：識(shí)別一個(gè)文法活前綴的DFA的狀態(tài)的全體，構(gòu)成該文法的LR（O）項(xiàng)目集規(guī)范族。59為了求出LR（O）項(xiàng)目集規(guī)范族，定義如下兩個(gè)函數(shù)： (1) 項(xiàng)目集I的閉包函數(shù)Closure(I)設(shè)I是增廣文法的任一項(xiàng)目集，項(xiàng)目集I的閉包按如下規(guī)則求得：I中任何項(xiàng)目Closure（I）若A.BC

39、losure（I），BVN 則任意的 B.Closure（I）重復(fù)步驟，直到Closure（I）不再增長(zhǎng)。 （2）狀態(tài)轉(zhuǎn)換函數(shù)GO（I，X）GO（I，X）=Closure（J），X(VNVT)，其中GO（I，X）表示當(dāng)前狀態(tài)I，經(jīng)過X的后繼狀態(tài)。J為形如A.X的項(xiàng)目的后繼項(xiàng)目所組成的集合： J=AX.|A.XIGO函數(shù)把這些項(xiàng)目集連接成一個(gè)DFA。識(shí)別活前綴的有窮自動(dòng)機(jī)構(gòu)造LR（0）項(xiàng)目集規(guī)范族構(gòu)造DFA 60 LR（0）項(xiàng)目集規(guī)范族的構(gòu)造借助上述兩個(gè)函數(shù)，可構(gòu)造出增廣文法G的項(xiàng)目集規(guī)范族：把G的第一個(gè)項(xiàng)目S.S作為初態(tài)I0的核，通過求核的閉包得到I0，再利用狀態(tài)轉(zhuǎn)換函數(shù)，求出LR（O）項(xiàng)目集

40、規(guī)范族。識(shí)別活前綴的有窮自動(dòng)機(jī)構(gòu)造LR（0）項(xiàng)目集規(guī)范族構(gòu)造DFA 61例：已知文法GA：A(A) | a ，構(gòu)造LR（O）項(xiàng)目集規(guī)范族。解：增廣文法：(0)AA (1)A(A) (2)Aa LR（0）項(xiàng)目： A A AA A (A) A ( A) A (A ) A (A) A a A a 下面利用項(xiàng)目集的閉包函數(shù)和狀態(tài)轉(zhuǎn)換函數(shù)求LR（O）項(xiàng)目集規(guī)范族:I1=GO(I0,A)=Closure(AA.)=AA.I0=Closure(A.A)=A.A,A.(A),A.aI3=GO(I0,a)=Closure(Aa.)=Aa.I2=GO(I0,( ）=A(.A),A.(A),A.a I4=GO(I2

41、,A)=Closure(A(A.)=A(A.)I5=GO(I4,)=Closure(A(A).)=A(A).識(shí)別活前綴的有窮自動(dòng)機(jī)構(gòu)造LR（0）項(xiàng)目集規(guī)范族構(gòu)造DFA 62四 構(gòu)造LR（0）分析表的算法 假設(shè)已經(jīng)構(gòu)造出LR(0)項(xiàng)目集規(guī)范族：C= I0，I1，In , 分析表的動(dòng)作表ACTION和狀態(tài)轉(zhuǎn)換表GOTO的構(gòu)造方法為： 若Ab Ii ，bVT 且GO(Ii,b)= Ik 則令 ACTION(i, b)=Sk （移進(jìn)b(符號(hào)棧)，k入狀態(tài)棧頂） 若AIi 則對(duì)任何bVT # , 令A(yù)CTION(i, b)=rj (rj表示用第j條規(guī)則A歸約） 若SSIi 則令A(yù)CTION(i, #)=

42、acc 若GO(Ii,A)= Ij ， AVN 則令GOTO(i, A)=j (A在文法符號(hào)棧頂, j入狀態(tài)棧頂)凡不能用上述填入的項(xiàng)，均應(yīng)填上報(bào)錯(cuò)標(biāo)志。63 例 文法： A(A) | a，根據(jù)項(xiàng)目集規(guī)范族構(gòu)造分析表。 解： 拓廣文法：(0) AA (1) A(A) (2)Aa 該文法的項(xiàng)目集規(guī)范族為： I0=A .A, A.(A)，A.a I1=A A. I2= A(.A)，A.(A)，A.a I3= Aa. I4= A(A.) I5= A(A).狀態(tài) ACTION GOTO () a# A0S2S311ACC2S2S343R2R2R2R24S55R1R1R1R1 LR(0)分析表 四 構(gòu)造

43、LR（0）分析表的算法 64五 LR（0）文法 1 存在沖突的項(xiàng)目集 項(xiàng)目分成4類：移進(jìn)項(xiàng)目、歸約項(xiàng)目、待約項(xiàng)目和接受項(xiàng)目。 一個(gè)項(xiàng)目集中可能包含不同類型的項(xiàng)目，但必須滿足兩個(gè)條件：1)不能有移進(jìn)項(xiàng)目和歸約項(xiàng)目并存，2)不能有多個(gè)歸約項(xiàng)目并存。 如果某一項(xiàng)目集出現(xiàn)移進(jìn)項(xiàng)目和歸約項(xiàng)目并存，我們說該項(xiàng)目集存在“移進(jìn)-歸約沖突”； 如果某一項(xiàng)目集出現(xiàn)多個(gè)歸約項(xiàng)目并存，我們說該項(xiàng)目集存在“歸約-歸約沖突”。65沖突：若一個(gè)項(xiàng)目集中同時(shí)存在兩個(gè)有效項(xiàng)目，其動(dòng)作是不同的，就會(huì)產(chǎn)生沖突。沖突類型：1）移進(jìn)-歸約沖突 2）歸約-歸約沖突 Ik：沖突解決：通過向前看k個(gè)符號(hào)來解決，能解決的稱為L(zhǎng)R(k)文法無論

44、向前看多少符號(hào)都無法解決沖突非LR(k)文法Ik ：A. bB.面臨輸入符號(hào)b時(shí)移進(jìn)b歸約為B沖突A. B.歸約為A歸約為B沖突66移進(jìn)-歸約沖突： 例如某項(xiàng)目集為 Ab，B，因Ab是移進(jìn)項(xiàng)目，而B 是歸約項(xiàng)目，則當(dāng)面臨輸入符號(hào)b時(shí)，無法確定應(yīng)把b移進(jìn)棧，還是把 歸約為B，從而發(fā)生移進(jìn)-歸約沖突。 歸約-歸約沖突 如果某一項(xiàng)目集中存在多個(gè)歸約項(xiàng)目并存，則該項(xiàng)目集存在歸約-歸約沖突。例如某項(xiàng)目集為A，B，則在該狀態(tài)下，不知應(yīng)歸約為A還是B。 2. LR(0) 文法定義 若一個(gè)文法的LR(0)項(xiàng)目集規(guī)范族不存在含“移進(jìn)-歸約沖突”或“歸約-歸約沖突”的項(xiàng)目集，則該文法稱為L(zhǎng)R(0)文法，所構(gòu)造的分

45、析表為L(zhǎng)R(0)分析表。顯然LR(0)分析表不存在多重定義。 五 LR（0）文法67例：S(S)S| ，判斷該文法是否為L(zhǎng)R(0)文法。為什么？解：增廣文法：(0)SS(1)S(S)S(2)SLR（0）項(xiàng)目： S.S S S. S.(S)S S(.S)S S(S.)S S(S).S S (S)S. S.LR（0）項(xiàng)目集規(guī)范族I0 ：S .S，S.(S)S，S.I1 ：S S.I2： S (.S)S，S.(S)S，S.I3： S (S.)SI4： S (S).S，S.(S)S，S.I5： S (S)S.因?yàn)镮0、I2、I4都包含了移進(jìn)-歸約沖突，所以該文法不是LR(0)文法。 狀態(tài) ACTION

46、 GOTO () #S0R2、S2R2R211ACC2R2、S2R2R233S44R2、S2R2R255R1R1R1五 LR（0）文法68 只有LR(0)文法才能構(gòu)造有效的LR(0)分析表，否則，構(gòu)造的分析表會(huì)出現(xiàn)多重定義。 LR(0)文法是一種非常簡(jiǎn)單的文法，在這種文法的識(shí)別活前綴的自動(dòng)機(jī)中，每一個(gè)狀態(tài)對(duì)應(yīng)的項(xiàng)目集都不含沖突項(xiàng)目。然而，很多文法都不是LR(0)文法，如表達(dá)式文法就不是LR(0)文法。 實(shí)際上，LR(0)文法并不能充分表達(dá)當(dāng)前程序設(shè)計(jì)語言中的各種結(jié)構(gòu)。對(duì)這些語言為了確定分析動(dòng)作，至少要向前查看一個(gè)符號(hào)。這就是我們接下來要介紹的SLR(1)分析器。五 LR（0）文法697.3 S

47、LR（1）分析法 1. SLR（1）分析法 LR(0)文法是一類非常簡(jiǎn)單的文法，其LR(0) 項(xiàng)目集規(guī)范族的任何項(xiàng)目集不能含有 “移進(jìn)-歸約沖突”或“歸約-歸約沖突”。 當(dāng)不是LR(0)文法時(shí)，通過向前查看一個(gè)輸入符號(hào)來協(xié)助解決沖突的分析方法，稱為SLR(1) 分析法。 2SLR(1) 分析法對(duì)沖突的解決 由于句柄是和具體的規(guī)范句型相聯(lián)系，每個(gè)句柄后面所跟隨的符號(hào)是固定的。當(dāng)對(duì)某句柄歸約時(shí)，可根據(jù)相應(yīng)句柄后面的符號(hào)來判斷這種歸約是否正確。句柄后面的符號(hào)可由句柄對(duì)應(yīng)的非終極符的Follow集求得。 ET+E）E（T-E規(guī)范句型：E+(E-T)EE+T | TTT*F | FFi | (E)707

48、.3 SLR（1）分析法 一般地，如果一個(gè)LR(0)規(guī)范族中含有如下形式的一個(gè)項(xiàng)目集：I= Ab ，B ，C 解決移進(jìn)-歸約沖突及歸約-歸約沖突的辦法： (1) 對(duì)于歸約項(xiàng)目B 和C ，分別求出B和C的Follow集。 對(duì)于移進(jìn)項(xiàng)目Ab ，求出移進(jìn)符號(hào)集b， 如果滿足如下的條件，就可以解決沖突: b Follow（B）=, b Follow（C）=， 且 Follow(B) Follow(C)= 。(2) 當(dāng)DFA的狀態(tài)I面臨任何輸入符號(hào)a時(shí)： 若a=b，則移進(jìn)。 若a Follow（B）,用B 歸約。 若a Follow（C）,用C 歸約。 此外出錯(cuò)。717.3 SLR（1）分析法 3SLR

49、(1) 分析表SLR(1) 分析表是通過向前看一個(gè)符號(hào)構(gòu)造出來的，方法詳見下頁。構(gòu)造方法與LR（0）分析表類似，只需修改 ：若AIi, 則對(duì)任何 bFOLLOW(A), 令A(yù)CTION(i, b)=rj ( rj表示用第j條規(guī)則A歸約）對(duì)于歸約項(xiàng)目，僅對(duì)屬于Follow集中的符號(hào)填rj 。這比LR(0)分析表優(yōu)越， 有利于及時(shí)發(fā)現(xiàn)錯(cuò)誤，避免非法歸約。 4SLR(1) 文法 如果一文法能構(gòu)造出只含唯一表項(xiàng)的SLR(1)分析表，或者當(dāng)“移進(jìn)-歸約沖突”和“歸約-歸約沖突”可以通過考察有關(guān)非終結(jié)符的FOLLOW集而得到解決，即通過向前查看一個(gè)輸入符號(hào)來協(xié)助解決沖突時(shí)，該文法就是SLR(1)文法。 一

50、個(gè)LR(0)文法顯然存在非二義性的SLR(1)分析表，所以LR(0)文法一定是SLR(1)文法。727.3 SLR（1）分析法3 SLR（1）分析表假設(shè)已經(jīng)構(gòu)造出LR(0)項(xiàng)目集規(guī)范族：C= I0，I1，In , 分析表的動(dòng)作表ACTION和狀態(tài)轉(zhuǎn)換表GOTO的構(gòu)造方法為： 若Ab Ii ，bVT 且GO(Ii,b)= Ik 則令 ACTION(i, b)=Sk （移進(jìn)b(符號(hào)棧)，k入狀態(tài)棧頂） 若AIi 則對(duì)任何 bFOLLOW(A), 令A(yù)CTION(i, b)=rj (rj表示用第j條規(guī)則A歸約） 若SSIi 則令A(yù)CTION(i, #)=acc 若GO(Ii,A)= Ij ， AVN

51、 則令GOTO(i, A)=j (A在文法符號(hào)棧頂, j入狀態(tài)棧頂)凡不能用上述填入的項(xiàng)，均應(yīng)填上報(bào)錯(cuò)標(biāo)志。737.3 SLR（1）分析法 例：S(S)S| ，判斷該文法是否為SLR(1)文法。為什么？解：增廣文法：(0)SS(1)S(S)S(2)SI0的沖突解決：Follow(S)=#,），移進(jìn)符號(hào)集為（， 顯然有（ Follow（S）=,所以I0遇見“（” 移進(jìn)，遇見“#”或“）”時(shí)用S歸約。 I2、I4 的解決方法與I0 相同。該文法通過向前看一個(gè)符號(hào)，解決了LR(0)沖突，可構(gòu)造具有無二義性的SLR(1)分析表，所以是SLR(1)文法。 I0 ：S .S，S.(S)S，S.I1 ：S

52、S.I2： S (.S)S，S.(S)S，S.I3： S (S.)SI4： S (S).S，S.(S)S，S.I5： S (S)S.因?yàn)镮0、I2、I4都包含了移進(jìn)-歸約沖突，所以該文法不是LR(0)文法。 狀態(tài) ACTION GOTO () # S0S2R2R211ACC2S2R2R233S44S2R2R255R1R1747.3 SLR（1）分析法 例：S(S)S| ，判斷該文法是否為SLR(1)文法。為什么？解：狀態(tài) ACTION GOTO () # S0S2R2R211ACC2S2R2R233S44S2R2R255R1R1輸入串 ()()# 的分析過程 步驟狀態(tài)棧符號(hào)棧輸入流分析動(dòng)作00

53、#()()#S2102#()()#r22023#(S)()#S430234#(S)()#S2402342#(S)()#r25023423#(S)(S)#S460234234#(S)(S)#r2702342345#(S)(S)S#r1802345#(S)S#r19 01 #S # acc SLR(1)分析表增廣文法：(0)SS(1)S(S)S(2)S757.3 SLR（1）分析法 例：文法SaSb|aSc|ab是否為SLR(1)文法？若是，給出SLR(1)分析表，若不是，給出理由。解：增廣文法：(0)SS(1)SaSb(2)SaSc(3)Sab 因?yàn)長(zhǎng)R(0)項(xiàng)目集規(guī)范族無沖突的項(xiàng)目集，所以該文

54、法是LR(0)文法，也是SLR(1)文法。 LR(0)項(xiàng)目集規(guī)范族：I0：S.S，S.aSb，S.aSc，S.abI1：SS.I2：Sa.Sb，Sa.Sc，Sa.b， S.aSb， S.aSc，S.ab I3：SaS.b，SaS.c，I4：Sab.I5：SaSb.I6：SaSc.狀態(tài) ACTION GOTO ab c# S0S211ACC2S2S433S5S64R3R3R356R1R2R1R2R1R276例2：(p131)下面文法是否為L(zhǎng)R(0)文法？是否為SLR(1)文法？為什么？并給出相應(yīng)的分析表。GE： 1) EaA 4) Ad 2) EbB 5) BcB 3) AcA 6) Bd解：拓

55、廣文法： 0) SE 1) EaA 4) Ad 2) EbB 5) BcB 3) AcA 6) Bd77LR（0）分析表狀態(tài)（規(guī)范族） a b c d #E A BI0: S.E E.aA E.bB S2 S31I1: SE. accI2: Ea.A A.cA A.d S5 S6 4I3: Eb.B B.cB B.d S8 S9 7I4: EaA.r1 r1 r1 r1 r1I5: Ac.A A.cA A.d S5 S6 10I6: Ad.r4 r4 r4 r4 r4 follow(A)=#78LR（0）分析表狀態(tài)（規(guī)范族） a b c d #E A BI7: EbB. r2 r2 r2 r2

56、 r2I8: Bc.B B.cB B.d S8 S9 11I9: Bd.r6 r6 r6 r6 r6I10: AcA.r3 r3 r3 r3 r3 I11: BcB.r5 r5 r5 r5 r5 由于LR（0）分析表沒有沖突項(xiàng)目，所以是LR（0）文法，也是SLR（1）文法。79例3：GS SrD DD, i | i是否為SLR(1)文法，是否為L(zhǎng)R(0)文法？解：拓廣文法為G: (0) SS (2) DD, i (1) SrD (3) Di識(shí)別活前綴的DFA：（直接構(gòu)造）I3: SrD. DD.,i I2: Sr.D D.D,i D.iI1:SS. SI6:DD,i. I5:DD,.i I4:

57、Di. I0: S.S S.rD D,iir80分析：在I3中含項(xiàng)目SrD. 歸約DD.,i 移進(jìn)項(xiàng)目顯然不是LR(0)文法。但由于：follow(S)=# Follow(D)=，, #構(gòu)造SLR(1)分析表如下：狀態(tài)fgotor,i#SD0S211acc2S433S5r14r3r35S66r2r2SLR(1)表中無多重定義，所以是SLR(1)文法。注意:教材P138 表7.7有誤 (0) SS (2) DD, (1) SrD (3) Di81例4(p140)：GE拓廣文法如下：(0) SE (3) TT*F (1) EE+T (4) TF (2) ET (5) F(E) (6) Fi證明其是

58、SLR(1)文法，并構(gòu)造出分析表。文法是LR(0)文法嗎？解：I0 : S.E E.E+T E.T T.T*F T.F F.(E) F.iI1 : GOTO(I0,E) SE. EE.+T I2 : ET.GOTO(I0,T) TT.*F I3 : TF.GOTO(I0,F) I4 : F(.E) I8GOTO(I0,() E.E+T E.T I2 T.T*E T.F I3 F. (E) I4 F.i I5 82I5 : GOTO(I0,i) Fi. I6 : GOTO(I1,+) EE+.T T.T*F T.F F.(E) F.i I7 : GOTO(I2,*) TT*.F F.(E) F.

59、i I8 : GOTO(I4,E) F(E.) EE.+T I9 : GOTO(I6,T) EE+T. TT.*F I11 : GOTO(I8,) F(E). I10 : GOTO(I7,F) TT*F. 83判斷：考察全部項(xiàng)目集（1）只有一個(gè)項(xiàng)目，不可能沖突（2）沒有歸約項(xiàng)目，也不可能沖突只有I2,I9中存在移進(jìn)-歸約沖突：I1中：SE.只有在遇到#號(hào)時(shí)，接受； EE.+T，遇到+號(hào)移進(jìn)，不沖突I2中：ET. , TT.*F 由于follow(E)=+, ), #，所以面臨+,),#時(shí)，用產(chǎn)生式ET規(guī)約。當(dāng)面臨*號(hào)時(shí)，則移進(jìn)?？山鉀Q沖突I9中：EE+T, TT.*F 與I2類似，遇到foll

60、ow(E)=+,),#歸約，遇到*號(hào)移進(jìn)所以文法是SLR(1)文法，不是LR(0)文法84SLR(1)分析表狀態(tài)ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48 235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r585C:狀態(tài)fgabcde#SAI0: S.S S.aAd S.bAc Saec S.bed S2S31I1: SS.accI2: Sa.Ad Sa.ec A.eS54I3: Sb.Ac Sb.ed A.eS76例5：(0) SS (1) SaAd (