編譯原理課程設(shè)計(jì)-LL1文法分析器設(shè)計(jì)C++語(yǔ)言實(shí)現(xiàn)

1、集美大學(xué)計(jì)算機(jī)工程學(xué)院編譯原理課程設(shè)計(jì)報(bào)告選題名稱: LL（1）文法分析 院（系）: 計(jì)算機(jī)工程學(xué)院專 業(yè): 計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí): 計(jì)算1412 指導(dǎo)教師: 付永剛 學(xué)年學(xué)期: 2016 2017 學(xué)年 第 2 學(xué)期 2017年 06 月 29 日摘要：選題要求：根據(jù)某一文法編制調(diào)試LL(1) 文法語(yǔ)法分分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。本次課程設(shè)計(jì)的目的主要是加深對(duì)預(yù)測(cè)分析LL(1)文法語(yǔ)法分析法的理解。具體如下：1、對(duì)語(yǔ)法規(guī)則有明確的定義；2、編寫(xiě)的分析程序能夠?qū)o定文法進(jìn)行正確的語(yǔ)法分析；3、對(duì)輸入給定的文法，手工計(jì)算FIRST、FOLLOW集合和select集合，應(yīng)能判斷識(shí)

2、別是否為給定文法的句子，并給出推導(dǎo)過(guò)程。4、對(duì)輸入給定的文法，由程序自動(dòng)構(gòu)造FIRST、FOLLOW集合。5、對(duì)于遇到的語(yǔ)法錯(cuò)誤，能夠做出簡(jiǎn)單的錯(cuò)誤處理，給出簡(jiǎn)單的錯(cuò)誤提示，保證順利完成語(yǔ)法分析過(guò)程。關(guān)鍵詞：語(yǔ)法分析；FIRST集合；FOLLOW集合；分析表一、設(shè)計(jì)內(nèi)容及要求(1) 基于PL/0語(yǔ)言，通過(guò)編程判斷該文法是否為L(zhǎng)L(1)文法； (2)計(jì)算出文法的First() Follow()(3)構(gòu)造相應(yīng)文法的預(yù)測(cè)分析表(4)對(duì)某個(gè)輸入句子進(jìn)行語(yǔ)法分析二、實(shí)現(xiàn)原理1LL(1)文法LL(1)文法是一類可以進(jìn)行確定的自頂向下語(yǔ)法分析的文法。就是要求描述語(yǔ)言的文法是無(wú)左遞歸的和無(wú)回溯的。根據(jù)LL(1

3、)文法的定義，對(duì)于同一非終結(jié)符A的任意兩個(gè)產(chǎn)生式A:=a和A:=b，都要滿足：SELECT(A：=a )SELECT(A:=b)=。（1）文法的左遞歸當(dāng)一個(gè)文法是左遞歸文法時(shí)，采用自頂向下分析法會(huì)使分析過(guò)程進(jìn)入無(wú)窮循環(huán)之中。所以采用自頂向下語(yǔ)法分析需要消除文法的左遞歸性。文法的左遞歸是指若文法中對(duì)任一非終結(jié)符A有推導(dǎo)AA，則稱該文法是左遞歸的。左遞歸又可以分為直接左遞歸和間接左遞歸。 直接左遞歸若文法中的某一產(chǎn)生式形如AA，V*，則稱該文法是直接左遞歸的。消除直接左遞歸的方法：設(shè)有產(chǎn)生式是關(guān)于非終結(jié)符A的直接左遞歸：AA| （,V*，且不以A開(kāi)頭）對(duì)A引入一個(gè)新的非終結(jié)符A，把上式改寫(xiě)為：A

4、A AA| 間接左遞歸若文法中存在某一非終結(jié)符A，使得AA至少需要兩步推導(dǎo)，則稱該文法是間接左遞歸的。消除間接左遞歸的方法：【方法一】采用代入法把間接左遞歸變成直接左遞歸。 【方法二】直接改寫(xiě)文法：設(shè)有文法G10S： SA| AS 因?yàn)镾AS，所以S是一個(gè)間接遞歸的非終結(jié)符。為了消除這種間接左遞歸，將式代入式，即可得到與原文法等價(jià)的文法（可以證明）： SS| 式是直接左遞歸的，可以采用前面介紹的消除直接左遞歸的方法，對(duì)文法進(jìn)行改寫(xiě)后可得文法：SSSS|2. 計(jì)算First集(1) 若XVT ，則First(X)=X(2) 若XVN ，且有產(chǎn)生式Xa, aVT則First(X)=X(3) 若XV

