編譯原理課程設(shè)計(jì)

1、課 程 設(shè) 計(jì) 報(bào) 告設(shè)計(jì)題目：一個(gè)簡單文法編譯器的設(shè)計(jì)與實(shí)現(xiàn)班 級(jí)：計(jì)算機(jī)1302組長學(xué)號(hào)：20133823組長姓名：高思坦指導(dǎo)教師：肖桐設(shè)計(jì)時(shí)間：2015年12月1設(shè)計(jì)分工組長學(xué)號(hào)及姓名：20133823 高思坦分工：目標(biāo)代碼生成組員1學(xué)號(hào)及姓名：20133826 李北分工：語法分析、中間代碼生成組員2學(xué)號(hào)及姓名：20133822 方秋生分工：詞法分析翻譯器組員3學(xué)號(hào)及姓名：20133839 吳永琪分工：詞法分析識(shí)別器組員4學(xué)號(hào)及姓名：20133832 劉向甲分工：符號(hào)表管理摘 要現(xiàn)代計(jì)算機(jī)的程序很多都是用高級(jí)語言編寫的，而這些高級(jí)語言計(jì)算機(jī)是無法識(shí)別的，因此需要將它們轉(zhuǎn)變成計(jì)算機(jī)能識(shí)別的

2、語言，此時(shí)就需要借助到編譯程序。編譯程序是一種翻譯程序，它特指把某種高級(jí)語言（如C、Java、Pascal）翻譯成具體計(jì)算機(jī)上的低級(jí)程序設(shè)計(jì)語言。編譯程序是計(jì)算機(jī)系統(tǒng)軟件最主要的組成部分之，也是用戶最直接關(guān)系的工具之一。一個(gè)編譯程序的可以劃分為前端和后端。前端包括詞法分析、語法分析、語義分析與中間代碼生成三個(gè)階段，后端包括優(yōu)化、目標(biāo)代碼生成兩個(gè)階段，另外還有符號(hào)表的管理和錯(cuò)誤處理貫穿整個(gè)過程。一個(gè)編譯程序，既可以一個(gè)階段一個(gè)階段地對(duì)源程序進(jìn)行分析，也可以前端只對(duì)源程序進(jìn)行一遍分析，后端也只進(jìn)行一遍分析。本課設(shè)實(shí)現(xiàn)了對(duì)C語言中的一部分功能的編譯，包括算術(shù)邏輯表達(dá)式、if語句、while語句以及一

3、維數(shù)組等。前端對(duì)源程序掃描一遍實(shí)現(xiàn)詞法分析、語法分析、語義分析與中間代碼生成三個(gè)階段，后端進(jìn)行目標(biāo)代碼生成，整個(gè)過程穿插符號(hào)表管理和錯(cuò)誤處理。關(guān)鍵詞：編譯程序，前端，后端目 錄摘要.I1 概述 .12 課程設(shè)計(jì)任務(wù)及要求 .2 2.1 設(shè)計(jì)任務(wù) .2 2.2 設(shè)計(jì)要求.23 算法與數(shù)據(jù)結(jié)構(gòu).3 3.1 算法的總體思想（流程）.3 3.2 詞法分析識(shí)別器模塊.4 3.2.1 功能.4 3.2.2 數(shù)據(jù)結(jié)構(gòu).5 3.2.3 算法.9 3.3 語法分析模塊.11 3.3.1 功能.113.3.2 數(shù)據(jù)結(jié)構(gòu).12 3.3.3 算法.16 3.4 語義分析和中間代碼生成模塊.30 3.4.1 功能.30

