編譯原理課設(shè)2

1、姓名：課程設(shè)計(jì)名稱課程設(shè)計(jì)(論文)任務(wù)書 軟 件 學(xué) 院 學(xué)院 軟件測試 專業(yè) 2 班 一、課程設(shè)計(jì)(論文)題目 FirstVT集和LastVT集生成算法模擬 二、課程設(shè)計(jì)(論文)工作自 2016 年 6 月 20 日起至 2016 年 6 月 24 日止。三、課程設(shè)計(jì)(論文) 地點(diǎn): 軟 件 學(xué) 院 實(shí) 訓(xùn) 中 心 四、課程設(shè)計(jì)(論文)內(nèi)容要求：1本課程設(shè)計(jì)的目的進(jìn)一步培養(yǎng)學(xué)生編譯器設(shè)計(jì)的思想，加深對編譯原理和應(yīng)用程序的理解，針對編譯過程的重點(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)和編譯原理的知識, 熟悉使用開發(fā)工

2、具VC /JAVA/C#/.NET 。2課程設(shè)計(jì)的任務(wù)及要求1）課程設(shè)計(jì)任務(wù)： 設(shè)計(jì)一個(gè)由正規(guī)文法生成FirstVT集和LastVT集的算法動態(tài)模擬。 動態(tài)模擬算法的基本功能是：（1）輸入一個(gè)文法G；（2）輸出由文法G構(gòu)造FIRSTVT集的算法；（3）輸出FirstVT集； （4）輸出由文法G構(gòu)造LastVT集的算法；（5）輸出LastVT集。2）創(chuàng)新要求：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)想法等

3、。（5）設(shè)計(jì)體會與小結(jié)-設(shè)計(jì)遇到的問題及解決辦法，通過設(shè)計(jì)學(xué)到了哪些新知識，鞏固了哪些知識，有哪些提高。（6）報(bào)告按規(guī)定排版打印，要求裝訂平整，否則要求返工；（7）課設(shè)報(bào)告的裝訂順序如下：封面-任務(wù)書-中文摘要-目錄-正文-附錄(代碼及相關(guān)圖片)（8）嚴(yán)禁抄襲，如有發(fā)現(xiàn)，按不及格處理。4）課程設(shè)計(jì)評分標(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、4學(xué)時(shí)）：選擇設(shè)計(jì)題目、了解設(shè)計(jì)目的要求、查閱相關(guān)資料2程序模塊設(shè)計(jì)分析階段（4學(xué)時(shí)）：程序總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)3代碼編寫調(diào)試階段（8學(xué)時(shí)）：程序模塊代碼編寫、調(diào)試、測試4撰寫論文階段（4學(xué)時(shí)）：總結(jié)課程設(shè)計(jì)任務(wù)和設(shè)計(jì)內(nèi)容，撰寫課程設(shè)計(jì)論文學(xué)生簽名： 2016 年 6 月 24 日課程設(shè)計(jì)(論文)評審意見（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）論文撰寫（2

5、0分）：優(yōu)（）、良（）、中（）、一般（）、差（）； 評閱人： 職稱： 副教授 2016 年 6 月 日中文摘要隨著計(jì)算機(jī)科學(xué)的飛速發(fā)展，形式語言與自動機(jī)理論和方法的研究也越來越受到人們的重視，但前者已經(jīng)成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。本課程設(shè)計(jì)主要研究自動機(jī)在編譯方面的應(yīng)用，并將討論重點(diǎn)放在算符優(yōu)先分析法上，并用此理論完成算數(shù)表達(dá)式的正確與否的判斷。算符優(yōu)先分析算法通過編寫一個(gè)語法程序，使程序具有通用性。其基本思想描述，語法分析前首先要對輸入的文法和句子進(jìn)行詞法分析，去除多余的自負(fù)，并將產(chǎn)生式和終結(jié)符、非終結(jié)符填入有關(guān)數(shù)組，為語法分析做前期準(zhǔn)備。本課程設(shè)計(jì)的題目為“FirstVT集和LastVT集生

