LL1分析法

实验报告实验名称LL1分析法专业计算机科学与技术课程名称编译原理指导老师赵智超班级计算机一班姓名夏红涛学号12103140102评分实验地点1C26217实验日期2014-04-30一、实验目的1．掌握LL(1)分析法的基本原理；2．掌握LL(1)分析表的构造方法；3．掌握LL(1)驱动程序的构造方法。二、实验原理根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序分析法的功能是利用LL(1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程三、实验过程及步骤（程序源代码、算法说明及调试过程）#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;voidfirst(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());}}}voidfollow(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);}}}}voidselect(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];}for(i=0;iSUM;i++){first(n[i],n,i);}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;}}}}}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[i].newfollow(n[j].getfollow());}}for(i=0;iSUM;i++){select(n[i],n);}for(i=0;iNODE.length();i++){str.erase();for(j=0;jSUM;j++)if(n[j].getlf()[0