編譯原理中ＬＲ分析法的教學探討

文章編號：1672-5913(2008)18-0112-03

摘要：LR分析法是編譯原理課程的重點和難點之一。本文對LR分析法的教學內容和教學方法進行了簡化，避開了部分抽象概念的講解，以一種較簡潔和直觀的方式幫助學生理解LR分析法的原理和技術。

關鍵詞：編譯原理；移近；規約；符號棧；LR分析法

中圖分類號：G642 文獻標識碼：B

1引言

編譯原理是高校計算機專業的一門非常重要的核心課程，但由于課程教學內容多，理論抽象，算法復雜，并且涉及到形式語言與自動機、離散數學、數據結構、操作系統等多門先修課程的知識，使得它的難度大大提高，同學普遍反應學習難度太大，雖花了不少時間，但學習效果并不理想。在教學的過程中，如何根據不同層次的學生，適當更新編譯原理教學內容和教學方法，幫助學生在有限的時間內更加輕松和深入的掌握復雜的編譯知識，從而有效的提高課程教學質量是一個有待解決的研究課題。

在編譯原理的教學內容中，語法分析是教學的重點，而LR分析法又是語法分析中較難掌握的一種分析方法。本文就以LR分析法為例展開探討，介紹我們在教學過程中使用的方法。實踐證明，采用這種教學方法，可以較大的簡化LR分析法的教學，在較短的時間內讓學生對LR分析的全過程有一個直觀而深刻的認識。

2LR分析法概述

LR分析法是一種自下而上的語法分析方法。對輸入串進行LR分析的過程，實質上就是逐一將輸入串中的符號移入符號棧，從中識別出句柄并在棧頂進行規約的過程。

要理解和掌握LR分析法，關鍵是要理解符號棧棧頂和句柄之間的關系，或者句柄在符號棧棧頂的形成過程。如果句柄還未在棧頂形成，就應進行“移近”的動作，以期待在將來形成句柄；如果句柄已經在棧頂形成，就應進行“規約”的動作。為了幫助學生直觀的理解這個過程，我們引入了“項目”的概念。一個項目就是在一個產生式的右端加上一個小圓點，這個小圓點將該產生式右端分成了左右兩個部分。我們將一個項目的含義理解為：項目表示符號棧對某個句柄的識別程度，小圓點左邊的部分已經從輸入串中識別出來，并出現在符號棧的棧頂；小圓點右邊的部分還沒有識別出來，期望從剩余的輸入串中對其加以識別。一個文法的產生式數量有限，相應的項目數也有限，如果我們根據每個項目所表示的意義和轉換關系進行狀態劃分和轉換，即可構造出一個有限的狀態轉換關系圖，這個狀態轉換關系圖正好可以反映在符號棧的某個狀態下分析程序應采取的動作：移近、規約、成功或出錯。這正是LR分析表應記錄的內容，因此我們可以很容易的將狀態轉換關系圖改寫成LR分析表。在利用LR分析表進行LR分析時，對照狀態轉換關系圖，可以更加直觀的理解LR分析過程中采取的每一個動作。

下面先討論根據項目的含義構造狀態轉換關系圖的方法，然后介紹如何將狀態轉換關系圖改寫為LR分析表。

3狀態轉換關系圖的構造

從項目的定義可以看出，項目雖不能反映出符號棧的全部內容，但它可以反映出符號棧棧頂的狀態，而這個狀態可用于判斷句柄是否已在符號棧棧頂形成。因此在構造狀態轉換關系圖的過程中，我們通過對項目的分析來反映符號棧的狀態，以及在該狀態下分析程序應采取的動作。

3.1文法及其項目

下面以托廣后的文法G(S’)為例進行分析。文法G(S’)的規則如下：

(1) S’→S

(2) S→BB

(3) B→aB

(4) B→b

根據各產生式可求得文法G(S’)的所有項目如下：

(1) S’→·S(6) B→·aB

(2) S’→S·(7) B→a·B

(3) S→·BB (8) B→aB·

(4) S→B·B (9) B→·b

(5) S→BB· (10) B→b·

3.2符號棧的初始狀態

分析開始前，符號棧為空。在分析的第一步，我們將開始符號#壓入棧底，并將這個狀態定義為符號棧的初始狀態(狀態0)。此時的符號棧狀態為(為方便書寫，這里將符號棧中的符號水平放置在方括號“[ ]”中，棧的生長方向為從左向右)