6、成算法模擬”，它是算符優(yōu)先分析算法中判斷三種優(yōu)先關(guān)系的關(guān)鍵。算符優(yōu)先分析算法是自底向上分析方法的一種。計(jì)算非終結(jié)符的FirstVT集和LastVT集是構(gòu)造算符優(yōu)先分析表的基礎(chǔ)，而算符優(yōu)先分析表的構(gòu)造又是算符優(yōu)先分析算法的基礎(chǔ)。因此，本程序的實(shí)現(xiàn)可以說是算符優(yōu)先分析算法實(shí)現(xiàn)的基礎(chǔ)。目錄一、課程設(shè)計(jì)任務(wù)及要求1二、需求分析2三、設(shè)計(jì)思路3四、詳細(xì)設(shè)計(jì)4五、運(yùn)行調(diào)試與分析討論8六、設(shè)計(jì)體會與小結(jié)9七、參考文獻(xiàn)10-第 3 頁 -一、課程設(shè)計(jì)任務(wù)及要求課設(shè)目的進(jìn)一步培養(yǎng)學(xué)生編譯器設(shè)計(jì)的思想，加深對編譯原理和應(yīng)用程序的理解，針對編譯過程的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行編程，獨(dú)立完成有一定工作量的程序設(shè)計(jì)任務(wù)，同時(shí)強(qiáng)

7、調(diào)好的程序設(shè)計(jì)風(fēng)格，并綜合使用程序設(shè)計(jì)語言、數(shù)據(jù)結(jié)構(gòu)和編譯原理的知識，熟悉使用開發(fā)工具VC /JAVA/C#/.NET ?？傮w要求1、 問題理解和分析充分地分析和理解問題本身，弄清要求做什么。2、確定解決問題的方法（設(shè)計(jì)）主要是找到解決問題的主要思路，是怎么做。在此階段可考慮系統(tǒng)的功能和模塊劃分等。 3、詳細(xì)設(shè)計(jì)和編碼確定算法的主要流程，再進(jìn)行編程。在此階段應(yīng)提醒學(xué)生程序可先在紙上寫，盡量想清楚了再動手上機(jī)，在編程過程中注意程序結(jié)構(gòu)的清晰性，避免出現(xiàn)很多明顯的程序邏輯錯(cuò)誤和語法錯(cuò)誤，提高后面程序調(diào)試效率。4、程序調(diào)試和運(yùn)行使學(xué)生掌握程序調(diào)試和排錯(cuò)的基本方法，增加編程的感覺和解決問題的成就感?；?/p>

8、本要求設(shè)計(jì)一個(gè)由正規(guī)文法生成FirstVT集和LastVT集的算法動態(tài)模擬，實(shí)現(xiàn)以下功能輸入一個(gè)文法G； 1. 輸出由文法G構(gòu)造FIRSTVT集的算法； 2. 輸出FirstVT集； 3. 輸出由文法G構(gòu)造LastVT集的算法； 4. 輸出LastVT集。二、需求分析本課程設(shè)計(jì)的題目為“FirstVT集和LastVT集生成算法模擬”，它是算符優(yōu)先分析算法中判斷三種優(yōu)先關(guān)系的關(guān)鍵。算符優(yōu)先分析算法是自底向上分析方法的一種。所謂自底向上分析，也稱移近規(guī)約分析，粗略地說它的實(shí)現(xiàn)思想是對輸入符號串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出的棧中，邊移進(jìn)邊分析，一旦棧頂符號串形成某個(gè)句型的句柄或可

9、規(guī)約串，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串，這稱為一部規(guī)約。重復(fù)這一過程直到規(guī)約到棧中只剩文法的開始符號則為分析成功，也就確認(rèn)輸入串是該文法的句子。而算符優(yōu)先分析算法的基本思想只是規(guī)定算符之間的優(yōu)先關(guān)系，也就是只考慮終結(jié)符之間的優(yōu)先關(guān)系。 本課程設(shè)計(jì)的要求只是構(gòu)造FirstVT集和LastVT集，在此基礎(chǔ)上擴(kuò)充建造算符優(yōu)先關(guān)系表。同時(shí)我們可以用數(shù)據(jù)庫存儲多行文法，用LIST控件顯示算法，用GRID類依據(jù)算法進(jìn)行作圖。并實(shí)現(xiàn)算法與生成過程的關(guān)聯(lián)。三、設(shè)計(jì)思路3.1基本算法1. FirstVT集的構(gòu)造 FIRSTVT(P）=a|P=+a或P=+Qa，aVT而QVN 若有產(chǎn)生式：Pa

10、或PQa,則aFIRSTVT(P)； 若aFIRSTVT(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P)。 步驟如下： 首先按規(guī)則對每個(gè)數(shù)組元素附初值。觀察這些初值，若FiA,ia的值是真，則將（A，a）推入棧中，直至對所有數(shù)組的初值都按此處理完。然后對棧做如下運(yùn)算。 將棧頂項(xiàng)彈出，則令其變?yōu)檎?，且將（A，a）推進(jìn)棧，如此重復(fù)直到棧彈空為止。 2.LastVT集的構(gòu)造 LASTVT(P)= a|P=+a或P=+aQ，aVT而QVN 若有產(chǎn)生式：Ua或UaV, 則aLASTVT(U)； 若aLASTVT(V)，且有產(chǎn)生式UV，則aLASTVT(U)。步驟同F(xiàn)irstVT集構(gòu)造步驟相同。 當(dāng)我們有

