編譯原理chapter7LR分析

第七章LR分析LR分析概述LR(0)分析SLR(1)分析LR(1)分析LALR(1)分析二義文法在LR分析中的應(yīng)用語法分析LR分析：YACC類語法分析器自動構(gòu)造工具所使用的主要算法自下而上的語法分析

（Bottom-upParsing）1 S ->exp2 exp ->exp+term3exp ->term4 term ->term*factor5 term ->factor6 factor ->ID7 factor ->INT2+3*4factor+3*4term+3*4exp+3*4exp+factor*4exp+term*4exp+term*factorexp+termexpS最右推導(dǎo)的逆過程Areverseofright-mostderivation!7.1LR分析概述自下而上分析的關(guān)鍵問題—如何確定“可歸約串”LR(k)分析方法是一種能根據(jù)當(dāng)前分析棧中的符號串（通常以狀態(tài)表示）和向右順序查看輸入串的k個(gè)（k>=0）符號就可唯一確定分析器的動作是移進(jìn)還是歸約以及用那個(gè)產(chǎn)生式歸約（從而確定句柄）的分析方法。LR分析是規(guī)范推導(dǎo)的逆過程—規(guī)范歸約，其可歸約串就是最左直接短語—句柄。7.1LR分析概述LR（k）分析法：1965年由Knuth提出(L、R、k)能力強(qiáng)幾乎所有CFG的語言結(jié)構(gòu)都能用LR分析，不需要對文法附加條件分析速度快、能準(zhǔn)確及時(shí)地指出出錯(cuò)位置難點(diǎn)工作量大，幾乎不可能用手工編寫實(shí)用語言文法的LR分析器現(xiàn)實(shí)有LR分析器的生成器本章介紹LR(0)SLR(1)LR(1)LALR(1)

理論基礎(chǔ)理論過渡最為嚴(yán)密實(shí)用7.1LR分析概述LR分析器的構(gòu)成總控程序（驅(qū)動程序）：對所有文法、所有LR分析器都相同分析表（核心）：包括ACTION表（動作表）和GOTO表（轉(zhuǎn)換表）兩部分，都可用二維數(shù)組表示。不同文法的LR分析表不同同一文法使用不同的LR分析方法時(shí)分析表也不同。分析棧：包括狀態(tài)棧和符號棧。7.1LR分析概述

分析器的總體結(jié)構(gòu)狀態(tài)/符號棧輸入緩沖區(qū)a1…ai…an#LR總控程序動作表action轉(zhuǎn)移表goto分析表SmSm-1………S1S0XmXm-1………X1#輸出7.1LR分析概述LR分析表（核心）ACTION表：告訴分析器，當(dāng)棧頂狀態(tài)為S,

當(dāng)前輸入符號是a時(shí)做什么ACTION[S,a]=Si

移進(jìn)a并在狀態(tài)棧棧頂放入新狀態(tài)i，輸入指針后移ACTION[S,a]=rj

按照第j條產(chǎn)生式（假設(shè)為A->，且||=n）進(jìn)行歸約（狀態(tài)棧和符號棧均出棧n個(gè)符號，假設(shè)新的狀態(tài)棧棧頂仍用S表示,

將S’=GOTO[S,A]和A分別進(jìn)入狀態(tài)棧和符號棧)ACTION[S,a]=acc分析成功，停止分析器工作ACTION[S,a]=error（空）GOTO表：GOTO[S,A]=S’，表示新棧頂狀態(tài)為S，歸約之后的非終結(jié)符為A時(shí)，要放到棧頂?shù)男聽顟B(tài)為S’7.1LR分析概述LR總控程序的工作過程：初始情況下，狀態(tài)0和#分別入狀態(tài)棧和符號棧;總控程序總是根據(jù)棧頂狀態(tài)和當(dāng)前輸入符號查分析表決定分析動作（移近or歸約）;重復(fù)上一步直至分析成功（acc）或出錯(cuò)(error)。對輸入串a(chǎn)bbcde#的LR分析過程：文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d步驟狀態(tài)棧符號棧輸入串ACTIONGOTO1234560#abbcde#S202#abbcde#S4024#abbcde#r23023#aAbcde#S60236#aAbcde#r33023#aAcde#S5對輸入串a(chǎn)bbcde#的LR分析過程：文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d步驟狀態(tài)棧符號棧輸入串ACTIONGOTO67891011023#aAcde#S50235#aAcde#S802358#aAcde#r4702357#aAcBe#S9023579#aAcBe#r1101#S#acc1)E–>E+T

2)E–>T

3)T–>(E)

4)T–>i對輸入串i+(i)#進(jìn)行分析對輸入串i+(i)#進(jìn)行分析步驟

狀態(tài)棧

符號棧

剩余輸入串

ACTIONGOTO10#i+(i)#s4204#i+(i)#r42302#T+(i)#r21401#E+(i)#s55015#E+(i)#s360153#E+(i)#s4701534#E+(i)#r42801532#E+(T)#r26901536#E+(E)#s710015367#E+(E)#r38110158#E+T#r111201#E#acc1)E–>E+T

