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

1、編譯原理程序設(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ǔ)言的程序。編譯是從源代碼（通常為高階 語(yǔ)言）到能直接被計(jì)算機(jī)或虛擬

2、機(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í)非常有用。“源碼到源碼編譯器”是指用一種高階語(yǔ)言作為輸入，輸出也是高階語(yǔ)言的 編譯器。例如：自動(dòng)并行化編譯器經(jīng)常采用一種高階語(yǔ)言作為輸入，轉(zhuǎn) 換其中的代碼，并用并行代碼注釋對(duì)它進(jìn)行注釋（如OpenMP或者用語(yǔ) 言構(gòu)造進(jìn)行注釋（如FORTRA的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)，這五個(gè)對(duì)應(yīng)階段分為編譯器的前

4、段，中間代碼以及后端。其中詞法分析器利用超前搜索、狀態(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)鍵詞：編譯原理，前端，中間代碼生成，后端,目錄設(shè)計(jì)分工2摘要31. 概 述72. 課程設(shè)計(jì)任務(wù)及要求92.1設(shè)計(jì)任務(wù)92.2設(shè)計(jì)要求102.3設(shè)計(jì)的文法結(jié)構(gòu)113. 算法及數(shù)據(jù)結(jié)構(gòu)173.1算法的總體思想（流程） 173.2詞法分析器模塊183.2.1 功能18數(shù)據(jù)結(jié)構(gòu) 19流程圖 203.2.4 算法20運(yùn)行截圖 223.3語(yǔ)法分析器模塊233.3.1 功能23數(shù)據(jù)結(jié)構(gòu) 24流程圖 253.3.4 算法26運(yùn)行截圖 333.4符號(hào)表生成模塊

6、343.4.1 功能34數(shù)據(jù)結(jié)構(gòu)35流程圖373.4.4 算法38運(yùn)行截圖393.5中間代碼生成模塊 393.5.1 功能40數(shù)據(jù)結(jié)構(gòu) 41流程圖 433.5.4 算法43運(yùn)行截圖 443.6中間代碼優(yōu)化模塊 443.6.1 功能44362數(shù)據(jù)結(jié)構(gòu)45流程圖 463.6.4 算法47運(yùn)行截圖493.7目標(biāo)代碼生成模塊503.7.1 功能50數(shù)據(jù)結(jié)構(gòu) 51流程圖 513.7.4 算法52運(yùn)行截圖 54這里不得不提到目標(biāo)代碼生成中存在的一些問(wèn)題， 554. 程序設(shè)計(jì)與實(shí)現(xiàn)584.1程序說(shuō)明584.2實(shí)驗(yàn)結(jié)果615. 結(jié)論635.1組長(zhǎng)：宋世波635.2組員：孫何奇645.3組員：黃潤(rùn)華646. 收

7、獲、體會(huì)和建議。666.1組長(zhǎng)：宋世波666.2組員：孫何奇676.3組員：黃潤(rùn)華 677. 附錄69源代碼：697.1可執(zhí)行文件鏈接698. 參考文獻(xiàn)701. 概 述本程序?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)建得到的詞法序列為二元式，二元式由兩部分組成，其種別碼和類型組成，其中關(guān)鍵字和界符記錄其數(shù)字，用到時(shí)只需查

8、其 對(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)行入棧出棧，匹配到相同的則

9、認(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ǔ)法分析相割裂開來(lái)，中間代碼生成采取的 是自底向上進(jìn)行分析，不過(guò)是基于單詞序列進(jìn)行的分析，其操作等于是 使用已獲得的偽動(dòng)作序列，與

