許高建, 徐浩宇

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

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

1 編譯器的分析與設(shè)計(jì)

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

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

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

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

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

2 算法設(shè)計(jì)

2.1 文法分析模塊算法流程

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

圖1 文法分析流程圖

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

① 求first集

文法G的任何符號(hào)串a(chǎn)=X1，X2，X3…Xn構(gòu)造集合first(a)[2]。置first(a)=first(X1)/e(e為空串)；若對(duì)任何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集

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

圖3 求follow集流程圖

③ 求LL分析表

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

表1 LL分析表算法

2.2 編譯器

(1) 算法的總體思路

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

在LL部分，修改與新建文法只需要修改儲(chǔ)存文法的文件即可，不需要對(duì)分析器本身進(jìn)行修改。

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

(2) 詞法分析器

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

詞法分析器從左往右進(jìn)行掃描源程序，分離出一個(gè)個(gè)單詞，識(shí)別其類別，并按照二元式(類別，單詞值)進(jìn)行輸出，流程圖如圖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"]

##標(biāo)識(shí)符

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

##運(yùn)算符

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

##界符

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

圖4 詞法分析流程圖

(3)語法分析器

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

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

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

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

根據(jù)輸入的語義動(dòng)作進(jìn)行語法制導(dǎo)翻譯，通過文法分析中自動(dòng)生成的LL分析表，將動(dòng)作當(dāng)作文法右部變?cè)忍幚?，逆序壓入棧，?dāng)遇到語義動(dòng)作的非終結(jié)符時(shí)，執(zhí)行相應(yīng)的語義動(dòng)作，同時(shí)將產(chǎn)生的四元式輸出并存儲(chǔ)，作為代碼生成的輸入部分，產(chǎn)生四元式。

(5)目標(biāo)代碼生成

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

3 編譯器實(shí)現(xiàn)

3.1 編譯器程序設(shè)計(jì)流程圖

Python語言是面向?qū)ο蟆⒔忉屝蕴貏e好的腳本語言，同時(shí)也是可讀性強(qiáng)、功能強(qiáng)大而完善的通用型語言[6]。本設(shè)計(jì)中使用遞歸下降法自頂向下進(jìn)行編寫，程序設(shè)計(jì)流程圖如圖5所示。

圖5 程序設(shè)計(jì)流程圖

3.2 程序設(shè)計(jì)說明

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

圖6 wenfa界面圖

4 系統(tǒng)測(cè)試

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

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

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

圖9 匯編代碼生成示意圖

5 結(jié) 語

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