2)E–>T

3)T–>(E)

4)T–>i7.2LR(0)分析問題：有了分析表，就可以對輸入串進(jìn)行分析，但分析表是怎么得來的？LR分析的基本思想？7.2LR(0)分析步驟符號棧輸入符號串動作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S911）#S#接受01acc3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r4710）#aAcBe#歸約(S→aAcBe)023579r11狀態(tài)棧ACTIONGOTOS=>aAcBe=>aAbcde=>aAbcde=>abbcdeLR分析過程為規(guī)范歸約過程文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d進(jìn)一步分析：分析棧中內(nèi)容

+剩余符號串=文法的一個(gè)規(guī)范句型分析棧中內(nèi)容為某一規(guī)范句型的前綴每次歸約時(shí)，句型的前部分(棧中的部分)都包含了當(dāng)前句型的句柄：規(guī)范句型的這種前部分串稱為可歸前綴形成可歸前綴之前包括可歸前綴在內(nèi)的所有規(guī)范句型的前綴稱為活前綴（ActivePrefix）ε,a,abε,a,aA,aAbε,a,aA,aAc,aAcdε,a,aA,aAc,aAcB,aAcBe步驟符號棧輸入符號串動作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S911）#S#接受01acc3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r4710）#aAcBe#歸約(S→aAcBe)023579r11狀態(tài)棧ACTIONGOTOS<=aAcBe<=aAbcde<=aAbcde<=abbcde活前綴的形式定義G=(VN,VT,P,S),若有S’βAωβαω,γ是βα的前綴,則稱γ是文法G的活前綴.其中S’是對原文法擴(kuò)充(S’S)增加的非終結(jié)符.目的是使S’不出現(xiàn)在任何產(chǎn)生式的右部.如有文法G：SSa,Sa

則拓廣文法G‘：S’

S,SSa,Sa*7.2LR(0)分析活前綴不會包含句柄右部的任何符號

因?yàn)橐坏┑竭_(dá)可歸前綴（形成句柄）即進(jìn)行歸約活前綴與句柄的關(guān)系不含句柄的任何符號A→.12

（如#a#aAc等）包含句柄的部分符號A→1.2

（如#aA#aAcB等）包含句柄A→12.（如#ab#aAb#aAcd#aAcBe）7.2LR(0)分析重新審視規(guī)范歸約過程（LR分析過程）是一個(gè)在棧中逐步產(chǎn)生并且識別活前綴及可歸前綴的過程設(shè)想：是否可構(gòu)造一個(gè)識別文法活前綴及可歸前綴的DFA，將文法的終結(jié)符和非終結(jié)符看成輸入符號，每當(dāng)一個(gè)符號進(jìn)棧就認(rèn)為識別了該符號，并進(jìn)行狀態(tài)轉(zhuǎn)換。當(dāng)識別到可歸前綴時(shí)，相當(dāng)于在棧中形成了句柄，認(rèn)為達(dá)到了識別句柄的終態(tài)。若能構(gòu)造一個(gè)識別文法所有活前綴的DFA，則可以其作為句型的識別機(jī)制。步驟符號棧輸入符號串動作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S911）#S#接受01acc3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r4710）#aAcBe#歸約(S→aAcBe)023579r11狀態(tài)棧ACTIONGOTOLR分析的基本思想對任何文法，活前綴集是正規(guī)集。7.2LR(0)分析仍以文法G[s]為例，先構(gòu)造識別文法活前綴的NFA：文法G[S]：