狀態0：[ # ]

可見在狀態0時，符號棧中只有一個開始符號#，分析程序尚未從輸入串中讀入任何符號。把項目S’→#8226;S歸入與符號棧狀態0對應的項目集I0中。此時項目集I0的內容為

I0：{S’→#8226;S}

項目S’→#8226;S中的#8226;S表示分析程序期望從輸入串中識別的下一個符號是S，而S是一個非終結符，不可能直接從輸入串中讀入。要識別S，必須先從輸入串中識別出其它符號，然后在符號棧棧頂進行規約得到。能規約得到S的產生式只有S→BB，因此，要識別S，必須先識別出BB，再將BB規約為S。在文法G(S’)的所有項目中，項目S→#8226;BB表示了這個狀態，因此，我們應把項目S→#8226;BB擴充到項目集I0中。此時項目集I0的內容為

I0：{S’→#8226;S，S→#8226;BB}

對于新增加的項目S→#8226;BB，#8226;BB表示分析程序期望從輸入串中識別的下一個符號是B。B是一個非終結符，根據前面的分析，我們應把項目B→#8226;aB和B→#8226;b擴充到項目集I0中。此時項目集I0的內容為

I0：{S’→#8226;S，S→#8226;BB，B→#8226;aB，B→#8226;b}

對于新增加的項目B→#8226;aB，#8226;aB表示分析程序期望從輸入串中識別的下一個符號是a，a是一個終結符，可以直接從輸入串中讀入，無須擴充。同理，新增加的項目B→#8226;b也無須擴充。到此，項目集I0已經構造完畢，總共包含4個項目。這4個項目分別從不同的角度反映了符號棧的當前狀態，即符號棧期望分析程序從后面的輸入串中識別出S、BB、aB和b中的任意一個，除此之外的其它的符號均視為非法。換言之，用這樣的方法構造出的項目集可有效的反映出符號棧的當前狀態和它期望的合法輸入。下面分別從這4個項目出發，考慮分析程序對輸入符號的識別和符號棧狀態的變化。

3.3符號的識別和狀態的轉換

首先考慮I0中的項目S’→#8226;S，在接下來的分析中，如果分析程序從輸入串中成功識別出符號S，則符號棧狀態變為

狀態1：[ # S ]

這個狀態下，我們已經在棧頂形成了可以規約的句柄S，下一步即可利用產生式S’→S進行規約，得到文法的開始符S’。在文法G(S’)的所有項目中，項目S’→S#8226;表示了這個狀態，因此，我們把項目S’→S#8226;歸入項目集I1中。此時項目集I1的內容為

I1：{S’→S#8226;} (reduce 0)

項目S’→S#8226;是一個規約項目，表示產生式的右端已經在棧頂形成，分析程序的下一步動作應該是根據該產生式進行規約，而不是從輸入串中讀入新的符號。我們將這個信息在項目集后面的括號中注明，reduce 0表示下一步應根據產生式0(即S’→S)進行規約。

圖1是狀態0和狀態1之間的狀態轉換關系圖。圖中連線上的標記S表示狀態轉換的條件，及符號棧在狀態0時，如果分析程序從輸入串中識別出符號S，則符號棧狀態轉換到狀態1。

下面考慮I0中的項目S→#8226;BB，在接下來的分析中，如果分析程序從輸入串中成功識別出符號B，則符號棧狀態變為(我們這里只關心棧頂的情況，其余符號用省略號表示)

狀態2：[ # … B ]

此時棧頂的符號為B，表示已經從輸入串中識別出句柄BB中的前一個B，期望從剩余的輸入串中識別后一個B。在文法G(S’)的所有項目中，項目S→B#8226;B表示了這個狀態，因此，我們把項目S→B#8226;B歸入項目集I2中。

I2：{S→B#8226;B}

按照前面擴充I1的方法，我們對I2進行擴充，得到最終的項目集I2為

I2：{S→B#8226;B，B→#8226;aB，B→#8226;b}

如前所述，符號棧在狀態0時，如果分析程序從輸入串中識別出符號B，則符號棧的狀態會轉換到2。為體現出這個轉換關系，我們將圖1的狀態轉換關系圖進行擴充，得到圖2所示的狀態轉換關系圖。

下面考慮I0中的項目B→#8226;aB，在接下來的分析中，如果分析程序從輸入串中成功識別出符號a，則符號棧狀態變為

狀態3：[ # … a ]

此時棧頂的符號為a，表示已經從輸入串中識別出句柄aB中的a，期望從剩余的輸入串中識別出B。在文法G(S’)的所有項目中，項目S→a#8226;B表示了這個狀態，因此，我們把項目S→a#8226;B歸入項目集I3中。

I3：{S→a#8226;B}

按照前面擴充I1的方法，我們對I3進行擴充，得到最終的項目集I3為

I3：{S→a#8226;B，B→#8226;aB，B→#8226;b}

如前所述，符號棧在狀態0時，如果分析程序從輸入串中識別出符號a，則符號棧的狀態會轉換到3。為體現出這個轉換關系，我們將圖2的狀態轉換關系圖進行擴充，得到圖3所示的狀態轉換關系圖。

下面考慮I0中的項目B→#8226;b，在接下來的分析中，如果分析程序從輸入串中成功識別出符號b，則符號棧狀態變為

狀態4：[ # … b ]

這個狀態下，我們已經在棧頂形成了可以規約的句柄b，下一步即可利用產生式B→b進行規約，得到符號B。在文法G(S’)的所有項目中，項目B→b#8226;表示了這個狀態，因此，我們把項目B→b#8226;歸入項目集I4中。

I4：{B→b#8226;} (reduce 3)

項目B→b#8226;是一個規約項目，表示產生式的右端已經在棧頂形成。reduce 3表示下一步應根據產生式3(即B→b)進行規約。

如前所述，符號棧在狀態0時，如果分析程序從輸入串中識別出符號b，則符號棧的狀態會轉換到4。為體現出這個轉換關系，我們將圖3的狀態轉換關系圖進行擴充，得到圖4所示的狀態轉換關系圖。

到此，已對項目集I0中所有項目進行了分析。項目集I0反映了符號棧在狀態0時所期望的所有合法輸入，由此構造出的狀態轉換關系圖也就反映了符號棧在狀態0時，當分析程序從輸入串中識別出每一個合法的輸入符號后，符號棧上應進行的動作(移近或規約)和狀態的轉換關系。

按照同樣的方法逐一分析其它狀態，直至不再產生新的符號棧狀態和新的狀態轉換關系為止，同時也構造出最終的狀態轉換關系圖如圖5所示。

各狀態對應的項目集分別為

項目集I0：{S’→#8226;S，S→#8226;BB，B→#8226;aB，B→#8226;b}，

項目集I1：{S’→S#8226;} (reduce 0)，

項目集I2：{S→B#8226;B，B→#8226;aB，B→#8226;b}，

項目集I3：{S→a#8226;B，B→#8226;aB，B→#8226;b}，

項目集I4：{B→b#8226;} (reduce 3)，

項目集I5：{S→BB·} (reduce 1)，

項目集I6：{B→aB·} (reduce 2)。

其中，狀態0為初態，表示分析工作開始時符號棧的狀態；其余狀態均為終態，分別表示分析過程中的某一時刻符號棧所處的狀態。每個狀態的具體情況由對應的項目集表示。

根據項目集里面的項目，我們可以了解到當前符號棧棧頂是否已形成句柄，如未形成句柄，則下一步期望從輸入串中識別哪些符號；如已形成句柄，則下一步應該根據哪一個產生式進行規約。

4LR分析表的構造

將圖5所示的狀態轉換關系圖用一個二維的表格結構重新表示出來，即可得到圖6所示的LR分析表。

5總結

我們首先利用文法規則求得文法的所有項目，再根據每個項目的含義對LR分析過程中可能出現的狀態進行分類，同時對各個狀態之間的轉換關系進行分析，并構造出狀態轉換關系圖，然后將轉換關系圖表格化，獲得了LR分析表。通過這樣的方法構造的狀態轉換關系圖直觀的展示了LR分析的全過程。利用這樣的方法講授LR分析法，可以避開很多抽象概念(如活前綴、可規約前綴、項目的有效性、有效項目集、項目集規范族)的講解，簡化學生對LR分析法的學習過程。當然，本文中構造的LR分析表只是LR(0)分析表，對應的分析法也只適用于LR(0)文法的情況。要更加深入的理解LR分析法，進一步學習SLR(1)分析法、LR(1)分析法和LALR(1)分析法，還必須對這些抽象的概念加以補充。本文提出的方法可用在引入LR分析法的時候，在較短的時間內給學生一個直觀而深刻的認識，為進一步學習更加復雜的分析方法打好基礎。

參 考 文 獻

[1] 龔天富. 程序設計語言與編譯(第2版)[M]. 北京:電子工業出版社，2003.

[2] 陳火旺等. 程序設計語言編譯原理(第3版)[M]. 北京:國防工業出版社，2000.

[3] 張素琴等. 編譯原理(第2版)[M]. 北京:清華大學出版社，2005.

[4]Alfred V. Aho etc. Compilers: Principles， Techniques， and Tools[M]. Addison

Wesley， Pearson Education， Inc. 1986.