FirstVT集和LastVT集生成算法模擬3

1、華東交通大學(xué)課程設(shè)計(jì)(論文)任務(wù)書(shū) 軟 件 學(xué) 院 學(xué)院 軟件測(cè)試 專(zhuān)業(yè) 4 班 一、課程設(shè)計(jì)(論文)題目 FIRSTVT集和LASTVT集生成算法模擬 二、課程設(shè)計(jì)(論文)工作自 2021 年 6 月 16 日起至 2021 年 6 月 21 日止。三、課程設(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ì)編譯過(guò)程的重點(diǎn)和難點(diǎn)內(nèi)容進(jìn)行編程，獨(dú)立完成有一定工作量的程序設(shè)計(jì)任務(wù)，同時(shí)，強(qiáng)調(diào)好的程序設(shè)計(jì)風(fēng)格，并綜合使用程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)和編譯原理的知識(shí), 熟悉使用開(kāi)發(fā)工具VC

2、 /JAVA/C#/.NET 。2課程設(shè)計(jì)的任務(wù)及要求1課程設(shè)計(jì)任務(wù)： 設(shè)計(jì)一個(gè)由正規(guī)文法生成FIRSTVT集和LASTVT集的算法動(dòng)態(tài)模擬。(算法參見(jiàn)教材) 動(dòng)態(tài)模擬算法的根本功能是：(1) 輸入一個(gè)文法G；(2) 輸出由文法G構(gòu)造FIRSTVT集的算法；(3) 輸出FIRSTVT集； (4) 輸出由文法G構(gòu)造LASTVT集的算法；(5) 輸出LASTVT集。2創(chuàng)新要求：用界面的形式來(lái)展現(xiàn)這個(gè)結(jié)果集，這樣顯得更加的美觀。3課程設(shè)計(jì)論文編寫(xiě)要求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é)果，有何改良想法等。5設(shè)計(jì)體會(huì)與小結(jié)-設(shè)計(jì)遇到的問(wèn)題及解決方法，通過(guò)設(shè)計(jì)學(xué)到了哪些新知識(shí)，穩(wěn)固了哪些知識(shí)，有哪些提高。6報(bào)告按規(guī)定排版打印，要求裝訂平整，否那么要求返工；7課設(shè)報(bào)告的裝訂順序如下：封面-任務(wù)書(shū)-中文摘要-目錄-正文-附錄(代碼及相關(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答復(fù)下列問(wèn)題：20分；5論文撰寫(xiě)：20分。5參考文獻(xiàn)：1張素琴，呂映芝. 編譯原理M., 清華大學(xué)出版社2蔣立源、康慕寧等，編譯原理第2版M，西安：西北工業(yè)大學(xué)出版社6課程設(shè)計(jì)進(jìn)度安排1準(zhǔn)備階段4學(xué)時(shí)

4、：選擇設(shè)計(jì)題目、了解設(shè)計(jì)目的要求、查閱相關(guān)資料2程序模塊設(shè)計(jì)分析階段4學(xué)時(shí)：程序總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)3代碼編寫(xiě)調(diào)試階段8學(xué)時(shí)：程序模塊代碼編寫(xiě)、調(diào)試、測(cè)試4撰寫(xiě)論文階段4學(xué)時(shí)：總結(jié)課程設(shè)計(jì)任務(wù)和設(shè)計(jì)內(nèi)容，撰寫(xiě)課程設(shè)計(jì)論文學(xué)生簽名： 2021 年 6 月 21 日課程設(shè)計(jì)(論文)評(píng)審意見(jiàn)1學(xué)習(xí)態(tài)度20分：優(yōu)、良、中、一般、差； 2系統(tǒng)設(shè)計(jì)20分：優(yōu) 、良、中、一般、差； 3編程調(diào)試20分：優(yōu)、良、中、一般、差；4答復(fù)下列問(wèn)題20分：優(yōu)、良、中、一般、差；5論文撰寫(xiě)20分：優(yōu)、良、中、一般、差； 評(píng)閱人： 職稱(chēng)： 副教授 2021 年 6 月 26 日目錄緒論4正文4設(shè)計(jì)實(shí)現(xiàn)10測(cè)試數(shù)據(jù)運(yùn)行結(jié)果分析

