1、提供全套畢業(yè)論文，各專業(yè)都有課 程 設(shè) 計(jì) 報(bào) 告 設(shè)計(jì)題目：簡單文法的編譯器的設(shè)計(jì)與實(shí)現(xiàn)班 級：計(jì)算機(jī)1206組長學(xué)號：組長姓名：指導(dǎo)教師：設(shè)計(jì)時間：2014年12月 摘 要 編譯原理是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)一門重要的專業(yè)課,它具有很強(qiáng)的理論性與實(shí)踐性，目的是系統(tǒng)地向?qū)W生介紹編譯系統(tǒng)的結(jié)構(gòu)、工作原理以及編譯程序各組成部分的設(shè)計(jì)原理和實(shí)現(xiàn)技術(shù)，在計(jì)算機(jī)本科教學(xué)中占有十分重要的地位。計(jì)算機(jī)語言之所以能由單一的機(jī)器語言發(fā)展到現(xiàn)今的數(shù)千種高級語言，就是因?yàn)橛辛司幾g技術(shù)。編譯技術(shù)是計(jì)算機(jī)科學(xué)中發(fā)展得最迅速、最成熟的一個分支，它集中體現(xiàn)了計(jì)算機(jī)發(fā)展的成果與精華。 本課設(shè)是詞法分析、語法分析、語義分析的綜合

2、，外加上擴(kuò)展任務(wù)中間代碼的優(yōu)化和目標(biāo)代碼的生成，主要是鍛煉學(xué)生的邏輯思維能力，進(jìn)一步理解編譯原理的方法和步驟。關(guān)鍵詞：編譯原理，前端，目標(biāo)代碼，后端 目 錄摘要.3 1. 概述.6 2. 課程設(shè)計(jì)任務(wù)及要求.8 2.1 設(shè)計(jì)任務(wù).8 2.2 設(shè)計(jì)要求.9 3. 算法及數(shù)據(jù)結(jié)構(gòu).10 3.1算法的總體思想.10 3.2 詞法分析器模塊.11 3.2.1 功能.11 3.2.2 數(shù)據(jù)結(jié)構(gòu).11 3.2.3 算法.12 3.3 語法分析器模塊.13 3.3.1功能.13 3.3.2 數(shù)據(jù)結(jié)構(gòu).13 3.3.3算法.14 3.4 中間代碼產(chǎn)生器模塊.24 3.4.1 功能.24 3.4.2 數(shù)據(jù)結(jié)構(gòu).

3、24 3.4.3 算法.25 3.5 優(yōu)化器模塊.27 3.5.1 功能.27 3.5.2 數(shù)據(jù)結(jié)構(gòu).27 3.5.3 算法.283.6 目標(biāo)代碼生成器模塊.30 3.6.1功能.30 3.6.2 數(shù)據(jù)結(jié)構(gòu).30 3.6.3 算法.31 4. 程序設(shè)計(jì)與實(shí)現(xiàn).32 4.1 程序流程圖.32 4.2 程序說明.33 4.3 實(shí)驗(yàn)結(jié)果.355. 結(jié)論.426. 參考文獻(xiàn).437. 收獲、體會和建議.44 1 概述 在計(jì)算機(jī)上執(zhí)行一個高級語言程序一般要分為兩步；第一步，用一個編譯程序把高級語言翻譯成機(jī)器語言程序；第二步，運(yùn)行所得的機(jī)器語言程序求得計(jì)算結(jié)果。在學(xué)習(xí)編譯原理課程過程中，逐漸掌握各章節(jié)構(gòu)造

4、編譯程序的基本理論，并能獨(dú)立完成詞法分析器、語法分析器和語義分析器實(shí)驗(yàn)，在基本實(shí)驗(yàn)完成的基礎(chǔ)上，逐步完成課程設(shè)計(jì)。針對自己的理解和學(xué)習(xí)，實(shí)現(xiàn)一個小編譯器括符號表的構(gòu)造。 編譯程序的工作過程一般可以劃分為五個階段：詞法分析、語法分析、語義分析和中間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼生成。 第一階段，詞法分析。詞法分析的任務(wù)是：輸入源程序，對構(gòu)成源程序的字符串進(jìn)行分解和掃描，識別出一個個的單詞或符號。我們設(shè)計(jì)了符號表，包括名字欄和信息欄，其中名字欄作為關(guān)鍵字，根據(jù)給定的名字，在符號表中查找其信息。如果該名字在符號表中不存在，則將其加入到符號表中，否則返回指向該名字的指針，從符號表中刪除給定名字的表項(xiàng)，并且設(shè)