5、N ，且有產(chǎn)生式X,則First(X)=X(4) 若X，Y1 ，Y2 ，Yn 都VN，而由產(chǎn)生式XY1 Y2 Yn 。當(dāng)Y1 ，Y2 ，Yi-1都能推導(dǎo)出時(shí)，（其中1in），則First(Y1)-, First(Y2)-, First(Yi)都包含在First(X)中(5)當(dāng)(4)中所有Yi都能推導(dǎo)出，（i=1，2，n），則First(X)=First(Y1)First(Y2)First(Yn)反復(fù)使用上述步驟直到每個(gè)符合的First集合不再增大為止。3. 計(jì)算Follow集對(duì)文法中的每個(gè)AVN，計(jì)算Follw(A)：(1) 設(shè)S為文法的開(kāi)始符合，把#加入Follow(S)中；(2) 若AB是

6、一個(gè)產(chǎn)生式，則把First()的非空元素加入Follow(B)中，如果能推導(dǎo)出，則把Follow(A)也加入(B)中；(3) 反復(fù)使用以上步驟直到每個(gè)非終結(jié)符號(hào)的Follow集不再增大為止。4. 預(yù)測(cè)分析方法預(yù)測(cè)分析方法是自頂向下分析的另一種方法，一個(gè)預(yù)測(cè)分析器是由三個(gè)部分組成：預(yù)測(cè)分析程序；先進(jìn)后出棧；預(yù)測(cè)分析表。預(yù)測(cè)分析程序的框圖如下：目錄1系統(tǒng)分析11.1選題要求11.2預(yù)期目標(biāo)12.程序流程圖12.1總流程圖12.2First集和Follow集22.3預(yù)測(cè)分析表流程33.代碼編寫(xiě)33.1檢查左遞歸33.2first集合53.3follow集合63.4分析表輸出84.程序調(diào)試105.總結(jié)

7、116.指導(dǎo)教師評(píng)語(yǔ)127.源碼13正文：1.系統(tǒng)分析 1.1選題要求根據(jù)某一文法編制調(diào)試LL(1) 文法語(yǔ)法分分析程序，以便對(duì)任意輸入的符 號(hào)串進(jìn)行分析。本次課程設(shè)計(jì)的目的主要是加深對(duì)預(yù)測(cè)分析LL(1)文法語(yǔ)法分析法的理解。 1.2預(yù)期目標(biāo)構(gòu)造LL(1)文法語(yǔ)法分析程序，任意輸入一個(gè)文法符號(hào)串，并判斷它是否為文法的一個(gè)句子。程序要求為該文法構(gòu)造預(yù)測(cè)分析表，并按照預(yù)測(cè)分析算法對(duì)輸入串進(jìn)行語(yǔ)法分析，判別程序是否符合已知的語(yǔ)法規(guī)則，如果不符合（編譯出錯(cuò)），則輸出錯(cuò)誤信息。2. 程序流程圖 21.總流程圖2.2.First集和Follow集的流程圖2.3.預(yù)測(cè)分析表流程：3. 代碼編寫(xiě) 3.1檢查左

8、遞歸：Parser& Parser:DelLeft(int i) int n=StrNum(contenti); char c=RandChar(); char z=contenti0; int s=0; for(int k=1;k=n;k+) string tmp=GetSub(k,contenti,|); if(z=tmp0) s=1; if(s=0) return *this; cout文法句contenti含有直接左遞歸,; while(1) if(Findchar(c,non)=-1) break; else c=RandChar(); cout隨機(jī)產(chǎn)生非終結(jié)符為:c; string

9、 next; next+=c; next+=-; for(int k=1;ki;j-) contentj=contentj-1; contenti+1=next; return *this;3.2 first集合string Parser:First(char x) string ch=; if(Findchar(x,ter)!=-1) ch.append(1,x); ch.append(1, ); else if(Findchar(x,non)!=-1) int i=Findid(x); if(i!=-1) string q=contenti; unsigned int k=3; while