(0)S’→S(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d由于文法拓廣而增加的可歸前綴x5④⑧9①21430671011121615⒀1718⒆SaaaaAAAbccbdeB*ε,a,abε,a,aA,aAbε,a,aA,aAc,aAcdε,a,aA,aAc,aAcB,aAcBe7.2LR(0)分析NFA確定化得到識別文法活前綴的DFA對輸入串a(chǎn)bbcde#的識別過程3577.2LR(0)分析NFA確定化得到識別文法活前綴的DFA對輸入串a(chǎn)bbcde#的識別過程(對ab+cde#)驗(yàn)證成功！7.2LR(0)分析根據(jù)識別活前綴的DFA構(gòu)造LR(0)分析表文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d與前面給出的基本一致7.2LR(0)分析本節(jié)最開始的兩個(gè)問題初步得到解決LR分析表(狀態(tài))——由識別文法活前綴的DFA轉(zhuǎn)換而來、LR分析的基本思想——構(gòu)造識別文法活前綴的DFA但這個(gè)例子只是個(gè)巧合對于任何一個(gè)復(fù)雜文法，它的活前綴（可歸前綴）并不是如此簡單就能得到。7.2LR(0)分析構(gòu)造識別文法活前綴的DFA，有三種方法：計(jì)算文法活前綴及可歸前綴->構(gòu)造NFA->NFA確定化（了解）由文法產(chǎn)生式構(gòu)造識別文法活前綴的NFA->NFA確定化（了解）由文法產(chǎn)生式直接構(gòu)造識別文法活前綴的DFA

（掌握）7.2LR(0)分析出發(fā)點(diǎn)：從產(chǎn)生式出發(fā)構(gòu)造DFA為刻劃在分析過程中產(chǎn)生式的右部符號已有多大一部分被識別（出現(xiàn)在棧頂）的情況，分別用標(biāo)有圓點(diǎn)的產(chǎn)生式來指示位置。A→α．刻劃產(chǎn)生式A→α的右部α已出現(xiàn)在棧頂A→α1.α2

刻劃A→α1α2的右部子串α1已出現(xiàn)在棧頂，期待從輸入串中看到α2推出的符號A→.α

刻劃沒有句柄的任何符號在棧頂，此時(shí)期望A→α的右部所推出的符號串LR(0)項(xiàng)目/配置

7.2LR(0)分析LR(0)項(xiàng)目或配置（itemorconfiguration）對Axyz則有A.xyz

Ax.yz Axy.z Axyz.一個(gè)右部長度為n的產(chǎn)生式對應(yīng)n+1個(gè)LR(0)項(xiàng)目如：S→aAdS→.aAdS→a.AdS→aA.dS→aAd對于A→ε，LR(0)項(xiàng)目只有A→?

7.2LR(0)分析LR(0)項(xiàng)目分類：根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符，可把項(xiàng)目分為以下幾類：移進(jìn)項(xiàng)目，形如A→?aa是終結(jié)符,,V*待約項(xiàng)目，形如A→?B歸約項(xiàng)目，形如A→?

（?A→ε的LR(0)項(xiàng)目A→?

是歸約項(xiàng)目）接受項(xiàng)目，形如

S’→S?

構(gòu)造識別文法所有活前綴的NFA1.列出文法的所有LR(0)項(xiàng)目，每個(gè)項(xiàng)目作為一個(gè)狀態(tài)，S’->.S對應(yīng)初態(tài)。2.若狀態(tài)i為XX1

…Xi-1.Xi

…Xn

，狀態(tài)j為XX1

…Xi-1Xi

.Xi+1

…Xn

，則從狀態(tài)i畫一條標(biāo)志為Xi的有向邊到狀態(tài)j；3.若狀態(tài)i為X.A，A為非終結(jié)符，則從狀態(tài)i畫一條邊到所有狀態(tài)A.。把識別文法所有活前綴的NFA確定化7.2LR(0)分析

構(gòu)造識別文法活前綴的DFA-方法2文法G(S)：S→EE→aA|bBA→cA|dB→cB|d

該文法的項(xiàng)目有：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·7.2LR(0)分析

構(gòu)造識別文法活前綴的DFA-方法2識別活前綴的NFA1.S→·E2.S→E·

3.E→·aA4.E→a·A5.E→aA·

6.A→·cA7.A→c·A8.A→cA·

9.A→·d10.A→d·

11.E→·bB12.E→b·B13.E→bB·

14.B→·cB15.B→c·B16.B→cB·

17.B→·d18.B→d·134675891011121314151617182*EaAbBdBdcAc識別活前綴的DFA（與P129-130方法1結(jié)果相吻合）0:S→·EE→·aAE→·bB

4:A→c·AA→·cAA→·d

2:E→a·AA→·cAA→·d1:S→E·3:E→b·BB→·cBB→·d5:B→c·BB→·cBB→·d11:B→d·9:B→cB·7:E→bB·10:A→d·6:E→aA·8:A→cA·ccbEadAccdddBAB7.2LR(0)分析

構(gòu)造識別文法活前綴的DFA-方法30:S→·EE→·aAE→·bB

4:A→c·AA→·cAA→·d

2:E→a·AA→·cAA→·d1:S→E·3:E→b·BB→·cBB→·d5:B→c·BB→·cBB→·d11:B→d·9:B→cB·7:E→bB·10:A→d·6:E→aA·8:A→cA·ccbEadAccdddBAB觀察右側(cè)DFA發(fā)現(xiàn)：若項(xiàng)目A→·B在狀態(tài)i中，則所有形如B→·

的項(xiàng)目也都在i中。若項(xiàng)目A→·X在狀態(tài)i中，項(xiàng)目A→X·在狀態(tài)j中，則狀態(tài)j是狀態(tài)i關(guān)于X的后繼狀態(tài)。考慮：是否可以從產(chǎn)生式出發(fā)直接構(gòu)造識別文法活前綴的DFA?G’:S’→EE→aA∣bBA→cA|dB→cB|d7.2LR(0)分析

構(gòu)造識別文法活前綴的DFA-方法3從產(chǎn)生式出發(fā)，直接構(gòu)造識別文法活前綴的DFA構(gòu)成識別一個(gè)文法活前綴的DFA項(xiàng)目集（狀態(tài)）的全體，稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族。假定I是文法G的任一項(xiàng)目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：1.I的任何項(xiàng)目都屬于CLOSURE(I)；2.若A→·B屬于CLOSURE(I)，那么，對任何關(guān)于B的產(chǎn)生式B→，項(xiàng)目B→·也屬于CLOSURE(I)；

3.重復(fù)執(zhí)行上述兩步驟直至CLOSURE(I)不再增大為止。7.2LR(0)分析

構(gòu)造識別文法活前綴的DFA-方法3狀態(tài)轉(zhuǎn)換函數(shù)GO：I是一個(gè)項(xiàng)目集，X是一個(gè)文法符號，函數(shù)GO(I，X)定義為：GO(I，X)＝CLOSURE(J)

其中

J＝{任何形如A→X·的項(xiàng)目|A→·

X屬于I}。直觀上說，若I是識別某個(gè)活前綴

的項(xiàng)目集，那么，GO(I，X)便是識別X

的項(xiàng)目集。7.2LR(0)分析

構(gòu)造識別文法活前綴的DFA-方法3構(gòu)造文法G的拓廣文法G的LR(0)項(xiàng)目集規(guī)范族算法：PROCEDUREITEMSETS(G)；BEGIN C:={CLOSURE({S·S})}；

REPEAT FORC中每個(gè)項(xiàng)目集I和G的每個(gè)符號XDO IFGO(I，X)非空且不屬于CTHEN

把GO(I，X)放入C族中; UNTILC 不再增大END轉(zhuǎn)換函數(shù)GO把項(xiàng)目集連接成一個(gè)DFA轉(zhuǎn)換圖.7.2LR(0)分析

構(gòu)造識別文法活前綴的DFA-方法3文法的產(chǎn)生式有限，所以此過程必會在有限步驟內(nèi)結(jié)束！文法G(S)S→EE→aA|bBA→cA|dB→cB|dI0={S→·E,E→·aA,E→·bB}GO(I0,E)=closure(J)=closure({S’→E·}) ={S’→E·}=I1GO(I0,a)=closure(J)=closure({E→a·A}) ={E→a·A,A→·cA,A→·d})=I2GO(I0,b)=closure(J)=closure({E→b.B}) ={E→b.B,B→.cB,B→.d}=I30:S→·EE→·aAE→·bB

