FirstVT集和LastVT集生成算法模擬(編譯原理課設(shè))

1、華東交通大學(xué)課程設(shè)計(jì)(論文)任務(wù)書 軟 件 學(xué) 院 學(xué)院 軟件測試 專業(yè) 4 班 一、課程設(shè)計(jì)(論文)題目 FIRSTVT集和LASTVT集生成算法模擬 二、課程設(shè)計(jì)(論文)工作自 2014 年 6 月 16 日起至 2014 年 6 月 21 日止。三、課程設(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)和編譯原理的知識(shí), 熟悉使用開發(fā)工具VC

2、 /JAVA/C#/.NET 。2課程設(shè)計(jì)的任務(wù)及要求1）課程設(shè)計(jì)任務(wù)： 設(shè)計(jì)一個(gè)由正規(guī)文法生成FIRSTVT集和LASTVT集的算法動(dòng)態(tài)模擬。(算法參見教材) 動(dòng)態(tài)模擬算法的基本功能是：(1) 輸入一個(gè)文法G；(2) 輸出由文法G構(gòu)造FIRSTVT集的算法；(3) 輸出FIRSTVT集； (4) 輸出由文法G構(gòu)造LASTVT集的算法；(5) 輸出LASTVT集。2）創(chuàng)新要求：用界面的形式來展現(xiàn)這個(gè)結(jié)果集，這樣顯得更加的美觀。3）課程設(shè)計(jì)論文編寫要求（1）課程設(shè)計(jì)任務(wù)及要求（2）設(shè)計(jì)思路-工作原理、功能規(guī)劃（3）詳細(xì)設(shè)計(jì)-數(shù)據(jù)分析、算法思路、功能實(shí)現(xiàn)（含程序流程圖、主要代碼及注釋）、界面等。（

3、4）運(yùn)行調(diào)試與分析討論-給出運(yùn)行屏幕截圖，分析運(yùn)行結(jié)果，有何改進(jìn)想法等。（5）設(shè)計(jì)體會(huì)與小結(jié)-設(shè)計(jì)遇到的問題及解決辦法，通過設(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）蔣立源、康慕寧等，編譯原理

4、（第2版）M，西安：西北工業(yè)大學(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é)生簽名： 2014 年 6 月 21 日課程設(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）回答問題（

5、20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）論文撰寫（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； 評(píng)閱人： 職稱： 副教授 2014 年 6 月 26 日目錄緒論4正文4設(shè)計(jì)實(shí)現(xiàn)10測試數(shù)據(jù)運(yùn)行結(jié)果分析12課程設(shè)計(jì)總結(jié)13參考文獻(xiàn)14緒論隨著計(jì)算機(jī)科學(xué)的飛速發(fā)展，形式語言與自動(dòng)機(jī)理論和方法的研究也越來越受到人們的重視，但前者已經(jīng)成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。本課程設(shè)計(jì)主要研究自動(dòng)機(jī)在編譯方面的應(yīng)用，并將討論重點(diǎn)放在算符優(yōu)先分析法上，并用此理論完成算數(shù)表達(dá)式的正確與否的判斷。根據(jù)算符優(yōu)先分析算法，編寫一個(gè)語法程序，程序具有通用性，即編制的語法縫隙程序能夠適用于不同文法以及各種

6、輸入的單詞串?；舅枷朊枋?，語法分析前首先要對輸入的文法和句子進(jìn)行詞法分析，去除多余的自負(fù)，并將產(chǎn)生式和終結(jié)符、非終結(jié)符填入有關(guān)數(shù)組，為語法分析做前期準(zhǔn)備。算符優(yōu)先分析算法的核心算法教材上已給出，因此所要做的事只是將其變成實(shí)現(xiàn)。正文設(shè)計(jì)目的本課程設(shè)計(jì)的題目為“FirstVT集和LastVT集生成算法模擬”，它是算符優(yōu)先分析算法中判斷三種優(yōu)先關(guān)系的關(guān)鍵。算符優(yōu)先分析算法是自底向上分析方法的一種。所謂自底向上分析，也稱移近規(guī)約分析，粗略地說它的實(shí)現(xiàn)思想是對輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出的棧中，邊移進(jìn)邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄或可規(guī)約串，就用該產(chǎn)生式的左部非

7、終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱為一部規(guī)約。重復(fù)這一過程直到規(guī)約到棧中只剩文法的開始符號(hào)則為分析成功，也就確認(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è)計(jì)一個(gè)給定文法和對應(yīng)的FIRSTVT和LASTVT集，能依據(jù)依據(jù)文法和FIRSTVT和LASTVT生成算符優(yōu)先分析表?？梢詣?dòng)態(tài)模擬算法的基本功能，通過輸入一個(gè)給定文法，及FIRSTVT和LASTVT集，本題目以文法GE為測試數(shù)據(jù): 文法GE:E->TEE->+

8、TE|T->FTT->*FT|F->(E)|i該文法有對應(yīng)的FIRSTVT(E)= +, * ,( ,i LASTVT(E)= +，*，),i FIRSTVT(E')= + LASTVT(E')= +，*，),i FIRSTVT(T)= * ,( ,i LASTVT(T)= *，),i FIRSTVT(T')= * LASTVT(T')= *，),i FIRSTVT(F)= ( ,i LASTVT(F)= ),i 通過算符優(yōu)先關(guān)系表構(gòu)造算法： 給定文法中任何二個(gè)終結(jié)符對(a,b)之間的優(yōu)先關(guān)系有三種優(yōu)先關(guān)系計(jì)算為：關(guān)系：可以直接查看產(chǎn)生式的右部