5、計(jì)了詞法分析器，具體實(shí)現(xiàn)為設(shè)計(jì)各單詞的狀態(tài)轉(zhuǎn)換圖，并為不同的單詞設(shè)計(jì)種別碼。將詞法分析器設(shè)計(jì)成供語法分析器調(diào)用的子程序。詞法分析器具備預(yù)處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設(shè)計(jì)一個供詞法分析調(diào)用的預(yù)處理子程序；，能夠拼出語言中的各個單詞，將拼出的標(biāo)識符填入符號表，返回識別單詞或符號的種別碼和屬性值。 第二階段，語法分析。在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位。通過語法分析，確定整個輸入串是否構(gòu)成語法上正確的“程序”。我們實(shí)現(xiàn)了語法分析器，能夠使用預(yù)測分析法、遞歸下降分析法、算符優(yōu)先分析法、SLR分析法實(shí)現(xiàn)對表達(dá)式、各種說明語句、控制

6、語句進(jìn)行語法分析。 第三階段，語義分析和中間代碼產(chǎn)生。對語法分析所識別的各類語法范疇，分析其含義，并進(jìn)行初步翻譯(產(chǎn)生中間代碼）。這一階段包括兩個方面的工作。首先，對每種語法范疇進(jìn)行靜態(tài)語義檢查。如果語義正確，則依循語言的語義規(guī)則進(jìn)行中間代碼的翻譯。 第四階段，優(yōu)化。優(yōu)化的任務(wù)在于對前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效的目標(biāo)代碼。例如公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼。 第五階段，目標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級語言代碼，有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義來實(shí)現(xiàn)最后的翻譯。在能完成指定寄存器個數(shù)的情況下將一中間代碼程序段翻譯成匯編語言目標(biāo)代碼。 通

7、過對編譯器的設(shè)計(jì)實(shí)現(xiàn)，一方面再次熟悉了c語言的編程方法及思想，另一方面加深了而對所學(xué)編譯知識的掌握和理解，也深刻的理解了編譯器的思想和實(shí)現(xiàn)方法；從詞法分析到語法分析，再到語義分析，整個獨(dú)立而又緊密聯(lián)系的環(huán)節(jié)，緊緊相扣，整體的實(shí)現(xiàn)理解的更加透徹。不過由于編譯程序本身涉及到詞法分析、語法分析、代碼生成、錯誤恢復(fù)和優(yōu)化等諸多模塊，要在實(shí)驗(yàn)中做到面面俱到不太可能，所以本編譯器不可避免的會存在各種問題，但作為一個具有基本功能的、可擴(kuò)充的系統(tǒng)，完全達(dá)到了鞏固編譯原理的理論知識，并將其運(yùn)用于實(shí)踐的目的。 2 課程設(shè)計(jì)任務(wù)及要求2.1 設(shè)計(jì)任務(wù)任務(wù)內(nèi)容：定義一個簡單程序設(shè)計(jì)語言文法（包括變量說明語句、算術(shù)運(yùn)算

8、表達(dá)式、賦值語句；擴(kuò)展包括邏輯運(yùn)算表達(dá)式、If語句、While語句等）；掃描器設(shè)計(jì)實(shí)現(xiàn)；語法分析器設(shè)計(jì)實(shí)現(xiàn)；中間代碼設(shè)計(jì)；中間代碼生成器設(shè)計(jì)實(shí)現(xiàn)；中間代碼優(yōu)化；生成目標(biāo)代碼。 分析完任務(wù)內(nèi)容，我們制定出一套滿足老師要求的語句的文法結(jié)構(gòu)，具體內(nèi)容如下（其中“？”代表空產(chǎn)生式）：程序-void main ()函數(shù)體函數(shù)體-變量聲明語句 函數(shù)體|賦值語句 函數(shù)體|if(表達(dá)式)函數(shù)體else函數(shù)體函數(shù)體|while(表達(dá)式)函數(shù)體 函數(shù)體|?變量聲明語句-類型 標(biāo)識符 變量聲明語句_1 ;類型-int |char |bool變量聲明語句_1-,標(biāo)識符 變量聲明語句_1 |=表達(dá)式 變量聲明語句_1|

9、?賦值語句-標(biāo)識符=表達(dá)式;表達(dá)式-算數(shù)表達(dá)式 邏輯表達(dá)式邏輯表達(dá)式- =算數(shù)表達(dá)式|T E1E1-+ T E1|- T E1|?T-F T1T1-* F T1|/ F T1|?F-標(biāo)識符常數(shù)|(E)這個文法滿足老師的要求，但是也存在一些不足，比如變量類型中沒有處理實(shí)數(shù)，數(shù)組和結(jié)構(gòu)體以及if語句和while語句后必須有大括弧匹配。2.2 設(shè)計(jì)要求 1、在深入理解編譯原理基本原理的基礎(chǔ)上，對于選定的題目，以小組為單位，先確定設(shè)計(jì)方案；2、設(shè)計(jì)系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)，設(shè)計(jì)每個模塊的處理流程。要求設(shè)計(jì)合理；3、編程序?qū)崿F(xiàn)系統(tǒng)，要求實(shí)現(xiàn)可視化的運(yùn)行界面，界面應(yīng)清楚地反映出系統(tǒng)的運(yùn)行結(jié)果；4、確定測試

