天津科技大學(xué)編譯原理 第4章LR分析法

4.5LR分析法迄今為止我們所學(xué)的分析方法對(duì)文法都有一定的要求,即有局限性;1965年D.Knuth提出了分析效率極高的LR(k)分析技術(shù);LR分析:自左至右掃描的自底向上的分析;在分析的每一步,只須根據(jù)分析棧中的已移進(jìn)的和已歸約出的符號(hào),并至多向前掃描k個(gè)字符就能確定應(yīng)采取什么分析動(dòng)作(移進(jìn)、歸約、接受、報(bào)錯(cuò));LR分析對(duì)文法要求很少,效率極高,且能及時(shí)發(fā)現(xiàn)錯(cuò)誤,是目前最廣泛使用的方法;一般用CFG描述的語言均可用LR分析法缺點(diǎn)：構(gòu)造LR分析程序工作量很大。由于常見的程序設(shè)計(jì)語言均能由LR(1)文法產(chǎn)生,因此我們只討論k=0,1兩種情況;本節(jié)中,將先介紹LR分析器的邏輯結(jié)構(gòu)及工作原理,再分別介紹幾種LR分析器(即LR(0),SLR(1),LR(1)和LALR(1))的構(gòu)造;1.LR分析法根本思想：在標(biāo)準(zhǔn)規(guī)約分析過程中，根據(jù)分析棧中記錄的已移進(jìn)和規(guī)約出的整個(gè)符號(hào)串〔即歷史〕和根據(jù)使用的規(guī)那么推測(cè)未來可能遇到的輸入符號(hào)〔即展望〕，以及現(xiàn)實(shí)讀到的輸入符號(hào)，這三個(gè)方面的信息來確定句柄的形成。即根據(jù)分析棧形成的歷史和展望〔常以狀態(tài)表示〕向右順序查看輸入串的K個(gè)〔K>=0〕符號(hào)就可唯一地確定句柄。

4.5.1LR分析器工作原理和過程2.LR分析器的組成

LR總控程序

actiongoto

LR分析表a1a2

ai

an#輸入串

輸出狀態(tài)符號(hào)分析?？偪爻绦颍核蠰R分析器總控程序相同。分析棧:記錄了已分析的內(nèi)容及當(dāng)前的狀態(tài)，包括狀態(tài)棧S和文法符號(hào)棧X。分析表是LR分析器的核心ACTION[Si,a](a?VT)當(dāng)棧頂狀態(tài)Si面臨輸入符號(hào)a時(shí)，應(yīng)采取分析動(dòng)作.GOTO[Si,X](X?VTorVN)指明當(dāng)分析棧移進(jìn)一個(gè)輸入符號(hào)或按某產(chǎn)生式進(jìn)行歸約后所要轉(zhuǎn)移到的下一狀態(tài)。在分析的每一步，總控程序從左到右掃描輸入符號(hào)串，并根據(jù)狀態(tài)棧棧頂狀態(tài)和當(dāng)前輸入符號(hào)a查LR分析表，并執(zhí)行表中規(guī)定的操作完成每一步的分析工作。a1a2…alS1ACTION(S1,a1]ACTION(S1,a2]…ACTION(S1,al]S2ACTION(S2,a1]ACTION(S2,a2]…ACTION(S2,al]……………SnACTION(Sn,a1]ACTION(Sn,a2]…ACTION(Sn,al]X1X2…XlS1GOTO(S1,X1]GOTO(S1,X2]…GOTO(S1,Xl]S2GOTO(S2,X1]GOTO(S2,X2]…GOTO(S2,Xl]……………SnGOTO(Sn,X1]GOTO(Sn,X2]…GOTO(Sn,Xl]GOTO表ACTION表3.LR分析器的工作過程1.分析開始時(shí),首先將初始狀態(tài)S0及$壓入狀態(tài)棧和符合棧;2.設(shè)在分析的某一步,分析棧和剩余輸入串處于格局:

