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

1、<p>　　2011-2012學(xué)年第二學(xué)期</p><p>　　《編譯原理》課程設(shè)計(jì)報(bào)告</p><p>　　學(xué) 院： 計(jì)算機(jī)科學(xué)與工程學(xué)院 </p><p>　　班 級(jí)： 10803070115 </p><p>　　學(xué)生姓名： 羅代鵬

2、 學(xué)號(hào)： 10703070115 </p><p>　　成 績(jī)： </p><p>　　指導(dǎo)教師： 王柯柯 </p><p>　　時(shí)間： 2012年 5 月</p><p><b>　　1　緒

3、論3</b></p><p>　　2　課程設(shè)計(jì)的目的3</p><p>　　3　課程設(shè)計(jì)的內(nèi)容及要求3</p><p><b>　　4　開(kāi)發(fā)工具4</b></p><p>　　5　問(wèn)題分析及相關(guān)原理介紹4</p><p>　　5.1編譯系統(tǒng)原理介紹4</p>

4、<p>　　5.2　預(yù)測(cè)分析算法4</p><p>　　6　設(shè)計(jì)思路及關(guān)鍵問(wèn)題的解決方法5</p><p>　　6.1　編譯系統(tǒng)5</p><p>　　6.2　預(yù)測(cè)分析算法6</p><p>　　7分析結(jié)果及測(cè)試分析7</p><p>　　7.1 語(yǔ)義分析結(jié)果及測(cè)試分析7</p>&

5、lt;p>　　7.2 預(yù)測(cè)分析結(jié)果及測(cè)試分析9</p><p>　　8 總結(jié)及心得體會(huì)11</p><p><b>　　9 參考文獻(xiàn)11</b></p><p><b>　　1　緒論</b></p><p>　　隨著計(jì)算機(jī)科學(xué)的飛速發(fā)展，形式語(yǔ)言與自動(dòng)機(jī)理論和方法的研究也越來(lái)越受到人們的

6、重視，但前者已經(jīng)成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。本課程設(shè)計(jì)主要研究自動(dòng)機(jī)在編譯方面的應(yīng)用，并將討論重點(diǎn)放在算符優(yōu)先分析法上，并用此理論完成算數(shù)表達(dá)式的正確與否的判斷。</p><p>　　根據(jù)算符優(yōu)先分析算法，編寫(xiě)一個(gè)語(yǔ)法程序，程序具有通用性，即編制的語(yǔ)法縫隙程序能夠適用于不同文法以及各種輸入的單詞串?；舅枷朊枋觯Z(yǔ)法分析前首先要對(duì)句子進(jìn)行詞法分析，去除多余的自負(fù)，為語(yǔ)法分析做前期準(zhǔn)備。算符優(yōu)先分析算法的核心算法教材

7、上已給出，因此所要做的事只是將其變成實(shí)現(xiàn)。</p><p><b>　　2　課程設(shè)計(jì)的目的</b></p><p>　　通過(guò)課程設(shè)計(jì)進(jìn)一步理解高級(jí)語(yǔ)言在計(jì)算機(jī)中的執(zhí)行過(guò)程，加深對(duì)編譯原理中重點(diǎn)算法和編譯技術(shù)的理解，提高自己的編程能力，培養(yǎng)好的程序設(shè)計(jì)風(fēng)格。同時(shí)通過(guò)某種可視化編程語(yǔ)言的應(yīng)用，具備初步的Windows環(huán)境下的編程思想。</p><p&g

8、t;　　3　課程設(shè)計(jì)的內(nèi)容及要求</p><p>　　語(yǔ)義分析設(shè)計(jì)：利用eclipse可視化編程工具編寫(xiě)JAVA語(yǔ)言的可視化編譯平臺(tái)，包括源文件編輯器、詞法分析、語(yǔ)法分析與中間代碼生成，要求具四元式表、錯(cuò)誤信息等功能?！?lt;/p><p>　　預(yù)測(cè)分析的設(shè)計(jì)：利用eclipse可視化編程工具實(shí)現(xiàn)預(yù)測(cè)分析算法模擬</p><p>　　課程設(shè)計(jì)要求：功能相對(duì)完善，有輸入

9、、輸出描述，有測(cè)試數(shù)據(jù)，并介紹不足。</p><p><b>　　4　開(kāi)發(fā)工具</b></p><p>　　JAVA可視化編程工具:Eclipse</p><p>　　5　問(wèn)題分析及相關(guān)原理介紹</p><p>　　5.1編譯系統(tǒng)原理介紹</p><p><b>　?。?）編譯程序介紹&

