编译原理实验报告LL(1)分析法

课程编译原理实验名称实验二LL(1)分析法实验目的1．掌握LL(1)分析法的基本原理；2．掌握LL(1)分析表的构造方法；3．掌握LL(1)驱动程序的构造方法。一.实验内容及要求根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG（3）G-ε（4）T-FS（5）S-*FS（6）S-ε（7）F-(E)（8）F-i程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。输出过程如下：步骤分析栈剩余输入串所用产生式1Ei+i*i#E-TG............二.实验过程及结果代码如下：#includeiostream#includeedge.husingnamespacestd;edge::edge(){cinleftright;rlen=right.length();if(NODE.find(left)NODE.length())NODE+=left;}stringedge::getlf(){returnleft;}stringedge::getrg(){returnright;}stringedge::getfirst(){returnfirst;}stringedge::getfollow(){returnfollow;}stringedge::getselect(){returnselect;}stringedge::getro(){stringstr;str+=right[0];returnstr;}intedge::getrlen(){returnright.length();}voidedge::newfirst(stringw){inti;for(i=0;iw.length();i++)if(first.find(w[i])first.length())first+=w[i];}voidedge::newfollow(stringw){inti;for(i=0;iw.length();i++)if(follow.find(w[i])follow.length()&&w[i]!='@')follow+=w[i];}voidedge::newselect(stringw){inti;for(i=0;iw.length();i++)if(select.find(w[i])select.length()&&w[i]!='@')select+=w[i];}voidedge::delfirst(){inti=first.find('@');first.erase(i,1);}intSUM;stringNODE,ENODE;//计算firstvoidfirst(edgeni,edge*n,intx){inti,j;for(j=0;jSUM;j++){if(ni.getlf()==n[j].getlf()){if(NODE.find(n[j].getro())NODE.length()){for(i=0;iSUM;i++)if(n[i].getlf()==n[j].getro())first(n[i],n,x);}elsen[x].newfirst(n[j].getro());}}}//计算followvoidfollow(edgeni,edge*n,intx){inti,j,k,s;stringstr;for(i=0;ini.getrlen();i++){s=NODE.find(ni.getrg()[i]);if(sNODE.length()&&s-1)//是非终结符if(ini.getrlen()-1)//不在最右for(j=0;jSUM;j++)if(n[j].getlf().find(ni.getrg()[i])==0){if(NODE.find(ni.getrg()[i+1])NODE.length()){for(k=0;kSUM;k++)if(n[k].getlf().find(ni.getrg()[i+1])==0){n[j].newfollow(n[k].getfirst());if(n[k].getfirst().find(@)n[k].getfirst().length())n[j].newfollow(ni.getfollow());}}else{str.erase();str+=ni.getrg()[i+1];n[j].newfollow(str);}}}}//计算selectvoidselect(edge&ni,edge*n){inti,j;if(ENODE.find(ni.getro())ENODE.length()){ni.newselect(ni.getro());if(ni.getro()==@)ni.newselect(ni.getfollow());}elsefor(i=0;ini.getrlen();i++){for(j=0;jSUM;j++)if(ni.getrg()[i]==n[j].getlf()[0]){ni.newselect(n[j].getfirst());if(n[j].getfirst().find('@')n[j].getfirst().length())return;}}}//输出集合voidout(stringp){inti;if(p.length()==0)return;cout{;for(i=0;ip.length()-1;i++){coutp[i],;}coutp[i]};}//连续输出符号voidoutfu(inta,stringc){inti;for(i=0;ia;i++)coutc;}//输出预测分析表voidoutgraph(edge*n,string(*yc)[50]){inti,j,k;boolflag;for(i=0;iENODE.length();i++){if(ENODE[i]!='@'){outfu(10,);coutENODE[i];}}outfu(10,);cout#endl;intx;for(i=0;iNODE.length();i++){outfu(4,);coutNODE[i];outfu(5,);for(k=0;kENODE.length();k++){flag=1;for(j=0;jSUM;j++){if(NODE[i]==n[j].getlf()[0]){x=n[j].getselect().find(ENODE[k]);if(xn[j].getselect().length()&&x-1){cout-n[j].getrg();yc[i][k]=n[j].getrg();outfu(9-n[j].getrlen(),);flag=0;}x=n[j].getselect().find('#');if(k==ENODE.length()-1&&xn[j].getselect().length()&&x-1){cout-n[j].getrg();yc[i][j]=n[j].getrg();}}}if(flag&&ENODE[k]!='@')outfu(11,);}coutendl;}}//分析符号串intpipei(string&chuan,string&fenxi,string(*yc)[50],int&b){charch,a;intx,i,j,k;b++;coutendlb;if(b9)outfu(8,);elseoutfu(9,);coutfenxi;outfu(26-chuan.length()-fenxi.length(),);coutchuan;outfu(10,);a=chuan[0];ch=fenxi[fenxi.length()-1];x=ENODE.find(ch);if(xENODE.length()&&x-1){if(ch==a){fenxi.erase(fenxi.length()-1,1);chuan.erase(0,1);cout'a'匹配;if(pipei(chuan,fenxi,yc,b))return1;elsereturn0;}elsereturn0;}else{if(ch=='#'){if(ch==a){cout分析成功endl;return1;}elsereturn0;}elseif(ch=='@'){fenxi.erase(fenxi.length()-1,1);if(pipei(chuan,fenxi,yc,b))return1;elsereturn0;}else{i=NODE.find(ch);if(a=='#'){x=ENODE.find('@');if(xENODE.length()&&x-1)j=ENODE.length()-1;elsej=ENODE.length();}elsej=ENODE.find(a);if(yc[i][j].length()){coutNODE[i]-yc[i][j];fenxi.erase(fenxi.length()-1,1);for(k=yc[i][j].length()-1;k-1;k--)if(yc[i][j][k]!='@')fenxi+=yc[i][j][k];if(pipei(chuan,fenxi,yc,b))return1;elsereturn0;}elsereturn0;}}}voidmain(){edge*n;stringstr,(*yc)[50];inti,j,k;boolflag=0;cout请输入上下文无关文法的总规则数：endl;cinSUM;cout请输入具体规则（格式：左部右部，@为空）：endl;n=newedge[SUM];for(i=0;iSUM;i++)for(j=0;jn[i].getrlen();j++){str=n[i].getrg();if(NODE.find(str[j])NODE.length()&&ENODE.find(str[j])ENODE.length())ENODE+=str[j];}//计算first集合for(i=0;iSUM;i++){first(n[i],n,i);}//outfu(10,~*~);coutendl;for(i=0;iSUM;i++)if(n[i].getfirst().find(@)n[i].getfirst().length()){if(NODE.find(n[i].getro())NODE.length()){for(k=1;kn[i].getrlen();k++){if(NODE.find(n[i].getrg()[k])NODE.length()){for(j=0;jSUM;j++){if(n[i].getrg()[k]==n[j].getlf()[0]){n[i].newfirst(n[j].getfirst());break;}}if(n[j].getfirst().find(@)n[j].getfirst().length()){n[i].delfirst();break;}}}}}//计算follow集合for(k=0;kSUM;k++){for(i=0;iSUM;i++){if(n[i].getlf()==n[0].getlf())n[i].newfollow(#);follow(n[i],n,i);}for(i=0;iSUM;i++){for(j=0;jSUM;j++)if(n[j].getrg().find(n[i].getlf())==n[j].getrlen()-1)n