first集和follow集生成算法模擬

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

2、JAVA/C#/.NET 。2課程設(shè)計(jì)的任務(wù)及要求1）課程設(shè)計(jì)任務(wù)：設(shè)計(jì)一個(gè)由正規(guī)文法生成First集和Follow集并進(jìn)行簡化的算法動(dòng)態(tài)模擬。2）創(chuàng)新要求：動(dòng)態(tài)模擬算法的基本功能是：（） 輸入一個(gè)文法（） 輸出由文法G構(gòu)造的FIRST集算法（） 輸出FIRST算法（） 輸出由文法G構(gòu)造的FOLLOW集算法（） 輸出FOLLOW集3）課程設(shè)計(jì)論文編寫要求（1）課程設(shè)計(jì)任務(wù)及要求（2）設(shè)計(jì)思路-工作原理、功能規(guī)劃（3）詳細(xì)設(shè)計(jì)-數(shù)據(jù)分析、算法思路、功能實(shí)現(xiàn)（含程序流程圖、主要代碼及注釋）、界面等。（4）運(yùn)行調(diào)試與分析討論-給出運(yùn)行屏幕截圖，分析運(yùn)行結(jié)果，有何改進(jìn)想法等。（5）設(shè)計(jì)體會(huì)與小結(jié)-設(shè)計(jì)

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

4、設(shè)計(jì)目的要求、查閱相關(guān)資料2程序模塊設(shè)計(jì)分析階段（4學(xué)時(shí)）：程序總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)3代碼編寫調(diào)試階段（8學(xué)時(shí)）：程序模塊代碼編寫、調(diào)試、測(cè)試4撰寫論文階段（4學(xué)時(shí)）：總結(jié)課程設(shè)計(jì)任務(wù)和設(shè)計(jì)內(nèi)容，撰寫課程設(shè)計(jì)論文學(xué)生簽名： 2015 年 6 月 19 日課程設(shè)計(jì)(論文)評(píng)審意見（1）學(xué)習(xí)態(tài)度（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （2）系統(tǒng)設(shè)計(jì)（20分）：優(yōu)（ ）、良（）、中（）、一般（）、差（）； （3）編程調(diào)試（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）回答問題（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）論文撰寫（20分）：優(yōu)（）、良（）、中（

5、）、一般（）、差（）； 評(píng)閱人： 職稱： 講師 2015 年 6 月 19 日中文摘要隨著計(jì)算機(jī)科學(xué)的飛速發(fā)展，形式語言與自動(dòng)機(jī)理論和方法研究也越來越收到人們的重視，但前者已經(jīng)成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。此次的課程設(shè)計(jì)主要任務(wù)是研究自動(dòng)機(jī)在編譯方面的應(yīng)用，并將重點(diǎn)放在求FIRST集和FOLLOW集。根據(jù)構(gòu)造FIRST集的算法和FOLLOW集的算法，編寫一個(gè)程序，程序具有通用性，即編制的愈發(fā)程序能夠適用于不同的文法。基本思想描述，通過對(duì)輸入的文法進(jìn)行判斷，進(jìn)而根據(jù)構(gòu)造的FIRST集和FOLLOW集的算法。并把計(jì)算所得的FIRST集和FOLLOW集輸出。構(gòu)造FIRST集的算法和FOLLOW集的算法的

6、核心算法教材上已經(jīng)給出了，因此要做的事只是將他們實(shí)現(xiàn)。關(guān)鍵字：FIRST集，F(xiàn)OLLOW集，算法。目錄一、課程設(shè)計(jì)任務(wù)及要求1二、需求分析2三、設(shè)計(jì)思路3四、詳細(xì)設(shè)計(jì)7五、運(yùn)行調(diào)試與分析討論8六、設(shè)計(jì)體會(huì)與小結(jié)10七、參考文獻(xiàn)11八、附錄.11-第 3 頁 -一、課程設(shè)計(jì)任務(wù)及要求1.任務(wù)：設(shè)計(jì)一個(gè)由正規(guī)文法生成First集和Follow集并進(jìn)行簡化的算法動(dòng)態(tài)模擬。First集和Follow集生成模擬算法的基本功能：（1） 輸入一個(gè)文法G（2） 輸入由文法G構(gòu)造First集的算法（3） 輸出First集（4） 輸入由文法構(gòu)造Follow集的算法（5） 輸出Follow集2. 實(shí)驗(yàn)?zāi)康模狠斎耄喝?/p>

