編譯原理課程設(shè)計---s語言的編譯器的設(shè)計與實現(xiàn)

1、<p><b>　　編譯原理課程設(shè)計</b></p><p>　　S語言的編譯器的設(shè)計與實現(xiàn)</p><p>　　學(xué) 院（系）：計算機科學(xué)學(xué)院</p><p>　　學(xué) 生 姓 名： </p><p>　　學(xué) 號： </p><p

2、>　　班 級： </p><p>　　同 組 人 ： </p><p><b>　　引 言</b></p><p>　　《編譯原理》是國內(nèi)外各高等院校計算機科學(xué)技術(shù)類專業(yè)，特別是計算機軟件專業(yè)的一門重要專業(yè)課程。該課程系統(tǒng)地向?qū)W生介紹編譯程序的結(jié)構(gòu)、工作流程及編譯程序各組成

3、部分的設(shè)計原理和實現(xiàn)技術(shù)。由于該課程理論性和實踐性都比較強，內(nèi)容較為抽象復(fù)雜，涉及到大量的軟件設(shè)計算法，因此，一直是一門比較難學(xué)的課程。為了使學(xué)生更好地理解和掌握編譯技術(shù)的基本概念、基本原理和實現(xiàn)方法，實踐環(huán)節(jié)非常重要，只有通過上機進行程序設(shè)計，才能使學(xué)生對比較抽象的教學(xué)內(nèi)容產(chǎn)生具體的感性認識，增強學(xué)生綜合分析問題、解決問題的能力，并對提高學(xué)生軟件設(shè)計水平大有益處。</p><p>　　編譯原理涉及詞法分析，語法

4、分析，語義分析及優(yōu)化設(shè)計等各方面。詞法分析階段是編譯過程的第一個階段，是編譯的基礎(chǔ)。這個階段的任務(wù)是從左到右一個字符一個字符地讀入源程序，即對構(gòu)成源程序的字符流進行掃描然后根據(jù)構(gòu)詞規(guī)則識別單詞(也稱單詞符號或符號)。詞法分析程序?qū)崿F(xiàn)這個任務(wù)。語法分析是對所需要的語言進行分析，根據(jù)不同的分析方法采用不同的程序結(jié)構(gòu)，本編譯器采用LL（1）文法的預(yù)測分析法進行語法分析，用遞歸下降子程序法實現(xiàn)最為簡單。</p><p>

5、<b>　　正 文</b></p><p><b>　　1 需求分析</b></p><p><b>　　1.1 功能需求</b></p><p>　　根據(jù)課程設(shè)計要求可知，程序需要實現(xiàn)的有詞法分析，語法分析，語義分析目標代碼生成，四大部分子程序，其中語法分析部分因為采用遞歸下降子程序法，所以將語

6、義分析嵌入到語法分析部分實現(xiàn)。</p><p>　　所以，本程序需要三部分：詞法分析，語法分析，語法制導(dǎo)翻譯程序段。</p><p><b>　　1.2 性能需求</b></p><p>　　響應(yīng)時間盡量短，分析的程序段無需過大，最大共300字符就行。</p><p><b>　　1.3 可靠性</b&g

7、t;</p><p>　　出現(xiàn)輸出錯誤的次數(shù)不可超過總試驗次數(shù)的5%。</p><p><b>　　2 概要設(shè)計</b></p><p><b>　　2.1 詞法分析器</b></p><p>　　本編譯器使用數(shù)組進行處理，詞法分析部分對輸入的單詞進行讀入后錄入數(shù)組中形成有序列，后便可輸出二元式序列

8、，而數(shù)組操作十分的方便簡單，易于理解。</p><p>　　自動機是單詞識別的重要步驟，根據(jù)這個步驟便可以寫出詞法分析程序。詞法分析的結(jié)果放入BUFFER[maxsize][max]中，作為全局變量執(zhí)行為語法分析提供單詞序列。</p><p><b>　　2.2語法分析</b></p><p>　　詞法分析結(jié)束后得到一個單詞序列，語法分析部分使

9、用給定的文法對單詞序列進行分析，運用遞歸下降子程序法進行，所以在進行語法分析時先改造文法，使之能滿足遞歸下降的要求，即消除左遞歸和消除文法二義性。</p><p><b>　　構(gòu)造函數(shù)時：</b></p><p>　　針對每個非終極符編寫函數(shù)，根據(jù)規(guī)則候選式的結(jié)構(gòu)， 按從左到右的順序定義函數(shù)體。對于規(guī)則中的終極符，sym匹配上了規(guī)則中的一個終極符，就把下一個待匹配符讀

