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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上編譯原理程序設(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)化部分目標(biāo)代碼生成 組員1學(xué)號及姓名：黃潤華20143740分工：中間代碼生成(LR0)部分目標(biāo)代碼生成 組員2學(xué)號及姓名：孫何奇20143754分工：符號表組織部分目標(biāo)代碼生成摘要編譯器是將便于人編寫，閱讀，維護的高級計算機語言翻譯為計算機能解讀、運行的低階機器語言的程序。

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

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

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

5、中還包括對表格的操作和對錯誤的處理，這些也都是非常重要的環(huán)節(jié)。環(huán)境：編譯器整體全部使用visual studio2015編寫目標(biāo)代碼在8086指令集機器上運行關(guān)鍵詞：編譯原理，前端，中間代碼生成，后端，目錄1. 概 述本程序?qū)崿F(xiàn)的數(shù)據(jù)類型有整型（int）、浮點型（float）、char（字符型）、字符串型（string），同時在最后的目標(biāo)代碼生成部分允許出現(xiàn)布爾（bool）類型，實現(xiàn)的操作有if，else以及while循環(huán)，和輸入輸出語句，能做到直接生成目標(biāo)代碼并運行。做到了類型檢查和重定義的判斷，同時也有優(yōu)化部分。詞法分析部分構(gòu)建得到的詞法序列為二元式，二元式由兩部分組成，其種別碼和類型組成

6、，其中關(guān)鍵字和界符記錄其數(shù)字，用到時只需查其對應(yīng)的關(guān)鍵字表和界符表即可，而字符類型、字符串類型、數(shù)字類型、以及標(biāo)識符類型的值一律用字符串存儲，其中數(shù)字類型存儲時對其使用atoi和itoa函數(shù)進行數(shù)字轉(zhuǎn)字符串即可，要使用到其數(shù)字時只需要將對其使用字符串轉(zhuǎn)數(shù)字函數(shù)再獲得即可。語法分析部分采用的是LL1分析方法，這是一種自上而下的語法分析法，又稱為預(yù)測分析法，語法分析器部分實現(xiàn)了自動求first集合和follow集合，采用的是遞歸程序獲得select集合，在實現(xiàn)對產(chǎn)生式完全掃描以后，便可以獲得一張完整的分析表，表中標(biāo)注了是否為預(yù)測以及對應(yīng)的產(chǎn)生式序列，而后進行語法分析，通過于獲得的分析表進行比對，進

7、行入棧出棧，匹配到相同的則認(rèn)為匹配成果，當(dāng)文法匹配成功，同時單詞也匹配成功的時候，認(rèn)為語法分析完成，語法無錯誤，否則報錯。在符號表生成部分，程序?qū)Λ@取的單詞序列中的標(biāo)識符進行再分析，確定每一個標(biāo)識符的存儲范圍，同時從此之中獲取函數(shù)的參數(shù)表，函數(shù)表部分，構(gòu)建出編譯器全局可用的活動記錄表，以供目標(biāo)代碼生成使用，同時也為編譯器增添新內(nèi)容做準(zhǔn)備。中間代碼生成部分，在此之前需注意到，由于再語法分析部分已經(jīng)生成了一個具體可理解的動作序列，所以中間代碼生成部分的所用方法并非語法制導(dǎo)，其本身也與語法分析相割裂開來，中間代碼生成采取的是自底向上進行分析，不過是基于單詞序列進行的分析，其操作等于是使用已獲得的偽動

8、作序列，與源程序去作比較，找出偽動作序列的實際含義，將其順序填好，最后便完成了整個中間代碼（四元式）的生成，并將其重新輸出到文件中。中間代碼優(yōu)化部分是對填裝完畢的中間代碼的再處理，也就是減少無用式子，給目標(biāo)代碼的生成提供便利，先進行基本塊劃分，而后采取的是DAG圖優(yōu)化，即無環(huán)有向圖優(yōu)化，順序是構(gòu)建DAG圖（無環(huán)有向圖），減少無用分支，或刪改部分同義分支，完成DAG圖改造后便又重新由樹組裝四元式，組裝好的四元式又再次重新輸出到文件中。目標(biāo)代碼生成部分較長，也并不僅僅包含目標(biāo)代碼生成部分，在這個部分文件中，同時需要對前述獲得的符號表，中間代碼進行再處理，以得到符號目標(biāo)代碼生成所用的符號表和中間代碼

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

10、；中間代碼設(shè)計；中間代碼生成器設(shè)計實現(xiàn)。 2.難度相當(dāng)?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. 中間代碼生成器設(shè)計實現(xiàn)。8. 中間代碼優(yōu)化9. 中間代碼優(yōu)化實現(xiàn)10. 目標(biāo)代碼設(shè)計11. 目標(biāo)代碼生成器設(shè)計

11、實現(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)編譯階段的運行結(jié)果。詞法分析階段：Token序列；關(guān)鍵字表、界符表、符號表系統(tǒng)。語法分析階段：LL1型產(chǎn)生式、分析

12、表、語法分析所用棧符號表生成階段：符號表系統(tǒng)中間代碼生成階段：四元式序列；符號表系統(tǒng)。中間代碼優(yōu)化階段：四元式序列、DAG圖、優(yōu)化完成的四元式序列目標(biāo)代碼生成階段：符號表系統(tǒng)、四元式序列、目標(biāo)代碼(8086指令集)2.3設(shè)計的文法結(jié)構(gòu)產(chǎn)生式中文對照:1. - ( ) 2. -int|float|char|void|$3. - ( ) | | |4. - 5. - 6. - * | / | $ 7. - + | - | $ 8. - | $ 9. - |10. - = | $ 11. - 12. - , | $ 13. - 14. - | $ 15. - ;16. - | | | | $ 17.

13、 - 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&#type%int|float|char|void&#factor%(&exp&)|id|number|ch&#exp%divi&item&#divi%factor&faccycle&#faccy

14、cle%*&factor&faccycle|/&factor&faccycle|$&#item%+&divi&item|-&divi&item|$&#parastate%state&stateclo|$&#state%type&id&init|id&init&#init%=&rvalue|$&#rvalue%exp&#stateclo%,&stateclo|$&#funcblock%staclo&funcbloclo&#staclo%statement&staclo|$&#statement%state&;&#funcbloclo%opera&funcbloclo|whilecycle&fun

15、cbloclo|condistate&funcbloclo|funcend&funcbloclo|coutstate&funcbloclo|cinstate&funcbloclo|$&#opera%id&callstate&#callstate%=&rvalue&;|(¶list&)&;&#paralist%para¶clo&#paraclo%,¶¶clo|$&#para%id|number|string&#whilecycle%while&(&logicexp&)&do&funcblock&we&#logicexp%exp&logicopera&exp&#logicopera%|=|=&#condistate%if&(&logicexp&)&funcblock&nor&ie&#nor%else&funcblock&|$&#funcend%return&factor&;&#coutstate%cout&id&;&#do%$&#we%$&#ie%$&#詞法分析序列表：標(biāo)識符表i常數(shù)表C關(guān)鍵字表KIntFloatCharStringVoidIfElseSwitchCaseForDoWhileContinueBreakDefaultSizeofReturnCoutCin12345678910111213141516171819界符表P=,=