11、了這二個(gè)集合之后，就可以通過檢查每個(gè)產(chǎn)生式的候選式確定滿足關(guān)系的“”和“”的所有終結(jié)符對。 我們假定有產(chǎn)生式的一個(gè)侯選式形為aP，那么，對任何bFIRSTVT(P），ab； 假定有產(chǎn)生式的一個(gè)候選形為Pb，那么，對任何aLASTVT(P)，有ab。3. 構(gòu)造算符優(yōu)先關(guān)系表 在我們有了每個(gè)非終結(jié)符P的FIRSTVT(P）和LASTVT(P)集合之后，就能夠構(gòu)造文法G的優(yōu)先表。3.2語法定義本次課設(shè)題目以文法GE為測試數(shù)據(jù)；文法GE：E-TEE-+TE|T-FTT-*FT|F-(E)|i3.3計(jì)算FirstVT集和LastVT集該文法有對應(yīng)集合：FirstVT(E)= +, * ,( ,i Las

12、tVT(E)= +，*，),i FirstVT(E)= +LastVT(E)= +，*，),i FirstVT(T)= * ,( ,i LastVT(T)= *，),i FirstVT(T)= * LastVT(T)= *，),i FirstVT(F)= ( ,i LastVT(F)= ),i 4、 詳細(xì)設(shè)計(jì)4.1.1課設(shè)基本代碼char data2020;char s100; char lable20;/文法終極符集char input100;/文法輸入符號串char string2010;int k; char a; int j; char q; int r;int r1;char st1

13、030;char first1010;/文法非終結(jié)符FIRSTVT集char last1010;/文法非終結(jié)符LASTVT集int fflag10=0;int lflag10=0;int deal();/對輸入串的分析int zhongjie(char c);/判斷字符c是否是終極符int xiabiao(char c);void out(int j,int k,char *s);void firstvt(char c);/求非終結(jié)符c的FIRSTVT集void lastvt(char c); /求非終結(jié)符c的LASTVT集void table(); /創(chuàng)建文法優(yōu)先關(guān)系表4.1.2主要數(shù)據(jù)存儲

14、存儲結(jié)構(gòu)void FirstVT(char c) /求FirstVT集int i,j,k,m,n;for(i=0;ir;i+)if(sti0=c)break;if(fflagi=0)n=firsti0+1;m=0;doif(m=2|stim=|)if(zhongjie(stim+1)firstin=stim+1;n+;elseif(zhongjie(stim+2)firstin=stim+2;n+;if(stim+1!=c)FirstVT(stim+1);for(j=0;jr;j+)if(stj0=stim+1)break;for(k=0;kfirstj0;k+)int t;for(t=0;t

15、n;t+)if(firstit=firstjk+1)break;if(t=n)firstin=firstjk+1;n+;m+;while(stim!=0);firstin=0;firsti0=-n;fflagi=1;void lastvt(char c) /求LASTVT集int i,j,k,m,n;for(i=0;ir;i+)if(sti0=c)break;if(lflagi=0)n=lasti0+1;m=0;doif(stim+1=0|stim+1=|)if(zhongjie(stim)lastin=stim;n+;elseif(zhongjie(stim-1)lastin=stim-1;

16、n+;if(stim!=c)lastvt(stim);for(j=0;jr;j+)if(stj0=stim)break;for(k=0;klastj0;k+)int t;for(t=0;tTEE-+TE|T-FTT-*FT| F-(E)|i 2、運(yùn)行結(jié)果截圖：第 7 頁 6、 設(shè)計(jì)體會與小結(jié)經(jīng)過為期三天的編譯原理課程設(shè)計(jì)上機(jī)和實(shí)踐，加深了我對編譯原理這門課的理解，同時(shí)由于課設(shè)題目的要求，我對自底向上的分析方法和算符優(yōu)先文法也有了更深一層次的理解，明白了在編碼過程中需要構(gòu)建兩個(gè)優(yōu)先關(guān)系函數(shù)：FirstVT和LastVT以及語法的輸入函數(shù)和輸出函數(shù)，同時(shí)也運(yùn)用到了進(jìn)棧、入棧知識點(diǎn)。雖然最后完成了課設(shè)的總體目標(biāo)，但是在課設(shè)進(jìn)行的過程中還是遇到了很多麻煩，例如不知道運(yùn)用什么函數(shù)來記錄