LR分析法

LR分析是當前最一般的分析方法。它對文法的限制最少，現今能用上下文無關文法描述的程式設計語言一般均可用LR方法進行有效的分析。

基本介紹

• 中文名：LR分析法
• 時間：1965年
• 性質：從左至右掃描和自底向上
• 屬性：產生式左部符號

分析法介紹

1965年，D.Knuth首先提出了LR(K)文法及LR(K)分析技術。所謂LR(K)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據分析棧當前已移進和歸約出的全部文法符號，並至多再向前查看K個輸入符號，就能確定相對於某一產生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應採取的分析動作 (是移進還是按某一產生式進行歸約等)。

LR分析是當前最一般的分析方法。這是因為它對文法的限制最少，現今能用上下文無關文法描述的程式設計語言一般均可用LR方法進行有效的分析，而且在分析的效率上也不比諸如不帶回溯的自頂向下分析、一般的“移進歸約”以及算符優先等分析方法遜色。此外，LR分析器在工作過程中，還能準確及時地發現輸入符號串的語法錯誤。凡此種種，就使LR分析方法在國際上受到了廣泛的重視。

對於LR(K)文法的理論研究業已證明：① 每一LR(K)文法都是無二義性文法；② 一個由LR(K)文法所產生的語言也可由某一LR(1)文法產生。同時，由於通常的程式設計語言一般均能由LR(1)文法來產生。因此，對程式設計語言的編譯來說，我們可僅考慮k≤1，即LR(0)和LR(1)的情況。

下面，我們首先介紹LR分析器的邏輯結構及工作原理，接著再依次介紹LR(0)，SLR(1)，LR(1)及LALR(1)等四種LR分析器的構造方法。其中，LR(0)分析器的分析能力最低，但它是構造其餘三種LR分析器的基礎。SLR是“簡單LR”分析的縮寫，它是為了解決構造LR(0)分析器所出現的問題而形成的一種方法，其分析能力自然要比LR(0)分析器稍強一些。

LR(1)分析器的分析能力是四種LR分析器中的最強者，但對規模較大的文法來說，在具體構造分析器時，由於所需的工作量及要求的存儲空間都很龐大，將會遇到很大的困難。為此，採用所謂向前LR分析器即LALR(1)分析器將是一種恰當的選擇。LALR(1)分析器的能力介於SLR(1)和LR(1)之間，但其分析表的規模比LR(1)分析表要小得多。至於工作量的問題，則可通過開發和使用LR分析器的自動生成工具來解決。目前十分流行的語法分析器自動生成工具YACC和OCCS正是為自動生成LALR(1)分析器而研製的。

結構及原理

在邏輯上，一個LR分析器有一個輸入符號串，一個下推分析棧，以及一個總控程式和分析表。LR分析器在總控程式的控制下自左至右掃視輸入串的各個符號，並根據當前分析棧中所存放之文法符號的狀況及正注視的輸入符號，按分析表的指示完成相應的分析動作。在分析的每一時刻，分析棧中記錄了迄今為止所移進或歸約出的全部文法符號，即記錄了從分析開始到目前為止的整個歷程。

因此，為了方便，對於分析過程的每一步，我們可將分析棧中所存放的全部文法符號用一種“狀態”來刻畫，且將此狀態名置於分析棧的棧頂所示。分析剛開始時，棧中僅有一個句子的左界符#，此時分析器處於初始狀態S0，它不僅刻畫了分析棧中當前僅有一個符號#這一事實，而且還預示著即將掃視的輸入符號應當是可作為句子首符號的那些符號。類似地，狀態S1刻畫了分析棧中已有符號#X1的情況，…，棧頂狀態Sm則刻畫了分析棧中已存在符號串#X1X2…Xm的情況，等等。此外，根據分析棧的棧頂狀態，還可對當前可能遇到的輸入符號進行預測。例如，對於前面所述的文法G[E]，設分析棧中已移進和歸約出的符號串為#E+T時的棧頂狀態為Si，則Si不僅表征了迄今掃描過的輸入串部分已被歸約成#E+T，而且由Si還可以作這樣的預測： 若輸入符號串無語法錯誤，則當前可遇到的輸入符號僅能是+,*,)或#。

顯然，在棧頂狀態為上述Si的情況下，若當前所掃視到的符號為*，則應將*移進棧中；當所掃視到的符號為+,)或#時，則應將E+T歸約為E；若所掃視到的符號不是上述四種符號之一，則應按語法錯誤處理。由此可見，知道了棧頂狀態Sm和正掃視到的輸入符號ai，就知道了當前所需的全部有用信息，從而也就可惟一地確定當前LR分析器所應採取的動作。所以，在具體實現時，並不需要將文法符號記入分析棧中。

LR分析器的核心是一張分析表，它由兩個子表組成： 其一是分析動作表；另一個為狀態轉移表。其中： S1,S2,…,Sn為分析器的各個狀態；a1,a2,…,al為文法的全部終結符號和句子界符；X1,X2,…,Xp為文法字彙表中的全部文法符號。分析動作表中的每一個元素ACTION[Sm,ai]指明，當棧頂狀態為Sm且正掃視的輸入符號為ai時要完成的分析動作。狀態轉移表中的元素GOTO[Sm,Xi]則指明，當向分析棧中移進一個輸入符號或按某一產生式進行歸約之後所要轉移到的下一狀態。

LR分析器的工作在總控程式的控制下進行，其過程如下 (為書寫方便，我們將分析棧按順時針旋轉90度)：

1?分析開始時，首先將初始狀態S0及句子左界符#推入分析棧。

2?設在分析的某一步，分析棧和餘留輸入符號串處於如下格局：

S0S1S2…S↓m[]#X1X2…Xma↓iai+1…an#

則用當前棧頂的狀態Sm及正掃視的輸入符號ai組成符號對(Sm,ai)去查分析動作表，並根據分析表元素ACTION[Sm,ai]的指示採取相應的分析動作，每一分析表元素所指示的僅能是下列四種動作之一：

(1) 若ACTION[Sm,ai]=“移進”，則表明句柄尚未在棧頂部形成，正期待繼續移進輸入符號以形成句柄，故將當前的輸入符號ai推入棧中，即

