語法分析-自底向上分析.ppt

1、第5章 語法分析自底向上分析,在自底向上的分析方法中，分析過程從輸入符號串開始，通過反復(fù)查找當(dāng)前句型的句柄，并使用規(guī)則，將找到的句柄歸約成相應(yīng)的非終結(jié)符號，直到歸約到開始符號。,5.1 規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約 規(guī)范推導(dǎo)就是最右推導(dǎo)，而通過規(guī)范推導(dǎo)能得到的句型就是規(guī)范句型。規(guī)范歸約也稱為最左歸約，是規(guī)范推導(dǎo)的逆過程，即在分析的每一步，將當(dāng)前句型的句柄歸約成相應(yīng)的非終結(jié)符號。,5.1 規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約,從符號串開始，向上歸約，如果最終能夠規(guī)約到文法的開始符號S，則同樣可以說明該輸入符號串是這個文法的句子。其歸約過程如圖5.1所示。,例 5.1有文法GS： S:=aAcBe A:=

2、b A:=Ab B:=d 分析符號串a(chǎn)bbcde是否為該文法的句子。,解：首先，我們從文法的開始符號進(jìn)行規(guī)范推導(dǎo)，依次使用1、4、3、2規(guī)則，就可得到符號串a(chǎn)bbcde。規(guī)范推導(dǎo)過程如下： S =aAcBe =aAcde =aAbcde =abbcde,5.2自底向上分析方法的一般過程,自底向上分析方法，也稱為移進(jìn)歸約法，其過程是：設(shè)置一個寄存符號的先進(jìn)后出棧，稱為符號棧。在分析進(jìn)行時，把輸入符號逐個按掃描順序移進(jìn)棧里，當(dāng)棧頂符號串形成句柄(即為某條規(guī)則的右部)時，就歸約，把棧頂構(gòu)成句柄的那個符號串用相應(yīng)規(guī)則左部的非終結(jié)符號來代替。再檢查棧頂是否又出現(xiàn)了新的句柄，若有，繼續(xù)歸約；若沒有形成新的

3、句柄，則再從輸入符號串移進(jìn)新的符號，如此繼續(xù)直到整個輸入符號串處理完畢。最終如果棧里只有識別符號，則所分析的輸入符號串為合法的句子，報告成功；否則，輸入串是不合法的符號串，報告錯誤。,表5.1輸入串a(chǎn)bbcde的分析過程,上述分析可看出，每次歸約的句柄都出現(xiàn)在符號棧的棧頂，不會出現(xiàn)在棧的中間，因為算法是自左向右掃描輸入符號串，進(jìn)行的是最左歸約。,例 5.1有文法GS： S:=aAcBe A:=b A:=Ab B:=d 分析符號串a(chǎn)bbcde是否為該文法的句子。,5.2自底向上分析方法的一般過程,存在著句柄識別問題 :例如表5.1中的第5步，棧內(nèi)符號串為aAb，由于文法中同時有規(guī)則A:=Ab和A

4、:=b，那么，符號串Ab和b都是某規(guī)則的右部，都可以作為句柄歸約。如果選擇b作為句柄歸約成A，那么，最終就達(dá)不到歸約到開始符號S的目的。事實上，不能因為規(guī)則A:=b就斷定b是句柄，因為aAAcde并不是一個句型，即不存在推導(dǎo)過程S=*aAAcde。對句型aAbcde來說，其簡單短語是Ab和d，其中Ab是最左簡單短語，所以是句柄。,從自底向上分析的一般過程可看出，如何尋找或確定一個句型的句柄，是構(gòu)造一個自左向右掃描、自底向上分析方法必須要解決的一個關(guān)鍵問題。最常用的自底向上的分析方法有算符優(yōu)先方法和LR分析方法，算符優(yōu)先方法僅適用于算符文法，而LR分析方法應(yīng)用比較普遍。,5.3 LR分析方法,在

