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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、t;p><b>　　3.2語(yǔ)法分析部分</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是終極符, 語(yǔ)法類別是關(guān)系運(yùn)算符,因?yàn)椴皇荓L（1）文法，所以需要對(duì)文法進(jìn)行消除左遞歸和左公共因子，構(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>　　對(duì)應(yīng)文法的非終結(jié)符的first集和follow集<

20、;/p><p><b>　　程序流程：</b></p><p>　　每一個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)函數(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>　　采用遞歸下降子程序法：進(jìn)入某函數(shù)前，待匹配符已經(jīng)讀進(jìn)sym中， 函數(shù)結(jié)束時(shí)， 下一個(gè)待匹配符也已經(jīng)讀進(jìn)sym中。對(duì)于規(guī)則中的終極符，sym匹配上了規(guī)則中的一個(gè)終極符，就把下一個(gè)待匹配符讀進(jìn)sym中；若匹配不成功， 表明有語(yǔ)法錯(cuò)誤，語(yǔ)法檢查停止。</p><p><b>　　3.3語(yǔ)義分析</b&

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

25、;/p><p><b>　　實(shí)驗(yàn)用例</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>　　測(cè)試結(jié)果：</b></p><p><b>　　

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

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

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

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

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

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

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

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

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