快速掌握編譯器設(shè)計(jì)方法

劉 濤，賈麗娟，于 峰

（1. 哈爾濱理工大學(xué) 計(jì)算機(jī)學(xué)院，黑龍江 哈爾濱 150000；2. 哈爾濱理工大學(xué) 理學(xué)院，黑龍江 哈爾濱 150000）

0 引言

現(xiàn)實(shí)世界依賴著程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)[3]開(kāi)發(fā)各種軟件，解決各領(lǐng)域諸多問(wèn)題。作為一名理工科院校學(xué)生，學(xué)會(huì)用高級(jí)語(yǔ)言編程是其應(yīng)該具備的最基本的能力，這就需要所用軟件平臺(tái)[8]要提供較好的編譯器[1]。軟件開(kāi)發(fā)商為我們提供了各種平臺(tái)的不同語(yǔ)言[9]的編譯器，但有些設(shè)備（如手機(jī)或 PAD）的編譯器能力較弱，需要后期的開(kāi)發(fā)者對(duì)其進(jìn)行改進(jìn)或重新編寫。

簡(jiǎn)單講，編譯器就是將"一種語(yǔ)言(通常為高級(jí)語(yǔ)言)"翻譯為"另一種語(yǔ)言(通常為低級(jí)語(yǔ)言)"的程序。其中主要涵蓋了最重要的詞法分析和語(yǔ)法分析過(guò)程，再之后進(jìn)行語(yǔ)義分析生成中間代碼及優(yōu)化，生成目標(biāo)代碼。

因此，寫好一個(gè)編譯器程序的前提是要了解編譯器的運(yùn)行原理[4]，并掌握它的詞法分析技術(shù)與語(yǔ)法分析技術(shù)[5]。編譯的宗旨是在翻譯一個(gè)源程序的過(guò)程中，編譯器所做的所有翻譯工作都不能改變被翻譯的源程序的含義，這是我們需要遵循的根本原則。

通過(guò)對(duì)下面對(duì)編譯器的詞法分析器和語(yǔ)法分析器的分析，再寫編譯器編程就方便了許多。

1 詞法分析器[1]

詞法分析器的功能輸入源程序，按照構(gòu)詞規(guī)則分解成一系列單詞符號(hào)。單詞是語(yǔ)言中具有獨(dú)立意義的最小單位，包括關(guān)鍵字、標(biāo)識(shí)符、運(yùn)算符、界符和常量等。

首先介紹一下詞法分析器，詞法分析器讀入組成源程序的字符流，并且將它們組織成有意義的詞素序列。每組成一個(gè)詞法單元（Token）就將其傳給語(yǔ)法分詞器，例如：

int i=10;

那么詞法分析器所要做的就是將int ,i ,= ,10分別識(shí)別然后結(jié)合各詞素對(duì)應(yīng)的屬性（例如10，作為一個(gè)NUM，10就是它的屬性value）打包成詞法單元傳送給語(yǔ)法分析器。

圖1 編譯流程Fig.1 Compile process

詞法分析器需要和符號(hào)表進(jìn)行交互，當(dāng)詞法分析器發(fā)現(xiàn)一個(gè)標(biāo)識(shí)符的詞素‘a(chǎn)dan’時(shí)，它會(huì)詢問(wèn)符號(hào)表是否已經(jīng)存在這一詞素，如果沒(méi)有就創(chuàng)建新的詞法單元，并將其加入到符號(hào)表中，如果已經(jīng)存在就讀取標(biāo)識(shí)符的信息，以確定向語(yǔ)法分析器傳送哪個(gè)詞法單元。同時(shí)詞法分析器除了負(fù)責(zé)讀取源程序，它還會(huì)執(zhí)行另外兩大任務(wù)：

（1）過(guò)濾空白和注釋

（2）將編譯器生成的錯(cuò)誤信息與源程序的位置聯(lián)系起來(lái)。