5、12課程設(shè)計(jì)總結(jié)13參考文獻(xiàn)14緒論隨著計(jì)算機(jī)科學(xué)的飛速開(kāi)展，形式語(yǔ)言與自動(dòng)機(jī)理論和方法的研究也越來(lái)越受到人們的重視，但前者已經(jīng)成為計(jì)算機(jī)科學(xué)的理論根底。本課程設(shè)計(jì)主要研究自動(dòng)機(jī)在編譯方面的應(yīng)用，并將討論重點(diǎn)放在算符優(yōu)先分析法上，并用此理論完成算數(shù)表達(dá)式的正確與否的判斷。根據(jù)算符優(yōu)先分析算法，編寫(xiě)一個(gè)語(yǔ)法程序，程序具有通用性，即編制的語(yǔ)法縫隙程序能夠適用于不同文法以及各種輸入的單詞串。根本思想描述，語(yǔ)法分析前首先要對(duì)輸入的文法和句子進(jìn)行詞法分析，去除多余的自負(fù)，并將產(chǎn)生式和終結(jié)符、非終結(jié)符填入有關(guān)數(shù)組，為語(yǔ)法分析做前期準(zhǔn)備。算符優(yōu)先分析算法的核心算法教材上已給出，因此所要做的事只是將其變成實(shí)現(xiàn)

6、。正文設(shè)計(jì)目的本課程設(shè)計(jì)的題目為“FirstVT集和LastVT集生成算法模擬，它是算符優(yōu)先分析算法中判斷三種優(yōu)先關(guān)系的關(guān)鍵。算符優(yōu)先分析算法是自底向上分析方法的一種。所謂自底向上分析，也稱(chēng)移近規(guī)約分析，粗略地說(shuō)它的實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出的棧中，邊移進(jìn)邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄或可規(guī)約串，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱(chēng)為一部規(guī)約。重復(fù)這一過(guò)程直到規(guī)約到棧中只剩文法的開(kāi)始符號(hào)那么為分析成功，也就確認(rèn)輸入串是該文法的句子。而算符優(yōu)先分析算法的根本思想只是規(guī)定算符之間的優(yōu)先關(guān)系，也就是只考慮終結(jié)符之間的優(yōu)先關(guān)系。

7、本課程設(shè)計(jì)的要求只是構(gòu)造FirstVT集和LastVT集，在此根底上擴(kuò)充建造算符優(yōu)先關(guān)系表。問(wèn)題描述設(shè)計(jì)一個(gè)給定文法和對(duì)應(yīng)的FIRSTVT和LASTVT集，能依據(jù)依據(jù)文法和FIRSTVT和LASTVT生成算符優(yōu)先分析表?？梢詣?dòng)態(tài)模擬算法的根本功能，通過(guò)輸入一個(gè)給定文法，及FIRSTVT和LASTVT集，此題目以文法GE為測(cè)試數(shù)據(jù): 文法GE:E->TEE->+TE|T->FTT->*FT|F->(E)|i該文法有對(duì)應(yīng)的FIRSTVT(E)= +, * ,( ,i LASTVT(E)= +，*，),i FIRSTVT(E')= + LASTVT(E'

8、)= +，*，),i FIRSTVT(T)= * ,( ,i LASTVT(T)= *，),i FIRSTVT(T')= * LASTVT(T')= *，),i FIRSTVT(F)= ( ,i LASTVT(F)= ),i 通過(guò)算符優(yōu)先關(guān)系表構(gòu)造算法： 給定文法中任何二個(gè)終結(jié)符對(duì)(a,b)之間的優(yōu)先關(guān)系有三種優(yōu)先關(guān)系計(jì)算為：關(guān)系：可以直接查看產(chǎn)生式的右部，對(duì)如下形式的產(chǎn)生式：Aab或 AaBb那么有a=b成立。 關(guān)系：求出每個(gè)非終結(jié)符B的FIRSTVT(B)，觀察如下形式的產(chǎn)生式：AaB對(duì)每一bFIRSTVT(B)，有ab成立。 關(guān)系：計(jì)算每個(gè)非終結(jié)符B的LASTVT(B)，

