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

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

2、 學號： 10703070115 </p><p>　　成 績： </p><p>　　指導教師： 王柯柯 </p><p>　　時間： 2012年 5 月</p><p><b>　　1　緒

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

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

5、lt;p>　　7.2 預測分析結(jié)果及測試分析9</p><p>　　8 總結(jié)及心得體會11</p><p><b>　　9 參考文獻11</b></p><p><b>　　1　緒論</b></p><p>　　隨著計算機科學的飛速發(fā)展，形式語言與自動機理論和方法的研究也越來越受到人們的

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

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

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

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

10、lt;/b></p><p>　　編譯過程采用一趟掃描的方式，以語法分析程序為核心，詞法分析程序和代碼生成程序都作為一個獨立的過程，當語法分析需要讀單詞就調(diào)用詞法分析程序，而當語法分析正確需生成相應(yīng)的目標代碼時，則調(diào)用代碼生成程序。</p><p>　　（2）對所寫編譯程序的源語言的描述</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>　　如以上示例，是對C語言的分析</p><p>　?。?）各部分的

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

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

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

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

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

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

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

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

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

21、，并將輸入符逐個移入一個后進先出的棧中，邊移進邊分析，一旦棧頂符號串形成某個句型的句柄或可規(guī)約串，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串，這稱為一部規(guī)約。重復這一過程直到規(guī)約到棧中只剩文法的開始符號則為分析成功，也就確認輸入串是該文法的句子。而算符優(yōu)先分析算法的基本思想只是規(guī)定算符之間的優(yōu)先關(guān)系，也就是只考慮終結(jié)符之間的優(yōu)先關(guān)系。</p><p>　　（2）預測分析及其解決方法</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è)計主要采用棧的數(shù)據(jù)結(jié)構(gòu)，定義一個棧的類，類中主要成員函數(shù)實現(xiàn)棧的一些基本操作，如：push（）為入棧操作，pop（）為出棧操作，empty（）判斷棧中是否為空，clear（）用于對棧進行清空處理。</p><p>　　7分析結(jié)果及測試分析</p><p&

24、gt;　　7.1 語義分析結(jié)果及測試分析</p><p>　　1、軟件運行環(huán)境及限制</p><p>　　環(huán)境：eclipse</p><p><b>　　2、測試數(shù)據(jù)說明</b></p><p><b>　　語義分析數(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、運行結(jié)果及功能說明</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、測試及分析說明</b></p><p>　　能對表達式，if-else，while進行分析及輸出四元式</p><p>　　7.2 預測分析結(jié)果及測試分

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

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

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

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

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