LR(1)实验

基于LR(1)的语法分析程序1.设计目的：设计、编制和调试一个典型的LR(1)分析器，进一步掌握LR(1)语法分析方法,掌握用预测分析方法分析LR(1)文法的具体过程，加深对LR(1)文法和预测分析方法的理解。2.设计要求：（1）根据LR(1)分析法编写一个语法分析程序，.输入已给定文法，直接输入根据己知文法构造的LR(1)分析表。（2）对于输入的符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。3.设计过程：3.1LR(1)文法的含义：LR分析法的规约过程是规范推倒的逆过程，所以LR分析过程是一种规范规约的逆过程，L表示从左到右扫描输入串，R表示最左规约（即最右推导的逆过程），括号中的1表示向右查看输入符号数为1。LR（1）项目可以看成两个部分组成，一部分和LR（0）项目相同，这部分成为心，另一部分为向前搜索符集合。所以只有当面临的输入符属于向前搜索符的集合，才做规约动作，其他情况均出错。LR（1）方法恰好解决SLR（1）方法在某些情况下存在的无效规约问题。3.2实验流程图开始进行分析字符串分析成功？进行规约分析输出分析结果结束输入一个待判断的字符串YN3.3实验截图3.3.1实验初期的实现截屏3.3.2输入正确的文法i+i*i#的截屏3.3.3输入错误的文法ii#的截屏4实验的主要程序代码#includeiostream#includecstdio#includecstdlib#includecstring#includestackusingnamespacestd;intk=0;structNode1{intstate;charvt;ints;}map[100];//当状态栈中的状态遇到终结符或者非终结符时应如何归约或移进//用M代表S',用R代表E',W代表T',e代表空intss[12]={0,1,2,3,4,5,6,7,8,9,10,11};charS[12][4]={S0,S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11};charR[12][4]={r0,r1,r2,r3,r4,r5,r6};charG[10][10]={M-E,E-E+T,E-T,T-T*F,T-F,F-(E),F-i};//存储文法中的产生式charVN[6]={'E','T','F'};//存储非终结符charVT[6]={'+','*','(',')','i','#'};//存储终结符charRight[10][8]={E,E+T,T,T*F,F,(E),i};stackcharstak1,stak2;//stak用于状态栈，stak1用于符号栈intACTION[12][6]={200,200,4,200,5,200,6,200,200,200,200,0,102,7,200,102,200,102,104,104,200,104,200,104,200,200,4,200,5,200,106,106,200,106,200,106,200,200,4,200,5,200,200,200,4,200,5,200,6,200,200,11,200,200,101,7,200,101,200,101,103,103,200,103,200,103,105,105,200,105,200,105};intGOTO[12][3]={1,2,3,200,200,200,200,200,200,200,200,200,8,2,3,200,200,200,200,9,3,200,200,10,200,200,200,200,200,200,200,200,200,200,200,200};intFind(intstate,charvt){inti;for(i=0;ik;i++){if(map[i].vt==state&&map[i].vt==vt)returnmap[i].s;}return200;}intempty1(intq[],intn){for(inti=0;in;i++){if(q[i]!=-1)return1;break;}return0;}intpoint(intstak[],intn){inttemp=0;for(inti=0;in;i++){if(stak[i]==-1)break;}temp=i-1;returntemp;}voidpop1(intq[],intn){inttemp;temp=point(q,n);q[temp]=-1;}voidpush1(intq[],intn,inte){inttemp;temp=point(q,n);q[temp+1]=e;}inttop1(intq[],intn){inttemp;temp=point(q,n);returnq[temp];}intvn_t(charc){for(inti=0;i6;i++)if(VT[i]==c)returni;for(i=0;i6;i++)if(VN[i]==c)returni;return100;}char*Analyse(char*word){intstak[12];intp,q;inth;intvt_n1;intact;charoutput[10];inti=1,j,l=strlen(word),k=0,m;for(intd=0;d12;d++)stak[d]=-1;while(!stak1.empty())stak1.pop();while(empty1(stak,12))pop1(stak,12);push1(stak,12,100);stak1.push('#');push1(stak,12,0);printf(________________________________________________________________________________\n);printf(\n对符号串%s的分析过程\n,word);printf(步骤状态栈元素符号栈顶元素剩余输入串ACTIONGOTO\n);p=top1(stak,12);h=stak1.top();while(p!=100){printf(%3d,i++);p=top1(stak,12);q=point(stak,12);for(i=1;i=q;i++)printf(%d,stak[i]);printf();h=stak1.top();printf(%8c,h);for(j=k,m=0;jl;j++)output[m++]=word[j];output[m]='\0';printf(%10s,output);vt_n1=vn_t(word[k]);if(vt_n1==100){printf(error!);//returnerror;break;}act=ACTION[p][vt_n1];if(act==0){printf(接受\n);returnSUCCESS;}elseif(act100){push1(stak,12,act);stak1.push(word[k]);k++;printf(%s,S[act]);}elseif(act200){act=act-100;intlen=strlen(Right[act]);charfina=G[act][0];intw=vn_t(fina);printf(%s,R[w]);for(i=0;ilen;i++){pop1(stak,12);stak1.pop();}p=top1(stak,12);m=GOTO[p][w];if(m100){push1(stak,12,m);printf(%s,S[m]);}elsereturnerror;stak1.push(fina);}elseif(act==200){printf(没有可用的产生式\n);returnerror;}printf(\n);}if(strcmp(output,#)!=0)returnERROR;}intmain(){intm,o,e;inti,j,k=0,h;charc;charsource[100];printf(________________________________________________________________________________\n);//分析表for(i=0;i12;i++){for(j=0;j6;j++){map[k].state=i;map[k].vt=VT[j];map[k].s=ACTION[i][j];k++;}for(h=0;h3;h++){map[k].state=i;map[k].vt=VN[h];map[k].s=GOTO[i][h];k++;}}printf(\nLR(1)文法的分析表如下：\n\n);printf();for(i=0;i6;i++)printf(%8c,VT[i]);for(i=0;i3;i++)printf(%8c,VN[i]);printf(\n);for(i=0;i12;i++){printf(-----------------------------------------------------------------------------\n);if(i=10)printf(%d,i);elseprintf(%d,i);for(j=0;j6;j++){for(m=0;mk;m++){if(ss[i]==map[m].state&&VT[j]==map[m].vt){o=map[m].s;if(o==0)printf(acc);elseif(o100)printf(%7s,S[o]);elseif(o200){o=o-100;printf(%7s,R[o]);}elseif(o==200)printf();break;}}}for(j=0;j3;j++){for(m=0;mk;m++){if(ss[i]==map[m].state&&VN[j]==map[m].vt){o=map[m].s;if(o100)printf(%8s,S[o]);elseif(o==200)printf();break;}}}printf(\n);}/*预测分析程序Analyse函数*///输入源文件串printf(请输入待分析的字符串:\n);scanf(%c,&c);e=0;while(c!='\n'){source[e]=c;e++;scanf(%c,&c);}source[e++]='\0';printf(\n分析结果：%s\n\n,Analyse(source));while(1);return0;}5心得体会：此次课程设计中受益良多，从一开始的不知道从何入手，再到决定用的编程语言、设计程序流程、调试，最后到程序运行成功。较好的文法分析器是功能全面的能自动构造其项目集和转换函数并构造分析表，然后进行分析的程序，但是实现LR（1）文法的自动分析程序对我来说很困难，最后决定直接输出分析表，而让程序实现对输入符号串的分析，在编程过程中也遇到了很多困难，如对某些终结符的动作或是规约函数的实现，最后通过请教同学和上网查找参考资料，都得到了解决。虽然我做的程序功能很简单，而且借鉴的地方不是很清楚具体细节，但是是我参与并动手了的成果，感觉很有收获。最后也感谢各位课设指导老师