編譯原理課設(shè)3

1、姓名：課程設(shè)計(jì)名稱課程設(shè)計(jì)(論文)任務(wù)書 軟 件 學(xué) 院 學(xué)院 軟件測試 專業(yè) 2 班 一、課程設(shè)計(jì)(論文)題目 LL(1)分析過程模擬 二、課程設(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ā)工具VC /JAVA/C

2、#/.NET 。2課程設(shè)計(jì)的任務(wù)及要求1）課程設(shè)計(jì)任務(wù)：對文法G的句子進(jìn)行確定的自頂向下語法分析的充分必要條件是，G的任意兩個(gè)具有相同左部的產(chǎn)生式A>| 滿足下列條件：（1）如果、均不能推導(dǎo)出，則 FIRST() FIRST() = 。（2） 和 至多有一個(gè)能推導(dǎo)出 。（3）如果 *> ，則 FIRST() FOLLOW(A) = 。將滿足上述條件的文法稱為LL(1)文法。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)試與分析討論-給出

3、運(yùn)行屏幕截圖，分析運(yùn)行結(jié)果，有何改進(jìn)想法等。（5）設(shè)計(jì)體會(huì)與小結(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è)

4、大學(xué)出版社6）課程設(shè)計(jì)進(jìn)度安排1準(zhǔn)備階段（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、（）、一般（）、差（）；（5）論文撰寫（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； 評閱人： 職稱： 副教授 2016 年 6 月 日中文摘要對文法G的句子進(jìn)行確定的自頂向下語法分析的充分必要條件是，G的任意兩個(gè)具有相同左部的產(chǎn)生式A>| 滿足下列條件：（1）如果、均不能推導(dǎo)出，則 FIRST() FIRST() = 。（2） 和 至多有一個(gè)能推導(dǎo)出 。（3）如果 *> ，則 FIRST() FOLLOW(A) = 。將滿足上述條件的文法稱為LL(1)文法。概要第一個(gè)L代表從左向右掃描輸入符號串，第二個(gè)L代表產(chǎn)生最左推導(dǎo)，1代表在分析過程中執(zhí)行每一步推導(dǎo)都要向前查看一個(gè)輸

6、入符號當(dāng)前正在處理的輸入符號。LL(1)文法既不是二義性的，也不含左遞歸，對LL(1)文法的所有句子均可進(jìn)行確定的自頂向下語法分析。需要注意的是，并不是所有的語言都可以用LL(1)文法來描述，而且不存在判定某語言是否是LL(1)文法的算法。也就是說，確定的自頂向下分析只能實(shí)現(xiàn)一部分上下文無關(guān)語言的分析，這就是LL(1)文法所產(chǎn)生的語言。另外，在上述LL(1)文法的條件中，要求： FIRST(1)， FIRST(2)， FIRST(n) 中至多有一個(gè)成立。 目錄一、課程設(shè)計(jì)任務(wù)及要求1二、需求分析2三、設(shè)計(jì)思路3四、詳細(xì)設(shè)計(jì)5五、運(yùn)行調(diào)試與分析討論10六、設(shè)計(jì)體會(huì)與小結(jié)11七、參考文獻(xiàn)12-第

7、5 頁 -一、課程設(shè)計(jì)任務(wù)及要求題目：LL(1)分析過程模擬【問題描述】 設(shè)計(jì)一個(gè)給定LL（1）分析表，輸入一個(gè)句子，能由依據(jù)LL（1）分析表輸出與句子對應(yīng)的語法樹。能對語法樹生成過程進(jìn)行模擬。(算法參見教材)【基本要求】 動(dòng)態(tài)模擬算法的基本功能是：輸入LL（1）分析表和一個(gè)句子；輸出LL（1）總控程序；輸出依據(jù)句子構(gòu)成的對應(yīng)語法樹的過程；【測試數(shù)據(jù)】輸入句子：i*i+i輸入LL（1）分析表®(E)®iF®e® e®*FT '® eT'®FT '®FT'T®e®

