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

劉 濤，賈麗娟，于 峰

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

0 引言

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

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

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

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

1 詞法分析器[1]

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

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

int i=10;

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

圖1 編譯流程Fig.1 Compile process

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

（1）過濾空白和注釋

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

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

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

知道怎么去表達(dá)一個(gè)標(biāo)識(shí)符之后我們就借助狀態(tài)轉(zhuǎn)移[1]圖來模擬一下詞法分析器運(yùn)行的過程[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 無符號(hào)數(shù)字的狀態(tài)轉(zhuǎn)移圖Fig.4 S tate transition diagram of unsigned digits

2 語法分析器[1]

接下來就介紹一下語法分析器，在設(shè)計(jì)語言時(shí)，每種程序設(shè)計(jì)語言都有一組精確地規(guī)則來描述良構(gòu)程序的語法結(jié)構(gòu)，程序設(shè)計(jì)語言的語法可以用上上下文無關(guān)文法來描述，文法為語言設(shè)計(jì)者和編譯器的編寫者都提供了很大的便利，有很多很多的文法可以用來很好的描述程序設(shè)計(jì)語法，我們使用預(yù)測(cè)分析算法[1]來實(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]語法分析，但是其為左遞歸[1,2]，不能用于自頂向下[1]的語法分析，所以推出以上文法的非左遞歸版本（可用于自頂向下的語法分析）：

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)

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

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

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

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

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

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

方法：

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

設(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 語法規(guī)則解析樹Fig.5 Parsing tree of syntax rules

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

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

3 結(jié)論

了解一個(gè)編譯器到底在干些什么事情對(duì)我們理解語言本身有很大的幫助，當(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++語言開發(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.