10、源程序去作比較，找出偽動(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圖改造后便又重新由樹組裝四元式，組裝好的四元式又再次重新輸出到文件中。目標(biāo)代碼生成部分較長(zhǎng)，也并不僅僅包含目標(biāo)代碼生成部分，在這 個(gè)部分文件中，同時(shí)需要對(duì)前述獲得的符號(hào)表，中間代碼進(jìn)行再處理， 以得到符號(hào)目標(biāo)代碼生成所用的符號(hào)表和中

11、間代碼，再進(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ì)

12、實(shí)現(xiàn)； 語(yǔ)法分析器設(shè)計(jì)實(shí)現(xiàn)； 中間代碼設(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)

13、代碼設(shè)計(jì)11. 目標(biāo)代碼生成器設(shè)計(jì)實(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)表

14、系統(tǒng)。語(yǔ)法分析階段：LL1型產(chǎn)生式、分析表、語(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. <函數(shù)定義 >-> < 類型 > < 標(biāo)識(shí)符 > （ < 參數(shù)聲明> ） <函數(shù)塊> 2. < 類型 > ->i nt|float|char|void|$3. <因式 >-> （ < 表達(dá)式&g

15、t; ）| < 標(biāo)識(shí)符> | <數(shù)字> |<字符>4. <表達(dá)式 > -> < 因子 > < 項(xiàng)>5. <因子 > -> < 因式> < 因式遞歸>6. <因式遞歸>-> * < 因式 > < 因式遞歸> | / < 因式 > < 因式遞歸> | $7. <項(xiàng)>-> + <因子< 項(xiàng)| - < 因子 > < 項(xiàng)| $8. <參數(shù)聲明 >-> &l

16、t; 聲明 > <聲明閉包> | $9. <聲明 >-> < 類型 > < 標(biāo)識(shí)符 > < 賦初值> |<標(biāo)識(shí)符 ><賦初值>10. <賦初值 >-> = < 右值> | $11. <右值 >-> < 表達(dá)式>12. <聲明閉包 >-> , < 聲明> <聲明閉包> | $13. <函數(shù)塊 > -> < 聲明語(yǔ)句閉包 > < 函數(shù)塊閉包>14. <聲明

17、語(yǔ)句閉包 > -> < 聲明語(yǔ)句 > <聲明語(yǔ)句閉包> | $15. <聲明語(yǔ)句 >-> < 聲明> ;16. <函數(shù)塊閉包 >-> < 賦值函數(shù) > < 函數(shù)塊閉包> | vwhile 循環(huán) > < 函數(shù) 塊閉包> I <條件語(yǔ)句 > <函數(shù)塊閉包> | <函數(shù)返回 > <函數(shù)塊閉包> |<cout 語(yǔ)句 ><函數(shù)塊閉包>|<cin語(yǔ)句 ><函數(shù)塊閉包>| $17. <

18、;賦值函數(shù) >-> < 標(biāo)識(shí)符 > < 賦值或函數(shù)調(diào)用>18. <賦值或函數(shù)調(diào)用 > -> = < 右值> ;| （ <參數(shù)列表> ）;19. <參數(shù)列表 >-> < 參數(shù) > <參數(shù)閉包>20. 參數(shù)閉包 - , 參數(shù) 參數(shù)閉包 | $21. <參數(shù) > -> < 標(biāo)識(shí)符> | <數(shù)字> | <字符串>22. vWhile循環(huán)>->while(<邏輯表達(dá)式>)<函數(shù)塊>23. <

19、邏輯表達(dá)式 > -> < 表達(dá)式 > < 邏輯運(yùn)算符 > < 表達(dá)式>24. <邏輯運(yùn)算符 > -> < | > | = |>=|<=25. <條件語(yǔ)句> -> if ( <邏輯表達(dá)式> ) <函數(shù)塊> <否則語(yǔ)句>26. <否則語(yǔ)句> -> else <函數(shù)塊> | $27. <函數(shù)返回> -> return <因式> ;28. vcout 語(yǔ)句 >->cout<<

20、< 標(biāo)識(shí)符 >|cout<< < 數(shù)字>|cout<< < 字符 >29. vein 語(yǔ)句 >->cin>>< 標(biāo)識(shí)符 >；產(chǎn)生式如下：fun cdef%type&id&(&parastate&)&&fun cblock&&#type%i nt|float|char|void &#factor%(&exp&)|id| nu mber|ch &#exp%di vi&ite m&#divi%f

21、actor&faccycle &#faccycle%*&factor&faccycle|/&factor&faccycle|$ &#item%+&divi&item |-&di vi&item|$&#parastate%state&stateclo|$ &#state%type&id&in it|id&in it&#ini t%=&rvalue|$ &#rvalue%exp&#stateclo%, &stateclo|$

22、&#fun cblock%staclo&fun cbloclo &#staclo%stateme nt&staclo|$&#stateme nt%state&&#fun cbloclo%opera &fun cbloclo|whilecycle&fun cbloclo|con distate&fun cbloclo|fu ncend&fun cbloclo|coutstate &fun cbloclo|c in state&fun cbloclo|$ &#opera%id &

23、callstate&#callstate%=&rvalue&|(&paralist&)&&#paralist%para&paracl o&#paraclo%,&para&paraclo|$&#para%id |nu mber|stri ng&#whilecycle%while&(&logicexp&)&do&&fun cblock&&we&#logicexp%exp&l ogicopera&exp &am

24、p;#logicopera%>|<|=|>=|v二&#con distate%if&(&logicexp&)&&fun cblock&&n or&ie&#nor%else&&fun cblock& |$ &#funcen d%return &factor&&# coutstate%cout&<&<&id&&# cin state%ci n&>&>&id&a

25、mp;&# do%$ &#we%$ &#ie%$ &#詞法分析序列表:標(biāo)識(shí)符表i常數(shù)表C關(guān)鍵子表KInt1Float2Char3Stri ng4Void5If6Else7Switch8Case9For10Do11While12Con ti nue13Break14Default15Sizeof16Retur n17Cout18Cin19界符表P>=1<=2=3=4>5<6+7-8*9/101112J13J14(15)161718字符表Ch字符串表st3. 算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）中間代碼優(yōu)化目標(biāo)代碼生成結(jié)束算法總體思想文

26、字解釋如下：1. 從文件中讀取代碼，調(diào)入詞法分析，生成詞法序列。2. 而后將詞法序列傳遞給語(yǔ)法分析器，語(yǔ)法分析器從文件中讀入產(chǎn)生式，自動(dòng)產(chǎn)生first集和follow集，構(gòu)建出完整的分析表，而后與得到 的詞法序列進(jìn)行比較，吮吸進(jìn)行語(yǔ)法分析，按照分析表查得產(chǎn)生式進(jìn) 行入棧出棧，完成LL1語(yǔ)法分析的整個(gè)過(guò)程。3. 符號(hào)表繼續(xù)使用詞法序列，不依賴于語(yǔ)法分析而直接構(gòu)建符號(hào)表，依 據(jù)詞法中的標(biāo)識(shí)符直接構(gòu)建函數(shù)表、參數(shù)表、符號(hào)表和活動(dòng)記錄表， 并對(duì)于其后的目標(biāo)代碼生成產(chǎn)生作用。4. 中間代碼生成模塊使用語(yǔ)法分析過(guò)程中所獲得的偽動(dòng)作序列，同時(shí)依靠獲得的詞法分析序列，逐個(gè)進(jìn)行比對(duì)，同時(shí)將標(biāo)識(shí)符依次入棧，需要時(shí)

27、取出，通過(guò)完整棧區(qū)的出棧入棧實(shí)現(xiàn)整個(gè)中間代碼（四元式）的 填寫。5. 中間代碼優(yōu)化模塊獲取前述過(guò)程中所生成的四元式文件，而后依托于四元式構(gòu)建DAG圖，由產(chǎn)生的DAG圖采用教材ppt所述方法按節(jié)點(diǎn) 進(jìn)行優(yōu)化，直接產(chǎn)生優(yōu)化后的 DAG圖并生成優(yōu)化后的四元式填裝回 文件中。6. 目標(biāo)代碼生成部分直接提取之前編譯器部分所獲得的四元式和符號(hào)表，依據(jù)其成果直接構(gòu)建目標(biāo)代碼（匯編代碼，8086指令集），同時(shí)在此其中進(jìn)行類型檢查，重定義等，完成語(yǔ)義分析。3.2詞法分析器模塊（負(fù)責(zé)人：宋世波）功能1獲取待處理的源代碼2生成二元式序列3. 采用DFA和自動(dòng)機(jī)實(shí)現(xiàn)二元式的填寫4. 將獲得的二元式輸入到文件中詞法分析

28、過(guò)程是將字符序列轉(zhuǎn)換為 Token序列的過(guò)程。此階段的任 務(wù)是從左到右依次掃描源程序中的字符，即對(duì)構(gòu)成字符流進(jìn)行掃描然后 根據(jù)構(gòu)詞規(guī)則識(shí)別Token。設(shè)計(jì)的詞法分析器能相對(duì)完善地構(gòu)造出不同的單詞，用二元式的形式存儲(chǔ)，簡(jiǎn)顯易懂，并將新的標(biāo)識(shí)符單詞填入變臉 表當(dāng)中，實(shí)現(xiàn)在計(jì)算機(jī)內(nèi)單詞序列的統(tǒng)一存儲(chǔ)。322數(shù)據(jù)結(jié)構(gòu)enumstyle I , C K, P, Ch, St, def; /* 枚舉種類 */static char *keyword18= "int" , "float" , "char" , "void" ,

29、"if" , "else" , "switch" , "case" , "for ","do", "while" , "continue" , "break" , "default" , "sizeof" , "return" "cout" , "cin" ; /* 關(guān)鍵字表 */static char *delimi

30、ters18= ">=", "<=", "=", "=" , ">" , "<" ,"+" ,"-" , "*" ,"/"II(",")","","" /* 界符表 */char variate1610 = ;/* 變量表 */static struct twoele /* 二元式數(shù)據(jù)結(jié)構(gòu) */style

31、 kind;char value125;int value2;二元式包含三項(xiàng)，但實(shí)際使用時(shí)只會(huì)用到其中兩項(xiàng)，單詞種類的不 同決定了其對(duì)應(yīng)有不同的處理方式，kind用來(lái)存放種類，value1和value2 都是用來(lái)存儲(chǔ)單詞所含值的，相對(duì)于不同類單詞有不同處理方式。而其 中kind所可為的值以及在上面數(shù)據(jù)結(jié)構(gòu)中相應(yīng)的有所列出的，對(duì)應(yīng)查較 即可。具體分配如下，當(dāng)單詞為關(guān)鍵字或者界符時(shí)，使用的是 kind和value2項(xiàng)，即value2存儲(chǔ)對(duì)應(yīng)固定表中單詞所對(duì)序列而當(dāng)單詞為其他時(shí)，即單詞為字符、字符串、標(biāo)識(shí)符或者數(shù)字時(shí)， 采取將單詞直接字符串化直接存儲(chǔ)其值，為數(shù)字時(shí)調(diào)用庫(kù)函數(shù)將其字符 化，取出時(shí)候按照

32、其相應(yīng)種別碼采取不同的取出方式。static twoele TOKEN1000;/* 詞法序列（二元式結(jié)構(gòu)）*/323流程圖開始獲取程序代碼Error否為變量?為關(guān)鍵字或變量？是是14關(guān)鍵字掃描數(shù)字掃描否為關(guān)鍵字？變量掃描（含數(shù)組）界符掃描為界符？字符字符串掃描否Error是是否代碼是否已讀完？否一w為字符或字符串？ 是結(jié)束算法static void init_twoele（twoele *tok） /* 初始化二元式，同時(shí)將變量表初始化*/int tra（ char*cmp /*查詢獲得單詞是否為關(guān)鍵字，是則返回關(guān)鍵字序號(hào)*/void addvar( char*cmp /* 加入變量表 */

33、void prep( char ch) /*預(yù)處理，過(guò)濾注釋*/ static void scanner() /* 詞法掃描 */在詞法分析之前有一段的注釋處理部分，其相應(yīng)方案是在遇到/符時(shí)即進(jìn)入注釋處理，而后再次遇到/符時(shí)候認(rèn)為離開注釋處理部分，但有所 控制，若較長(zhǎng)范圍內(nèi)并未再遇到/符則跳出自動(dòng)機(jī)，認(rèn)為/符號(hào)就是一個(gè)單 純的界符，由于c語(yǔ)言中并沒(méi)有/所用的語(yǔ)言，如果此時(shí)并不在字符串中， 可直接進(jìn)行報(bào)錯(cuò)處理。以下就詞法分析遇到的單詞處理方法進(jìn)行分情況解釋：字符：首先是用if判斷字符，字符都會(huì)帶單引號(hào)，所以若識(shí)別出單 引號(hào)則進(jìn)入字符判別部分，執(zhí)行 ch=fgetc(fp)，進(jìn)入下一個(gè)判斷語(yǔ)句，

34、若條件為假則輸出error，這樣可以完成一個(gè)簡(jiǎn)單的報(bào)錯(cuò)功能。若為真的 話，執(zhí)行ch=fgetc(fp)，判斷是否為單引號(hào)，若為假則輸出error，為真就要將找到ch對(duì)應(yīng)的token。(這一段包括在界符處理的字部分中)字符串：字符串的判斷與字符的判斷差不多，不同的是字符串要識(shí) 別的是雙引號(hào)，而且需要加一個(gè)循環(huán)來(lái)將整個(gè)字符串識(shí)別完畢。首先ch若為“，則進(jìn)入字符串的判別部分，ch=fgetc(fp)，然后就要進(jìn)入一個(gè)while循環(huán)，每循環(huán)一次就執(zhí)行ch=fgetc(fp)，若為數(shù)字或字母就將其裝入 字符數(shù)組，否則跳出循環(huán)。剩下的就同識(shí)別字符一樣，若識(shí)別不到”，就輸出error。然后查找token和壓

35、隊(duì)列的操作。標(biāo)識(shí)符：由于關(guān)鍵字也是一些字符串，所以一般放在一起來(lái)判斷， 若不是關(guān)鍵字則為標(biāo)識(shí)符。由于關(guān)鍵字和標(biāo)識(shí)符都必須是以字母開頭， 所以用if為字符來(lái)判斷，為真接著判斷，while循環(huán)來(lái)識(shí)別完整個(gè)標(biāo)識(shí) 符或關(guān)鍵字的部分與識(shí)別字符串相同，也是裝入字符數(shù)組，但比字符串 部分多出一點(diǎn)就是標(biāo)識(shí)符可以有下劃線，所以中間判斷條件會(huì)變成數(shù)字 字符下劃線均可。While循環(huán)結(jié)束后需要在字符數(shù)組的最后一位后加上 0'。識(shí)別完畢后就需要判斷該字符串到底是標(biāo)識(shí)符還是關(guān)鍵字了， 關(guān)鍵字個(gè)數(shù)是固定的，挨個(gè)匹配就可以了，界符：判斷方法簡(jiǎn)單粗暴，直接 switch即可，不過(guò)要注意比如= 這種需要多判一次，即單詞

36、讀取應(yīng)向后延伸一位，其他并沒(méi)有什么難題， 需要注意的是，字符以及字符串判斷也放入了這里面作字部分（由于字 符和字符串開頭的單引號(hào)和“雙引號(hào)也算是實(shí)際意義上的界符）數(shù)字：最后是數(shù)字的識(shí)別，首先，識(shí)別數(shù)字直接進(jìn)行if比較，接著同字符串一樣進(jìn)入循環(huán)識(shí)別整個(gè)數(shù)字，都存入整形數(shù)組。由于要存入常 數(shù)表的應(yīng)該是一個(gè)數(shù)而不是整形數(shù)組，所以應(yīng)做出一個(gè)變量用于計(jì)算置 位，大致思想就是用循環(huán)來(lái)將數(shù)組中的數(shù)乘 10,數(shù)組的第一位先乘10, 每循環(huán)一次增加數(shù)組下一位。將整數(shù)部分都識(shí)別完了后就要判斷是否為小數(shù)或者科學(xué)計(jì)數(shù)法，若 ch為小數(shù)點(diǎn)就進(jìn)入小數(shù)的判斷部分，小數(shù)部分從數(shù)組轉(zhuǎn)變?yōu)樾?shù)的程序 就是將上述的函數(shù)中的乘便為除

37、，然后再識(shí)別符號(hào)后面的數(shù)，轉(zhuǎn)化為整 數(shù)，將之前識(shí)別出來(lái)的數(shù)除或乘該整數(shù)次數(shù)的10，而后用數(shù)字轉(zhuǎn)字符串函數(shù)存入二元式中，二元式種類寫一個(gè)常數(shù)種別碼。運(yùn)行截圖Lal:in1 請(qǐng)IWIHEJiLFfrs-Rllr g 曙 93 wiEitirr 蠱xlstr.v-£ld e n" h- n 1 H-n.-h o H B 2 a o X H sss.fr標(biāo)-tiplfl2llDJlE!j2a233g34J4M1I1B14 4a .yr -yr ij. I. kJ yr TJ L- Hv hr hj hr hr UJ. hr LJ. hr .r £ In. fa fl- J

38、Li 5 ? LJ n» ft H -Mu - 9 n 4 B Tllh .u JJ H 2 6 .u J fl mu al目 1 r : _ " a3 J 4 再40 野ip 胃 <1 V T 陽(yáng) <9 用弓勺u(yù)11int:ZfhriL- ICQ<-5Utfl W 77 H 特龍欝罪fit韻MIThITp鬥也osiallEPiR氧fllaFsnEamT* ndlr 沖山.' 1MI:I7珂覽 HslSTallJT515351'酣L*19- - >»ri al rf did W ¥ sw WEC O4CTJT 宇

39、:一 百3曲帛耳居臂 lnN2.$ErlpNT'¥1NHM石 NNNNNinluinn:! E !tt*frlliT.¥.#wXKKWW»N»w»斥kydK 曲報(bào)loll<llal.二運(yùn)妙:+幻 K w-靈VQz 319%弄fld 字宀nt 神 sasnff . : RF s. s' Eip曲：If萌LPZKJtil-flpEJFiFFivul-FJ-ITiuEltzli肌廚"D 丐斬怖*TH.-rmw-r畫rlr 斥sc新需 峙刑 hh牛 FH杯用t4” rlSJrldI旬嘲S.IFLI固|描?ILJ®

40、;V;!ISI7ILI-SI甘CCI?I打>6w ssl.72ifrF->:;4? n 必強(qiáng)-* 霽皿出 -1 r 112 - - 2 - -i J 4 4 OJ L- D n- 7 - s - ft i 1H ,l_n 1 Id 11 ! T *11Mid .1dIm.ctiUj(9 dELllLL1屮補(bǔ)*3.3語(yǔ)法分析器模塊（負(fù)責(zé)人：宋世波）功能1. 獲取產(chǎn)生式2. 自動(dòng)求first和follow集合3. 構(gòu)建分析表4. 構(gòu)建分析棧5. 通過(guò)查分析表進(jìn)行語(yǔ)法分析6. 輸出動(dòng)作序列LL1文法解釋：LL（1）分析法是指從左到右掃描、最左推導(dǎo)（LL）和只查看一個(gè)當(dāng)前符 號(hào)（括號(hào)中的1

41、）之意；LL（1）分析法又稱預(yù)測(cè)分析法，與遞歸子程序法同屬于自頂向下確定 性語(yǔ)法分析方法；LL(1)分析法的基本要點(diǎn)有三：利用一個(gè)分析表，登記如何選擇產(chǎn)生式的知識(shí)；利用一個(gè)分析棧，記錄分析過(guò)程；此分析法要求文法必須是 LL(1)文法。語(yǔ)法分析是編譯中的第二階段，它的任務(wù)是識(shí)別和處理比單詞更大 的語(yǔ)法單位，判斷源程序在結(jié)構(gòu)上是否正確。從形式上來(lái)說(shuō)，語(yǔ)法分析是對(duì)一個(gè)給定的字符串，判斷它是否為文法 的一個(gè)句子。在我設(shè)計(jì)的語(yǔ)法分析器中，直接采用LL(1)分析方法。當(dāng)然 由于本身文法為上下文無(wú)關(guān)文法，所以純 LL1并沒(méi)有使用問(wèn)題，此外， 對(duì)于錯(cuò)誤的識(shí)別，該語(yǔ)法分析器可以輸出錯(cuò)誤信息。332數(shù)據(jù)結(jié)構(gòu)str

42、uct pronode /* 產(chǎn)生式節(jié)點(diǎn) */type it;char symbol15;；struct product /*產(chǎn)生式數(shù)據(jù)結(jié)構(gòu)*/char vn 15;pron ode itself10;product c100;產(chǎn)生式是從文件中讀入的，也就是本語(yǔ)言的文法結(jié)構(gòu)，其中產(chǎn)生式 結(jié)構(gòu)的首點(diǎn)product為產(chǎn)生式左部，pronode部分為右部。與實(shí)際產(chǎn)生式進(jìn)行比較，很容易知道這個(gè)數(shù)據(jù)結(jié)構(gòu)所允許的任何產(chǎn) 生式右部最多能容納十個(gè)元素，左部元素長(zhǎng)度不超過(guò)十五。對(duì)于文法中的終結(jié)符和非終結(jié)符，在遞歸子程序方法中非終結(jié)符直 接轉(zhuǎn)換為字符串，終結(jié)符則是對(duì)應(yīng)的 Token,但當(dāng)調(diào)用LL(1)子程序時(shí),

43、需要將非終結(jié)符和終結(jié)符都轉(zhuǎn)換為 string類型，這樣做的好處是統(tǒng)一格 式之后便于進(jìn)行壓棧彈棧等操作，但是會(huì)提高算法的時(shí)間復(fù)雜度，屬于 以時(shí)間換空間，用簡(jiǎn)單的數(shù)據(jù)類型便于提高程序的可讀性。typedef struct Node/* 棧中元素節(jié)點(diǎn) */char eleme nt15;struct Node*pNext;NOD,E* PNODEtypedef struct Stack/*堆棧，包含棧頂和棧底*/PNODETop;PNODEBottom; STACK* PSTAC;K這就是一個(gè)正常的堆棧格式，唯一需要注意的是因?yàn)橐c產(chǎn)生式進(jìn) 行入棧出棧，所以元素是用字符串存儲(chǔ)。333流程圖開始T否分

44、析表構(gòu)建子程序，包含求first集合和follow集合W單詞序列是否讀完?334算法bool traverse( char tra 10015,char cmp15) /* 遍歷終結(jié)符和非終結(jié)符表，查看是否存在要加入元素*/int tableprep( char tra 10015,char cmp15)/* 準(zhǔn)備填表 */void inittable()/*分析表的初始化*/void nor( int cmp /* 填表 */void cyclefirst( int i) /* 查 first集合*/void first( int x1, int i, int local ) /* 求 fi

45、rst 集合*/void follow( int i , int x1,int local ) /* 求 follow 集合 */void initproduct()/*初始化產(chǎn)生式結(jié)構(gòu)*/void getselect( int n) /* 判斷為求 first 或 follow 集合 */void tableend()/* 完成分析表 */char* pop( PSTACK)ut) /*獲取棧頂元素用于比較*/void inistack(PSTACK)egin) /* 初始化分析棧 */void analysis( int mint n, PSTACK)ut) /* 分析棧進(jìn)行匹配，按分析

46、表進(jìn)行*/void gra( PSTACK)egin) /*語(yǔ)法分析主體程序*/void before() /*在開始運(yùn)行前對(duì)所用文件進(jìn)行清空重建*/由于分析函數(shù)部分過(guò)多，不采取完整講述，可以簡(jiǎn)單進(jìn)行理解為由于需要遍歷整張產(chǎn)生式表，所以很容易知道first和follow函數(shù)(即求first集和follow集函數(shù))采取的函數(shù)自遞歸，當(dāng)從其產(chǎn)生元式子出發(fā) 后就必須遍歷完整個(gè)產(chǎn)生式表得出結(jié)果，同時(shí)與此傳遞一個(gè)產(chǎn)生式序號(hào) 用于填表。Getselect是一個(gè)區(qū)分函數(shù)，用于區(qū)分該產(chǎn)生式是否能推出空而決定是采用求first或求follow，其中求follow函數(shù)部分允許調(diào)用求first 集合，這也是LL1文

