編譯原理課程設(shè)計報告(一個完整的編譯器)

1、編譯原理程序設(shè)計報告一個簡單文法的編譯器的設(shè)計與實現(xiàn) 專業(yè)班級 ： 計算機1406班 組長姓名 ： 宋世波 組長學(xué)號 ： 20143753 指導(dǎo)教師 ： 肖 桐 2016年12月設(shè)計分工 組長學(xué)號及姓名：宋世波20143753分工：文法及數(shù)據(jù)結(jié)構(gòu)設(shè)計詞法分析語法分析（ll1）基于dag的中間代碼優(yōu)化部分目標代碼生成 組員1學(xué)號及姓名：黃潤華20143740分工：中間代碼生成(lr0)部分目標代碼生成 組員2學(xué)號及姓名：孫何奇20143754分工：符號表組織部分目標代碼生成摘要編譯器是將便于人編寫，閱讀，維護的高級計算機語言翻譯為計算機能解讀、運行的低階機器語言的程序。編譯是從源代碼（通常為高階

2、語言）到能直接被計算機或虛擬機執(zhí)行的目標代碼（通常為低階語言或機器語言）的翻譯過程。一編譯器的概述1.編譯器的概念編譯器是將便于人編寫，閱讀，維護的高級計算機語言翻譯為計算機能解讀、運行的低階機器語言的程序。編譯器將原始程序作為輸入，翻譯產(chǎn)生使用目標語言的等價程序。源代碼一般為高階語言如pascal、c+、java 等，而目標語言則是匯編語言或目標機器的目標代碼，有時也稱作機器代碼。2編譯器的種類編譯器可以生成用來在與編譯器本身所在的計算機和操作系統(tǒng)（平臺）相同的環(huán)境下運行的目標代碼，這種編譯器又叫做“本地”編譯器。另外，編譯器也可以生成用來在其它平臺上運行的目標代碼，這種編譯器又叫做交叉編譯

3、器。交叉編譯器在生成新的硬件平臺時非常有用?！霸创a到源碼編譯器”是指用一種高階語言作為輸入，輸出也是高階語言的編譯器。例如: 自動并行化編譯器經(jīng)常采用一種高階語言作為輸入，轉(zhuǎn)換其中的代碼，并用并行代碼注釋對它進行注釋（如openmp）或者用語言構(gòu)造進行注釋（如fortran的doall指令）。3.本編譯器概述 編譯程序的工作過程一般可以分為五個階段：詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、優(yōu)化、目標代碼生成。每一個階段在功能上是相對獨立的，它一方面從上一個階段獲取分析的結(jié)果來進行分析，另一方面由將結(jié)果傳遞給下一個階段。由編譯程序的五個階段就對應(yīng)了編譯系統(tǒng)的結(jié)構(gòu)，這五個對應(yīng)階段分為編譯器的前

4、段，中間代碼以及后端。其中詞法分析器利用超前搜索、狀態(tài)轉(zhuǎn)換等方法，將源程序轉(zhuǎn)化成為一個一個的單詞符號二元式。一般程序語言的單詞符號包括關(guān)鍵字、運算符、常數(shù)、標識符和界符。語法分析器將這些單詞符號作為輸入，對它進行語法分析。語法分析采用ll1分析法，語法分析器把語法單元作為輸入供語義分析器使用。在語法分析的同時進行語法分析，并產(chǎn)生一定的語義動作，來生成中間代碼。優(yōu)化和目標代碼生成是針對某一種處理器而言的。代碼優(yōu)化是將語義分析生成的中間代碼進行優(yōu)化，產(chǎn)生執(zhí)行效率更高的代碼。目標代碼生成最終生成可以在某種機器上運行的機器語言或者匯編語言。還要有符號表可供查詢。在整個編譯過程中還包括對表格的操作和對錯

5、誤的處理，這些也都是非常重要的環(huán)節(jié)。環(huán)境：編譯器整體全部使用visual studio2015編寫目標代碼在8086指令集機器上運行關(guān)鍵詞：編譯原理，前端，中間代碼生成，后端，目錄設(shè)計分工2摘要31. 概 述72. 課程設(shè)計任務(wù)及要求92.1 設(shè)計任務(wù)92.2 設(shè)計要求102.3設(shè)計的文法結(jié)構(gòu)113. 算法及數(shù)據(jù)結(jié)構(gòu)173.1 算法的總體思想（流程）173.2 詞法分析器模塊183.2.1 功能183.2.2 數(shù)據(jù)結(jié)構(gòu)193.2.3 流程圖203.2.4 算法203.2.5 運行截圖223.3 語法分析器模塊233.3.1 功能233.3.2 數(shù)據(jù)結(jié)構(gòu)243.3.3 流程圖253.3.4 算法

