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

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

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

關(guān)鍵詞：編譯原理；移近；規(guī)約；符號棧；LR分析法

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

1引言

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

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

2LR分析法概述

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

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

下面先討論根據(jù)項目的含義構(gòu)造狀態(tài)轉(zhuǎn)換關(guān)系圖的方法，然后介紹如何將狀態(tài)轉(zhuǎn)換關(guān)系圖改寫為LR分析表。

3狀態(tài)轉(zhuǎn)換關(guān)系圖的構(gòu)造

從項目的定義可以看出，項目雖不能反映出符號棧的全部內(nèi)容，但它可以反映出符號棧棧頂?shù)臓顟B(tài)，而這個狀態(tài)可用于判斷句柄是否已在符號棧棧頂形成。因此在構(gòu)造狀態(tài)轉(zhuǎn)換關(guān)系圖的過程中，我們通過對項目的分析來反映符號棧的狀態(tài)，以及在該狀態(tài)下分析程序應(yīng)采取的動作。

3.1文法及其項目

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

(1) S’→S

(2) S→BB

(3) B→aB

(4) B→b

根據(jù)各產(chǎn)生式可求得文法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符號棧的初始狀態(tài)

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

狀態(tài)0：[ # ]

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

I0：{S’→#8226;S}

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

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

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

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

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

3.3符號的識別和狀態(tài)的轉(zhuǎn)換

首先考慮I0中的項目S’→#8226;S，在接下來的分析中，如果分析程序從輸入串中成功識別出符號S，則符號棧狀態(tài)變?yōu)?/p>

狀態(tài)1：[ # S ]

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

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

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

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

下面考慮I0中的項目S→#8226;BB，在接下來的分析中，如果分析程序從輸入串中成功識別出符號B，則符號棧狀態(tài)變?yōu)?我們這里只關(guān)心棧頂?shù)那闆r，其余符號用省略號表示)

狀態(tài)2：[ # … B ]

此時棧頂?shù)姆枮锽，表示已經(jīng)從輸入串中識別出句柄BB中的前一個B，期望從剩余的輸入串中識別后一個B。在文法G(S’)的所有項目中，項目S→B#8226;B表示了這個狀態(tài)，因此，我們把項目S→B#8226;B歸入項目集I2中。

I2：{S→B#8226;B}

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

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

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

下面考慮I0中的項目B→#8226;aB，在接下來的分析中，如果分析程序從輸入串中成功識別出符號a，則符號棧狀態(tài)變?yōu)?/p>

狀態(tài)3：[ # … a ]

此時棧頂?shù)姆枮閍，表示已經(jīng)從輸入串中識別出句柄aB中的a，期望從剩余的輸入串中識別出B。在文法G(S’)的所有項目中，項目S→a#8226;B表示了這個狀態(tài)，因此，我們把項目S→a#8226;B歸入項目集I3中。

I3：{S→a#8226;B}

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

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

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

下面考慮I0中的項目B→#8226;b，在接下來的分析中，如果分析程序從輸入串中成功識別出符號b，則符號棧狀態(tài)變?yōu)?/p>

狀態(tài)4：[ # … b ]

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

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

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

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

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

按照同樣的方法逐一分析其它狀態(tài)，直至不再產(chǎn)生新的符號棧狀態(tài)和新的狀態(tài)轉(zhuǎn)換關(guān)系為止，同時也構(gòu)造出最終的狀態(tài)轉(zhuǎn)換關(guān)系圖如圖5所示。

各狀態(tài)對應(yīng)的項目集分別為

項目集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)。

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

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

4LR分析表的構(gòu)造

將圖5所示的狀態(tài)轉(zhuǎn)換關(guān)系圖用一個二維的表格結(jié)構(gòu)重新表示出來，即可得到圖6所示的LR分析表。

5總結(jié)

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

參 考 文 獻

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

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

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

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

Wesley， Pearson Education， Inc. 1986.