S0S1S2…Sm$X1X2…Xm aiai+1ai+2…an$用Sm,ai查ACTION表，并根據(jù)指示完成相應(yīng)的動(dòng)作：移進(jìn)，歸約，報(bào)錯(cuò)，接受四種:(1)移進(jìn)句柄尚未在棧頂形成,正期待繼續(xù)移進(jìn)輸入符號(hào)以形成句柄,故將ai壓入符號(hào)棧:

S0S1S2…Sm$X1X2…Xmaiai+1ai+2…an$再用Sm,ai

查GOTO表,獲得下一狀態(tài)Sm+1,將Sm+1壓入狀態(tài)棧:S0S1S2…SmSm+1$X1X2…Xmaiai+1ai+2…an$(2)歸約rj:其中rj表示按P的第j規(guī)那么AXm-r+1Xm-r+2Xm進(jìn)行歸約；這說明棧頂部的符號(hào)串Xm-r+1Xm-r+2Xm是當(dāng)前句型的句柄。歸約的方法是從狀態(tài)棧和符號(hào)棧棧頂去掉r個(gè)符號(hào)，將A壓入符號(hào)棧,此時(shí)的格局為 S0S1S2…Sm-r#X1X2…Xm-rAaiai+1ai+2…an# 再以〔Sm-r,A〕查GOTO表,得Sk,將Sk壓入狀態(tài)棧,得到格局: S0S1S2…Sm-rSk#X1X2…Xm-rAaiai+1ai+2…an# 注意：完成歸約動(dòng)作時(shí)，輸入串指針并未移動(dòng)。(3)假設(shè)ACTION(Sm,ai)=“acc〞，那么說明當(dāng)前輸入串已被成功地分析完畢,結(jié)束；(4)假設(shè)ACTION(Sm,ai)=“ERROR〞，那么說明當(dāng)前輸入串有語法錯(cuò)誤,轉(zhuǎn)入出錯(cuò)處理程序；3.重復(fù)步驟2.的工作，直到分析棧中只剩文法開始符號(hào)和當(dāng)前讀到的輸入符號(hào)是〞$〞為止。此時(shí)的格局應(yīng)為: S0SZ $Z$ 其中,Z為文法的開始符號(hào),SZ是使ACTION(SZ,$)=“acc〞的唯一狀態(tài)。ACTIONGOTOacebd$acebd$SAB0S211acc2SS133r2r2r2r2r2r2ACTIONGOTOacebd$SAB0S211acc2S1S33r2r2r2r2r2r2從分析表的功能中可知,GOTO表中所有關(guān)于終結(jié)符的狀態(tài)轉(zhuǎn)換都與相應(yīng)的ACTION表相關(guān)，故可將其合并到ACTION表中，只將關(guān)于VN的狀態(tài)轉(zhuǎn)換保存在GOTO表中。4.LR分析表合并5.總控程序的算法輸入：輸入串w和LR分析表輸出：w是否是合法語句While(Action[S,a]!=acc){ if(Action[S,a]==Si) { 將狀態(tài)i和輸入符號(hào)a進(jìn)棧； 下一個(gè)輸入符號(hào)讀進(jìn)a; } elseif(Action[S,a]==rj) { 用第j條規(guī)那么規(guī)約A-->β; 將|β|個(gè)狀態(tài)和符號(hào)出棧； 當(dāng)前棧頂符號(hào)S’，將A和GOTO[S’,A]進(jìn)棧； } elseif(Action[S,a]==error) error();}LR分析例〔LR(0)分析〕文法G[S]：(1)S->aAcBe (2)A->b (3)A->Ab (4)B->d對(duì)輸入串a(chǎn)bbcde$進(jìn)行LR分析ACTIONGOTOacebd$SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR(0)分析表為：對(duì)輸入串a(chǎn)bbcde$的分析過程(1)S->aAcBe (2)A->b (3)A->Ab (4)B->dacc$$011R1$$aAcBe02357910S9e$$aAc02359R4e$$aAcd023588S8de$$aAc02357S5cde$$a026R3cde$$aAb02365S6bcde$$a024R2bcde$$ab0243S4bbcde$$a022S2abbcde$$01GOTOACTION輸入串符號(hào)棧狀態(tài)棧步驟A333A37B71S14.5.2LR(0)分析法使用LR(0)分析表的LR分析器稱為LR(0)分析器。LR(0)分析在分析每一步，只需根據(jù)當(dāng)前棧頂狀態(tài)而不必向前查看輸入符號(hào)就能確定采取的動(dòng)作。LR(0)分析法對(duì)文法的限制較大，對(duì)絕大多數(shù)高級(jí)語言的語法分析器不適用。構(gòu)造LR(0)分析表的思想和方法是構(gòu)造其他LR分析表的根底。構(gòu)造LR分析表根本思想從給定的上下文無關(guān)文法直接構(gòu)造識(shí)別文法所有標(biāo)準(zhǔn)句型的活前綴的DFA按DFA構(gòu)造相應(yīng)分析表——狀態(tài)轉(zhuǎn)換表和動(dòng)作表1.標(biāo)準(zhǔn)句型的活前綴前綴：是指字符串的任意首部。例：abc的前綴有ε，a，ab，abc?；钋熬Y：是指標(biāo)準(zhǔn)句型的前綴，此前綴不包含句柄右邊的任何符號(hào)。注意：活前綴可以是一個(gè)或假設(shè)干個(gè)標(biāo)準(zhǔn)句型的前綴。例：標(biāo)準(zhǔn)句型aAbcde(下劃線為句柄)的活前綴為：ε，a，aA，aAb活前綴在LR分析中的作用 在LR分析過程中，任何時(shí)刻棧中文法符號(hào)總是某一標(biāo)準(zhǔn)句型的活前綴。一旦在棧中出現(xiàn)句型的句柄，就用相應(yīng)的產(chǎn)生式進(jìn)行歸約， 在分析的過程中，只要符號(hào)棧中的符號(hào)串是一個(gè)活前綴，就可保證已被分析過的局部是該文法標(biāo)準(zhǔn)句型的正確局部。LR分析過程實(shí)際上就是一個(gè)逐步產(chǎn)生(識(shí)別)活前綴的過程。提示:假設(shè)能構(gòu)造一個(gè)識(shí)別所有活前綴的自動(dòng)機(jī),那么構(gòu)造分析表就不難了。歸約（S→aAcBe）$$aAcBe10）接受$$S11）移進(jìn)ee$$aAcB9）歸約（B→d）e$$aAcd8）移進(jìn)dde$$aAc7）歸約（A→Ab）cde$$aAb5）移進(jìn)ccde$$aA6）移進(jìn)bbcde$$aA4）歸約（A→b）bcde$$ab3）移進(jìn)bbbcde$$a2）移進(jìn)aabbcde$$1）動(dòng)作輸入符號(hào)串符號(hào)棧步驟活前綴全部列出在符號(hào)棧中，對(duì)句柄的識(shí)別變成了對(duì)活前綴的識(shí)別〔1〕活前綴與當(dāng)前句柄的關(guān)系句柄全部在活前綴中(句柄是活前綴的后綴)。活前綴只含句柄的局部符號(hào)(活前綴的后綴是句柄的前綴)。活前綴不含任何句柄符號(hào)。對(duì)于①,應(yīng)進(jìn)行歸約:A,記：A;對(duì)于②,應(yīng)移進(jìn)(句柄的后半局部),記：A12;對(duì)于③,期望移進(jìn)一產(chǎn)生式的右部，記：A2.LR(0)工程〔2〕在文法G中每個(gè)產(chǎn)生式的右部適當(dāng)位置添加一個(gè)圓點(diǎn)構(gòu)成LR(0)工程。例：產(chǎn)生式U→XYZ對(duì)應(yīng)有4個(gè)工程[0]U→?XYZ [1]U→X?YZ[2]U→XY?Z [3]U→XYZ? 產(chǎn)生式A→ε只有一個(gè)工程A→?〔3〕一個(gè)LR(0)工程指明了對(duì)文法標(biāo)準(zhǔn)句型活前綴的不同識(shí)別狀態(tài)，文法G的全部LR(0)工程是構(gòu)造識(shí)別文法所有標(biāo)準(zhǔn)句型活前綴的DFA根底。文法G(S)S→EE→aA|bBA→cA|dB→cB|d該文法的工程有：1.S→·E 2.S→E· 3.E→·aA4.E→a·A 5.E→aA· 6.A→·cA7.A→c·A 8.A→cA· 9.A→·d10.A→d· 11.E→·bB 12.E→b·B13.E→bB· 14.B→·cB 15.B→c·B16.B→cB· 17.B→·d 18.B→d·〔3〕LR(0)工程分類根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符把工程分為以下幾種:移進(jìn)工程：形如A→α?аβ的工程，其中а∈VT,α,β∈V*。那么有待于移進(jìn)一個(gè)VT符號(hào)X到棧中,因此稱為移進(jìn)工程。待約工程：形如A→α?Bβ的工程，其中B∈VN,α,β∈V*。即圓點(diǎn)后面為非終結(jié)符的工程。說明用產(chǎn)生式A的右部歸約時(shí)，首先要將B的產(chǎn)生式右部歸約為B，對(duì)A的右部才能繼續(xù)進(jìn)行分析。也就是期待著繼續(xù)分析過程中首先能歸約得到B。歸約工程：形如A→α?的工程，α∈V*,α=ε對(duì)應(yīng)的工程為A->?即圓點(diǎn)在最右端的工程。說明該產(chǎn)生式的右部已分析完，句柄已形成，可以把α歸約為A。接受工程：當(dāng)歸約工程為S’→S?，其中S‘是文法開始符號(hào)即對(duì)文法開始符的歸約工程。說明輸入串可歸約為文法開始符，分析結(jié)束。3.構(gòu)造以LR(0)工程集為狀態(tài)的識(shí)別活前綴的DFALR(0)工程集：識(shí)別文法標(biāo)準(zhǔn)句型活前綴的DFA的每個(gè)狀態(tài)都是由假設(shè)干LR(0)工程組成的集合。LR(0)工程集標(biāo)準(zhǔn)族：LR(0〕工程集(狀態(tài))的全體。識(shí)別活前綴的DFA的構(gòu)造如何構(gòu)造DFA的一個(gè)狀態(tài)〔工程集〕如何由DFA的一個(gè)狀態(tài)求其他狀態(tài)如果I是拓廣文法G’的一個(gè)LR(0)工程集，定義和構(gòu)造I的閉包CLOSURE(I)如下：I的工程均在CLOSURE(I)中；b)A→XCLOSURE(I),XVN,那么任何X-產(chǎn)生式X→P, XCLOSURE(I);重復(fù)b〕直到CLOSURE(I)不再增大為止。說明：圓點(diǎn)后為終結(jié)符或在一個(gè)產(chǎn)生式的最后，求閉包時(shí)不會(huì)增加新的工程〔1〕閉包函數(shù)CLOSURE(I)例：S’→EE→aA|bBA→cA|d B→cB|d設(shè)工程集I={S’→?E}那么CLOSURE(I)={S’→?E，E→?aA，E→?bB}