5、自底向上的分析中，當(dāng)一串貌似句柄的符號串出現(xiàn)在棧頂時，用什么方法來判定它是否為一個真正的句柄呢？這里我們介紹LR(K)分析技術(shù)。 LR(K)分析方法的L表示從左到右掃描所給定的輸入串，R表示以相反的方向構(gòu)造該輸入串的最右推導(dǎo)(即規(guī)范推導(dǎo))。K表示為了做出分析決定需要向前看的輸入符號的個數(shù)。LR分析方法對文法適應(yīng)性強(qiáng)，分析能力強(qiáng)，對源程序中錯誤的診斷靈敏，但結(jié)構(gòu)比前面介紹的自頂向下的分析方法復(fù)雜，向前查看的符號愈多，相應(yīng)的分析方法愈復(fù)雜。LR(0)分析器是LR分析方法中最簡單的一種，在確定分析動作時，不需要向前查看任何符號。這種分析器分析能力較弱，實用性差，但它是構(gòu)造其它更復(fù)雜的LR分析器的基礎(chǔ)

6、 。,5.3.1 LR分析器邏輯結(jié)構(gòu),LR分析器有一個給定的輸入符號串，一個分析棧和一個有窮的控制系統(tǒng)。如圖5.2所示。,輸入符號串,分析棧：,有窮的控制系統(tǒng)： 分析表(動作、轉(zhuǎn)換) 總控程序,其中，輸入符號串就是等待分析的符號串。分析棧有兩部分：一個是符號棧，另一個是狀態(tài)棧，它們都是先進(jìn)后出棧。而控制系統(tǒng)包括一個分析表和一個總控程序。對于不同的文法來說，分析表各有不同，但總控程序都是一樣的。LR分析器的工作過程就是在總控程序的控制下，從左到右掃描輸入符號串，根據(jù)分析棧中的符號和狀態(tài)以及當(dāng)前的輸入符號，查閱分析表并按分析表的指示完成相應(yīng)的分析動作，直到符號棧中出現(xiàn)開始符號。,圖5.2 LR分析

7、器的模型,5.3.2 LR分析表的構(gòu)成,LR分析表是LR分析器的核心部分，它由兩部分組成，一是動作部分ACTION表，二是狀態(tài)轉(zhuǎn)換部分GOTO表。表中S1、S2、Sn為分析器的各個狀態(tài)；a1、a2、am為文法的全部終結(jié)符號及右界符#；X1、X2、Xk為文法的非終結(jié)符號。,表5.2 LR分析表,分析表的動作部分， Si所在行與aj所在列對應(yīng)單元ACTIONSi，aj表示當(dāng)分析狀態(tài)棧的棧頂為Si，輸入符號為aj時應(yīng)執(zhí)行的動作；而在分析表的狀態(tài)轉(zhuǎn)換部分，Si行Xj列對應(yīng)的單元GOTOSi，Xj表示當(dāng)前狀態(tài)Si下符號棧頂為非終結(jié)符號Xj后應(yīng)移入狀態(tài)棧的狀態(tài)。,5.3.2 LR分析表的構(gòu)成,分析表的動作

8、有下列四種： 移進(jìn)(Sn)：將輸入符號aj移進(jìn)符號棧，將狀態(tài)n移進(jìn)狀態(tài)棧，輸入指針指向下一個輸入符號。 歸約(R)：當(dāng)棧頂形成句柄時，按照相應(yīng)的產(chǎn)生式UW進(jìn)行歸約。若產(chǎn)生式右部W的長度為n，則將符號棧棧頂n個符號和狀態(tài)棧棧頂n個狀態(tài)出棧，然后將歸約后的文法符號U移入符號棧，并根據(jù)此時狀態(tài)棧頂?shù)臓顟B(tài)Si及符號棧頂?shù)姆朥，查GOTO標(biāo)，將GOTOSi，U移入狀態(tài)棧。 接受(A)：當(dāng)輸入符號串到達(dá)右界符#時，且符號棧只有文法的開始符號時，則分析成功結(jié)束，接受輸入符號串并結(jié)束分析。 報錯(E)：在狀態(tài)棧的棧頂狀態(tài)為Si時，如果輸入符號為不應(yīng)該遇到的符號時，即ACTIONSi，aj=空白，則報錯，說明

