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

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

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

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

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

5、整個(gè)編譯過程中還包括對表格的操作和對錯(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)，和輸入輸出語句，能做到直接生成目標(biāo)代碼并運(yùn)行。做到了類型檢查和重定義的判斷，同時(shí)也有優(yōu)化部分。詞法分析部分構(gòu)建得到的詞法序列為二元式，二元式由兩部分組成，其種別

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

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

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

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

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

11、碼生成器設(shè)計(jì)實(shí)現(xiàn)2.2 設(shè)計(jì)要求1、在深入理解編譯原理基本原理的基礎(chǔ)上，對于選定的題目，以小組為單位，先確定設(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、確定測試方案，選擇測試用例，對系統(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)告。以下為本組設(shè)計(jì)要求：給出一個(gè)源程序文件，作為編譯器前端的輸入，輸出相關(guān)編譯階段的運(yùn)行結(jié)果。詞法分析階段：Token序列；關(guān)鍵字表、界符表、符號表系統(tǒng)。語法分析階段：LL1型

12、產(chǎn)生式、分析表、語法分析所用棧符號表生成階段：符號表系統(tǒng)中間代碼生成階段：四元式序列；符號表系統(tǒng)。中間代碼優(yōu)化階段：四元式序列、DAG圖、優(yōu)化完成的四元式序列目標(biāo)代碼生成階段：符號表系統(tǒng)、四元式序列、目標(biāo)代碼(8086指令集)2.3設(shè)計(jì)的文法結(jié)構(gòu)產(chǎn)生式中文對照:1.<函數(shù)定義> -> <類型> <標(biāo)識符> ( <參數(shù)聲明> ) <函數(shù)塊> 2.<類型> ->int|float|char|void|$3.<因式> -> ( <表達(dá)式> ) | <標(biāo)識符> | <數(shù)字

13、> |<字符>4.<表達(dá)式> -> <因子> <項(xiàng)> 5.<因子> -> <因式> <因式遞歸> 6.<因式遞歸> -> * <因式> <因式遞歸> | / <因式> <因式遞歸> | $ 7.<項(xiàng)> -> + <因子> <項(xiàng)> | - <因子> <項(xiàng)> | $ 8.<參數(shù)聲明> -> <聲明> <聲明閉包> | $ 9.

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

15、$ 15.<聲明語句> -> <聲明> ;16.<函數(shù)塊閉包> -> <賦值函數(shù)> <函數(shù)塊閉包> | <while循環(huán)> <函數(shù)塊閉包> | <條件語句> <函數(shù)塊閉包> | <函數(shù)返回> <函數(shù)塊閉包> |<cout語句><函數(shù)塊閉包>|<cin語句><函數(shù)塊閉包>| $ 17.<賦值函數(shù)> -> <標(biāo)識符> <賦值或函數(shù)調(diào)用> 18.<賦值或函數(shù)調(diào)用&

16、gt; -> = <右值> ; | ( <參數(shù)列表> ) ; 19.<參數(shù)列表> -> <參數(shù)> <參數(shù)閉包> 20.<參數(shù)閉包> -> , <參數(shù)> <參數(shù)閉包> | $ 21.<參數(shù)> -> <標(biāo)識符> | <數(shù)字> | <字符串> 22.<While循環(huán)>->while(<邏輯表達(dá)式>)<函數(shù)塊>23.<邏輯表達(dá)式> -> <表達(dá)式> <邏輯運(yùn)算

17、符> <表達(dá)式> 24.<邏輯運(yùn)算符> -> < | > | = |>=|<= 25.<條件語句> -> if ( <邏輯表達(dá)式> ) <函數(shù)塊> <否則語句> 26.<否則語句> -> else <函數(shù)塊> | $ 27.<函數(shù)返回> -> return <因式> ; 28.<cout語句>->cout<< <標(biāo)識符>|cout<< <數(shù)字>|cout&l

18、t;< <字符>29.<cin語句>->cin>><標(biāo)識符>產(chǎn)生式如下：funcdef%type&id&(&parastate&)&&funcblock&&#type%int|float|char|void&#factor%(&exp&)|id|number|ch&#exp%divi&item&#divi%factor&faccycle&#faccycle%*&factor&faccycle|

19、/&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&stacl

20、o|$&#statement%state&&#funcbloclo%opera&funcbloclo|whilecycle&funcbloclo|condistate&funcbloclo|funcend&funcbloclo|coutstate&funcbloclo|cinstate&funcbloclo|$&#opera%id&callstate&#callstate%=&rvalue&|(&paralist&)&&#paralist%para&a

21、mp;paraclo&#paraclo%,&para&paraclo|$&#para%id|number|string&#whilecycle%while&(&logicexp&)&do&&funcblock&&we&#logicexp%exp&logicopera&exp&#logicopera%>|<|=|>=|<=&#condistate%if&(&logicexp&)&&funcb

22、lock&&nor&ie&#nor%else&&funcblock&|$&#funcend%return&factor&&#coutstate%cout&<&<&id&&#cinstate%cin&>&>&id&&#do%$&#we%$&#ie%$&#詞法分析序列表：標(biāo)識符表i常數(shù)表C關(guān)鍵字表KIntFloatCharStringVoidIfElseSwitchCaseForDoW

23、hileContinueBreakDefaultSizeofReturnCoutCin12345678910111213141516171819界符表P>=<=><+-*/,;()123456789101112131415161718字符表Ch字符串表st3. 算法及數(shù)據(jù)結(jié)構(gòu)3.1 算法的總體思想（流程）算法總體思想文字解釋如下：1. 從文件中讀取代碼，調(diào)入詞法分析，生成詞法序列。2. 而后將詞法序列傳遞給語法分析器，語法分析器從文件中讀入產(chǎn)生式，自動(dòng)產(chǎn)生first集和follow集，構(gòu)建出完整的分析表，而后與得到的詞法序列進(jìn)行比較，吮吸進(jìn)行語法分析，按照分析表查得產(chǎn)生

24、式進(jìn)行入棧出棧，完成LL1語法分析的整個(gè)過程。3. 符號表繼續(xù)使用詞法序列，不依賴于語法分析而直接構(gòu)建符號表，依據(jù)詞法中的標(biāo)識符直接構(gòu)建函數(shù)表、參數(shù)表、符號表和活動(dòng)記錄表，并對于其后的目標(biāo)代碼生成產(chǎn)生作用。4. 中間代碼生成模塊使用語法分析過程中所獲得的偽動(dòng)作序列，同時(shí)依靠獲得的詞法分析序列，逐個(gè)進(jìn)行比對，同時(shí)將標(biāo)識符依次入棧，需要時(shí)取出，通過完整棧區(qū)的出棧入棧實(shí)現(xiàn)整個(gè)中間代碼（四元式）的填寫。5. 中間代碼優(yōu)化模塊獲取前述過程中所生成的四元式文件，而后依托于四元式構(gòu)建DAG圖，由產(chǎn)生的DAG圖采用教材ppt所述方法按節(jié)點(diǎn)進(jìn)行優(yōu)化，直接產(chǎn)生優(yōu)化后的DAG圖并生成優(yōu)化后的四元式填裝回文件中。6.

25、 目標(biāo)代碼生成部分直接提取之前編譯器部分所獲得的四元式和符號表，依據(jù)其成果直接構(gòu)建目標(biāo)代碼（匯編代碼，8086指令集），同時(shí)在此其中進(jìn)行類型檢查，重定義等，完成語義分析。3.2 詞法分析器模塊（負(fù)責(zé)人：宋世波）3.2.1 功能1.獲取待處理的源代碼2.生成二元式序列3.采用DFA和自動(dòng)機(jī)實(shí)現(xiàn)二元式的填寫4.將獲得的二元式輸入到文件中 詞法分析過程是將字符序列轉(zhuǎn)換為Token序列的過程。此階段的任務(wù)是從左到右依次掃描中的字符，即對構(gòu)成字符流進(jìn)行掃描然后根據(jù)構(gòu)詞規(guī)則識別Token。設(shè)計(jì)的詞法分析器能相對完善地構(gòu)造出不同的單詞，用二元式的形式存儲，簡顯易懂，并將新的標(biāo)識符單詞填入變臉表當(dāng)中，實(shí)現(xiàn)在計(jì)

26、算機(jī)內(nèi)單詞序列的統(tǒng)一存儲。3.2.2 數(shù)據(jù)結(jié)構(gòu)enum styleI,C,K,P,Ch,St,def;/*枚舉種類*/static char *keyword18 = "int","float","char","void","if","else","switch","case","for","do","while","continue","brea

27、k","default","sizeof","return","cout","cin" ;/*關(guān)鍵字表*/static char *delimiters18 = ">=","<=","=","=",">","<","+","-","*","/","&quo

28、t;,"",",","","(",")" ,"",""/*界符表*/char variate1610 = ;/*變量表*/static struct twoele /*二元式數(shù)據(jù)結(jié)構(gòu)*/style kind;char value125;int value2; 二元式包含三項(xiàng)，但實(shí)際使用時(shí)只會用到其中兩項(xiàng)，單詞種類的不同決定了其對應(yīng)有不同的處理方式，kind用來存放種類，value1和value2都是用來存儲單詞所含值的，相對于不同類單詞有不同處理方式。而其

29、中kind所可為的值以及在上面數(shù)據(jù)結(jié)構(gòu)中相應(yīng)的有所列出的，對應(yīng)查較即可。具體分配如下，當(dāng)單詞為關(guān)鍵字或者界符時(shí)，使用的是kind和value2項(xiàng)，即value2存儲對應(yīng)固定表中單詞所對序列。而當(dāng)單詞為其他時(shí)，即單詞為字符、字符串、標(biāo)識符或者數(shù)字時(shí)，采取將單詞直接字符串化直接存儲其值，為數(shù)字時(shí)調(diào)用庫函數(shù)將其字符化，取出時(shí)候按照其相應(yīng)種別碼采取不同的取出方式。static twoele TOKEN1000;/*詞法序列（二元式結(jié)構(gòu)）*/3.2.3 流程圖3.2.4 算法static void init_twoele(twoele*tok) /*初始化二元式，同時(shí)將變量表初始化*/int tra(c

30、har*cmp) /*查詢獲得單詞是否為關(guān)鍵字，是則返回關(guān)鍵字序號*/void addvar(char*cmp) /*加入變量表*/void prep(char ch) /*預(yù)處理，過濾注釋*/static void scanner() /*詞法掃描*/ 在詞法分析之前有一段的注釋處理部分，其相應(yīng)方案是在遇到/符時(shí)即進(jìn)入注釋處理，而后再次遇到/符時(shí)候認(rèn)為離開注釋處理部分，但有所控制，若較長范圍內(nèi)并未再遇到/符則跳出自動(dòng)機(jī)，認(rèn)為/符號就是一個(gè)單純的界符，由于c語言中并沒有/所用的語言，如果此時(shí)并不在字符串中，可直接進(jìn)行報(bào)錯(cuò)處理。以下就詞法分析遇到的單詞處理方法進(jìn)行分情況解釋：字符：首先是用if判

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

32、其裝入字符數(shù)組，否則跳出循環(huán)。剩下的就同識別字符一樣，若識別不到”，就輸出error。然后查找token和壓隊(duì)列的操作。標(biāo)識符：由于關(guān)鍵字也是一些字符串，所以一般放在一起來判斷，若不是關(guān)鍵字則為標(biāo)識符。由于關(guān)鍵字和標(biāo)識符都必須是以字母開頭，所以用if為字符來判斷，為真接著判斷，while循環(huán)來識別完整個(gè)標(biāo)識符或關(guān)鍵字的部分與識別字符串相同，也是裝入字符數(shù)組，但比字符串部分多出一點(diǎn)就是標(biāo)識符可以有下劃線，所以中間判斷條件會變成數(shù)字字符下劃線均可。While循環(huán)結(jié)束后需要在字符數(shù)組的最后一位后加上0。識別完畢后就需要判斷該字符串到底是標(biāo)識符還是關(guān)鍵字了，關(guān)鍵字個(gè)數(shù)是固定的，挨個(gè)匹配就可以了，界符：

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

34、部分，小數(shù)部分從數(shù)組轉(zhuǎn)變?yōu)樾?shù)的程序就是將上述的函數(shù)中的乘便為除，然后再識別符號后面的數(shù)，轉(zhuǎn)化為整數(shù)，將之前識別出來的數(shù)除或乘該整數(shù)次數(shù)的10，而后用數(shù)字轉(zhuǎn)字符串函數(shù)存入二元式中，二元式種類寫一個(gè)常數(shù)種別碼。3.2.5 運(yùn)行截圖3.3 語法分析器模塊（負(fù)責(zé)人：宋世波）3.3.1 功能1.獲取產(chǎn)生式2.自動(dòng)求first和follow集合3.構(gòu)建分析表4.構(gòu)建分析棧5.通過查分析表進(jìn)行語法分析6.輸出動(dòng)作序列LL1文法解釋：LL(1)分析法是指從左到右掃描、最左推導(dǎo)(LL)和只查看一個(gè)當(dāng)前符號（括號中的 1）之意； LL(1)分析法又稱預(yù)測分析法，與遞歸子程序法同屬于自頂向下確定性語法分析方法;