4、3.4.2 數(shù)據(jù)結(jié)構(gòu).31 3.4.3 算法.33 3.5 符號(hào)表模塊.41 3.5.1 功能.413.5.2 數(shù)據(jù)結(jié)構(gòu).41 3.5.3 算法.43 3.6 目標(biāo)代碼生成模塊.43 3.6.1 功能.433.6.2 數(shù)據(jù)結(jié)構(gòu).44 3.6.3 算法.454 程序設(shè)計(jì)與實(shí)現(xiàn).474.1 程序流程圖.47 4.2 程序說明.47 4.3 實(shí)驗(yàn)結(jié)果.505 結(jié)論.616 參考文獻(xiàn).627 收獲、體會(huì)和建議.62641 概述在計(jì)算機(jī)上執(zhí)行一個(gè)高級(jí)語言程序一般要分為兩步；第一步，把高級(jí)語言翻譯成機(jī)器語言程序；第二步，運(yùn)行所得的機(jī)器語言程序求得計(jì)算結(jié)果。編譯程序就是將高級(jí)語言程序翻譯成機(jī)器語言程序或匯編

5、語言程序的工具。工作過程一般可以劃分為五個(gè)階段：詞法分析、語法分析、語義分析和中間代碼生成、優(yōu)化、目標(biāo)代碼生成。前端包含詞法分析、語法分析、語義分析和中間代碼生成三個(gè)階段，后端包含優(yōu)化、目標(biāo)代碼生成兩個(gè)階段。詞法分析的任務(wù)是對(duì)構(gòu)成源程序的字符串進(jìn)行分解和掃描，識(shí)別出一個(gè)個(gè)Token序列，并標(biāo)上類別碼以區(qū)分關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、變量、數(shù)組界符等。詞法分析器用自動(dòng)機(jī)實(shí)現(xiàn)，每讀入一個(gè)字符，就進(jìn)行狀態(tài)轉(zhuǎn)移，當(dāng)轉(zhuǎn)移到終止?fàn)顟B(tài)的時(shí)候一個(gè)Token就識(shí)別出來了。此外，詞法分析還要進(jìn)行常數(shù)處理、關(guān)鍵字和標(biāo)識(shí)符的區(qū)分操作。語法分析在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，確定整個(gè)輸入串在語法上是否是正確的。分析方

6、法有遞歸下降子程序分析法、LL(1)分析法、LR(0)分析法、簡單優(yōu)先分析法等。在語義分析和中間代碼生成這一過程中，對(duì)語法分析所識(shí)別的各類語法范疇，要分析其含義，并以四元式的形式產(chǎn)生中間代碼。優(yōu)化的任務(wù)在于對(duì)中間代碼進(jìn)行加工變換以產(chǎn)生出更為高效的目標(biāo)代碼，主要進(jìn)行常數(shù)合并、公共子表達(dá)式節(jié)省、刪除無用賦值、循環(huán)優(yōu)化等操作。目標(biāo)代碼生成的任務(wù)是把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼，這一步需要考慮硬件系統(tǒng)結(jié)構(gòu)、機(jī)器指令以及寄存器個(gè)數(shù)等情況，將一中間代碼程序段翻譯成匯編語言或機(jī)器語言目標(biāo)代碼。此外，在這五個(gè)階段當(dāng)中，符號(hào)表的管理、錯(cuò)誤處理要穿插在當(dāng)中進(jìn)行。本次課設(shè)將前端的三個(gè)階段整合到一起，通過對(duì)

7、輸入的源程序掃描一遍的方式實(shí)現(xiàn)，入口為語法分析，使用遞歸下降子程序分析法。將詞法分析器作為語法分析的子程序，當(dāng)語法分析需要用到Token時(shí)，調(diào)用詞法分析器識(shí)別出一個(gè)Token串，同時(shí)在語法分析的過程中插入語義動(dòng)作，每識(shí)別完一定的Token串就能生成四元式。在后端則直接根據(jù)四元式生成目標(biāo)代碼。符號(hào)表用于存儲(chǔ)變量以及檢查是否有重定義、未定義的變量。在錯(cuò)誤處理中，一旦發(fā)現(xiàn)錯(cuò)誤，就進(jìn)行輸出并立即停止編譯過程。2 課程設(shè)計(jì)任務(wù)及要求2.1 設(shè)計(jì)任務(wù)定義一個(gè)簡單程序設(shè)計(jì)語言文法（包括變量說明語句、算術(shù)運(yùn)算表達(dá)式、賦值語句；擴(kuò)展包括邏輯運(yùn)算表達(dá)式、If語句、While語句等）；掃描器設(shè)計(jì)實(shí)現(xiàn)；語法分析器設(shè)計(jì)

