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

1、課 程 設(shè) 計(jì) 報(bào) 告設(shè)計(jì)題目：一個(gè)簡(jiǎn)單文法編譯器的設(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)分析法、簡(jiǎn)單優(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è)簡(jiǎn)單程序設(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、確定測(cè)試方案，選擇測(cè)試用例，對(duì)系統(tǒng)進(jìn)行測(cè)試；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）界符：?jiǎn)巫址绶?,*,/,！,%等。雙字符界符：>=,<=,=,!=,&&,|等。翻譯器：根據(jù)有限自動(dòng)機(jī)所識(shí)別出的對(duì)象，完成從單詞傳到單詞的TOKEN串的翻譯。輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行分解和掃描，識(shí)別出一個(gè)個(gè)的單詞或符號(hào)。具體實(shí)現(xiàn)為設(shè)計(jì)各單詞的狀態(tài)

11、轉(zhuǎn)換圖，并為不同的單詞設(shè)計(jì)種別碼。3.2.2 數(shù)據(jù)結(jié)構(gòu)識(shí)別器關(guān)鍵字或標(biāo)識(shí)符以字母開頭，數(shù)值型常量以字母開頭，字符型常量或字符串常量以或”開頭，其它的多以自身形態(tài)識(shí)別之。如何識(shí)別單詞并尋找其可達(dá)狀態(tài)，我們的方法是利用鏈表構(gòu)建一個(gè)識(shí)別單詞的有限自動(dòng)機(jī)。定義自動(dòng)機(jī)狀態(tài)的結(jié)構(gòu)體鏈表：typedef struct statechar acceptkey;int nextstate;struct state *next;state;/自動(dòng)機(jī)狀態(tài)鏈表結(jié)點(diǎn)構(gòu)建鏈表結(jié)點(diǎn)：typedef struct tokennode token to; struct tokennode *next;tokennode;自動(dòng)機(jī)

12、圖：1230313234668791011121314151617282930212223242526272829llll|ddddd.“>>=<<=!&|&小數(shù)整數(shù)指數(shù)字符字符串>=>><=<<=!=&&|其余翻譯器共用體：union extramessage double num;/常數(shù) int subscript;/數(shù)組下標(biāo);Token結(jié)構(gòu)體：typedef struct tokenchar s20;int code;extramessage extra;token;/token結(jié)構(gòu)體char s

13、tore20；token KT15；token PT25；state *st33一個(gè)程序語言的關(guān)鍵字，運(yùn)算符和界符都是確定的，一般只有幾十個(gè)或上百個(gè)。而對(duì)于標(biāo)識(shí)符或常數(shù)的使用都不加限制。詞法分析器所輸出的單詞符號(hào)常常表示為二元式結(jié)構(gòu)：（單詞種別，單詞符號(hào)的屬性值）；相應(yīng)的數(shù)據(jù)結(jié)構(gòu)處理為：TokenKT15="void",4,"char",5,"short",6,"int",7,"longlong",8,"float",9,"double",10,"

14、;bool",11,"if",12,"else",13,"while",14,"do",15,"for",16,"main",17,"return",18;/關(guān)鍵字表TokenPT25=">=",19,"<=",20,"=",21,"!=",22,">",23,"<",24,"=",2

15、5,"&&",26,"|",27,"!",28,"+",29,"",30,"*",31,"/",32,"%",33,"<<",34,">>",35,",",36,"",37,"(",38,")",39,"",40,"",41,"&

16、quot;,42,"",43"數(shù)組",44;/界符表還有對(duì)常數(shù)的處理和數(shù)組的單獨(dú)處理（編號(hào)和屬性的區(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ù)是