35、LL(1) 分析法的基本要點(diǎn)有三：1 利用一個(gè)分析表，登記如何選擇產(chǎn)生式的知識；2 利用一個(gè)分析棧，記錄分析過程；3 此分析法要求文法必須是 LL(1)文法。語法分析是編譯中的第二階段，它的任務(wù)是識別和處理比單詞更大的語法單位，判斷源程序在結(jié)構(gòu)上是否正確。從形式上來說，語法分析是對一個(gè)給定的字符串，判斷它是否為文法的一個(gè)句子。在我設(shè)計(jì)的語法分析器中，直接采用LL(1)分析方法。當(dāng)然由于本身文法為上下文無關(guān)文法，所以純LL1并沒有使用問題，此外，對于錯(cuò)誤的識別，該語法分析器可以輸出錯(cuò)誤信息。3.3.2 數(shù)據(jù)結(jié)構(gòu)struct pronode /*產(chǎn)生式節(jié)點(diǎn)*/type it;char symbol

36、15;struct product /*產(chǎn)生式數(shù)據(jù)結(jié)構(gòu)*/char vn15;pronode itself10;product c100;產(chǎn)生式是從文件中讀入的，也就是本語言的文法結(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è)元素，左部元素長度不超過十五。對于文法中的終結(jié)符和非終結(jié)符，在遞歸子程序方法中非終結(jié)符直接轉(zhuǎn)換為字符串，終結(jié)符則是對應(yīng)的Token，但當(dāng)調(diào)用LL(1)子程序時(shí)，需要將非終結(jié)符和終結(jié)符都轉(zhuǎn)換為string類型，這樣做的好處是統(tǒng)一格式之后便于進(jìn)行壓棧彈棧等操作，但