9、觀察如下形式的產(chǎn)生式： ABb對(duì)每一aLASTVT(B)，有ab成立。 這樣，對(duì)于給定的文法和對(duì)應(yīng)的FIRSTVT和LASTVT集，通過(guò)二個(gè)終結(jié)符之間的優(yōu)先關(guān)系表構(gòu)造算法，可以得到算法優(yōu)先分析表構(gòu)造過(guò)程的過(guò)程和算符優(yōu)先分析表生成算法。 所以，我們的重點(diǎn)應(yīng)該放在算符優(yōu)先分析表的生成算法上，解決了這一問(wèn)題，也就可以得到我們想要的結(jié)果，算法優(yōu)先分析表以及分析過(guò)程。其中，對(duì)于FIRSTVT集和LASTVT集的表示可以采取集合的方式，同樣也可以采用關(guān)系圖法進(jìn)行表示?？傮w設(shè)計(jì)算符優(yōu)先分析表的構(gòu)造原理：通過(guò)檢查文法G的每個(gè)產(chǎn)生式的每個(gè)候選式，可以首先找出滿足ab的終結(jié)符對(duì)；為了找出所有滿足關(guān)系和的終結(jié)符對(duì)，

10、我們首先需要對(duì)文法G的每個(gè)非終結(jié)符P構(gòu)造二個(gè)集合FIRSTVTP和LASTVT(P)。1. FirstVT集的構(gòu)造FIRSTVT(P=a|P=>+a或P=>+Qa，aVT而QVN 假設(shè)有產(chǎn)生式：Pa或PQa,那么aFIRSTVT(P)；假設(shè)aFIRSTVT(Q)，且有產(chǎn)生式PQ，那么aFIRSTVT(P)。2. LastVT集的構(gòu)造LASTVT(P)= a|P=>+a或P=>+aQ，aVT而QVN 假設(shè)有產(chǎn)生式：Ua或UaV, 那么aLASTVT(U)；假設(shè)aLASTVT(V)，且有產(chǎn)生式UV，那么aLASTVT(U)。當(dāng)我們有了這二個(gè)集合之后，就可以通過(guò)檢查每個(gè)產(chǎn)生式

11、的候選式確定滿足關(guān)系的“和“的所有終結(jié)符對(duì)。我們假定有產(chǎn)生式的一個(gè)侯選式形為aP，那么，對(duì)任何bFIRSTVT(P，ab；假定有產(chǎn)生式的一個(gè)候選形為Pb，那么，對(duì)任何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：在算符文法中任何句型都不包含兩個(gè)相鄰的非終結(jié)符。性質(zhì)2：如果Aa或者bA出現(xiàn)在算符文法的句型S中，其中A是非終結(jié)符，b是終結(jié)符，那么S中任何含此b的短語(yǔ)必含有A。1. FirstVT集的構(gòu)造，算法描述：假設(shè)有產(chǎn)生式A->a

12、或A->Ba，那么a屬于FirstVTA，其中A、B為非終結(jié)符，a為終結(jié)符。 ：假設(shè)a屬于FirstVTB且有產(chǎn)生式A->B那么有a屬于FirstVTA。為了計(jì)算方便，建立一個(gè)布爾數(shù)組Fm,nm為非終結(jié)字符的個(gè)數(shù)，n為終結(jié)字符的個(gè)數(shù)和一個(gè)后進(jìn)先出棧STACK。將所有的非終結(jié)符排序，用iA表示非終結(jié)符A的序號(hào)，再將所有的終結(jié)符排序，用ia表示終結(jié)符a的序號(hào)。算法的目的是要使數(shù)組的一個(gè)元素最終取值滿足：FiA,ja的值為真，當(dāng)且僅當(dāng)a屬于FirstVTA。至此，顯然所有的非終結(jié)符的FirstVT集已完全確定。步驟如下：首先按規(guī)那么對(duì)每個(gè)數(shù)組元素附初值。觀察這些初值，假設(shè)FiA,ia的值

13、是真，那么將A，a推入棧中，直至對(duì)所有數(shù)組的初值都按此處理完。然后對(duì)棧做如下運(yùn)算。將棧頂項(xiàng)彈出，那么令其變?yōu)檎?，且將A，a推進(jìn)棧，如此重復(fù)直到棧彈空為止。假設(shè)表達(dá)式文法為：0 E'# E #1 EE + T2 ET3 TT*F4 TF5 FPF | P6 P(E)7 Pi計(jì)算每個(gè)非終結(jié)符的FirstVT集和LastVT集得到如下結(jié)果：FIRSTVT(E') = # FIRSTVT(E) = +，*，iFIRSTVT(T) = *，iFIRSTVT(F) = ，iFIRSTVT(P)=，i2. LastVT集的構(gòu)造，算法描述：用于構(gòu)建輸入文法的LastVT集假設(shè)有規(guī)那么U:=a或

