編譯原理C++語法分析器

1、可編輯課程設(shè)計報告課程名稱：編譯原理課程設(shè)計題目：語法分析器姓 名：系：計算機專 業(yè)：計算機科學(xué)與技術(shù)年 級：2009級學(xué) 號：指導(dǎo)教師：職 稱：20102011學(xué)年第一學(xué)期精品文檔評語：成績：指導(dǎo)教師簽字：任務(wù)下達日期：評定日期：目 錄1 正則表達式11.1 正則表達式11.2 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖11.3 分析程序代碼11.4 程序運行截圖41.5 小結(jié)42 LL(1)分析52.1 LL(1)文法52.2 LL(1)預(yù)測分析表52.3 分析程序代碼52.4 程序運行截圖72.5 小結(jié)73 算符優(yōu)先分析83.1 算符優(yōu)先文法83.2 算符優(yōu)先關(guān)系表83.3 分析程序代碼83.4 程序

2、運行截圖103.5 小結(jié)114 LR分析124.1 LR文法124.2 LR分析表124.3 分析程序代碼124.4 程序運行截圖144.5 小結(jié)14參考文獻：141 正則表達式1.1 正則表達式 (a|b)*(aa|bb)(a|b)* (注：該正規(guī)式為示例，可更改）1.2 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖 1.3 分析程序代碼 #include#includeusingnamespacestd;constintMax=20;typedefstructArcNodeintadjvex;/該弧所指向的頂點的位置charinfo;/權(quán)structArcNode*nextarc;/指向下一條弧的指針Ar

3、cNode;typedefstructVNodechardata;/頂點信息ArcNode*firstarc;/指向第一條依附該頂點的弧的指針VNode;classNfapublic:Nfa();/構(gòu)造函數(shù),初始化nfaintFindAdj(charc);/返回c狀態(tài)的在鄰接表中的序號voidAlpAdd(charc);/向字母表集合中添加表中沒有的新元素cvoidInitVisit();/初始化Visited集合voide_closure(intindex);/求單一狀態(tài)c的e-閉包voide_closure(inta);/重載的狀態(tài)集合的e-閉包voidmove(intI,chara);/

4、單一狀態(tài)I的a弧轉(zhuǎn)換voidmove(intI,chara);/重載的狀態(tài)集合的a弧轉(zhuǎn)換voidNfa:Visit_I(int*Temp);/Visited轉(zhuǎn)換為集合voidInsert(intI,inta);/向狀態(tài)集合中添加新元素intTAdd(intI);/狀態(tài)矩陣T中加入新狀態(tài)集合voidResault(inti);voidNfa_Dfa();private:intK;/狀態(tài)數(shù)intTMaxMax;/狀態(tài)子集矩陣VNodeAdjListMax;/nfa,鄰接表的數(shù)據(jù)結(jié)構(gòu)存儲VNodeDfaMax;/dfaboolVisitedMax;/存e-閉包結(jié)果charAlpMax;/字母表,0號

5、單元用于存放個數(shù);Nfa:Nfa()K=Alp0=0;charc;stringline;ArcNode*p;while(cinc&c!=#)AdjListK.data=c;AdjListK.firstarc=newArcNode;AdjListK.firstarc-nextarc=NULL;K+;getline(cin,line);while(getline(cin,line)&line!=#)intindex=FindAdj(line0);if(index!=-1)p=AdjListindex.firstarc;while(p-nextarc)p=p-nextarc;p-nextarc=ne

6、wArcNode;p-nextarc-nextarc=NULL;p-nextarc-adjvex=FindAdj(line4);p-nextarc-info=line2;AlpAdd(p-nextarc-info);cout-endl;coutInitializationcompletely.endl;coutK=;for(inti=0;iK-1;i+)coutAdjListi.data,;coutAdjListK-1.data.endl;cout=;for(inti=1;i(int)Alp0;i+)coutAlpi,;coutAlpAlp0.endl;for(inti=0;inextarc;

7、while(p)coutf(AdjListi.data,info)=adjvexnextarc;if(inextarc)#includeint exch42=1,2,3,2,1,3,3,3;void judge(char *s) int cur = 0, i = 0;while(si)if(si-a 1 | si a)break;cur=exchcur si+ - a;if(si = 0 & cur = 3)printf (%s Right！nn,s);else printf (%s Wrong！nn,s);int main()char str100;while(1) printf(有限自動機

8、，判斷是否符合 (a|b)*(aa|bb)(a|b)*n); printf(請輸入字符串： ); gets(str); judge(str);1.4 程序運行截圖1.5 小結(jié)平時的學(xué)習(xí)需要通過實踐來檢驗，通過這次實驗我能發(fā)現(xiàn)自身存在的一些問題，并且加以改正，同時通過實驗加強了自己的動手能力，并且增強了對于正則表達式的理解，并不只在于應(yīng)試方面。2 LL(1)分析2.1 LL(1)文法 ETE (注：該文法為示例，可更改） E+TE| TFT T*FT| F(E)|i2.2 LL(1)預(yù)測分析表i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)2.3 分析程序代碼

9、 輸入文法：ETE (注：該文法為示例，可更改） E+TE| TFT T*FT| F(E)|i代碼：#include#include char data5610= 12,12, ,12+,-,-, 34,34, ,-,34*,-,-, i,)0(,;/ 第一維0-4分別代表 EETTF ，第二維0-5代表i+*()# -代表int exch(char ch)switch(ch) case i: return 0; case +: return 1; case *: return 2; case (: return 3; case ): return 4; case 0 : return 5;

10、/字符串結(jié)束標志代表#. default: return -1;void judge(char *s)int tot=0,i=0,cur,k=exch(s0);char sta100;sta+tot=0;while(tot0)cur = statot - 0;if(si = ) / 去空格+tot,k=exch(s+i);else if(cur+0 = si) / 推導(dǎo)出相同字符，出棧k=exch(s+i);else if(k 0 | datacurk0 = 0) / 踩空，或者出現(xiàn)非法字符break;else if(datacurk0 != -) /不是，進棧繼續(xù)推導(dǎo)strcpy(sta+t

11、ot,datacurk);tot+=strlen(datacurk);-tot; if(tot=0) printf( %s Right！nn,s); else printf( %s Wrong！nn,s);int main() char str100;printf(判斷符號串是否符合文法：nntETEnt);printf(E+TE|ntTFTntT*FT|ntF(E)|inn);while(printf(輸入符號串: )&gets(str)&str0)judge(str);return 0;2.4 程序運行截圖2.5 小結(jié) 實踐實踐驗證里的唯一標準，這次課程設(shè)計主要鞏固了我對LL(1)文法的深

12、刻認識，掌握程序?qū)崿F(xiàn)文法判斷、鏈表的使用等多種問題的基本方法，進一步提高了綜合運用所學(xué)知識的能力。 3 算符優(yōu)先分析3.1 算符優(yōu)先文法 ET | E+T | E-T (注：該文法為示例，可更改） TF | T*F | T/F F(E) | i3.2 算符優(yōu)先關(guān)系表+-*/()i#+-*/()i#3.3 分析程序代碼#include#includechar com88= , , , , , , , , , , , , , , , , , , , , , , , , , , , , , =, , , , , -, , -, , , , , , -, , -, , , , , , , -, 0&s

13、tan!=0)for(i=0;i0)m=tot;do cur=exch(stam-);while(cur0); / 要忽略變量，直接對終結(jié)符進行比較優(yōu)先級。while(si = ) / 跳過空格i+;k = exch(si);if( cur=k&cur=7)tot = 0; / 規(guī)約成功，結(jié)束標記。 else if( k ) / 遇到，準備規(guī)約if(statot = N) / 這里一個小問題就是變量N是要在左邊還是右邊呢，這要取決于終結(jié)符是什么，左右兩邊有幾個變量，不過針對本程序方法，只需全部放在右邊。statot = comcurk;sta+tot = N;else sta+tot = co

14、mcurk;sta+tot =si+;else if( (tot = confirm( sta,tot )=0 ) /檢驗終結(jié)符是否帶了應(yīng)有的變量。沒有，就規(guī)約失敗 tot = -1;if(tot=0) printf( %s Right！nn,s); else printf( %s Wrong！nn,s);int main() char str100;printf(判斷符號串是否符合文法：nntET | E+T | E-TntTF | T*F | T/FntF(E) | inn);while(printf(輸入符號串: )&gets(str)&str0)judge(str);return 0;

15、3.4 程序運行截圖3.5 小結(jié)通過這次課程設(shè)計，我發(fā)現(xiàn)之前沒發(fā)現(xiàn)的問題。算符優(yōu)先分析方法有一定的局限性由于算符優(yōu)先分析法去掉了單非終結(jié)符之間的歸約，盡管在分析過程中，當(dāng)決定是否為句柄時采取一些檢查措施，但仍難完全避免把錯誤的句子得到正確的歸約。4 LR分析4.1 LR文法 (0) SS (注：該文法為示例，可更改） (1) SBB (2) BaB (3) Bb4.2 LR分析表ACTIONGOTOab#SB0S3S4121acc2S3S453S3S464r3r3r35r1r1r16r2r2r24.3 分析程序代碼#include#include int action75= 3, 4, 0,

16、1, 2, 0, 0,-4, 0, 0, 3, 4, 0, 0, 5, 3, 4, 0, 0, 6, -3,-3,-3, 0, 0, -1,-1,-1, 0, 0, -2,-2,-2, 0, 0;/ 負數(shù)代表此時可規(guī)約，即r，第二維0-5分別代表a b # S B,-4表示accint cnt=0,S*10+2,B*10+2,B*10+1;/ 表示ri的產(chǎn)生式的左邊變量和右邊長度int exch(char ch)switch(ch) case a: return 0; case b: return 1; case #: case0: return 2; /字符串結(jié)束標志代表#. case S:

17、 return 3; case B: return 4; default: return -1;void judge(char *s)int int_stack100,ti=0,tc=0,i=1,cur,k=exch(s0);char char_stack100;int_stack+ti=0; while(ti0)cur = int_stackti;if(k0) /入棧，等待規(guī)約int_stack+ti = actioncurk; /數(shù)字棧char_stack+tc = si; /字符棧k = exch(si+);else if(actioncurk = -4) /規(guī)約完成，說明是符合要求ti = 0;else / 可以規(guī)約-i; /說明輸入的字符si-1還沒有用，此時它不進棧，故i-，以便下次取到的是要si-1;ti -= cnt -actioncurk %10; / 取ri的長度，出棧這么多個的字符tc -= cnt -actioncurk %10; char_stack+tc = cnt -actioncurk /10; / 取產(chǎn)生式的左邊變量，進行規(guī)約。k = exch( char_stacktc ); if(ti = 0) printf( %s Right！nn,s); else printf( %s Wrong！nn,s);int main() char s