LR分析法的LR 0 分析表的構造

2021-09-07 14:02:49 字數 4838 閱讀 1481

1樓:泥凡邇

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

為了給出構造lr分析表的演算法,我們首先需要引入一些非常重要的概念和術語。 由例4?6對輸入串「a,b,a」的分析過程容易看出,如果所分析的輸入串沒有語法錯誤,則在分析的每一步,若將分析棧中已移進和歸約出的全部文法符號與餘留的輸入符號串拼接起來,就形成了所給文法的一個規範句型。

換言之,也就是在分析的每一步,如輸入串已被掃視的部分無語法錯誤,則當前分析棧中的全部文法符號應當是某一規範句型的字首。而且還不難看出,此種規範句型的字首決不會含有控制代碼右邊的任何符號,這是因為一旦句型的控制代碼在棧的頂部形成,將會立即被歸約之故。以後,我們將把規範句型具有上述性質 (即不含控制代碼之右的任何符號)的字首稱為它的活字首。

例如,對於文法g[l]的規範句型「e,b,a」 (見表412分析過程第5步),其控制代碼為「b」,棧中的符號串為「e,b」,此句型的活字首為ε,「e」,「e,」,「e,b」等。

由此可見,一個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)專案,將是構造識別其全部活字首的有限自動機的基礎。

在作出文法的全部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的過程,可用一個對其基本專案集的閉包運算,即closure()來表示。一般地,設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()=

i2=go(i0,a)=closure()=

i3=go(i0,b)=closure()=

i4=go(i0,a)=closure()=

i5=go(i0,c)=closure()=

i6=go(i0,d)=closure()=

請注意,由於i0中無圓點在b之前的專案,故go(i0,b)無定義。這樣,我們求出了i0的全部後繼專案集i1,i2,i3,i4,i5,i6。容易看出,由於i1,i2,i3,i5,i6諸專案集中的專案均無後繼專案,因此它們都沒有後繼狀態。

對於專案集i4,我們再仿此求出它的後繼狀態,這些後繼狀態是:

i7=go(i4,a)=closure()=

i9=go(i4,b)=closure()=

此外,由於

go(i4,a)=i4go(i4,c)=i5go(i4,d)=i6

故它們均不產生新的專案集。最後,再求出i7,i9的後繼專案集。它們分別是

i8=go(i7,b)=closure()=

i10=go(i9,b)=closure()=

由於i8和i10已無後繼專案集,所以至此我們已求出所給文法g[s]的全部專案集i0~i10,通常,我們將這些專案集的全體稱為文法g[s]的lr(0)專案集規範族,並記為

c=於是,我們所要構造的識別文法g[s]全部活字首的dfa為

m=(c,v,go,i0,c)

其中: m的狀態集也就是文法的lr(0)專案集規範族c=;

m的字母表也就是文法的字彙表v=;

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) 在分析表中,凡不能按上述規則填入資訊的元素,均置為「出錯」。

swot分析法在哪本書裡,SWOT分析法的步驟

企業人力資源管理叢書 績效管理 中有。運用這種方法,可以對研究物件所處的情景進行全面 系統 準確的研究,從而根據研究結果制定相應的發展戰略 計劃以及對策等。s strengths 是優勢 w weaknesses 是劣勢,o opportunities 是機會 t threats 是威脅。按照企業競...

用分析法證明若a0則根號a

題目 高考 用分析法證明 若a 0,則a 2 1 a 2 2 a 1 a 2.證明 要證a 2 1 a 2 2 a 1 a 2.只要證a 2 1 a 2 2 a 1 a 2.也即 a 1 a 2 a 1 a 2 令a 1 a t,則不等式轉化為t 2 t 2 0,其中a 1 a t 2 a 1 a ...

關於LR單刷厄運的問題100分送上(不是高手不要進)

死心吧 bug已經修改了,現在只能老老實實去刷了 bug早修復了 哈哈哈,可憐的100分 我好些月沒玩了,聽說是這樣的.要找一個ss,綁個石頭給你.殺完國王對話.再死掉.跑進來就沒怪殺你了 你這100分打水漂兒了.這個bug目前已經被遮蔽掉了,不能夠再使用 哈哈 真是的 bug沒有用拉。獵人單刷厄運...