10、方案，選擇測試用例，對系統(tǒng)進(jìn)行測試；5、運(yùn)行系統(tǒng)并要通過驗(yàn)收，講解運(yùn)行結(jié)果，說明系統(tǒng)的特色和創(chuàng)新之處，并回答指導(dǎo)教師的提問； 3 算法及數(shù)據(jù)結(jié)構(gòu) 3.1 算法的總體思想 詞法分析器又稱為掃描器，它的任務(wù)就是對輸入的源程序進(jìn)行詞法分析輸出單詞符號供語法分析使用，語法分析器簡稱分析器，對單詞符號串進(jìn)行語法分析，根據(jù)語法規(guī)則進(jìn)行推導(dǎo)，識別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序”。語義分析與中間代碼產(chǎn)生器，按照語義規(guī)則對語法分析器推導(dǎo)出的語法單位進(jìn)行語義分析并把它們翻譯成一定形式的中間代碼。優(yōu)化器就是對中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成器，把中間代碼翻譯成目標(biāo)程序。符號表用來登記源程

11、序中出現(xiàn)的變量及其屬性。另外，如果源程序有錯誤，編譯發(fā)現(xiàn)錯誤，把有關(guān)錯誤信息報(bào)告給用戶，即出錯處理。流程圖如下： 出 錯 處 理 符 號 表 詞法分析器 源程序 語法分析器 單詞符號 優(yōu)化器 語義分析及中間代碼產(chǎn)生器 語法單位 目標(biāo)代碼生成器 中間代碼 中間代碼 目標(biāo)代碼3.2 詞法分析器模塊 3.2.1 功能 詞法分析器功能室輸入源程序，輸出單詞符號。單詞符號是一個程序語言的基本語法符號。程序語言的單詞符號一般可分為下列5種。 （1）關(guān)鍵字 是由程序語言定義的具有固定億的標(biāo)識符。有時稱這些標(biāo)識符為保留字或基本字。 （2）標(biāo)識符 用來標(biāo)示各種名字，如變量名，數(shù)組名，函數(shù)名等。 （3）常數(shù) 程序

12、中出現(xiàn)用來運(yùn)算的數(shù)值 （4）運(yùn)算符 我們所定義的文法包括+，-，*，/算術(shù)運(yùn)算符，還有and，or，not，=，,四元式的個數(shù) n 出口 y 以上為優(yōu)化器的第一個模塊，構(gòu)造基本塊內(nèi)優(yōu)化的DAG；出口之后是另外一個模塊。該結(jié)點(diǎn)為帶有附加標(biāo)記的葉結(jié)點(diǎn)結(jié)構(gòu)：B|A1，A2.按結(jié)點(diǎn)編碼順序，依次讀取每一結(jié)點(diǎn)信息 入口有兩個假設(shè)：臨時變量的作用域是基本塊內(nèi)非臨時變量的作用域也可以是基本塊內(nèi)。 結(jié)點(diǎn)為帶有附加標(biāo)記的非葉結(jié)點(diǎn)結(jié)構(gòu)： n n A|A1，A2 結(jié)束i結(jié)點(diǎn)個數(shù) 生成A i=A(i=1,2,.)A i為非臨時變量 生成四元式A=B C 生成四元式A i = B (i=1,2,.)A i為非臨時變量

