房超 楊連賀

摘要：傳統(tǒng)的C、C++、Java編譯系統(tǒng)大而全，集成了大量的庫(kù)和框架，足讓開發(fā)者使用非常方便，卻不利于開發(fā)者對(duì)編譯理論與技術(shù)的理解。該文針對(duì)上述問題，研究了簡(jiǎn)單的代碼編譯器的技術(shù)構(gòu)成，開發(fā)出了一個(gè)具有通用意義的簡(jiǎn)單編譯系統(tǒng)，可使讀者更好地學(xué)習(xí)編譯原理和技術(shù)并提高對(duì)這門課的興趣。首先，該文對(duì)Tina解釋器的主要功能和應(yīng)用進(jìn)行了概述，并對(duì)其執(zhí)行過程進(jìn)行了分析和討論；針對(duì)該研究領(lǐng)域的實(shí)際情況，提出了Tina解釋器的設(shè)計(jì)方法。 其次，從Tina的代碼結(jié)構(gòu)和格式入手，分析了常見的詞法、語(yǔ)法問題；研究了編譯技術(shù)，并對(duì)程序的控制結(jié)構(gòu)、判斷的解析過程進(jìn)行詳細(xì)的分析。編譯過程分為詞法分析、語(yǔ)法分析以及代碼生成和處理三個(gè)階段。以Windows系統(tǒng)為開發(fā)平臺(tái)、以C語(yǔ)言為開發(fā)工具，運(yùn)用遞歸技術(shù)和鏈表、隊(duì)列、棧等數(shù)據(jù)結(jié)構(gòu)對(duì)這三個(gè)模塊進(jìn)行了具體的設(shè)計(jì)。

關(guān)鍵詞：編譯技術(shù)；解釋器；詞法分析；語(yǔ)法分析

中圖分類號(hào)：TP314 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）14-0223-03

Abstract： The traditional C、C ++、Java compiler system are large and integrate a large number of libraries and frameworks， allowing developers to use conveniently， are not conducive to understand the compiler theory and technology. In this paper， aiming at the above problems， we research the a simple structure of code compiler technology， developed a simple compiler system with common sense，making the reader betterly learn compiler theory and technology and increasing the interest of this course. Firstly， the main features and applications what Tina interpreter were discussed， and the analysis and discussion of the implementation process. The actual situation in the field of researching， proposed Tina compiler which is the design method of this solution. Secondly， from code structure and format of Tina， it analyzes the common lexical， grammatical problems. Research on the compiler technology， control structures and procedures， parsing judgment for detailed analysis. Compilation process is divided into lexical analysis， syntax analysis and code generation three processing stages，which let the Windows system as the development platform and let C language as development tools and use recursive technique and the data structure of lists and queue and stacks implementing the three modules of the specific design.

Key words： compiler technology； lexical analysis； lexical analysis； interpreter parsing

1 Tina解釋器功能簡(jiǎn)介

Tina解釋器程序完成從源程序的輸入、預(yù)處理、加載、詞法分析、語(yǔ)法分析、語(yǔ)義分析并生成中間逆波蘭表達(dá)式、用虛擬機(jī)執(zhí)行中間代碼、返回結(jié)果等一系列過程[1-3]，其中包括對(duì)while、for、if、function、var、expression、class、array、return、print、API（系統(tǒng)自帶函數(shù)）的解釋過程。Tina是個(gè)很小的腳本語(yǔ)言解釋器，支持類的繼承和加、減、乘、除、與、或運(yùn)算，可以輸出字符串和經(jīng)基本運(yùn)算處理后的結(jié)果，并且假設(shè)程序員編寫的應(yīng)用程序沒有語(yǔ)法錯(cuò)誤[4]。Tina是用C語(yǔ)言設(shè)計(jì)的一款簡(jiǎn)單腳本語(yǔ)言，其中主要運(yùn)用了棧、隊(duì)列、鏈表、數(shù)組等簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)。它實(shí)現(xiàn)的功能過于簡(jiǎn)單，并無(wú)商業(yè)價(jià)值可言，僅僅是讓人們對(duì)編譯理論的實(shí)現(xiàn)以及編譯技術(shù)有一個(gè)更好的理解[5]。圖1是用Tina寫的應(yīng)用程序，圖2是程序的輸出結(jié)果。

2 Tina解釋器的執(zhí)行過程

