編譯原理課程設(shè)計(jì)報(bào)告(一個(gè)完整的編譯器)(共70頁(yè))

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

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

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

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

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

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

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

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

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

10、；中間代碼設(shè)計(jì)；中間代碼生成器設(shè)計(jì)實(shí)現(xiàn)。 2.難度相當(dāng)?shù)淖赃x題目, 如:一個(gè)簡(jiǎn)單文法的編譯器后端的設(shè)計(jì)與實(shí)現(xiàn)。一個(gè)簡(jiǎn)單文法的編譯器的設(shè)計(jì)與實(shí)現(xiàn)。自選一個(gè)感興趣的與編譯原理有關(guān)的問(wèn)題加以實(shí)現(xiàn)以下為本組選擇部分：一個(gè)簡(jiǎn)單文法的編譯器的設(shè)計(jì)與實(shí)現(xiàn)。1. 定義一個(gè)簡(jiǎn)單程序設(shè)計(jì)語(yǔ)言文法（包括變量說(shuō)明語(yǔ)句、算術(shù)運(yùn)算表達(dá)式、賦值語(yǔ)句；擴(kuò)展包括邏輯運(yùn)算表達(dá)式、If語(yǔ)句、While語(yǔ)句等）；2. 掃描器設(shè)計(jì)實(shí)現(xiàn)3. 語(yǔ)法分析器設(shè)計(jì)實(shí)現(xiàn)；4. 符號(hào)表設(shè)計(jì)5. 符號(hào)表生成器設(shè)計(jì)實(shí)現(xiàn)6. 中間代碼設(shè)計(jì)；7. 中間代碼生成器設(shè)計(jì)實(shí)現(xiàn)。8. 中間代碼優(yōu)化9. 中間代碼優(yōu)化實(shí)現(xiàn)10. 目標(biāo)代碼設(shè)計(jì)11. 目標(biāo)代碼生成器設(shè)計(jì)

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

12、表、語(yǔ)法分析所用棧符號(hào)表生成階段：符號(hào)表系統(tǒng)中間代碼生成階段：四元式序列；符號(hào)表系統(tǒng)。中間代碼優(yōu)化階段：四元式序列、DAG圖、優(yōu)化完成的四元式序列目標(biāo)代碼生成階段：符號(hào)表系統(tǒng)、四元式序列、目標(biāo)代碼(8086指令集)2.3設(shè)計(jì)的文法結(jié)構(gòu)產(chǎn)生式中文對(duì)照: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)識(shí)符表i常數(shù)表C關(guān)鍵字表KIntFloatCharStringVoidIfElseSwitchCaseForDoWhileContinueBreakDefaultSizeofReturnCoutCin12345678910111213141516171819界符表P=,=