在詞法分析器中通常會(huì)用正則表達(dá)式倆描述一個(gè)標(biāo)識(shí)符，對(duì)于正則表達(dá)式的規(guī)則就不做過(guò)多的敘述，只在這列舉一下用正則表達(dá)式在表示的詞法單元的模式[1]：

表1 詞法單元的模式Tab.1 The pattern of the lexical unit

知道怎么去表達(dá)一個(gè)標(biāo)識(shí)符之后我們就借助狀態(tài)轉(zhuǎn)移[1]圖來(lái)模擬一下詞法分析器運(yùn)行的過(guò)程[1,5]：

getToken()：查看對(duì)應(yīng)于剛找到的詞素的符號(hào)表?xiàng)l目，并且根據(jù)符號(hào)表中的信息返回該詞素所代表的詞法單元名字—要么是 id，要么是一個(gè)初始化時(shí)就加入到符號(hào)表的關(guān)鍵字。

圖2 r elop狀態(tài)轉(zhuǎn)移圖Fig.2 Relop state transition diagram

圖3 ID 和關(guān)鍵字的狀態(tài)轉(zhuǎn)移圖Fig.3 State transfer graph of ID and keywords

圖4 無(wú)符號(hào)數(shù)字的狀態(tài)轉(zhuǎn)移圖Fig.4 S tate transition diagram of unsigned digits

2 語(yǔ)法分析器[1]

接下來(lái)就介紹一下語(yǔ)法分析器，在設(shè)計(jì)語(yǔ)言時(shí)，每種程序設(shè)計(jì)語(yǔ)言都有一組精確地規(guī)則來(lái)描述良構(gòu)程序的語(yǔ)法結(jié)構(gòu)，程序設(shè)計(jì)語(yǔ)言的語(yǔ)法可以用上上下文無(wú)關(guān)文法來(lái)描述，文法為語(yǔ)言設(shè)計(jì)者和編譯器的編寫者都提供了很大的便利，有很多很多的文法可以用來(lái)很好的描述程序設(shè)計(jì)語(yǔ)法，我們使用預(yù)測(cè)分析算法[1]來(lái)實(shí)現(xiàn)一個(gè)預(yù)測(cè)分析表[1]：

expression代表表達(dá)式，term代表項(xiàng)factor代表因子：

Expression ->expression + term | term;

term -> term* factor | factor

factor ->NUMBER | (expression)

以上這個(gè)文法指明了運(yùn)算符的結(jié)合性和優(yōu)先級(jí)，該文法屬于LR（第一個(gè)L代表從左向右掃描輸入，第二個(gè)R代表出聲最左推導(dǎo)）文法，適用于自底向上[1]語(yǔ)法分析，但是其為左遞歸[1,2]，不能用于自頂向下[1]的語(yǔ)法分析，所以推出以上文法的非左遞歸版本（可用于自頂向下的語(yǔ)法分析）：

expression代表表達(dá)式，term代表項(xiàng)factor代表因子；而expression'和term'是為了解決左遞歸的情況，所以以下給出非左遞歸的表達(dá)式文法：

（1）statements -> “空” | expression; statements

（2）expression-> term expression'

（3）expression'-> +term expression' | “空”

（4）term -> factor term'

（5）term' -> * factor term' | “空”

（6）factor -> number | (expression)

這組修改后的語(yǔ)法規(guī)則比修改前更加難以理解，但能保證，這組規(guī)則不會(huì)出現(xiàn)修改前那樣導(dǎo)致解析死循環(huán)[1,7]。語(yǔ)法規(guī)則中的“空”表示結(jié)束，什么都不做。例如如果我們輸入一個(gè)空字符串“”給語(yǔ)法解析器，那么規(guī)則 1中就以“空”來(lái)解析輸入的空字符串，其結(jié)果就是程序什么都不做，直接返回，在程序中“空”相當(dāng)于return語(yǔ)句。

我們用表達(dá)式：1 + 2 ; 看看語(yǔ)法規(guī)則形成的解析樹(shù)[1]是怎樣的：

