吉林大學(xué)《編譯原理課程設(shè)計》滿分實驗報告

1、2016級編譯原理課程設(shè)計總結(jié)報告2016級編譯原理課程設(shè)計總結(jié)報告（組）_2019_年_5_月_25_日姓名性別班級學(xué)號所占比例個人成績男04%男04%男04%任務(wù)分工：（請用小四號宋體填寫）編譯系統(tǒng)的總體分析與設(shè)計-具體功能的設(shè)計與實現(xiàn)- 對應(yīng)的測試與驗證過程- 系統(tǒng)界面的設(shè)計與美工- 成績評定：詞法分析自底向上語法分析中間代碼生成自頂向下語法分析語義分析目標代碼生成團隊成績教師簽章備注填寫說明：1、請將首頁紅色部分信息填全，其中：班級為2位數(shù)字，保留首位的0；學(xué)號為8位數(shù)字，軟件學(xué)院以54開頭；所占比例為百分數(shù)，精確到個位數(shù)，且所有人的所占比例之和為100%；不足3人的分組請保留后面的多

2、余空行，請勿修改該表的結(jié)構(gòu)。2、請根據(jù)實際情況填寫任務(wù)分工部分，主要任務(wù)包括：編譯系統(tǒng)的總體分析與設(shè)計，4個具體功能的設(shè)計與實現(xiàn)，對應(yīng)的測試與驗證過程（報告正文需要列出若干組具體測試樣例與對應(yīng)結(jié)果），系統(tǒng)界面的設(shè)計與美工，以及輔助工具、視圖和文件等。3、成績評定部分由指導(dǎo)教師填寫，請勿填寫和修改。報告正文（請用小四號宋體填寫，自行組織章節(jié)和段落）目錄第一部分 實驗成果統(tǒng)計表 1第二部分 實驗簡介 2第三部分 詞法分析 3第四部分 語法分析 64.1 LL(1)語法分析 74.2 LR語法分析 10第五部分 程序測試22第一部分 實驗成果統(tǒng)計表見首頁第二部分 實驗簡介實驗?zāi)康姆纸M（每組最多3人）

3、完成對SNL語言的以下兩個程序：詞法分析程序，語法分析程序（方法不限）。察并鍛煉學(xué)生的團隊協(xié)作能力，代碼編寫能力，加深同學(xué)對編譯原理中SNL編譯系統(tǒng)的理解，幫助同學(xué)理解整個編譯原理的機制實驗內(nèi)容本實驗中實現(xiàn)了SNL編譯系統(tǒng)中的詞法分析、語法分析。其中語法分析包括LL（1）分析方法和LR分析方法詞法分析，以源程序為輸入，生成單詞的內(nèi)部表示TOKEN序列。語法分析，以TOKEN序列為輸入進行語法分析，并生成整個源程序的語法分析樹。在SNL編譯程序中，采用了兩種語法分析方法實現(xiàn)：LL（1）和LR，前者為自頂向下的，后者為自底向上的。兩種語法分析的結(jié)果是一樣的。實驗步驟 編譯系統(tǒng)的總體分析（算法分析，

4、數(shù)據(jù)結(jié)構(gòu)設(shè)計，優(yōu)化）代碼實現(xiàn)，分工進行詞法分析，語法分析部分代碼測試結(jié)果反饋，修正系統(tǒng)界面優(yōu)化設(shè)計第三部分 詞法分析源程序一般表現(xiàn)為字符串（機器語言稱其為ASCII碼）序列的形式，而編譯程序的翻譯工作應(yīng)該在單詞一級上進行，這與自然語言的翻譯理解過程是類似的。因此要進行編譯工作，首先要把源程序的字符序列翻譯成單詞序列。詞法分析是編譯過程的第一階段。它的任務(wù)就是對輸入的字符串形式的源程序按順序進行掃描，根據(jù)源程序的詞法規(guī)則識別具有獨立意義的單詞（符號），并輸出與其等價的TOKEN序列。TOKEN是單詞（符號）的內(nèi)部表示。完成詞法分析任務(wù)的程序稱為詞法分析程序，通常也稱為詞法分析器或掃描器（scan

