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

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

3、)文法的定義，對于同一非終結符A的任意兩個產生式A:=a和A:=b，都要滿足：SELECT(A：=a )SELECT(A:=b)=。（1）文法的左遞歸當一個文法是左遞歸文法時，采用自頂向下分析法會使分析過程進入無窮循環之中。所以采用自頂向下語法分析需要消除文法的左遞歸性。文法的左遞歸是指若文法中對任一非終結符A有推導AA，則稱該文法是左遞歸的。左遞歸又可以分為直接左遞歸和間接左遞歸。 直接左遞歸若文法中的某一產生式形如AA，V*，則稱該文法是直接左遞歸的。消除直接左遞歸的方法：設有產生式是關于非終結符A的直接左遞歸：AA| （,V*，且不以A開頭）對A引入一個新的非終結符A，把上式改寫為：A

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

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

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

7、116.指導教師評語127.源碼13正文：1.系統分析 1.1選題要求根據某一文法編制調試LL(1) 文法語法分分析程序，以便對任意輸入的符 號串進行分析。本次課程設計的目的主要是加深對預測分析LL(1)文法語法分析法的理解。 1.2預期目標構造LL(1)文法語法分析程序，任意輸入一個文法符號串，并判斷它是否為文法的一個句子。程序要求為該文法構造預測分析表，并按照預測分析算法對輸入串進行語法分析，判別程序是否符合已知的語法規則，如果不符合（編譯出錯），則輸出錯誤信息。2. 程序流程圖 21.總流程圖2.2.First集和Follow集的流程圖2.3.預測分析表流程：3. 代碼編寫 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隨機產生非終結符為: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請輸入分析串：;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當前輸入t動作endl;while(x!=$)x=Top();c=Ip();coutstacktinstacktt;if(Findchar(x,ter)!=-1)if(Mate(x,c) k+;cout匹配cendl;elsecoutk出錯(終結符不匹配)！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出錯（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錯誤endl;elsecoutk出錯(未能識別的字符)！endl;flag=1;instack.erase(0,1); k+;4. 程序調試導入正確的文法：符合文法的串不符合文法的串導入有左遞歸的文法：串分析： 總 結通過這次課程設計，對于LL1文法的認識有了進一步的提升，特別是對于FIRST集合和FOLLOW集合的求取，前面對于求取者兩個集合理解還不是很好，經過這次課程設計，逐漸理解了求解的過程，并且懂得了如何通過代碼，自動生成某LL1文法的FIRST集合和FOLLOW集合，在剛開始做時，根本不知道求，通過網上查找資料，同學的請教，慢慢地懂得了如何做，最終正確地求出FIRS

16、T集合和FOLLOW集合。并且能夠使用者兩個集合構建預測分析表以及對一段輸入的串進行分析是否是該文法的串，出錯的地方能夠做出錯處理，總的來說，完成了課程設計要求的大部分內容，對于GUI的使用沒有能夠實現，暴露了自身在這方面的不足，需要在以后的學習和工作中進行沉入學習提高。在實現的功能中還有存在著，對于不含直接左遞歸的文法沒法正確找出，提示錯誤。在判斷是否是LL1文法上還有很大的不足，沒法使用代碼實現當兩個FIRST有存在交集判斷不是LL1文法的功能，這點要求自己對于代碼的編程能力有著必要的提高。這次課程設計使用C+來實現LL1文法分析的功能，自己對于C+語言的使用有了很大的提高。特別是對于一些

17、C+的語法要求，有了很大的認識。但存在的不足還是比較多的。都是需要在今后的學習中認真總結，以使自己能更好地語言的使用，提升自身的技能。這次課程設計總的收獲是不少的。每一次的實踐都是提高自身能力的機會，在今后的生活中，要抓住實踐的機會，實踐是驗證真理最好的途徑。對于一個計算機專業的學生來說，更應該注重實踐的機會，只有實踐多了，一些理論知識才能被自己正真的認識，不然，值懂理論，沒有對于正確性進行驗證，還是會有問題的，特別是計算機機器，總存在未知的錯誤，只有不斷地探索，才能更好地去使用我們的工具。指導教師評語學號姓名班級選題名稱序號評價內容權重（%）得分1考勤記錄、學習態度、工作作風與表現。52自學

18、情況：上網檢索機時數、文獻閱讀情況（筆記）。103論文選題是否先進，是否具有前沿性或前瞻性。54成果驗收：是否完成設計任務；能否運行、可操作性如何等。205報告的格式規范程度、是否圖文并茂、語言規范及流暢程度；主題是否鮮明、重心是否突出、論述是否充分、結論是否正確；是否提出了自己的獨到見解。306文獻引用是否合理、充分、真實。57答辯情況： 自我陳述、回答問題的正確性、用語準確性、邏輯思維、是否具有獨到見解等。25合計指導教師（簽章）： 年 月 日 源碼：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文法內容(共rs.num條):endl;int i=0;while(irs.num)outputrs.contenti+endl;output結 終 符:rs.terendl;output非結終符:rs.nonendl;co

23、ut非終結符的FIRST集合 endl;for(unsigned int j=0;jrs.non.size();j+)coutFIRST(rs.nonj) = rs.firstjtendl;cout非終結符的FOLLOW集合 endl;for(unsigned int j=0;jrs.non.size();j+)coutFOLLOW(rs.nonj) = rs.followjtendl;output預測分析表: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無法打開文件！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長度不對!) 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將形成無窮推導！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隨機產生非終結符為: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)!=-