first集和follow集生成算法模擬

1、編譯原理課設(shè)課程設(shè)計(論文)任務(wù)書 軟 件 學(xué) 院 學(xué)院 軟件測試 專業(yè) 1 班 一、課程設(shè)計(論文)題目 first集和follow集生成算法模擬 二、課程設(shè)計(論文)工作自 2021 年 6 月 16 日起至 2021 年 6 月 19 日止。三、課程設(shè)計(論文) 地點(diǎn): 軟 件 學(xué) 院 實(shí) 訓(xùn) 中 心 四、課程設(shè)計(論文)內(nèi)容要求：1本課程設(shè)計的目的進(jìn)一步培養(yǎng)學(xué)生編譯器設(shè)計的思想，加深對編譯原理和應(yīng)用程序的理解，針對編譯過程的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行編程，獨(dú)立完成有一定工作量的程序設(shè)計任務(wù)，同時，強(qiáng)調(diào)好的程序設(shè)計風(fēng)格，并綜合使用程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)和編譯原理的知識, 熟悉使用開發(fā)工具VC /

2、JAVA/C#/.NET 。2課程設(shè)計的任務(wù)及要求1課程設(shè)計任務(wù)：設(shè)計一個由正規(guī)文法生成First集和Follow集并進(jìn)行簡化的算法動態(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詳細(xì)設(shè)計-數(shù)據(jù)分析、算法思路、功能實(shí)現(xiàn)含程序流程圖、主要代碼及注釋、界面等。4運(yùn)行調(diào)試與分析討論-給出運(yùn)行屏幕截圖，分析運(yùn)行結(jié)果，有何改良想法等。5設(shè)計體會與小結(jié)-設(shè)計遇到的問題及解決方法，通過設(shè)計

3、學(xué)到了哪些新知識，穩(wěn)固了哪些知識，有哪些提高。6報告按規(guī)定排版打印，要求裝訂平整，否那么要求返工；7課設(shè)報告的裝訂順序如下：封面-任務(wù)書-中文摘要-目錄-正文-附錄(代碼及相關(guān)圖片)8嚴(yán)禁抄襲，如有發(fā)現(xiàn)，按不及格處理。4課程設(shè)計評分標(biāo)準(zhǔn)： 1學(xué)習(xí)態(tài)度：20分；2系統(tǒng)設(shè)計：20分；3編程調(diào)試：20分；4答復(fù)以下問題：20分；5論文撰寫：20分。5參考文獻(xiàn)：1張素琴，呂映芝. 編譯原理M., 清華大學(xué)出版社2蔣立源、康慕寧等，編譯原理第2版M，西安：西北工業(yè)大學(xué)出版社6課程設(shè)計進(jìn)度安排1準(zhǔn)備階段4學(xué)時：選擇設(shè)計題目、了解設(shè)計目的要求、查閱相關(guān)資料2程序模塊設(shè)計分析階段4學(xué)時：程序總體設(shè)計、詳細(xì)設(shè)計

4、3代碼編寫調(diào)試階段8學(xué)時：程序模塊代碼編寫、調(diào)試、測試4撰寫論文階段4學(xué)時：總結(jié)課程設(shè)計任務(wù)和設(shè)計內(nèi)容，撰寫課程設(shè)計論文學(xué)生簽名： 2021 年 6 月 19 日課程設(shè)計(論文)評審意見1學(xué)習(xí)態(tài)度20分：優(yōu)、良、中、一般、差； 2系統(tǒng)設(shè)計20分：優(yōu) 、良、中、一般、差； 3編程調(diào)試20分：優(yōu)、良、中、一般、差；4答復(fù)以下問題20分：優(yōu)、良、中、一般、差；5論文撰寫20分：優(yōu)、良、中、一般、差； 評閱人： 職稱： 講師 2021 年 6 月 19 日中文摘要隨著計算機(jī)科學(xué)的飛速開展，形式語言與自動機(jī)理論和方法研究也越來越收到人們的重視，但前者已經(jīng)成為計算機(jī)科學(xué)的理論根底。此次的課程設(shè)計主要任務(wù)是

5、研究自動機(jī)在編譯方面的應(yīng)用，并將重點(diǎn)放在求FIRST集和FOLLOW集。根據(jù)構(gòu)造FIRST集的算法和FOLLOW集的算法，編寫一個程序，程序具有通用性，即編制的愈發(fā)程序能夠適用于不同的文法。根本思想描述，通過對輸入的文法進(jìn)行判斷，進(jìn)而根據(jù)構(gòu)造的FIRST集和FOLLOW集的算法。并把計算所得的FIRST集和FOLLOW集輸出。構(gòu)造FIRST集的算法和FOLLOW集的算法的核心算法教材上已經(jīng)給出了，因此要做的事只是將他們實(shí)現(xiàn)。關(guān)鍵字：FIRST集，F(xiàn)OLLOW集，算法。目錄一、課程設(shè)計任務(wù)及要求1二、需求分析2三、設(shè)計思路3四、詳細(xì)設(shè)計7五、運(yùn)行調(diào)試與分析討論8六、設(shè)計體會與小結(jié)10七、參考文獻(xiàn)