10、lt;/b></p><p>　　編譯過(guò)程采用一趟掃描的方式，以語(yǔ)法分析程序?yàn)楹诵模~法分析程序和代碼生成程序都作為一個(gè)獨(dú)立的過(guò)程，當(dāng)語(yǔ)法分析需要讀單詞就調(diào)用詞法分析程序，而當(dāng)語(yǔ)法分析正確需生成相應(yīng)的目標(biāo)代碼時(shí)，則調(diào)用代碼生成程序。</p><p>　?。?）對(duì)所寫(xiě)編譯程序的源語(yǔ)言的描述</p><p>　　while(x<3){ y=y+2; };&l

11、t;/p><p><b>　　a=m[0]+4;</b></p><p>　　y=y*2-3*3;</p><p>　　if(x<0){ y=xxx+2; y=y*2-3*3; } else { y=3; };</p><p>　　如以上示例，是對(duì)C語(yǔ)言的分析</p><p>　?。?）各部分的

12、功能介紹及分析</p><p>　　詞法分析功能：語(yǔ)法分析從讀入第一個(gè)單詞開(kāi)始，由非終結(jié)符<程序>（即開(kāi)始符）出發(fā)，沿語(yǔ)法描述圖箭頭所指出的方向進(jìn)行分析。</p><p>　　語(yǔ)義分析功能：對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫(xiě)出相應(yīng)語(yǔ)法分析子程序。</p><p>　　5.2　預(yù)測(cè)分析算法</p><p><b>　?。?）算

13、法思想介紹</b></p><p>　　本課程設(shè)計(jì)的題目為預(yù)測(cè)分析算法模擬，它是算符優(yōu)先分析算法中判斷三種優(yōu)先關(guān)系的關(guān)鍵。算符優(yōu)先分析算法是自底向上分析方法的一種。所謂自底向上分析，也稱(chēng)移近——規(guī)約分析</p><p>　?。?）算法功能及分析</p><p>　　預(yù)測(cè)分析功能：對(duì)表達(dá)式進(jìn)行分析，結(jié)合預(yù)測(cè)分析表進(jìn)行一步一步的分析，</p>

14、<p>　　6　設(shè)計(jì)思路及關(guān)鍵問(wèn)題的解決方法</p><p><b>　　6.1　編譯系統(tǒng)</b></p><p><b>　?。?）設(shè)計(jì)思路</b></p><p>　　遞歸子程序法：對(duì)應(yīng)每個(gè)非終結(jié)符語(yǔ)法單元，編一個(gè)獨(dú)立的處理過(guò)程（或子程序）。語(yǔ)法分析從讀入第一個(gè)單詞開(kāi)始，由非終結(jié)符<程序>（即開(kāi)始

15、符）出發(fā)，沿語(yǔ)法描述圖箭頭所指出的方向進(jìn)行分析。當(dāng)遇到非終結(jié)符時(shí)，則調(diào)用相應(yīng)的處理過(guò)程，也就進(jìn)入了一個(gè)語(yǔ)法單元，再沿當(dāng)前所進(jìn)入的語(yǔ)法單元所指箭頭方向繼續(xù)進(jìn)行分析。當(dāng)遇到描述圖中是終結(jié)符時(shí)，則判斷當(dāng)前讀入的單詞是否與圖中的終結(jié)符相匹配，若匹配，再讀取下一個(gè)單詞繼續(xù)分析。遇到分支點(diǎn)時(shí)，將當(dāng)前的單詞與分支點(diǎn)上多個(gè)終結(jié)符逐個(gè)相比較，若都不匹配時(shí)可能是進(jìn)入下一個(gè)非終結(jié)符語(yǔ)法單位或是出錯(cuò)。 </p><p>　?。?）詞法分

16、析及其解決方法</p><p>　　詞法分析程序的主要任務(wù)是對(duì)構(gòu)成源程序的字符串從左到右的掃描，逐個(gè)字符地讀入源程序字符并按照構(gòu)詞規(guī)則切分成一個(gè)一個(gè)具有獨(dú)立意義的單詞。并確定其屬性（如保留字、標(biāo)識(shí)符、運(yùn)算符、界限符和常量等）。再把它們轉(zhuǎn)換成長(zhǎng)度統(tǒng)一的標(biāo)準(zhǔn)形式—屬性字。</p><p>　　詞法分析是編譯過(guò)程中的第一個(gè)階段，在語(yǔ)法分析前進(jìn)行 。也可以和語(yǔ)法分析結(jié)合在一起作為一遍，由語(yǔ)法分析程

17、序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。</p><p>　　單詞的分類(lèi)（五類(lèi)）：</p><p>　　1. 關(guān)鍵字：由程序語(yǔ)言定義的具有固定意義的標(biāo)識(shí)符。也稱(chēng)為保留字或基本字。</p><p>　　2. 標(biāo)識(shí)符：用來(lái)表示程序中各種名字的字符串。</p><p>　　3. 常 數(shù)：常數(shù)的類(lèi)型一般有整型、實(shí)型、布爾型、文字型。&l