9、輸入符號串有語法錯誤。,5.3.2 LR分析表的構(gòu)成,LR分析器的關(guān)鍵是構(gòu)造分析表。表5.2給出了文法G： 0)SA，1)A(A)，2)Aa 的分析表。,表5.3 LR分析表,5.3.3 LR分析過程,圖5.3 LR的分析流程,分析開始時，棧內(nèi)的初始狀態(tài)為0，符號棧為#。當(dāng)狀態(tài)棧頂為某個狀態(tài)p時，當(dāng)前輸入指針指向的符號是a時，查分析動作表的p行、a列。如果得到的動作指示ACTIONp,a是移進(jìn)Si，則將a壓入符號棧，將狀態(tài)i壓入狀態(tài)棧，然后將輸入指針指向輸入符號串的下一個符號；如果得到的動作指示是歸約Ri，且歸約產(chǎn)生式為B，則從符號棧內(nèi)彈出|個符號，從狀態(tài)棧內(nèi)彈出|個狀態(tài)，,假設(shè)此時出棧后的狀

10、態(tài)棧棧頂為p，查狀態(tài)轉(zhuǎn)換表的p行、B列，得到下一個狀態(tài)GOTOp,B=q，并將該后繼狀態(tài)q壓入狀態(tài)棧；如果得到的動作指示是接受，則接受輸入的符號串，分析成功結(jié)束；,5.3.3 LR分析過程,例5.2，利用表5.3分析表分析符號串 (a)。,5.4 LR(0)分析方法,LR(0)分析器是LR分析方法中最簡單的一種，在確定分析動作時，不需要向前查看任何符號, 它是構(gòu)造其它更復(fù)雜的LR分析器的基礎(chǔ)。為了進(jìn)行LR(0)分析，首先需要對文法進(jìn)行拓廣，目的是使文法只有一個以識別符號作為左部的產(chǎn)生式，從而使構(gòu)造出來的分析器有唯一的接受狀態(tài)。拓廣后的文法稱為拓廣文法。,例5.3,對文法G ET|E+T|ET

11、Ti|(E) 進(jìn)行拓廣。 解：引入一個新的開始符號S，使得文法的開始符號所在的規(guī)則唯一，這樣得到拓廣文法如下： SE ET|E+T|ET Ti|(E),5.4.1活前綴和可歸前綴,前綴:從任意符號串x的末尾刪除0或多個符號后得到的符號串. 如u、uni、universi ty都是university的前綴。 活前綴:前綴的子集，它是針對規(guī)范句型而言的，而可歸前綴是一個特殊的活前綴。,活前綴： 設(shè)t是一個規(guī)范句型，即 t是能用最右推導(dǎo)得到的句型，其中表示句柄，tVt*，如果 =u1u2ur，那么稱符號串u1u2ui(其中1ir)是句型 t的活前綴。 從活前綴的定義可知，一個規(guī)范句型的活前綴可以有

