編譯程序語(yǔ)法分析句柄問(wèn)題分析與探討

朱朝霞

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

關(guān)鍵詞：編譯器； 自底向上語(yǔ)法分析；句柄；棧；歸約

中圖分類(lèi)號(hào)：TP314.51 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）33-0110-02

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

1 自底向上語(yǔ)法分析

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

在自底向上的分析過(guò)程中，最關(guān)鍵的問(wèn)題是句柄的識(shí)別問(wèn)題，即每次規(guī)約時(shí)按當(dāng)前句型的句柄進(jìn)行規(guī)約。自底向上語(yǔ)法分析方法主要有優(yōu)先分析法和LR分析法。下面以?xún)煞N分析法為例求解句型的句柄及可歸約串問(wèn)題。

2 優(yōu)先分析法

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

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

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

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

先根據(jù)已知優(yōu)先文法構(gòu)造相應(yīng)優(yōu)先關(guān)系矩陣，并將文法的產(chǎn)生式保存，設(shè)置符號(hào)棧S：

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

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

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

4）重復(fù)上述三步直到歸約完輸入符號(hào)串，棧中只剩文法的開(kāi)始符號(hào)為止。

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

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

圖中U即為移進(jìn)-歸約分析過(guò)程中當(dāng)前句型的句柄。

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

自底向上的算符優(yōu)先分析法，也稱(chēng)自左向右歸約。由于算符優(yōu)先分析法不考慮非終結(jié)符之間的優(yōu)先關(guān)系，在歸約過(guò)程中只要找到可歸約串就歸約，并不考慮歸約到哪個(gè)非終結(jié)符名，因此算符優(yōu)先分析過(guò)程中的句柄是一個(gè)最左素短語(yǔ)的求解過(guò)程。對(duì)一文法來(lái)說(shuō)，需先求得句型的所有素短語(yǔ)，處于句型最左邊的素短語(yǔ)即算符優(yōu)先分析的句柄。一個(gè)算符優(yōu)先文法的最左素短語(yǔ)形式為NiaiNi+1ai+1…ajNj+1，符號(hào)的優(yōu)先關(guān)系應(yīng)滿(mǎn)足：ai-1aj+1。

使用算符優(yōu)先分析法的規(guī)約過(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

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

3 LR分析法

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

LR分析過(guò)程：將文法的終結(jié)符和非終結(jié)符都看成有窮自動(dòng)機(jī)的輸入符號(hào)，每次把一個(gè)符號(hào)進(jìn)?？闯梢炎R(shí)別過(guò)了該符號(hào)，同時(shí)狀態(tài)進(jìn)行轉(zhuǎn)換，當(dāng)識(shí)別到可歸前綴時(shí)，相當(dāng)于在棧中形成句柄，認(rèn)為達(dá)到了識(shí)別句柄的終態(tài)。

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

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

LR分析法中的歸約過(guò)程：

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

對(duì)符號(hào)串#baab#分析過(guò)程中，歸約過(guò)程中求得的句柄依次為：ε、ε、aBa、bAb、AB。

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

[4] 陳火旺， 蔣偉進(jìn). 編譯原理[M]. 長(zhǎng)沙：中南大學(xué)出版社， 2005.

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