10、進sym中；若匹配不成功， 表明有語法錯誤，語法檢查停止。</p><p>　　對于規(guī)則右部的非終極符，就調(diào)用該非終極符所對應(yīng)的函數(shù)。</p><p><b>　　2.3語法制導(dǎo)翻譯</b></p><p>　　根據(jù)設(shè)計說明和要求的指示，語法制導(dǎo)翻譯與語法分析一同進行。</p><p>　　語法制導(dǎo)翻譯有三種：</

11、p><p><b>　　1、聲明語句的翻譯</b></p><p>　　把變量的類型和變量名插入到符號表中，并在符號表中分配地址。 </p><p>　　2、簡單賦值語句的翻譯</p><p>　　簡單賦值語句的翻譯包括語義檢查和算術(shù)表達式的翻譯，最終生成四元式代碼</p><p><b>

12、　　控制語句的翻譯</b></p><p><b>　　3詳細設(shè)計</b></p><p>　　3.1詞法分析器部分</p><p>　　在概要設(shè)計中已經(jīng)說到了，本編譯器采用數(shù)組BUFFER[MAXSIZE][MAX]對詞法分析結(jié)果進行存儲，以方便后續(xù)的程序進程。</p><p>　　本編譯器所能識別的單詞：

13、if,else,then,while,do,read,int.</p><p>　　標示符用助記符(單詞記號） ID 表示。</p><p>　　常數(shù)： 用助記符　NUM　表示。</p><p>　　算術(shù)運算符：+、- 、*、/。</p><p>　　邏輯運算符： & 、 | 。</p><p>　　關(guān)系運

14、算符：<、>、!= 、==</p><p>　?。ㄓ弥浄elop　表示。）</p><p>　　分隔符：{、}、 ；、（、 ）、：=</p><p><b>　　掃描器接口設(shè)計：</b></p><p>　　詞法分析的輸出常用二元式序列進行輸出，一列為單詞類別，一列為單詞值。</p>&l

15、t;p><b>　　3.2語法分析部分</b></p><p><b>　　所用文法為:</b></p><p><b>　　P→｛DS｝</b></p><p>　　D→Dint ID; | int ID; </p><p>　　S→if (B) then S else

16、 S | if (B) then S | while (B) do S | { L } | ID=E</p><p>　　| read ID; </p><p>　　L→S; L | S</p><p>　　B→B and B| B or B| ID relop ID | ID </p><p>　　E→E+E | E-E |E*E | E

17、 / E | (E) |ID | NUM</p><p>　　其中relop是終極符, 語法類別是關(guān)系運算符,因為不是LL（1）文法，所以需要對文法進行消除左遞歸和左公共因子，構(gòu)成LL(1)文法，改造后的文法如下：</p><p><b>　　P→｛DS｝</b></p><p>　　D→int ID;{int ID;}</p>

18、<p>　　S→if (B) then S else S | if (B) then S | while (B) do S | { L } | ID=E</p><p>　　| read ID; </p><p><b>　　L→S{;S}</b></p><p><b>　　B→O{or O}</b><

19、/p><p>　　O→A{and A}</p><p>　　A→ID relop ID |ID</p><p>　　E→T{+T|-T}</p><p>　　T→F{*F|/F}</p><p>　　F→ID|NUM|(E)</p><p>　　對應(yīng)文法的非終結(jié)符的first集和follow集<

20、;/p><p><b>　　程序流程：</b></p><p>　　每一個非終結(jié)符對應(yīng)一個函數(shù)</p><p><b>　　所以所有的函數(shù)有：</b></p><p><b>　　void P();</b></p><p><b>　　void D

21、();</b></p><p><b>　　void S();</b></p><p><b>　　void B();</b></p><p><b>　　void L();</b></p><p>　　void L1();</p><p>

22、<b>　　void B();</b></p><p>　　void T1();</p><p>　　void F1();</p><p><b>　　void E();</b></p><p><b>　　void T();</b></p><p>&

23、lt;b>　　void F();</b></p><p>　　采用遞歸下降子程序法：進入某函數(shù)前，待匹配符已經(jīng)讀進sym中， 函數(shù)結(jié)束時， 下一個待匹配符也已經(jīng)讀進sym中。對于規(guī)則中的終極符，sym匹配上了規(guī)則中的一個終極符，就把下一個待匹配符讀進sym中；若匹配不成功， 表明有語法錯誤，語法檢查停止。</p><p><b>　　3.3語義分析</b&

24、gt;</p><p>　　由于小組能力比較差，只能實現(xiàn)到聲明語句的翻譯。</p><p>　　聲明語句由于是對聲明的單詞進行存儲，將變量的類型和變量的名字插入到符號表</p><p>　　word[MAXSIZE][MAX]中，所以這一段可以嵌入到語法分析中進行。</p><p><b>　　4 編譯測試</b><

25、;/p><p><b>　　實驗用例</b></p><p>　　文件名:process1.txt</p><p><b>　　{</b></p><p><b>　　int a;</b></p><p><b>　　int b;</b>

26、;</p><p><b>　　int c;</b></p><p><b>　　c:=a+b</b></p><p><b>　　}#</b></p><p><b>　　測試結(jié)果：</b></p><p><b>　　

27、詞法：</b></p><p><b>　　詞法分析的二元式：</b></p><p>　　語法分析以及對應(yīng)的符號表：</p><p><b>　　錯誤用例</b></p><p>　　測試文檔1：文件名：process.txt</p><p>　　測試文檔不存在

28、時的輸出。</p><p>　　測試文檔2：文件名:process2.txt</p><p><b>　　輸出的二元式：</b></p><p><b>　　語法分析結(jié)果：</b></p><p><b>　　測試文檔3：</b></p><p>　　文

29、件名：process3.txt</p><p><b>　　測試結(jié)果：</b></p><p><b>　　詞法：</b></p><p><b>　　二元式：</b></p><p><b>　　語法分析：</b></p><p>

30、;　　缺少‘）’，所以報錯。</p><p><b>　　總 結(jié)</b></p><p>　　由于個人能力有限，編譯器的最終目的并未能全部實現(xiàn)，僅實現(xiàn)了部分功能，缺失的比較厲害。望老師見諒。通過本次試驗，深感自己的編程能力還是很差，寫程序的時候沒有設(shè)計文檔，沒有做總體設(shè)計和各部分的設(shè)計，一開始就寫，雖然寫的很快，但是未進行測試，越寫到后面就發(fā)現(xiàn)越難寫，出現(xiàn)了很多的b

31、ug。調(diào)試起來真的很累，定義char類型的字符串的時候定義成了char *a; 雖然也是字符串，但是只能用一次，第二次就會出現(xiàn)錯誤，多次調(diào)試都無法通過，讓我糾結(jié)了很久，都因為當初學(xué)習(xí)c語言時不用功，造成的后果是很嚴重的，幸運的是最終還是解決了。但是程序的開發(fā)周期太長了，這是我很慚愧的。在大學(xué)剩下的這段時光中，我想好好地再去學(xué)習(xí)編程的技巧，讓自己能更加充實。通過本次程序設(shè)計，使我學(xué)會了很多東西，知道了程序和內(nèi)存之間的聯(lián)系，產(chǎn)生了一個較為體

32、系的知識系統(tǒng)。也吸取了很多的經(jīng)驗教訓(xùn):1.寫程序之前要先寫好開發(fā)的需求分析，概要設(shè)計，詳細設(shè)計等等文檔，為程序開發(fā)提供參考和依靠；2.小組開發(fā)時，要分工合理，模塊化一定要強，這樣可以使開發(fā)時間大大縮短，效率大大提高；3.對于程序的測試要做一部分就要測試一部分，每做20至30行代碼就要調(diào)</p><p>　　總的來說，程序開發(fā)是一件特別讓人崩潰的事情，因為它總是出現(xiàn)各種各樣的錯誤，讓人調(diào)試起來沒完沒了，編譯器處能通

33、過，語法語義分析也都能實現(xiàn)，但是程序還是不能出現(xiàn)理想的輸出結(jié)果，讓人頭疼不已。不過，通過這次課程設(shè)計學(xué)習(xí)到的東西真的特別多，感謝趙晶老師的悉心指導(dǎo)和關(guān)注。 </p><p>　　過編譯原理課程設(shè)計這門課程，我進一步理解了編譯的原理，能通過理論聯(lián)系實踐，和組員一起寫出一個編譯器，可以進行詞法分析，語法分析和語義分析，雖然，最后我們沒有寫出生成四元式的代碼，但是，我對四元式的理解加深了。此課程設(shè)計中，

34、能否熟練運用C語言是課程設(shè)計能否順利進行的一個重要因素，因此，在今后的學(xué)習(xí)中，我要注重計算機語言的學(xué)習(xí)和運用。</p><p>　　通過本次編譯原理課程設(shè)計的學(xué)習(xí)，我認識到了自己的許多不足，同時也獲得了一些進步。自己的不足包括基礎(chǔ)知識掌握的并不扎實，編程實際操作起來也不熟練，這讓我認識到做一個編程人員，一定要有自己對知識的理解并多次熟練的操作，這樣才是一個基本合格的程序員。另外通過本次學(xué)習(xí)，我對c語

35、言，編譯原理的知識有了新的認識并復(fù)習(xí)了一些知識。最后謝謝老師的大力支持。</p><p><b>　　參 考 文 獻</b></p><p>　　[1]張素琴，呂映芝，蔣維杜，戴桂蘭等，《編譯原理（第二版）》[M]，北京：清華大學(xué)出版社，2007.</p><p>　　[2]譚浩強等，《c語言程序設(shè)計（第三版）》[M]，北京，清華大學(xué)出