4:A→c·AA→·cAA→·dc5:B→c·BB→·cBB→·dc3:E→b·BB→·cBB→·db1:S→E·E2:E→a·AA→·cAA→·da11:B→d·d8:A→cA·Accd10:A→d·dd9:B→cB·B6:E→aA·A7:E→bB·B文法G(S)S→EE→aA|bBA→cA|dB→cB|d識別活前綴的DFA（與方法1結(jié)果相吻合）7.2LR(0)分析

構(gòu)造識別文法活前綴的DFA-方法3在構(gòu)造LR(0)項(xiàng)目集規(guī)范族的過程中，每一個(gè)新的項(xiàng)目集都是在某一個(gè)（或多個(gè)）項(xiàng)目的基礎(chǔ)上衍生出來的（閉包），我們把這樣的項(xiàng)目稱為核項(xiàng)目。圓點(diǎn)不在產(chǎn)生式右部最左端的項(xiàng)目稱為核，但開始狀態(tài)拓廣文法的第一個(gè)項(xiàng)目S·S除外。核可能由一個(gè)或若干個(gè)項(xiàng)目組成。用GO（I，X）轉(zhuǎn)換函數(shù)得到的J為轉(zhuǎn)向后狀態(tài)所含項(xiàng)目集的核7.2LR(0)分析假若一個(gè)文法G的拓廣文法G的LR(0)項(xiàng)目集規(guī)范族中不存在下述情況：

1)既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目

2)含有多個(gè)歸約項(xiàng)目則稱G是一個(gè)LR(0)文法。移進(jìn)—?dú)w約沖突

A->·aB->.歸約—?dú)w約沖突A->.B->.圖7.2LR(0)分析LR(0)分析表的構(gòu)造令每個(gè)項(xiàng)目集Ik的下標(biāo)k作為分析器的狀態(tài)，包含項(xiàng)目S→·S的集合Ik的下標(biāo)k為分析器的初態(tài)（0）。分析表的ACTION和GOTO子表構(gòu)造方法：1.若項(xiàng)目A→·a屬于Ik且GO(Ik,a)＝Ij，a為終結(jié)符，則置ACTION[k,a]為“sj”。2.若項(xiàng)目A→·屬于Ik，那么，對任何終結(jié)符a(或結(jié)束符#)，置ACTION[k,a]為“rj”(假定產(chǎn)生式A→是文法G的第j個(gè)產(chǎn)生式)。3.若項(xiàng)目S→S·屬于Ik，則置ACTION[k,#]為“acc”。4.若GO(Ik,A)＝Ij，A為非終結(jié)符，則置GOTO[k,A]=j。5.分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“報(bào)錯(cuò)標(biāo)志”。圖識別活前綴的DFA0:S→·EE→·aAE→·bB

4:A→c·AA→·cAA→·d

2:E→a·AA→·cAA→·d1:S→E·3:E→b·BB→·cBB→·d5:B→c·BB→·cBB→·d11:B→d·9:B→cB·7:E→bB·10:A→d·6:E→aA·8:A→cA·ccbEadAccdddBAB文法G(S)S→EE→aA|bB（1、2）A→cA|d（3、4）B→cB|d（5、6）表44ACTIONGOTOabcd#EAB01234567891011圖S2S3S4S10S5S11S4S10S5S11r1r1r1r1r1r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r6acc16879分析7.2LR(0)分析按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱它為文法G的一張LR(0)分析表。具有LR(0)分析表的文法G稱為一個(gè)LR(0)文法。LR(0)文法是無二義的。文法G是一個(gè)LR（0）文法文法G(S)S→EE→aA|bB（1、2）A→cA|d（3、4）B→cB|d（5、6）7.2LR(0)分析假若一個(gè)文法G的拓廣文法G的LR(0)項(xiàng)目集規(guī)范族中不存在下述情況：

1)既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目

