LL文法的预测分析.doc

LL（1）文法的预测分析2008-12-05 22:27/edge.h#ifndef HEAD_EDGE #define HEAD_EDGE#includeusing namespace std;extern int SUM;extern string NODE,ENODE;class edgepublic:edge();string getlf();string getrg();string getfirst();string getfollow();string getselect();string getro();int getrlen();void newfirst(string w);void newfollow(string w);void newselect(string w);void delfirst();private:string left,right,first,follow,select;int rlen;#endif /edge.cpp#include#include edge.husing namespace std;edge:edge()cinleftright;rlen=right.length();if(NODE.find(left)NODE.length() NODE+=left;string edge:getlf()return left;string edge:getrg()return right;string edge:getfirst()return first;string edge:getfollow()return follow;string edge:getselect()return select;string edge:getro()string str;str+=right0;return str;int edge:getrlen()return right.length();void edge:newfirst(string w)int i;for(i=0;ifirst.length() first+=wi;void edge:newfollow(string w)int i;for(i=0;ifollow.length()&wi!=*) follow+=wi;void edge:newselect(string w)int i;for(i=0;iselect.length()&wi!=*) select+=wi;void edge:delfirst()int i=first.find(*);first.erase(i,1);/LL1.cpp#include#include#include edge.husing namespace std;int SUM;string NODE,ENODE;/计算firstvoid first(edge ni,edge *n,int x)int i,j;for(j=0;jSUM;j+) if(ni.getlf()=nj.getlf() if(NODE.find(nj.getro()NODE.length() for(i=0;iSUM;i+) if(ni.getlf()=nj.getro() first(ni,n,x); else nx.newfirst(nj.getro(); /计算followvoid follow(edge ni,edge *n,int x)int i,j,k,s;string str;for(i=0;ini.getrlen();i+) s=NODE.find(ni.getrg()i); if(s-1) /是非终结符 if(ini.getrlen()-1) /不在最右 for(j=0;jSUM;j+) if(nj.getlf().find(ni.getrg()i)=0) if(NODE.find(ni.getrg()i+1)NODE.length() for(k=0;kSUM;k+) if(nk.getlf().find(ni.getrg()i+1)=0) nj.newfollow(nk.getfirst(); if(nk.getfirst().find(*)nk.getfirst().length() nj.newfollow(ni.getfollow(); else str.erase(); str+=ni.getrg()i+1; nj.newfollow(str); /计算selectvoid select(edge &ni,edge *n)int i,j;if(ENODE.find(ni.getro()ENODE.length() ni.newselect(ni.getro(); if(ni.getro()=*) ni.newselect(ni.getfollow();else for(i=0;ini.getrlen();i+) for(j=0;jnj.getfirst().length() return; /输出集合void out(string p)int i;if(p.length()=0) return;cout;for(i=0;ip.length()-1;i+) coutpi,;coutpi;/连续输出符号void outfu(int a,string c)int i;for(i=0;ia;i+) coutc;/输出预测分析表void outgraph(edge *n,string (*yc)50)int i,j,k;bool flag;for(i=0;iENODE.length();i+) if(ENODEi!=*) outfu(10, ); coutENODEi; outfu(10, );cout#endl;int x;for(i=0;iNODE.length();i+) outfu(4, ); coutNODEi; outfu(5, ); for(k=0;kENODE.length();k+) flag=1; for(j=0;jSUM;j+) if(NODEi=nj.getlf()0) x=nj.getselect().find(ENODEk); if(x-1) coutnj.getrg(); ycik=nj.getrg(); outfu(9-nj.getrlen(), ); flag=0; x=nj.getselect().find(#); if(k=ENODE.length()-1&x-1) coutnj.getrg(); ycij=nj.getrg(); if(flag&ENODEk!=*) outfu(11, ); coutendl; /分析符号串int pipei(string &chuan,string &fenxi,string (*yc)50,int &b)char ch,a;int x,i,j,k;b+;coutendl 9) outfu(8, );else outfu(9, );coutfenxi;outfu(26-chuan.length()-fenxi.length(), );coutchuan;outfu(10, );a=chuan0;ch=fenxifenxi.length()-1;x=ENODE.find(ch);if(x-1) if(ch=a) fenxi.erase(fenxi.length()-1,1); chuan.erase(0,1); couta匹配; if(pipei(chuan,fenxi,yc,b) return 1; else return 0; else return 0;else if(ch=#) if(ch=a) cout分析成功endl; return 1; else return 0; else if(ch=*) fenxi.erase(fenxi.length()-1,1); if(pipei(chuan,fenxi,yc,b) return 1; else return 0; else i=NODE.find(ch); if(a=#) x=ENODE.find(*); if(x-1) j=ENODE.length()-1; else j=ENODE.length(); else j=ENODE.find(a); if(ycij.length() coutNODEi-1;k-) if(ycijk!=*) fenxi+=ycijk; if(pipei(chuan,fenxi,yc,b) return 1; else return 0; else return 0; void main()edge *n;string str,(*yc)50;int i,j,k;bool flag=0;cout请输入上下文无关文法的总规则数：SUM;cout请输入具体规则（格式：左部 右部，*为空）：endl;n=new edgeSUM;for(i=0;iSUM;i+) for(j=0;jNODE.length()&ENODE.find(strj)ENODE.length() ENODE+=strj; /计算first集合for(i=0;iSUM;i+) first(ni,n,i); /* coutFirst(ni.getlf()=; out(ni.getfirst(); coutendl; */outfu(10,*);coutendl;for(i=0;iSUM;i+) if(ni.getfirst().find(*)ni.getfirst().length() if(NODE.find(ni.getro()NODE.length() for(k=1;kni.getrlen();k+) if(NODE.find(ni.getrg()k)NODE.length() for(j=0;jnj.getfirst().length() ni.delfirst(); break; /*for(i=0;iSUM;i+) coutFirst(ni.getlf()=; out(ni.getfirst(); coutendl;outfu(10,*);coutendl;*/计算follow集合for(k=0;kSUM;k+) for(i=0;iSUM;i+) if(ni.getlf()=n0.getlf() ni.newfollow(#); follow(ni,n,i); for(i=0;iSUM;i+) for(j=0;jSUM;j+) if(nj.getrg().find(ni.getlf()=nj.getrlen()-1) ni.newfollow(nj.getfollow(); /* coutFollow(ni.getlf()=; out(ni.getfollow(); coutendl; */ /outfu(10,*);coutendl;/计算select集合for(i=0;iSUM;i+) select(ni,n); /* coutSelect(ni.getlf()ni.getrg()=; out(ni.getselect(); coutendl; */for(i=0;iNODE.length();i+) str.erase(); for(j=0;jSUM;j+) if(nj.getlf()0=NODEi) if(!str.length() str=nj.getselect(); else for(k=0;knj.getselect().length();k+) if(str.find(nj.getselect()k)str.length() flag=1; break; /*for(i=0;iSUM;i+) coutSelect(ni.getlf()ni.getrg()=; out(ni.getselect(); coutendl;*/输出coutendl非终结符;outfu(SUM, );coutFirst;outfu(SUM, );coutFollowendl;outfu(5+SUM,-*-);coutendl;for(i=0;iNODE.length();i+) for(j=0;jSUM;j+) if(NODEi=nj.getlf()0) outfu(3, ); coutNODEi; outfu(SUM+4, ); out(nj.getfirst(); outfu(SUM+4-2*nj.getfirst().length(), ); out(nj.getfollow(); coutendl; break; outfu(5+SUM,-*-);coutendl判定结论： ;if(flag) cout该文法不是LL(1)文法!endl; return;else cout该文法是LL(1)文法!endl;/输出预测分析表coutendl预测分析表如下：endl;yc=new stringNODE.length()50;outgraph(n,yc);/*for(i=0;iNODE.length();i+) for(j=0;jENODE.length();j+) if(ycij.length() coutycij ; else outfu(10, ); coutendl;*/string chuan,fenxi,fchuan;coutendlchuan;fchuan=chuan;fenxi=#;fenxi+=NODE0;/coutchuan=chuanendlfenxi=fenxiendl;/分析符号串i=0;coutendl预测分析过程如下：endl;cout步骤;outfu(8, );cout分析栈;outfu(10, );cout剩余输入串;outfu(10, );cout动作;if(pipei(chuan,fenxi,yc,i) coutendl输入串fchuan是该文法的句子！endl;else coutendl输入串fchuan不是该文法的句子！aH H -aMd -d M -Ab -* -* -Ab A -aM -e请输入符号串：aaabd#预测分析过程如下：步骤 分析栈 剩余输入串 动作1 #S aaabd# S-aH2 #Ha aaabd# a匹配3 #H aabd# H-aMd4 #dMa aabd# a匹配5 #dM abd# M-Ab6 #dbA abd# A-aM7 #dbMa abd# a匹配8 #dbM bd# M-*9 #db bd# b匹配10 #d d# d匹配11 # #