37、是會提高算法的時(shí)間復(fù)雜度，屬于以時(shí)間換空間，用簡單的數(shù)據(jù)類型便于提高程序的可讀性。typedef struct Node/*棧中元素節(jié)點(diǎn)*/char element15;struct Node *pNext;NODE, *PNODE;typedef struct Stack/*堆棧，包含棧頂和棧底*/PNODE pTop;PNODE pBottom;STACK, *PSTACK; 這就是一個(gè)正常的堆棧格式，唯一需要注意的是因?yàn)橐c產(chǎn)生式進(jìn)行入棧出棧，所以元素是用字符串存儲。3.3.3 流程圖3.3.4 算法bool traverse(char tra10015, char cmp15) /*遍

38、歷終結(jié)符和非終結(jié)符表，查看是否存在要加入元素*/int tableprep(char tra10015, char cmp15) /*準(zhǔn)備填表*/void inittable() /*分析表的初始化*/void nor(int cmp) /*填表*/void cyclefirst(int i) /*查first集合*/void first(int x1,int i,int local) /*求first集合*/void follow(int i,int x1,int local) /*求follow集合*/void initproduct() /*初始化產(chǎn)生式結(jié)構(gòu)*/void getselec

39、t(int n) /*判斷為求first或follow集合*/void tableend() /*完成分析表*/char* pop(PSTACK out) /*獲取棧頂元素用于比較*/void inistack(PSTACK begin) /*初始化分析棧*/void analysis(int m,int n, PSTACK out) /*分析棧進(jìn)行匹配，按分析表進(jìn)行*/void gra(PSTACK begin) /*語法分析主體程序*/void before() /*在開始運(yùn)行前對所用文件進(jìn)行清空重建*/ 由于分析函數(shù)部分過多，不采取完整講述，可以簡單進(jìn)行理解為由于需要遍歷整張產(chǎn)生式表，所