18、t;/p><p>　　4. 運(yùn)算符：如+、－ 、*、/ 等。</p><p>　　5. 界限符：如逗號(hào)、分號(hào)、括號(hào)等。</p><p>　　詞法分析的有效字符串為: IF,ELSE,THEN, <,>,.<=,>=,=，和從a到z的單個(gè)標(biāo)識(shí)符，但是程序還是相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，復(fù)雜的表達(dá)式可能不能處理，以后會(huì)改進(jìn)。而詞法分析的結(jié)果就是將相應(yīng)的單詞賦予

19、不同的屬性值，利用詞法分析表將結(jié)果保存起來(lái)，為后面的語(yǔ)義分析做準(zhǔn)備。詞法分析完成之后就是把詞法分析的結(jié)果都顯示出來(lái)。</p><p>　?。?）語(yǔ)義分析及其解決方法</p><p>　　在程序語(yǔ)言的語(yǔ)法定義中有許多采用遞歸定義。我們?cè)趯?duì)它進(jìn)行語(yǔ)法分析時(shí)，編制的處理程序也采取遞歸的方式，可使其結(jié)構(gòu)簡(jiǎn)單易讀。但由于頻繁地調(diào)用子程序大大地降低了分析速度。</p><p>

20、　　遞歸下降法的主要思想是：對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫(xiě)出相應(yīng)語(yǔ)法分析子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱(chēng)此種方法稱(chēng)為遞歸子程序法或遞歸下降法。</p><p>　　6.2　預(yù)測(cè)分析算法</p><p><b>　?。?）設(shè)計(jì)思路</b></p><p>　　它的實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左向右進(jìn)行掃描

21、，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出的棧中，邊移進(jìn)邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄或可規(guī)約串，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱(chēng)為一部規(guī)約。重復(fù)這一過(guò)程直到規(guī)約到棧中只剩文法的開(kāi)始符號(hào)則為分析成功，也就確認(rèn)輸入串是該文法的句子。而算符優(yōu)先分析算法的基本思想只是規(guī)定算符之間的優(yōu)先關(guān)系，也就是只考慮終結(jié)符之間的優(yōu)先關(guān)系。</p><p>　　（2）預(yù)測(cè)分析及其解決方法</p>

22、<p><b>　　文法G[E]:</b></p><p><b>　　E->TE’</b></p><p>　　E’->+TE’|ε</p><p><b>　　T->FT’</b></p><p>　　T’->*FT’|ε</p>

23、;<p><b>　　F->(E)|i</b></p><p>　　本課程設(shè)計(jì)主要采用棧的數(shù)據(jù)結(jié)構(gòu)，定義一個(gè)棧的類(lèi)，類(lèi)中主要成員函數(shù)實(shí)現(xiàn)棧的一些基本操作，如：push（）為入棧操作，pop（）為出棧操作，empty（）判斷棧中是否為空，clear（）用于對(duì)棧進(jìn)行清空處理。</p><p>　　7分析結(jié)果及測(cè)試分析</p><p&

24、gt;　　7.1 語(yǔ)義分析結(jié)果及測(cè)試分析</p><p>　　1、軟件運(yùn)行環(huán)境及限制</p><p>　　環(huán)境：eclipse</p><p><b>　　2、測(cè)試數(shù)據(jù)說(shuō)明</b></p><p><b>　　語(yǔ)義分析數(shù)據(jù)：</b></p><p>　　while(x<

25、3){ y=y+2; };</p><p><b>　　a=m[0]+4;</b></p><p>　　y=y*2-3*3;</p><p>　　if(x<0){ y=xxx+2; y=y*2-3*3; } else { y=3; };</p><p>　　3、運(yùn)行結(jié)果及功能說(shuō)明</p><p&

26、gt;<b>　　pro1:</b></p><p>　　=xnulltemp1</p><p>　　= 3nulltemp2</p><p>　　<temp1temp2temp3</p><p>　　Jumpnullpro2temp3</p><p>　　=yn

27、ulltemp4</p><p>　　= 2nulltemp5</p><p>　　+temp4temp5temp6</p><p>　　=temp6nully</p><p>　　Jumppro1nulltrue</p><p><b>　　pro2:</b></

28、p><p>　　= 0nulltemp7</p><p>　　= 4nulltemp8</p><p>　　+m[temp7]temp8temp9</p><p>　　=temp9nulla</p><p>　　=ynulltemp10</p><p>　　= 2n

29、ulltemp11</p><p>　　*temp10temp11temp12</p><p>　　= 3nulltemp13</p><p>　　= 3nulltemp14</p><p>　　*temp13temp14temp15</p><p>　　-temp12temp15tem

30、p16</p><p>　　=temp16nully</p><p>　　=xnulltemp17</p><p>　　= 0nulltemp18</p><p>　　<temp17temp18temp19</p><p>　　Jumppro3pro4temp19</p>

