張增明-0543042176-編譯原理課程設(shè)計-副本

學(xué)生：張增明學(xué)號：0543042176課程：編譯原理與實踐教師：楊秋輝PAGE46-編譯原理課程設(shè)計報告課題名稱：c-minus編譯器__________提交文檔學(xué)生姓名：張增明提交文檔學(xué)生學(xué)號：0543042176同組成員名單：無指導(dǎo)教師姓名：楊秋輝指導(dǎo)教師評閱成績：指導(dǎo)教師評閱意見：..提交報告時間：2007年12月4日目錄編譯原理課程設(shè)計報告 11. 課程設(shè)計目標(biāo) 32. 分析與設(shè)計 32.1程序設(shè)計思路 32.2系統(tǒng)體系結(jié)構(gòu) 42.3數(shù)據(jù)結(jié)構(gòu)設(shè)計 52.3.1各數(shù)據(jù)結(jié)構(gòu)使用介紹 52.3.2程序中各數(shù)據(jù)結(jié)構(gòu)的聲明 72.4設(shè)計類 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程序測試流程設(shè)計 143. 程序代碼實現(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. 測試結(jié)果 394.1測試數(shù)據(jù)選擇 394.2測試結(jié)果分析 415. 總結(jié) 465.1收獲 465.2特色 465.3不足 461. 課程設(shè)計目標(biāo)本課程設(shè)計是實現(xiàn)c-minus編譯器的前兩個部分，即詞法分析和語法分析。要求能夠掌握編譯原理的基本理論,，理解了編譯程序的基本結(jié)構(gòu)，掌握了編譯各階段的基本理論和技術(shù)，掌握了編譯程序設(shè)計的基本理論和步驟.，增強編寫和調(diào)試高級語言源程序的能力。并且能夠掌握詞法分析、語法分析的基本概念和實現(xiàn)方法，能夠用給定的c-minus語言文法變換成可以進(jìn)行LL(1)分析的LL(1)文法，并自動由程序生成其對應(yīng)的First集和Follow集，以及分析表，并且能夠?qū)⒔o定的c-minus源程序進(jìn)行詞法和語法編譯，并最終生成其對應(yīng)的分析樹。2. 分析與設(shè)計2.1程序設(shè)計思路系統(tǒng)采用面向?qū)ο蟮脑O(shè)計思想，用Java語言實現(xiàn)。整個系統(tǒng)的實現(xiàn)分三個步驟：詞法分析、文法轉(zhuǎn)換和語法分析。詞法分析所謂詞法分析就是將用C-minus語言編寫好的源程序解析成一個個編譯器可以識別的tokens，這部分工作是由ParserGenerator軟件實現(xiàn)的，我所做的只是編寫ParserGenerator的輸入文件(見3.1節(jié)C-minus.l)，然后通過ParserGenerator生成具體的Java語言的詞法分析器。文法轉(zhuǎn)換文法轉(zhuǎn)換是將所給的C-minus文法轉(zhuǎn)化為可以進(jìn)行LL(1)分析的LL(1)文法，這部分的轉(zhuǎn)換分為兩個步驟，第一步是將原來非LL(1)文法中的直接的左遞歸和左因子轉(zhuǎn)化為對應(yīng)的LL(1)文法的形式，第二個步驟是在第一個步驟的基礎(chǔ)之上將間接的左遞歸和左因子轉(zhuǎn)化，并最終形成標(biāo)準(zhǔn)的LL(1)文法。本部分手工完成并由程序檢驗是否變換成功。語法分析語法分析第一步是將給定的LL(1)文法通過求First集和Follow集，并最終形成文法的分析表的過程，第二步結(jié)合詞法分析產(chǎn)生的token，并對照分析表建立分析樹，這是本次課程設(shè)計的最后一步。本部分還會判斷輸入的文法文件是否有語法錯誤，比如出現(xiàn)了一個既不是非終結(jié)符號又不是終結(jié)符號的符號等。以上三個過程的形象化表示和其之間的關(guān)系見圖2-1.掃描器掃描器Token文件Tokentype文件1.詞法分析3.語法分析求First集求Follow集構(gòu)建分析表初始文法消除直接的左遞歸和左因子LL(1)文法2.文法變換消除間接的左遞歸和左因子C-minus源程序執(zhí)行分析過程構(gòu)建分析樹圖2-SEQ圖_2-\*ARABIC1詞法分析、文法轉(zhuǎn)換、語法分析的過程和其之間關(guān)系示意圖2.2系統(tǒng)體系結(jié)構(gòu) 本系統(tǒng)采用面向?qū)ο蟮乃枷脒M(jìn)行設(shè)計和實現(xiàn)，如2.1節(jié)中闡述的那樣，系統(tǒng)的實現(xiàn)分為三個部分，見圖2-1. 本系統(tǒng)在實現(xiàn)過程中一共設(shè)計了十個類，各個類的名稱和作用見表2-1.表2-SEQ表_2-\*ARABIC1系統(tǒng)中各個類的說明類名功能備注TokenType提供文法中所有的終結(jié)符合的定義。是接口TokenProcess提供對終結(jié)符合的處理功能，包括將int型的終結(jié)符號轉(zhuǎn)化為String型，以及判斷一個String型的符號是否終結(jié)符號。Parser將輸入的源程序轉(zhuǎn)化為tokens，并分為token和tokentype分別存放在兩個文件中，以便使用。由ParserGenerator通過“C-minus.l”輸入文件自動生成。FirstSet負(fù)責(zé)將文法轉(zhuǎn)入數(shù)據(jù)結(jié)構(gòu)(見2.3節(jié)數(shù)據(jù)結(jié)構(gòu)設(shè)計)，并且判斷文法是否有語法錯誤，以及求文法的First集。FollowSet負(fù)責(zé)求文法的Follow集合。ParsingTable負(fù)責(zé)構(gòu)建文法的分析表ParsingTree負(fù)責(zé)生成源程序?qū)?yīng)于文法的分析樹。ParsingTreeNodeParsingTree的內(nèi)部類，負(fù)責(zé)定義分析樹的節(jié)點。TreeFrame負(fù)責(zé)將ParsingTree中產(chǎn)生的分析樹用JTree的Swing控件形象化顯示出來。Controller系統(tǒng)中的主類，負(fù)責(zé)控制整個流程。 系統(tǒng)中各個類之間的關(guān)系見圖2-2(圖形制作：RationalRose2003)。圖2-SEQ圖_2-\*ARABIC2系統(tǒng)中類關(guān)系圖2.3數(shù)據(jù)結(jié)構(gòu)設(shè)計2.3.1各數(shù)據(jù)結(jié)構(gòu)使用介紹本系統(tǒng)中所設(shè)計的數(shù)據(jù)結(jié)構(gòu)主要是鏈表數(shù)組和向量。1.將文法裝入數(shù)據(jù)結(jié)構(gòu)文法的存儲涉及到了六個數(shù)據(jù)結(jié)構(gòu)，分別是：vectorGrammar --將文法按照候選分開存儲的向量vectorGrammarTogether --將文法按照非終結(jié)符號存儲的向量listGrammar[] --將文法按照候選分開存儲的鏈表數(shù)組listNonTerminals --存儲所有的非終結(jié)符號的鏈表listTerminals --存儲所有終結(jié)符號的鏈表listNonTerminalApartly --按照候選存儲所有非終結(jié)符號的鏈表由于數(shù)據(jù)結(jié)構(gòu)太多，不好一一詳述，下面介紹什么是按照候選的存儲方式：系統(tǒng)實現(xiàn)過程中首先將文法按照候選分開寫，分別都存放在listGrammar數(shù)組的鏈表元素中。這一過程示意如下： 首先對于下面的一行文法：declaration-1→var-declaration-1|(params)compound-stmt 將其按照候選分開寫，如下： declaration-1→var-declaration-1 declaration-1→(params)compound-stmt 可以看出一行文法變成了兩行，然后將這兩行文法存儲在兩個鏈表中，即鏈表數(shù)組的兩個連續(xù)的元素中，如表2-2所示：表2-SEQ表_2-\*ARABIC2文法入鏈表示意表鏈表元素0元素1元素2元素3listGrammar[i]var-declaration-1listGrammar[i+1](params)compound-stmt 然后將每個鏈表裝入Vector中，形成一個Vector對象，如表2-3所示：表2-SEQ表_2-\*ARABIC3文法向量示意表Vector對象元素0元素1元素2……vectorGrammarlistGrammar[0]listGrammar[1]listGrammar[2]…… 2.First集合的存儲First集合的存儲涉及到了四個數(shù)據(jù)結(jié)構(gòu)，分別是：vectorFirstSetApart --按照候選存儲First集合鏈表的向量vectorFirstSet --按照非終結(jié)符號存儲First集合鏈表的向量listFirstSetApart [] --按照候選存儲First集合的鏈表數(shù)組listFirstSet[] --按照非終結(jié)符號存儲First集合的鏈表數(shù)組這四個數(shù)據(jù)結(jié)構(gòu)共同協(xié)作，實現(xiàn)了系統(tǒng)中對First集合的存儲和使用工作。前兩個向量對象的存儲機制與表2-3中的存儲機制相似，這里不再贅述，下面重點介紹后兩個數(shù)據(jù)結(jié)構(gòu)的存儲機制：還是對于本節(jié)第一部分的文法來說：declaration-1→var-declaration-1|(params)compound-stmt 將其按照候選分開寫，如下： declaration-1→var-declaration-1 declaration-1→(params)compound-stmt分別對每個候選求First集合，假設(shè)得到的結(jié)果如下： First(declaration-1)={(,ID,NUM,int} First(declaration-1)={if,else,while}然后將這兩個First集合裝入listFirstSetApart []數(shù)組中的兩個連續(xù)的元素中，如表2-4所示：表2-SEQ表_2-\*ARABIC4按候選存儲的First集合示意鏈表元素0元素1元素2元素3ListFirstSetApart[i](IDNUMIntlistFirstSetApart[i+1]IfElsewhile然后需要構(gòu)建按照非終結(jié)符號存儲的First集合，即將上面的數(shù)組中類似以上的兩個元素合并起來，之后的存儲機制如表2-5所示：表2-SEQ表_2-\*ARABIC5按非終結(jié)符號存儲的First集合示意鏈表元素0元素1元素2元素3元素4元素5元素6listFirstSet[k](IDNUMIntIfElsewhile 之所以要選擇這樣的存儲方式是為了系統(tǒng)的需要，具體請見2.4節(jié)設(shè)計類。 3.Follow集合的存儲 Follow集合的存儲涉及的數(shù)據(jù)結(jié)構(gòu)有以下四個：vectorFollowSetvectorFollowSetApartlistFollowSet[]listFollowSetApart[]Follow集合的存儲方式非常類似于First集合的存儲方式，這里就不再闡述了。 4.分析表的存儲分析表的存儲涉及的數(shù)據(jù)結(jié)構(gòu)只有一個：String[][]parsingTable很明顯，這是一個字符串形式的二維數(shù)組，元素通過其在listNonTerminals和listTerminals(見1.將文法裝入數(shù)據(jù)結(jié)構(gòu))中的位置確定其在分析表中的位置。 5.分析樹的存儲 分析樹的存儲涉及到的數(shù)據(jù)結(jié)構(gòu)只有一個：ParsingTreeNoderoot;這是ParsingTreeNode類的實例，這個類中有指向自己的元素數(shù)組(見2.4.6節(jié))2.3.2程序中各數(shù)據(jù)結(jié)構(gòu)的聲明 本系統(tǒng)中各數(shù)據(jù)結(jié)構(gòu)的聲明是分布在不同的文件中的，具體見圖2-3、圖2-4、圖2-5及圖2-6中的說明。publicpublicVectorvectorGrammar;//格式化存儲文法結(jié)構(gòu)的向量publicVectorvectorGrammarTogether;//格式化存儲文法結(jié)構(gòu)的向量publicVectorvectorFirstSetApart;//存儲按照候選分開的各個非終結(jié)符的first集合publicVectorvectorFirstSet;//存儲每個非終結(jié)符的first集合，按照非終結(jié)符分類publicLinkedListlistNonTerminals;//存儲非終結(jié)字符的鏈表對象publicLinkedListlistGrammar[];//裝有每條文法的鏈表數(shù)組publicLinkedListlistFirstSetApart[];//按候選裝每個非終結(jié)符號的First集鏈表數(shù)組publicLinkedListlistFirstSet[];//按非終結(jié)符號裝每個符號的First集的鏈表數(shù)組圖2-SEQ圖_2-\*ARABIC3FirstSet類中涉及的數(shù)據(jù)結(jié)構(gòu) //存儲follow集的Vector對象publicVectorvectorFollowSet;publicVectorvectorFollowSetApart; //暫存follow集的鏈表數(shù)組publicLinkedListlistFollowSet[];//按照非終結(jié)字符種類存放publicLinkedListlistFollowSetApart[];//按照各個非終結(jié)字符的候選來存放圖2-SEQ圖_2-\*ARABIC4FollowSet類中涉及的數(shù)據(jù)結(jié)構(gòu)publicpublicLinkedListlistTerminals;//存儲終結(jié)符號的鏈表publicString[][]parsingTable;//String型的二維數(shù)組，用來存儲分析表publicLinkedListlistNonTerminalApartly;//用來將非終結(jié)符號按候選分開存放的鏈表圖2-SEQ圖_2-\*ARABIC5ParsingTable類中涉及的數(shù)據(jù)結(jié)構(gòu)publicpublicParsingTreeNoderoot;圖2-SEQ圖_2-\*ARABIC6ParsingTree類中涉及到的數(shù)據(jù)結(jié)構(gòu)2.4設(shè)計類2.4.1TokenType.java此類是個接口，用來提供文法中所有的終結(jié)符合的定義，其實現(xiàn)很簡單，如下所示：packagepackagecminus;publicinterfaceTokenType{ publicfinalintENDFILE=0; //endfile publicfinalintELSE=1; //else //省略}圖2-SEQ圖_2-\*ARABIC7TokenType接口2.4.2TokenProcess.java本類實現(xiàn)接口TokenType，提供對終結(jié)符合的處理功能，包括將int型的終結(jié)符號轉(zhuǎn)化為String型，以及判斷一個String型的符號是否終結(jié)符號，在多個類中都有其實例的定義。本類的類結(jié)構(gòu)圖如圖2-8所示。圖2-SEQ圖_2-\*ARABIC8TokenProcess類結(jié)構(gòu)圖其中：tokenToString函數(shù)用來將int型的終結(jié)符號轉(zhuǎn)化為String型，isTerminal函數(shù)用來判斷一個String型的符號是否終結(jié)符號。2.4.3FirstSet.java本類負(fù)責(zé)將文法轉(zhuǎn)入數(shù)據(jù)結(jié)構(gòu)，并且判斷文法是否有語法錯誤，以及求文法的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é)點。圖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控件形象化顯示出來。圖2-SEQ圖_2-\*ARABIC14TreeFrame類結(jié)構(gòu)圖2.4.9本類系統(tǒng)中的主類，負(fù)責(zé)控制整個流程。圖2-SEQ圖_2-\*ARABIC15Controller類結(jié)構(gòu)圖2.5重要函數(shù)流程圖2.5.1FirstSet類getFirstSet()函數(shù)YYNYNYYNN開始取一行文法L得到L中第一個符號A得到下一個符號BB是終結(jié)符號加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中第一個符號AL中有兩個Token得到下兩個符號B和C得到下一個符號BB為終結(jié)符加Follow(A)給Follow(B)B為終結(jié)符號得到從C開始直到L最后一個字符的First集S將S-ε加入Follow(B)ε∈S將Follow(A)加入Follow(B)C是文法最后一個字符將Follow(A)加入Follow(C)圖2-SEQ圖_2-\*ARABIC17求Follow集程序流程圖2.6程序測試流程設(shè)計Token文件Token文件輸入源程序Tokentype文件輸入文法文件First集測試Follow集測試分析表測試分析樹測試詞法分析測試語法分析測試圖2-SEQ圖_2-\*ARABIC18系統(tǒng)測試流程圖3. 程序代碼實現(xiàn)3.1C-minus.l/************************************************//************************************************//*Inputfileforlexforc-minus *//*Author:張增明(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("文件無法找到:"+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ù)，為了測試時的方便而加上的，可以刪去。 Parserparser=newParser(); try{ parser.setSourceFile("zhang.cm"); parser.getToken(); }catch(Exceptione){ System.err.println("Scanningerror:"+e.getMessage()); } }}packagecminus;/**packagecminus;/***Interfaceforutilityusing,*allreservedwordsandsymbolaredefinitehere.*@author張增明(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 對應(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ù)：判斷某個字符是否是終結(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)文法。* 同時得到文法中所有非終結(jié)符號的個數(shù)并且格式化存儲之。*@authorAdministrator*/importjava.io.*;importjava.util.*;publicclassFirstSet{ //由于程序太大，其他函數(shù)和類屬性的定義省略，這里只給出求First集的函數(shù)getFirstSet() publicvoidgetFirstSet(){ intfirst=0; booleanchanged=true; booleanisChanged[]=newboolean[vectorGrammar.size()]; Stringsymbol="";//產(chǎn)生式中第一個字符 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)包含空字 //如果得到的每行的第一個值是非終結(jié)符號，這點肯定滿足 if(!tokenPro.isTerminal(symbol=(String)listGrammar[i].get(0))){ symbol2=(String)listGrammar[i].get(k);//產(chǎn)生式中第二個字符 //如果下一個符號是終結(jié)字符，直接加到當(dāng)前鏈表的first集合中 if(tokenPro.isTerminal(symbol2)){ isToJudgeContainsEmpty=false; if(!listFirstSetApart[i].contains(symbol2)){ listFirstSetApart[i].add(symbol2.trim()); isChanged[i]=true;//改變了 } }else{ //如果第二個不是終結(jié)字符，那么就找到此符號的first集， //將其中的除empty外的所有符號加入到當(dāng)前非終結(jié)符號的first集合中 //找到以該非終結(jié)字符為首的鏈表 for(inta=0;a<vectorGrammar.size();a++){ Stringsymbol3=(String)listGrammar[a].get(0); if(symbol3.equals(symbol2)){//二者相等，說明找到了 //找到之后將其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)){//二者相等，說明找到了 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()]; //初始化各個listFollowSetApart數(shù)組，按照候選存儲各個非終結(jié)符號的Followset try{ for(inti=0;i<vectorGrammar.size();i++) listFollowSetApart[i]=newLinkedList(); for(inti=0;i<vectorGrammar.size();i++){ //每個鏈表都存儲了一個非終結(jié)符號作為標(biāo)識 listFollowSetApart[i].add(listGrammar[i].get(0)); } }catch(Exceptione){ System.out.println("初始化follow集數(shù)組錯誤： "+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個數(shù)為2 if(listGrammar[i].size()==2){ //如果第二個token不是終結(jié)符號，則將第一個的follow集給第二個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的個數(shù)大于二 else{ for(intj=1;j<listGrammar[i].size()-1;j++){ inttempflag=j;//臨時標(biāo)記變量，用來指示臨時鏈表從何處(哪個token)開始構(gòu)建 //一次獲取兩個token Stringstr1=(String)listGrammar[i].get(j); //此次得到str2為了判斷結(jié)尾時使用 Stringstr2=(String)listGrammar[i].get(j+1); if(!tokenPro.isTerminal(str1)){ //將str2str3...的first集中不是empty的元素給str1的follow集 //通過將上面的first集合求出裝載在一個臨時的鏈表里，然后復(fù)制這個鏈表來實現(xiàn)。 LinkedListtmpList=newLinkedList();//存儲first集的臨時鏈表 Stringfirst=(String)listGrammar[i].get(0);//獲取第一個token //構(gòu)建這個臨時鏈表，將str2str3...的first集裝入臨時鏈表 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"); } //將臨時鏈表中的除了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)記臨時鏈表中是否有empty的變量。 if(tmpList.contains("EMPTY")){ tempboolean=true; } tmpList.clear(); //如果臨時鏈表中有EMPTY，則將第一個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; } } } } //如果一個token是這行的最后一個token，則將第一個token的follow集拷貝到這個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++){ //對每個候選構(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)+""; } } //對由此候選求出的first集合 Stringnonterminal=(String)this.listFirstSetApart[i].get(0