6、11八、附錄.11-第 3 頁 -一、課程設(shè)計任務(wù)及要求1.任務(wù)：設(shè)計一個由正規(guī)文法生成First集和Follow集并進(jìn)行簡化的算法動態(tài)模擬。First集和Follow集生成模擬算法的根本功能：（1） 輸入一個文法G（2） 輸入由文法G構(gòu)造First集的算法（3） 輸出First集（4） 輸入由文法構(gòu)造Follow集的算法（5） 輸出Follow集2. 實(shí)驗(yàn)?zāi)康模狠斎耄喝我獾纳舷挛臒o關(guān)文法。輸出：所輸入的上下文無關(guān)文法一切非終結(jié)符的first集合和follow 集合。3.設(shè)文法GSVN，VT，P，S，那么首字符集為： FIRSTa | a，aVT，,V *。假設(shè)，F(xiàn)IRST。由定義可以看出，F(xiàn)

7、IRST是指符號串能夠推導(dǎo)出的所有符號串中處于串首的終結(jié)符號組成的集合。所以FIRST集也稱為首符號集。設(shè)x1x2xn，F(xiàn)IRST可按以下方法求得：令FIRST，i1；（1） 假設(shè)xiVT，那么xiFIRST；（2） 假設(shè)xiVN； 假設(shè)FIRSTxi，那么FIRSTxiFIRST； 假設(shè)FIRSTxi，那么FIRSTxiFIRST；（3） ii+1，重復(fù)1、2，直到xiVT，i2，3，n或xiVN且假設(shè)FIRSTxi或i>n為止。當(dāng)一個文法中存在產(chǎn)生式時，例如，存在A，只有知道哪些符號可以合法地出現(xiàn)在非終結(jié)符A之后，才能知道是否選擇A產(chǎn)生式。這些合法地出現(xiàn)在非終結(jié)符A之后的符號組成的集

8、合被稱為FOLLOW集合。下面我們給出文法的FOLLOW集的定義。設(shè)文法GSVN，VT，P，S，那么 FOLLOWAa | S Aa ，aVT。假設(shè)SA，#FOLLOWA。由定義可以看出，F(xiàn)OLLOWA是指在文法GS的所有句型中，緊跟在非終結(jié)符A后的終結(jié)符號的集合。FOLLOW集可按以下方法求得：（1） 對于文法GS的開始符號S，有#FOLLOWS；（2） 假設(shè)文法GS中有形如BxAy的規(guī)那么，其中x，yV *，那么FIRSTyFOLLOWA；（3） 假設(shè)文法GS中有形如BxA的規(guī)那么，或形如BxAy的規(guī)那么且FIRSTy，其中x，yV *，那么FOLLOWBFOLLOWA；3. 實(shí)驗(yàn)內(nèi)容：計

9、算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. 實(shí)現(xiàn)提示：用數(shù)據(jù)庫存儲多行文法，用LIST控件顯示算法，用GRID類依據(jù)算法進(jìn)行作圖。并實(shí)現(xiàn)算法與生成過程的關(guān)聯(lián)。三、設(shè)計思路1.識別終結(jié)符集和非終結(jié)符集 開始 結(jié)束計算產(chǎn)生

10、式的總數(shù)N輸入要分析的文法G 開始 開始 輸入n=0識別所有符號集合Z讀取一條產(chǎn)生式n=n+1終結(jié)符集合Vt=Z - Vn識別產(chǎn)生式左部的字符V并添加到非終結(jié)符集合Vn輸出Vt N>n 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可以推導(dǎo) Y Y N將該終結(jié)符參加V的First集中還有未計算的非終結(jié)符 結(jié)束3. 計算所有非終結(jié)符的Follow集 開始讀取Vn中的一個非終結(jié)符V從語

11、法G中查找左部是V的所有產(chǎn)生式V的后一個字符V*為終結(jié)符V是最后一個字符 N Y N添加V*到V的Follow集中添加#到V的Follow集中 Y 是否遍歷完所有右部含有的產(chǎn)生式 添加V*的First集到V的Follow集中 有未求過的非終結(jié)符 完成四、詳細(xì)設(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集表格。根