8、實(shí)現(xiàn)；中間代碼設(shè)計(jì)；中間代碼生成器設(shè)計(jì)實(shí)現(xiàn)；目標(biāo)代碼生成。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、確定測試方案，選擇測試用例，對(duì)系統(tǒng)進(jìn)行測試；5、運(yùn)行系統(tǒng)并要通過驗(yàn)收，講解運(yùn)行結(jié)果，說明系統(tǒng)的特色和創(chuàng)新之處，并回答指導(dǎo)教師的提問；6、提交課程設(shè)計(jì)報(bào)告。3 算法與數(shù)據(jù)結(jié)構(gòu)3.1 算法的總體思想（流程）對(duì)給定的一段源程序，先進(jìn)行前端分析。前端包括詞法分析、語法分析、語義分析和中間代碼

9、生成三個(gè)階段，這三個(gè)階段通過對(duì)輸入的源程序掃描一遍的方式即可實(shí)現(xiàn)，詞法分析器作為語法分析的子程序，當(dāng)語法分析需要用到Token時(shí)，調(diào)用詞法分析器識(shí)別出一個(gè)Token串，同時(shí)在語法分析的過程中插入語義動(dòng)作，在進(jìn)行語法分析的同時(shí)也能生成四元式。然后將生成的四元式交給后端進(jìn)行目標(biāo)代碼生成。此外，符號(hào)表用來記錄源程序中出現(xiàn)的變量，如果在分析的過程中出現(xiàn)錯(cuò)誤，則進(jìn)行錯(cuò)誤處理，將哪一行出現(xiàn)的哪種錯(cuò)誤輸出。具體流程圖如下：源程序前端（詞法分析、語法分析、語義分析和中間代碼生成）后端（目標(biāo)代碼生成）中間代碼目標(biāo)代碼符號(hào)表管理錯(cuò)誤處理3.2 詞法分析模塊3.2.1 功能識(shí)別器：詞法分析器中識(shí)別器的具體功能為識(shí)別

10、單詞的有限自動(dòng)機(jī)。單詞符號(hào)是一個(gè)程序語言的基本語法符號(hào)。程序語言的單詞符號(hào)一般可分為下列4種。（1）關(guān)鍵字：由程序語言定義的具有固定億的標(biāo)識(shí)符。有時(shí)稱這些標(biāo)識(shí)符為保留字或基本字。（2）標(biāo)識(shí)符：標(biāo)示各種名字，如變量名，數(shù)組名，函數(shù)名等。 （3）常數(shù)：程序中出現(xiàn)用來運(yùn)算的數(shù)值，即以自身形態(tài)面對(duì)用戶和系統(tǒng)。（4）界符：單字符界符：+,*,/,！,%等。雙字符界符：=,=,19,23,24,=,25,&,26,|,27,!,28,+,29,30,*,31,/,32,%,33,35,36,;,37,(,38,),39,40,41,42,43數(shù)組,44;/界符表還有對(duì)常數(shù)的處理和數(shù)組的單獨(dú)處理（編號(hào)和屬性

11、的區(qū)分）。3.2.3 算法：數(shù)組處理：先查找字符找到數(shù)組的左括號(hào)，將其賦值為“0”，然后再找到右括號(hào)，將數(shù)組標(biāo)號(hào)的值計(jì)算出來。+dd-ddddd.e+|-整數(shù)小數(shù)e指數(shù)e常數(shù)處理：詞法分析的算法流程圖：開始結(jié)束調(diào)用識(shí)別器關(guān)鍵字/標(biāo)識(shí)符算術(shù)常數(shù)結(jié)束符#查KT表查到查填I(lǐng)T表查填CT表常數(shù)處理C.TOKEN查PT表P.TOKENI.TOKENK.TOKENyn查到ere:非法界符ynyynnny3.3 語法分析模塊3.3.1 功能語法分析是編譯的第二階段，其任務(wù)是識(shí)別和處理比單詞更大的語法單位，如：程序設(shè)計(jì)語言中的表達(dá)式、各種說明和語句乃至全部源程序，指出其中的語法錯(cuò)誤；必要時(shí)，可生成內(nèi)部形式，便