6、263.3.5 運行截圖333.4符號表生成模塊343.4.1 功能343.4.2 數(shù)據(jù)結(jié)構(gòu)353.4.3 流程圖373.4.4 算法383.4.5 運行截圖393.5中間代碼生成模塊393.5.1 功能403.5.2 數(shù)據(jù)結(jié)構(gòu)403.5.3 流程圖433.5.4 算法433.5.5 運行截圖443.6中間代碼優(yōu)化模塊443.6.1 功能443.6.2 數(shù)據(jù)結(jié)構(gòu)453.6.3 流程圖463.6.4 算法473.6.5運行截圖493.7目標代碼生成模塊503.7.1 功能503.7.2 數(shù)據(jù)結(jié)構(gòu)513.7.3 流程圖513.7.4 算法523.7.5 運行截圖54這里不得不提到目標代碼生成中存在

7、的一些問題，554. 程序設(shè)計與實現(xiàn)584.1 程序說明584.2 實驗結(jié)果615. 結(jié)論635.1組長：宋世波635.2組員：孫何奇645.3組員：黃潤華646. 收獲、體會和建議。666.1組長：宋世波666.2組員：孫何奇666.3組員：黃潤華677.附錄69源代碼：697.1可執(zhí)行文件鏈接698、參考文獻701. 概 述本程序?qū)崿F(xiàn)的數(shù)據(jù)類型有整型（int）、浮點型（float）、char（字符型）、字符串型（string），同時在最后的目標代碼生成部分允許出現(xiàn)布爾（bool）類型，實現(xiàn)的操作有if，else以及while循環(huán)，和輸入輸出語句，能做到直接生成目標代碼并運行。做到了類型檢查

8、和重定義的判斷，同時也有優(yōu)化部分。詞法分析部分構(gòu)建得到的詞法序列為二元式，二元式由兩部分組成，其種別碼和類型組成，其中關(guān)鍵字和界符記錄其數(shù)字，用到時只需查其對應(yīng)的關(guān)鍵字表和界符表即可，而字符類型、字符串類型、數(shù)字類型、以及標識符類型的值一律用字符串存儲，其中數(shù)字類型存儲時對其使用atoi和itoa函數(shù)進行數(shù)字轉(zhuǎn)字符串即可，要使用到其數(shù)字時只需要將對其使用字符串轉(zhuǎn)數(shù)字函數(shù)再獲得即可。語法分析部分采用的是ll1分析方法，這是一種自上而下的語法分析法，又稱為預(yù)測分析法，語法分析器部分實現(xiàn)了自動求first集合和follow集合，采用的是遞歸程序獲得select集合，在實現(xiàn)對產(chǎn)生式完全掃描以后，便可以

9、獲得一張完整的分析表，表中標注了是否為預(yù)測以及對應(yīng)的產(chǎn)生式序列，而后進行語法分析，通過于獲得的分析表進行比對，進行入棧出棧，匹配到相同的則認為匹配成果，當文法匹配成功，同時單詞也匹配成功的時候，認為語法分析完成，語法無錯誤，否則報錯。在符號表生成部分，程序?qū)Λ@取的單詞序列中的標識符進行再分析，確定每一個標識符的存儲范圍，同時從此之中獲取函數(shù)的參數(shù)表，函數(shù)表部分，構(gòu)建出編譯器全局可用的活動記錄表，以供目標代碼生成使用，同時也為編譯器增添新內(nèi)容做準備。中間代碼生成部分，在此之前需注意到，由于再語法分析部分已經(jīng)生成了一個具體可理解的動作序列，所以中間代碼生成部分的所用方法并非語法制導(dǎo)，其本身也與語法

10、分析相割裂開來，中間代碼生成采取的是自底向上進行分析，不過是基于單詞序列進行的分析，其操作等于是使用已獲得的偽動作序列，與源程序去作比較，找出偽動作序列的實際含義，將其順序填好，最后便完成了整個中間代碼（四元式）的生成，并將其重新輸出到文件中。中間代碼優(yōu)化部分是對填裝完畢的中間代碼的再處理，也就是減少無用式子，給目標代碼的生成提供便利，先進行基本塊劃分，而后采取的是dag圖優(yōu)化，即無環(huán)有向圖優(yōu)化，順序是構(gòu)建dag圖（無環(huán)有向圖），減少無用分支，或刪改部分同義分支，完成dag圖改造后便又重新由樹組裝四元式，組裝好的四元式又再次重新輸出到文件中。目標代碼生成部分較長，也并不僅僅包含目標代碼生成部分