12、多個，但觀察這些活前綴，會發(fā)現(xiàn)其中活前綴u1、u1u2、u1u2ur-1不含有完整句柄，只有活前綴u1u2ur含有完整句柄，那么這個含有句柄的活前綴u1u2ur稱為可歸前綴。 活前綴不含句柄右邊的任意符號，而可歸前綴是含有句柄的活前綴。對一個規(guī)范句型來說，活前綴可有多個，可歸前綴只有一個。,5.4.1活前綴和可歸前綴,例5.4，有文法GET|E+T|E-T，Ti|(E)，找規(guī)范句型E+(i-i)的活前綴和可歸前綴。 解：首先畫出E+(I-i)的語法樹，可找出第一個i是句柄，那么=E+(i ，t=-i) 因此活前綴為：E，E+，E+(，E+(i，其中E+(i是可歸前綴。,總結(jié)活前綴求法：先畫出句

13、型的語法樹，找出句柄，然后，從句型的左邊第一個符號開始，取長度分別為1、2、的符號串，直到包含句柄在內(nèi)的長度符號串就是該句型所有的活前綴。而可歸前綴就是最長的活前綴。注意：所有活前綴都不包括句柄右邊的任何符號(即t中的任何符號)。,LR分析過程中，如果輸入符號串沒有語法錯誤，則在分析的每一步，若將符號棧中的全部文法符號與剩余的輸入符號串連接起來，得到的一定是所給文法的一個規(guī)范句型。也就是說，壓入符號棧中的符號串一定是某一規(guī)范句型的前綴，而且這種前綴不會含有任何句柄右邊的符號，所以都是活前綴。當(dāng)符號棧形成句柄，即符號棧的內(nèi)容為可歸前綴時，就會立即被歸約。所以說，LR分析就是逐步在符號棧中產(chǎn)生可歸

14、前綴，再進(jìn)行歸約的過程。,5.4.1活前綴和可歸前綴,5.4.2 LR(0)項目,雖然LR分析器可以識別活前綴，但它的主要目的是要輸出為給定的輸入串構(gòu)造逆向最右推導(dǎo)時使用的產(chǎn)生式序列。因此分析器的一個基本功能就是要檢測句柄。為了檢測句柄，分析器首先必須能夠識別出當(dāng)前句型中含有句柄的可歸前綴。在介紹如何構(gòu)造LR分析器之前，我們還要先了解項目及項目有效性的概念。,5.4.2 LR(0)項目,1、項目的定義 對某個文法G來說，如果A12為G的一條規(guī)則，那么，對規(guī)則的右部加上一個圓點，就成為一個項目。其形式為：A12 圓點是表示項目的一種標(biāo)記，也就是說，如果一條規(guī)則的右部標(biāo)有圓點，那么它就是項目。一般

15、情況下，因為圓點的位置不同。一條規(guī)則可以有幾個項目。,例如，有文法SE，ET|E+T|E-T，Ti|(E)， 對于規(guī)則SE右部有一個符號，因圓點位置不同，可有下面兩個項目 S.E ， SE. 對于規(guī)則EET，右部有三個符號，可有下面四個項目 EET ， EET ， EET ， EET,項目中點后面的符號稱為該項目的后繼符號。后繼符號可能是終結(jié)符號，也可能是非終結(jié)符號，如果點在最后，后繼符號則為空。,第5章 語法分析自底向上分析,根據(jù)項目中點的位置和后繼符號，可把項目分成以下幾種： 移進(jìn)項目：后繼符號為終結(jié)符號，如EET。 待約項目：后繼符號為非終結(jié)符號，如EET和S.E 歸約項目：后繼符號為空

16、，即點在最后。如EET和SE. 接受項目：文法的開始符號S的歸約項目。接受項目是一個特殊的歸約項目，它表示該產(chǎn)生式歸約后分析將結(jié)束。上例中的項目SE.就是接受項目。,2、項目有效性 項目就是對規(guī)則的右部標(biāo)記了圓點，而且，圓點位置不同代表不同的項目，那么項目有什么含義呢？這就是項目的有效性。 一個項目A12對于某個活前綴 1是有效的，當(dāng)且僅當(dāng)存在某個最右推導(dǎo)。 S =|*= At =|= 12t ，其中t是終結(jié)符號串。 在LR分析過程中，活前綴就是符號棧的內(nèi)容，是已經(jīng)讀入的符號，它不包含句柄右邊的任何符號。 活前綴和句柄的關(guān)系有三種：活前綴包含句柄、含有句柄的一部分或不含句柄的任何符號。,第5章

17、 語法分析自底向上分析,第5章 語法分析自底向上分析,1) 如果活前綴包含句柄，表示符號棧頂形成句柄，則就可以歸約。假設(shè)歸約產(chǎn)生式為A，由于活前綴包含完整的，說明已經(jīng)識別了的全部，所以說項目A.對活前綴有效。因此，當(dāng)一個點在最后的項目對活前綴有效時，則可以進(jìn)行歸約，所以把點在最后的項目稱為歸約項目。 2) 如果活前綴只包含句柄的部分符號時，正期待著從余流的輸入符號中看到句柄的其余符號。假設(shè)活前綴含有1，有產(chǎn)生式A12，由于活前綴中有產(chǎn)生式右部12的1部分，所以說A1.2對活前綴有效。同樣，如果有另一個產(chǎn)生式B13，那么B1.3對活前綴也有效。 3) 如果活前綴不含句柄的任何符號，則需將余流的輸

18、入符號移進(jìn)。假設(shè)下一步移進(jìn)的符號可能是的前綴，那么，對于任一產(chǎn)生式A來說，由于活前綴中不含的任何符號，所以說A.對活前綴有效。 一個項目指明了在分析過程的某一時刻，已經(jīng)看到的一個產(chǎn)生式右部的多少。 一般來說，活前綴與有效項目是多對多關(guān)系。,第5章 語法分析自底向上分析,例5.5，有文法 SE ，ET|E+T|E-T ，Ti|(E)，列出該文法的所有項目，并找出對活前綴E有效的項目。 解：首先列出每條規(guī)則對應(yīng)的多個項目： SE，有項目S.E，SE. ET ，有項目E.T，ET. EE+T ，有項目E.E+T，EE.+T，EE+.T，EE+T. EE-T ，有項目E.E-T，EE. -T，EE-.