17、識(shí)別和處理比單詞更大的語法單位，如：程序設(shè)計(jì)語言中的表達(dá)式、各種說明和語句乃至全部源程序，指出其中的語法錯(cuò)誤；必要時(shí)，可生成內(nèi)部形式，便于下一階段處理。另一方面語法分析是編譯過程的核心部分。它的任務(wù)是在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。語法分析器在編譯程序中的地位也是非常重要。語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。因此，語法分析器的工作本質(zhì)上就是按照文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。  按照語法分析樹的建立方法，可以粗略的把語法分析方法分成兩類，一類是自上而下的分析方法，另一類是自下而上的分析方法。在本次的課程設(shè)計(jì)中我們組使用的是

18、自上而下的分析方法中的遞歸下降分析法，用這種分析法的好處是，直觀易懂，便于表示做遞歸和因子提取，對(duì)文法的要求比較低，可以通過文法變換的方法將其轉(zhuǎn)換為遞歸下降的方式。通過遞歸下降的方法將文法翻譯成語法制導(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ù)組聲明，賦

19、值，數(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)定義的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

20、字符：01sT字符串：02CT常數(shù)：03KT關(guān)鍵字：void 04,char 05,short 06,int 07,long long 08,float 09,double 10,bool 11,if 12,else 13,while 14,do 15,for 16,main 17,return 18PT界符：>= 19,<= 20,= 21,!= 22,> 23,< 24,= 25,&& 26,| 27,! 28,+ 29,- 30,* 31,/ 32,% 33,<< 34,>> 35, 36,; 37,( 38,) 39, 4

21、0, 41, 42, 431 語言的文法產(chǎn)生式集合·程序定義<程序> à <類型> <標(biāo)識(shí)符> ( ) <復(fù)合語句> /只有主函數(shù)·語句定義<復(fù)合語句> à <語句表> <語句表> à <語句> <語句表> | <語句> à <變量說明語句> | <賦值語句> | <條件語句> | <while語句><變量說明語句> à <類型> &l

22、t;標(biāo)識(shí)符表>；<標(biāo)識(shí)符表> à <變量> <后繼標(biāo)識(shí)符><后繼標(biāo)識(shí)符> à ，<變量><后繼標(biāo)識(shí)符> | <變量> à <標(biāo)識(shí)符> | <標(biāo)識(shí)符> = <算術(shù)表達(dá)式> | <標(biāo)識(shí)符> = <字符> |<標(biāo)識(shí)符> = <字符串> <賦值語句> à <標(biāo)識(shí)符> = <算術(shù)表達(dá)式>； | <標(biāo)識(shí)符> = <字符>； |<標(biāo)

23、識(shí)符> = <字符串>；<條件語句> à if（<邏輯語句>）<復(fù)合語句> | if（<邏輯語句>）<復(fù)合語句> else <復(fù)合語句> <while語句>àwhile (<邏輯語句>) <復(fù)合語句>·邏輯語句定義<邏輯語句> à <邏輯語句> | <邏輯項(xiàng)> | <邏輯項(xiàng)> <邏輯項(xiàng)> à <邏輯項(xiàng)> && <邏輯因子>

24、 | <邏輯因子> <邏輯因子> à <邏輯因子> 1 <邏輯因子2> | <邏輯因子2> <邏輯因子2> à <邏輯因子2> 2 <算術(shù)表達(dá)式> | <算術(shù)表達(dá)式> ·算術(shù)表達(dá)式定義<算術(shù)表達(dá)式> à <算術(shù)表達(dá)式> 0 <項(xiàng)> | <項(xiàng)> <項(xiàng)> à <項(xiàng)> 1 <因子> | <因子> <因子> à <單元>

25、; | 2 <單元><單元> à <算術(shù)量> | ( <邏輯語句> )<算術(shù)量> à <標(biāo)識(shí)符> | <常數(shù)> ·類型定義<類型> à int | double | char | ·單詞集定義<標(biāo)識(shí)符> à <字母> | <標(biāo)識(shí)符> <數(shù)字> | <標(biāo)識(shí)符> <字母><常數(shù)> à <數(shù)> e <數(shù)><數(shù)> 

