面向?qū)嶒?yàn)教學(xué)的可拆卸小型編譯器設(shè)計(jì)

諶志群　王小華

【摘要】“編譯原理”是計(jì)算機(jī)專業(yè)的重要專業(yè)課之一，理論性和實(shí)踐性要求均很高，在計(jì)算機(jī)本科教學(xué)體系中占有十分重要的地位。設(shè)計(jì)實(shí)現(xiàn)了一個(gè)面向“編譯原理”實(shí)驗(yàn)教學(xué)的可拆卸小型編譯器——SMini。詳細(xì)介紹了SMini的系統(tǒng)結(jié)構(gòu)、設(shè)計(jì)方法與實(shí)現(xiàn)技術(shù)。

【關(guān)鍵詞】 編譯原理；編譯器；實(shí)驗(yàn)教學(xué)；可拆卸

【中圖分類號(hào)】G40-057【文獻(xiàn)標(biāo)識(shí)碼】A 【論文編號(hào)】1009—8097（2009）06—0111—03

編譯系統(tǒng)作為計(jì)算機(jī)系統(tǒng)最基本的組成部分，已發(fā)展成為一門具有完整的理論、方法和技術(shù)的計(jì)算機(jī)學(xué)科[1][2]。國(guó)內(nèi)外高校都將“編譯原理”列為計(jì)算機(jī)專業(yè)的主要課程，它對(duì)提高學(xué)生軟件設(shè)計(jì)素養(yǎng)，認(rèn)識(shí)計(jì)算機(jī)信息處理本質(zhì)起著重要作用。“編譯原理”是門實(shí)踐性很強(qiáng)的課程，實(shí)驗(yàn)是課程教學(xué)過程中很重要的一個(gè)環(huán)節(jié)。目前國(guó)內(nèi)的大多數(shù)高校在“編譯原理”課程的實(shí)踐環(huán)節(jié)都是不分授課對(duì)象要求學(xué)生能上機(jī)實(shí)現(xiàn)一個(gè)小型模型語(yǔ)言的完整編譯程序。在只是空洞地學(xué)習(xí)了一些編譯理論與算法并且沒有很好掌握的情況下，這對(duì)于大部分學(xué)生來說都是不可能完成的任務(wù)。造成很大部分學(xué)生在動(dòng)手之前就早早放棄了努力，也就不可能達(dá)到預(yù)定的實(shí)驗(yàn)效果。為了解決這個(gè)問題，在教學(xué)實(shí)踐中，設(shè)計(jì)了一個(gè)簡(jiǎn)單的具有高級(jí)語(yǔ)言主要特點(diǎn)的模型語(yǔ)言（本文稱S語(yǔ)言），設(shè)計(jì)了該語(yǔ)言的目標(biāo)代碼格式，實(shí)現(xiàn)了從源語(yǔ)言到目標(biāo)代碼轉(zhuǎn)化的小型編譯器（本文稱SMini）的各個(gè)模塊，給出了模塊之間接口的定義。模塊是可拆卸的，在實(shí)驗(yàn)教學(xué)時(shí)可根據(jù)實(shí)際情況要求學(xué)生實(shí)現(xiàn)S語(yǔ)言編譯系統(tǒng)的部分模塊，并且實(shí)現(xiàn)的模塊可以方便地嵌入到SMini中進(jìn)行測(cè)試。本文詳細(xì)介紹了SMini編譯器的系統(tǒng)結(jié)構(gòu)、核心模塊的設(shè)計(jì)方法與實(shí)現(xiàn)技術(shù)。

一 模型語(yǔ)言

本文設(shè)計(jì)的模型語(yǔ)言（S語(yǔ)言）的文法用類產(chǎn)生式系統(tǒng)描述如下：

（1） <程序>→[<常量說明>][<變量說明>]<語(yǔ)句>

（2） <常量說明>→Const <常量定義>{，<常量定義>}；

（3） <常量定義>→<標(biāo)識(shí)符>＝<無符號(hào)整數(shù)>

（4） <無符號(hào)整數(shù)>→<數(shù)字>{<數(shù)字>}

（5） <字母>→a|b|c| … |z

（6） <數(shù)字>→0|1|2| … |9

（7） <標(biāo)識(shí)符>→<字母>{<字母>|<數(shù)字>}

（8） <變量說明>→Var <標(biāo)識(shí)符>{，<標(biāo)識(shí)符>}；

（9） <語(yǔ)句>→<賦值語(yǔ)句>|<條件語(yǔ)句>|<當(dāng)循環(huán)語(yǔ)句>|<讀入語(yǔ)句>|<輸出語(yǔ)句>|<復(fù)合語(yǔ)句>|ε

（10） <賦值語(yǔ)句>→<標(biāo)識(shí)符>＝<表達(dá)式>;

（11） <表達(dá)式>→[＋|－]<項(xiàng)>{<加法運(yùn)算符><項(xiàng)>}

（12） <項(xiàng)>→<因子>{<乘法運(yùn)算符><因子>}

（13） <因子>→<標(biāo)識(shí)符>|<無符號(hào)整數(shù)>|‘(<表達(dá)式>‘)