9、，對如下形式的產(chǎn)生式：Aab或 AaBb則有a=b成立。 關(guān)系：求出每個(gè)非終結(jié)符B的FIRSTVT(B)，觀察如下形式的產(chǎn)生式：AaB對每一bFIRSTVT(B)，有ab成立。 關(guān)系：計(jì)算每個(gè)非終結(jié)符B的LASTVT(B)，觀察如下形式的產(chǎn)生式： ABb對每一aLASTVT(B)，有ab成立。 這樣，對于給定的文法和對應(yīng)的FIRSTVT和LASTVT集，通過二個(gè)終結(jié)符之間的優(yōu)先關(guān)系表構(gòu)造算法，可以得到算法優(yōu)先分析表構(gòu)造過程的過程和算符優(yōu)先分析表生成算法。 所以，我們的重點(diǎn)應(yīng)該放在算符優(yōu)先分析表的生成算法上，解決了這一問題，也就可以得到我們想要的結(jié)果，算法優(yōu)先分析表以及分析過程。其中，對于FIR

10、STVT集和LASTVT集的表示可以采取集合的方式，同樣也可以采用關(guān)系圖法進(jìn)行表示。總體設(shè)計(jì)算符優(yōu)先分析表的構(gòu)造原理：通過檢查文法G的每個(gè)產(chǎn)生式的每個(gè)候選式，可以首先找出滿足ab的終結(jié)符對；為了找出所有滿足關(guān)系和的終結(jié)符對，我們首先需要對文法G的每個(gè)非終結(jié)符P構(gòu)造二個(gè)集合FIRSTVT（P）和LASTVT(P)。1. FirstVT集的構(gòu)造FIRSTVT(P）=a|P=>+a或P=>+Qa，aVT而QVN 若有產(chǎn)生式：Pa或PQa,則aFIRSTVT(P)；若aFIRSTVT(Q)，且有產(chǎn)生式PQ，則aFIRSTVT(P)。2. LastVT集的構(gòu)造LASTVT(P)= a|P=&

11、gt;+a或P=>+aQ，aVT而QVN 若有產(chǎn)生式：Ua或UaV, 則aLASTVT(U)；若aLASTVT(V)，且有產(chǎn)生式UV，則aLASTVT(U)。當(dāng)我們有了這二個(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)先表。詳細(xì)設(shè)計(jì)首先介紹算符優(yōu)先文法的幾個(gè)重要性質(zhì)：性質(zhì)1：在算符

12、文法中任何句型都不包含兩個(gè)相鄰的非終結(jié)符。性質(zhì)2：如果Aa（或者bA）出現(xiàn)在算符文法的句型S中，其中A是非終結(jié)符，b是終結(jié)符，則S中任何含此b的短語必含有A。1. FirstVT集的構(gòu)造，算法描述：若有產(chǎn)生式A->a或A->Ba，則a屬于FirstVT（A），其中A、B為非終結(jié)符，a為終結(jié)符。 ：若a屬于FirstVT（B）且有產(chǎn)生式A->B則有a屬于FirstVT（A）。為了計(jì)算方便，建立一個(gè)布爾數(shù)組Fm,n（m為非終結(jié)字符的個(gè)數(shù)，n為終結(jié)字符的個(gè)數(shù)）和一個(gè)后進(jìn)先出棧STACK。將所有的非終結(jié)符排序，用iA表示非終結(jié)符A的序號(hào)，再將所有的終結(jié)符排序，用ia表示終結(jié)符a的序號(hào)

13、。算法的目的是要使數(shù)組的一個(gè)元素最終取值滿足：FiA,ja的值為真，當(dāng)且僅當(dāng)a屬于FirstVT（A）。至此，顯然所有的非終結(jié)符的FirstVT集已完全確定。步驟如下：首先按規(guī)則對每個(gè)數(shù)組元素附初值。觀察這些初值，若FiA,ia的值是真，則將（A，a）推入棧中，直至對所有數(shù)組的初值都按此處理完。然后對棧做如下運(yùn)算。將棧頂項(xiàng)彈出，則令其變?yōu)檎?，且將（A，a）推進(jìn)棧，如此重復(fù)直到棧彈空為止。若表達(dá)式文法為：（0） E'# E #（1） EE + T（2） ET（3） TT*F（4） TF（5） FPF | P（6） P(E)（7） Pi計(jì)算每個(gè)非終結(jié)符的FirstVT集和LastVT集得到

