编译原理实验报告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............实验过程及结果代码如下：#include<iostream>#include"edge.h"usingnamespacestd;edge::edge(){ cin>>left>>right; 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;i<w.length();i++) if(first.find(w[i])>first.length()) first+=w[i];}voidedge::newfollow(stringw){ inti; for(i=0;i<w.length();i++) if(follow.find(w[i])>follow.length()&&w[i]!='@') follow+=w[i];}voidedge::newselect(stringw){ inti; for(i=0;i<w.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;j<SUM;j++) { if(ni.getlf()==n[j].getlf()) { if(NODE.find(n[j].getro())<NODE.length()) { for(i=0;i<SUM;i++) if(n[i].getlf()==n[j].getro()) first(n[i],n,x); } else n[x].newfirst(n[j].getro()); } }}//计算followvoidfollow(edgeni,edge*n,intx){ inti,j,k,s; stringstr; for(i=0;i<ni.getrlen();i++) { s=NODE.find(ni.getrg()[i]); if(s<NODE.length()&&s>-1)//是非终结符 if(i<ni.getrlen()-1)//不在最右 for(j=0;j<SUM;j++) if(n[j].getlf().find(ni.getrg()[i])==0) { if(NODE.find(ni.getrg()[i+1])<NODE.length()) { for(k=0;k<SUM;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()); } else for(i=0;i<ni.getrlen();i++) { for(j=0;j<SUM;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;i<p.length()-1;i++) {cout<<p[i]<<","; } cout<<p[i]<<"}";}//连续输出符号voidoutfu(inta,stringc){ inti; for(i=0;i<a;i++) cout<<c;}//输出预测分析表voidoutgraph(edge*n,string(*yc)[50]){ inti,j,k; boolflag; for(i=0;i<ENODE.length();i++) { if(ENODE[i]!='@') { outfu(10,""); cout<<ENODE[i]; } } outfu(10,""); cout<<"#"<<endl; intx; for(i=0;i<NODE.length();i++) { outfu(4,""); cout<<NODE[i]; outfu(5,""); for(k=0;k<ENODE.length();k++) { flag=1; for(j=0;j<SUM;j++) { if(NODE[i]==n[j].getlf()[0]) { x=n[j].getselect().find(ENODE[k]); if(x<n[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&&x<n[j].getselect().length()&&x>-1) { cout<<"->"<<n[j].getrg(); yc[i][j]=n[j].getrg(); } } } if(flag&&ENODE[k]!='@') outfu(11,""); } cout<<endl; }}//分析符号串intpipei(string&chuan,string&fenxi,string(*yc)[50],int&b){ charch,a; intx,i,j,k; b++; cout<<endl<<""<<b; if(b>9) outfu(8,""); else outfu(9,""); cout<<fenxi; outfu(26-chuan.length()-fenxi.length(),""); cout<<chuan; outfu(10,""); a=chuan[0]; ch=fenxi[fenxi.length()-1]; x=ENODE.find(ch); if(x<ENODE.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; else return0; } else return0; } else { if(ch=='#') { if(ch==a) { cout<<"分析成功"<<endl; return1; } else return0; } else if(ch=='@') { fenxi.erase(fenxi.length()-1,1); if(pipei(chuan,fenxi,yc,b)) return1; else return0; } else { i=NODE.find(ch); if(a=='#') { x=ENODE.find('@'); if(x<ENODE.length()&&x>-1) j=ENODE.length()-1; else j=ENODE.length(); } else j=ENODE.find(a); if(yc[i][j].length()) { cout<<NODE[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; } else return0; } }}voidmain(){ edge*n; stringstr,(*yc)[50]; inti,j,k; boolflag=0; cout<<"请输入上下文无关文法的总规则数："<<endl; cin>>SUM; cout<<"请输入具体规则（格式：左部右部，@为空）："<<endl; n=newedge[SUM]; for(i=0;i<SUM;i++) for(j=0;j<n[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;i<SUM;i++) { first(n[i],n,i); } //outfu(10,"~*~");cout<<endl; for(i=0;i<SUM;i++) if(n[i].getfirst().find("@")<n[i].getfirst().length()) { if(NODE.find(n[i].getro())<NODE.length()) { for(k=1;k<n[i].getrlen();k++) { if(NODE.find(n[i].getrg()[k])<NODE.length()) { for(j=0;j<SUM;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;k<SUM;k++) { for(i=0;i<SUM;i++) { if(n[i].getlf()==n[0].getlf()) n[i].newfollow("#"); follow(n[i],n,i); } for(i=0;i<SUM;i++) { for(j=0;j<SUM;j++) if(n[j].getrg().find(n[i].getlf())==n[j].getrlen()-1) n[i].newfollow(n[j].getfollow()); } } //计算select集合 for(i=0;i<SUM;i++) { select(n[i],n); } for(i=0;i<NODE.length();i++) { str.erase(); for(j=0;j<SUM;j++) if(n[j].getlf()[0]==NODE[i]) { if(!str.length()) str=n[j].getselect(); else { for(k=0;k<n[j].getselect().length();k++) if(str.find(n[j].getselect()[k])<str.length()) { flag=1; break; } } } } //输出 cout<<endl<<"非终结符"; outfu(SUM,""); cout<<"First"; outfu(SUM,""); cout<<"Follow"<<endl; outfu(5+SUM,"-*-"); cout<<endl; for(i=0;i<NODE.length();i++) { for(j=0;j<SUM;j++) if(NODE[i]==n[j].getlf()[0]) { outfu(3,""); cout<<NODE[i]; outfu(SUM+4,""); out(n[j].getfirst()); outfu(SUM+4-2*n[j].getfirst().