CLOSURE(I)作為DAF的一個(gè)狀態(tài)作用：由DFA的一個(gè)狀態(tài)求其他狀態(tài)設(shè)I為拓廣文法G‘的某一工程集(狀態(tài))，X∈(VN∪VT),那么 GO(I,X)=CLOSURE(J) 其中J={A→αX?β│A→α?Xβ∈I}稱J為“核〞〔2〕狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)例：設(shè)拓廣文法G(S’):S’→EE→aA|bB A→cA|dB→cB|d設(shè)I={S’→?E，E→?aA，E→?bB}，那么GO(I,E)=CLOSURE({S’→E?})={S’→E?}GO(I,a)=CLOSURE({E→a?A})={E→a?A,A→?cA,A→?d}GO(I,b)=CLOSURE({E→b?B})={E→b?B,B→?cB,B→?d}(3)構(gòu)造以LR(0)工程集為狀態(tài)的DFA 構(gòu)造初始狀態(tài)I0=CLOSURE({S’→?S})，并且它是未被標(biāo)記的。從已經(jīng)構(gòu)造的DFA局部圖中選擇一個(gè)未被標(biāo)記的狀態(tài)Ii，標(biāo)記Ii，假設(shè)工程集Ii中含有工程 U->x?Ry(R∈V,x,y為任一符號(hào)串)，且GO(Ii,R)=Ij，假設(shè)Ij不在DFA中，那么將Ij作為未被標(biāo)記的參加DFA中，且從Ii出發(fā)引一條標(biāo)記為R的弧到Ij，重復(fù)b)直到?jīng)]有未被標(biāo)記的狀態(tài)為止。我們可得到全部的狀態(tài),其集合稱為文法G‘的LR(0)工程集標(biāo)準(zhǔn)族,記為C(C={I0,I1,…,I10});至此,構(gòu)造的識(shí)別文法G’全部活前綴的DFA為:M=(C,V,GO,I0,C);其中,狀態(tài)集及終態(tài)集為工程集標(biāo)準(zhǔn)族C;字母表為V=VN∪VT初態(tài)為I0;轉(zhuǎn)換函數(shù)為GO;例拓廣文法G’：S’→E E→aA|bB A→cA|d B→cB|d構(gòu)造以LR(0)工程集為狀態(tài)的DFAS’→?ES’→E?E→a?A