40、以很容易知道first和follow函數(shù)（即求first集和follow集函數(shù)）采取的函數(shù)自遞歸，當(dāng)從其產(chǎn)生元式子出發(fā)后就必須遍歷完整個(gè)產(chǎn)生式表得出結(jié)果，同時(shí)與此傳遞一個(gè)產(chǎn)生式序號用于填表。 Getselect是一個(gè)區(qū)分函數(shù)，用于區(qū)分該產(chǎn)生式是否能推出空而決定是采用求first或求follow，其中求follow函數(shù)部分允許調(diào)用求first集合，這也是LL1文法的實(shí)際求法模擬。 Tableend則是根據(jù)上述操作獲取的數(shù)字逐個(gè)的、順序的形成屬于該文法的分析表，并作為一個(gè)全局變量二維數(shù)組存儲，留存用于馬上的語法分析。LL(1)分析法是指從左到右掃描，最左推導(dǎo)和只查看一個(gè)當(dāng)前符號的意思。它屬于自頂向

41、下確定性語法分析方法。LL(1)分析方法有以下三個(gè)基本要點(diǎn)： 利用一個(gè)分析表，登記如何選擇產(chǎn)生式的知識； 利用一個(gè)分析棧，記錄分析過程； 此分析法要求文法必須是 LL(1)文法。在分析的過程中，我們將以下變換后的LL(1)文法歸為LL(1)分析方法的范疇，并且求出了它們對應(yīng)的select集合(由于非終結(jié)符和終結(jié)符過多，無法在文檔中完全描述出分析表，因此在此僅列出select集合，LL(1)分析表只需根據(jù)集合填寫即可)：以下為完整的分析表：vn/vtid()intfuncdef000001type000002factor870000exp12120000divi13130000faccycle0

