搜索
..LR分析方法程序设计原理与实现技术XXX1028XXX计科1XXX班1.程序功能描述`通过设计、编写和构造LR（0）项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR（0）分析表的步骤，对文法的要求，能够从文法G出发生成LR（0）分析表，并对给定的符号串进行分析。要求以表格或图形的方式实现。实现LR(0)分析法，完成以下文法。G[E]:E→aA∣bBA→cA∣dB→cB∣d2.设计要求（1）构造LR（0）项目集规范簇；要求输入LR(0)文法时，可以直接输入，也可以读取文件，并能够以表格的形式输出项目集规范簇集识别活前缀的有穷自动机（2）构造LR（0）分析表。要求要求输入LR(0)文法时，可以直接输入，也可以读取文件；输出项目集规范簇，可以调用前一处理部分的结果，输出为LR(0)分析表（3）LR(0)分析过程【移进、归约、接受、报错】的实现。要求调用前一部分处理结果的分析表，输入一个符号串，依据LR（0）分析表输出与句子对应的语法树，或直接以表格形式输出分析过程。3.主要数据结构描述：文法表示，项目集规范族表示以及文法接受的符号和移植到的位置：..4.程序结构描述本程序一共有10个功能函数：voidget();//获取文法voidprint();//打印文法voidfun();//构造LR（0）项目集规范族voidanaly();//构造LR（0）分析表voidtest();//测试文法intequal(progectp1,progectp2);//判断两项是否相等intfindpoint(stringstr);//判断点的位置是否在最后，是的话就是规约项目intfindlocal(stringstr);//寻找此符号串对应的规范族的位置chargettype(charch,intnum);//根据状态集，返回操作的类别（移近，规约，接受）intgetnumber(charch,intnun);//根据状态机，返回下一步所跳转的状态集5.实验代码详见附件structgrammar{//文法charleft;vectorstringright;};structgrammar1{charleft;vectorstringright;intsign;};structdefine{intdata;chartype;};structprogect{//项集vectorgrammar1data;//数据vectorcharacc;//可接受的符号vectordefinenext;//转移到的位置};vectorgrammarlge;//文法vectorprogectpro;//项目集规范族..6.程序测试6.1功能测试程序运行后显示如下功能菜单：选择获取文法：..选择打印文法：选择构造LR（0）项目集规范族：....选择构造LR（0）分析表：..6.2文法测试分析失败:aAcAd分析成功:acd7.实验总结：本次实验按照书上的相应步骤，一步一步按照要求来完成实现，最终文成了给定文法的分析程序。首先是获取文法，文法的获取是采用直接输入的方法，保存成预先设定的结构体，然后根据文法，对文法编号，求出项目集规范族，然后再构造LR（0）分析表，最后根据分析表来判断输入符号串是否为此文法产生的语言。这次实验花费的时间比较长，因为用c语言在编写项目集族以及构造分析表的算法都遇到了一些困难,需要再实验中边写边学习。在完成实验后，我对LR（0）文法有了更加深入的了解。..//lr0.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includeiostream#includestring#includevectorusingnamespacestd;structgrammar{//文法charleft;vectorstringright;};structgrammar1{charleft;vectorstringright;intsign;};structdefine{intdata;chartype;};structprogect{//项目集vectorgrammar1data;//数据vectorcharacc;//可接受的符号vectordefinenext;//转移到的位置..};vectorgrammarlge;//文法vectorprogectpro;//项目集规范族voidget();//获取文法voidprint();//打印文法voidfun();//构造LR（0）项目集规范族voidanaly();//构造LR（0）分析表voidtest();//测试文法intequal(progectp1,progectp2);//判断两项是否相等intfindpoint(stringstr);//判断点的位置是否在最后，是的话就是规约项目intfindlocal(stringstr);//寻找此符号串对应的规范族的位置chargettype(charch,intnum);//根据状态集，返回操作的类别（移近，规约，接受）intgetnumber(charch,intnun);//根据状态机，返回下一步所跳转的状态集intmain(){intchoose;while(1){cout****************************************endl;cout获取文法请按1endl;cout打印文法请按2endl;cout构造LR（0）项目集规范族请按3endl;cout构造LR（0）分析表请按4endl;cout文法测试请按5endl;cout结束请按0endl;..cout****************************************endl;coutendl;cinchoose;if(choose==0)break;switch(choose){case1:get();break;case2:print();break;case3:fun();break;case4:analy();break;case5:test();break;default:break;}}return0;}voidget(){grammartemp,temp1,temp2;temp.left='E';temp.right.push_back(aA);temp.right.push_back(bB);temp1.left='A';temp1.right.push_back(cA);temp1.right.push_back(d);temp2.left='B';temp2.right.push_back(cB);..temp2.right.push_back(d);lge.push_back(temp);lge.push_back(temp1);lge.push_back(temp2);cout****************************************endl;cout文法获取完成endl;cout****************************************endl;coutendl;}voidprint(){cout****************************************endl;for(inti=0;ilge.size();i++){for(intj=0;jlge[i].right.size();j++){coutlge[i].left--;coutlge[i].right[j]endl;}}cout****************************************endl;coutendl;}voidfun(){grammar1g;//存入首元素g.sign=0;g.left='S';g.right.push_back(.E);progectp;..p.data.push_back(g);pro.push_back(p);intsign=0;while(1){sign=0;for(inti=0;ipro[0].data.size();i++){for(intj=0;jpro[0].data[i].right.size();j++){charch=pro[0].data[i].right[j][1];if(ch='Z'&&ch='A'&&pro[0].data[i].sign==0){//需要迭代pro[0].data[i].sign=1;sign=1;for(intk=0;klge.size();k++){if(lge[k].left==ch){grammar1gg;gg.left=lge[k].left;gg.sign=0;for(intp=0;plge[k].right.size();p++){gg.right.push_back(.+lge[k].right[p]);}pro[0].data.push_back(gg);}}}}}if(sign==0){break;..}}//迭代添加其他的sign=0;while(1){sign=0;for(inti=0;ipro.size();i++){for(intj=0;jpro[i].data.size();j++){for(intk=0;kpro[i].data[j].right.size();k++){stringtemp=pro[i].data[j].right[k];intp=0;while(ptemp.length()&&temp[p]!='.'){p++;}if(ptemp.length()-1){//需要添加progectpp;grammar1gg;gg.left=pro[i].data[j].left;gg.sign=0;stringtemp1=;for(intq=0;qp;q++){//复制改变右部temp1+=temp[q];}temp1+=temp[p+1];//.右边第一个元素temp1+=.;for(intq=p+2;qtemp.length();q++){temp1+=temp[q];}gg.right.push_back(temp1);..pp.data.push_back(gg);p=0;while(temp1[p]!='.'&&ptemp1.length()){p++;}if(ptemp1.length()-1){if(temp1[p+1]='A'&&temp1[p+1]='Z'){//非终结符，继续添加for(intm=0;mlge.size();m++){if(lge[m].left==temp1[p+1]){grammar1gg1;gg1.left=temp1[p+1];gg1.sign=0;for(intn=0;nlge[m].right.size();n++){gg1.right.push_back(.+lge[m].right[n]);}pp.data.push_back(gg1);}}}}//判断是否已经存在intsign1=0;for(inti1=0;i1pro.size();i1++){if(equal(pro[i1],pp)){sign1=1;}..}if(sign1==0){sign=1;pro.push_back(pp);//添加新的东西}}}}}if(sign==0){break;}}cout****************************************endl;for(inti=0;ipro.size();i++){//打印coutIi:endl;for(intj=0;jpro[i].d