編譯原理實驗報告LL分析法

1、課程 編譯原理實驗名稱 實驗二LL(1)分析法實驗?zāi)康? 掌握LL(1)分析法的基本原理；2. 掌握LL(1)分析表的構(gòu)造方法；3. 掌握LL(1)驅(qū)動程序的構(gòu)造方法。一.實驗內(nèi)容及要求根據(jù)某一文法編制調(diào)試LL (1)分析程序，以便對任意輸入的符號串進行分析。本次實驗的目的主要是加深對預(yù)測分析LL (1 )分析法的理解。對下列文法，用LL (1)分析法對任意輸入的符號串進行分析：(1) E->TG(2) G->+TG(3) G->s(4) T->FS(5) S->*FS(6) S->£(7) F->(E)(8) F->i程序輸入一以#結(jié)

2、束的符號串(包括+* () i#)，如：i+i*i#。輸出過程如下： 步驟 分析棧 剩余輸入串所用產(chǎn)生式1Ei+i*i#E->TG.實驗過程及結(jié)果代碼如下：#in clude<iostream>#in clude "edge.h" using n amespace std;edge:edge()cin> >left»right;rlen=right.le ngth();if(NODE.fi nd(left)>NODE.Ie ngth() NODE+=left;string edge:getlf()return left;stri

3、 ng edge:getrg()retur n right;stri ng edge:getfirst()return first;stri ng edge:getfollow()return follow;stri ng edge:getselect()retur n select;stri ng edge:getro()stri ng str;str+=rightO;return str;int edge:getrle n()retur n right.le ngth();void edge:newfirst(string w)int i;for(i=0;i<wen gth();i+

4、)if(first.fi nd(wi)>first.le ngth() first+=wi;void edge: newfollow(stri ng w)int i;for(i=0;i<wen gth();i+)if(follow.fi nd(wi)>follow.le ngth()&&&wi!=) follow+=wi;void edge: newselect(stri ng w)int i;for(i=0;i<wen gth();i+)if(select.fi nd(wi)>select.le ngth()&&&

5、wi!=) select+=wi;void edge:delfirst()int i=first.fi nd(); first.erase(i,1);int SUM;stri ng NODE,ENODE;計算firstvoid first(edge ni,edge *n,int x)int i,j;for(j=0;j<SUM;j+)if(n i.getlf()=nj.getlf()if(NODE.fi nd( nj.getro()<NODE.le ngth()for(i=0;i<SUM;i+)if(n i.getlf()=nj.getro()first( n i, n,x);

6、elsen x. newfirst (n j.getro();計算 followvoid follow(edge n i,edge *n ,i nt x)int i,j,k,s;stri ng str;for(i=0;i <n i.getrle n( );i+)s=NODE.fi nd( ni.getrg()i);if(s<NODE.le ngth()&&s>-1) /是非終結(jié)符if(i<ni.getrlen()-1) / 不在最右 for(j=0;j<SUM;j+)if(n j.getlf().fi nd(n i.getrg()i)=O)if(N

7、ODE.fi nd(n i.getrg()i+1)<NODE.le ngth() for(k=0;k<SUM;k+)if(n k.getlf().fi nd( ni.getrg()i+1)=0)n j. newfollow( nk.getfirst();if(n k.getfirst().fi nd(”")< nk.getfirst()e ngth() n j. newfollow( ni.getfollow();elsestr.erase();str+=n i.getrg()i+1;n j. newfollow(str);計算 selectvoid select(

8、edge &n i,edge *n)int i,j;if(ENODE.fi nd(n i.getro()<ENODE.Ie ngth()ni. newselect( ni.getro();if(n i.getro()="")ni. newselect( ni.getfollow();elsefor(i=0;i <n i.getrle n( );i+)for(j=0;j<SUM;j+)if(n i.getrg()i=nj.getlf()O)ni. newselect( nj.getfirst();if(n j.getfirst().fi nd()&g

9、t; nj.getfirst().le ngth() return;輸出集合void out(stri ng p)int i;if(p.le ngth()=0)return;cout<<""for(i=0;i<pen gth()-1;i+)cout<<pi<<"," cout<<pi<<""/連續(xù)輸出符號void outfu(i nt a,stri ng c)int i;for(i=0;i<a;i+) cout<<c;輸出預(yù)測分析表void outgr

10、aph(edge *n, stri ng (*yc)50) int i,j,k;bool flag;for(i=0;i<ENODEe ngth();i+)if(ENODEi!='')outfu(10,""); cout<<ENODEi;outfu(10,""); cout<<"#"<<e ndl;int x;for(i=0;i<NODE.le ngth();i+)outfu(4,"");cout<<NODEi;outfu(5,"&

11、quot;);for(k=0;k<ENODEe ngth();k+) flag=1;for(j=0;j<SUM;j+)if(NODEi=nj.getlf()0)x=nj.getselect().fi nd(ENODEk); if(x< nj.getselect().le ngth()&&x>-1) cout<<"->" <<n j.getrg(); ycik=nj.getrg();outfu(9-n j.getrle n()," ”); flag=O;x=nj.getselect().fi nd

12、('#');if(k=ENODE.Ie ngth()-1 &&x<n j.getselect().le ngth() && x>-1) cout<<"->" <<n j.getrg();ycij=nj.getrg();if(flag&&ENODEk!='')outfu(11,"");cout<<e ndl;分析符號串int pipei(string &chuan,string &fenxi,string (

13、*yc)50,int &b)char ch,a;int x,i,j,k;b+;cout<<e ndl<<" "<<b;if(b>9)outfu(8,"");elseoutfu(9,"");cout<<fe nxi;outfu(26-chua n.le ngth()-fe nxi.le ngth(),"");cout<<chua n;outfu(10,"");a=chua n 0;ch=fe nxife nxi.le ngt

14、h()-1;x=ENODE.fi nd(ch);if(x<ENODE.le ngth()&& x>-1)if(ch=a)fen xi.erase(fe nxi .len gth()-1,1);chua n. erase(0,1);cout<<"”'<<a<<"'匹配"if(pipei(chua n,fen xi,yc,b)return 1;elsereturn 0;elsereturn 0;elseif(ch='#')if(ch=a)cout<<"

15、分析成功"<<endl; return 1;elsereturn 0;elseif(ch=)fen xi.erase(fe nxi .len gth()-1,1); if(pipei(chua n,fen xi,yc,b) return 1;elsereturn 0;elsei=NODE.fi nd(ch);if(a='#')x=ENODE.fi nd(''); if(x<ENODE.le ngth() && x>-1) j=ENODE.le ngth()-1;elsej=ENODE.le ngth();else

16、j=ENODE.fi nd(a); if(ycij.le ngth()cout<<NODEi<<"->"<<ycij; fen xi.erase(fe nxi .len gth()-1,1);for(k=ycij.le ngth()-1;k>-1;k-)if(ycijk!=)fen xi+=ycijk;if(pipei(chua n,fen xi,yc,b)return 1;elsereturn 0;elsereturn 0;void mai n()edge *n;stri ng str,(*yc)50;int i,j,k;b

17、ool flag=0;cout<<"請輸入上下文無關(guān)文法的總規(guī)則數(shù)："<<endl;cin> >SUM;cout<<"請輸入具體規(guī)則(格式：左部 右部，為空)："<<endl; n=new edgeSUM;for(i=0;i<SUM;i+)for(j=0;j< ni.getrle n( );j+)str=n i.getrg();if(NODE.fi nd(strj)>NODE.Ie ngth()&&ENODE.fi nd(strj)>ENODE.Ie ng

18、th() ENODE+=strj;/計算first集合for(i=0;i<SUM;i+)first( ni, n,i);outfu(10,"*");cout<<e ndl;for(i=0;i<SUM;i+)if(n i.getfirst().fi nd("")< ni.getfirst().le ngth()if(NODE.fi nd( ni.getro()<NODE.le ngth()for(k=1;k< ni.getrle n();k+)if(NODE.fi nd( ni.getrg()k)<NODEe

19、 ngth()for(j=0;j<SUM;j+)if(n i.getrg()k=nj.getlf()O)n i. newfirst (n j.getfirst(); break;if(n j.getfirst().fi nd("")> nj.getfirst().le ngth() n i.delfirst();break;計算follow 集合for(k=0;k<SUM;k+)for(i=0;i<SUM;i+)if(n i.getlf()=nO.getlf()n i. newfollow("#");follow( ni, n,i

20、);for(i=0;i<SUM;i+)for(j=0;j<SUM;j+)if(n j.getrg().fi nd(n i.getlf()=nj.getrle n()-1)n i. newfollow( nj.getfollow();/計算select集合for(i=0;i<SUM;i+)select( ni, n);for(i=0;i<NODE.le ngth();i+)str.erase();for(j=0;j<SUM;j+)if(n j.getlf()0=NODEi)if(!str.le ngth()str=nj.getselect();elsefor(k=0

21、;k< nj.getselect().le ngth();k+) if(str.fi nd( nj.getselect()k)<str.le ngth() flag=1;break;/輸出cout<<endl<<"非終結(jié)符"outfu(SUM,"");cout<<"First"outfu(SUM,"");cout<<"Follow"<<e ndl;outfu(5+SUM,"-*-");cout<&l

22、t;e ndl;for(i=0;i<NODE.le ngth();i+)for(j=0;j<SUM;j+)if(NODEi=nj.getlf()0)outfu(3,"");cout<<NODEi; outfu(SUM+4,""); out( nj.getfirst();outfu(SUM+4-2*nj.getfirst().length(),""); out( nj.getfollow();cout<<e ndl;break;outfu(5+SUM,"-*-");cout<

23、<endl<<"判定結(jié)論："if(flag)cout<<"該文法不是LL文法!"<<endl; return;else cout<<"該文法是 LL(1)文法!"<<endl;/輸出預(yù)測分析表cout<<endl<<"預(yù)測分析表如下："<<endl;yc=new stringNODE.Iength()50;outgraph( n,yc);string chuan,fenxi,fchuan;cout<<endl<<"請輸入符號串："cin> >chua n;fchua n=chua n;fen xi="#"fen xi+=NODE0;i=0;cout<<endl<<"預(yù)測分析過程如下："<<endl;cout<<"步驟"outfu(7,"");cout<<"分析棧"o