47、法的實(shí)際求法模擬。Tablee nd則是根據(jù)上述操作獲取的數(shù)字逐個(gè)的、順序的形成屬于該文法的分析表，并作為一個(gè)全局變量二維數(shù)組存儲(chǔ)，留存用于馬上的語(yǔ) 法分析。LL(1)分析法是指從左到右掃描，最左推導(dǎo)和只查看一個(gè)當(dāng)前符號(hào)的意 思。它屬于自頂向下確定性語(yǔ)法分析方法。LL(1)分析方法有以下三個(gè)基本要點(diǎn)： 利用一個(gè)分析表，登記如何選擇產(chǎn)生式的知識(shí)；利用一個(gè)分析棧，記錄分析過(guò)程； 此分析法要求文法必須是LL(1)文法。在分析的過(guò)程中，我們將以下變換后的LL(1)文法歸為L(zhǎng)L(1)分析方法的范疇，并且求出了它們對(duì)應(yīng)的select集合(由于非終結(jié)符和終結(jié)符 過(guò)多，無(wú)法在文檔中完全描述出分析表，因此在此僅

48、列出select集合，LL(1)分析表只需根據(jù)集合填寫即可)：以下為完整的分析表：vn/vtid()intfun cdef000001type000002factor870000exp12120000divi13130000faccycle0016000item0019000parastate200210020state23000022init0025000rvalue26260000stateclo0028000fun cblock29000029staclo310003130stateme nt32000032fun cbloclo33000390opera4000000callstate