程序從解釋器的主函數(shù)開始，如果未加說(shuō)明則解釋執(zhí)行本地的test.tina腳本，然后向虛擬機(jī)中注冊(cè)一個(gè)函數(shù)，輸入它在腳本中的名字，以及它的函數(shù)指針、參數(shù)個(gè)數(shù)，函數(shù)的樣式為 void API_FUNC （）。之后建立函數(shù)，分三步：第一步，加載；第二步，預(yù)處理；第三步，掃描。每一步都有一個(gè)獨(dú)立的C程序模塊對(duì)Tina腳本進(jìn)行處理，下面分別介紹之。

（1） 加載。把以.tina為后綴的源文件作為函數(shù)輸入，通過C語(yǔ)言自帶的讀文件函數(shù)，把讀到的所有源文件的字符全部放入緩沖區(qū)中，等待下一步的處理。

（2） 預(yù)處理。從緩沖區(qū)中讀出源程序，并且去掉單行注釋和塊注釋。

（3） 掃描。掃描進(jìn)行三遍，第一遍掃描， 如圖3所示，掃描所有的全局函數(shù)聲明，用token_get（）函數(shù)進(jìn)行詞法分析和語(yǔ)法分析[6]，把掃描到的字符放到圖4所示的t_k結(jié)構(gòu)體中，并根據(jù)掃描到的符號(hào)類型，來(lái)判斷是否為函數(shù)符號(hào)。如果是，則調(diào)用函數(shù)定義解析模塊進(jìn)行解析；如果掃描到的是類，則略過類的名字和定義塊。第二遍掃描，掃描所有類的定義，發(fā)現(xiàn)類的定義并調(diào)用類解析模塊進(jìn)行解析。第三遍掃描，發(fā)現(xiàn)函數(shù)的名字以及定義，并調(diào)用函數(shù)定義解析模塊進(jìn)行解析。這三遍中用到的解析模塊以及進(jìn)行詞法分析的token_get（）函數(shù)將在后面介紹[7]。

3 Tina解釋器的體系結(jié)構(gòu)

Tina解釋器的體系結(jié)構(gòu)從主程序模塊main.c開始，這個(gè)模塊包括五個(gè)部分，其中構(gòu)建模塊也包括五個(gè)部分，函數(shù)解析模塊包含七部分：詞法分析模塊，貫穿整個(gè)函數(shù)解析模塊；中間代碼執(zhí)行模塊調(diào)用函數(shù)解析模塊、虛擬機(jī)運(yùn)行模塊、API解析模塊和變量處理模塊；變量處理和表達(dá)式解析模塊會(huì)調(diào)用詞法分析、變量處理、函數(shù)解析模塊。

3.1 token_get（）函數(shù)

從當(dāng)前位置（pos）解析一個(gè)詞法標(biāo)記，并將詞法標(biāo)記的相關(guān)信息存入t_k所指向的TokenInfo對(duì)象里，解析之后，當(dāng)前位置會(huì)向后跳躍一個(gè)詞法標(biāo)記，我們假設(shè)整個(gè)待輸入的緩存中的詞法是無(wú)錯(cuò)的（即不存在無(wú)效的詞法單元）。

首先，刷新t_k的字符串內(nèi)容，建立臨時(shí)儲(chǔ)存詞法標(biāo)記字符串的數(shù)組并且清零。檢測(cè)是否已經(jīng)到了文件尾并且刪除前導(dǎo)空白符（回車、換行、空格），檢查復(fù)合運(yùn)算符（>=，<=，==，！=，+=，-=，*=，/=）、運(yùn)算符（.，+，-，*，/，>，<，=，（，[）、引用標(biāo)記（&、]、）、{、}）、分號(hào)和逗號(hào)，如果遇到數(shù)字或字母，則一定是字符或者數(shù)字常量，如果是字符，則依次檢查是否為關(guān)

鍵字，是否為引用成員運(yùn)算符，是否為API函數(shù)，是否為自定義函數(shù)，并把判斷的類型存入t_k結(jié)構(gòu)體中。

3.2 function函數(shù)解析模塊

模塊分為兩部分：函數(shù)聲明的解析和函數(shù)定義的解析[8]。

函數(shù)聲明的解析：用token_get（）獲取函數(shù)名稱，為局部變量加入后綴“_M”，防止與全局變量的聲明混淆，檢查有無(wú)重名函數(shù)，沒有則創(chuàng)建函數(shù)。

函數(shù)定義的解析：我們已經(jīng)預(yù)掃描過了函數(shù)的聲明，現(xiàn)在我們直接通過函數(shù)的名字獲取該函數(shù)的結(jié)構(gòu)，并設(shè)置該函數(shù)為當(dāng)前掃描函數(shù)，解析參數(shù)形如（a，b，c），我們把參數(shù)當(dāng)作函數(shù)的最外層的幾個(gè)變量，調(diào)用解析變量模塊對(duì)函數(shù)體內(nèi)的局部變量進(jìn)行掃描，確定其相對(duì)索引，并放在變量列表隊(duì)列中。