8、e®+TE'E'®TE'®TE'E#)(*+i【實(shí)現(xiàn)提示】用結(jié)構(gòu)體數(shù)組存儲(chǔ)多行正規(guī)式，用LIST控件顯示算法，用CDC類依據(jù)進(jìn)行算法進(jìn)行作圖。并實(shí)現(xiàn)算法與生成過程的關(guān)聯(lián)。二、需求分析問題理解用數(shù)據(jù)庫存儲(chǔ)多行文法，用LIST控件顯示算法，用GRID類依據(jù)算法進(jìn)行作圖。并實(shí)現(xiàn)算法與生成過程的關(guān)聯(lián)。問題分析求出First集和Follow集，是求出Select集的基礎(chǔ)，因此本程序也做了些完善，功能擴(kuò)展發(fā)面，在出First集和Follow集的基礎(chǔ)上求Select集，判斷是否為LL1文法，構(gòu)造預(yù)測分析表。判斷是在LL1分析文法中通過Select

9、集判斷是否是LL1文法，求出預(yù)測分析表之后，實(shí)現(xiàn)了字符串，依據(jù)LL1分析表單步輸出字符串的分析過程。三、設(shè)計(jì)思路1、設(shè)計(jì)原理（1）、LL（1）文法的定義LL(1)分析法屬于確定的自頂向下分析方法。LL(1)的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第2個(gè)L表明分析過程中將使用最左推導(dǎo)，1表明只需向右看一個(gè)符號便可決定如何推導(dǎo)，即選擇哪個(gè)產(chǎn)生式(規(guī)則)進(jìn)行推導(dǎo)。LL(1)文法的判別需要依次計(jì)算FIRST集、FOLLOW集和SELLECT集,然后判斷是否為LL(1)文法,最后再進(jìn)行句子分析。（2）、預(yù)測分析表構(gòu)造LL(1)分析表的作用是對當(dāng)前非終極符和輸入符號確定應(yīng)該選擇用哪個(gè)產(chǎn)生式

10、進(jìn)行推導(dǎo)。它的行對應(yīng)文法的非終極符，列對應(yīng)終極符，表中的值有兩種：一是產(chǎn)生式的右部的字符串，一是null。若用M表示LL(1)分析表，則M可表示如下：M: VN×VTàPErrorM(A, t) = Aà，當(dāng)tÎselect(Aà) ，否則M(A, t) = Error其中P表示所有產(chǎn)生式的集合。（2）、語法分析程序構(gòu)造LL(1)分析中X為符號棧棧頂元素，a為輸入流當(dāng)前字符，E為給定測試數(shù)據(jù)的開始符號，#為句子括號即輸入串的括號。分析表用一個(gè)二位數(shù)組M表示，數(shù)組元素MA，a中的下標(biāo)A表示非終結(jié)符，a為終結(jié)符或句子括號#，二維數(shù)組中存放的是一條關(guān)

11、于A 的產(chǎn)生式，表明當(dāng)非終結(jié)符A向下推導(dǎo)時(shí)，面臨輸入符a時(shí)，所采用的候選產(chǎn)生式，當(dāng)元素內(nèi)容無產(chǎn)生式時(shí)，則表明用A 的左部向下推導(dǎo)時(shí)出現(xiàn)了不該出現(xiàn)的符號，因此元素內(nèi)容轉(zhuǎn)向出錯(cuò)處理的信息。2、主要算法思想（1）、 分析開始時(shí)，首先將標(biāo)志符號#和文法開始符號E依次壓入符號棧；輸入流指針指向分析串的第一個(gè)輸入符號，即由符號棧和輸入流構(gòu)成的初始格局為：(#E,a1a2.an#)然后，反復(fù)執(zhí)行第2步所列的工作。（2）、設(shè)在分析的某一步，符號棧及剩余的輸入流處于如下的格局：(#A12.Am-1Am,aiai+1.an#)其中，A1A2.Am-1Am為分析棧中的文法符號，此時(shí)，可視棧頂符號Xm的不同情況，分別