2)含有多個(gè)歸約項(xiàng)目則稱G是一個(gè)LR(0)文法。沖突存在會使得分析表中有多重定義的元素，無法進(jìn)行確定的分析。移進(jìn)—?dú)w約沖突

A->·aB->.歸約—?dú)w約沖突A->.B->.例:對acccd#進(jìn)行分析步驟狀態(tài)棧

符號棧

剩余輸入串ActionGoto

1 0 # acccd#S2 2 02 #a cccd#S4 3 024 #ac ccd#S4 4 0244 #acc cd#S4 5 02444 #accc d#S10 6 0244410 #acccd #r48 7 024448 #acccA #r38 8 02448 #accA #r38 9 0248 #acA #r36 10 026 #aA #r11 11 01 #E #acc文法G(S)S→EE→aA|bB（1、2）A→cA|d（3、4）B→cB|d（5、6）7.2LR(0)分析表文法G:

S→BB

B→aB

B→bI0:S’→.SS→.BBB→.aBB→.b I1:S’→S.SBI2:S→B.BB→.aBB→.b

aI4:B→a.BB→.aBB→.b bI3:B→b.

BI5:S→BB.abBI6:B→aB.ab是LR(0)文法例分析表(練習(xí))

拓廣文法

0)Ｅ'→Ｅ

1)Ｅ→Ｅ+Ｔ

2)Ｅ→Ｔ

3)Ｔ→Ｔ*Ｆ

4)Ｔ→Ｆ