aE→b?B

EbE→aA?A→c?A

cAA→d?E→bB?B→c?B

cB→d?A→cA?AB→cB?BdcddBcdE→?aAE→?bBI0I1I2I3I4I5I6I7I8I9I10I11A→?cAA→?dB→?cBB→?dA→?cAA→?dB→?cBB→?d(4)LR(0)分析表的構(gòu)造假設(shè)對(duì)于一個(gè)文法G的拓廣文法G’的LR(0)工程集標(biāo)準(zhǔn)族中的每個(gè)工程集，不存在移進(jìn)工程和歸約工程同時(shí)并存或多個(gè)歸約工程同時(shí)并存，那么稱G為LR(0)文法。為了節(jié)省存儲(chǔ)空間，把關(guān)于終結(jié)符局部的GOTO表和ACTION表重疊，也就是把當(dāng)前狀態(tài)下面臨終結(jié)符應(yīng)做的移進(jìn)－歸約動(dòng)作和轉(zhuǎn)向動(dòng)作一起表示。對(duì)LR(0)文法，其分析表的構(gòu)造算法如下:設(shè)LR(0)工程集標(biāo)準(zhǔn)族為C={I0,I1,…,In}，令工程集Ik對(duì)應(yīng)的狀態(tài)為k，含S’→?S工程的工程集對(duì)應(yīng)的狀態(tài)為初始狀態(tài)，分析表的ACTION表和GOTO表構(gòu)造步驟為：假設(shè)工程A→α?aβ∈Ik，a∈VT，且GO(Ik,a)=Ij，那么置ACTION[k,a]=‘Sj’假設(shè)工程A→α?Bβ∈Ik，B∈VN，且GO(Ik,B)=Ij，那么置GOTO[k,B]=‘j’假設(shè)工程A→α?∈Ik，且產(chǎn)生式A→α的編號(hào)為j，那么對(duì)任何a〔終結(jié)符和‘$’〕，置ACTION[k,a]=‘rj’假設(shè)工程S’→S?∈Ik，那么置ACTION[k,$]=‘a(chǎn)cc’不能用上述方法填入的分析表的元素均應(yīng)填上“報(bào)錯(cuò)標(biāo)志〞。拓廣文法G’：(0)S’→E (1)E→aА (2)E→bB (3)A→cА(4)A→d (5)B→cB (6)B→d識(shí)別活前綴的DFA：