（14） <加法運(yùn)算符>→＋|－

（15） <乘法運(yùn)算符>→* |／

（16） <條件語(yǔ)句>→if <條件> then <語(yǔ)句>| if <條件> then <語(yǔ)句> else <語(yǔ)句>

（17） <條件>→<表達(dá)式><關(guān)系運(yùn)算符><表達(dá)式>

（18） <關(guān)系運(yùn)算符>→＝＝|＜＝|＜|＞|＞＝|＜＞

（19） <當(dāng)循環(huán)語(yǔ)句>→while <條件> do <語(yǔ)句>

（20） <復(fù)合語(yǔ)句>→begin <語(yǔ)句>{；<語(yǔ)句>} end

注：產(chǎn)生式中<、>括起的部分表示一個(gè)非終結(jié)符號(hào)，[、]括起的部分表示可選項(xiàng)，{、}括起的部分表示可重復(fù)，符號(hào) | 表示“或”。

上述模型語(yǔ)言具有高級(jí)程序設(shè)計(jì)語(yǔ)言的主要特點(diǎn)，也是SMini編譯器處理的源語(yǔ)言。

二 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

1 系統(tǒng)結(jié)構(gòu)

整個(gè)系統(tǒng)由3個(gè)模塊構(gòu)成，包括源程序編輯模塊、編譯模塊和信息輸出模塊。各個(gè)模塊又包含若干子模塊。系統(tǒng)結(jié)構(gòu)如圖1所示。

源程序編輯模塊主要實(shí)現(xiàn)源程序的 編輯的工作，在主屏幕窗口中可以輸入、修改源程序，通過菜單欄可以新建 、打開、保存S語(yǔ)言源代碼文件。編譯模塊完成實(shí)際的編譯功能，分為4個(gè)子步驟：詞法分析、語(yǔ)法分析、語(yǔ)義分析、目標(biāo)代碼生成。信息輸出模塊有兩個(gè)子模塊：錯(cuò)誤信息輸出和中間結(jié)果輸出。錯(cuò)誤信息輸出子模塊實(shí)時(shí)輸出編譯時(shí)刻的錯(cuò)誤信息。中間結(jié)果輸出子模塊通過一個(gè)窗口來察看編譯信息文件，包括詞法分析結(jié)果，語(yǔ)法分析結(jié)果（語(yǔ)法樹）， 語(yǔ)義分析結(jié)果（符號(hào)表）和三地址代碼。為了屏蔽機(jī)器代碼的復(fù)雜性，SMini采用三地址代碼作為目標(biāo)代碼。

2 核心模塊設(shè)計(jì)

（1） 詞法分析模塊

詞法分析模塊的主要功能是識(shí)別S語(yǔ)言源程序中的記號(hào)（Token）。Token的識(shí)別由函數(shù)getToken來完成。函數(shù)getToken每次被調(diào)用時(shí)從輸入緩沖區(qū)中讀入輸入字符序列并識(shí)別一個(gè)Token。該函數(shù)采用基于DFA狀態(tài)轉(zhuǎn)換圖的算法，起始狀態(tài)為START，結(jié)束狀態(tài)為DONE。每次調(diào)用，該函數(shù)從起始狀態(tài)START開始，不斷調(diào)用getNextChar函數(shù)，根據(jù)其返回值進(jìn)行相應(yīng)的狀態(tài)轉(zhuǎn)移，一直到當(dāng)前狀態(tài)為DONE為止。函數(shù)中使用另一個(gè)變量save用來指定是否將讀入的字符存入全局變量tokenString中。一般來說，構(gòu)成一個(gè)Token的所有有效字符都將被存入tokenString，而空白，注釋和將被退回的字符不被存入tokenString。此外，如果編譯選項(xiàng)TraceScan被設(shè)為真，該函數(shù)還將調(diào)用函數(shù)printToken打印當(dāng)前Token的有關(guān)信息到編譯信息文件中，包括行號(hào)和Token的類型。

（2） 語(yǔ)法分析模塊

語(yǔ)法分析模塊的功能是以詞法分析程序生成的Token序列作為輸入，在分析過程中驗(yàn)證這個(gè)Token序列是否符合S語(yǔ)言的文法。若是，則以語(yǔ)法樹作為輸出；若不是則指明錯(cuò)誤，并指出錯(cuò)誤的性質(zhì)和位置。關(guān)鍵問題是建立語(yǔ)法樹，這里采用了自頂向下的遞歸分析法來實(shí)現(xiàn)，即為每一條產(chǎn)生式寫一個(gè)match函數(shù)，從頂部（樹根）到底部（樹葉）來建立語(yǔ)法樹。match函數(shù)的基本邏輯是根據(jù)S語(yǔ)言文法比較實(shí)際的Token與預(yù)計(jì)的Token是否一致，如果一致則取下一個(gè)Token，如果不一致則給出錯(cuò)誤類型并調(diào)用syntaxError函數(shù)輸出錯(cuò)誤。實(shí)際的語(yǔ)法樹是以為文本形式輸出的。語(yǔ)法樹中的父子關(guān)系由文本行開頭的數(shù)字序列和嵌套關(guān)系來體現(xiàn)。如一個(gè)簡(jiǎn)單語(yǔ)句“while a>0 do a=a-1;”的語(yǔ)法樹如圖2所示。