13、y B|. C|. y n y n y 3.6 目標(biāo)代碼生成器模塊 3.6.1 功能 編譯模型的最后一個階段是代碼生成。它以源程序的中間代碼作為輸入，并產(chǎn)生等價(jià)的目標(biāo)程序作為輸出。代碼生成器的輸入包括中間代碼和符號表的信息。代碼生成是把語義分析后或優(yōu)化后的中間代碼換成目標(biāo)代碼。目標(biāo)代碼一般都有三種形式。（1） 能夠立即執(zhí)行的機(jī)器語言代碼，所有地址均已定位。（2） 待裝配的機(jī)器語言模塊。當(dāng)需要執(zhí)行時，由連接裝入程序把它們和某些運(yùn)行程序連接起來，轉(zhuǎn)換成能執(zhí)行的機(jī)器語言代碼。（3） 匯編語言代碼，尚需經(jīng)過匯編程序匯編，轉(zhuǎn)換成可執(zhí)行的機(jī)器語言代碼。 代碼生成主要考慮兩個問題：一是如何使生成的目標(biāo)代碼較

14、短；另一是如何充分利用計(jì)算機(jī)的寄存器，減少目標(biāo)代碼中訪問存儲單元的次數(shù)。這兩個問題都直接影響目標(biāo)代碼的執(zhí)行速度。 再次說明一下，本次課設(shè)沒有涉及基本塊的劃分。 3.6.2 數(shù)據(jù)結(jié)構(gòu) typedef struct CODEchar *op;/匯編操作指令char *op1;/第一操作數(shù)char *op2;/第二操作數(shù)CODE;CODE Code1000;目標(biāo)代碼結(jié)構(gòu)體數(shù)組char *R=NULL;/寄存器，里面放的是變量的名，就是一個描述表另外還有一個常用棧的描述。 開始 3.6.3 算法 釋放寄存器 編寫目標(biāo)指令 取下一四元式 變量信息生成 結(jié)束 結(jié)束處理 取到了 取下一基本塊 預(yù)處理 n y

15、 基本塊出口 y n 4 程序設(shè)計(jì)與實(shí)現(xiàn)4.1程序流程圖 錯誤輸出中間代碼產(chǎn)生器 目標(biāo)代碼生成器 結(jié)束 優(yōu)化器有錯誤 語法分析器 詞法分析器 開始 程序的總體流程圖如下： y n 各個模塊的程序具體流程圖參考第3節(jié)。4.2 程序說明main()： 調(diào)用子模塊的功能InitStack(S);初始化一個棧結(jié)構(gòu)cifa_main();調(diào)用詞法分析功能yufa_main();調(diào)用語法分析功能output_yuyi();輸出四元式序列詞法分析：cifa_main(): 詞法分析可以生成Token序列及靜態(tài)符號表并輸出IsLetter():判斷字符是否為字母IsDigit():判斷字符是否為數(shù)字IsKey

16、():判斷是否為關(guān)鍵字IsDefinition():判斷是否為界符InsertID():向符號表中添加標(biāo)示符（可判斷符號表之前是否已存在此標(biāo)示符）InsertConst():向符號表中添加數(shù)字（可判斷符號表之前是否已存在此數(shù)字）語法分析,及中間代碼生成： 遞歸下降子程序：判斷文法是否正確，并輸出自上而下的推導(dǎo)過程 輸出錯誤情況 插入語義動作并生成未優(yōu)化的四元式 儲存原始的四元式編譯后端（四元式的優(yōu)化）：DAG_Main():四元式優(yōu)化的主函數(shù)QuatBelongToNumber():判斷四元式中操作數(shù)是不是為常數(shù)Replace():替換冗余的四元式DeleteQuat():刪除冗余的四元式Ge