S0 S1 S2 … S↓m[]# X1 X2 … Xm aia↓i+1ai+2…an#

然後，以符號對(Sm,ai)查狀態轉移表，設相應的表元素GOTO[Sm,ai]=Sm+1，再將此新的狀態Sm+1 (即要轉移到的下一狀態)推入棧中，則有如下格局：

S0 S1 S2 … Sm S↓m+1[]# X1 X2 … Xm aia↓i+1ai+2…an#

(2) 若ACTION[Sm,ai]=rj，其中rj意指按文法的第j個產生式A→Xm-r+1Xm-r+2…Xm進行歸約。這表明棧頂部的符號串Xm-r+1Xm-r+2…Xm已是當前句型 (對非終結符號A)的句柄。按第j個產生式進行歸約，也就是將分析棧從頂向下的r個符號 (因為該產生式右部符號串的長度為r)退出，然後再將文法符號A推入棧中，此時分析棧的格局為

S0 S1 S2 … S↓m-r[]# X1 X2 … Xm-r Aa↓iai+1…an#

然後再以(Sm-r,A)查狀態轉移表，設GOTO[Sm-r,A]=SK，將此新狀態推入棧中，則有如下的格局：

S0S1S2…Sm-rS↓K[]#X1X2…Xm-rAa↓iai+1…an#

必須注意的是，當完成歸約動作之後，輸入串指示器不向前推進，它仍然指向動作前的位置。

(3) 若ACTION[Sm,ai]=“接受”則表明當前的輸入串已被成功地分析完畢，應中止分析器的工作。

(4) 若ACTION[Sm,ai]=ERROR，則表明當前的輸入串中有語法錯誤，此時應調用出錯處理程式進行處理。

3?重複步驟2的工作，直到在分析的某一步，棧頂出現“接受狀態”為止。此時，分析棧的最終格局應為

S0S↓z[]#Z#↓