12、作如下動(dòng)作：若AmÎVN，則以Am及ai組成的符號對(Am，ai)查分析表M。設(shè)M(Am，ai)為一產(chǎn)生式，假設(shè)是AmàUVW，此時(shí)將Am從分析棧中彈出，并將UVW逆序壓入棧中，從而得到新的格局：(#A1A2.Am-1WVU,aiai+1.an#)但若T(Am，ai)=NULL或null，則調(diào)用出錯(cuò)處理程序進(jìn)行處理；。四、詳細(xì)設(shè)計(jì)總體思路分析及流程圖給定一個(gè)正規(guī)文法G，在LL(1)預(yù)測分析中，必須先求出First集和Follow集，然后求出Select集，通過Select集判斷是否是LL1文法，如果是的話，構(gòu)造預(yù)測分析表。求出預(yù)測分析表之后，再輸入一個(gè)字符串，依據(jù)LL1分析

13、表單步輸出字符串的分析過程。功能模塊分解圖（1）主程序流程圖（2）核心算法流程圖 1.計(jì)算非終結(jié)符的First集的算法及流程：First集合的構(gòu)造算法：（1）若XVT，則First（X）=X。（2）若XVN，且有產(chǎn)生式Xa，則把a(bǔ)加入到First (X)中；若X也是一條產(chǎn)生式，則把也加到First (X)中。（3）若XY是一個(gè)產(chǎn)生式且YVN，則把First (Y)中的所有非-元素都加到First (X)中；若XY1Y2Yk是一個(gè)產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對于任何j，1ji-1，F(xiàn)irst (Yj)都含有（即Y1Yi-1* ），則把First (Yj)中的所有非-元素都加到Fir

14、st (X)中；特別是，若所有的First (Yj)均含有，j=1,2,，k，則把加到First (X)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合First不再增大為止。2.計(jì)算非終結(jié)符的Follow集：Follow集合的具體構(gòu)造算法如下：（1）對于文法的開始符號S，置#于Follow(S)中；（2）若AB是一個(gè)產(chǎn)生式，則把First()|加至Follow(B)中；（3）若AB是一個(gè)產(chǎn)生式，或AB是一個(gè)產(chǎn)生式而 （即First()），則把Follow(A)加至Follow(B)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合Follow不再增大為止。3.預(yù)測分析控制程序的算法流程2、測試數(shù)據(jù)i*i+i 的語法樹

15、 關(guān)鍵代碼計(jì)算非終結(jié)符的First集：void first(edge ni,edge *n,int x)/ni為一個(gè)產(chǎn)生式，n為整個(gè)文法int i,j;for(j=0;j<SUM;j+)if(ni.getlf()=nj.getlf()if(NODE.find(nj.getro()<NODE.length()/非終結(jié)符的情況for(i=0;i<SUM;i+)if(ni.getlf()=nj.getro()first(ni,n,x);elsenx.newfirst(nj.getro();/終結(jié)符的情況計(jì)算非終結(jié)符的Follow集：void follow(edge ni,edge

16、*n,int x) /計(jì)算followint i,j,k,s;string str;for(i=0;i<ni.getrlen();i+) s=NODE.find(ni.getrg()i);if(s<NODE.length()&&s>-1) /是非終結(jié)符if(i<ni.getrlen()-1) /不在最右for(j=0;j<SUM;j+)if(nj.getlf().find(ni.getrg()i)=0)if(NODE.find(ni.getrg()i+1)<NODE.length() for(k=0;k<SUM;k+)if(nk.get

17、lf().find(ni.getrg()i+1)=0) nj.newfollow(nk.getfirst(); if(nk.getfirst().find("*")<nk.getfirst().length() nj.newfollow(ni.getfollow();elsestr.erase(); str+=ni.getrg()i+1; nj.newfollow(str);五、運(yùn)行調(diào)試與分析討論第 9 頁 六、設(shè)計(jì)體會(huì)與小結(jié)對于此次的課設(shè)，我得出一句話：紙上得來終覺淺，絕知此事要躬行。只有你親手去做了，你才有資格說這件事的難易。即使你失敗了，也是受益匪淺的。由于實(shí)驗(yàn)失敗的原因，本次實(shí)驗(yàn)對于我個(gè)人來說，成就沒有多大意義。不過對于失敗后的一些感觸及心得體會(huì)如下。1。準(zhǔn)備越充分，實(shí)驗(yàn)越順利。2。交流是最好的老師。實(shí)驗(yàn)過程中，多多少少會(huì)遇到問題，多咨詢老師或者會(huì)做實(shí)驗(yàn)的同學(xué)。這樣才能將難題一一化解。3。一半時(shí)