許高建, 徐浩宇

(安徽農(nóng)業(yè)大學 信息與計算機學院， 安徽 合肥 230036)

編譯原理是計算機科學與技術(shù)專業(yè)本科生的必修課程，原理相對復雜，課時較長，基本概念抽象，本科生理解比較困難，在教學的過程中需要探索出一種更好的教學方式。程序設計語言中的編譯技術(shù)，是把高級語言編寫的程序翻譯成等價的目標程序或機器語言，在計算機領(lǐng)域中很多方面得到應用[1]。例如：文本編輯器、信息檢索系統(tǒng)、模式識別器、排版和繪圖系統(tǒng)。為了讓大學本科生更好地理解編譯原理，在本課程后期帶領(lǐng)學生使用面向?qū)ο蟮某绦蛟O計語言Python從零開發(fā)出一款類C語言編譯器，讓學生更好地理解編譯原理。

1 編譯器的分析與設計

該編譯器主要由兩大模塊組成：文法分析模塊與語法分析模塊。

文法分析模塊：由用戶將類C文法文件輸入程序，可以實現(xiàn)求first集和follow集，最終生成LL分析表等功能。該模塊嵌入到main.py中，按照其特性進行遞歸匹配、生成。

語法分析模塊：用戶將類C程序文檔輸入程序，按照順序進行詞法分析、語法分析，生成四元式，最終生成匯編語言。詞法分析器作為一個函數(shù)提供給語法分析器。該函數(shù)對關(guān)鍵字、標識符、常數(shù)、運算符和分界符等分別進行編號，并對輸入程序進行匹配，在每次調(diào)用時返回詞法分析后的字符串和詞法屬性。

LL分析法主要識別結(jié)構(gòu)簡單但是需要處理較多細節(jié)的部分。該方法對于文法的要求很高，不能有左遞歸和公共左因子。為了減少代碼修改，對于輸入文法，經(jīng)過預處理后，自動求得該文法的LL分析表，不需要對分析器本身進行修改。語義分析上采用了屬性文法的方法，歸約時執(zhí)行語義動作。

目標代碼生成采用寄存器分配方法。首先分配寄存器，處理操作數(shù)尋址方式，生成對應的目標代碼，然后生成運算部分的目標代碼。處理了算法細節(jié)使算法更加健壯完備，生成基于IntelX8086的匯編指令代碼。

2 算法設計

2.1 文法分析模塊算法流程

文法分析模塊流程圖如圖1所示。

圖1 文法分析流程圖

(1) first集、follow集、LL分析表算法

① 求first集

文法G的任何符號串a(chǎn)=X1，X2，X3…Xn構(gòu)造集合first(a)[2]。置first(a)=first(X1)/e(e為空串)；若對任何1≤j≤i-1，e屬于first(Xj)，就把first(Xj)中e以外的元素加到first(a)中；若所有first(Xj)均含有e，1≤j≤n，則將e加至first(a)中。流程圖如圖2所示。

圖2 求first集流程圖

② 求follow集

對于文法的開始符號S，置#到follow中；若A→aBb是一個產(chǎn)生式，則將first(B)/e加到first(B)中；若A→aB是一個產(chǎn)生式，或者A→aBb是一個產(chǎn)生式，而b的first集合中包含空串，則將follow(A)加到follow(B)中。求follow集流程圖如圖3所示。

圖3 求follow集流程圖

③ 求LL分析表

預測分析表示一個M(A,a)形式的矩陣,其中A為非終結(jié)符，a為終結(jié)符或者‘#’。矩陣元素M(A,a)中存放著一條關(guān)于A的產(chǎn)生式，指出當A面臨輸入符號a時所應采用的候選。M(A,a)中也可能存放一個“出錯標志”，指出A根本不該面臨輸入符號a。LL分析表算法如表1所示。

表1 LL分析表算法

2.2 編譯器

(1) 算法的總體思路

編譯器的邏輯階段必不可少的部分：詞法分析、語法分析、語義分析和目標代碼生成。 編譯器前端使用了以語法分析為中心的方法。詞法分析器作為一個封裝類提供給語法分析器，詞法分析器的輸入為文檔，輸出為下一步LL語法分析所需字符串。LL分析法中，采用了上一步產(chǎn)生的LL分析表，將語法動作插入到產(chǎn)生式中。在分析過程中填寫符號表，進行類型檢查的判斷。只需將符號表傳遞給后端，降低了編碼復雜性。

在LL部分，修改與新建文法只需要修改儲存文法的文件即可，不需要對分析器本身進行修改。

通過得到四元式序列，目標代碼生成算法處理序列得到目標匯編指令。目標代碼生成分配寄存器，處理操作數(shù)尋址方式，并生成對應的目標代碼，然后生成運算部分的目標代碼[3]。

(2) 詞法分析器