S’→?E

S’→E?E→a?A

a

E→b?BEbE→aA?A→c?A

cA

A→d?

E→bB?

B→c?B

c

B→d?

A→cA?A

B→cB?BdcddBcdE→?aAE→?bBI0I1I2I3I4I5I6I7I8I9I10I11A→?cAA→?dB→?cBB→?dA→?cAA→?dB→?cBB→?d10

aACTION

b

c

d

$EGOTOA狀態(tài)119876543210BLR(0)分析表1S2S3acc4S5S67S8S9r1r1r1r1r110S5S6r4r4r4r4r4r2r2r2r2r211S9S8r6r6r6r6r6r3r3r3r3r3r5r5r5r5r5(0)S’→E (1)E→aА (2)E→bB (3)A→cА(4)A→d (5)B→cB (6)B→d輸入串bccd$的分析過程步驟狀態(tài)棧符號(hào)棧輸入串ACTIONGOTO1

2

3

4

567890$bccd$S303$bccd$S8038$bccd$S80388$bccd$S903889$bccd$$$$$r6110388$bccr511038$bcr5703$br210$accB(11)B(11)B7E1寫出給定文法G的拓廣文法G’寫出文法G’的LR(0)工程集〔初態(tài)〕利用CLOSURE和GOTO函數(shù)，求出相應(yīng)的LR(0)工程集標(biāo)準(zhǔn)族C;構(gòu)造識(shí)別該文法全部活前綴的DFA；根據(jù)算法構(gòu)造LR(0)分析表；(5)構(gòu)造LR(0)分析表步驟小結(jié)當(dāng)一個(gè)文法是LR(0)文法時(shí)，才可構(gòu)造出無沖突的LR(0)分析表。LR(0)分析器的特點(diǎn)是不需向前查看輸入符號(hào)就能歸約，不管下一個(gè)輸入符號(hào)是什么都可以立即進(jìn)行歸約而不發(fā)生錯(cuò)誤。4.5.3SLR(1)分析工程集中的沖突 移進(jìn)—?dú)w約沖突 移進(jìn)工程A→α?aβ和歸約工程B→r?同在一個(gè)工程集中，當(dāng)面臨輸入符a時(shí)，不能確定移進(jìn)a還是把r歸約為B；歸約—?dú)w約沖突 歸約工程A→β?和歸約工程B→r?同在一個(gè)工程集中，不管面臨什么輸入符都不能確定把β歸約為A還是把r歸約為B。 一個(gè)文法的LR(0)工程集標(biāo)準(zhǔn)族中的工程集不存在移進(jìn)—?dú)w約沖突，也不存在歸約—?dú)w約沖突時(shí)，稱該文法為LR(0)文法。文法G‘：