42、016000item0019000parastate200210020state23000022init0025000rvalue26260000stateclo0028000funcblock29000029staclo310003130statement32000032funcbloclo33000390opera4000000callstate0420000paralist4300000paraclo0045000para4600000whilecycle000000logicexp50500000logicopera000000condistate000000nor58000580fu

43、ncend000000coutstate000000cinstate000000do0006200we63000630ie64000640vn/vtfloatcharvoidstrnumberchfuncdef111100type345600factor0000910exp00001212divi00001313faccycle000000item000000parastate2020202000state2222222200init000000rvalue00002626stateclo000000funcblock2929292900staclo3030303000statement323

44、2323200funcbloclo000000opera000000callstate000000paralist0000430paraclo000000para0000470whilecycle000000logicexp00005050logicopera000000condistate000000nor000000funcend000000coutstate000000cinstate000000do000000we000000ie000000vn/vtstring*/+-=funcdef000000type000000factor1100000exp1200000divi1300000

45、faccycle0141516160item00017180parastate000000state000000init0000024rvalue2600000stateclo000000funcblock000000staclo000000statement000000funcbloclo000000opera000000callstate0000041paralist4300000paraclo000000para4800000whilecycle000000logicexp5000000logicopera000000condistate000000nor000000funcend000

46、000coutstate000000cinstate000000do000000we000000ie000000vn/vt,;while><=funcdef000000type000000factor000000exp000000divi000000faccycle16160161616item19190191919parastate000000state000000init25250000rvalue000000stateclo2700000funcblock000000staclo0031000statement000000funcbloclo0034000opera00000

47、0callstate000000paralist000000paraclo4400000para000000whilecycle0049000logicexp000000logicopera000515253condistate000000nor0058000funcend000000coutstate000000cinstate000000do000000we0063000ie0064000>=<=ifelsereturncoutcin0000000000000000000000000000000000016160000019190000000000000000000000000

48、00000000000000000000000031031313100000000035036373800000000000000000000000000000000000000000000000005455000000056000000585758585800005900000006000000006100000000063063636300640646464每個(gè)產(chǎn)生式大括號中的內(nèi)容便是該產(chǎn)生式的select集合。可以看出同一產(chǎn)生式select集合不相交即為LL(1)文法。根據(jù)上述集合即可構(gòu)造出LL(1)分析表，由于產(chǎn)生式數(shù)目較多， LL(1)分析器主要由LL(1)分析表和LL(1)控制程序

49、兩部分構(gòu)成：LL(1)分析表是存儲文法select集合的知識表，可通過預(yù)先設(shè)置的語法棧的棧頂符和當(dāng)前掃描的單詞來確定產(chǎn)生式的序號，從而進(jìn)行下一步判斷或者壓棧操作。其后的語法分析主函數(shù)便是根據(jù)上述所寫的分析表，獲取要分析單詞，與堆棧區(qū)棧頂然后進(jìn)入分析表，按照分析表所寫進(jìn)行入棧出棧，完成分析即認(rèn)為語法無錯(cuò)誤，否則則認(rèn)為有錯(cuò)誤，發(fā)現(xiàn)情況無法對應(yīng)分析表時(shí)也認(rèn)為是發(fā)生了錯(cuò)誤。3.3.5 運(yùn)行截圖可以直觀地看出LL(1)的分析過程，可以看出對于一個(gè)稍微簡單的文法，LL(1)分析過程需要多步才能判斷完全。至此，LL(1)分析方法設(shè)計(jì)完成。3.4符號表生成模塊（負(fù)責(zé)人：孫何奇）3.4.1 功能1. 構(gòu)建活動(dòng)記

