lr分析的四種分析方法優缺點

㈠ LR分析法的LR(1)分析表的構造

前面所介紹的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)文法。