19、T，EE-T. Ti，有項目E. i，Ei. T(E) ，有項目T.(E) T(.E) T(E.) T(E).,在上面的眾多項目中，只有項目EET，Ti和T(E)對活前綴E是有效的， 這是因為從S到含有活前綴E的規(guī)范句型的規(guī)范推導(dǎo)中，能夠使用這些項目：,第5章 語法分析自底向上分析,先看推導(dǎo)過程S = E = ET，最后一步推導(dǎo)使用的規(guī)則是EET，句柄為ET，該過程推導(dǎo)出的句型ET含有活前綴E，而E是句柄ET的一部分，所以說規(guī)則EET的項目EET對E是有效的。 接下來看推導(dǎo)過程S= E= ET =Ei，最后一步推導(dǎo)使用的規(guī)則是Ti，句柄為i，該過程推導(dǎo)出的句型Ei也含有活前綴E，但由于活前綴E

20、-不含句柄i的任何符號，所以說項目Ti對E也是有效的。 同理，對于推導(dǎo)過程S = E = ET= E(E)，可證明項目T(E)對E也是有效的。 因此，EET，Ti和T(E)是活前綴E-的有效項目集。,從LR分析過程看，當(dāng)符號棧內(nèi)容為E-時，有項目EET、Ti和T(E)對E-有效，則將來形成的句柄一定是EET，Ti和T(E)這幾條規(guī)則之一的右部。究竟會形成哪條規(guī)則的右部取決于下一個讀入的符號，如果下一個符號是i，則形成句柄i；如果下一個符號是(，則將等待形成句柄(E)。,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),在LR實際分析過程中，并不直接分析符號棧中的符號是否形成句柄。 但我們可以把文法中的符

21、號都看成是有窮自動機(jī)的輸入符號，每當(dāng)一個符號進(jìn)棧時表示已經(jīng)識別了該符號，并進(jìn)行狀態(tài)轉(zhuǎn)換；當(dāng)識別出可歸前綴時，相當(dāng)于在棧中形成句柄，則認(rèn)為到達(dá)了識別句柄的狀態(tài)。 自動機(jī)中的每個狀態(tài)都和無數(shù)個活前綴密切相關(guān)，每個狀態(tài)中都包含該狀態(tài)所能識別的活前綴。因為文法有無窮的句型，所以一個可用文法具有無窮數(shù)目的活前綴，因此，根據(jù)活前綴集合直接構(gòu)造對應(yīng)的自動機(jī)狀態(tài)是不可能的。因為每個活前綴對應(yīng)的有效項目是有窮的，因此，可以將一個活前綴的可能的無窮集對應(yīng)到一個有窮的有效項目集上。因此，如果我們能得到對應(yīng)分析器每個狀態(tài)的有效項目的有窮集合，那么，也就能得到識別活前綴的有窮自動機(jī)。,1、 項目集的閉包運(yùn)算 設(shè)I為一項

22、目集，I的閉包運(yùn)算CLOSURE(I) 定義如下： I中的每一個項目都屬于CLOSURE(I)。 如項目A1X2屬于CLOSURE(I)，且X為非終結(jié)符號，則將形式為X.的項目添加到CLOSURE(I)中。 重復(fù)(1)和(2)，直到CLOSURE(I)封閉為止。,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),例5.6，有文法：E :=E，E:=E+T，E:=T，T:=T*F，T:=F，F(xiàn):=(E)，F(xiàn):=i， 設(shè)項目集I=E.E，求CLOSURE(I)。 解：根據(jù)閉包運(yùn)算的第1條，CLOSURE(I)= E .E 根據(jù)第2條，因為E是非終結(jié)符號，所以將規(guī)則E:

23、=E+T和 E:=T在其右部最前面加點形成E.E+T和E.T，加進(jìn)CLOSURE(I)中： CLOSURE(I)= E .E，E.E+T，E.T 根據(jù)第3條，重復(fù)計算，直到CLOSURE(I)封閉為止。因為T是非終結(jié)符號，所以將規(guī)則T:=T*F和T:=F在其右部最前面加點形成T.T*F和T.F，加進(jìn)CLOSURE(I)中： CLOSURE(I)= E .E，E.E+T，E.T，T.T*F，T.F 因為F是非終結(jié)符號，所以將F .(E)和F . i，加進(jìn)CLOSURE(I)中： CLOSURE(I)= E .E，E.E+T，E.T，T.T*F，T.F，F(xiàn).(E)，F(xiàn).i 至此，CLOSURE(I

24、)封閉。,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),2、 項目集之間的轉(zhuǎn)換函數(shù)GO 假設(shè)有一項目為A.X，令X是一個字匯表中的符號，則對項目A.X進(jìn)行讀X操作，結(jié)果為項目AX.。 設(shè)I是一個項目集,X是任一文法符號，則項目集之間的轉(zhuǎn)換用GOI,X函數(shù)表示，定義為： GOI,X=CLOSURE(J) 其中J=任何具有A X.的項目| A .X I ，即對項目集I中所有的項目進(jìn)行讀X操作的結(jié)果。CLOSURE(J)為對J進(jìn)行了閉包運(yùn)算得到的項目集，稱為I的后繼項目集。令狀態(tài)I代表項目集I，狀態(tài)J代表后繼項目集CLOSURE(J)，用狀態(tài)圖表示則為：,例5.7，有文法：E :=E，E:=E+T，E:=

25、T，T:=T*F，T:=F，F(xiàn):=(E)，F(xiàn):=i 有項目集I=E E.,E E.+T, 求GOI,+ 解：在I中挑出點后是+的項目有：E E.+T,將點移到+后面得J=E E+.T 對J進(jìn)行閉包運(yùn)算得 CLOSURE(J)=E E+.T，T.F，T.T*F, F.(E), F.i GO(I,+) =E E+.T，T.F，T.T*F, F.(E), F.i 用狀態(tài)圖表示為：,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),3、舉例說識別活前綴的有窮自動機(jī)的構(gòu)造方法 假設(shè)有拓廣文法為：0) SA，1) A(A)，2) Aa 從文法的開始符號所在的規(guī)則SA開始，項目

26、S.A將作為有窮自動機(jī)的開始狀態(tài)。項目S.A反映了此時分析器還沒有識別任何(非空)活前綴。對例中的文法，開始符號所在的規(guī)則為SA，所以開始狀態(tài)0的項目集有C0=S.A，且項目S.A稱為基本項目。 然后，需要對項目集中的各成員進(jìn)行閉包(closure)運(yùn)算，也就是看項目中的點后面的符號是否是非終結(jié)符號。如果是非終結(jié)符號，則將該非終結(jié)符號為左部的規(guī)則，在其右部最前面加點構(gòu)成項目，并填加到該項目集中。對于C0=S.A，由于S.A點后面是非終結(jié)符號A，那么就對文法中所有左部符號為A的規(guī)則，在右部最前面加點，并添加到項目集C0中。這樣就可獲得開始狀態(tài)0對應(yīng)得項目集為：C0=S.A, A.(A)，A.a