5、ner）。TOKEN是單詞在編譯程序處理過程中的一種內(nèi)部表示，也是詞法分析程序?qū)Τ绦蛑懈黝悊卧~進行處理之后的輸出形式。對于一種語言而言，如何對它的單詞進行分類，每一類單詞的TOKEN數(shù)據(jù)結(jié)構(gòu)的形式如何，都沒有固定的模式，可以隨編譯程序的不同而不同。通常TOKEN的結(jié)構(gòu)可以分成兩部分，單詞的語法信息和語義信息。其中語法信息記錄的是這個單詞的種類，語義信息則記錄著這個單詞的具體信息。這樣，就能為以后的語法分析和語義分析處理單詞做好準備。SNL語法分析對每類單詞的分析結(jié)果的TOKEN結(jié)構(gòu)為三元組（詞法信息、語義信息以及該單詞在源程序中的行號）。實現(xiàn)詞法分析器的注意事項：1.保留字和標識符名字的區(qū)分2

6、.復(fù)合單詞的處理3.向前搜索及回退4.數(shù)字的轉(zhuǎn)換5.輸入時邊界的處理6.注釋的處理詞法分析主要的類有DoToken、Data、Rule、TokenDoToken是最主要的類，它包括identifier標識符列表、INTC常量列表、isIdentifier()標識符自動機、isINTC()數(shù)字常量自動機。Data類包括tokenShow顯示token用StringBuffer、tokenShow2測試token用StringBuffer、token token列表、separator 分隔符列表等、以及LL（1）分析表，終極符，非終極符等。Rule表示SNL的語法規(guī)則。doToken（）函數(shù)是最

7、主要的函數(shù)，它每次調(diào)用詞法分析方法時要先重新初始化各列表和緩沖字符串，然后從源程序中一個字符一個字符地進行讀取，并逐個分離出單詞，然后構(gòu)造它們的機內(nèi)表示Token。如果該字符不是分隔符則直接追加到sb中，如果該字符是分隔符，則處理分離出的單詞。如果是數(shù)字常量，則對數(shù)字常量進行處理，如果數(shù)字常量列表INTC中沒有該數(shù)字常量則添加。若程序結(jié)束時分離出的單詞長度不為零，則處理為相應(yīng)的Token（盡管詞法分析已失敗，因為程序未能成功結(jié)束），并重新初始化用以分離單詞的緩沖字符串。當整個源程序都分析完成的時候，將TOKEN鏈表中各個TOKEN存入文件Tokenlist.txt中，將來輸出顯示TOKEN時再

8、從Tokenlist.txt中讀取。isIdentifier（）函數(shù)被doToken（）函數(shù)調(diào)用，如果分隔出的字符串是標識符則在token和tokenShow都要追加。isINTC（）函數(shù)被doToken（）函數(shù)調(diào)用，對數(shù)字常量列表進行判斷，如果數(shù)字常量列表中沒有該數(shù)字常量則添加。Token（）函數(shù)中，i表示類型，1為分隔符，2為保留字，3為標識符，4為數(shù)字主要函數(shù)doToken（）的流程圖如下：第四部分 語法分析語法分析是編譯程序的第二階段，也是編譯程序的核心部分。語法分析的任務(wù)是，根據(jù)語言的語法規(guī)則，對源程序進行語法檢查，并識別出相應(yīng)的語法成分。按照SNL編譯程序的模型，語法分析的輸入時從

9、詞法分析器輸出的源程序的TOKEN序列形式，然后根據(jù)語言的文法規(guī)則進行分析處理，語法分析的輸出是無語法錯誤的語法成分，表示成語法樹的形式。語言是具有獨立意義的單詞根據(jù)一定的語法規(guī)則組成的句子的集合，句子的結(jié)構(gòu)由語法規(guī)則給出，句子的含義由語義規(guī)則給出，而對語言的語法分析就是對語言的句子結(jié)構(gòu)的分析。歸于程序設(shè)計語言而言，它的句子就是程序，程序設(shè)計語言定義的是符合其語法規(guī)則的程序的集合，因此程序設(shè)計語言的語法分析的關(guān)鍵是識別程序（句子）的語法結(jié)構(gòu)。完成語法分析任務(wù)的程序成為語法分析程序，也稱為語法分析器或簡稱分析器。 編譯器的語法分析采用自頂向下的語法分析LL（1）和自底向上的語法分析。LL（1）語

10、法分析LL（1）語法分析方法是一種自頂向下的語法分析方法，它是LL（k）分析方法的特例，其中k表示向前看k個符號的意思。LL（1）分析程序工作過程首先初始化，即把開始符壓入棧中，以后的每步分析必是下面的四種情況之一：（1）分析棧的棧頂元素是終極符，則看其是否與輸入流的頭符相匹配，如果匹配成功，則去掉棧頂元素并讀入下一個單詞；若匹配不成功，則報錯。（2）棧頂是非終極符，則用棧頂和輸入流的當前單詞去查當前矩陣，如果查得的值是產(chǎn)生式編號，則把對應(yīng)的產(chǎn)生式右部逆序壓入棧中；如果查得的值為錯誤信息，則報錯。（3）棧已空，輸入流不空，這時輸入流報錯。（4）若棧已空，輸入流也空，則語法分析成功。SNL語法程