11、，在這個部分文件中，同時需要對前述獲得的符號表，中間代碼進行再處理，以得到符號目標代碼生成所用的符號表和中間代碼，再進行預(yù)處理完成之后，具體為根據(jù)四元式動作，按順序依次生成目標代碼，需要依據(jù)不同的四元式動作每個采取不同的操作方法，生成相應(yīng)目標代碼。測試部分采用的emu8086軟件，這個軟件支持的指令集為8086指令集，由于64位機器上對匯編的支持并不算好，所以在8086機上最后進行的是對目標代碼的正確性檢驗以及運行，運行通過且符合源程序?qū)嶋H操作即認為編譯器任務(wù)完成。2. 課程設(shè)計任務(wù)及要求2.1 設(shè)計任務(wù)1.一個簡單文法的編譯器前端的設(shè)計與實現(xiàn)定義一個簡單程序設(shè)計語言文法（包括變量說明語句、算

12、術(shù)運算表達式、賦值語句；擴展包括邏輯運算表達式、if語句、while語句等）；掃描器設(shè)計實現(xiàn)；語法分析器設(shè)計實現(xiàn)；中間代碼設(shè)計；中間代碼生成器設(shè)計實現(xiàn)。 2.難度相當?shù)淖赃x題目, 如:一個簡單文法的編譯器后端的設(shè)計與實現(xiàn)。一個簡單文法的編譯器的設(shè)計與實現(xiàn)。自選一個感興趣的與編譯原理有關(guān)的問題加以實現(xiàn)以下為本組選擇部分：一個簡單文法的編譯器的設(shè)計與實現(xiàn)。1. 定義一個簡單程序設(shè)計語言文法（包括變量說明語句、算術(shù)運算表達式、賦值語句；擴展包括邏輯運算表達式、if語句、while語句等）；2. 掃描器設(shè)計實現(xiàn)3. 語法分析器設(shè)計實現(xiàn)；4. 符號表設(shè)計5. 符號表生成器設(shè)計實現(xiàn)6. 中間代碼設(shè)計；7.

13、 中間代碼生成器設(shè)計實現(xiàn)。8. 中間代碼優(yōu)化9. 中間代碼優(yōu)化實現(xiàn)10. 目標代碼設(shè)計11. 目標代碼生成器設(shè)計實現(xiàn)2.2 設(shè)計要求1、在深入理解編譯原理基本原理的基礎(chǔ)上，對于選定的題目，以小組為單位，先確定設(shè)計方案；2、設(shè)計系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)，設(shè)計每個模塊的處理流程。要求設(shè)計合理；3、編程序?qū)崿F(xiàn)系統(tǒng)，要求實現(xiàn)可視化的運行界面，界面應(yīng)清楚地反映出系統(tǒng)的運行結(jié)果；4、確定測試方案，選擇測試用例，對系統(tǒng)進行測試；5、運行系統(tǒng)并要通過驗收，講解運行結(jié)果，說明系統(tǒng)的特色和創(chuàng)新之處，并回答指導(dǎo)教師的提問；6、提交課程設(shè)計報告。以下為本組設(shè)計要求：給出一個源程序文件，作為編譯器前端的輸入，輸出相關(guān)編

14、譯階段的運行結(jié)果。詞法分析階段：token序列；關(guān)鍵字表、界符表、符號表系統(tǒng)。語法分析階段：ll1型產(chǎn)生式、分析表、語法分析所用棧符號表生成階段：符號表系統(tǒng)中間代碼生成階段：四元式序列；符號表系統(tǒng)。中間代碼優(yōu)化階段：四元式序列、dag圖、優(yōu)化完成的四元式序列目標代碼生成階段：符號表系統(tǒng)、四元式序列、目標代碼(8086指令集)2.3設(shè)計的文法結(jié)構(gòu)產(chǎn)生式中文對照:1. - ( ) 2. -int|float|char|void|$3. - ( ) | | |4. - 5. - 6. - * | / | $ 7. - + | - | $ 8. - | $ 9. - |10. - = | $ 11.