27、,接下來構(gòu)造C0的后繼項目集。觀察狀態(tài)0的項目集C0的每個項目，發(fā)現(xiàn)點后的符號即后繼符號為A、(、a，說明項目集C0有3個后繼項目集C1 (GO0，A) 、C2 (GO0，() 、C3 (GO0，a) ，即狀態(tài)0有3條弧線指向狀態(tài)1、2、3，弧線上分別標(biāo)記符號A、(、a。下面介紹項目集C1、C2、C3的構(gòu)造：,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),1) 首先將C0中后繼符號為A的項目挑選出來，可得項目集S.A，將點移到A的后面，得到C1的基本項目集為SA. ，然后對此項目集進(jìn)行閉包運(yùn)算。由于在該項目集只有一個項目中，且點位于最右，所以閉包運(yùn)算沒有添加任何項目，最終C1=SA.，即GO0，A=

28、1。,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),2) 看C0中的項目 A.(A)，后繼符號是(，將點移到(的后面，得到C2的基本項目集為 A(.A) 。由于點后面是非終結(jié)符號A，所以將A.(A)，A.a加入項 目集，最終C2= A(.A)，A.(A)，A.a ，即GO0，(=2。 3) 看C0中的項目 A.a ，最終得C3= Aa. ，即GO0，a=3。 到此、我們構(gòu)造好了狀態(tài)0、1、2、3。如圖5.7所示。,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),繼續(xù)上述的后繼項目構(gòu)造過程, 直到再沒有新的項目集產(chǎn)生。 C2的基本項目集為 A(.A) ，最終C2= A(.A)，A.(A)，A.a 。分析狀態(tài)2

29、的項目： A(.A)：后繼項目集C4= A(A.) A.(A)：后繼項目集仍是C2本身 A.a：后繼項目集為C3 Aa. 對狀態(tài)4的項目A(A.) 后繼項目集C5= A(A).。 至此，我們得到的所有項目集如表5.8所示。,因為每個項目集是有窮的，因此最終產(chǎn)生的狀態(tài)數(shù)目肯定是有限的。最終產(chǎn)生的識別活前綴的有窮自動機(jī)如圖5.8所示。,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),4、識別活前綴的有窮自動機(jī)構(gòu)造算法 給定一文法G，該文法的開始符號為S，下面算法為給定文法G生成識別活前綴的有窮自動機(jī)。該自動機(jī)包含有下列項目集集合 C= C0,C1,Cn, 其中C0是

30、開始項目集，C稱為LR(0) 項目集規(guī)范族。該自動機(jī)的狀態(tài)是0,1,n,其中每個狀態(tài)j是由項目集Cj得到的。,1) 生成開始項目集： 賦給開始項目集一個下標(biāo)0，然后將項目S.放入集合C0，對應(yīng)的狀態(tài)為0。 對該項目集執(zhí)行閉包運(yùn)算，即找到在圓點之后的非終結(jié)符X，將形式為X.的項目放置到集合中，其中X是文法G的一個產(chǎn)生式。該閉包運(yùn)算也要對所有導(dǎo)出的新項目進(jìn)行。 2) 生成LR(0)的所有項目集C：重復(fù)第3到第4步，直到再沒有新的項目集出現(xiàn)。 3) 對一個項目集Ci求后繼項目集Cj，構(gòu)造項目集的轉(zhuǎn)換： 對項目集Ci中的每個后繼符號X進(jìn)行讀操作，生成一個新的項目集Cj，且 GOCi,X= Cj。 如果

31、該項目集已經(jīng)存在，則Cj就是已經(jīng)存在的項目集；否則，得到一個新的基本項目集Cj； 4) 對新的項目集進(jìn)行閉包運(yùn)算。,5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),5.4.3 構(gòu)造識別活前綴的有窮自動機(jī),如果LR(0) 項目集規(guī)范族中的每個項目集看做有窮自動機(jī)的一個狀態(tài)，則項目集規(guī)范族的GO函數(shù)把這些項目集連接成一個DFA。令C0為DFA的初態(tài)，則該 DFA就是恰好識別文法所有活前綴的有限自動機(jī)。因此得結(jié)論：對于任一文法G,關(guān)于該文法的LR(0) 項目集規(guī)范族的GO函數(shù)定義了一個識別文法所有活前綴的DFA。 實際上，一個活前綴w的有效項目集，正是由識別文法所有活前綴的DFA的初態(tài)出發(fā)，經(jīng)由標(biāo)記為w的路

32、徑所到達(dá)的那個項目集。在LR分析過程中，符號棧中的活前綴的有效項目集就是棧頂?shù)臓顟B(tài)所代表的那個項目集。,5.4.4 LR(0)分析表的構(gòu)造,構(gòu)造出了識別活前綴的有窮自動機(jī)后，就可以構(gòu)造分析表。分析表分兩部分，動作表每列的開頭是文法的終結(jié)符號以及右界符#，每行的開頭為狀態(tài)號。假設(shè)已經(jīng)構(gòu)造出LR(0)項目集規(guī)范族：C= C0，C1，Cn，其中Ci為項目集的名字，對應(yīng)的狀態(tài)為i。假設(shè)S是文法開始符號所在的規(guī)則，令包含項目S.的項目集Ci對應(yīng)的狀態(tài)i為開始狀態(tài)，那么，分析表的動作表和狀態(tài)轉(zhuǎn)換表的構(gòu)造方法為：,1) 若項目A.aCi且GOCi,a= Cj,其中a為終結(jié)符，置ACTIONi,a=“把狀態(tài)j