圖2 語(yǔ)法樹的文本輸出形式

（3） 語(yǔ)義分析模塊

語(yǔ)義分析部分的主要功能是遍歷語(yǔ)法分析時(shí)建立的語(yǔ)法樹，建立符號(hào)表并進(jìn)行簡(jiǎn)單的類型檢查，即判斷源程序中語(yǔ)句部分中的變量是否已定義和是否賦值給常量。S語(yǔ)言沒有作用域信息，并且所有的變量都是整型，符號(hào)表數(shù)據(jù)結(jié)構(gòu)BucketList設(shè)計(jì)如下：

typedef struct LineListRec

{ int lineno;

struct LineListRec * next;

} * LineList;

其中：lineno為常量或變量所在的行的行號(hào)，next指向下一同類型標(biāo)識(shí)符。

（4） 目標(biāo)代碼生成模塊

目標(biāo)代碼生成部分的主要功能是生成與源程序等價(jià)的三地址代碼。主要函數(shù)是CGen::cGen( TreeNode * tree,int snextl)。由于建立語(yǔ)法樹時(shí)語(yǔ)句和表達(dá)式都是FirstK類型的結(jié)點(diǎn)，所以它僅檢測(cè)此類型的節(jié)點(diǎn)，并根據(jù)不同的分類作相應(yīng)處理，然后遞歸調(diào)用 自身完成對(duì)整個(gè)語(yǔ)法樹的遍歷。例：語(yǔ)句“while a>0 do a=a-1;”對(duì)應(yīng)的三地址代碼如圖3所示。

圖3 三地址代碼序列

3 系統(tǒng)實(shí)現(xiàn)與界面設(shè)計(jì)

SMini在Visual C++集成環(huán)境[3]下開發(fā)。首先用MFC AppWizard創(chuàng)建工程文件，建立后會(huì)自動(dòng)生成文件：應(yīng)用程序：CsminiApp類，框架：CmainFrame類，文檔：CsminiDoc類，視窗：CsminiView類，對(duì)話框有關(guān)的CaboutDlg類，還包括了一些在主框架中的初始化工具條的工作，在此基礎(chǔ)上實(shí)現(xiàn)具體的功能與界面。軟件界面采用單文檔構(gòu)架，拆分窗口視圖，界面主要分為五個(gè)部分：菜單欄、工具欄、編輯區(qū)、信息輸出區(qū)和狀態(tài)欄。操作方法與目前流行的編譯器相似，可通過窗口實(shí)現(xiàn)源程序的編輯、修改、編譯與信息察看。系統(tǒng)主界面如圖4所示。

圖4 系統(tǒng)界面

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

“編譯原理”課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的主干必修課，也是軟件工程專業(yè)的重要專業(yè)基礎(chǔ)課。實(shí)驗(yàn)教學(xué)是“編譯原理”課程教學(xué)的重要環(huán)節(jié)也是薄弱環(huán)節(jié)，通過開發(fā)輔助實(shí)驗(yàn)教學(xué)系統(tǒng)提高課程實(shí)驗(yàn)教學(xué)的效果具有現(xiàn)實(shí)意義。設(shè)計(jì)開發(fā)了一個(gè)簡(jiǎn)單模型語(yǔ)言的可拆卸編譯器，可輔助課程實(shí)踐環(huán)節(jié)的教學(xué)，解決了以往由于設(shè)計(jì)一個(gè)完整的編譯器難度與工作量太大，造成實(shí)驗(yàn)效果不好的弊端。該系統(tǒng)還可提高教師驗(yàn)收學(xué)生實(shí)驗(yàn)成果的效率，在實(shí)際的教學(xué)過程中已取得了較好的效果。

參考文獻(xiàn)

[1] Alfred V Aho, Ravi Sethi, Jeffrey D Ullman. Compilers:Principles,Techniques,and Tools[M].北京:人民郵電出版社,2002:1-24.

[2] 張素琴,呂映芝,蔣維杜等.編譯原理(第2版)[M].北京:清華大學(xué)出版社,2005:1-11.

[3] 朱磊,周彬.Windows下的C/C++高級(jí)編程[M].北京:人民郵電出版社,2002:1-120.

Dismountable Mini Compiler Design for Experiment Teaching

CHEN Zhi-qun WANG Xiao-hua

(Institute of Computer Application Technology, Hangzhou Dianzi University, Hangzhou, Zhejiang, 310018, China)

Abstract: Compiler principle is one of the important specialized courses in the computer science, requiring highly both in theory and practice, and it occupy the essential position in the computer's teaching system. SMini- a dismountable mini compiler for experiment teaching of compiler principle is implemented. This paper introduces the system architecture, design method and implementation technology of SMini.

Keywords: Compiler Principle; Compiler; Experiment Teaching; Dismountability