49、0420000paralist4300000paraclo0045000para4600000whilecycle000000logicexp50500000logicopera000000con distate000000nor58000580funcend000000coutstate000000ci nstate000000do0006200we63000630ie64000640vn/vtfloatcharvoidstrnu mber chfun cdef111100type345600factor0000910exp00001212divi00001313faccycle000000

50、item000000parastate2020202000state2222222200init000000rvalue00002626stateclo000000fun cblock2929292900staclo3030303000stateme nt3232323200fun cbloclo000000opera000000callstate000000paralist0000430paraclo000000para0000470whilecycle000000logicexp00005050logicopera000000con distate000000nor000000funcen

51、d000000coutstate000000cin state000000do000000we000000ie000000vn/vtstri ng*/+-=fun cdef000000type000000factor1100000exp1200000divi1300000faccycle0141516160item00017180parastate000000state000000init0000024rvalue2600000stateclo000000fun cblock000000staclo000000stateme nt000000fun cbloclo000000opera0000

52、00callstate0000041paralist4300000paraclo000000para4800000whilecycle000000logicexp5000000logicopera000000con distate000000nor00funcend00coutstate00cin state00do00we00ie00vn/vt,;whilefun cdef00type00factor00exp00divi00faccycle1616item1919parastate00state00init2525rvalue00stateclo270fun cblock00staclo00stateme nt00fun cbloclo00opera00callstate00paralist00paraclo440para00whilecycle00logicexp00logicopera00con distate00nor00000000000000000000000><