26、24; <整數(shù)> | <實(shí)數(shù)><整數(shù)> à <數(shù)字> | <整數(shù)> <數(shù)字><實(shí)數(shù)> à <整數(shù)> . <整數(shù)> ·字符集定義<字母> à A|B|C|Z|a|b|c|z<數(shù)字> à 0|1|2|3|4|5|6|7|8|9 其中：0 +或- 1 *或/或% 2 單目運(yùn)算符 1 =或!= 2 >=或>或<=或<對(duì)文法進(jìn)行修改：Programàtype identifier()Comp

27、oundStatementCompoundstatementàStateTableStatetableàStatement StateTable|Statementà說明|賦值|條件|循環(huán)說明àtype IdentifyTable;IdentifyTableàVariate NextStatementNextStatementà,Variate NextStatementVariateàidentifier AAà=Expression|=字符|=字符串|賦值àidentifier=CCàExp

28、ression；|字符；|字符串；條件àif(LogicStatement) CompoundStatement BBàelse CompoundState|循環(huán)àwhile(LogicStatement) CompoundStatement邏輯:LogicStatementà LogicItem| LogicItemLogicItemà LogicFactor1&& LogicFactor1LogicFactor1à LogicFactor2 LogicFactor2LogicFactor2à Expres

29、sion Expression算術(shù):ExpressionàTTTàYYYàF|FFàArithmetic|(LogicStatement)Arithmeticàidentifier|const3.3.3算法下面便是本次遞歸下降子程序的程序框圖（包含語義動(dòng)作）：主程序開 始-1NEXT(W)Program結(jié) 束NError0Program 語法入口入 口typeNEXT(W)出 口identifier(NEXT(W)NEXT(W)CompoundStatementError1Error1Error1NNNNError1入口NEXT(W)State

30、mentTable出 口NError1CompoundStatement 復(fù)合語句StatementTable 語句表入 口StatementStatementTable出 口NYNEXT(W)Statement語句入 口出 口NEXT(W)W)typeIdentifyTableIdentifieror arrayPUSH(i);NEXT(W)NEXT(W)W)=NEXT(W)C GEQ(=)IfWhileCompoundStatementW)NEXT(W)W)(LogicStatementLogicStatementW)NEXT(W)W)NEXT(W)W)CompoundStatementN

31、EXT(W)BW)NNNNNNNNNNError1Error2Error2Error2Error2Error2Error2IdentifyTable標(biāo)識(shí)符表Variate變量入 口NEXT(W)VariateVariate，出 口N入 口Identifier or arrayPUSH(i)NEXT(W)出 口ANError1A子程序，聲明語句分支入 口 =Next(w)出 口PUSH(i)字符NEXT(W)GEQ(=)字符串PUSH(i)GEQ(=)ExpressionGEQ(=)POP(i)NNC子程序，賦值語句分支入 口出 口PUSH(i)字符NEXT(W)字符串PUSH(i)Expres

32、sion；NEXT(W)NNNLogicStatement 邏輯語句B子程序 條件語句分支入 口elseNEXT(W)Compundstater出 口N入 口NEXT(W)LogicItemLogicItem| GEQ(|)出 口NLogicItem 邏輯項(xiàng)入 口NEXT(W)LogicFactor1LogicFactor1&& GEQ(&&)出 口NLogicFactor1 邏輯因子1入 口NEXT(W)LogicFactor2LogicFactor2= GEQ(=)出 口!=NEXT(W)LogicFactor2 GEQ(!=)NNLogicFactor2

33、邏輯因子2入 口NEXT(W)ExpressionExpression>= GEQ(>=)出 口N>NEXT(W)Expression GEQ(>)<=<NEXT(W)Expression GEQ(<=)NEXT(W)Expression GEQ(<)NNNNExpression 表達(dá)式入 口NEXT(W)TT+ GEQ(+)出 口-NEXT(W)T GEQ(-)NNT 算數(shù)項(xiàng)入 口NEXT(W)YY* GEQ(*)出 口N/NEXT(W)Y GEQ(/)%NEXT(W)Y GEQ(%)NNN入 口NEXT(W)F+ GEQ(+) FN-NEXT

