編譯原理課程設(shè)計(jì)語(yǔ)法分析器

1、福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院計(jì)算機(jī)類課程設(shè)計(jì)報(bào)告課程名稱：編譯原理課程設(shè)計(jì)題目：語(yǔ)法分析器姓 名：系：專 業(yè)：年 級(jí)：2學(xué) 號(hào)：指導(dǎo)教師：職 稱：20102011學(xué)年第一學(xué)期福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院計(jì)算機(jī)類課程設(shè)計(jì)結(jié)果評(píng)定評(píng)語(yǔ)：成績(jī)：指導(dǎo)教師簽字：任務(wù)下達(dá)日期：評(píng)定日期：目 錄1 正則表達(dá)式11.1 正則表達(dá)式11.2 確定化(化簡(jiǎn))后的狀態(tài)轉(zhuǎn)換圖11.3 分析程序代碼11.4 程序運(yùn)行截圖11.5 小結(jié)22 ll(1)分析32.1 ll(1)文法32.2 ll(1)預(yù)測(cè)分析表32.3 分析程序代碼32.4 程序運(yùn)行截圖52.5 小結(jié)63 算符優(yōu)先分析73.1 算符優(yōu)先文法73.2 算符優(yōu)

2、先關(guān)系表73.3 分析程序代碼73.4 程序運(yùn)行截圖103.5 小結(jié)104 lr分析114.1 lr文法114.2 lr分析表114.3 分析程序代碼114.4 程序運(yùn)行截圖164.5 小結(jié)16參考文獻(xiàn)：161 正則表達(dá)式1.1 正則表達(dá)式 (a|b)*(aa|bb)(a|b)* (注：該正規(guī)式為示例，可更改）1.2 確定化(化簡(jiǎn))后的狀態(tài)轉(zhuǎn)換圖 1.3 分析程序代碼#includestdio.hvoid main()int s42=1,2,3,2,1,3,3,3;char c100;scanf(%s,c); int i=0; intk=0;int x;while(ci!=0)switch(c

3、i) case a: x=0;break; case b: x=1;break; default: x=-1;if(x0)break;k=skx;i+;if(k=3) printf(成功!n);else printf(出錯(cuò)了!n);1.4 程序運(yùn)行截圖輸入abab出錯(cuò)輸入abaaa1.5 小結(jié)通過(guò)本次實(shí)驗(yàn)熟悉了正則表達(dá)式程序?qū)崿F(xiàn)方法和進(jìn)一步熟悉了由正規(guī)式到dfa的轉(zhuǎn)換2 ll(1)分析2.1 ll(1)文法 ete (注：該文法為示例，可更改） e+te| tft t*ft| f(e)|i2.2 ll(1)預(yù)測(cè)分析表i+*()#eeteeteee+teeettfttftttt*ftttffif

4、(e)2.3 分析程序代碼#include#include#include #include using namespace std;char vn=e,e,t,t,f; char vt=i,+,*,(,),#; int lenvt=sizeof(vt);void showstack(stack st) int i,j; char ch100; j=st.size(); for(i=0;i=0;i-) coutchi; st.push(chi); int find(char c,char array,int n) int i; int flag=0; for(i=0;in;i+) if(c=a

5、rrayi) flag=1; return flag;int location(char c,char array) int i; for(i=0;c!=arrayi;i+); return i;void error() cout 出錯(cuò)!endl;void analyse(char vn,char vt,string m56,string str) int i,j,p,q,h,flag=1; char a,x; stack st; /定義堆棧 st.push(#); st.push(vn0); /#與識(shí)別符號(hào)入棧 j=0; h=1; a=strj; cout步驟 分析棧 剩余輸入串 所用產(chǎn)生式

6、endl; while(flag=1) couth ; h+; showstack(st); cout ; for(i=j;istr.size();i+) coutstri; x=st.top(); if(find(x,vt,lenvt)=1) if(x=a) if (x!=#) cout x匹配endl; st.pop(); a=str+j; else cout 接受!endlendl; flag=0; elseerror();break;elsep=location(x,vn); q=location(a,vt); string s1(null),s2(null); if(mpq=s1 |

7、 mpq=s2) error();break; elsestring str0=mpq; cout xstr0=0;i-) st.push(str0i); main() string m56=te ,null,null,te, null,null, null,+te ,null,null,$, $,ft, null,null,ft, null,null,null,$, *ft, null,$, $,i, null,null,(e), null,null; /預(yù)測(cè)分析表 string str; int errflag,i; coute+t|t t-t*f|f f-(e)|iendl; cout請(qǐng)

