first集和follow集生成算法模擬.doc

課程設(shè)計(論文)任務(wù)書 軟 件 學 院 學院 軟件測試 專業(yè) 1 班 一、課程設(shè)計(論文)題目 first集和follow集生成算法模擬 二、課程設(shè)計(論文)工作自 2015 年 6 月 16 日起至 2013 年 6 月 19 日止。三、課程設(shè)計(論文) 地點: 軟 件 學 院 實 訓 中 心 四、課程設(shè)計(論文)內(nèi)容要求：1本課程設(shè)計的目的進一步培養(yǎng)學生編譯器設(shè)計的思想，加深對編譯原理和應(yīng)用程序的理解，針對編譯過程的重點和難點內(nèi)容進行編程，獨立完成有一定工作量的程序設(shè)計任務(wù)，同時，強調(diào)好的程序設(shè)計風格，并綜合使用程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)和編譯原理的知識, 熟悉使用開發(fā)工具VC /JAVA/C#/.NET 。2課程設(shè)計的任務(wù)及要求1）課程設(shè)計任務(wù)：設(shè)計一個由正規(guī)文法生成First集和Follow集并進行簡化的算法動態(tài)模擬。2）創(chuàng)新要求：動態(tài)模擬算法的基本功能是：（） 輸入一個文法（） 輸出由文法G構(gòu)造的FIRST集算法（） 輸出FIRST算法（） 輸出由文法G構(gòu)造的FOLLOW集算法（） 輸出FOLLOW集3）課程設(shè)計論文編寫要求（1）課程設(shè)計任務(wù)及要求（2）設(shè)計思路-工作原理、功能規(guī)劃（3）詳細設(shè)計-數(shù)據(jù)分析、算法思路、功能實現(xiàn)（含程序流程圖、主要代碼及注釋）、界面等。（4）運行調(diào)試與分析討論-給出運行屏幕截圖，分析運行結(jié)果，有何改進想法等。（5）設(shè)計體會與小結(jié)-設(shè)計遇到的問題及解決辦法，通過設(shè)計學到了哪些新知識，鞏固了哪些知識，有哪些提高。（6）報告按規(guī)定排版打印，要求裝訂平整，否則要求返工；（7）課設(shè)報告的裝訂順序如下：封面-任務(wù)書-中文摘要-目錄-正文-附錄(代碼及相關(guān)圖片)（8）嚴禁抄襲，如有發(fā)現(xiàn)，按不及格處理。4）課程設(shè)計評分標準： （1）學習態(tài)度：20分；（2）系統(tǒng)設(shè)計：20分；（3）編程調(diào)試：20分；（4）回答問題：20分；（5）論文撰寫：20分。5）參考文獻：（1）張素琴，呂映芝. 編譯原理M., 清華大學出版社（2）蔣立源、康慕寧等，編譯原理（第2版）M，西安：西北工業(yè)大學出版社6）課程設(shè)計進度安排1準備階段（4學時）：選擇設(shè)計題目、了解設(shè)計目的要求、查閱相關(guān)資料2程序模塊設(shè)計分析階段（4學時）：程序總體設(shè)計、詳細設(shè)計3代碼編寫調(diào)試階段（8學時）：程序模塊代碼編寫、調(diào)試、測試4撰寫論文階段（4學時）：總結(jié)課程設(shè)計任務(wù)和設(shè)計內(nèi)容，撰寫課程設(shè)計論文學生簽名： 2015 年 6 月 19 日課程設(shè)計(論文)評審意見（1）學習態(tài)度（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （2）系統(tǒng)設(shè)計（20分）：優(yōu)（ ）、良（）、中（）、一般（）、差（）； （3）編程調(diào)試（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）回答問題（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）論文撰寫（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； 評閱人： 職稱： 講師 2015 年 6 月 19 日中文摘要隨著計算機科學的飛速發(fā)展，形式語言與自動機理論和方法研究也越來越收到人們的重視，但前者已經(jīng)成為計算機科學的理論基礎(chǔ)。此次的課程設(shè)計主要任務(wù)是研究自動機在編譯方面的應(yīng)用，并將重點放在求FIRST集和FOLLOW集。根據(jù)構(gòu)造FIRST集的算法和FOLLOW集的算法，編寫一個程序，程序具有通用性，即編制的愈發(fā)程序能夠適用于不同的文法?；舅枷朊枋觯ㄟ^對輸入的文法進行判斷，進而根據(jù)構(gòu)造的FIRST集和FOLLOW集的算法。并把計算所得的FIRST集和FOLLOW集輸出。構(gòu)造FIRST集的算法和FOLLOW集的算法的核心算法教材上已經(jīng)給出了，因此要做的事只是將他們實現(xiàn)。關(guān)鍵字：FIRST集，F(xiàn)OLLOW集，算法。目錄一、課程設(shè)計任務(wù)及要求1二、需求分析2三、設(shè)計思路3四、詳細設(shè)計7五、運行調(diào)試與分析討論8六、設(shè)計體會與小結(jié)10七、參考文獻11八、附錄.11一、課程設(shè)計任務(wù)及要求1.任務(wù)：設(shè)計一個由正規(guī)文法生成First集和Follow集并進行簡化的算法動態(tài)模擬。First集和Follow集生成模擬算法的基本功能：（1） 輸入一個文法G（2） 輸入由文法G構(gòu)造First集的算法（3） 輸出First集（4） 輸入由文法構(gòu)造Follow集的算法（5） 輸出Follow集2. 實驗目的：輸入：任意的上下文無關(guān)文法。輸出：所輸入的上下文無關(guān)文法一切非終結(jié)符的first集合和follow 集合。3.設(shè)文法GS（VN，VT，P，S），則首字符集為： FIRST（）a | a，aVT，,V *。若，F(xiàn)IRST（）。由定義可以看出，F(xiàn)IRST（）是指符號串能夠推導出的所有符號串中處于串首的終結(jié)符號組成的集合。所以FIRST集也稱為首符號集。設(shè)x1x2xn，F(xiàn)IRST（）可按下列方法求得：令FIRST（），i1；（1） 若xiVT，則xiFIRST（）；（2） 若xiVN； 若FIRST（xi），則FIRST（xi）FIRST（）； 若FIRST（xi），則FIRST（xi）FIRST（）；（3） ii+1，重復（1）、（2），直到xiVT，（i2，3，n）或xiVN且若FIRST（xi）或in為止。當一個文法中存在產(chǎn)生式時，例如，存在A，只有知道哪些符號可以合法地出現(xiàn)在非終結(jié)符A之后，才能知道是否選擇A產(chǎn)生式。這些合法地出現(xiàn)在非終結(jié)符A之后的符號組成的集合被稱為FOLLOW集合。下面我們給出文法的FOLLOW集的定義。設(shè)文法GS（VN，VT，P，S），則 FOLLOW（A）a | S Aa ，aVT。若SA，#FOLLOW（A）。由定義可以看出，F(xiàn)OLLOW（A）是指在文法GS的所有句型中，緊跟在非終結(jié)符A后的終結(jié)符號的集合。FOLLOW集可按下列方法求得：（1） 對于文法GS的開始符號S，有#FOLLOW（S）；（2） 若文法GS中有形如BxAy的規(guī)則，其中x，yV *，則FIRST（y）FOLLOW（A）；（3） 若文法GS中有形如BxA的規(guī)則，或形如BxAy的規(guī)則且FIRST（y），其中x，yV *，則FOLLOW（B）FOLLOW（A）；3. 實驗內(nèi)容：計算FIRST集和FOLLOW集4.二、需求分析1.基本要求： 動態(tài)模擬算法的基本功能是：（1） 輸入一個文法G；（2） 輸出由文法G構(gòu)造FIRST集的算法；（3） 輸出First集；i)(*+F的first集T的first集E的first集111111111（4） 輸出由文法G構(gòu)造FOLLOW集的算法；（5） 輸出FOLLOW集。2.測試數(shù)據(jù)：輸入文法E：E TEE +TE|T FTT *FT|F-(E)|i3. 實現(xiàn)提示：用數(shù)據(jù)庫存儲多行文法，用LIST控件顯示算法，用GRID類依據(jù)算法進行作圖。并實現(xiàn)算法與生成過程的關(guān)聯(lián)。三、設(shè)計思路1.識別終結(jié)符集和非終結(jié)符集 開始 結(jié)束計算產(chǎn)生式的總數(shù)N輸入要分析的文法G 開始 開始 輸入n=0識別所有符號集合Z讀取一條產(chǎn)生式n=n+1終結(jié)符集合Vt=Z - Vn識別產(chǎn)生式左部的字符V并添加到非終結(jié)符集合Vn輸出Vt Nn Y 結(jié)束 N輸出Vn 識別終結(jié)符集 結(jié)束 識別非終結(jié)符集 2. 計算所有非終結(jié)符的First集 開始讀取Vn中的一個非終結(jié)符V從語法G中查找左部是V的所有產(chǎn)生式 產(chǎn)生式的右部第一個符號V*是終結(jié)符或者V*取出其中的一條產(chǎn)生式 N V*右部的第一個非終結(jié)符V可以推導 Y Y N將該終結(jié)符加入V的First集中還有未計算的非終結(jié)符 結(jié)束3. 計算所有非終結(jié)符的Follow集 開始讀取Vn中的一個非終結(jié)符V從語法G中查找左部是V的所有產(chǎn)生式V的后一個字符V*為終結(jié)符V是最后一個字符 N Y N添加V*到V的Follow集中添加#到V的Follow集中 Y 是否遍歷完所有右部含有的產(chǎn)生式 添加V*的First集到V的Follow集中 有未求過的非終結(jié)符 完成四、詳細設(shè)計 開始1.操作界面的控制流圖輸入文法計算所有的非終結(jié)符Vn和終結(jié)符Vt并顯示計算所有非終結(jié)符的First集和Follow集并顯示 結(jié)束2. 具體設(shè)計通過分析輸入的文法，分析出文法腫的非終結(jié)符和終結(jié)符，然后計算出每個非終結(jié)符的FIRST集和FOLLOW集。在輸出的結(jié)果上應(yīng)該顯示文法中的非終結(jié)符和終結(jié)符，F(xiàn)IRST集和FOLLOW集表格。根據(jù)表格中的每個非終結(jié)符后面的表示的是：相對應(yīng)的終結(jié)符是屬于該非終結(jié)符的。五、運行調(diào)試與分析討論1.運行程序2.輸入文法3.輸出非終結(jié)符和終結(jié)符4.計算First集并輸出計算Follow集并輸出六、設(shè)計體會與小結(jié)這次的編譯原理的課程設(shè)計歷時兩天，進過不斷的查看課本從網(wǎng)上差資料解決問題，讓我對文法的FIRST集和FOLLOW集有了更多的了解。雖然做課程設(shè)計是一個比較辛苦的過程，但是從它的過程中我們還是可以學到很多東西的，比如思維的方式，鍛煉自己的耐心，寫文檔時的邏輯能力。在寫課設(shè)的過程中遇到了以下的問題：1 終結(jié)符 V和V，多了個帶 的終結(jié)符，但是它在處理的時候只能當一個符號來識別，而用程序設(shè)計語言表示時它能表示成兩個字符，如果處理不當?shù)脑?，V就可能被認為是終結(jié)符號V和非終結(jié)符。這無疑給處理過程添加了難度。2 還有一些自認為理所當然能實現(xiàn)的，卻實際并不可取的方法。如：本來JAVA API有個方法String.split(String s);用于以s 為分割字符，將指定的字符分成字符數(shù)組。但是s 為括號時（無論左右括號，大小括號，方框括號），都不能分割，并且拋異常。這是個很難理解的問題。迫不得已，我不得不想其他的方法來實現(xiàn)分割算法。3 再有就是對編譯原理中First Follow算法設(shè)計時，采取何種策略效率最高的問題。最后我想到了用遞歸方式。下面總結(jié)此次課程設(shè)計的一些收獲：1.對程序設(shè)計理解，算法的設(shè)計，有了進一不的提高。 2.對程序調(diào)試的技巧收獲不小。因為該程序主要是算法研究，所以程序分支較復雜。斷點調(diào)試是必不可缺并且很實用的工作。3對程序到軟件過程的理解。這次也是我第一次將自己做的程序制作成一個可自定義安裝過程的小軟件。從而將程序的運行與IDE脫離開來。4毫無疑問，就是對編譯原理的理解。能夠很好地理解程序設(shè)計與編譯原理的關(guān)系。七、參考文獻1 張素琴.編譯原理. 北京:清華大學出版社,20052 付京周.JAVA程序設(shè)計語言. 北京:人民郵電出版社,20078、 附錄/求VN和VTvoid VNVT(STR *p) int i,j; for(i=0;iN;i+) for(j=0;j=A&pi.leftj100) Vn+=pi.leftj; else if(Vt.find(pi.leftj)100) Vt +=pi.leftj; for(j=0;j=A&pi.rightj100) Vt +=pi.rightj; else if(Vn.find(pi.rightj)100) Vn+=pi.rightj; void getlr(STR *p,int i) int j; for(j=0;j) pi.left=strings.substr(0,j); pi.right=strings.substr(j+2,strings.length()-j); /對每個文法符號求first集string Letter_First(STR *p,char ch)int t;if(!(Vt.find(ch)100)firstVt.find(ch)=ch;return firstVt.find(ch)-1;if(!(Vn.find(ch)100)for(int i=0;i100) if(FirstVn.find(ch).find(pi.right0)100) FirstVn.find(ch)+=pi.right0; if(pi.right0=*) if(FirstVn.find(ch).find(*)100) FirstVn.find(ch)+=*; if(!(Vn.find(pi.right0)100) if(pi.right.length()=1) string ff; ff=Letter_First(p,pi.right0); for(int i_i=0;i_i100) FirstVn.find(ch)+=ffi_i; else for(int j=0;j100)&(j+1)pi.right.length() sort(TT.begin(),TT.end(); string tt; for(int t=1;tTT.length();t+) tt+=TTt; TT=tt; tt=; for(t=0;t100) FirstVn.find(ch)+=TTt; else for(t=0;t100) FirstVn.find(ch)+=TTt; break; return FirstVn.find(ch);/ 求每個非終結(jié)符的Follow集string Letter_Follow(STR *p,char ch)int t,k;NONEVn.find(ch)+;if(NONEVn.find(ch)=2)NONEVn.find(ch)=0;return FollowVn.find(ch);for(int i=0;iN;i+)for(int j=0;jpi.righ