34、(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)化和目標(biāo)生成）。在我看來，中間代碼即四元式的生成其實(shí)是為后期的一個(gè)準(zhǔn)備過程，這樣做的好處是：便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化工作；使編譯程序改變目標(biāo)機(jī)更容易；使編譯程序的結(jié)構(gòu)在邏輯上更

35、為簡(jiǎn)單明確，以中間語言為界面，編譯前端和后端的接口更清晰。下面我來介紹一下四元式生成的過程：首先我們要先定義一個(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） 單目運(yùn)算符（3） 賦值運(yùn)算符（4） 條件語句（5） 循環(huán)語句（6） 數(shù)組 在四元式生成過程中要注意棧頂與次棧頂?shù)某鰲ｍ樞颍智逯鞑僮鲾?shù)和次操作數(shù)，我認(rèn)為合適插入語義動(dòng)作以及語義動(dòng)作

36、的調(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; FourFactor Factor3; struct FourItem *next; FourItem;/四元式結(jié)構(gòu)體鏈表在中間代碼生成過程中，考慮到四元式的數(shù)量不確定，我們通過結(jié)構(gòu)體鏈

37、表作為主要的數(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=1;i<=len/2;i+) char tmp=Token1.si; Token1.si=T

38、oken1.slen-i; Token1.slen-i=tmp; Token1.slen='$'Token1.slen+1='0'通過一個(gè)字符數(shù)組來對(duì)要生成的臨時(shí)變量t進(jìn)行標(biāo)號(hào)，從t1開始，由于我們的棧操作都是token類型，所以臨時(shí)變量也定義成token類型，解決了類型問題。3.4.3算法：四元式的流程圖在語法分析中也涵蓋了，下面我來分模塊來列舉一下語義動(dòng)作的插入，不一一介紹了。四元式生成流程圖：開 始語法分析掃描判斷是否為語義動(dòng)作？終結(jié)符入棧將語義棧頂和次棧頂彈棧處理生成四元式結(jié) 束雙目算術(shù)運(yùn)算符：+，-，*，/,%入 口NEXT(W)TT+ GEQ(+)出

39、 口-NEXT(W)T GEQ(-)NN單目運(yùn)算符：正，負(fù)，非入 口NEXT(W)F+ GEQ(+) FN-NEXT(W)F GEQ(-)!NEXT(W)F GEQ(!) 出 口NNN雙目邏輯運(yùn)算符：>=,>,<=,<,=,!=,|,&&入 口NEXT(W)ExpressionExpression>= GEQ(>=)出 口N>NEXT(W)Expression GEQ(>)<=<NEXT(W)Expression GEQ(<=)NEXT(W)Expression GEQ(<)NNNN賦值語句：入 口出 口I

40、dentifieror arrayPUSH(i)NEXT(W)W)W)=NEXT(W)W)C GEQ(=)NError2條件語句（if, else,ifend）If(LogicStatement)NEXT(W)W)CompoundStatementNEXT(W)W)GEQ(IE)W)GEQ(IF)W)BW)出 口入 口Error2Error2NN入 口elseNEXT(W)Compundstater出 口NGEQ(EL)循環(huán)語句（while,do,while end）出 口WhileCompoundStatementW)NEXT(W)W)(LogicStatementW)NEXT(W)W)NN

