朱朝霞

摘要：語法分析是編譯程序的核心部分，其任務是檢查詞法分析器輸出的單詞序列是否是源語言中的句子。該文以編譯程序自底向上語法分析為主線，探討自底向上語法分析歸約中的句柄求解問題，希望對編譯原理的課程教學有啟發(fā)作用。

關鍵詞：編譯器； 自底向上語法分析；句柄；棧；歸約

中圖分類號：TP314.51 文獻標識碼：A 文章編號：1009-3044（2016）33-0110-02

語法分析是編譯程序的核心部分，其任務是檢查詞法分析器輸出的單詞序列是否是源語言中的句子，亦即是否符合源語言的語法規(guī)則。完成句型的分析，主要有兩種方式：一種是使用推導方式推導出句子，即自頂向下的語法分析方法；另一種是利用歸約方式識別句子，即自底向上的語法分析方法。本文以編譯程序自底向上語法分析為主線，探討自底向上語法分析歸約中的句柄求解問題，希望對編譯原理的課程教學有啟發(fā)作用。

1 自底向上語法分析

自底向上語法分析，也稱移進-歸約分析，指從給定的輸入符號串w出發(fā)，試圖將其歸約為文法的開始符號。其實現(xiàn)思想是對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄或可歸約串時，就用該產(chǎn)生式的左部非終結符代替相應右部的文法符號串，重復這一過程直到歸約到棧中只剩下文法的開始符號時為分析成功。

在自底向上的分析過程中，最關鍵的問題是句柄的識別問題，即每次規(guī)約時按當前句型的句柄進行規(guī)約。自底向上語法分析方法主要有優(yōu)先分析法和LR分析法。下面以兩種分析法為例求解句型的句柄及可歸約串問題。

2 優(yōu)先分析法

優(yōu)先分析法可分為簡單優(yōu)先分析法和算符優(yōu)先分析法。簡單優(yōu)先分析法的基本思想是對一個文法按一定原則求出該文法所有符號即包括終結符和非終結符之間的優(yōu)先關系，按照這種優(yōu)先關系確定歸約過程的句柄，其歸約過程是一種規(guī)范歸約。

算符優(yōu)先分析的基本思想是只規(guī)定算符之間的優(yōu)先關系，不考慮非終結符之間的優(yōu)先關系，在歸約過程中只要找到可歸約串就歸約，并不考慮歸約到哪個非終結符名，其歸約過程不是歸范歸約。

2.1 簡單優(yōu)先分析法中的句柄

簡單優(yōu)先分析法的分析算法：

先根據(jù)已知優(yōu)先文法構造相應優(yōu)先關系矩陣，并將文法的產(chǎn)生式保存，設置符號棧S：

1）將輸入符號串a(chǎn)1 a2 an #依次逐個存入符號棧S中，直到遇到棧頂符號ai的優(yōu)先性大于下一個待輸入符號aj時，停止進棧；

2）以棧頂當前符號ai為句柄尾，由此向左在棧中找句柄的頭符號ak，即找到ak-1的優(yōu)先性小于ak為止；

3）由句柄ak ai在文法的產(chǎn)生式中查找右部為ak ai的產(chǎn)生式，若找到則用相應左部代替句柄，若找不到則為出錯，此時可斷定輸入串不是該文法的句子；

4）重復上述三步直到歸約完輸入符號串，棧中只剩文法的開始符號為止。

對符號串#b（aa）b#的移進-歸約分析過程中，根據(jù)算法及優(yōu)先關系表求得歸約的句柄依次分別為：a、Aa）、（B、bAb。

簡單優(yōu)先分析法中句柄的求解過程是每次察看句型中相鄰的兩個符號，通過兩個符號的優(yōu)先關系判定出前一個符號是句柄的尾。然后，再反向找出句柄的頭。如下圖所示：

圖中U即為移進-歸約分析過程中當前句型的句柄。

2.2 算符優(yōu)先分析法中的句柄