15、- 12. - , | $ 13. - 14. - | $ 15. - ;16. - | | | | $ 17. - 18. - = ; | ( ) ; 19. - 20. - , | $ 21. - | | 22.-while()23. - 24. - | = |=|= 25. - if ( ) 26. - else | $ 27. - return ; 28.-cout ;|cout ;|cout ;29.-cin;產(chǎn)生式如下：funcdef%type&id&(¶state&)&funcblock&|(¶list&)&;()1234567891011121314151617

16、18字符表ch字符串表st3. 算法及數(shù)據(jù)結(jié)構(gòu)3.1 算法的總體思想（流程）算法總體思想文字解釋如下：1. 從文件中讀取代碼，調(diào)入詞法分析，生成詞法序列。2. 而后將詞法序列傳遞給語法分析器，語法分析器從文件中讀入產(chǎn)生式，自動產(chǎn)生first集和follow集，構(gòu)建出完整的分析表，而后與得到的詞法序列進行比較，吮吸進行語法分析，按照分析表查得產(chǎn)生式進行入棧出棧，完成ll1語法分析的整個過程。3. 符號表繼續(xù)使用詞法序列，不依賴于語法分析而直接構(gòu)建符號表，依據(jù)詞法中的標識符直接構(gòu)建函數(shù)表、參數(shù)表、符號表和活動記錄表，并對于其后的目標代碼生成產(chǎn)生作用。4. 中間代碼生成模塊使用語法分析過程中所獲得的

17、偽動作序列，同時依靠獲得的詞法分析序列，逐個進行比對，同時將標識符依次入棧，需要時取出，通過完整棧區(qū)的出棧入棧實現(xiàn)整個中間代碼（四元式）的填寫。5. 中間代碼優(yōu)化模塊獲取前述過程中所生成的四元式文件，而后依托于四元式構(gòu)建dag圖，由產(chǎn)生的dag圖采用教材ppt所述方法按節(jié)點進行優(yōu)化，直接產(chǎn)生優(yōu)化后的dag圖并生成優(yōu)化后的四元式填裝回文件中。6. 目標代碼生成部分直接提取之前編譯器部分所獲得的四元式和符號表，依據(jù)其成果直接構(gòu)建目標代碼（匯編代碼，8086指令集），同時在此其中進行類型檢查，重定義等，完成語義分析。3.2 詞法分析器模塊（負責(zé)人：宋世波）3.2.1 功能1.獲取待處理的源代碼2.生

18、成二元式序列3.采用dfa和自動機實現(xiàn)二元式的填寫4.將獲得的二元式輸入到文件中 詞法分析過程是將字符序列轉(zhuǎn)換為token序列的過程。此階段的任務(wù)是從左到右依次掃描源程序中的字符，即對構(gòu)成字符流進行掃描然后根據(jù)構(gòu)詞規(guī)則識別token。設(shè)計的詞法分析器能相對完善地構(gòu)造出不同的單詞，用二元式的形式存儲，簡顯易懂，并將新的標識符單詞填入變臉表當中，實現(xiàn)在計算機內(nèi)單詞序列的統(tǒng)一存儲。3.2.2 數(shù)據(jù)結(jié)構(gòu)enum stylei,c,k,p,ch,st,def;/*枚舉種類*/static char *keyword18 = int,float,char,void,if,else,switch,case,

19、for,do,while,continue,break,default,sizeof,return,cout,cin ;/*關(guān)鍵字表*/static char *delimiters18 = =,=ifelsereturncoutcin00000000000000000000000000000000000161600000191900000000000000000000000000000000000000000000000003103131310000000003503637380000000000000000000000000000000000000000000000000545500000

20、0056000000585758585800005900000006000000006100000000063063636300640646464每個產(chǎn)生式大括號中的內(nèi)容便是該產(chǎn)生式的select集合?？梢钥闯鐾划a(chǎn)生式select集合不相交即為ll(1)文法。根據(jù)上述集合即可構(gòu)造出ll(1)分析表，由于產(chǎn)生式數(shù)目較多， ll(1)分析器主要由ll(1)分析表和ll(1)控制程序兩部分構(gòu)成：ll(1)分析表是存儲文法select集合的知識表，可通過預(yù)先設(shè)置的語法棧的棧頂符和當前掃描的單詞來確定產(chǎn)生式的序號，從而進行下一步判斷或者壓棧操作。其后的語法分析主函數(shù)便是根據(jù)上述所寫的分析表，獲取要分析