其中，Z為文法的開始符號，Sz則為使ACTION[Sz,#]=“接受”的惟一狀態 (即接受狀態)。

上述所列的三個步驟，實質上是對LR分析器總控程式的一個非形式化的描述，它對任何不同的LR分析表都是適用的。順便提及，LR分析器的輸出是在用某個產生式進行歸約之後，通過執行相應的語義子程式來實現的，我們將在第5章再討論這一問題。

分析表構造

顧名思義，LR(0)分析就是LR(K)分析當K=0的情況，亦即在分析的每一步，只要根據當前的棧頂狀態 (或者說根據當前分析棧中已移進或歸約出的全部文法符號)就能確定應採取何種分析動作，而無須向前查看輸入符號。

為了給出構造LR分析表的算法，我們首先需要引入一些非常重要的概念和術語。

活前綴

(viable prefix)

由例4?6對輸入串“a,b,a”的分析過程容易看出，如果所分析的輸入串沒有語法錯誤，則在分析的每一步，若將分析棧中已移進和歸約出的全部文法符號與餘留的輸入符號串拼接起來，就形成了所給文法的一個規範句型。換言之，也就是在分析的每一步，如輸入串已被掃視的部分無語法錯誤，則當前分析棧中的全部文法符號應當是某一規範句型的前綴。而且還不難看出，此種規範句型的前綴決不會含有句柄右邊的任何符號，這是因為一旦句型的句柄在棧的頂部形成，將會立即被歸約之故。以後，我們將把規範句型具有上述性質 (即不含句柄之右的任何符號)的前綴稱為它的活前綴。例如，對於文法G[L]的規範句型“E,b,a” (見表412分析過程第5步)，其句柄為“b”，棧中的符號串為“E，b”，此句型的活前綴為ε，“E”，“E，”，“E,b”等。

由此可見，一個LR分析器的工作過程，實質上也就是一個逐步產生 (或識別)所給文法的規範句型之活前綴的過程。同時，在分析的每一步，分析棧中的全部文法符號 (如果輸入串無語法錯誤)應是當前規範句型的活前綴，並且與此時的棧頂狀態相關聯。因此，我們自然會想到，如果能構造一個識別所給文法的所有活前綴的有限自動機，那么就能很方便地構造出相應的LR分析表來。稍後我們將討論這一問題。

LR項目

上面我們已經說過，在一個規範句型的活前綴中決不含有句柄右邊的任何符號。因此，活前綴與句柄的關係不外下述三種情況：

(1) 其中已含有句柄的全部符號 (句柄的最右符號即為活前綴的最右符號)；

(2) 其中只含句柄的一部分符號 (句柄開頭的若干符號與活前綴最右的若干個符號一致)；

(3) 其中全然不含有句柄的任何符號。

第一種情況表明，此時某一產生式A→β的右部符號串β已出現在棧頂，因此相應的分析動作應是用此產生式進行歸約。第二種情況意味著形如A→β1β2的產生式的右部子串β1已出現於棧頂，正期待著從餘留輸入串中看到能由β2推出的符號串。而第三種情況則意味著期望從餘留輸入串中能看到由某一產生式A→α的右部，即α所推出的符號串。為了刻畫在分析過程中，文法的一個產生式右部符號串已有多大一部分被識別，我們可在該產生式的右部的某處加上一個圓點“·”來指示位置。例如，對於上述三種情況，標有圓點的產生式分別為A→β·，A→β1·β2以及A→·α。我們把右部某位置上標有圓點的產生式稱為相應文法的一個LR(0)項目。特別，對形如A→ε的產生式，相應的LR(0)項目為A→·。顯然，不同的LR(0)項目反映了分析過程中棧頂的不同情況。下面我們就會看到，文法的全部LR(0)項目，將是構造識別其全部活前綴的有限自動機的基礎。

識別活前綴

DFA

在作出文法的全部LR(0)項目之後，現在用它們來構造識別全部活前綴的DFA。這種DFA的每一個狀態由若干個LK(0)項目所組成的集合 (稱為項目集)來表示。下面以例4?7所給出的文法為例來說明構造此種DFA的方法。

首先，我們用I0表示這個DFA的初態，它預示著分析過程的開始，並且期待著將給定的輸入符號串逐步歸約為文法的開始符號S′。或者反過來說，我們所期待的是，從使用產生式S′→S開始，能夠逐步推導出所給的輸入符號串。因此，我們應將項目S′→·S列入狀態I0中。換言之，也就是我們期待著將要掃視的輸入串正好就是能由S推出的任何終結符號串。然而，由於不能從輸入串中直接讀出非終結符號S，因此我們也應當把項目S→·A以及S→·B列入到I0中。由於A和B同樣是非終結符號，所以又應當將A→·aAb，A→·c和B→·aBb，B→·d列入I0中。由於最後列入I0的項目中，圓點之後都是終結符號，故I0已經“封閉”，構造項目集I0宣告結束。這樣，表示初態的項目集I0由如下的項目組成：

I0: S′→·SS→·AA→·aAb

S→·BB→·aBbB→·d

A→·c

我們將項目S′→·S稱為項目集I0的基本項目。上述從項目S′→·S出發構造項目集I0的過程，可用一個對其基本項目集{S′→·S}的閉包運算，即CLOSURE({S′→·S})來表示。一般地，設I為一項目集，則構造I的閉包CLOSURE(I)的算法如下：

(1) I中每一項目都屬於CLOSURE(I)；

(2) 若形如A→α·Xβ的項目屬於CLOSURE(I)，且X為非終結符號，則文法中任何X產生式的一切圓點在最左邊的項目X→·γ也都屬於CLOSURE(I)；

(3) 重複上述過程，直至不再有新的項目加入CLOSURE(I)為止。

有了初態I0之後，我們來說明如何確定從I0可能轉移到的下一個狀態。設X為一個文法符號 (終結符號或非終結符號)，若I0中有圓點位於X左邊的項目A→α·Xβ (其中α可以為ε)，則當分析器從輸入串識別出 (即移進或歸約出)文法符號X後，分析器將進入它的下一個狀態。設此狀態為Ii，顯然Ii中必含有全部形如A→αX·β的項目，我們將這樣的項目稱為A→α·Xβ的後繼項目。對於每一文法符號X，如果存在這樣的後繼項目，則可能不止一個，設其組成的集合為J,J中的每個項目也就是項目集Ii的基本項目。因此，按照與上面構造項目集I0相類似的討論，我們就有

Ii=CLOSURE(J)

為了指明Ii是“I0關於文法符號X的後繼狀態”這一事實，我們可定義一個狀態轉移函式

GO(I,X)=CLOSURE(J)

其中，I為當前狀態，X為文法符號，J為I中所有形如A→α·Xβ的項目的後繼項目所組成的集合，而CLOSURE(J)就是項目集I (即狀態I)關於X的後繼項目集 (即後繼狀態)。例如，對於上例，我們有：

I1=GO(I0,S)=CLOSURE({S′→S·})={S′→S·}

I2=GO(I0,A)=CLOSURE({S→A·})={S→A·}

I3=GO(I0,B)=CLOSURE({S→B·})={S→B·}

I4=GO(I0,a)=CLOSURE({A→a·Ab,B→a·Bb})=

{A→a·Ab, B→a·Bb, A→·aAb, B→·aBb, A→·c, B→·d}

I5=GO(I0,c)=CLOSURE({A→c·})={A→c·}

I6=GO(I0,d)=CLOSURE({B→d·})={B→d·}

請注意，由於I0中無圓點在b之前的項目，故GO(I0,b)無定義。這樣，我們求出了I0的全部後繼項目集I1,I2,I3,I4,I5,I6。容易看出，由於I1,I2,I3,I5,I6諸項目集中的項目均無後繼項目，因此它們都沒有後繼狀態。對於項目集I4，我們再仿此求出它的後繼狀態，這些後繼狀態是：

I7=GO(I4,A)=CLOSURE({A→aA·b})={A→aA·b}

I9=GO(I4,B)=CLOSURE({B→aB·b})={B→aB·b}

此外，由於

GO(I4,a)=I4GO(I4,c)=I5GO(I4,d)=I6

故它們均不產生新的項目集。最後，再求出I7,I9的後繼項目集。它們分別是

I8=GO(I7,b)=CLOSURE({A→aAb·})={A→aAb·}

I10=GO(I9,b)=CLOSURE({B→aBb·})={B→aBb·}

由於I8和I10已無後繼項目集，所以至此我們已求出所給文法G[S]的全部項目集I0~I10，通常，我們將這些項目集的全體稱為文法G[S]的LR(0)項目集規範族，並記為

C={I0,I1,I2,I3,…,I10}

於是，我們所要構造的識別文法G[S]全部活前綴的DFA為

M=(C,V,GO,I0,C)

其中： M的狀態集也就是文法的LR(0)項目集規範族C={I0,I1,…,I10}；

M的字母表也就是文法的字彙表V={S′，S，A，B，a,b,c,d}；

M的映像也就是如上定義的狀態轉換函式GO；

M的終態集也是C，這表明M的每一狀態都是它的終態。

對於上述文法G[S]，如上構造的識別其全部活前綴的DFA的狀態轉換圖如圖416所示。

由於狀態轉換圖416中的每一個狀態都是終態，因此在上述DFA工作的過程中，從初態I0齣發，沿著有向邊所指示的方向前進，可以使DFA在所經歷的任何狀態上中止它的工作。當DFA到達某一狀態時，我們把從初態I0齣發，到達該狀態所經過的全部有向邊上的標記符號依次連線起來，就得到了DFA在到達該狀態時，所識別出的某規範句型的一個活前綴。例如：當上述DFA處於初態I0時，它所識別的活前綴為ε；當M處於狀態I3時，它所識別的活前綴為B；當M處於I4時，它所識別的活前綴為aa*；而達到I9時，它所識別的活前綴為aa*B等等。需要注意的是，對那些只含有歸約項目的項目集，即M的I1,I2,I3,I5,I6,I8和I10，當M到達這些狀態時，表明活前綴中已含有相應句柄的全部符號 (即句柄已在棧頂形成)，因此，我們將這些狀態稱為句柄識別狀態。特別是當M處於狀態I1時，M所識別的活前綴為S，這意味著已將所給的輸入串歸約為S，如果再按產生式S′→S歸約一步，就得到了拓廣文法G′的開始符號S′。因此，我們將狀態I1稱為“接受狀態”，它預示著對輸入串的分析已成功地完成。

對於一個給定文法G的拓廣文法G′，當識別它的全部活前綴的DFA作出之後，我們就可據此構造相應的LR(0)分析表了。然而，應當首先注意的是，用前述方法所構造的每一個LR(0)項目集，實質上表征了在分析過程中可能出現的一種分析狀態；再根據前面對LR(0)項目的分類，項目集中的每一個項目又與某一種分析動作相關聯，因此，我們自然會提出這樣的要求，即每一項目集中的諸項目應當是相容的。所謂相容，是指在一個項目集中，不出現這樣的情況：

(1) 移進項目和歸約項目並存；

(2) 多個歸約項目並存。

如果一個文法G滿足上述條件，也就是它的每個LR(0)項目集中都不含衝突項目，則稱G為LR(0)文法。顯然，只有當一個文法是LR(0)文法時，才能構造出不含衝突動作的LR(0)分析表來。

從前面的討論和分析，我們將不難得出構造LR(0)分析表的算法。為方便起見，我們用整數0，1，2，…表示狀態I0,I1,…，而且如表411那樣，也將GOTO子表中有關終結符號的各列併入ACTION子表相應的各列中去，此外，算法中形如sj和rj等記號的含義同前，此算法如下：

(1) 對於每個項目集Ii中形如A→α·Xβ的項目，若GO(Ii,X)=Ij，且X為一終結符號a時，置ACTION[i,a]=sj。但若X為非終結符號時，則僅置GOTO[i,X]=j。

(2) 若歸約項目A→α·屬於Ii，設A→α為文法的第j個產生式，則對文法的任何終結符號或句子的右界符# (將它們統一地記為a)，置ACTION[i,a]=rj。

(3) 若接受項目S′→S·屬於Ii，則置ACTION[i,#]=acc。

(4) 在分析表中，凡不能按上述規則填入信息的元素，均置為“出錯”。

SLR構造

在前面討論LR(0)分析表的構造算法時，我們曾經指出，僅當一個文法G是LR(0)文法時，才能對它構造出無衝突動作的LR(0)分析表。然而，對於通常的程式設計語言來說，它們一般都不能用LR(0)文法來描述。例如，考慮如下“簡單分程式”的文法G[B′]：

0? B′→B3? D→d

1? B→bD;Se4? S→s;S

2? D→D;d5? S→s

相應識別其全部活前綴的DFA及LR(0)分析表如圖417及表414所示。由於在項目集I8中，既含有移進項目[S→s·;S]，又含有歸約項目[S→s·]，因而反映到分析表中就出現了具有多重定義的元素ACTION[8,′；′]={s10,r5}，前者指明當輸入符號為“；”時應將它移進棧中，而後者則要求按第5個產生式S→s進行歸約。於是就出現了有“移進歸約”衝突的分析動作。又如，對於通常用來描述簡單表達式的文法G[E]，當構造它的項目集規範族時，也會出現類似的情況。這就表明，這兩個文法都不是LR(0)文法。然而，儘管如此，對大多數程式設計語言來說，這種具有衝突項目的項目集，在整個項目集規範族中所占的比例畢竟是很小的。因此，如果我們能設法解決出現在一個項目集中的“移進歸約”或“歸約歸約”衝突，那么，只要對前述構造LR(0)分析表的算法稍加修改，它仍能適用於我們現在討論的情況。

表414G[B′]的LR(0)分析表

b[]d[]；[]s[]e[]#[]B[]D[]S0[]s2[8]11[7]acc2[3]s4[9]33[4]s54[]r3[]r3[]r3[]r3[]r3[]r35[][]s7[][]s8[10]66[6]s97[]r2[]r2[]r2[]r2[]r2[]r28[]r5[]r5[]r5,s10[]r5[]r5[]r59[]r1[]r1[]r1[]r1[]r1[]r110[5]s8[10]1111[]r4[]r4[]r4[]r4[]r4[]r4

仔細分析上述構造LR(0)分析表的算法容易看出，使分析表中出現多重定義分析動作的原因在於其中的規則(2)，即對於每一項目集Ii中的歸約項目A→α·，不管當前的輸入符號是什麼，都把ACTION子表相應於Ii那一行 (即第i行)的各個元素指定為rj，其中j是產生式A→α的編號。因此，如果該項目集Ii中同時還含有形如B→α·bβ或C→α·的項目，則在分析表的第i行中，必然會出現多重定義的元素。

由此可見，對於含有衝突的項目集

Ii={B→α·bβ，A→α·，C→α·}

在構造分析表時，如果能根據不同的向前符號a，將Ii中各項目所對應的分析動作加以區分，那么就有可能使衝突得到解決。為此，對於文法中的非終結符號U，我們定義集合

FOLLOW(U)={a|S′#?*…Ua…, a∈VT∪{#}}

即FOLLOW(U)是由所有含U的句型中，直接跟在U後的終結符號或#組成的集合。現對上述項目集Ii，考察FOLLOW(A)，FOLLOW(C)及{b}，若它們兩兩不相交，則可採用下面的方法，對Ii中各個項目所對應的分析動作加以區分。

對任何輸入符號a：

(1) 當a=b時，置ACTION[i,b]=“移進”；

(2) 當a∈FOLLOW(A)時，置ACTION[i,a]={按產生式A→α歸約}；

(3) 當a∈FOLLOW(C)時，置ACTION[i,a]={按產生式C→α歸約}；

(4) 當a不屬於上述三種情況之一時，置ACTION[i,a]=“ERROR”。

一般地，若一個項目集I含有多個移進項目和歸約項目，例如

I={A1→α·a1β1, A2→α·a2β2，…，Am→α·amβm, B1→α·, B2→α·, …, Bn→α·}

則當集合{a1,a2,…,am}，FOLLOW(B1),FOLLOW(B2)，…,FOLLOW(Bn)兩兩不相交時，可類似地根據不同的向前符號，對狀態為i時的衝突動作進行區分。

上述用來解決分析動作衝突的方法稱為SLR(1)規則。此規則是由F?DeRemer於1971年提出的。

有了SLR(1)規則之後，只須對前述構造LR(0)分析表的算法中的規則(2)作如下的修改：“(2)′若歸約項目A→α·屬於Ii，設A→α為文法的第j個產生式，則對於任何屬於FOLLOW(A)的輸入符號a，置ACTION[i,a]=rj”，且其餘的規則仍保持不變，就得到了構造SLR(1)分析表的算法。

對於給定的文法G，若按上述算法構造的分析表不含多重定義的元素，則稱文法G為SLR(1)文法。例如，對於上面的文法G[B′]，它的項目集

I8={S→s·; S,S→s·}

含有衝突的項目，但由於FOLLOW(S)={e}≠{;}，故衝突可用SLR(1)規則解決，與上述項目相應的分析動作分別是：

ACTION[8,;]=s10ACTION[8,e]=r5

此外，再注意到FOLLOW(B′)=FOLLOW(B)={#}和FOLLOW(D)={;}，則按上述算法為G[B′]所構造的SLR(1)分析表b[]d[];[]s[]e[]#[]B[]D[]S0[]s2[8]11[7]acc2[3]s4[9]33[4]s54[4]r35[3]s7[][]s8[10]66[6]s97[4]r28[4]s10[][]r59[7]r110[5]s8[10]1111[6]r4

LR構造

前面所介紹的SLR(1)分析法是一種較實用的方法。其優點是狀態數目少，造表算法簡單，大多數程式設計語言基本上都可用SLR(1)文法來描述。然而，也的確存在這樣的文法，其項目集的“移進歸約”衝突不可能通過SLR(1)規則得到解決。試看下面的例子。

例4?8考察文法G[S′]=({S′,S,A,B,C,D}, {a,b},,P,S′)其中，P由如下的產生式組成：

0? S′→S4?B→C

1?S→CbBA5?B→Db

2?A→Aab6?C→a

3?A→ab7?D→a

識別此文法的全部活前綴的DFA見圖418。其中項目集I10={S→CbBA·,A→A·ab}存在“移進歸約”衝突，但因FOLLOW(S)={#}，故上述衝突可通過SLR(1)規則得到解決。然而，在項目集I8={C→a·,D→a·}中，由於FOLLOW(C)={a,b}，FOLLOW(D)={b}，即FOLLOW(C)∩FOLLOW(D)≠?，故用SLR(1)規則解決上述“歸約歸約”衝突無效。而且還可驗證，對於任何K>0，上述文法也是非SLR(k)的，故不能通過任何SLR(k)規則使項目集I8中的“歸約歸約”衝突得到解決 [2]。因此，我們需要更強的LR分析法，即LR(1)分析方法來解決這一問題。

對SLR(1)規則稍作分析即可發現，它對某些文法失效的原因，在於當所給的文法出現衝突的分析動作時，SLR(1)規則僅孤立地考察輸入符號是否屬於與歸約項目A→α·相關聯的集合FOLLOW(A)，以確定是否應按產生式A→α進行歸約，而沒有考察符號串α所在規範句型的“環境”，即沒有考察α在規範句型中的“上下文”，這就具有一定的片面性。因為一旦α出現在分析棧的頂部 (設分析棧當前所存放的符號串為#δα)，且當前的輸入符號a也屬於FOLLOW(A)，就貿然將α歸約為A，此時分析棧中的符號串將變成#δA，但若文法中並不存在以δAa為前綴的規範句型，那么，這種歸約無效。例如，對於上述文法中的規範句型Cbabab，當分析達到格局

I0I2I4I8[]#Cbabab(4?50)

時，如果僅根據當前輸入符號b∈FOLLOW(C)，就將棧頂符號a按產生式C→a歸約為C，則有如下的格局：

I0I2I4I6[]#CbCbab

但在該文法中，根本不存在以CbCb為前綴的規範句型，因此在執行下一動作將b移進之前，分析器將報告“出錯”。由此可見，在分析過程中，當試圖用某一產生式A→α歸約棧頂符號串α時，不僅應查看棧中符號串δα，還應向前掃視一輸入符號a (我們將a稱為向前搜尋符號)，只有當δAa的確構成文法某一規範句型的前綴時，才能用此產生式進行歸約。為了指明上述事實，應當在原來的每一LR(0)項目[A→α·β]中放置一個向前搜尋符號a，使之成為[A→α·β,a]的形式，我們將此種項目稱為一個LR(1)項目。同時，為了使分析的每一步都能在棧中得到一個規範句型的活前綴，還應要求每一個LR(1)項目對相應的活前綴都是有效的 (其定義在下面給出)。此外，為了克服分析動作的衝突，在必要時，我們還可將某些項目集進行分解，以便使每一個狀態都能確切地指明： 當α已出現在棧頂，且面臨哪些輸入符號時，才能按產生式A→α將α歸約為A。

所謂一個LR(1)項目[A→α·β，a]對活前綴γ=δα有效，是指存在規範推導

S?*δAy?δαβyy∈V*T

且滿足下列條件：

(1) 當y≠ε時，a是y的首符號；

(2) 當y=ε時，a=#。

例如，對於例4?8所給文法，因有

S?CbBA?CbBab?CbDbab

其中，δ=Cb,α=D,β=b,y=ab,A=B，故LR(1)項目[B→D·b,a]對活前綴γ=CbD有效。又因

S?*CbDbab?Cbabab

其中，δ=Cb,A=D,α=a,β=ε,y=bab,故LR(1)項目[D→a·,b]對活前綴γ=Cba有效。由此也可看出，當分析器所處的格局為式(4?50)時，應當將棧頂符號a歸為D，而不應將它歸約為C。

與LR(0)文法的情況相類似，識別文法全部活前綴的DFA的每一個狀態也是用一個LR(1)項目集來表示，而每一個項目集又是由若干個對相應活前綴有效的LR(1)項目組成。為了構造LR(1)項目集族，我們同樣需要用到兩個函式，即CLOSURE(I)及GO(I，X)。

對每一LR(1)項目集I，相應的CLOSURE(I)的定義如下：

(1) I中的任何LR(1)項目都屬於CLOSURE(I)。

(2) 設項目[A→α·Bβ，a]∈CLOSURE(I)，並假設它對活前綴γ=δα有效，則對文法中所有形如B→η的產生式和每一個b∈FIRST(βa)，形如[B→·η,b]的全部項目也都對γ有效，故若[B→·η,b]原不在CLOSURE(I)中，則應將其放入。事實上，因為[A→α·Bβ，a]對γ=δα有效，則由定義我們有：

s?*δAy?δαBβyy∈V*T

且a∈FIRST(y)∪{#}，故可將上面的推導寫成

S?*δAy?δαBβaωω∈V*T∪{#}

現設文法已經過化簡，故不論β是否為ε，從βaω總能推出終結符號串，於是可假定

βaω?*bω′

又因a≠ε，有FIRST(βaω)=FIRST(βa)，從而就得到推導

S?*δαBbω′

由此可見，一切形如[B→·η,b]的項目也對活前綴γ=δα有效。

(3) 重複步驟(2)直到沒有新的項目加入為止。

至於函式GO(I，X)，其中I為一LR(1)項目集，X為某一文法符號，與LR(0)文法類似，我們也將它定義為：

GO(I,X)=CLOSURE(J)

其中J是由這樣的一些LR(1)項目組成： 對I中所有圓點在X左邊形如[A→α·Xβ,a]的項目，其後繼項目[A→αX·β,a]∈J。注意，每一LR(1)項目與其後繼項目有相同的向前搜尋符號。

有了上述CLOSURE(I)和GO(I，X)的定義之後，採用與LR(0)類似的方法，可構造出所給文法G的LR(1)項目集族C及狀態轉換圖。例如，對於上述文法，其LR(1)項目集及狀態轉換圖如圖419所示。

對於給定的文法G，當相應的LR(1)項目集族C及GO函式構造出來之後，便可按如下的算法構造它的LR(1)分析表：

(1) 對於每個項目集Ii中形如[A→α·Xβ,b]的項目，若GO(Ii,X)=Ij，且當X為一終結符號a時，置ACTION[i,a]=sj。但若X為一非終結符號時，則置GOTO[i,X]=j。

(2) 若歸約項目[A→α·,a]∈Ii，A→α為文法的第j個產生式，則置ACTION[i,a]=rj。

(3) 若項目[S′→S·,#]∈Ii，則置ACTION[i,#]=acc。

(4) 在分析表中，凡不能照上述規則填入信息的元素，均置為“出錯”。

對於一個文法G來說，若按上述算法所構造的分析表不含有多重定義的元素，則稱此分析表為G的LR(1)分析表。凡具有LR(1)分析表的文法稱為LR(1)文法。例如，上述文法的LR(1)分析表見表416，所以它是一個LR(1)文法。

LALR構造

上述每個LR(1)項目均由兩部分組成： 第一部分是一個LR(0)項目，稱為LR(1)項目的核；第二部分則是一個向前搜尋符號集。對於移進項目而言，搜尋符號對分析表的構造無影響；但對歸約項目而言，則僅在當前輸入符號屬於該搜尋符號集時，才能用相應的產生式進行歸約。LR(1)分析表的這種機理，較圓滿地解決了SLR(1)分析所難以解決的某些“移進歸約”或“歸約歸約”衝突，從而使LR(1)的分析能力比SLR(1)分析有明顯的提高。然而，LR(1)分析的主要缺點在於，對同一個文法而言，LR(1)分析表的規模將遠遠大於相應的SLR(1)或LR(0)分析表。例如，為一個C語言構造LR(0)分析表，一般大約設定300個狀態即可，而構造LR(1)分析表則需上千個狀態，即後者將導致時間和記憶體空間開銷的急劇上升。因此，就有必要尋求一種其分析表的規模與SLR(1)相當，但其分析能力又不比LR(1)相差太大的LR分析方法，這就是下面我們要介紹的LALR(1)分析技術。

下面，我們首先對造成LR(1)項目集族規模大幅度上升的原因進行分析，然後再設法從中找出構造高效LR分析表 (即LALR(1)分析表)的方法。為此，試看下面的例子。

再考察文法G[E]：

0?S→E4?T→F

1?E→E+T5?F→(E)

2?E→T6?F→ID

3?T→T*F

利用上面所給算法，為G[E]構造的LR(1)項目集族和識別活前綴的DFA如圖420(a)，(b)所示 (請注意，由於圖幅較大，這裡將其劃分為(a)，(b)兩部分)。對比這兩幅圖我們立即就會發現，除其中的狀態0和狀態3之外，對於(a)中的每一狀態 (LR(1)項目集)，在(b)中都有一個狀態 (LR(1)項目集)與其相似。例如，比較狀態7和16：在這兩個項目集中，除搜尋符號集不同外，各個LR(1)項目的核都彼此相同 (即產生式相同，且產生式中圓點的位置也相同)，我們把具有這種特點的兩個LR(1)項目集稱為同心集。所以，在圖420(a)和(b)中，7/16，5/12，10/17，4/13，8/18，2/14，11/19，6/20，1/15和9/21都是同心集。顯然，在LR(0)分析器中，每個“心”僅對應一個LR(0)項目集；但在LR(1)分析器中，由於向前搜尋符號的不同，同一個“心”將會派生出多個同心集。這就是對同一文法而言，LR(1)項目集族遠大於LR(0)項目集規範族的原因。

7E→E+·T[]#+T→·T*F

T→·F

F→·(E)

F→·ID〖〗#+*

#+*

#+*

#+*[][]16E→E+·T[]+)T→·T*F

T→·F

F→·(E)

F→·ID〖〗+)*

+)*

+)*

+)*

為解決上述問題，F?DeRemer提出了LALR(1)分析法。這種方法的基本思想是將LR(1)項目集族中的同心項目集加以合併，以削減項目集的個數。所謂合併同心集，實際上也就是將其中的每個LR(1)項目的向前搜尋符集對應地合併在一起。例如，對於文法G[E]的同心項目集4和13，設合併後的新項目集為4/13，則有

4E→T·

T→T·*F〖〗#+

#+*[][]13E→T·

T→T·*F〖〗+)

+)*[][]4/13E→T·

T→T·*F〖〗#+)

#+)*

由於同心集的合併，對原來識別活前綴的DFA也須作相應的修改。

對於LALR(1)項目集族，我們須著重指出如下幾點：

(1) 合併同心集也就是將同心集中每個LR(1)項目的兩個組成部分 (核及向前搜尋符號集)分別、對應地合併在一起。設I1,I2,…,Im為同心項目集，J是合併之後的新的項目集，顯然J與Ii同心；再設X∈V∪{#}，則GO(I1,X),GO(I2,X)，…，GO(Im,X)也必然同心，若把這m個同心項目集合併後的新項目集記為K，則有GOTO(J，X)=K。可見前面定義的GOTO函式在這裡仍然適用。

(2) 儘管原來各LR(1)項目集均不存在衝突，但合併同心集後就有可能出現衝突。換言之，即LR(1)文法未必總是LALR(1)文法。不過，由此引入的衝突只能是“歸約歸約”衝突，而決不會是“移進歸約”衝突。事實上，設原LR(1)項目集族中有如下兩個項目集

Ik：

[A→α·，W1]

[B→β·aγ,b]Ij:

[A→α·,W2]

[B→β·aγ，c]

並設Ik與Ij均無衝突，故有

W1∩{a}=?W2∩{a}=?

從而

(W1∪W2)∩{a}=?

現將Ik與Ij合併，有

Ik/j:

[A→α·,W1∪W2]

[B→β·aγ，{b}∪{c}]

若此時Ik/j有“移進歸約”衝突，則必有

(W1∪W2)∩{a}≠?

這就與Ik與Ij無衝突的假設相矛盾。因此，合併同心集不會引入新的“移進歸約”衝突。

(3) 對同一個語法上正確的輸入符號串而言，不論用LALR(1)分析表還是用LR(1)分析表進行分析，所經歷的移進、歸約序列總是相同的 (僅狀態名可能不同)。然而，當輸入符號串有錯時，LALR分析器可能會比LR(1)分析器多進行幾步歸約才能報錯，但決不會比LR分析器多移進輸入符號。也就是說，LALR分析器雖然可能延遲了發現出錯的時間，但對錯誤的準確定位不產生影響。

(4) LALR(1)項目集族總是與同一文法的SLR(1)項目集族有同樣個數的項目集。但是構造LALR項目集族的開銷比SLR大。實現LALR分析對文法的要求比LR(1)嚴、比SLR(1)寬，但開銷遠小於LR(1)。權衡利弊的結果，LALR堪稱為當前實現自底向上語法分析，特別是構造分析器自動生成工具的最為適用的技術。

綜上所述，可給出構造LALR(1)分析表的算法如下。

1? 對已給的拓廣文法G′，構造相應的LR(1)項目集族C={I0,I1,…,In}。

2? 對於C，將各LR(1)項目集按同心關係進行分組，並將同組的同心集加以合併，設所得的新項目集族為C′={J0,J1,…,Jm}，其中含有項目[S′→·S,#]的項目集對應於初態。

3? 若C′中的項目集含有衝突項目，則G′不是LALR(1)文法。否則，可按如下法則構造LALR(1)分析表：

(1) 用構造LR(1)分析表類似的方法構造ACTION表；

(2) 對於某個X∈VN，若有GO(Jk,X)=Jt，則置GOTO(k,X)=t。

上述通過構造LR(1)項目集族和合併同心集來構造LALR分析表的方式僅有理論意義而無實用價值。因為構造完整的LR(1)項目集族的時間和空間開銷都很大，故應首先設法予以解決。

迄今已有多種高效構造LALR分析表的算法，其共同的特點都是不從直接構造完整的LR(1)項目集入手，而是通過構造LR(0)項目集並添加相應的向前搜尋符號來形成LALR(1)項目集 (請注意，對同一個文法而言，LALR(1)項目集與同心的LR(0)項目集一一對應)。例如，OCCS/YACC構造LALR(1)項目集所採用的策略是，每當創建一新的項目集時，就檢查目前是否已存在與之同心的項目集，若有這樣的項目集，則只需將向前搜尋符號加入其中，而不再建立新的項目集。一種更為有效的方法甚至無需構造完整的LALR(1)項目集，而僅通過各個項目集中的“核心項目”便能構造相應的LALR(1)分析表。這裡所說的核心項目是指形如[S′→·S，#]的項目 (其中，S′→S是拓廣文法的第1個產生式)，或者是形如[A→α·Xβ,a]的項目 (其中，α≠ε，即圓點不出現在產生式右部的最左位置)，亦即那些用於構造本項目集閉包的“基本項目”。例如，對於文法G[E]，各項目集的核心項目如圖422所示。

下面，我們對利用項目集的核心項目構造LALR分析表的原理進行說明。

ACTION

構造ACTION表的關鍵在於確定“歸約”和“移進”兩種動作。

(1) 歸約動作的確定

由核心項目的定義可知，任何歸約項目都必然會出現在某個項目集的核心項目之中，現設項目集I的核心為K，若[A→α·,a]∈K (其中α≠ε，搜尋符號如何配置下面再介紹)，我們立即可以確定： 在當前狀態下所面臨的輸入符號為a時，應按產生式A→α進行歸約，即有

ACTION[I,a]=rj

若α=ε，則若且唯若

[B→γ·Cδ， b]∈KC?*[]rAη

且a∈FIRST(ηδb)時，才能確定面臨輸入符號a時用產生式A→ε進行歸約。由於對任何C∈VN，滿足C?*[]rAη的所有非終結符號A預先能完全確定，故項目集I所引發的歸約動作，僅由其核心K即能完全確定。

(2) 移進動作的確定

若

[A→α·Xβ,b]∈KX?*[]raη(a∈VT)

且上述推導的最後一步未使用ε產生式，則可確定： 狀態I面臨輸入符號a時的動作為“移進”。其中，終結符號a可通過預先計算FIRST(X)加以確定。

GOTO

對於任何項目[B→γ·Xδ,b]∈K，相應的項目[B→γX·δ,b]顯然必屬於某個項目集J=GO(I，X)的核心L。另外，若

[B→γ·Cδ,b]∈KC?*[]rAη

且A→Xβ是文法中的一個產生式，則對於任何

a∈FIRST(ηδb)[A→X·β,a]∈L

由於對每一對非終結符號(C，A)，是否存在關係C?*[]rAη，可採用類似於計算FIRST集的方法預先求出，故僅從I的核心同樣可構造出GOTO表。

配置

上面的討論，是在假定每個核心項目都已配置了搜尋符號的情況下進行的。現在，再回頭討論： 如何為每個LR(0)項目集的核心項目配置搜尋符號，使之成為LALR項目集的核心項目。為此，我們首先考察搜尋符號從項目集I傳播到項目集GO(I，X)的規律。

再設項目集I的核心為K，若有

[B→γ·Cδ,b]∈KC?*[]rAη

且A→Xβ是文法中的一個產生式，則根據上面的討論有

[A→X·β,a]∈La∈FIRST(ηδb)

其中L是項目集J的核心，且J=GO(I,X)。現分如下兩種情況討論搜尋符號a和b間的關係。

(1) 當ηδ?*ε時，顯然也有[A→X·β,b]∈L。此時，我們就說項目[A→X·β,b]中的搜尋符號b是從項目[B→γ·Cδ,b]中傳遞過來的 (propagate)。

(2) 當ηδ不能推導出ε時，a僅取決於η或δ，而與b無關，此時我們就說搜尋符號a是自生的 (spotaneous)。

無論a是傳遞的還是自生的，它總能根據項目[B→γ·Cδ,b]中的有關信息，通過上述計算獲得，這便是搜尋符號從項目集I傳播到項目集J的規律。

其次，在同一項目集中，核心項目中的搜尋符號向非核心項目傳播的規律與上述規律極為相似。事實上，設[B→γ·Cδ,b]∈K，而C→α是文法中的一個產生式，則[C→·α，c]是I的一個非核心項目。其中，搜尋符c∈FIRST(δb)，且按如下方法確定： 若δ不能推出ε，則c是自生的；否則，c=b，即c是從上面的項目傳遞下來的。

類似地，也可討論搜尋符號在非核心項目間的傳播規律。例如，對於文法G[E]，從核心項目[S→·E，#]開始，向前搜尋符號在I0中的傳遞和自生的情況如圖423所示。

設K是LR(0)項目集I的核心，X是某個文法符號，則對GO(I，X)的核心中的每一項目A→αX·β，通過程式47描述的操作 (請注意，這裡使用了一個虛擬搜尋符號lookahead)，可由I中的項目確定其全部自生的搜尋符號，並能確定K中的哪些項目將其搜尋符號傳遞給GO(I，X)中的項目A→αX·β。

程式47確定自生搜尋符號和傳遞搜尋符號的項目

for (K中的每個項目B→γ·δ)

{

J′=CLOSURE ([B→γ·δ,lookahead]);

/*計算GO函式之值 */

for (J′中的每一項目[A→α·Xβ,a])

{

if(a!=lookahead)

確定GO(I，X)核心項目[A→αX·β,a]

之搜尋符號a是自生的

if(a==lookahead)

確定GO(I，X)核心項目[A→αX·β，a]之搜尋符號a是從K中項目

B→γ·δ傳遞過來的；

}

}

最後，我們再考慮如何給每個LR(0)項目集的核心中的各個項目都配置一個搜尋符號集，以獲得各個LALR(1)項目集的核心。完成此項任務的大致過程如下。

(1) 為拓廣文法G′構造全部LR(0)項目集的核心。

(2) 首先從初始項目集I0惟一的核心項目S′→·S (其搜尋符號顯然為#)開始，對每個LR(0)項目集的核心和每個文法符號X，利用上面的算法，確定GO(I，X)各核心項目的自生搜尋符號集，並確定從I的哪些項目將搜尋符號傳遞到GO(I，X)的核心項目。

(3) 按某種便於操作的結構，建立一張核心項目表，此項目表記錄了每個項目集的各個核心項目及其相應的搜尋符號集。開始時，這些搜尋符號集僅是由第(2)步所確定的自生搜尋符號集 (若該核心項目無自生向前搜尋符號則為空)。

(4) 傳遞每個核心項目中的自生搜尋符號，直到無法再進行傳遞為止。即反覆掃視各項目集的每個核心項目，每當訪問一個核心項目i時，便根據第(2)步所獲的信息，將i當前要傳遞的搜尋符號添加到承接它的那個核心項目之中，直至沒有新的搜尋符號要傳遞為止。

對一個給定的文法G而言，當它的各個LALR(1)項目集的核心構造出來之後，就能根據上面所描述的原理，為G構造相應的LALR(1)分析表。不過，儘管上述構造LALR分析表的方法效率較高，但對於常見的程式設計語言，企圖用手工的方式來建立LALR分析表仍幾乎是不可能的。所幸的是，目前已有一些自動生成LALR分析表的工具可資使用(如YACC)。

還應當指出，在構造LR語法分析器時，尚有若干技術問題需予以考慮，如二義性文法的處理，避免按單產生式的歸約，等等。前者我們將在第5章介紹語法分析器自動生成工具時再進行討論；至於後者，由於需涉及一些語義處理及其信息傳遞的細節，故就不再討論了。

在結束本章時，我們還要給出如下的結論，這些結論的證明讀者可參閱有關的文獻(1，2，8，15)。

(1) 任何LR(K)，LL(K)及簡單優先文法類都是無二義性的；對於算符優先文法，如果不考慮歸約所得非終結符號的名字，也可認為是無二義性的。

(2) 任何二義性的文法都不可能是LR(1)(或LL(1))文法，但可藉助於其它因素，如算符的優先權和結合規則以及某些語義解釋等等，來構造無衝突的分析表。

(3) 每個SLR(K)文法都是LR(K)文法，但卻存在這樣的LR(1)文法，它對任何K而言均不是SLR(K)文法。

各類文法之間的關係