面向實驗教學的可拆卸小型編譯器設計

諶志群　王小華

【摘要】“編譯原理”是計算機專業的重要專業課之一，理論性和實踐性要求均很高，在計算機本科教學體系中占有十分重要的地位。設計實現了一個面向“編譯原理”實驗教學的可拆卸小型編譯器——SMini。詳細介紹了SMini的系統結構、設計方法與實現技術。

【關鍵詞】 編譯原理；編譯器；實驗教學；可拆卸

【中圖分類號】G40-057【文獻標識碼】A 【論文編號】1009—8097（2009）06—0111—03

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

一 模型語言

本文設計的模型語言（S語言）的文法用類產生式系統描述如下：

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

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

（3） <常量定義>→<標識符>＝<無符號整數>

（4） <無符號整數>→<數字>{<數字>}

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

（6） <數字>→0|1|2| … |9

（7） <標識符>→<字母>{<字母>|<數字>}

（8） <變量說明>→Var <標識符>{，<標識符>}；

（9） <語句>→<賦值語句>|<條件語句>|<當循環語句>|<讀入語句>|<輸出語句>|<復合語句>|ε

（10） <賦值語句>→<標識符>＝<表達式>;

（11） <表達式>→[＋|－]<項>{<加法運算符><項>}

（12） <項>→<因子>{<乘法運算符><因子>}

（13） <因子>→<標識符>|<無符號整數>|‘(<表達式>‘)

（14） <加法運算符>→＋|－

（15） <乘法運算符>→* |／

（16） <條件語句>→if <條件> then <語句>| if <條件> then <語句> else <語句>

（17） <條件>→<表達式><關系運算符><表達式>

（18） <關系運算符>→＝＝|＜＝|＜|＞|＞＝|＜＞

（19） <當循環語句>→while <條件> do <語句>

（20） <復合語句>→begin <語句>{；<語句>} end

注：產生式中<、>括起的部分表示一個非終結符號，[、]括起的部分表示可選項，{、}括起的部分表示可重復，符號 | 表示“或”。

上述模型語言具有高級程序設計語言的主要特點，也是SMini編譯器處理的源語言。

二 系統設計與實現

1 系統結構

整個系統由3個模塊構成，包括源程序編輯模塊、編譯模塊和信息輸出模塊。各個模塊又包含若干子模塊。系統結構如圖1所示。

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

2 核心模塊設計

（1） 詞法分析模塊

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

（2） 語法分析模塊

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

圖2 語法樹的文本輸出形式

（3） 語義分析模塊

語義分析部分的主要功能是遍歷語法分析時建立的語法樹，建立符號表并進行簡單的類型檢查，即判斷源程序中語句部分中的變量是否已定義和是否賦值給常量。S語言沒有作用域信息，并且所有的變量都是整型，符號表數據結構BucketList設計如下：

typedef struct LineListRec

{ int lineno;

struct LineListRec * next;

} * LineList;

其中：lineno為常量或變量所在的行的行號，next指向下一同類型標識符。

（4） 目標代碼生成模塊

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

圖3 三地址代碼序列

3 系統實現與界面設計

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

圖4 系統界面

三 結束語

“編譯原理”課程是計算機科學與技術專業的主干必修課，也是軟件工程專業的重要專業基礎課。實驗教學是“編譯原理”課程教學的重要環節也是薄弱環節，通過開發輔助實驗教學系統提高課程實驗教學的效果具有現實意義。設計開發了一個簡單模型語言的可拆卸編譯器，可輔助課程實踐環節的教學，解決了以往由于設計一個完整的編譯器難度與工作量太大，造成實驗效果不好的弊端。該系統還可提高教師驗收學生實驗成果的效率，在實際的教學過程中已取得了較好的效果。

參考文獻

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

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

[3] 朱磊,周彬.Windows下的C/C++高級編程[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