50、錄表2. 構(gòu)建符號表3. 構(gòu)建函數(shù)表4. 構(gòu)建長度表5. 添加活動(dòng)記錄6. 添加變量表7. 符號表預(yù)處理8. 添加函數(shù)表9. 添加參數(shù)表10. 構(gòu)建活動(dòng)記錄與變量表（二合一） 符號表是在目標(biāo)代碼生成中不可以缺少的提供查詢服務(wù)的表，在其中記錄了程序收集，記錄于使用的源程序的語法符號的類型、特征等相關(guān)信息，信息集中反映了標(biāo)識符的語義特征屬性。在詞法分析及語法在分析過程中不斷積累和更新表中的信息，并在詞法分析到代碼生成的各階段，按各自的需要從表中獲取不同的屬性信息。在本次課設(shè)中，符號表的作用和地位是重要關(guān)鍵的。符號表是一個(gè)編譯器的核心數(shù)據(jù)結(jié)構(gòu)，它代表了標(biāo)識符的動(dòng)態(tài)語義詞典，屬于編譯中語義分析的知識庫

51、。符號表中所登記的信息在編譯的不同階段都要用到，對于一個(gè)多遍掃描的編譯程序，不同遍所用的符號表也往往各有不同，因?yàn)槊勘樗P(guān)心的信息各有差異。符號表的組織方式也決定了未來處理符號表內(nèi)容時(shí)的效率。我所設(shè)計(jì)的符號表生成器能夠在定義標(biāo)識符時(shí)把對應(yīng)的語義信息填入符號表中；當(dāng)在語句中使用該標(biāo)識符時(shí)，通過查找相應(yīng)的表項(xiàng)來判斷該標(biāo)識符是否存在且使用正確。符號表常見的功能有定義和重定義檢查、類型匹配校驗(yàn)、數(shù)據(jù)的越界和溢出檢查、值單元存儲分配信息和函數(shù)的參數(shù)傳遞與校驗(yàn)。由于時(shí)間有限，我設(shè)計(jì)的符號表系統(tǒng)只完成了上述功能中的一部分。 3.4.2 數(shù)據(jù)結(jié)構(gòu)在編譯程序中，符號表項(xiàng)的組織傳統(tǒng)上采用三種構(gòu)造方法：線性組織排列

52、組織及二分法散列組織線性表按符號掃描的順序有序填入，但在查詢時(shí)效率較低；排列表按首字符大小來填寫符號表，查詢效率較高，但填寫時(shí)實(shí)現(xiàn)較復(fù)雜。因此，散列表可以通過一定的散列函數(shù)來實(shí)現(xiàn)符號表的高效填寫和查詢。至此，我們可以寫出符號表總體的數(shù)據(jù)結(jié)構(gòu)：char variate1615 = ;/*變量表*/enum TYPin,real,ch,b,default1;/*類型，包括int，float,char,bool型*/enum CATf,con,t,d,v,vn,vf,default2;/*種類，包括f函數(shù)，c常量，t類型，d域名，v變量，vn換名形參，vf，賦值形參*/enum ADDRPFINFL

53、,LENL,VALL,default3;/*地址表，包括函數(shù)表，活動(dòng)記錄表*/int idlocate16;/*記錄標(biāo)識符在代碼中首次出現(xiàn)的位置*/struct symbol /*符號表*/char name15;TYP type;CAT kind;ADDR addr;struct pfinfl /*函數(shù)表*/int level;int off;int fn;symbol para5;/*參數(shù)表*/int entry;struct vall /*活動(dòng)記錄表，采用鏈表結(jié)構(gòu)*/char name15;char name115;int low;int up;struct vall *next;vall *firstnode=new vall;struct lenl /*長度表*/char name10;int length;lenl lengt10;符號表是標(biāo)識符的動(dòng)態(tài)語義詞典，屬于編譯中語義分析的知識庫；主要內(nèi)容： 名字 標(biāo)識符源碼，用作查詢關(guān)鍵字； 類型 - 該標(biāo)識符的數(shù)據(jù)類型及其相關(guān)信息； 種類 - 該標(biāo)識符在源程序中的語義