31、<p><b>　　pro3:</b></p><p>　　=xxxnulltemp20</p><p>　　= 2nulltemp21</p><p>　　+temp20temp21temp22</p><p>　　=temp22nully</p><p>

32、　　=ynulltemp23</p><p>　　= 2nulltemp24</p><p>　　*temp23temp24temp25</p><p>　　= 3nulltemp26</p><p>　　= 3nulltemp27</p><p>　　*temp26temp27te

33、mp28</p><p>　　-temp25temp28temp29</p><p>　　=temp29nully</p><p>　　Jumppro5nulltrue</p><p><b>　　pro4:</b></p><p>　　= 3nulltemp30</

34、p><p>　　=temp30nully</p><p><b>　　pro5:</b></p><p><b>　　4、測(cè)試及分析說(shuō)明</b></p><p>　　能對(duì)表達(dá)式，if-else，while進(jìn)行分析及輸出四元式</p><p>　　7.2 預(yù)測(cè)分析結(jié)果及測(cè)試分

35、析</p><p>　　1、軟件運(yùn)行環(huán)境及限制</p><p>　　環(huán)境：eclipse</p><p><b>　　2、測(cè)試數(shù)據(jù)說(shuō)明</b></p><p>　　id*(id+id)</p><p>　　3、運(yùn)行結(jié)果及功能說(shuō)明</p><p><b>　　4、測(cè)

36、試及分析說(shuō)明</b></p><p>　　能對(duì)表達(dá)式進(jìn)行預(yù)測(cè)分析</p><p><b>　　8 總結(jié)及心得體會(huì)</b></p><p>　　經(jīng)過(guò)一個(gè)多月的不斷修改和完善我們總算完成了編譯原理課程的實(shí)驗(yàn)設(shè)計(jì)。此次實(shí)驗(yàn)可以說(shuō)是我自從進(jìn)入大學(xué)計(jì)算機(jī)系以來(lái)所接手的工作量最大，設(shè)計(jì)最復(fù)雜，代碼量最大，涉及數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)最多的一次實(shí)驗(yàn)。通

37、過(guò)這次的實(shí)驗(yàn)雖然離目標(biāo)還差著相當(dāng)?shù)倪h(yuǎn)，但終于使我明白了其實(shí)設(shè)計(jì)想象中這樣一個(gè)優(yōu)秀的編譯器不是這么簡(jiǎn)單的，它需要成千上萬(wàn)的優(yōu)秀程序員的智慧和汗水。</p><p>　　我在這次設(shè)計(jì)后深深的感受到“一分耕耘，一分收獲”。設(shè)計(jì)的過(guò)程是辛苦的，但當(dāng)設(shè)計(jì)完成時(shí)會(huì)有一種滿(mǎn)足感，而且自己也收獲不少。通過(guò)這次設(shè)計(jì)，我發(fā)覺(jué)我學(xué)到了很多東西，把學(xué)到的東西都派上了用場(chǎng)。在我的設(shè)計(jì)中體現(xiàn)了這幾年來(lái)大學(xué)的學(xué)習(xí)和生活的價(jià)值。作為一名計(jì)算機(jī)專(zhuān)

38、業(yè)的學(xué)生，我的目標(biāo)不僅僅是程序員。而這一次設(shè)計(jì)就是我向自己的目標(biāo)邁出的第一步。剛開(kāi)始我們從編譯器組成的各個(gè)模塊入手，我們發(fā)現(xiàn)每個(gè)模塊之間的聯(lián)系都異常的緊密，從詞法分析，語(yǔ)法分析等再到最終的解釋程序等等。整個(gè)編譯器就是一個(gè)工程而模塊設(shè)計(jì)的好壞直接關(guān)系到了這個(gè)工程的質(zhì)量。</p><p>　　首先我加深了對(duì)語(yǔ)法分析，語(yǔ)義分析的認(rèn)識(shí)及理解，通過(guò)一個(gè)完整的項(xiàng)目把自己學(xué)習(xí)的東西融合到一起。我重新復(fù)習(xí)了預(yù)測(cè)分析方法，其中重點(diǎn)

39、復(fù)習(xí)了算符優(yōu)先分析算法，對(duì)詞法、文法的判斷有了較深刻的認(rèn)識(shí)，對(duì)其中數(shù)據(jù)的流向和數(shù)據(jù)的輸出操作有了很清晰的認(rèn)識(shí)，對(duì)數(shù)據(jù)在該課程設(shè)計(jì)中的存儲(chǔ)和運(yùn)算有了深刻的理解。</p><p><b>　　9 參考文獻(xiàn)</b></p><p>　?。?］胡元義等．編譯原理實(shí)踐教程．西安電子科技大學(xué)出版社．2002年1月</p><p>　　［2］王雷等．編譯原理