10、(kq.size() if(qk-1=|k=3) if(Findchar(qk,ter)!=-1|qk=) ch.append(1,qk); ch.append(1, ); else if(k=3|qk+1=|k=q.size()-1) ch+=First(qk); else string temp=First(qk-1); if(Findchar(,temp)!=-1) ch+=First(qk); k+; else k+; return ch;3.3 follow集合string Parser:Follow(char x) string ch; if(Findchar(x,non)!=-1

11、) if(!Findid(x) ch+=$; ch+= ; int i=0; while(inum) string q=contenti; unsigned int k=3; char c=contenti0; while(kq.size() while(qk=x) if(kq.size()-1&qk+1!=|) string temp=Delchar(,First(qk+1); if(ch.find(temp)=string:npos) ch+=temp; if(Findchar(,First(qk+1)!=-1) string follow_c = Follow(c); if(ch!=fo

12、llow_c&ch.find(follow_c)=std:string:npos) ch+=follow_c; else if(k=q.size()-1) string follow_c = Follow(c); if(ch.find(follow_c)=std:string:npos) ch+=follow_c; k+; k+; i+; return ch;3.4 分析表輸出int Parser:Analysis() stack.append($);char chose;coutchose;while(chose=y)stack+=non0;cout請(qǐng)輸入分析串：;cininstack;if

13、 (instack=q) exit(0);if(instackinstack.size()-1!=$) instack+=$;int k=1,flag=0; char x=Top();char c=Ip();cout分析棧t當(dāng)前輸入t動(dòng)作endl;while(x!=$)x=Top();c=Ip();coutstacktinstacktt;if(Findchar(x,ter)!=-1)if(Mate(x,c) k+;cout匹配cendl;elsecoutk出錯(cuò)(終結(jié)符不匹配)！endl;flag=1;if(x=) Pop();else instack.erase(0,1); k+;else i

14、f(Findchar(x,non)!=-1)int idf=Findchar(x,non);int idz=Findchar(c,ter);if(idz=-1) idz=int(ter.size();string temp=tableidfidz;if(temp.empty() coutk出錯(cuò)（c不屬于FIRST(x)）！endl;flag=1;instack.erase(0,1); k+;elsePop();if(temp!=) Push(temp);coutxtempendl;else coutxtempendl;else if(x=$&c=$)if(flag=0) cout正確endl;

15、else cout錯(cuò)誤endl;elsecoutk出錯(cuò)(未能識(shí)別的字符)！endl;flag=1;instack.erase(0,1); k+;4. 程序調(diào)試導(dǎo)入正確的文法：符合文法的串不符合文法的串導(dǎo)入有左遞歸的文法：串分析： 總 結(jié)通過(guò)這次課程設(shè)計(jì)，對(duì)于LL1文法的認(rèn)識(shí)有了進(jìn)一步的提升，特別是對(duì)于FIRST集合和FOLLOW集合的求取，前面對(duì)于求取者兩個(gè)集合理解還不是很好，經(jīng)過(guò)這次課程設(shè)計(jì)，逐漸理解了求解的過(guò)程，并且懂得了如何通過(guò)代碼，自動(dòng)生成某LL1文法的FIRST集合和FOLLOW集合，在剛開(kāi)始做時(shí)，根本不知道求，通過(guò)網(wǎng)上查找資料，同學(xué)的請(qǐng)教，慢慢地懂得了如何做，最終正確地求出FIRS

16、T集合和FOLLOW集合。并且能夠使用者兩個(gè)集合構(gòu)建預(yù)測(cè)分析表以及對(duì)一段輸入的串進(jìn)行分析是否是該文法的串，出錯(cuò)的地方能夠做出錯(cuò)處理，總的來(lái)說(shuō)，完成了課程設(shè)計(jì)要求的大部分內(nèi)容，對(duì)于GUI的使用沒(méi)有能夠?qū)崿F(xiàn)，暴露了自身在這方面的不足，需要在以后的學(xué)習(xí)和工作中進(jìn)行沉入學(xué)習(xí)提高。在實(shí)現(xiàn)的功能中還有存在著，對(duì)于不含直接左遞歸的文法沒(méi)法正確找出，提示錯(cuò)誤。在判斷是否是LL1文法上還有很大的不足，沒(méi)法使用代碼實(shí)現(xiàn)當(dāng)兩個(gè)FIRST有存在交集判斷不是LL1文法的功能，這點(diǎn)要求自己對(duì)于代碼的編程能力有著必要的提高。這次課程設(shè)計(jì)使用C+來(lái)實(shí)現(xiàn)LL1文法分析的功能，自己對(duì)于C+語(yǔ)言的使用有了很大的提高。特別是對(duì)于一些

17、C+的語(yǔ)法要求，有了很大的認(rèn)識(shí)。但存在的不足還是比較多的。都是需要在今后的學(xué)習(xí)中認(rèn)真總結(jié)，以使自己能更好地語(yǔ)言的使用，提升自身的技能。這次課程設(shè)計(jì)總的收獲是不少的。每一次的實(shí)踐都是提高自身能力的機(jī)會(huì)，在今后的生活中，要抓住實(shí)踐的機(jī)會(huì)，實(shí)踐是驗(yàn)證真理最好的途徑。對(duì)于一個(gè)計(jì)算機(jī)專業(yè)的學(xué)生來(lái)說(shuō)，更應(yīng)該注重實(shí)踐的機(jī)會(huì)，只有實(shí)踐多了，一些理論知識(shí)才能被自己正真的認(rèn)識(shí)，不然，值懂理論，沒(méi)有對(duì)于正確性進(jìn)行驗(yàn)證，還是會(huì)有問(wèn)題的，特別是計(jì)算機(jī)機(jī)器，總存在未知的錯(cuò)誤，只有不斷地探索，才能更好地去使用我們的工具。指導(dǎo)教師評(píng)語(yǔ)學(xué)號(hào)姓名班級(jí)選題名稱序號(hào)評(píng)價(jià)內(nèi)容權(quán)重（%）得分1考勤記錄、學(xué)習(xí)態(tài)度、工作作風(fēng)與表現(xiàn)。52自學(xué)

18、情況：上網(wǎng)檢索機(jī)時(shí)數(shù)、文獻(xiàn)閱讀情況（筆記）。103論文選題是否先進(jìn)，是否具有前沿性或前瞻性。54成果驗(yàn)收：是否完成設(shè)計(jì)任務(wù)；能否運(yùn)行、可操作性如何等。205報(bào)告的格式規(guī)范程度、是否圖文并茂、語(yǔ)言規(guī)范及流暢程度；主題是否鮮明、重心是否突出、論述是否充分、結(jié)論是否正確；是否提出了自己的獨(dú)到見(jiàn)解。306文獻(xiàn)引用是否合理、充分、真實(shí)。57答辯情況： 自我陳述、回答問(wèn)題的正確性、用語(yǔ)準(zhǔn)確性、邏輯思維、是否具有獨(dú)到見(jiàn)解等。25合計(jì)指導(dǎo)教師（簽章）： 年 月 日 源碼：LL1.h#include #include #include #include using namespace std; class Pa

19、rserpublic: Parser(); Parser(const Parser&); friend ostream& operator(istream& input,Parser& rs); int Findid(char); int Check(); string Checkstr(string&); string Delchar(char,string); int Findchar(char,string); int StrNum(const string&); char RandChar(); string GetSub(int,const string&,char); Parser

20、& DelLeft(int); string First(char); string First(const string&); string Follow(char); Parser& FirstAndFollow(); Parser& CreateTable(); Parser(); char Pop(); int Mate(char,char); char Top(); char Ip(); Parser& Push(const string&); int Analysis();private: int num; string ter,non,end,stack,instack; str

21、ing *content; string *first; string *follow; string *table;LL1.cpp#include LL1.hParser:Parser() content=new string255; first=new string255; follow=new string255; table=new string *255; Parser:Parser(const Parser& rs) ter=rs.ter; non=rs.non; end=rs.end; num=rs.num; content=new string255; first=new st

22、ring255; follow=new string255; table=new string *255; for(int i=0;i=num;i+) contenti=rs.contenti; FirstAndFollow(); CreateTable(); ostream& operator(ostream& output,const Parser& rs)output文法內(nèi)容(共rs.num條):endl;int i=0;while(irs.num)outputrs.contenti+endl;output結(jié) 終 符:rs.terendl;output非結(jié)終符:rs.nonendl;co

23、ut非終結(jié)符的FIRST集合 endl;for(unsigned int j=0;jrs.non.size();j+)coutFIRST(rs.nonj) = rs.firstjtendl;cout非終結(jié)符的FOLLOW集合 endl;for(unsigned int j=0;jrs.non.size();j+)coutFOLLOW(rs.nonj) = rs.followjtendl;output預(yù)測(cè)分析表:endlt;for(unsigned int j=0;jrs.ter.size();j+)outputrs.terjt;output$endl;for(unsigned int j=0;

24、jrs.non.size();j+)outputrs.nonjt;for(unsigned int k=0;k=rs.ter.size();k+)coutrs.tablejkt;output(istream& input,Parser& rs)unsigned int j=0;char filename255;coutfilename;ifstream infile(filename,ios:in);if(!infile)cout無(wú)法打開(kāi)文件！rs.end; rs.contentj+=rs.end;if(infile.eof() break;while(i=A&rs.endi=Z)if(std

25、:string:npos=rs.non.find(rs.endi) rs.non.append(1,rs.endi);else if(std:string:npos=rs.ter.find(rs.endi) rs.ter.append(1,rs.endi);i+;rs.num=j-1;if(rs.Check()=0)exit(0);rs.FirstAndFollow();rs.CreateTable();return input; int Parser:Findid(char a) int i=0; while(inum) if(contenti0=a) return i; i+; retur

26、n -1; char Parser:RandChar() switch(rand()%3) case 0:return A; case 1:return B; case 2:return C; case 3:return D; return D; int Parser:Check() unsigned int j=0; int i=0; while(inum) if(contenti.size()=3) cout文法句contenti長(zhǎng)度不對(duì)!) cout文法句contenti!endl; return 0; int n=StrNum(contenti); int s=0; char z=co

27、ntenti0; int m=0; for(int k=1;k=n;k+) string tmp=GetSub(k,contenti,|); if(z=tmp0) s=1; m+; if(m=n) cout文法句contenti將形成無(wú)窮推導(dǎo)！endl; return 0; if(s=1) DelLeft(i); i+; return 1; Parser& Parser:DelLeft(int i) int n=StrNum(contenti); char c=RandChar(); char z=contenti0; int s=0; for(int k=1;k=n;k+) string t

28、mp=GetSub(k,contenti,|); if(z=tmp0) s=1; if(s=0) return *this; cout文法句contenti含有直接左遞歸,; while(1) if(Findchar(c,non)=-1) break; else c=RandChar(); cout隨機(jī)產(chǎn)生非終結(jié)符為:c; string next; next+=c; next+=-; for(int k=1;ki;j-) contentj=contentj-1; contenti+1=next; return *this; string Parser:Checkstr(string & a)

29、unsigned int i=0,j=0; for(;ia.size();i+) for(j=i+1;ja.size();j+) if(ai=aj) a.erase(j,1); return a; string Parser:Delchar(char x,string a) int j,i=int(a.size(); for(j=0;ji;j+) if(aj=x) a.erase(j,1); return a; int Parser:Findchar(char x,string a) unsigned int i=0; while(i=int(a.size() return ch; for(u

30、nsigned int k=3;ka.size();k+) if(ak=c) jn+=k; for(unsigned int k=ji-1+1;ka.size();k+) if(ak=c) break; else if(std:string:npos=ch.find(ak) ch.append(1,ak); return ch; int Parser:StrNum(const string& a) int n=0; for(unsigned int i=3;ia.size();i+) if(ai=|) n+; return n+1; string Parser:First(char x) st

31、ring ch=; if(Findchar(x,ter)!=-1) ch.append(1,x); ch.append(1, ); else if(Findchar(x,non)!=-1) int i=Findid(x); if(i!=-1) string q=contenti; unsigned int k=3; while(kq.size() if(qk-1=|k=3) if(Findchar(qk,ter)!=-1|qk=) ch.append(1,qk); ch.append(1, ); else if(k=3|qk+1=|k=q.size()-1) ch+=First(qk); el

32、se string temp=First(qk-1); if(Findchar(,temp)!=-1) ch+=First(qk); k+; else k+; return ch; string Parser:First(const string& a) return First(a0); string Parser:Follow(char x) string ch; if(Findchar(x,non)!=-1) if(!Findid(x) ch+=$; ch+= ; int i=0; while(inum) string q=contenti; unsigned int k=3; char c=contenti0; while(kq.size() while(qk=x) if(kq.size()-1&qk+1!=|) string temp=Delchar(,First(qk+1); if(ch.find(temp)=string:npos) ch+=temp; if(Findchar(,First(qk+1)!=-