（1） 遇到變量定義、數(shù)字、自身引用、布爾值都調(diào)用表達(dá)式解析模塊進(jìn)行解析；

（2） 如果有返回值，則調(diào)用返回值表達(dá)式解析；

（3） 遇到左括號(hào)，當(dāng)前層次增加1，遇到右括號(hào)當(dāng)前層次減少1，整段地銷毀原先最內(nèi)層次的變量，括號(hào)平衡（值為0）的話則函數(shù)定義結(jié)束。

（4） while、for、if、print表達(dá)式調(diào)用相應(yīng)的解析模塊進(jìn)行解析。

（5） 最后如果是左小括號(hào)的話，回退一格，進(jìn)行表達(dá)式求值，如果不是，則提示出現(xiàn)編譯錯(cuò)誤。

3.3 class類的解析

Class類的解析過程是：獲取類的名字；探測(cè)是否有繼承符號(hào)，如果有則獲取基類的名字。因?yàn)槲覀円曰惖拿謩?chuàng)建了一個(gè)函數(shù)，所以獲得的詞法標(biāo)記應(yīng)該為一個(gè)API函數(shù)；獲取基類成員并添加基類成員。

（1） 如果有函數(shù)，首先進(jìn)行函數(shù)定義解析，遇到大括號(hào)就跳轉(zhuǎn)，繼續(xù)監(jiān)測(cè)其訪問性與密封性以及類成員變量；

（2） 如果發(fā)現(xiàn)了函數(shù)定義符號(hào)，則調(diào)用函數(shù)定義解析模塊解析，并且檢查是否為一個(gè)API函數(shù)還是一個(gè)普通函數(shù)，添加到函數(shù)列表中，遇到右大括號(hào)則退出。

在沒有到達(dá)文件尾的時(shí)候，循環(huán)進(jìn)行以上操作。

3.4 while循環(huán)語(yǔ)句的解析

首先略過while的判斷表達(dá)式的左小括號(hào)，保留表達(dá)式的位置，稍后再解析。創(chuàng)建第一個(gè)跳轉(zhuǎn)節(jié)點(diǎn)，并且創(chuàng)建與第一個(gè)跳轉(zhuǎn)對(duì)應(yīng)的標(biāo)記，跳過條件表達(dá)式，先解析語(yǔ)句[9]。循環(huán)解析，直到文件結(jié)束或者跳出循環(huán)。

（1） 遇到break或者continue會(huì)插入一些節(jié)點(diǎn)；

（2） 遇到執(zhí)行自身的指針、變量定義、布爾值、數(shù)字、自定義函數(shù)、API函數(shù)將調(diào)用表達(dá)式解析；

（3） 遇到打印操作就調(diào)用打印解析模塊解析；

（4） 遇到返回表達(dá)式就調(diào)用返回解析模塊解析；

（5） 遇到左括號(hào)，當(dāng)前層次增加1，遇到右括號(hào)，當(dāng)前層次減少1，整段地銷毀原先最內(nèi)層次的變量；

（6） 遇到if、while、for就調(diào)用相應(yīng)的解析模塊解析；

3.5 for循環(huán)語(yǔ)句的解析

for循環(huán)是形如for（exp1； exp2；exp3） {..........}的語(yǔ)句，for循環(huán)的解析與while類似，但并不完全相同，其步驟如下：

（1） 創(chuàng)建四個(gè)跳轉(zhuǎn)節(jié)點(diǎn)并且創(chuàng)建四個(gè)與跳轉(zhuǎn)對(duì)應(yīng)的標(biāo)記，允許for語(yǔ)句的首個(gè)表達(dá)式出現(xiàn)定義語(yǔ)句，所以要檢查有無(wú) var關(guān)鍵字，如果有就用token_get（）跳過；

（2） 解析表達(dá)式1，并且保存表達(dá)式2和表達(dá)式3的位置，留著以后解析，并且略過這兩個(gè)表達(dá)式；

（3） 布爾值、數(shù)字、符號(hào)、API、自定義函數(shù)、變量都用解析表達(dá)式模塊解析，返回值表達(dá)式用解析返回值表達(dá)式解析；