14、如下結(jié)果：FIRSTVT(E') = # FIRSTVT(E) = +，*，（，iFIRSTVT(T) = *，（，iFIRSTVT(F) = ，（，iFIRSTVT(P)=（，i2. LastVT集的構(gòu)造，算法描述：用于構(gòu)建輸入文法的LastVT集若有規(guī)則U:=a或U:=aV,則a屬于LastVT（U）若有規(guī)則U:=V,且a屬于LastVT（V）則a屬于LastVT（U）設(shè)一個(gè)棧STACK，和一個(gè)布爾數(shù)組BProcedureInsert（U，a） IF NOT BU,a THEN BEGIN BU,a:=TRUE;把（U，a）推進(jìn)STACK棧； END；BEGIN FOR 每個(gè)非終結(jié)

15、符號(hào)U和終結(jié)符號(hào)a DO BU,a:=FALSE; FOR 每個(gè)形如U:=a或U:=aV的規(guī)則 DO INSERT(U,a); WHILE STACK棧非空 DO BEGIN 把STACK棧的棧頂彈出，記為（V,a）; FOR 沒條形如U:=V的規(guī)則 DO INSERT(U,a); END OF WHILE;END; 具體算法如下： Begin For每個(gè)終結(jié)符P和終結(jié)符 a Do FP,a=FALSE; For 每個(gè)形如P->a或P->aQ的產(chǎn)生式， Do insert （P，a） While Stack 非空 Do Begin 把Stack 的頂端，記為（Q，a），上托出去；

16、For每條形如P->Q的產(chǎn)生式 Insert（P，a） End of while； END針對上述算法可得到每個(gè)非終結(jié)符的LastVT集如下：LASTVT(E') = # LASTVT(E) +，*，），iLASTVT(T) *，），iLASTVT(F) ，），iLAVSTVT(P)），i 算符優(yōu)先分析流程圖圖1算符優(yōu)先分析流程圖設(shè)計(jì)實(shí)現(xiàn).主要數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)描述：本課程設(shè)計(jì)主要采用棧的數(shù)據(jù)結(jié)構(gòu)，定義一個(gè)棧的類，類中主要成員函數(shù)實(shí)現(xiàn)棧的一些基本操作，如：push（）為入棧操作，pop（）為出棧操作，empty（）判斷棧中是否為空，clear（）用于對棧進(jìn)行清空處理，核心代碼為： 建立

17、FirstVT函數(shù)集和SetFirstVT（），用來得到相應(yīng)文法中所對應(yīng)的非終結(jié)符的FirstVT集void CMyDlg:SetFirstVt(int Ptnum) /建立FRISTVT集int i,j; char Q; char a; for(i=0;i<100;i+) for(j=0;j<100;j+) Fij=false; for(i=0;i<=Ptnum;i+) if(Vt.Find(Pti.pright0)!=-1) InsertFirstOrLast(Pti.pleft,Pti.pright0,"First"); if(Pti.pright.

18、GetLength()>=2)if(Vn.Find(Pti.pright0)!=-1 && Vt.Find(Pti.pright1)!=-1)InsertFirstOrLast(Pti.pleft,Pti.pright1,"First"); while(!stack.empty() stack.pop(Q,a); for(i=0;i<Ptnum;i+) if(Pti.pright0=Q) InsertFirstOrLast(Pti.pleft,a,"First"); 建立LastVT集函數(shù)和SetLastVT函數(shù)，用來得到相應(yīng)

19、文法中所有非終結(jié)符的LastVT集void CMyDlg:SetLastVt(int Ptnum) /建立LASTVT集 int i,j; char Q; char a; for(i=0;i<100;i+) for(j=0;j<100;j+) Lij=false; for(i=0;i<Ptnum;i+) if(Vt.Find(Pti.pright.Right(1)0) InsertFirstOrLast(Pti.pleft,Pti.pright.Right(1)0,"Last"); if(Pti.pright.GetLength()>=2) if(V

20、t.Find(Pti.pright.Right(2)0)!=-1&&Vn.Find(Pti.pright.Right(2)1)!=-1)InsertFirstOrLast(Pti.pleft,Pti.pright.Right(2)0,"Last"); while(!stack.empty() stack.pop(Q,a); for(i=0;i<Ptnum;i+) if(Pti.pright0=Q) InsertFirstOrLast(Pti.pleft,a,"Last");測試數(shù)據(jù)運(yùn)行結(jié)果分析1、 測試數(shù)據(jù)如下，文法GSS# E #EE + TETTT*FTFFP-F | PP(E)|i它對性的FirstVT集和LastVT集為：FIRSTVT(S) = # FIRSTVT(E) = +，*，-，（，iFIRSTVT(T) = *，-，（，