41、NError1Error2Error2GEQ(WH）W)GEQ(DO)GEQ(WE)W)入 口3.5 符號(hào)表模塊3.5.1功能在編譯的各個(gè)分析階段，每遇到一個(gè)名字都要查找符號(hào)表。如果發(fā)現(xiàn)一個(gè)新的名字或者發(fā)現(xiàn)已有信息名字，則要修改符號(hào)表，填入新的名字和信息。符號(hào)表所登記的信息在編譯不同階段要用到。例如在語義分析中，符號(hào)表所登記的內(nèi)容將用于語義檢查和產(chǎn)生中間代碼。在目標(biāo)代碼生成階段，當(dāng)對(duì)符號(hào)名進(jìn)行地址分配時(shí)，符號(hào)表是地址分配的依據(jù)。對(duì)于一個(gè)多遍掃描的編譯程序，不同遍所用的符號(hào)表也往往不同。3.5.2數(shù)據(jù)結(jié)構(gòu)所用的數(shù)據(jù)結(jié)構(gòu)為嵌套的結(jié)構(gòu)體鏈表，是一個(gè)復(fù)合表。共有三個(gè)表：表，類型表，數(shù)組表。其中主表存有

42、name（標(biāo)識(shí)符名字），type（指向類型表相應(yīng)項(xiàng)的指針），cat（種類），add（地址），active（活躍狀態(tài)）。類型表tval(類型代碼)，tpoint（如果數(shù)據(jù)類型為數(shù)組型，則指向數(shù)組表的指針）。數(shù)組表有l(wèi)ow（下界），up（上界），ctp（數(shù)組成分類型），clen（數(shù)組長度）。具體如下：typedefstructint low;int up;intctp;intclen;bool *active;Array; /數(shù)組表typedefstructinttval; Array *tpoint;Tapel;/類型表typedefstruct Symbolchar name20;Tapel

43、*type;int kind;bool active;intaddr; Symbol *next;Symbol,*Sym; /主表3.5.3 算法結(jié)構(gòu)體鏈表采用尾插法建立，即設(shè)立頭尾節(jié)點(diǎn)，將新的節(jié)點(diǎn)插入尾結(jié)點(diǎn)處。當(dāng)初始化變量時(shí)，先從頭節(jié)點(diǎn)開始掃描，如果表中有相同名字項(xiàng)，則報(bào)錯(cuò)，同時(shí)停止編譯（重定義），如果沒有，插入新的節(jié)點(diǎn)，將新的變量的類型，種類，地址寫入符號(hào)表。當(dāng)查找時(shí)，同樣從頭掃描符號(hào)表，如果有重復(fù)項(xiàng)則表明已定義且正確。如果沒查到則報(bào)錯(cuò)（未定義）且終止編譯。如果查到的項(xiàng)的類型與參數(shù)的不相符，報(bào)錯(cuò)（類型不匹配）且終止編譯。在生成四元式過程中，為臨時(shí)變量建立了一個(gè)小符號(hào)表，每當(dāng)生成一個(gè)臨時(shí)變量

44、時(shí)就將其存入該表。與主表不同的是，小符號(hào)表只存有臨時(shí)變量的名字與類型以及活躍信息active，小符號(hào)表為一個(gè)單表。小符號(hào)表的數(shù)據(jù)結(jié)構(gòu)也是結(jié)構(gòu)體鏈表，構(gòu)造方法同樣為尾插法。typedefstruct Temporarychar name20;int type;struct Temporary *next;bool active;Temporary; /臨時(shí)變量表3.6 目標(biāo)代碼生成模塊3.6.1 功能目標(biāo)代碼生成是編譯程序的最后一個(gè)階段，它以中間代碼作為輸入，以與中間代碼功能相同的目標(biāo)代碼作為輸出。一般來說，生成的目標(biāo)代碼要么是能立即執(zhí)行的機(jī)器語言代碼，要么是匯編語言代碼，還需經(jīng)過匯編程序匯編才

