劉 濤，賈麗娟，于 峰

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

0 引言

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

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

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

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

1 詞法分析器[1]

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

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

int i=10;

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

圖1 編譯流程Fig.1 Compile process

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

（1）過濾空白和注釋

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

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

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

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

getToken()：查看對應(yīng)于剛找到的詞素的符號表條目，并且根據(jù)符號表中的信息返回該詞素所代表的詞法單元名字—要么是 id，要么是一個初始化時就加入到符號表的關(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 無符號數(shù)字的狀態(tài)轉(zhuǎn)移圖Fig.4 S tate transition diagram of unsigned digits

2 語法分析器[1]

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

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

Expression ->expression + term | term;

term -> term* factor | factor

factor ->NUMBER | (expression)

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

expression代表表達(dá)式，term代表項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ī)則不會出現(xiàn)修改前那樣導(dǎo)致解析死循環(huán)[1,7]。語法規(guī)則中的“空”表示結(jié)束，什么都不做。例如如果我們輸入一個空字符串“”給語法解析器，那么規(guī)則 1中就以“空”來解析輸入的空字符串，其結(jié)果就是程序什么都不做，直接返回，在程序中“空”相當(dāng)于return語句。

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

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

給出表驅(qū)動的預(yù)測語法分析：

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

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

方法：

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

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

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

if(x等于ip所指向的符號a)指向棧彈出操作，將ip向前移動一個位置

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

else if(M[x,a]是一個報錯條目) error();

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

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

輸出棧頂符號;

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

3 結(jié)論

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

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

[2] 埃克爾, Java編程思想(第四版)[M]. 機械工業(yè)出版社, 2007.

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

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

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

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

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

[8] C++語言開發(fā)跨平臺程序的研究與實現(xiàn)[J]. 熊凱, 高茂庭,于仁師. 電腦知識與技術(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.