14、U:=aV,那么a屬于LastVTU假設(shè)有規(guī)那么U:=V,且a屬于LastVTV那么a屬于LastVTU設(shè)一個(gè)棧STACK，和一個(gè)布爾數(shù)組BProcedureInsertU，a IF NOT BU,a THEN BEGIN BU,a:=TRUE;把U，a推進(jìn)STACK棧； END；BEGIN FOR 每個(gè)非終結(jié)符號(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 沒(méi)條形如U:=V的規(guī)那么 DO INSERT(U,a); EN

15、D 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，上托出去； For每條形如P->Q的產(chǎn)生式 InsertP，a End of while； END針對(duì)上述算法可得到每個(gè)非終結(jié)符的LastVT集如下：LASTVT(E') = # LASTVT(E) +，*，iLASTVT(T) *，iLASTVT(F) ，iLAVSTVT(P)，i 算符優(yōu)先

16、分析流程圖圖1算符優(yōu)先分析流程圖設(shè)計(jì)實(shí)現(xiàn).主要數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)描述：本課程設(shè)計(jì)主要采用棧的數(shù)據(jù)結(jié)構(gòu)，定義一個(gè)棧的類(lèi)，類(lèi)中主要成員函數(shù)實(shí)現(xiàn)棧的一些根本操作，如：push為入棧操作，pop為出棧操作，empty判斷棧中是否為空，clear用于對(duì)棧進(jìn)行清空處理，核心代碼為： 建立FirstVT函數(shù)集和SetFirstVT，用來(lái)得到相應(yīng)文法中所對(duì)應(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=f

17、alse; for(i=0;i<=Ptnum;i+) if(Vt.Find(Pti.pright0)!=-1) InsertFirstOrLast(Pti.pleft,Pti.pright0,"First"); if(Pti.pright.GetLength()>=2)if(Vn.Find(Pti.pright0)!=-1 && Vt.Find(Pti.pright1)!=-1)InsertFirstOrLast(Pti.pleft,Pti.pright1,"First"); while(!stack.empty() stac

18、k.pop(Q,a); for(i=0;i<Ptnum;i+) if(Pti.pright0=Q) InsertFirstOrLast(Pti.pleft,a,"First"); 建立LastVT集函數(shù)和SetLastVT函數(shù)，用來(lái)得到相應(yīng)文法中所有非終結(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

19、.Find(Pti.pright.Right(1)0) InsertFirstOrLast(Pti.pleft,Pti.pright.Right(1)0,"Last"); if(Pti.pright.GetLength()>=2) if(Vt.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");測(cè)試數(shù)據(jù)運(yùn)行結(jié)果分析1、 測(cè)試數(shù)據(jù)如下，文法GSS# E #EE + TETTT*FTFFP-F | PP(E)|i它對(duì)性的FirstVT集和LastVT集為：FIRSTVT(S) = # FIRSTVT(E) = +，*，-，iFIRSTVT(T) = *，-，iFIRSTVT(F)