12、于下一階段處理。另一方面語法分析是編譯過程的核心部分。它的任務(wù)是在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。語法分析器在編譯程序中的地位也是非常重要。語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。因此，語法分析器的工作本質(zhì)上就是按照文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。 按照語法分析樹的建立方法，可以粗略的把語法分析方法分成兩類，一類是自上而下的分析方法，另一類是自下而上的分析方法。在本次的課程設(shè)計(jì)中我們組使用的是自上而下的分析方法中的遞歸下降分析法，用這種分析法的好處是，直觀易懂，便于表示做遞歸和因子提取，對(duì)文法的要求比較低，可以通過文法變換的方法將其轉(zhuǎn)換為

13、遞歸下降的方式。通過遞歸下降的方法將文法翻譯成語法制導(dǎo)的形式，將接收到的token串進(jìn)行掃描分析。本次試驗(yàn)我們其中一大亮點(diǎn)就是編譯前端在語法分析的基礎(chǔ)上進(jìn)行一遍掃描，完成詞法分析，語法分析，符號(hào)表填充以及中間代碼的生成。這樣要求在語法分析時(shí)每次接收一個(gè)token串(結(jié)構(gòu)體)，這樣在進(jìn)行語法分析的時(shí)候?qū)⒎?hào)表語義動(dòng)作和四元式生成的語義動(dòng)作嵌入到其中便可以達(dá)到目的。同時(shí)我們本次實(shí)驗(yàn)一個(gè)很大的亮點(diǎn)就是我們對(duì)數(shù)組進(jìn)行了識(shí)別以及各種運(yùn)算操作，支持?jǐn)?shù)組聲明，賦值，數(shù)組元素的計(jì)算等等。同時(shí)在語法中出現(xiàn)的錯(cuò)誤會(huì)報(bào)告出來，并終止程序的運(yùn)行。例如缺少分號(hào)，大括號(hào)，小括號(hào)等等。3.3.2 數(shù)據(jù)結(jié)構(gòu)在詞法分析中已經(jīng)定

14、義的token結(jié)構(gòu)體typedef struct tokenchar s20;int code;extramessage extra;token;/token結(jié)構(gòu)體對(duì)于語法分析過程而言，其處理的數(shù)據(jù)是來自于Token序列，是詞法分析的產(chǎn)物。語法分析的任務(wù)就是識(shí)別和處理比單詞更大的語法單位，比如：程序設(shè)計(jì)語言中的表達(dá)式、各種說明和語句乃至全部程序。主要是通過子程序的遞歸調(diào)用完成語法分析，沒有過多的結(jié)構(gòu)體。以下是我們本次實(shí)驗(yàn)的文法：iT標(biāo)識(shí)符：00cT字符：01sT字符串：02CT常數(shù)：03KT關(guān)鍵字：void 04,char 05,short 06,int 07,long long 08,flo

15、at 09,double 10,bool 11,if 12,else 13,while 14,do 15,for 16,main 17,return 18PT界符：= 19, 23, 24,= 25,& 26,| 27,! 28,+ 29,- 30,* 31,/ 32,% 33, 35, 36,; 37,( 38,) 39, 40, 41, 42, 431 語言的文法產(chǎn)生式集合程序定義 ( ) /只有主函數(shù)語句定義 | | | | ； ， | | = | = | = = ； | = ； | = ； if（） | if（） else while () 邏輯語句定義 | | & | 1 | 2 |