5)Ｆ→(Ｅ)6)Ｆ→iI0:E’→.EE→.E+TE→.TT→.T*FT→.FF→.(E)F→.iEI1:E’→E.E→E.+TTI2:E→T.T→T.*FFI3:T→F.(I4:F→(.E)E→.E+TE→.TT→.T*FT→.FF→.(E)F→.iidI5:F→i.+I6:E→E+.TT→.T*FT→.FF→.(E)F→.i*I7:T→T*.FF→.(E)F→.iEI8:F→(E.)E→E.+TTF(idTI9:E→E+T.T→T.*FF(idFI10:T→T*F.()I11:F→(E).+*id不是LR(0)文法I2:E→T.T→T.*FI9:E→E+T.T→T.*F7.2LR(0)分析結(jié)論上下文無關(guān)文法不是都能用LR(0)方法進(jìn)行分析的。也就是說，一個(gè)CFG不一定是一個(gè)LR(0)文法.實(shí)際上，大多數(shù)實(shí)用的程序設(shè)計(jì)語言的文法不能滿足LR(0)文法的條件（P137實(shí)型變量說明文法）。I3:SrD?DD?,i52<實(shí)型變量說明>real<標(biāo)識符表>

<標(biāo)識符表><標(biāo)識符表>,i

<標(biāo)識符表>iS’S [0]SrD [1]DD,i [2]Di [3]I0:S’?SS?rDI1:S’S?I2:Sr?DD?D,iD?iI5:DD,?iI6:DD,i?I4:Di?Srii,D7.3SLR(1)分析53存在的問題SrD? 此項(xiàng)目為歸約項(xiàng)目DD?,i 此項(xiàng)目為移進(jìn)項(xiàng)目若構(gòu)成分析表，則在3狀態(tài)中可見I3:SrD?DD?,iACTIONGOTOr,i#SD0S211acc2S433r1r1，S5r1r14r3r3r3r35S66r2r2r2r2LR(0)分析的局限性LR(0)：對歸約項(xiàng)目不管輸入符號是什么都作歸約動作，相當(dāng)于向前查看0個(gè)輸入符號。導(dǎo)致—多余歸約！有必要作這么多次歸約嗎？沒有那什么情況下對形如B·的歸約項(xiàng)目進(jìn)行歸約？面臨非終結(jié)符B的Follow集符號時(shí)進(jìn)行歸約?。?！55I3:SrD?DD?,iFOLLOW(S)={#}在狀態(tài)I3中面臨“，”移近面臨“#”歸約因此，應(yīng)修改LR(0)分析表如下S’S [0]SrD [1]DD,i [2]Di [3]56狀態(tài)ACTIONGOTOr,i#SD0S211acc2S433S5r14r3r3r3r35S66r2r2r2r2————SLR分析表————討論為什么SLR(1)用FOLLOW集作為歸約項(xiàng)目的歸約范圍？7.3SLR(1)分析通常，一個(gè)文法的LR(0)項(xiàng)目集規(guī)范族中可能含有多個(gè)移進(jìn)項(xiàng)目和多個(gè)歸約項(xiàng)目，不妨假設(shè)I={A1→·a11，A2→·a22，…，Am→·amm，B1→1·，B2→2

·，…，Bn→n

·}；只要滿足集合{a1，…，am}，F(xiàn)OLLOW(B1)，…，F(xiàn)OLLOW(Bn)兩兩不相交，則仍可：1.若a是某個(gè)ai，i=1,2,…,m，則移進(jìn)；2.若aFOLLOW(Bi)，i=1,2,…,n，則用產(chǎn)生式Bi→進(jìn)行歸約；3.此外，報(bào)錯(cuò)。如果一個(gè)文法的LR(0)項(xiàng)目集規(guī)范族中的沖突（或LR(0)分析表中的多重定義）可用上述方法解決，則稱這個(gè)文法是SLR(1)文法，相應(yīng)的分析表稱為SLR(1)分析表，所用的分析器稱為SLR(1)分析器。59判斷是否為SLR(1)文法I2中：

FOLLOW(E)∩{*}=I9中：

FOLLOW(E)∩{*}=故此文法為SLR(1)文法，可得下面的SLR(1)分析表I2:ET?TT?*FI9:EE+T?TT?*F[0]S’E[1]EE+T[2]ET[3]TT*F[4]TF[5]F(E)[6]FiFOLLOW(E)={#,+,)}I0:E’→.EE→.E+TE→.TT→.T*FT→.FF→.(E)F→.iEI1:E’→E.E→E.+TTI2:E→T.T→T.*FFI3:T→F.(I4:F→(.E)E→.E+TE→.TT→.T*FT→.FF→.(E)F→.iidI5:F→i.+I6:E→E+.TT→.T*FT→.FF→.(E)F→.i*I7:T→T*.FF→.(E)F→.iEI8:F→(E.)E→E.+TTF(idTI9:E→E+T.T→T.*FF(idFI10:T→T*F.()I11:F→(E).+*idI2:E→T.T→T.*FI9:E→E+T.T→T.*F表1表261狀態(tài)ACTIONGOTOi+*()#ETF01234567891011————SLR分析表————S4S5123S6accS7r2r2r2r4r4r4r4r4r4S4S5r6r6r6r6r6r6S4S582393S4S510S11S6S7r1r1r1r3r3r3r3r3r3r5r5r5r5r5r5改進(jìn)的SLR(1)分析：對所有歸約項(xiàng)目都采用向前查看FOLLOW集符號的方法設(shè)置歸約動作。改進(jìn)的SLR(1)分析表提前發(fā)現(xiàn)錯(cuò)誤（分析表中的空元素增多）63狀態(tài)ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r234S5S482356S5S4937S5S4108S6S119r1S7r1r11011r4r4r4r4r6r6r6r6r3r3r3r3r5r5r5r5輸入串i+i*i#的分析過程0)Ｅ'→Ｅ1)Ｅ→Ｅ+ＴＥ→Ｔ3)Ｔ→Ｔ*Ｆ4)Ｔ→ＦＦ→(Ｅ)Ｆ→iSLR(1)分析的實(shí)質(zhì)：去除LR(0)中的多余歸約，對含有沖突的項(xiàng)目集中的歸約項(xiàng)目采用向前查看一個(gè)輸入符號的方法試圖解決沖突。S：Simple（只考慮沖突項(xiàng)目集）1：向前查看一個(gè)輸入符號結(jié)論：SLR(1)文法肯定是無二義性的文法一個(gè)LR(0)文法肯定是一個(gè)SLR(1)文法，反之不一定成立問題SLR(1)是否完美？7.4LR(1)分析移進(jìn)-歸約沖突Action[5,c]=s9/r5移進(jìn)-歸約沖突Action[7,d]=s11/r5(0)S’->S(1)S->aAd(2)S->bAc(3)S->aec(4)S->bed(5)A->eFOLLOW(A)={c,d}7.4LR(1)分析(0)S’->S(1)S->aAd(2)S->bAc(3)S->aec(4)S->bed(5)A->eSLR(1)分析表FOLLOW(A)={c,d}不是LR(0)文法也不是SLR(1)文法7.4LR(1)分析問題：SLR(1)中是否還存在無效歸約？存在無效歸約(1)S->aAd(2)S->bAc(3)S->aec(4)S->bed(5)A->eFOLLOW(A)={c,d}7.4LR(1)分析分析:FOLLOW集合提供的信息太泛！（前例中歸約符號集實(shí)際上是FOLLOW集的真子集）問題：怎樣確定執(zhí)行歸約動作的當(dāng)前輸入符號集合？7.4LR(1)分析重新定義項(xiàng)目每個(gè)項(xiàng)目的一般形式是[A→·,a1a2…ak]，這樣的一個(gè)項(xiàng)目稱為一個(gè)LR(k)項(xiàng)目。項(xiàng)目中的a1a2…ak

稱為它的向前搜索符串(或展望串)。當(dāng)k=1時(shí)，形如[A→·,a]的項(xiàng)目被稱為LR(1)項(xiàng)目，a稱為向前搜索符。若A.BI，則B

.

I（B

是一產(chǎn)生式），把FIRST()中的符號作為用B

歸約的向前搜索符，用以代替SLR(1)中的FOLLOW集。原LR(0)項(xiàng)目S’->.S的向前搜索符為#，即有對應(yīng)的LR(1)項(xiàng)目[S’->.S,#]向前搜索符僅對歸約項(xiàng)目[A→·，a]有意義，在非歸約項(xiàng)目中只起傳遞作用。7.4LR(1)分析

—LR(1)項(xiàng)目集規(guī)范族的構(gòu)造closure(I)按如下方式構(gòu)造(1)I的任何項(xiàng)目屬closure(I)；(2)若[A→β1·

Bβ2，a]∈closure(I)，B→δ是一產(chǎn)生式，那么對于FIRST(β2a)中的每個(gè)終結(jié)符b，如果[B→．δ,b]不在closure(I)中，則把它加進(jìn)去；(3)重復(fù)（1）（2），直至closure(I)不再增大。GO函數(shù)若I是一個(gè)項(xiàng)目集，X是一個(gè)文法符號，則GO(I,X)=closure(J)，其中J={任何形如[A→αX．β,a]的項(xiàng)目∣[A→α.Xβ,a]∈I}LR(1)項(xiàng)目規(guī)范族C的構(gòu)造算法類同LR(0)的，只是初始時(shí)：

C={closure({[S’→·S,#]})};7.4LR(1)分析文法(0)S’->S(1)S->aAd(2)S->bAc(3)S->aec(4)S->bed(5)A->e的LR(1)項(xiàng)目集規(guī)范族I0:S`→．S,#S→．a(chǎn)Ad,#S→．bAc,#S→．a(chǎn)ec,#S→．bed,#I1:S`→S．,#SI2:S→a．Ad,#S→a．ec,#A→．e,daI3:S→b．Ac,#S→b．ed,#A→．e,cbI4:S→aA．d,#AI5:S→ae．c,#A→e．,deI9:S→aec．,#cI7:S→be．d,#A→e．,ceI11:S→bed．,#dI10:S→bAc．,#cI8:S→aAd．,#dI6:S→bA．c,#A7.4LR(1)分析構(gòu)造LR(1)分析表令每個(gè)Ik的下標(biāo)k為分析表的狀態(tài)，令含有[S→·S,#]的Ik的k為分析器的初態(tài)ACTION子表和GOTO子表構(gòu)造如下：1.若項(xiàng)目[A→·a,b]屬于Ik且GO(Ik,a)＝Ij，a為終結(jié)符，則置ACTION[k,a]為“sj”。2.若項(xiàng)目[A→·，a]屬于Ik，則置ACTION[k,a]為“rj”；其中假定A→為文法G的第j個(gè)產(chǎn)生式。3.若項(xiàng)目[S→S·,#]屬于Ik，則置ACTION[k,#]為“acc”。4.若GO(Ik，A)＝Ij，則置GOTO[k,A]=j。5.分析表中凡不能用規(guī)則1至4填入信息的空白欄均填上“出錯(cuò)標(biāo)志”。按上述算法構(gòu)造的分析表，若不存在多重定義的入口，則稱它為文法G的一張LR(1)分析表。具有LR(1)分析表的文法G稱為一個(gè)LR(1)文法。7.4LR(1)分析文法(0)S’->S(1)S->aAd(2)S->bAc(3)S->aec(4)S->bed(5)A->e的LR(1)分析表例拓廣文法G(S)(0)S→S (1)S→BB (2)B→aB(3)B→b7.4LR(1)分析LR(1)的項(xiàng)目集規(guī)范族I0:S’?S,#S?BB,#B?aB,a/bB?b,a/bSI1:S’S?,#BI2:SB?B,#B?aB,#B?b,#aI3:Ba?B,a/bB?aB,a/bB?b,a/bbI4:Bb?,a/bBI5:SBB?,#aI6:Ba?B,#B?aB,#B?b,#bI7:Bb?,#BI8:BaB?,a/babaI9:BaB?,#BbI0:S’?S,#S?BB,#B?aB,aB?aB,bB?b,aB?b,b(0)S→S (1)S→BB (2)B→aB(3)B→b(0)S→S (1)S→BB (2)B→aB(3)B→bLR(1)分析表LR(1)文法練習(xí)：寫出文法的I0項(xiàng)目集S’:=S#S:= L=R|RL:= *R|idR:= LS’:=S,#S:=L=R,#S:=R,#L:=*R,=/#L:=id,=/#R:=L,#I07.4LR(1)分析關(guān)于LR(1)LR(1)的分析能力強(qiáng)于SLR(1)（P150例）LR(0)

SLR(1)LR(1)無二義文法一個(gè)LR(0)文法肯定是一個(gè)SLR(1)文法，也必是一個(gè)LR(1)文法，反之不一定成立LR(1)狀態(tài)可能比SLR(1)/LR(0)多LR(1)的項(xiàng)目集規(guī)范族：10個(gè)項(xiàng)目集I0:S’?S,#S?BB,#B?aB,a/bB?b,a/bSI1:S’S?,#BI2:SB?B,#B?aB,#B?b,#aI3:Ba?B,a/bB?aB,a/bB?b,a/bbI4:Bb?,a/bBI5:SBB?,#aI6:Ba?B,#B?aB,#B?b,#bI7:Bb?,#BI8:BaB?,a/babaI9:BaB?,#BbLR(0)項(xiàng)目集規(guī)范族：7個(gè)項(xiàng)目集I0:S’.SS.BBB.aBB.bI1:S’S.I2:SB.BB.aBB.bI3:Ba.BB.aBB.bI4:BaB.I5:Bb.I6:SBB.(0)S→S (1)S→BB (2)B→aB(3)B→b同心集7.5LALR(1)分析同心集：如果兩個(gè)LR(1)項(xiàng)目集去掉搜索符之后是相同的，則稱這兩個(gè)項(xiàng)目集具有相同的心。同心集的分裂使得LR(1)項(xiàng)目集的個(gè)數(shù)急劇增加LR(1)方法分析能力很強(qiáng)，但是也耗費(fèi)大量存儲空間。在實(shí)際應(yīng)用中，還須簡化。7.5LALR(1)分析LALR分析法的基本思想：在LR(1)項(xiàng)目集規(guī)范族中，合并同心集以減少狀態(tài)的數(shù)目LALR(lookaheadLR)合并LR（1）項(xiàng)目集規(guī)范族的同心集I36I47I89（心不變，向前搜索符取合集）.I3:BaB,a/bBaB,a/bBb,a/bI6:BaB,#BaB,#Bb,#I4:Bb,a/bI7:Bb,#I8:BaB,a/bI9:BaB,#I36:BaB,a/b#BaB,a/b#Bb,a/b/#I47:Bb,a/b/#I89:BaB,a/b/#7.5LALR(1)分析構(gòu)造LALR(1)分析表1.構(gòu)造文法G的LR(1)項(xiàng)目集規(guī)范族.2.合并同心集的狀態(tài).3.新LALR(1)狀態(tài)的GO函數(shù)是合并的同心集狀態(tài)的GO函數(shù)的并（轉(zhuǎn)換函數(shù)自動合并）.4.LALR(1)分析表的ACTION和GOTO登錄方法與LR(1)分析表一樣.經(jīng)上述步驟構(gòu)造的表若不存在沖突，則稱它為G的LALR(1)分析表。存在這種分析表的文法稱為LALR（1）文法。7.5LALR(1)分析文法的LALR(1)分析表(0)S→S (1)S→BB (2)B→aB(3)B→b7.5LALR(1)分析合并同心集的幾點(diǎn)說明心不變，向前搜索符取合集，轉(zhuǎn)換函數(shù)自動合并LR(1)文法合并同心集后只可能出現(xiàn)歸約-歸約沖突，而不可能出現(xiàn)移進(jìn)-歸約沖突（見下頁）合并同心集之后可能推遲錯(cuò)誤發(fā)現(xiàn)的時(shí)間，但錯(cuò)誤的定位仍是準(zhǔn)確的(見后)7.5LALR(1)分析設(shè)某LR(1）文法中，項(xiàng)目集Ik和Ij為同心集，其中Ik為：[A->α.,u1][B->β.aγ,b]Ij為：[A->α.,u2][B->β.aγ,c]可知u1∩{a}=?，u2∩{a}=?則{u1∪

u2}∩{a}=?合并同心集后Ikj為：[A->α.,u1/u2][B->β.aγ,b/c]向前搜索符集合{u1∪

u2}與待移進(jìn)符號集合{a}交集為空，所以不可能有移進(jìn)-歸約沖突，但有可能有歸約-歸約沖突（原同心集中含有多個(gè)歸約項(xiàng)目的情況）。7.5LALR(1)分析關(guān)于錯(cuò)誤發(fā)現(xiàn)7.5LALR(1)分析LALR(1)會推遲錯(cuò)誤的發(fā)現(xiàn)，但對錯(cuò)誤的定位仍然是準(zhǔn)確的。7.5LALR(1)分析結(jié)論LALR(1)文法是無二義的一個(gè)文法若是LALR(1)文法，一定也是LR(1)文法LR(1)分析法強(qiáng)于LALR(1)分析法，而LALR(1)分析法強(qiáng)于SLR(1)分析法。(P150-151)7.5LALR(1)分析7.6二義文法的應(yīng)用二義文法肯定不是LR類文法（P153表達(dá)式文法）通過加限制（規(guī)定運(yùn)算符的優(yōu)先級和結(jié)合性）來化解沖突，可以構(gòu)造出比相應(yīng)的非二義性文法更優(yōu)越的LR分析器（P155表7.18VS.P142表7.9）例：優(yōu)先級化解沖突E-> E*E| E+E| idS’->E#E->E*EE->E+EE->idS’->E