45、能執(zhí)行。在進(jìn)行代碼生成時(shí)，不經(jīng)要考慮如何使生成的代碼盡量短，還要考慮如何更多地利用寄存器，使目標(biāo)代碼執(zhí)行的時(shí)間更短。本課設(shè)生成的目標(biāo)代碼為匯編語言代碼，但不針對(duì)特定的模型機(jī)。3.6.2 數(shù)據(jù)結(jié)構(gòu)在這一模塊用到的數(shù)據(jù)結(jié)構(gòu)有匯編指令鏈表和匯編指令標(biāo)號(hào)棧，它們的定義如下：typedef struct assembly_instruction int id;/標(biāo)號(hào) char operation5;/操作指令 char dest5;/第一操作數(shù) char res5;/第二操作數(shù) int destid;/跳轉(zhuǎn)到的匯編指令標(biāo)號(hào)（針對(duì)跳轉(zhuǎn)指令） struct assembly_instruction *nex

46、t;/該結(jié)點(diǎn)指向的下一個(gè)結(jié)點(diǎn)assembly_instruction;/匯編指令鏈表結(jié)點(diǎn)typedef struct idstacknode int id;/標(biāo)號(hào) struct idstacknode *next;/該結(jié)點(diǎn)指向的下一個(gè)結(jié)點(diǎn)idstacknode;/匯編指令標(biāo)號(hào)棧結(jié)點(diǎn)typedef struct idstack idstacknode *base;/棧底 idstacknode *top;/棧頂idstack;/匯編指令標(biāo)號(hào)棧3.6.3 算法該模塊執(zhí)行過程如下：先對(duì)四元式劃分基本塊，然后目標(biāo)代碼以基本塊為單位生成。對(duì)于每個(gè)基本塊，先初始化變量的活躍信息，然后逆序?qū)γ總€(gè)四元式內(nèi)涉及

47、的變量的活躍信息更新，再依次取出每條四元式進(jìn)行匯編代碼生成，同時(shí)更新當(dāng)前寄存器由哪個(gè)變量占用，當(dāng)一個(gè)基本塊結(jié)束時(shí)，要釋放寄存器的內(nèi)容。最后還要編一條結(jié)束指令。具體流程圖如下：開始劃分基本塊取下一基本塊存在下一基本塊？否生成結(jié)束指令結(jié)束是初始化變量活躍信息逆序更新四元式中變量活躍信息取下一四元式生成匯編指令到達(dá)基本塊出口？否是釋放寄存器更新寄存器當(dāng)前占用變量4 程序設(shè)計(jì)與實(shí)現(xiàn)4.1 程序流程圖程序總體流程圖如下：開始前端（詞法分析、語法分析、語義分析和中間代碼生成）有錯(cuò)誤？是輸出錯(cuò)誤信息否后端（目標(biāo)代碼生成）結(jié)束4.2 程序說明詞法分析：void init()；創(chuàng)建鏈表int changesta

48、te(int nowstate,char ch)；狀態(tài)轉(zhuǎn)換int state_to_code(int laststate)；判別函數(shù)void getnum(token &to)；常數(shù)處理void getnameandsubscript(token &to)；數(shù)組處理token parse(int code,char* store)；token配對(duì)token get()；掃描函數(shù)語法分析：void Program();語法分析void CompoundStatement();復(fù)合語句子程序void StatementTable();語句表子程序void Statement();語

49、句子程序void IdentifyTable();標(biāo)識(shí)符表子程序void Variate();變量子程序void LogicStatement();邏輯語句子程序void LogicItem();邏輯項(xiàng)子程序void LogicFactor1();邏輯因子1子程序void LogicFactor2();邏輯因子2子程序void Expression();表達(dá)式子程序void A();聲明子程序void B();條件語句else子程序void C();賦值子程序void T();算術(shù)項(xiàng)子程序void Y();算術(shù)因子子程序void F();算術(shù)單元子程序void error1();錯(cuò)誤處理1void error2();錯(cuò)誤處理2void GoNext();取當(dāng)前token中間代碼生成：void GEQ_double(char symbol);雙目運(yùn)算符四元式void GEQ_single(char symbol);單目運(yùn)算符四元式void GEQ_assign(char symbol);賦值運(yùn)算四元式void IF();條