12、據(jù)表格中的每個非終結(jié)符后面的表示的是：相對應(yīng)的終結(jié)符是屬于該非終結(jié)符的。五、運(yùn)行調(diào)試與分析討論1.運(yùn)行程序2.輸入文法3.輸出非終結(jié)符和終結(jié)符4.計算First集并輸出計算Follow集并輸出六、設(shè)計體會與小結(jié)這次的編譯原理的課程設(shè)計歷時兩天，進(jìn)過不斷的查看課本從網(wǎng)上差資料解決問題，讓我對文法的FIRST集和FOLLOW集有了更多的了解。雖然做課程設(shè)計是一個比擬辛苦的過程，但是從它的過程中我們還是可以學(xué)到很多東西的，比方思維的方式，鍛煉自己的耐心，寫文檔時的邏輯能力。在寫課設(shè)的過程中遇到了以下的問題：1 終結(jié)符 V和V，多了個帶 的終結(jié)符，但是它在處理的時候只能當(dāng)一個符號來識別，而用程序設(shè)計語

13、言表示時它能表示成兩個字符，如果處理不當(dāng)?shù)脑挘琕就可能被認(rèn)為是終結(jié)符號V和非終結(jié)符。這無疑給處理過程添加了難度。2 還有一些自認(rèn)為理所當(dāng)然能實(shí)現(xiàn)的，卻實(shí)際并不可取的方法。如：本來JAVA API有個方法String.split(String s);用于以s 為分割字符，將指定的字符分成字符數(shù)組。但是s 為括號時無論左右括號，大小括號，方框括號，都不能分割，并且拋異常。這是個很難理解的問題。迫不得已，我不得不想其他的方法來實(shí)現(xiàn)分割算法。3 再有就是對編譯原理中First Follow算法設(shè)計時，采取何種策略效率最高的問題。最后我想到了用遞歸方式。下面總結(jié)此次課程設(shè)計的一些收獲：1.對程序設(shè)計理解

14、，算法的設(shè)計，有了進(jìn)一不的提高。 2.對程序調(diào)試的技巧收獲不小。因?yàn)樵摮绦蛑饕撬惴ㄑ芯?，所以程序分支較復(fù)雜。斷點(diǎn)調(diào)試是必不可缺并且很實(shí)用的工作。3對程序到軟件過程的理解。這次也是我第一次將自己做的程序制作成一個可自定義安裝過程的小軟件。從而將程序的運(yùn)行與IDE脫離開來。4毫無疑問，就是對編譯原理的理解。能夠很好地理解程序設(shè)計與編譯原理的關(guān)系。七、參考文獻(xiàn)1 張素琴.編譯原理. 北京:清華大學(xué)出版社,20052 付京周.JAVA程序設(shè)計語言. 北京:人民郵電出版社,20078、 附錄/求VN和VTvoid VNVT(STR *p) int i,j; for(i=0;i<N;i+) for

15、(j=0;j<(int)pi.left.length();j+) if(pi.leftj>='A'&&pi.leftj<='Z') if(Vn.find(pi.leftj)>100) Vn+=pi.leftj; else if(Vt.find(pi.leftj)>100) Vt +=pi.leftj; for(j=0;j<(int)pi.right.length();j+) if(!(pi.rightj>='A'&&pi.rightj<='Z') if

16、(Vt.find(pi.rightj)>100) 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<strings.length();j+) if(stringsj='-'&&stringsj+1='>') pi.left=strings.substr(0,j); pi.right=strings.substr(j+2,strings.length()-j); /對

17、每個文法符號求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;i<N;i+) if(pi.left0=ch) if(!(Vt.find(pi.right0)>100) if(FirstVn.find(ch).find(pi.right0)>100) FirstVn.find(ch)+=pi.right

18、0; 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_i<ff.length();i_i+) if( FirstVn.find(ch).find(ffi_i)>100) FirstVn.find(ch)+=

19、ffi_i; else for(int j=0;j<pi.right.length();j+) string TT; TT=Letter_First(p,pi.rightj); if(!(TT.find('*')>100)&&(j+1)<pi.right.length() sort(TT.begin(),TT.end(); string tt; for(int t=1;t<TT.length();t+) tt+=TTt; TT=tt; tt="" for(t=0;t<TT.length();t+) if( Fir

20、stVn.find(ch).find(TTt)>100) FirstVn.find(ch)+=TTt; else for(t=0;t<TT.length();t+) if( FirstVn.find(ch).find(TTt)>100) 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;r

21、eturn FollowVn.find(ch);for(int i=0;i<N;i+)for(int j=0;j<pi.right.length();j+)if(pi.rightj=ch)if(j+1=pi.right.length()string gg;gg=Letter_Follow(p,pi.left0);NONEVn.find(pi.left0)=0;for(int k=0;k<gg.length();k+)if(FollowVn.find(ch).find(ggk)>100)FollowVn.find(ch)+=ggk;else string FF; for(int jj=j+1;jj<pi.right.length();jj+) string TT; TT=Letter_First(p,pi.rightjj); if(!(TT.find('*')>100)&&(jj+1)<pi.rig