(0)S’

S

(1)SrD

(2)DD,i

(3)DiI0:

S‘→?S

S‘→?rDI2:

S→r?D

D

→?D,i

D→?iI3:

S→rD

?

D→D?,iI4:

D→i

?I5:

D→D,?iI1:

S‘→S?I6:

D→D,i

?

SriD,iLR(0)分析表2.SLR(1)分析法根本思想：對(duì)含有沖突的工程集向前查看一個(gè)輸入符號(hào)的方法來解決沖突。假設(shè)一個(gè)LR(0)標(biāo)準(zhǔn)族中工程集I含有沖突工程I={X→α?bβ?Α→r??Β→δ?},其中b∈VT， 如果FOLLOW(A)和FOLLOW(B)互不相交，且不含b，那么當(dāng)狀態(tài)I面臨輸入符a時(shí)，可采用以下動(dòng)作：假設(shè)a=b，那么移進(jìn)；假設(shè)a∈FOLLOW(A)，那么用產(chǎn)生式A→r歸約；假設(shè)a∈FOLLOW(B)，那么用產(chǎn)生式B→δ歸約；此外，報(bào)錯(cuò)。假設(shè)一個(gè)LR(0)標(biāo)準(zhǔn)族中的工程集I有m個(gè)移進(jìn)工程：A1→α1?a1β1,A2→α2?a2β2,…,A→αm?amβm；n個(gè)歸約工程：B1→r1?，B2→r2?，…，Bn→rn?，假設(shè)移進(jìn)符號(hào)集{a1，a2，…，am}和FOLLOW(B1)，F(xiàn)OLLOW(B2)，…，F(xiàn)OLLOW(Bn)兩兩交集為空， 那么當(dāng)狀態(tài)I面臨某輸入符a時(shí)，可采用以下動(dòng)作：假設(shè)a∈{a1，a2，…，am}，那么移進(jìn)；假設(shè)a∈FOLLOW(Bi)，i=1,2,…,n,那么用Bi→ri歸約；此外，報(bào)錯(cuò)。 假設(shè)一個(gè)文法的LR(0)分析表中所含有的動(dòng)作沖突都能用上述方法解決，那么稱這個(gè)文法是SLR(1)文法,所構(gòu)造的分析表為SLR(1)分析表，使用SLR(1)分析表的分析器為SLR(1)分析器。與LR(0)分析表的構(gòu)造類似，僅對(duì)含有沖突的工程集分別進(jìn)行處理。改進(jìn)的SLR(1)方法： 對(duì)所有的歸約工程僅對(duì)當(dāng)前輸入符號(hào)包含在該歸約工程左部非終結(jié)符的FOLLOW集中，才采取歸約動(dòng)作。改進(jìn)的SLR(1)分析表的構(gòu)造方法3.SLR(1)分析表的構(gòu)造算法 設(shè)已構(gòu)造出LR(0)工程集標(biāo)準(zhǔn)族為C={I0,I1,…，In}， 令工程集Ik對(duì)應(yīng)的狀態(tài)為k，含S’→?S工程的工程集為初態(tài)，分析表的ACTION表和GOTO表構(gòu)造步驟為：假設(shè)工程A→α?aβ∈Ik，a∈VT，且GO(Ik,a)=Ij， 那么置ACTION[k,a]=‘Sj’；假設(shè)工程A→α?Bβ∈Ik，B∈VN，且GO(Ik,B)=Ij， 那么置GOTO[k,B]=‘j’；假設(shè)工程A→α?∈Ik，且產(chǎn)生式A→α的編號(hào)為j，那么對(duì)任何a(終結(jié)符和‘$’)，且a∈FOLLOW(A)， 置ACTION[k,a]=‘rj’；假設(shè)工程S’→S?∈Ik，那么置ACTION[k,$]=‘a(chǎn)cc’；不能用上述方法填入的分析表元素均應(yīng)填上“報(bào)錯(cuò)標(biāo)志〞。文法G‘：