7、意的上下文無關(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（）是指符號(hào)串能夠推導(dǎo)出的所有符號(hào)串中處于串首的終結(jié)符號(hào)組成的集合。所以FIRST集也稱為首符號(hào)集。設(shè)x1x2xn，F(xiàn)IRST（）可按下列方法求得：令FIRST（），i1；（1） 若xiVT，則xiFIRST（）；（2） 若xiVN； 若FIRST（xi），則FIRST（xi）FIRST（）； 若FIRST（xi），則FIRST（xi）FIRST（）；（3

8、） ii+1，重復(fù)（1）、（2），直到xiVT，（i2，3，n）或xiVN且若FIRST（xi）或i>n為止。當(dāng)一個(gè)文法中存在產(chǎn)生式時(shí)，例如，存在A，只有知道哪些符號(hào)可以合法地出現(xiàn)在非終結(jié)符A之后，才能知道是否選擇A產(chǎn)生式。這些合法地出現(xiàn)在非終結(jié)符A之后的符號(hào)組成的集合被稱為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é)符號(hào)的集合。FOLLOW集可按下列方法求得：（1） 對(duì)于文法

9、GS的開始符號(hào)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. 實(shí)驗(yàn)內(nèi)容：計(jì)算FIRST集和FOLLOW集4.二、需求分析1.基本要求： 動(dòng)態(tài)模擬算法的基本功能是：（1） 輸入一個(gè)文法G；（2） 輸出由文法G構(gòu)造FIRST集的算法；（3） 輸出First集；i)(*+F的first集T的first集E的first集111111111（4） 輸出由文法G構(gòu)造FOLLOW集的算法；

10、（5） 輸出FOLLOW集。2.測(cè)試數(shù)據(jù)：輸入文法E：E TEE +TE|T FTT *FT|F->(E)|i3. 實(shí)現(xiàn)提示：用數(shù)據(jù)庫存儲(chǔ)多行文法，用LIST控件顯示算法，用GRID類依據(jù)算法進(jìn)行作圖。并實(shí)現(xiàn)算法與生成過程的關(guān)聯(lián)。三、設(shè)計(jì)思路1.識(shí)別終結(jié)符集和非終結(jié)符集 開始 結(jié)束計(jì)算產(chǎn)生式的總數(shù)N輸入要分析的文法G 開始 開始 輸入n=0識(shí)別所有符號(hào)集合Z讀取一條產(chǎn)生式n=n+1終結(jié)符集合Vt=Z - Vn識(shí)別產(chǎn)生式左部的字符V并添加到非終結(jié)符集合Vn輸出Vt N>n Y 結(jié)束 N輸出Vn 識(shí)別終結(jié)符集 結(jié)束 識(shí)別非終結(jié)符集 2. 計(jì)算所有非終結(jié)符的First集 開始讀取Vn中的

11、一個(gè)非終結(jié)符V從語法G中查找左部是V的所有產(chǎn)生式 產(chǎn)生式的右部第一個(gè)符號(hào)V*是終結(jié)符或者V*取出其中的一條產(chǎn)生式 N V*右部的第一個(gè)非終結(jié)符V可以推導(dǎo) Y Y N將該終結(jié)符加入V的First集中還有未計(jì)算的非終結(jié)符 結(jié)束3. 計(jì)算所有非終結(jié)符的Follow集 開始讀取Vn中的一個(gè)非終結(jié)符V從語法G中查找左部是V的所有產(chǎn)生式V的后一個(gè)字符V*為終結(jié)符V是最后一個(gè)字符 N Y N添加V*到V的Follow集中添加#到V的Follow集中 Y 是否遍歷完所有右部含有的產(chǎn)生式 添加V*的First集到V的Follow集中 有未求過的非終結(jié)符 完成四、詳細(xì)設(shè)計(jì) 開始1.操作界面的控制流圖輸入文法計(jì)算所

12、有的非終結(jié)符Vn和終結(jié)符Vt并顯示計(jì)算所有非終結(jié)符的First集和Follow集并顯示 結(jié)束2. 具體設(shè)計(jì)通過分析輸入的文法，分析出文法腫的非終結(jié)符和終結(jié)符，然后計(jì)算出每個(gè)非終結(jié)符的FIRST集和FOLLOW集。在輸出的結(jié)果上應(yīng)該顯示文法中的非終結(jié)符和終結(jié)符，F(xiàn)IRST集和FOLLOW集表格。根據(jù)表格中的每個(gè)非終結(jié)符后面的表示的是：相對(duì)應(yīng)的終結(jié)符是屬于該非終結(jié)符的。五、運(yùn)行調(diào)試與分析討論1.運(yùn)行程序2.輸入文法3.輸出非終結(jié)符和終結(jié)符4.計(jì)算First集并輸出計(jì)算Follow集并輸出六、設(shè)計(jì)體會(huì)與小結(jié)這次的編譯原理的課程設(shè)計(jì)歷時(shí)兩天，進(jìn)過不斷的查看課本從網(wǎng)上差資料解決問題，讓我對(duì)文法的FIRS

13、T集和FOLLOW集有了更多的了解。雖然做課程設(shè)計(jì)是一個(gè)比較辛苦的過程，但是從它的過程中我們還是可以學(xué)到很多東西的，比如思維的方式，鍛煉自己的耐心，寫文檔時(shí)的邏輯能力。在寫課設(shè)的過程中遇到了以下的問題：1 終結(jié)符 V和V，多了個(gè)帶 的終結(jié)符，但是它在處理的時(shí)候只能當(dāng)一個(gè)符號(hào)來識(shí)別，而用程序設(shè)計(jì)語言表示時(shí)它能表示成兩個(gè)字符，如果處理不當(dāng)?shù)脑?，V就可能被認(rèn)為是終結(jié)符號(hào)V和非終結(jié)符。這無疑給處理過程添加了難度。2 還有一些自認(rèn)為理所當(dāng)然能實(shí)現(xiàn)的，卻實(shí)際并不可取的方法。如：本來JAVA API有個(gè)方法String.split(String s);用于以s 為分割字符，將指定的字符分成字符數(shù)組。但是s