11、序的實現(xiàn)采用手工操作構(gòu)造LL（1）分析表。LL（1）分析表用一個二維矩陣表示，其中每個非終極符對應(yīng)一行，每個終極符對應(yīng)一列，一個非終極符和一個終極符可以確定矩陣中的一個元素。 SNL的LL（1）語法分析程序共用到四個棧，分別稱為：符號棧、語法樹棧、操作符棧和操作數(shù)棧。LL（1）語法分析的主要函數(shù)有：doGrammar()、Grammar()、findRuleIndex()、getVariables()、getStartVariable()、computeFirstSets()、computeFollowSet()、getRuledByLeftVariable()、getTerminals()、

12、getFirstSets()、getFallowSets()等等doGrammar()函數(shù)是最主要的函數(shù)。它利用LL（1）分析表和符號棧進行語法分析，并處理終極符不匹配和文件提前結(jié)束錯誤。函數(shù)處理完成后，得到整個語法樹。Grammar()函數(shù)主要進行Rule格式轉(zhuǎn)換。自底向上語法分析LR(0)分析方法實現(xiàn)過程結(jié)構(gòu)如下LR(0) ->LR0Item/在每個產(chǎn)生式的右部適當位置添加一個點構(gòu)成項目->LR0Item(Rule r)/以文法規(guī)則初始化構(gòu)造->getDotPointer()/返回點的位置->goTo()/判斷能否移動->getCurrentTerminal(

13、)/得到點后終極符->LR0State/LR(0)狀態(tài)->closure(Grammar grammar)/求文法閉包->LR0Parser/為LR（0）分析過程建立相應(yīng)的表->createStates()/創(chuàng)建相關(guān)狀態(tài)形成NFA對Token的操作有如下幾種Action ->ACCEPT/接受->SHIFT/移入->REDUCE/規(guī)約LR(1)分析方法實現(xiàn)過程，結(jié)構(gòu)如下LALR(1) ->LR1Item/在每個產(chǎn)生式的右部適當位置添加一個點構(gòu)成項目->LR1Item(Rule r,Lookahead l)->getDotPointer

14、()/返回點的位置->closure(Grammar grammar)/求文法閉包->LR1Parser/為LR(1)分析過程建立相應(yīng)的表->createStatesForLALR1()/創(chuàng)建相關(guān)狀態(tài)形成NFA->createGoToTable()/創(chuàng)建goto表->createActionTable()/創(chuàng)建action表LR分析驅(qū)動程序第五部分 程序測試正確情況：（1）詞法分析：（2）LL（1）語法分析： （3）LR（0）語法分析：（4）LALR（1）語法分析2.錯誤情況（由于篇幅原因這里僅以刪除冒泡排序倒數(shù)第二行endwh為例）：（1）詞法分析：（2） LL

15、（1）語法分析：（3） LR（0）語法分析：（4） LALR（1）語法分析結(jié)論（請用小四號宋體填寫） 還記得第一次編譯系統(tǒng)實驗的時候，我們在得知要設(shè)計一個SNL編譯器時，有很多迷茫。理論課上確實有涉及到設(shè)計的內(nèi)容，然而我們都沒有真正實踐過，完全不知道從何下手。但主要任務(wù)還是清晰的，詞法分析和語法分析。 考慮到時間不足，我們決定先明確每周分工，具體實施的時候就不用擔(dān)心最后趕工的情況發(fā)生了。大致是第一周編譯系統(tǒng)的總體分析（算法分析，數(shù)據(jù)結(jié)構(gòu)設(shè)計，算法優(yōu)化）。第二周代碼實現(xiàn)，分工進行詞法分析，語法分析部分。第三周代碼測試，結(jié)果反饋，系統(tǒng)界面優(yōu)化設(shè)計，實驗報告撰寫。進展有條不紊，每個人都被分到了相應(yīng)的任務(wù)，在具體實現(xiàn)時保持溝通，分工協(xié)作，推動工作開展。編程的過程中我們小組的成員密切配合，積極討論，共同探討不同模塊的耦合關(guān)系以及接口實現(xiàn)，遵循基本的軟件開發(fā)過程：設(shè)計、編碼、集成和測試。整個編程過程鍛煉了我們的學(xué)習(xí)和調(diào)試程序的能力，同時對于一些不完善的細節(jié)通過我們自己的努力進行重新編程和糾錯，最終完成了程序的相關(guān)功能。并達到了更高要求，完成