16、 算術(shù)表達(dá)式定義 0 | 1 | | 2 | ( ) | 類型定義 int | double | char | 單詞集定義 | | e | | . 字符集定義 A|B|C|Z|a|b|c|z 0|1|2|3|4|5|6|7|8|9 其中：0 +或- 1 *或/或% 2 單目運(yùn)算符 1 =或!= 2 =或或=或= GEQ(=)出 口NNEXT(W)Expression GEQ()=NEXT(W)Expression GEQ(=)NEXT(W)Expression GEQ()NNNNExpression 表達(dá)式入 口NEXT(W)TT+ GEQ(+)出 口-NEXT(W)T GEQ(-)NNT 算

17、數(shù)項(xiàng)入 口NEXT(W)YY* GEQ(*)出 口N/NEXT(W)Y GEQ(/)%NEXT(W)Y GEQ(%)NNN入 口NEXT(W)F+ GEQ(+) FN-NEXT(W)F GEQ(-)!NEXT(W)F GEQ(!) 出 口Y 算數(shù)因子NNN入 口PUSH(i)Identifier or const出口（NEXT(W)LogicStatement)NEXT(W)NNNError1Error2F 算數(shù)單元3.4 語義分析和中間代碼生成模塊3.4.1 功能中間代碼是高級(jí)程序語言中，各種語法成分的語義結(jié)構(gòu)表示；它介于源語言和目標(biāo)語言之間。中間代碼設(shè)置的目的是便于編譯的后期處理（如優(yōu)化和

18、目標(biāo)生成）。在我看來，中間代碼即四元式的生成其實(shí)是為后期的一個(gè)準(zhǔn)備過程，這樣做的好處是：便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化工作；使編譯程序改變目標(biāo)機(jī)更容易；使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確，以中間語言為界面，編譯前端和后端的接口更清晰。下面我來介紹一下四元式生成的過程：首先我們要先定義一個(gè)語義棧 SEMi,在語法分析掃描的過程中，我們要將接收的終結(jié)符壓入棧中（PUSH(i) 壓棧函數(shù)(把當(dāng)前 i 壓入語義棧)），這樣每當(dāng)讀到一個(gè)語義動(dòng)作的時(shí)候我們就可以執(zhí)行語義動(dòng)作（GEQ（i），將棧頂和次棧頂元素彈出，生成四元式。不同的語句的四元式結(jié)構(gòu)不同，在此我將四元式進(jìn)行分類：（1） 雙目運(yùn)算符（2） 單目

19、運(yùn)算符（3） 賦值運(yùn)算符（4） 條件語句（5） 循環(huán)語句（6） 數(shù)組 在四元式生成過程中要注意棧頂與次棧頂?shù)某鰲ｍ樞?，分清主操作?shù)和次操作數(shù)，我認(rèn)為合適插入語義動(dòng)作以及語義動(dòng)作的調(diào)用也要選擇恰當(dāng)時(shí)機(jī)。3.4.2 數(shù)據(jù)結(jié)構(gòu)定義語義棧，鏈?zhǔn)綏ypedef struct tokenstack tokennode *base; tokennode *top; SqStack;定義四元式域結(jié)構(gòu)體 struct FourFactor token Factor; bool active; ;定義四元式結(jié)構(gòu)體鏈表 typedef struct FourItem char operators20; FourF

20、actor Factor3; struct FourItem *next; FourItem;/四元式結(jié)構(gòu)體鏈表在中間代碼生成過程中，考慮到四元式的數(shù)量不確定，我們通過結(jié)構(gòu)體鏈表作為主要的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)生成的四元式，同時(shí)套用結(jié)構(gòu)體來對(duì)四元式的4個(gè)域進(jìn)行分定義：token類型和bool類型。Bool類型為了后期的目標(biāo)代碼生成做準(zhǔn)備。定義的鏈?zhǔn)綏Ｒ彩菗?dān)心空間不夠用。同時(shí)我們組對(duì)臨時(shí)變量的處理也是恰到好處：token Token1; Token1.s0=t; tot+; int now=tot; int len; for(len=1;now;len+) Token1.slen=now%10+0; now=now/10; for(int i=