張?jiān)雒?0543042176-編譯原理課程設(shè)計(jì)-副本

學(xué)生：張?jiān)雒鲗W(xué)號(hào)：0543042176課程：編譯原理與實(shí)踐教師：楊秋輝PAGE46-編譯原理課程設(shè)計(jì)報(bào)告課題名稱：c-minus編譯器__________提交文檔學(xué)生姓名：張?jiān)雒魈峤晃臋n學(xué)生學(xué)號(hào)：0543042176同組成員名單：無(wú)指導(dǎo)教師姓名：楊秋輝指導(dǎo)教師評(píng)閱成績(jī)：指導(dǎo)教師評(píng)閱意見(jiàn)：..提交報(bào)告時(shí)間：2007年12月4日目錄編譯原理課程設(shè)計(jì)報(bào)告 11. 課程設(shè)計(jì)目標(biāo) 32. 分析與設(shè)計(jì) 32.1程序設(shè)計(jì)思路 32.2系統(tǒng)體系結(jié)構(gòu) 42.3數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 52.3.1各數(shù)據(jù)結(jié)構(gòu)使用介紹 52.3.2程序中各數(shù)據(jù)結(jié)構(gòu)的聲明 72.4設(shè)計(jì)類 82.4.1TokenType.java 82.4.2TokenProcess.java 82.4.3FirstSet.java 82.4.4FollowSet.java 92.4.5ParsingTable.java 92.4.6ParsingTreeNode 102.4.7ParsingTree.java 102.4.8TreeFrame.java 112.4.9Controller.java 112.5重要函數(shù)流程圖 122.5.1FirstSet類getFirstSet()函數(shù) 122.5.2FollowSet類getFollowSet()函數(shù) 132.6程序測(cè)試流程設(shè)計(jì) 143. 程序代碼實(shí)現(xiàn) 153.1C-minus.l 153.2TokenType.java 183.3TokenProcess.java 193.4FirstSet.java 203.5FollowSet.java 223.6ParsingTable.java 273.7ParsingTree.java 293.8TreeFrame.java 323.9Controller.java 353.10ParsingTreeNode類 394. 測(cè)試結(jié)果 394.1測(cè)試數(shù)據(jù)選擇 394.2測(cè)試結(jié)果分析 415. 總結(jié) 465.1收獲 465.2特色 465.3不足 461. 課程設(shè)計(jì)目標(biāo)本課程設(shè)計(jì)是實(shí)現(xiàn)c-minus編譯器的前兩個(gè)部分，即詞法分析和語(yǔ)法分析。要求能夠掌握編譯原理的基本理論,，理解了編譯程序的基本結(jié)構(gòu)，掌握了編譯各階段的基本理論和技術(shù)，掌握了編譯程序設(shè)計(jì)的基本理論和步驟.，增強(qiáng)編寫和調(diào)試高級(jí)語(yǔ)言源程序的能力。并且能夠掌握詞法分析、語(yǔ)法分析的基本概念和實(shí)現(xiàn)方法，能夠用給定的c-minus語(yǔ)言文法變換成可以進(jìn)行LL(1)分析的LL(1)文法，并自動(dòng)由程序生成其對(duì)應(yīng)的First集和Follow集，以及分析表，并且能夠?qū)⒔o定的c-minus源程序進(jìn)行詞法和語(yǔ)法編譯，并最終生成其對(duì)應(yīng)的分析樹。2. 分析與設(shè)計(jì)2.1程序設(shè)計(jì)思路系統(tǒng)采用面向?qū)ο蟮脑O(shè)計(jì)思想，用Java語(yǔ)言實(shí)現(xiàn)。整個(gè)系統(tǒng)的實(shí)現(xiàn)分三個(gè)步驟：詞法分析、文法轉(zhuǎn)換和語(yǔ)法分析。詞法分析所謂詞法分析就是將用C-minus語(yǔ)言編寫好的源程序解析成一個(gè)個(gè)編譯器可以識(shí)別的tokens，這部分工作是由ParserGenerator軟件實(shí)現(xiàn)的，我所做的只是編寫ParserGenerator的輸入文件(見(jiàn)3.1節(jié)C-minus.l)，然后通過(guò)ParserGenerator生成具體的Java語(yǔ)言的詞法分析器。文法轉(zhuǎn)換文法轉(zhuǎn)換是將所給的C-minus文法轉(zhuǎn)化為可以進(jìn)行LL(1)分析的LL(1)文法，這部分的轉(zhuǎn)換分為兩個(gè)步驟，第一步是將原來(lái)非LL(1)文法中的直接的左遞歸和左因子轉(zhuǎn)化為對(duì)應(yīng)的LL(1)文法的形式，第二個(gè)步驟是在第一個(gè)步驟的基礎(chǔ)之上將間接的左遞歸和左因子轉(zhuǎn)化，并最終形成標(biāo)準(zhǔn)的LL(1)文法。本部分手工完成并由程序檢驗(yàn)是否變換成功。語(yǔ)法分析語(yǔ)法分析第一步是將給定的LL(1)文法通過(guò)求First集和Follow集，并最終形成文法的分析表的過(guò)程，第二步結(jié)合詞法分析產(chǎn)生的token，并對(duì)照分析表建立分析樹，這是本次課程設(shè)計(jì)的最后一步。本部分還會(huì)判斷輸入的文法文件是否有語(yǔ)法錯(cuò)誤，比如出現(xiàn)了一個(gè)既不是非終結(jié)符號(hào)又不是終結(jié)符號(hào)的符號(hào)等。以上三個(gè)過(guò)程的形象化表示和其之間的關(guān)系見(jiàn)圖2-1.掃描器掃描器Token文件Tokentype文件1.詞法分析3.語(yǔ)法分析求First集求Follow集構(gòu)建分析表初始文法消除直接的左遞歸和左因子LL(1)文法2.文法變換消除間接的左遞歸和左因子C-minus源程序執(zhí)行分析過(guò)程構(gòu)建分析樹圖2-SEQ圖_2-\*ARABIC1詞法分析、文法轉(zhuǎn)換、語(yǔ)法分析的過(guò)程和其之間關(guān)系示意圖2.2系統(tǒng)體系結(jié)構(gòu) 本系統(tǒng)采用面向?qū)ο蟮乃枷脒M(jìn)行設(shè)計(jì)和實(shí)現(xiàn)，如2.1節(jié)中闡述的那樣，系統(tǒng)的實(shí)現(xiàn)分為三個(gè)部分，見(jiàn)圖2-1. 本系統(tǒng)在實(shí)現(xiàn)過(guò)程中一共設(shè)計(jì)了十個(gè)類，各個(gè)類的名稱和作用見(jiàn)表2-1.表2-SEQ表_2-\*ARABIC1系統(tǒng)中各個(gè)類的說(shuō)明類名功能備注TokenType提供文法中所有的終結(jié)符合的定義。是接口TokenProcess提供對(duì)終結(jié)符合的處理功能，包括將int型的終結(jié)符號(hào)轉(zhuǎn)化為String型，以及判斷一個(gè)String型的符號(hào)是否終結(jié)符號(hào)。Parser將輸入的源程序轉(zhuǎn)化為tokens，并分為token和tokentype分別存放在兩個(gè)文件中，以便使用。由ParserGenerator通過(guò)“C-minus.l”輸入文件自動(dòng)生成。FirstSet負(fù)責(zé)將文法轉(zhuǎn)入數(shù)據(jù)結(jié)構(gòu)(見(jiàn)2.3節(jié)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì))，并且判斷文法是否有語(yǔ)法錯(cuò)誤，以及求文法的First集。FollowSet負(fù)責(zé)求文法的Follow集合。ParsingTable負(fù)責(zé)構(gòu)建文法的分析表ParsingTree負(fù)責(zé)生成源程序?qū)?yīng)于文法的分析樹。ParsingTreeNodeParsingTree的內(nèi)部類，負(fù)責(zé)定義分析樹的節(jié)點(diǎn)。TreeFrame負(fù)責(zé)將ParsingTree中產(chǎn)生的分析樹用JTree的Swing控件形象化顯示出來(lái)。Controller系統(tǒng)中的主類，負(fù)責(zé)控制整個(gè)流程。 系統(tǒng)中各個(gè)類之間的關(guān)系見(jiàn)圖2-2(圖形制作：RationalRose2003)。圖2-SEQ圖_2-\*ARABIC2系統(tǒng)中類關(guān)系圖2.3數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2.3.1各數(shù)據(jù)結(jié)構(gòu)使用介紹本系統(tǒng)中所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)主要是鏈表數(shù)組和向量。1.將文法裝入數(shù)據(jù)結(jié)構(gòu)文法的存儲(chǔ)涉及到了六個(gè)數(shù)據(jù)結(jié)構(gòu)，分別是：vectorGrammar --將文法按照候選分開存儲(chǔ)的向量vectorGrammarTogether --將文法按照非終結(jié)符號(hào)存儲(chǔ)的向量listGrammar[] --將文法按照候選分開存儲(chǔ)的鏈表數(shù)組listNonTerminals --存儲(chǔ)所有的非終結(jié)符號(hào)的鏈表listTerminals --存儲(chǔ)所有終結(jié)符號(hào)的鏈表listNonTerminalApartly --按照候選存儲(chǔ)所有非終結(jié)符號(hào)的鏈表由于數(shù)據(jù)結(jié)構(gòu)太多，不好一一詳述，下面介紹什么是按照候選的存儲(chǔ)方式：系統(tǒng)實(shí)現(xiàn)過(guò)程中首先將文法按照候選分開寫，分別都存放在listGrammar數(shù)組的鏈表元素中。這一過(guò)程示意如下： 首先對(duì)于下面的一行文法：declaration-1→var-declaration-1|(params)compound-stmt 將其按照候選分開寫，如下： declaration-1→var-declaration-1 declaration-1→(params)compound-stmt 可以看出一行文法變成了兩行，然后將這兩行文法存儲(chǔ)在兩個(gè)鏈表中，即鏈表數(shù)組的兩個(gè)連續(xù)的元素中，如表2-2所示：表2-SEQ表_2-\*ARABIC2文法入鏈表示意表鏈表元素0元素1元素2元素3listGrammar[i]var-declaration-1listGrammar[i+1](params)compound-stmt 然后將每個(gè)鏈表裝入Vector中，形成一個(gè)Vector對(duì)象，如表2-3所示：表2-SEQ表_2-\*ARABIC3文法向量示意表Vector對(duì)象元素0元素1元素2……vectorGrammarlistGrammar[0]listGrammar[1]listGrammar[2]…… 2.First集合的存儲(chǔ)First集合的存儲(chǔ)涉及到了四個(gè)數(shù)據(jù)結(jié)構(gòu)，分別是：vectorFirstSetApart --按照候選存儲(chǔ)First集合鏈表的向量vectorFirstSet --按照非終結(jié)符號(hào)存儲(chǔ)First集合鏈表的向量listFirstSetApart [] --按照候選存儲(chǔ)First集合的鏈表數(shù)組listFirstSet[] --按照非終結(jié)符號(hào)存儲(chǔ)First集合的鏈表數(shù)組這四個(gè)數(shù)據(jù)結(jié)構(gòu)共同協(xié)作，實(shí)現(xiàn)了系統(tǒng)中對(duì)First集合的存儲(chǔ)和使用工作。前兩個(gè)向量對(duì)象的存儲(chǔ)機(jī)制與表2-3中的存儲(chǔ)機(jī)制相似，這里不再贅述，下面重點(diǎn)介紹后兩個(gè)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)機(jī)制：還是對(duì)于本節(jié)第一部分的文法來(lái)說(shuō)：declaration-1→var-declaration-1|(params)compound-stmt 將其按照候選分開寫，如下： declaration-1→var-declaration-1 declaration-1→(params)compound-stmt分別對(duì)每個(gè)候選求First集合，假設(shè)得到的結(jié)果如下： First(declaration-1)={(,ID,NUM,int} First(declaration-1)={if,else,while}然后將這兩個(gè)First集合裝入listFirstSetApart []數(shù)組中的兩個(gè)連續(xù)的元素中，如表2-4所示：表2-SEQ表_2-\*ARABIC4按候選存儲(chǔ)的First集合示意鏈表元素0元素1元素2元素3ListFirstSetApart[i](IDNUMIntlistFirstSetApart[i+1]IfElsewhile然后需要構(gòu)建按照非終結(jié)符號(hào)存儲(chǔ)的First集合，即將上面的數(shù)組中類似以上的兩個(gè)元素合并起來(lái)，之后的存儲(chǔ)機(jī)制如表2-5所示：表2-SEQ表_2-\*ARABIC5按非終結(jié)符號(hào)存儲(chǔ)的First集合示意鏈表元素0元素1元素2元素3元素4元素5元素6listFirstSet[k](IDNUMIntIfElsewhile 之所以要選擇這樣的存儲(chǔ)方式是為了系統(tǒng)的需要，具體請(qǐng)見(jiàn)2.4節(jié)設(shè)計(jì)類。 3.Follow集合的存儲(chǔ) Follow集合的存儲(chǔ)涉及的數(shù)據(jù)結(jié)構(gòu)有以下四個(gè)：vectorFollowSetvectorFollowSetApartlistFollowSet[]listFollowSetApart[]Follow集合的存儲(chǔ)方式非常類似于First集合的存儲(chǔ)方式，這里就不再闡述了。 4.分析表的存儲(chǔ)分析表的存儲(chǔ)涉及的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)：String[][]parsingTable很明顯，這是一個(gè)字符串形式的二維數(shù)組，元素通過(guò)其在listNonTerminals和listTerminals(見(jiàn)1.將文法裝入數(shù)據(jù)結(jié)構(gòu))中的位置確定其在分析表中的位置。 5.分析樹的存儲(chǔ) 分析樹的存儲(chǔ)涉及到的數(shù)據(jù)結(jié)構(gòu)只有一個(gè)：ParsingTreeNoderoot;這是ParsingTreeNode類的實(shí)例，這個(gè)類中有指向自己的元素?cái)?shù)組(見(jiàn)2.4.6節(jié))2.3.2程序中各數(shù)據(jù)結(jié)構(gòu)的聲明 本系統(tǒng)中各數(shù)據(jù)結(jié)構(gòu)的聲明是分布在不同的文件中的，具體見(jiàn)圖2-3、圖2-4、圖2-5及圖2-6中的說(shuō)明。publicpublicVectorvectorGrammar;//格式化存儲(chǔ)文法結(jié)構(gòu)的向量publicVectorvectorGrammarTogether;//格式化存儲(chǔ)文法結(jié)構(gòu)的向量publicVectorvectorFirstSetApart;//存儲(chǔ)按照候選分開的各個(gè)非終結(jié)符的first集合publicVectorvectorFirstSet;//存儲(chǔ)每個(gè)非終結(jié)符的first集合，按照非終結(jié)符分類publicLinkedListlistNonTerminals;//存儲(chǔ)非終結(jié)字符的鏈表對(duì)象publicLinkedListlistGrammar[];//裝有每條文法的鏈表數(shù)組publicLinkedListlistFirstSetApart[];//按候選裝每個(gè)非終結(jié)符號(hào)的First集鏈表數(shù)組publicLinkedListlistFirstSet[];//按非終結(jié)符號(hào)裝每個(gè)符號(hào)的First集的鏈表數(shù)組圖2-SEQ圖_2-\*ARABIC3FirstSet類中涉及的數(shù)據(jù)結(jié)構(gòu) //存儲(chǔ)follow集的Vector對(duì)象publicVectorvectorFollowSet;publicVectorvectorFollowSetApart; //暫存follow集的鏈表數(shù)組publicLinkedListlistFollowSet[];//按照非終結(jié)字符種類存放publicLinkedListlistFollowSetApart[];//按照各個(gè)非終結(jié)字符的候選來(lái)存放圖2-SEQ圖_2-\*ARABIC4FollowSet類中涉及的數(shù)據(jù)結(jié)構(gòu)publicpublicLinkedListlistTerminals;//存儲(chǔ)終結(jié)符號(hào)的鏈表publicString[][]parsingTable;//String型的二維數(shù)組，用來(lái)存儲(chǔ)分析表publicLinkedListlistNonTerminalApartly;//用來(lái)將非終結(jié)符號(hào)按候選分開存放的鏈表圖2-SEQ圖_2-\*ARABIC5ParsingTable類中涉及的數(shù)據(jù)結(jié)構(gòu)publicpublicParsingTreeNoderoot;圖2-SEQ圖_2-\*ARABIC6ParsingTree類中涉及到的數(shù)據(jù)結(jié)構(gòu)2.4設(shè)計(jì)類2.4.1TokenType.java此類是個(gè)接口，用來(lái)提供文法中所有的終結(jié)符合的定義，其實(shí)現(xiàn)很簡(jiǎn)單，如下所示：packagepackagecminus;publicinterfaceTokenType{ publicfinalintENDFILE=0; //endfile publicfinalintELSE=1; //else //省略}圖2-SEQ圖_2-\*ARABIC7TokenType接口2.4.2TokenProcess.java本類實(shí)現(xiàn)接口TokenType，提供對(duì)終結(jié)符合的處理功能，包括將int型的終結(jié)符號(hào)轉(zhuǎn)化為String型，以及判斷一個(gè)String型的符號(hào)是否終結(jié)符號(hào)，在多個(gè)類中都有其實(shí)例的定義。本類的類結(jié)構(gòu)圖如圖2-8所示。圖2-SEQ圖_2-\*ARABIC8TokenProcess類結(jié)構(gòu)圖其中：tokenToString函數(shù)用來(lái)將int型的終結(jié)符號(hào)轉(zhuǎn)化為String型，isTerminal函數(shù)用來(lái)判斷一個(gè)String型的符號(hào)是否終結(jié)符號(hào)。2.4.3FirstSet.java本類負(fù)責(zé)將文法轉(zhuǎn)入數(shù)據(jù)結(jié)構(gòu)，并且判斷文法是否有語(yǔ)法錯(cuò)誤，以及求文法的First集。本類類結(jié)構(gòu)圖如圖2-9所示。圖2-SEQ圖_2-\*ARABIC9FirstSet類結(jié)構(gòu)圖2.4.4FollowSet.java本類負(fù)責(zé)求文法的Follow集合。本類的結(jié)構(gòu)如圖2-10所示。圖2-SEQ圖_2-\*ARABIC10FollowSet類結(jié)構(gòu)圖2.4.5ParsingTable.java本類負(fù)責(zé)構(gòu)建文法的分析表，其結(jié)構(gòu)如圖2-11所示。圖2-SEQ圖_2-\*ARABIC11ParsingTable類結(jié)構(gòu)圖2.4.6ParsingTreeNode本類ParsingTree的內(nèi)部類，負(fù)責(zé)定義分析樹的節(jié)點(diǎn)。圖2-SEQ圖_2-\*ARABIC12ParsingTreeNode類結(jié)構(gòu)圖2.4.7ParsingTree.java本類負(fù)責(zé)生成源程序?qū)?yīng)于文法的分析樹。 圖2-SEQ圖_2-\*ARABIC13ParsingTree類結(jié)構(gòu)圖2.4.8本類負(fù)責(zé)將ParsingTree中產(chǎn)生的分析樹用JTree的Swing控件形象化顯示出來(lái)。圖2-SEQ圖_2-\*ARABIC14TreeFrame類結(jié)構(gòu)圖2.4.9本類系統(tǒng)中的主類，負(fù)責(zé)控制整個(gè)流程。圖2-SEQ圖_2-\*ARABIC15Controller類結(jié)構(gòu)圖2.5重要函數(shù)流程圖2.5.1FirstSet類getFirstSet()函數(shù)YYNYNYYNN開始取一行文法L得到L中第一個(gè)符號(hào)A得到下一個(gè)符號(hào)BB是終結(jié)符號(hào)加B到First(A)中將First(B)-ε加入First(A)ε∈First(B)B不為空加ε到First(A)中繼續(xù)圖2-SEQ圖_2-\*ARABIC16求First集程序流程圖2.5.2FollowSet類getFollowSet()函數(shù)YYNNYYNNYYN開始取一行文法L得到L中第一個(gè)符號(hào)AL中有兩個(gè)Token得到下兩個(gè)符號(hào)B和C得到下一個(gè)符號(hào)BB為終結(jié)符加Follow(A)給Follow(B)B為終結(jié)符號(hào)得到從C開始直到L最后一個(gè)字符的First集S將S-ε加入Follow(B)ε∈S將Follow(A)加入Follow(B)C是文法最后一個(gè)字符將Follow(A)加入Follow(C)圖2-SEQ圖_2-\*ARABIC17求Follow集程序流程圖2.6程序測(cè)試流程設(shè)計(jì)Token文件Token文件輸入源程序Tokentype文件輸入文法文件First集測(cè)試Follow集測(cè)試分析表測(cè)試分析樹測(cè)試詞法分析測(cè)試語(yǔ)法分析測(cè)試圖2-SEQ圖_2-\*ARABIC18系統(tǒng)測(cè)試流程圖3. 程序代碼實(shí)現(xiàn)3.1C-minus.l/************************************************//************************************************//*Inputfileforlexforc-minus *//*Author:張?jiān)雒?0543042176)*//************************************************/%{importjava.io.*;importjava.util.*;%}%nameParser//classdefinition{ //Attributes publicstaticintlineno=1; publicStringsourceFileName; privateTokenProcesstokenPro=newTokenProcess();}//constructorfunction{ //donothing}//macrosdigit [0-9]number {digit}+letter [a-zA-Z]identifier {letter}+newline \r\nwhitespace [\t]+%%//returnexpressions%return"else" {returnELSE;}"if" {returnIF;}"int" {returnINT;}"return" {returnRETURN;}"void" {returnVOID;}"while" {returnWHILE;}"while" {returnWHILE;}{identifier} {returnID;}"+" {returnADD;}"-" {returnMINUS;}"*" {returnMUL;}"/" {returnDIV;}"<" {returnLESSTHEN;}"<=" {returnLESSEQUALTHEN;}">" {returnMORETHEN;}">=" {returnMOREEQUALTHEN;}"==" {returnEQUAL;}"!=" {returnNOTEQUAL;}"=" {returnASSIGN;}";" {returnSEMICOLON;}"," {returnCOMMA;} "(" {returnLSB;}")" {returnRSB;}"[" {returnLMB;}"]" {returnRMB;}"{" {returnLBB;}"}" {returnRBB;}"/*" { intc; booleanbloop=true; try{ while(bloop){ c=yyinput(); if(c=='\n') lineno++; elseif(c=='*'){ intcc=yyinput(); if(cc=='/') bloop=false; } } }catch(Exceptione){} break; }//"*/" {returnRCOMMENT;}{number} {returnNUM;}{newline} {lineno++;}{whitespace} {/*skipwhitespace*/break;}. {returnERROR;}%% publicvoidsetSourceFile(Stringfilename){ publicvoidsetSourceFile(Stringfilename){//設(shè)置源程序的文件名和路徑 sourceFileName=filename; } publicvoidgetToken()throwsException{//獲取源程序中所有的token，并存放在tokenFile和tokenTypeFile文件中。 StringtokenFile="tokenFile"; StringtokenTypeFile="tokenTypeFile"; //declarationthefile FileWriterToken=newFileWriter(tokenFile); FileWriterTokenType=newFileWriter(tokenTypeFile); Token.close(); TokenType.close(); //declarationforfileappender FileWriterwriteToken=newFileWriter(tokenFile,true); PrintWriterwriteTokenType= newPrintWriter(newFileWriter(tokenTypeFile,true)); //setsourcefile try{ Filefile=newFile(sourceFileName); yyin=newInputStreamReader(newFileInputStream(file)); }catch(FileNotFoundExceptione){ System.err.println("文件無(wú)法找到:"+e.getMessage()); System.exit(1); } yycreate(); intn=0; while((n=yylex())!=0){ writeTokenType.println("Line-"+this.lineno+""+tokenPro.tokenToString(n)); writeToken.write("Line-"+this.lineno+""); for(inti=0;i<yyleng;i++){ writeToken.write((char)yytext[i]); } writeToken.write("\n"); writeToken.flush(); } writeToken.close(); writeTokenType.close(); System.out.println("Scanningcompleted!\nSeefile'"+tokenFile+"'and'"+tokenTypeFile+"'."); } publicvoidshowTokens(){//打印所有的tokens，從文件中讀取，然后打印 try{ System.out.println("\nThetokensareasbelow:"); BufferedReaderfileIn= newBufferedReader(newFileReader("tokenFile")); Stringline=fileIn.readLine(); while(line!=null){ System.out.println("\t\t"+line); line=fileIn.readLine(); } } fileIn.close(); }catch(IOExceptione){ System.err.println("Readingfileerror:"+e.getMessage()); } } publicstaticvoidmain(Stringargs[])throwsException{//主函數(shù)，為了測(cè)試時(shí)的方便而加上的，可以刪去。 Parserparser=newParser(); try{ parser.setSourceFile("zhang.cm"); parser.getToken(); }catch(Exceptione){ System.err.println("Scanningerror:"+e.getMessage()); } }}packagecminus;/**packagecminus;/***Interfaceforutilityusing,*allreservedwordsandsymbolaredefinitehere.*@author張?jiān)雒?0543042176)**/publicinterfaceTokenType{ publicfinalintENDFILE=0; //endfile publicfinalintELSE=1; //else publicfinalintIF=2; //if publicfinalintINT=3; //int publicfinalintRETURN=4; //return publicfinalintVOID=5; //void publicfinalintWHILE=6; //while publicfinalintADD=7; //+ publicfinalintMINUS=8; //- publicfinalintMUL=9; //* publicfinalintDIV=10; /// publicfinalintLESSTHEN=11; //< publicfinalintLESSEQUALTHEN=12;//<= publicfinalintMORETHEN=13; //> publicfinalintMOREEQUALTHEN=14;//>= publicfinalintEQUAL=15; //== publicfinalintNOTEQUAL=16; //!= publicfinalintASSIGN=17; //= publicfinalintSEMICOLON=18; // ; publicfinalintCOMMA=19; // , publicfinalintLSB=20; // ( publicfinalintRSB=21; // ) publicfinalintLMB=22; // [ publicfinalintRMB=23; // ] publicfinalintLBB=24; // { publicfinalintRBB=25; // } publicfinalintLCOMMENT=26; // /* publicfinalintRCOMMENT=27; // */ publicfinalintNUM=28; // number publicfinalintID=29; // identifier publicfinalintERROR=100; // error publicfinalintEMPTY=101; //empty空字 }//endofinterfacepackagecminus;publicclassTokenProcesspackagecminus;publicclassTokenProcessimplementsTokenType{ /** *將int型的token轉(zhuǎn)化為String型的token以便于使用 *@paramtoken int被轉(zhuǎn)化的token *@return 對(duì)應(yīng)的String形式的token */ publicstaticStringtokenToString(inttoken){ switch(token){ caseIF: return"if"; caseELSE: return"else"; caseINT: return"int"; caseRETURN: return"return"; caseVOID: return"void"; //省略，以下的形式都一樣，不再贅述 default: return"UnkownToken"; } } /** *輔助函數(shù)：判斷某個(gè)字符是否是終結(jié)字符 * *@paramtoken被判斷的字符 *@return是終結(jié)字符是返回true否則返回false */ publicstaticbooleanisTerminal(Stringtoken){ if(token.equals("if")||token.equals("else")||token.equals("int") ||token.equals("return")||token.equals("void") ||token.equals("while")||token.equals("+") ||token.equals("-")||token.equals("*")||token.equals("/") ||token.equals("<")||token.equals("<=")||token.equals(">") ||token.equals(">=")||token.equals("==") ||token.equals("!=")||token.equals("=")||token.equals(";") ||token.equals(",")||token.equals("(")||token.equals(")") ||token.equals("[")||token.equals("]")||token.equals("{") ||token.equals("}")||token.equals("ID") ||token.equals("NUM")||token.equalsIgnoreCase("EMPTY")){ returntrue; }else{ returnfalse; } }}packagecminus;/**packagecminus;/***Classname：FirstSet.*功能：* 得到文法的first集合，并且判斷文法是否是LL(1)文法。* 同時(shí)得到文法中所有非終結(jié)符號(hào)的個(gè)數(shù)并且格式化存儲(chǔ)之。*@authorAdministrator*/importjava.io.*;importjava.util.*;publicclassFirstSet{ //由于程序太大，其他函數(shù)和類屬性的定義省略，這里只給出求First集的函數(shù)getFirstSet() publicvoidgetFirstSet(){ intfirst=0; booleanchanged=true; booleanisChanged[]=newboolean[vectorGrammar.size()]; Stringsymbol="";//產(chǎn)生式中第一個(gè)字符 while(changed){ for(intassign=0;assign<isChanged.length;assign++){ isChanged[assign]=false; } for(inti=0;i<vectorGrammar.size();i++){ intk=1; booleanisContinue=true; while(isContinue&&k<=listGrammar[i].size()-1){ Stringsymbol2=""; booleanisToJudgeContainsEmpty=true;//是否需要判斷first(Xk)包含空字 //如果得到的每行的第一個(gè)值是非終結(jié)符號(hào)，這點(diǎn)肯定滿足 if(!tokenPro.isTerminal(symbol=(String)listGrammar[i].get(0))){ symbol2=(String)listGrammar[i].get(k);//產(chǎn)生式中第二個(gè)字符 //如果下一個(gè)符號(hào)是終結(jié)字符，直接加到當(dāng)前鏈表的first集合中 if(tokenPro.isTerminal(symbol2)){ isToJudgeContainsEmpty=false; if(!listFirstSetApart[i].contains(symbol2)){ listFirstSetApart[i].add(symbol2.trim()); isChanged[i]=true;//改變了 } }else{ //如果第二個(gè)不是終結(jié)字符，那么就找到此符號(hào)的first集， //將其中的除empty外的所有符號(hào)加入到當(dāng)前非終結(jié)符號(hào)的first集合中 //找到以該非終結(jié)字符為首的鏈表 for(inta=0;a<vectorGrammar.size();a++){ Stringsymbol3=(String)listGrammar[a].get(0); if(symbol3.equals(symbol2)){//二者相等，說(shuō)明找到了 //找到之后將其first集中的所有東西給當(dāng)前鏈表 for(intb=1;b<listFirstSetApart[a].size();b++){ Stringtmp=(String)listFirstSetApart[a].get(b); if(!tmp.equalsIgnoreCase("EMPTY")){ if(!listFirstSetApart[i].contains(tmp)){ listFirstSetApart[i].add(tmp.trim()); isChanged[i]=true; } } } //break;此處不能break } } } } //判斷symbol2的first集中是否有空 if(isToJudgeContainsEmpty){ for(intp=0;p<vectorGrammar.size();p++){//找到以該非終結(jié)字符為首的鏈表 Stringsymbol3=(String)listGrammar[p].get(0); if(symbol3.equals(symbol2)){//二者相等，說(shuō)明找到了 if(!this.listFirstSetApart[p].contains("EMPTY")){ isContinue=false; }else{ isContinue=true; break; } //break;此處不能break } } }else{ isContinue=false; } k++; }//endofwhile if(isContinue){ if(!listFirstSetApart[i].contains("EMPTY")){ listFirstSetApart[i].add("EMPTY".trim()); isChanged[i]=true; } } } for(inti=0;i<vectorGrammar.size();i++){ if(isChanged[i]){ changed=true; break; }else changed=false; } } }packagecminus;/**packagecminus;/***Classname：FollowSet.*繼承了FirstSet類。*功能：* 得到文法的follow集合，并且判斷文法是否是LL(1)文法。*@authorAdministrator*/importjava.util.*;importjava.io.*;publicclassFollowSetextendsFirstSet{ //由于程序太大，其他函數(shù)和類屬性的定義省略，這里只給出求Follow集的函數(shù)getFollowSet() publicvoidgetFollowSet(){ //初始化暫存follow集的鏈表數(shù)組 listFollowSet=newLinkedList[this.numOfNonTerminals]; listFollowSetApart=newLinkedList[this.vectorGrammar.size()]; //初始化各個(gè)listFollowSetApart數(shù)組，按照候選存儲(chǔ)各個(gè)非終結(jié)符號(hào)的Followset try{ for(inti=0;i<vectorGrammar.size();i++) listFollowSetApart[i]=newLinkedList(); for(inti=0;i<vectorGrammar.size();i++){ //每個(gè)鏈表都存儲(chǔ)了一個(gè)非終結(jié)符號(hào)作為標(biāo)識(shí) listFollowSetApart[i].add(listGrammar[i].get(0)); } }catch(Exceptione){ System.out.println("初始化follow集數(shù)組錯(cuò)誤： "+e.getMessage()); } //求Follow集 //初始化 listFollowSetApart[0].add("$".trim()); booleanisChanged[]=newboolean[vectorGrammar.size()]; booleanchanged=true; while(changed){ for(inttt=0;tt<isChanged.length;tt++){ isChanged[tt]=false; } for(inti=0;i<this.vectorGrammar.size();i++){ //如果token個(gè)數(shù)為2 if(listGrammar[i].size()==2){ //如果第二個(gè)token不是終結(jié)符號(hào)，則將第一個(gè)的follow集給第二個(gè)token的follow集。 Stringstr1=(String)listGrammar[i].get(0); Stringstr=(String)listGrammar[i].get(1); if(!tokenPro.isTerminal(str)){ for(intk=0;k<this.vectorGrammar.size();k++){//findstr'sfollowset if(((String)listFollowSetApart[k].get(0)).equals(str)){ //findstr1'sfollowset for(inta=0;a<this.vectorGrammar.size();a++){ Stringtmp1=(String)listFollowSetApart[a].get(0); if(str1.equals(tmp1)){ for(ints=1;s<listFollowSetApart[a].size();s++){ Stringtmp=(String)listFollowSetApart[a].get(s); if(!listFollowSetApart[k].contains(tmp)){ listFollowSetApart[k].add(tmp.trim()); isChanged[i]=true; } } //break;//cannotbebreakhere } } } } } //如果token的個(gè)數(shù)大于二 else{ for(intj=1;j<listGrammar[i].size()-1;j++){ inttempflag=j;//臨時(shí)標(biāo)記變量，用來(lái)指示臨時(shí)鏈表從何處(哪個(gè)token)開始構(gòu)建 //一次獲取兩個(gè)token Stringstr1=(String)listGrammar[i].get(j); //此次得到str2為了判斷結(jié)尾時(shí)使用 Stringstr2=(String)listGrammar[i].get(j+1); if(!tokenPro.isTerminal(str1)){ //將str2str3...的first集中不是empty的元素給str1的follow集 //通過(guò)將上面的first集合求出裝載在一個(gè)臨時(shí)的鏈表里，然后復(fù)制這個(gè)鏈表來(lái)實(shí)現(xiàn)。 LinkedListtmpList=newLinkedList();//存儲(chǔ)first集的臨時(shí)鏈表 Stringfirst=(String)listGrammar[i].get(0);//獲取第一個(gè)token //構(gòu)建這個(gè)臨時(shí)鏈表，將str2str3...的first集裝入臨時(shí)鏈表 booleanisBreak=false; for(intbb=tempflag+1;bb<this.listGrammar[i].size();bb++){ StringbbString=(String)this.listGrammar[i].get(bb);//得到str2 if(tokenPro.isTerminal(bbString)){ if(!tmpList.contains(bbString)){ tmpList.add(bbString); } isBreak=true; break; } else{ //找到str2的first集 for(ints=0;s<this.numOfNonTerminals;s++){ Stringtmp2=(String)listFirstSet[s].get(0); if(bbString.equals(tmp2)){//findit //copybbString'sfirsttotmpList for(inthh=1;hh<listFirstSet[s].size();hh++){ if(!listFirstSet[s].contains("EMPTY")){ isBreak=true; } StringhhString=(String)listFirstSet[s].get(hh); if(!tmpList.contains(hhString)&& (!hhString.equalsIgnoreCase("EMPTY"))){ tmpList.add(hhString); } } break; } } if(isBreak){ break; } } } if(isBreak==false){ tmpList.add("EMPTY"); } //將臨時(shí)鏈表中的除了EMPTY的元素拷貝到str1的follow集中 for(intk=0;k<vectorGrammar.size();k++){ Stringtmp3=(String)listFollowSetApart[k].get(0); if(str1.equals(tmp3)){ for(intfff=0;fff<tmpList.size();fff++){ StringtmpStr=((String)tmpList.get(fff)).trim(); if(!tmpStr.equalsIgnoreCase("EMPTY")){ if(!listFollowSetApart[k].contains(tmpStr)){ listFollowSetApart[k].add(tmpStr); isChanged[i]=true; } } } break; } } booleantempboolean=false;//標(biāo)記臨時(shí)鏈表中是否有empty的變量。 if(tmpList.contains("EMPTY")){ tempboolean=true; } tmpList.clear(); //如果臨時(shí)鏈表中有EMPTY，則將第一個(gè)token的follow集拷貝給str1的follow集 if(tempboolean==true){ //findstr1'sfollowset for(intk=0;k<vectorGrammar.size();k++){ Stringtmp3=(String)listFollowSetApart[k].get(0); if(str1.equals(tmp3)){//findit. //findfirst'sfollowset for(intf=0;f<vectorGrammar.size();f++){ Stringtmp4=(String)listFollowSetApart[f].get(0); if(first.equals(tmp4)){//finditfor(intg=1;g<listFollowSetApart[f].size();g++){Stringtmp5=(String)listFollowSetApart[f].get(g); if(!listFollowSetApart[k].contains(tmp5)){ listFollowSetApart[k].add(tmp5.trim()); isChanged[i]=true; } } } } } break; } } } } //如果一個(gè)token是這行的最后一個(gè)token，則將第一個(gè)token的follow集拷貝到這個(gè)token的follow集中。 if(j==listGrammar[i].size()-2){ //Atthistime,str2isthelasttoken if(!tokenPro.isTerminal(str2)){//Findstr2'sfollowset for(inta=0;a<this.vectorGrammar.size();a++){ Stringtemp=(String)listFollowSetApart[a].get(0); if(str2.equals(temp)){//findit Stringheihei=(String)listGrammar[i].get(0); //Findthefirsttoken'sfollowset for(intb=0;b<this.vectorGrammar.size();b++){ Stringtemp2=(String)listFollowSetApart[b].get(0); if(heihei.equals(temp2)){//findit,thenstartcopying.for(intmama=1;mama<listFollowSetApart[b].size();mama++){Stringtemp3=(String)listFollowSetApart[b].get(mama); if(!listFollowSetApart[a].contains(temp3)){ listFollowSetApart[a].add(temp3.trim()); isChanged[i]=true; } } } } break; } } } } }//endoffor }//endofelse }//endoffor //Judgewhethershouldrunthe"while"loop. for(intaaaa=0;aaaa<this.vectorGrammar.size();aaaa++){ if(isChanged[aaaa]){ changed=true; break; } else{ changed=false; } } }//endofthewhileloop. }//endofthefunction.packagecminus;/**packagecminus;/***Class-name:ParsingTable*功能：構(gòu)造文法的分析表，并將其用一定的數(shù)據(jù)結(jié)構(gòu)保存。*@authorAdministrator**/importjava.util.*;importjava.io.*;publicclassParsingTableextendsFollowSet{ //由于程序太大，其他函數(shù)和類屬性的定義省略，這里只給出構(gòu)建分析表的主函數(shù)constructParsingTable() publicvoidconstructParsingTable(){ for(inti=0;i<this.listGrammar.length;i++){ //對(duì)每個(gè)候選構(gòu)造分析表的元素 Stringelement=""; for(intk=0;k<this.listGrammar[i].size();k++){ if(k==1){ element+="→"; element+=(String)this.listGrammar[i].get(k)+""; } else{ element+=(String)this.listGrammar[i].get(k)+""; } } //對(duì)由此候選求出的first集合 Stringnonterminal=(String)this.listFirstSetApart[i].get(0