詞法分析器主要功能是為語法分析器提供轉(zhuǎn)義字符串[4]。詞法分析器將準備編譯的源代碼作為輸入，利用設計好的有限自動機的狀態(tài)轉(zhuǎn)移函數(shù)(關(guān)鍵字與文法符號轉(zhuǎn)換)，實現(xiàn)狀態(tài)的轉(zhuǎn)移和對語句的分詞功能。根據(jù)終結(jié)狀態(tài)將分詞劃分為五大類：關(guān)鍵字、標識符、界符、運算符和常數(shù)。

詞法分析器從左往右進行掃描源程序，分離出一個個單詞，識別其類別，并按照二元式(類別，單詞值)進行輸出，流程圖如圖4所示。

詞法結(jié)構(gòu)定義：

##關(guān)鍵字

key_world_list = ["while","if","else","return","void","main","printf","int","scanf"]

key_translate_list = ["t","w","u","s","z","y","r","x","f"]

##標識符

flag_world_list = [chr(i) for i in range(97,122)] #添加a-z

##常數(shù)

constant_world_list = [chr(i) for i in range(48,57)] #添加0-9

##運算符

operator_world_list = ["+","-","*","/","=",">","<","==","!="]

##界符

delimiter_world_list = [";","{","}","(",")"]

圖4 詞法分析流程圖

(3)語法分析器

語法分析的任務是接收詞法分析的結(jié)果，按照定義的語法規(guī)則檢查語句的合法性。語法分析也叫層次分析，按照語法的層次，可以由下而上，也可以自上而下進行語法分析。

本文設計的語法分析器，選擇自上而下分析法，文法必須是LL文法，輸入為詞法分析器產(chǎn)生的轉(zhuǎn)義字符串，根據(jù)文法分析器生成的LL分析表，進行語法分析，為后續(xù)的四元式產(chǎn)生及語義分析做前置準備工作。語法分析的同時可以利用符號表中的信息進行類型檢查。

(4)語義分析與中間代碼生成(產(chǎn)生四元式)

語義分析是依據(jù)規(guī)則對識別出的各種語法分析其含義，進行初步翻譯，生成中間代碼。語義分析分為靜態(tài)和動態(tài)分析兩種，靜態(tài)主要是檢查語義成分的合法性，比如操作數(shù)的類型是否一致等；動態(tài)主要是檢查語義成分的作用域、運行時的存儲器分配等。

根據(jù)輸入的語義動作進行語法制導翻譯，通過文法分析中自動生成的LL分析表，將動作當作文法右部變元同等處理，逆序壓入棧，當遇到語義動作的非終結(jié)符時，執(zhí)行相應的語義動作，同時將產(chǎn)生的四元式輸出并存儲，作為代碼生成的輸入部分，產(chǎn)生四元式。

(5)目標代碼生成

目標代碼生成模塊將四元式和對應的變量活躍信息作為輸入，生成表達式語句、條件語句if-else、循環(huán)語句while和跳轉(zhuǎn)語句goto的目標代碼(匯編語言)，生成的目標代碼為基于單寄存器的類匯編語言代碼。

3 編譯器實現(xiàn)

3.1 編譯器程序設計流程圖

Python語言是面向?qū)ο?、解釋性特別好的腳本語言，同時也是可讀性強、功能強大而完善的通用型語言[6]。本設計中使用遞歸下降法自頂向下進行編寫，程序設計流程圖如圖5所示。

圖5 程序設計流程圖

3.2 程序設計說明

總體算法設計已在上一節(jié)詳述，這里不再詳述，文法的設計由于“void main”類似設計比較麻煩，這里進行了處理，如圖6所示。

圖6 wenfa界面圖

4 系統(tǒng)測試

基于Python語言實現(xiàn)的編譯器GUI界面簡潔，操作簡單，可以實現(xiàn)“文法分析”與“C語言編譯”功能如圖7所示。測試文件為“wenfa.txt”，在載入文法文件“wenfa.txt”之后可以實現(xiàn)“產(chǎn)生式信息”、“求first集”、“求follow集”及“LL分析表”等功能，如圖8所示。

圖7 程序界面 圖8 載入wenfa.txt文件圖

該系統(tǒng)中所有功能均可以正常使用，最終生成的匯編代碼如圖9所示。

圖9 匯編代碼生成示意圖

5 結(jié) 語

本編譯器中只能實現(xiàn)簡單的賦值、循環(huán)和邏輯運算，標識符分別為a、b和c，未能實現(xiàn)加、減、乘、除等數(shù)學運算，系統(tǒng)的可擴展性較好。編譯器容錯性較高，但是在Mac操作系統(tǒng)上運行速度并沒有達到預期效果，與項目整體規(guī)模和算法設計有很大的關(guān)系?？傮w來說達到了教學目的，算法設計有很大的改進空間。可以指導學生在此基礎上把加、減、乘、除、邏輯運算和位運算等功能分批加入到該編譯器中，完善編譯器的功能，優(yōu)化其編譯速度，培養(yǎng)學生的實踐動手能力。在實驗過程中可以讓學生花費較短的時間掌握編譯器的原理，讓學生積極參與課堂教學，活躍課堂氛圍，改變傳統(tǒng)的教學方式，讓學生更好地理解編譯原理，達到教學目的。