（4） 遇到左括號(hào)，當(dāng)前層次增加1，遇到右括號(hào)當(dāng)前層次減少，整段的銷毀原先最內(nèi)層次的變量，如果括號(hào)平衡，則跳出循環(huán)解析表達(dá)式2和表達(dá)式3。這里的兩個(gè)表達(dá)式都屬于for內(nèi)層的語(yǔ)句，但是因?yàn)槭窃谔隽薴or的括號(hào)之后才解析的，所以層次變量layer需要增加1；

（5） if、while、for用相應(yīng)的解析函數(shù)解析；

（6） 如果是左小括號(hào)的話，回退一格，進(jìn)行表達(dá)式求值，如果不是，則提示出現(xiàn)編譯錯(cuò)誤。

把解析后的表達(dá)式放到中間表達(dá)式的節(jié)點(diǎn)中，當(dāng)執(zhí)行到某個(gè)節(jié)點(diǎn)是，取當(dāng)前一個(gè)表達(dá)式的結(jié)果作為返回值，返回給上一層函數(shù)。中間表達(dá)式是一個(gè)五項(xiàng)的結(jié)構(gòu)體。

3.6 if表達(dá)式的解析

if表達(dá)式的解析過程如下：

（1） 略過if的判斷表達(dá)式的左小括號(hào)，先用解析表達(dá)式模塊解析if之后的條件表達(dá)式；

（2） 創(chuàng)建跳轉(zhuǎn)節(jié)點(diǎn)和創(chuàng)建與跳轉(zhuǎn)對(duì)應(yīng)的標(biāo)記，以便把解析后的中間表達(dá)式存放到節(jié)點(diǎn)中；

（3） 略過大括號(hào)，進(jìn)入新層次，并開始循環(huán)。

（4） 遇到操作符的時(shí)候，判斷下一個(gè)字符，如果是左小括號(hào)的話，進(jìn)行表達(dá)式求值，如果不是，則提示出現(xiàn)編譯錯(cuò)誤。

3.7 print解析函數(shù)

該解析函數(shù)調(diào)用表達(dá)式解析函數(shù)，即exp-parse（），并且插入中間節(jié)點(diǎn)。

4 總結(jié)

運(yùn)用編譯原理的知識(shí)，本文實(shí)現(xiàn)了源程序輸入、進(jìn)入緩沖區(qū)、詞法分析、語(yǔ)法分析、生成中間表達(dá)式、用虛擬機(jī)執(zhí)行并返回中間結(jié)果的功能，并對(duì)循環(huán)語(yǔ)句、返回輸出語(yǔ)句、函數(shù)、數(shù)組、判斷語(yǔ)句以及類的繼承進(jìn)行了解析。

第一部分：對(duì)Tina解釋器的功能進(jìn)行簡(jiǎn)單介紹。

第二部分：對(duì)解釋器執(zhí)行的過程進(jìn)行說(shuō)明，主要包括三步，分別為：加載、預(yù)處理、掃描。

第三部分：研究了Tina的代碼結(jié)構(gòu)，對(duì)Tina完成的功能進(jìn)行詳細(xì)的分析，給出每一個(gè)功能解析的詳細(xì)步驟。

參考文獻(xiàn)：

[1] 金龍飛，劉磊. 編譯器前端構(gòu)造工具及JLUCC的實(shí)現(xiàn)[J]. 吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2005（04）.

[2] 付爭(zhēng)方，張海娟. LR語(yǔ)法分析器構(gòu)造方法初探[J]. 中國(guó)科技信息，2005（15）.

[3] Liu Lei， Huang Yi. Achieve bottom-up parsing using recursive descent method[J]. Journal of Jilin University （Information Science Edition），2004 （03） （in Chinese）.

[4] Dou Xun， Wang Ping， Zhou Ming. Recursive descent analysis method in combination query[J]. Microcomputer Development，2004 （06） （in Chinese）.

[5] 宿潔，袁軍鵬. 防火墻技術(shù)及其進(jìn)展[J]. 計(jì)算機(jī)工程與應(yīng)用，2004（09）.

[6] 陳海明，董韞美. 上下文無(wú)關(guān)語(yǔ)言分析樹的一種表示形式[J]. 計(jì)算機(jī)研究與發(fā)展，2000（10）.

[7] Wang Li， Liu Jian. Parser design and implementation of high-level programming language statements[J]. Silicon Valley，2012 （06） （in Chinese）.

[8] Xiang Wei. Implementation and optimization of micro-compiler[D]. University of Electronic Science and Technology，2007（in Chinese）.

[9] 王心光. 虛擬數(shù)控加工通用G代碼編譯器的研究[D]. 浙江大學(xué)， 2005.