17、q():計(jì)算并優(yōu)化四元式編譯后端（目標(biāo)代碼生成）：TargetCode():生成目標(biāo)代碼InitSEMStack():初始化信息棧ActiveInfo():生成活躍信息表CollectAndEdit():生成匯編代碼output_code():輸出目標(biāo)代碼 4.3 實(shí)驗(yàn)結(jié)果 采用如下一段C語言程序進(jìn)行驗(yàn)證，包含了課設(shè)要求的基本語句。這是一段正確的程序，就是符合我們定義的文法。用它來進(jìn)行程序的驗(yàn)證，各模塊輸出結(jié)果如下所示。在這里先說明一下，若待驗(yàn)證的程序沒有錯誤，那么語法分析就檢測不出錯誤，為了能檢測到錯誤，展示語法分析的功能，就認(rèn)為的制造出錯誤，具體見下面語法分析輸出模塊。void main(

18、) int a,b,c,x; if(ab)x=(a+b)*c; else x=5-a*b; while(c=x)a=c+5*(3+2);b=a+x; （1）詞法分析器模塊輸出結(jié)果如下所示：它的輸出結(jié)果形式第一列代表所屬類型，第二列為對應(yīng)的單詞。我們的程序也可以識別出字符常量和字符串常量。因?yàn)閮?yōu)化那部分沒有涉及到這兩種常量，所以就沒有向大家展示出來。（2） 語法分析模塊輸出的結(jié)果如下： 因?yàn)橛脕眚?yàn)證的程序沒有錯誤，所以需要人為的添加錯誤。程序能識別的錯誤有：能夠識別出未定義標(biāo)識符能夠檢測出標(biāo)識符的重定義能夠檢測出括弧的匹配與否if和while的判斷條件不能為空能夠識別出關(guān)鍵字的拼寫正確與否表達(dá)式

19、的正確與否。給出檢測程序如下：void main() int a,b,x; char a;/a重定義 if()/if判斷條件為空x=(a+b)*c; else x=5-a*b; while(a=b)a=c+5*(3+2);b=a+x; d=a+b;/d沒定義 （3） 中間代碼產(chǎn)生器模塊輸出的結(jié)果如下：用四元式序列來表示。（4） 優(yōu)化器模塊輸出結(jié)果如下：（5） 目標(biāo)代碼生成模塊輸出結(jié)果如下：因?yàn)樯赡繕?biāo)代碼需要獲取相關(guān)變量的活躍度信息，所以先展示一下符號表的內(nèi)容。（6） 可視化界面如下圖所示：各模塊要輸出的內(nèi)容在上面已經(jīng)被標(biāo)出。 5 結(jié)論 我們所設(shè)計(jì)的C語言編譯系統(tǒng)可以根據(jù)自己所定義的文法成功的

20、進(jìn)行詞法分析，生成相應(yīng)的Token序列，另外，通過測試，也可以成功地生成靜態(tài)符號表，并能對靜態(tài)符號表隨時進(jìn)行查看。我們所設(shè)計(jì)的C語言編譯系統(tǒng)也可以成功地對文檔中的內(nèi)容采用LL1分析法進(jìn)行語法分析。通過測試，可以檢查出所有的錯誤，并提示出錯，但只能輸出部分與錯誤有關(guān)的信息，而不能輸出全部錯誤信息。總體來說還算成功。另外，在進(jìn)行語法分析的同時，我們通過插入語義動作可以同時生成四元式。通過測試，我們可以成功的生成所需的四元式。我們也對四元式的優(yōu)化進(jìn)行了測試，我們可以成功地對原始的四元式進(jìn)行部分的優(yōu)化，但不能優(yōu)化至最簡，而是只能對兩個操作數(shù)皆為常數(shù)，及四元式重復(fù)冗余這兩種情況進(jìn)行優(yōu)化。我們也可以成功地

21、生成活躍信息表，并通過活躍信息表生成相應(yīng)的機(jī)器代碼。通過測試，我們所生成的機(jī)器代碼是準(zhǔn)確無誤的。 因此，整體來說，我們所設(shè)計(jì)的C語言編譯系統(tǒng)是成功的。但我們也有遺憾，我們所設(shè)計(jì)的符號表，單獨(dú)是可以運(yùn)行的，并沒有建立相應(yīng)的活動記錄。 6 參考文獻(xiàn)1、陳火旺.程序設(shè)計(jì)語言編譯原理（第3版）. 北京：國防工業(yè)出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D. Ullman著.李建中，姜守旭譯.編譯原理.北京：機(jī)械工業(yè)出版社.2003.3、美 Kenneth C.Louden著.馮博琴等譯.編譯原理及實(shí)踐.北京：機(jī)械工業(yè)出版社.2002.4、金成植著.編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù). 北京：高等教育出版社. 2002. 7 收獲、體會和建議 經(jīng)過了為期2周的課程設(shè)計(jì)，讓一開始都不知道編譯器是何物的我們成功蛻變，在完成基本任務(wù)的基礎(chǔ)上又進(jìn)一步實(shí)現(xiàn)了編譯器后端。依稀記得剛剛接觸課程題目時，都不知道該如何下手，雖