21、單詞，與堆棧區(qū)棧頂然后進入分析表，按照分析表所寫進行入棧出棧，完成分析即認為語法無錯誤，否則則認為有錯誤，發(fā)現(xiàn)情況無法對應(yīng)分析表時也認為是發(fā)生了錯誤。3.3.5 運行截圖可以直觀地看出ll(1)的分析過程，可以看出對于一個稍微簡單的文法，ll(1)分析過程需要多步才能判斷完全。至此，ll(1)分析方法設(shè)計完成。3.4符號表生成模塊（負責(zé)人：孫何奇）3.4.1 功能1. 構(gòu)建活動記錄表2. 構(gòu)建符號表3. 構(gòu)建函數(shù)表4. 構(gòu)建長度表5. 添加活動記錄6. 添加變量表7. 符號表預(yù)處理8. 添加函數(shù)表9. 添加參數(shù)表10. 構(gòu)建活動記錄與變量表（二合一） 符號表是在目標代碼生成中不可以缺少的提供查

22、詢服務(wù)的表，在其中記錄了程序收集，記錄于使用的源程序的語法符號的類型、特征等相關(guān)信息，信息集中反映了標識符的語義特征屬性。在詞法分析及語法在分析過程中不斷積累和更新表中的信息，并在詞法分析到代碼生成的各階段，按各自的需要從表中獲取不同的屬性信息。在本次課設(shè)中，符號表的作用和地位是重要關(guān)鍵的。符號表是一個編譯器的核心數(shù)據(jù)結(jié)構(gòu)，它代表了標識符的動態(tài)語義詞典，屬于編譯中語義分析的知識庫。符號表中所登記的信息在編譯的不同階段都要用到，對于一個多遍掃描的編譯程序，不同遍所用的符號表也往往各有不同，因為每遍所關(guān)心的信息各有差異。符號表的組織方式也決定了未來處理符號表內(nèi)容時的效率。我所設(shè)計的符號表生成器能夠

23、在定義標識符時把對應(yīng)的語義信息填入符號表中；當在語句中使用該標識符時，通過查找相應(yīng)的表項來判斷該標識符是否存在且使用正確。符號表常見的功能有定義和重定義檢查、類型匹配校驗、數(shù)據(jù)的越界和溢出檢查、值單元存儲分配信息和函數(shù)的參數(shù)傳遞與校驗。由于時間有限，我設(shè)計的符號表系統(tǒng)只完成了上述功能中的一部分。 3.4.2 數(shù)據(jù)結(jié)構(gòu)在編譯程序中，符號表項的組織傳統(tǒng)上采用三種構(gòu)造方法：線性組織排列組織及二分法散列組織線性表按符號掃描的順序有序填入，但在查詢時效率較低；排列表按首字符大小來填寫符號表，查詢效率較高，但填寫時實現(xiàn)較復(fù)雜。因此，散列表可以通過一定的散列函數(shù)來實現(xiàn)符號表的高效填寫和查詢。至此，我們可以寫

24、出符號表總體的數(shù)據(jù)結(jié)構(gòu)：char variate1615 = ;/*變量表*/enum typin,real,ch,b,default1;/*類型，包括int，float,char,bool型*/enum catf,con,t,d,v,vn,vf,default2;/*種類，包括f函數(shù)，c常量，t類型，d域名，v變量，vn換名形參，vf，賦值形參*/enum addrpfinfl,lenl,vall,default3;/*地址表，包括函數(shù)表，活動記錄表*/int idlocate16;/*記錄標識符在代碼中首次出現(xiàn)的位置*/struct symbol /*符號表*/char name15;ty

25、p type;cat kind;addr addr;struct pfinfl /*函數(shù)表*/int level;int off;int fn;symbol para5;/*參數(shù)表*/int entry;struct vall /*活動記錄表，采用鏈表結(jié)構(gòu)*/char name15;char name115;int low;int up;struct vall *next;vall *firstnode=new vall;struct lenl /*長度表*/char name10;int length;lenl lengt10;符號表是標識符的動態(tài)語義詞典，屬于編譯中語義分析的知識庫；主要內(nèi)容： 名字 標識符源碼，用作查詢關(guān)鍵字； 類型 - 該標識符的數(shù)據(jù)類型及其相關(guān)信息； 種類 - 該標識符在源程序中的語義角色； 地址 - 與值單元相關(guān)的一些信息；在我設(shè)計的符號表生成器中，填寫階段主要使用詞法序列，來實現(xiàn)符號表的動態(tài)填寫。我將填寫符號表的過程分為四個階段：明確當前符號表的作用域，將作