33、和符號a移進(jìn)棧”，簡記為“Sj”; 2) 若項目A.Ci,則對于任何輸入符號a或結(jié)束符#，置ACTIONi,a=“用產(chǎn)生式A進(jìn)行歸約”，簡記為“Rj”(假定A是文法G的第j條產(chǎn)生式); 3) 若項目S. Ci ,則置ACTIONi,#=“接收”，簡記為A； 4) 若GOi,A= Cj,A為非終結(jié)符，則置GOTOi,A=j 5) 分析表中凡不能用規(guī)則- 添入信息的單元為空或均置上ERROR，表示有錯。,5.4.4 LR(0)分析表的構(gòu)造,例5.8，對拓廣文法：0)SA、1)A(A)、2)Aa，根據(jù)表5.5項目集構(gòu)造分析表。 解：因為文法有3個終結(jié)符號，除開始符號外有一個非終結(jié)符號A，所以，分析動

34、作表有4列，分別為(、)、a和#，GOTO表有1列A。前面已經(jīng)求出該文法的項目集規(guī)范族為： C0=S.A, A.(A)，A.a C1=SA. C2= A(.A)，A.(A)，A.a C3= Aa. C4= A(A.) C5= A(A).,5.4.4 LR(0)分析表的構(gòu)造,表5.6 LR(0)分析表,因此，分析表應(yīng)有6行，分別為0、1、2、3、4和5。,5.4.4 LR(0)分析表的構(gòu)造,觀察項目集C0=S.A, A.(A)，A.a ，因為S是開始符號，S.A在C0中，因此0為開始狀態(tài)。對于C0的項目A.(A)，將點從(前移到(后，產(chǎn)生項目集C2，因為(是終結(jié)符，因此，按照分析表構(gòu)造方法的第1

35、條，在ACTION得0行(列填入S2，即ACTION0,( =S2。對項目A.a，將點從a前移到a后，產(chǎn)生項目集C3，因此，置ACTION0, a=S3。對項目S.A，將點從A前移到A后，產(chǎn)生項目集C1，因為A是非終結(jié)符，因此，按照分析表構(gòu)造方法的第4條，則置GOTOi,A=j。,觀察C1=SA.，因為S是開始符號，SA.在C1中，符合分析表構(gòu)造方法的第3條，因此，置ACTION1, #=A，即接受。,觀察C3= Aa.，符合分析表構(gòu)造方法的第2條，因Aa是文法的第2條規(guī)則，因此對ACTION表的3行的所有單元填寫R2。,觀察C2= A(.A)，A.(A)，A.a 、C4= A(A.)和C5=

36、 A(A).，我們可填寫分析表的其它內(nèi)容，最后可得分析表如表5.6所示。,5.4.5 LR(0)分析器的工作過程,分析表是LR分析的關(guān)鍵，有了分析表后就可以在總控程序的控制下對輸入符號串進(jìn)行分析，其分析方法如下：,若ACTIONS，a=Sj，a為終結(jié)符，則把a(bǔ)移入符號棧，狀態(tài)j移入狀態(tài)棧。 若ACTIONS，a=Rj，a為終結(jié)符或#號，則用第j個產(chǎn)生式歸約。設(shè)k為第j個產(chǎn)生式右部的符號串長度，將符號棧和狀態(tài)棧頂?shù)膋個元素出棧，將產(chǎn)生式左部符號入符號棧。 若ACTIONS，a=A，a為#號，則為接受，表示分析成功。 若GOTOS，A= j，A為非終結(jié)符號并且是符號棧的棧頂，表示前一個動作是歸約，A是歸約后移入符號棧的非終結(jié)符，則將狀態(tài)j移入狀態(tài)棧。 若ACTIONS，a=空白，則轉(zhuǎn)入錯誤處理。,例5.9，利用表5.6的LR(0)分析表分析符號串“(a)”。 文法為：0)SA ，1)A(A) ，2)Aa 解：按照LR(0)分析器的工作過程，表5.7列出符號串“(a)”的分析過程。