我們以語(yǔ)句id+id*id為例子換一種方式運(yùn)用棧來(lái)通過(guò)每步移入歸約[2]實(shí)現(xiàn)，如表2所示。

給出表驅(qū)動(dòng)的預(yù)測(cè)語(yǔ)法分析：

輸入：一個(gè)串W，文法G的預(yù)測(cè)分析表M。

輸出：W在L(G)中，輸出的W的第一個(gè)最左推導(dǎo)，否則錯(cuò)誤提示。

方法：

最初，語(yǔ)法分析器格局：輸入緩沖區(qū)的是W$，而 G的開(kāi)始符號(hào)S位于棧頂，他的下面是$。一下程序使用預(yù)測(cè)分析表M生成了處理這個(gè)輸入的預(yù)測(cè)分析過(guò)程：

設(shè)置ip是它指向W的第一個(gè)字符，其中ip是輸入的指針

while(x!= $){//棧非空

if(x等于ip所指向的符號(hào)a)指向棧彈出操作，將ip向前移動(dòng)一個(gè)位置

else if(x是終結(jié)符號(hào)) error();

else if(M[x,a]是一個(gè)報(bào)錯(cuò)條目) error();

else if(M[x,a]=x→Y1Y2……Yn){

輸出產(chǎn)生式x→Y1Y2……Yk);

輸出棧頂符號(hào);

將YkYk-1……Y1壓入棧，其中Y1位于棧頂;

}

令x=棧頂元素;

圖5 語(yǔ)法規(guī)則解析樹(shù)Fig.5 Parsing tree of syntax rules

表2 id+id＊id行為流程Tab.2 The behavior process of Id+id＊id

}[2]并且編譯器的好壞可以在很大程度上影響著這一門編程語(yǔ)言的使用頻率，一個(gè)好的編譯器可以極大的提高程序效率，反之，亦可加大程序的開(kāi)銷，所以編譯器的設(shè)計(jì)和優(yōu)化[6]都顯得尤為重要，希望更多有能力的人投入進(jìn)來(lái)，開(kāi)發(fā)出更為便捷，強(qiáng)大的編譯器！

3 結(jié)論

了解一個(gè)編譯器到底在干些什么事情對(duì)我們理解語(yǔ)言本身有很大的幫助，當(dāng)然編譯技術(shù)本身也有很大的應(yīng)用潛力。

[1] (美)Alfred V. Aho, Monica S.Lam,Ravi Sethi, Jeffrey D.Ullman, 編譯原理[M]. 機(jī)械工業(yè)出版社, 2008.

[2] ?？藸? Java編程思想(第四版)[M]. 機(jī)械工業(yè)出版社, 2007.

[3] Steve McConnell, 代碼大全(第2版)[M]. 電子工業(yè)出版社出版, 2006.

[4] 高伸儀. 編譯原理及編譯程序構(gòu)造[M]. 北京: 北京航空航天大學(xué)出版社, 1990.

[5] DavidR. Hanson, ChristopherW.F.可變目標(biāo)C編譯器——設(shè)計(jì)與實(shí)現(xiàn)[M]. 北京: 電子工業(yè)出版社, 2005.

[6] 王鳳英. C++編譯器應(yīng)用研究與評(píng)析[J]. 計(jì)算機(jī)工程與應(yīng)用, 2002(15): 121-123.

[7] 吳元斌. C/C++運(yùn)算求值順序的缺陷分析[J]. 現(xiàn)代計(jì)算機(jī)(專業(yè)版), 2003(07): 60-62.

[8] C++語(yǔ)言開(kāi)發(fā)跨平臺(tái)程序的研究與實(shí)現(xiàn)[J]. 熊凱, 高茂庭,于仁師. 電腦知識(shí)與技術(shù). 2006(05).

[9] Platform-independent code conversion within the C++locale framework. Lars Engebretsen. Software. 2006.

[10] Developing platform independent designs:Model-based design is used to develop source code for multiple compilers,languages and platforms,. Colin Holland. Embedded Systems Europe. 2006.