8、輸入分析串（以#結(jié)束）：str; for(i=0;istr.size();i+) if(!find(stri,vt,lenvt) cout輸入串中包含有非終結(jié)符stri(輸入錯(cuò)誤)!endl; errflag=1; while(errflag=1); /判斷輸入串的合法性 analyse(vn, vt, m,str); return 0; 2.4 程序運(yùn)行截圖輸入i+i#2.5 小結(jié)通過(guò)本次實(shí)驗(yàn)，鞏固了關(guān)于文法分析的相關(guān)知識(shí)，進(jìn)一步掌握l(shuí)l(1)文法中first集和follow集的求法，以及l(fā)l(1)文法預(yù)測(cè)分析表的構(gòu)造方法。3 算符優(yōu)先分析3.1 算符優(yōu)先文法 et | e+t | e-t

9、(注：該文法為示例，可更改） tf | t*f | t/f f(e) | i3.2 算符優(yōu)先關(guān)系表+-*/()i#+-*/()i#3.3 分析程序代碼#include #include using namespace std;typedef struct ochar char char_ch; struct ochar *next; opgchar;opgchar *temp,*top,*z;int i,j,m,n,e;string str;int push(char pchar) /壓棧 temp=(opgchar*)malloc(sizeof(opgchar); temp-char_ch=

10、pchar; temp-next=top; top=temp; return 0; int pop() /彈棧 if(top-char_ch!=#) top=top-next; return 0; /* 預(yù)測(cè)分析表*/char table88 = /* o a n ( ) t f # */ , /o , /a , /n ,=,0,0,0,0, /) ,0,0,0,0, /t ,0,0,0,0, /f ,0,char_ch=#&strn=#)coutchar_ch)confirmij(strn); switch(t) case :push(strn);n+=1;cout:pop();cout歸約

11、n; break; case =:pop();n+=1;coutchar_ch; z=z-next; h+; for(int i=h-1;i=0;i-)coutai; coutt;return 0;/* 顯示剩余輸入串 */ int showchuan() for(int i=n+1;i=str.length();i+) coutstri; couttt; return 0;int main(int argc,char *argv) int s=0;coutstr; for(int i=0;istr.length();i+) if(stri!=+&stri!=-&stri!=/&stri!=(

12、&stri!=)&stri!=*&stri!=i&stri!=#) coutn輸入有誤，請(qǐng)重新輸入:endl; s=1; break; while(s); push(#); coutn步驟t符號(hào)棧t當(dāng)前符號(hào)t剩余輸入串t移進(jìn)或歸約endlendl; while(strn) cout+mt; zhan(); coutstrntt; showchuan(); yazhan(); if(e) coute+te-tt-t*ft-ff-(e)f-i4.2 lr分析表步驟狀態(tài)棧符號(hào)棧輸入串動(dòng)作說(shuō)明10#i+i*i#5壓棧20 5#i+i*i#3入棧30 3#f+i*i#2入棧40 2#t+i*i#1入棧5

13、0 1#e+i*i#6壓棧60 1 6#e+i*i#5壓棧70 1 6 5#e+i*i#3入棧80 1 6 3#e+f*i#9入棧90 1 6 9#e+t*i#7壓棧100 1 6 9 7#e+t*i#5壓棧110 1 6 9 7 5#e+t*i#10入棧120 1 6 9 7 10#e+t*f#9入棧130 1 6 9#e+t#1入棧140 1#e#acc:分析成功4.3 分析程序代碼#include #include #include #define max 15typedef struct /定義狀態(tài)棧int datamax; int sttop; /top指針ststack;ststa

14、ck st; /產(chǎn)生一個(gè)狀態(tài)棧sttypedef struct /定義字符棧char datamax; int chtop;chstack;chstack ch; /產(chǎn)生字符棧chvoid main()/界面及提示信息printf(tttlr(1)文法分析n);printf(n);printf(tt本程序的文法：n);printf(tt1.e-e+tn);printf(tt2.e-tn);printf(tt3.t-t*fn);printf(tt4.t-fn);printf(tt5.f-(e)n);printf(tt6.f-in);printf(n);/輸入字符程序段char in20; /用i

15、n數(shù)組保存輸入的字符串信息printf(請(qǐng)輸入所要分析的式子:);scanf(%s,in);int loc; /loc表示數(shù)組in的位置loc=0;/默認(rèn)為第一個(gè)字符i/定義action表int action126=5,-1,-1,4,-1,-1, -1,6,-1,-1,-1,200, -1,102,7,-1,102,102, -1,104,104,-1,104,104, 5,-1,-1,4,-1,-1, -1,106,106,-1,106,106, 5,-1,-1,4,-1,-1, 5,-1,-1,4,-1,-1, -1,6,-1,-1,11,-1, -1,101,7,-1,101,101,

16、 -1,103,103,-1,103,103, -1,105,105,-1,105,105;/定義goto表int goto123=1,2,3, 0,0,0, 0,0,0, 0,0,0, 8,2,3, 0,0,0, 0,9,3, 0,0,10, 0,0,0, 0,0,0, 0,0,0, 0,0,0;/處理過(guò)程/1.置空狀態(tài)棧與字符棧st.sttop=-1; /置空狀態(tài)棧ch.chtop=-1; /置空字符棧/2.將0和#壓入狀態(tài)棧和字符棧int stfirst=0; /狀態(tài)棧第一壓入的字符char chfirst=#; /字符棧第一個(gè)壓入的字符st.sttop+;st.datast.sttop

17、=stfirst; /把0壓入狀態(tài)棧ch.chtop+;ch.datach.chtop=chfirst; /把#壓入字符棧 /3.求action所對(duì)應(yīng)的值int a,b; /a,b表示action表的位置char deal; /deal表示待處理的字符while(1) a=st.datast.sttop; /取狀態(tài)棧的棧頂，作為action表的行號(hào) deal=inloc; /將待處理的字符傳給deal switch(deal) /求出action表的對(duì)應(yīng)列號(hào) casei:b=0;break; case+:b=1;break; case*:b=2;break; case(:b=3;break;

18、case):b=4;break; case#:b=5;break; default:printf(n分析失?。悍欠ㄗ址);exit(0); int actvalue; actvalue=actionab; /5.主要過(guò)程 int c,d; /c,d表示goto表的位置 /5.1對(duì)應(yīng)的表格無(wú)數(shù)值，則報(bào)錯(cuò) if(actvalue=-1) printf(n分析失敗：不符合文法n); exit(0); /5.2若取到的值落在0到100，則移進(jìn) else if(actvalue0&actvalue100&actvalue200) switch(actvalue) case 101: /若為第一個(gè)式子

19、 st.sttop=st.sttop-3; /歸約時(shí),彈出三個(gè)棧元素 ch.chtop=ch.chtop-3; c=st.datast.sttop; /將狀態(tài)棧的棧頂賦給c,作為goto表的行號(hào) ch.chtop+; ch.datach.chtop=e; /將字符e壓入字符棧 d=0; break; /下同 case 102: st.sttop-; ch.chtop-; c=st.datast.sttop; ch.chtop+; ch.datach.chtop=e; d=0; break; case 103: st.sttop=st.sttop-3; ch.chtop=ch.chtop-3; c=st.datast.sttop; ch.chtop+; ch