自底向上的算符優(yōu)先分析法，也稱自左向右歸約。由于算符優(yōu)先分析法不考慮非終結符之間的優(yōu)先關系，在歸約過程中只要找到可歸約串就歸約，并不考慮歸約到哪個非終結符名，因此算符優(yōu)先分析過程中的句柄是一個最左素短語的求解過程。對一文法來說，需先求得句型的所有素短語，處于句型最左邊的素短語即算符優(yōu)先分析的句柄。一個算符優(yōu)先文法的最左素短語形式為NiaiNi+1ai+1…ajNj+1，符號的優(yōu)先關系應滿足：ai-1aj+1。

使用算符優(yōu)先分析法的規(guī)約過程與規(guī)范歸約是不同的，以文法G[E]為例，

（1） E→E+T （2） E→T （3） T→T*F （4） T→F （5） F→PF|P （6） P→（E） （7） P→i

如果對輸入串#i+i#進行規(guī)范歸約分析過程需要12步，然而使用算符優(yōu)先歸約時只需要7步，分析過程中形成的歸約串只有三個：i、i、E+E。原因是算符優(yōu)先分析中去掉了單非終結符歸約，其歸約過程是一種快速歸約過程。

3 LR分析法

LR分析法是一種能根據(jù)當前分析棧中的符號串和向右順序查看輸入串的k個（k≥0）符號就可以唯一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約，因而也就能唯一地確定句柄。LR分析法是規(guī)范推導的逆過程，是一種規(guī)范歸約。

LR分析過程：將文法的終結符和非終結符都看成有窮自動機的輸入符號，每次把一個符號進?？闯梢炎R別過了該符號，同時狀態(tài)進行轉換，當識別到可歸前綴時，相當于在棧中形成句柄，認為達到了識別句柄的終態(tài)。

LR分析器的關鍵部分是分析表的構造。LR分析表是LR分析器的核心部分，是總控程序的依據(jù)。一張LR分析表包括兩部分：一部分是“動作”（ACTION）表，表示當前狀態(tài)下所面臨輸入符應做的動作是移進、歸約、接受或出錯。另一部分是“狀態(tài)轉換”（GOTO）表，表示在當前狀態(tài)下面臨文法的輸入符號時應轉向的下一個狀態(tài)。

對一個文法構造了它的LR分析表后就可以在LR分析器的總控程序控制下對輸入串進行分析，即根據(jù)輸入串的當前符號和分析棧的棧頂狀態(tài)查找分析表應采取的動作，對狀態(tài)棧和符號棧進行相應的操作即移進、歸約、接受或報錯。

LR分析法中的歸約過程：

當在棧頂形成句柄為β時，則用β歸約為相應的非終結符A，即當文法中有A→β的產(chǎn)生式，而β的長度為γ，則從狀態(tài)棧和文法符號棧中自頂向下去掉γ個符號。并把A移入文法符號棧內，再把滿足Sj=GOTO[Sm-γ，A]的狀態(tài)移進狀態(tài)棧，當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結束即當前輸入符是‘#，則為分析成功。

對符號串#baab#分析過程中，歸約過程中求得的句柄依次為：ε、ε、aBa、bAb、AB。

4 結束語

在編譯程序自底向上的語法分析過程中，最關鍵的問題是句柄的識別問題。簡單優(yōu)先分析法其歸約過程是一種規(guī)范歸約，準確、歸范、但分析效率較低，實際使用價值不大。算符優(yōu)先分析法其歸約過程不是歸范歸約，但分析速度快、簡單、直觀，特別適于用手工方式來實現(xiàn)，很多編譯程序都使用算符優(yōu)先法分析表達式。LR分析法分析速度快，能準確、及時地指出輸入串的語法錯誤及出錯位置，比自底向上優(yōu)先分析法對文法的限制要少得多，對大多數(shù)用無二義性的上下文無關文法描述的語言都可以用LR分析器予以識別。

參考文獻：

[1] 蔣宗禮，姜守旭. 編譯原理[M]. 北京：高等教育出版社， 2010.

[2] 張素琴， 呂映芝. 編譯原理[M]. 北京：清華大學出版社， 2005.

[3] 張昱，陳意云. 編譯原理與技術[M]. 北京：高等教育出版社， 2010.

[4] 陳火旺， 蔣偉進. 編譯原理[M]. 長沙：中南大學出版社， 2005.

[5] 黃賢英，王柯柯. 編譯原理及實踐教程[M]. 北京：清華大學出版社， 2008.