14、為括號(hào)時(shí)（無論左右括號(hào)，大小括號(hào)，方框括號(hào)），都不能分割，并且拋異常。這是個(gè)很難理解的問題。迫不得已，我不得不想其他的方法來實(shí)現(xiàn)分割算法。3 再有就是對(duì)編譯原理中First Follow算法設(shè)計(jì)時(shí)，采取何種策略效率最高的問題。最后我想到了用遞歸方式。下面總結(jié)此次課程設(shè)計(jì)的一些收獲：1.對(duì)程序設(shè)計(jì)理解，算法的設(shè)計(jì)，有了進(jìn)一不的提高。 2.對(duì)程序調(diào)試的技巧收獲不小。因?yàn)樵摮绦蛑饕撬惴ㄑ芯浚猿绦蚍种л^復(fù)雜。斷點(diǎn)調(diào)試是必不可缺并且很實(shí)用的工作。3對(duì)程序到軟件過程的理解。這次也是我第一次將自己做的程序制作成一個(gè)可自定義安裝過程的小軟件。從而將程序的運(yùn)行與IDE脫離開來。4毫無疑問，就是對(duì)編譯原理的

15、理解。能夠很好地理解程序設(shè)計(jì)與編譯原理的關(guān)系。七、參考文獻(xiàn)1 張素琴.編譯原理. 北京:清華大學(xué)出版社,20052 付京周.JAVA程序設(shè)計(jì)語言. 北京:人民郵電出版社,20078、 附錄/求VN和VTvoid VNVT(STR *p) int i,j; for(i=0;i<N;i+) for(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(

16、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(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.len

17、gth();j+) if(stringsj='-'&&stringsj+1='>') pi.left=strings.substr(0,j); pi.right=strings.substr(j+2,strings.length()-j); /對(duì)每個(gè)文法符號(hào)求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

18、)>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.right0; if(pi.right0='*') if(FirstVn.find(ch).find('*')>100) FirstVn.find(ch)+='*' if(!(Vn.find(pi.right0)>100) if(pi.right.l

19、ength()=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)+=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.rig

20、ht.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( FirstVn.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;

21、 break; return FirstVn.find(ch);/ 求每個(gè)非終結(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;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)&&(