(0)S’

S

(1)SrD

(2)DD,i

(3)DiI0:

S‘→?S

S‘→?rDI2:

S→r?D

D

→?D,i

D→?iI3:

S→rD

?

D→D?,iI4:

D→i

?I5:

D→D,?iI1:

S‘→S?I6:

D→D,i

?

SriD,iLR(0)分析表文法G‘：

(0)S’

S

(1)SrD

(2)DD,i

(3)DiSLR(1)分析表FOLLOW(S)={$

}FOLLOW(D)={$,,}I0:

S‘→?S

S‘→?rDI2:

S→r?D

D

→?D,i

D→?iI3:

S→rD

?

D→D?,iI4:

D→i

?I5:

D→D,?iI1:

S‘→S?I6:

D→D,i

?SriD,iLR(0)分析表4.仍有許多文法構(gòu)造的LR(0)工程集標(biāo)準(zhǔn)族存在的動(dòng)作沖突不能用SLR(1)方法解決。例如：文法G‘:(0)S'→SS→L=RS→RL→*RL→iR→L識(shí)別文法活前綴的DFAI0:S’->?S

S->?L=RS->?RL->?*RL->?iR->?LI5:L→i?I2:S->L?=RR->L?I3:S->R?I4:L→*?RR→?LL→?*RL→?iI1:S’->S?I6:S→L=?RR→?LL→?iL→?*RI7:

L→*R?I8:

R→L?I9:S→L=R?SLR*i=RL*iRLi*圖4.14I2:S->L?=RR->L?Follow(R)={$,=}與移進(jìn)符號(hào)集{=}交集不為空，SLR(1)方法不能解決沖突，該文法不是SLR(1)文法。4.5.4LR(1)分析法從SLR(1)解決問題的方法看,對(duì)于歸約工程A→,只要是FOLLOW(A)中的符號(hào)均可按此規(guī)那么進(jìn)行歸約,這有一定的片面性,因未考慮所在標(biāo)準(zhǔn)句型的“環(huán)境〞.當(dāng)在棧頂形成時(shí)(設(shè)此時(shí)棧內(nèi)容為#,輸入符為a),假設(shè)強(qiáng)行將歸約為A(棧內(nèi)容:#A),但#Aa又不是任何標(biāo)準(zhǔn)句型的前綴時(shí),此歸約就是無效的。例：圖4.14分析標(biāo)準(zhǔn)句型i=i的SLR(1)分析過程：狀態(tài)棧符號(hào)棧輸入串0$i=i$05$i=i$02$L=i$03$R=i$例文法G‘:(0)S'→S(1)S→L=R(3)S→R(4)L→*R(5)L→i(6)R→LLR(0)根本思想分析過程中，當(dāng)試圖用某一規(guī)那么A→歸約棧頂符號(hào)串時(shí)，不僅應(yīng)查看棧中符號(hào)串，還應(yīng)向前查看一輸入符號(hào)a，只有當(dāng)Aa構(gòu)成文法某一標(biāo)準(zhǔn)句型的前綴，才可用此規(guī)那么進(jìn)行歸約。為了確保上述條件,需重新定義LR(0)工程。LR(1)工程:二元組[A,a],A是LR(0)工程a是展望符或搜索符。搜索符僅對(duì)歸約工程[A→，a]有意義。對(duì)于任何移進(jìn)或待約工程[A→,a],，搜索符a沒有作用。歸約工程[A→,a]意味著：當(dāng)它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的輸入符號(hào)為a時(shí)，才可以把棧頂上的歸約為A。構(gòu)造LR〔1〕工程集的閉包函數(shù)

a.I的工程都在CLOSURE(I)中

b.假設(shè)[A→?B,a]CLOSURE(I)，B→是文法的規(guī)那么，V*，bFIRST(a),那么[B→?,b]也屬于CLOSURE(I)

c.重復(fù)b)直到CLOSURE(I)不再擴(kuò)大轉(zhuǎn)換函數(shù)的構(gòu)造

GOTO〔I，X〕=CLOSURE〔J〕

其中：I為LR(1)的工程集，X為一文法符號(hào)

J={任何形如[A→X?,a]的工程|[A→?X,a]屬于I}LR(1)工程集族的構(gòu)造〔DFA〕：(1)針對(duì)初始工程[S’→?S,#]求閉包(2)再用轉(zhuǎn)換函數(shù)逐步求出整個(gè)文法的LR(1)工程集族。文法G‘：(0)S’

S

(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeI0={[S’?

?S,#],[S

?aAd,#],[S?bAc,#],[S?aec,#],[S?bed,#]}I1=GOTO(I0,S)={[S’?S?,#]}I2=GOTO(I0,a)={[Sa?Ad,#],[Sa?ec,#],[A?e,d]}I3=GOTO(I0,b)={[Sb?Ac,#],[Sb?ed,#],[A?e,c]]}I4=GOTO(I2,A)={[SaA?d,#]}I5

=GOTO(I2,e)={[Sae?c,#],[Ae?,d]}I6=GOTO(I3,A)={[SbA?c,#]}I11=GOTO(I7,d)={[Sbed?,#]}I