编译原理语法分析器--算符优先文法分析器

编译原理实验报告实验名称：编写语法分析分析器实验类型：验证型实验指导教师：何中胜专业班级：12软件一姓名：学号：电子邮件：实验地点：秋白楼B720实验成绩：日期：2015年6月25日一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。1、选择最有代表性的语法分析方法，如LL(1)语法分析程序、算符优先分析程序和LR分析分析程序，至少选一题。2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。二、实验过程编写算符优先分析器。要求：（a）根据算符优先分析算法，编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入：Ⅰ：通过构造算符优先关系表，设计编制并调试一个算法优先分析程序Ⅱ：输入FIRSTVT，LASTVT集合，由程序自动生成该文法的算符优先关系矩阵。Ⅲ：输入已知文法，由程序自动生成该文法的算符优先关系矩阵。（b）程序具有通用性，即所编制的语法分析程序能够使用于不同文法以及各种输入单词串，并能判断该文法是否为算符文法和算符优先文法。（c）有运行实例。对于输入的一个文法和一个单词串，所编制的语法分析程序应能正确地判断，此单词串是否为该文法的句子，并要求输出分析过程。三、实验结果算符优先分析器：测试数据：E-E+T|TT-T*F|FF-(E)|i实验结果：(输入串为i+i*i+i)四、讨论与分析自下而上分析技术－算符优先分析法：算符文法：一个上下无关文法G，如果没有且没有P→..QR...(P,Q,R属于非终结符)，则G是一个算符文法。FIRSTVT集构造1、若有产生式P→a...或P→Qa...，则a∈FIRSTVT(P)。2、若有产生式P→...，则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出：若存在某个产生式：…P…，则对所有：b∈firstVT(P)都有：a≦b。构造优先关系表：1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。2、若产生式右部有...aP...的形式，则对于每个b∈FIRSTVT(P)都有a≦b(优先集)；3、若产生式右部有...Pb的形式，则对于每个a∈LASTVT(P)集,都有a≧b；4、若产生是形如：A→…ab…或A→…aBb…形式，则有a≒b。5、#与其他终结符的优先关系可利用拓广文法S‟#S#来获得。五、附录（全部代码）：#includestdio.h#includestdlib.h#includestring.h#includeiostream.hintanalyze();//对输入串的分析intisTerminator(charc);//判断字符c是否是终结符intgetIndex(charc);//求字符c在算符优先关系表中的下标voidprintS(intj,intk,char*s);//打印s栈voidfirstvt(charc);//求非终结符c的first集voidlastvt(charc);//求非终结符c的LASTVT集voidrelationTable();//创建文法优先关系表chardata[10][10];//算符优先关系chars[50];//模拟符号栈scharlable[30];//文法终极符集charinput[50];//文法输入符号串charstring[20][10];//用于输入串的分析intk,j,r=0,r1;chara,q;charst[10][30];//用来存储文法规则charfirst[10][10];//文法非终结符first集charlast[10][10];//文法非终结符LASTVT集intfflag[10]={0};//标志第i个非终结符的first集是否已求出intlflag[10]={0};//标志第i个非终结符的LASTVT集是否已求出intmain(){inti=0,j,k=0;printf(请输入文法规则（以#结束）\n);while(1){scanf(%s,st[i++]);//存储文法规则，初始化first集和LASTVT集*/if(strcmp(st[i-1],#)==0){r=i-1;break;}first[i][0]=0;/*first[i][0]和last[i][0]分别表示st[i][0]非终极符的first集和LASTVT集中元素的个数*/last[i][0]=0;}for(i=0;ir;i++)//判断文法是否合法{for(j=0;st[i][j]!='\0';j++){if(st[i][0]'A'||st[i][0]'Z'){printf(不是算符文法!\n);exit(-1);}if(st[i][j]='A'&&st[i][j]='Z'){if(st[i][j+1]='A'&&st[i][j+1]='Z'){printf(不是算符文法!\n);exit(-1);}}}}for(i=0;ir;i++){for(j=0;st[i][j]!='\0';j++){if((st[i][j]'A'||st[i][j]'Z')&&st[i][j]!='-'&&st[i][j]!=''&&st[i][j]!='|')lable[k++]=st[i][j];}}lable[k]='#';lable[k+1]='\0';relationTable();printf(每个非终结符的FIRSTVT集为：\n);//输出每个非终结符的first集for(i=0;ir;i++){printf(%c:,st[i][0]);for(j=0;jfirst[i][0];j++){printf(%c,first[i][j+1]);}printf(\n);}printf(每个非终结符的LASTVT集为：\n);//输出每个非终结符的LASTVT集for(i=0;ir;i++){printf(%c:,st[i][0]);for(j=0;jlast[i][0];j++){printf(%c,last[i][j+1]);}printf(\n);}printf(算符优先分析表如下:\n);for(i=0;lable[i]!='\0';i++)printf(\t%c,lable[i]);printf(\n);for(i=0;ik+1;i++){printf(%c\t,lable[i]);for(j=0;jk+1;j++){printf(%c\t,data[i][j]);}printf(\n);}printf(请输入文法输入符号串:);scanf(%s,input);analyze();}voidrelationTable(){chartext[20][10];inti,j,k,t,l,x=0,y=0;intm,n;x=0;for(i=0;ir;i++){firstvt(st[i][0]);lastvt(st[i][0]);}for(i=0;ir;i++){text[x][y]=st[i][0];y++;for(j=1;st[i][j]!='\0';j++){if(st[i][j]=='|'){text[x][y]='\0';x++;y=0;text[x][y]=st[i][0];y++;text[x][y++]='-';text[x][y++]='';}else{text[x][y]=st[i][j];y++;}}text[x][y]='\0';x++;y=0;}r1=x;printf(转化后的文法为:\n);for(i=0;ix;i++)//输出转化后的文法规则串{printf(%s\n,text[i]);}for(i=0;ix;i++)/*求每个终结符的推导结果(去掉-后的转化文法，用于最后的规约)*/{string[i][0]=text[i][0];for(j=3,l=1;text[i][j]!='\0';j++,l++)string[i][l]=text[i][j];string[i][l]='\0';}for(i=0;ix;i++){for(j=1;text[i][j+1]!='\0';j++){if(isTerminator(text[i][j])&&isTerminator(text[i][j+1])){m=getIndex(text[i][j]);n=getIndex(text[i][j+1]);data[m][n]='=';}if(text[i][j+2]!='\0'&&isTerminator(text[i][j])&&isTerminator(text[i][j+2])&&!isTerminator(text[i][j+1])){//（终结符非终结符终结符）情形m=getIndex(text[i][j]);n=getIndex(text[i][j+2]);data[m][n]='=';}if(isTerminator(text[i][j])&&!isTerminator(text[i][j+1]))//(终结符a非终结符A)afirst(A){for(k=0;kr;k++){if(st[k][0]==text[i][j+1])break;}m=getIndex(text[i][j]);for(t=0;tfirst[k][0];t++){n=getIndex(first[k][t+1]);data[m][n]='';}}if(!isTerminator(text[i][j])&&isTerminator(text[i][j+1]))//(非终结符A终结符a)LASTVT(A)a{for(k=0;kr;k++){if(st[k][0]==text[i][j])break;}n=getIndex(text[i][j+1]);for(t=0;tlast[k][0];t++){m=getIndex(last[k][t+1]);data[m][n]='';}}}}m=getIndex('#');for(t=0;tfirst[0][0];t++)//#first(开始符){n=getIndex(first[0][t+1]);data[m][n]='';}n=getIndex('#');for(t=0;tlast[0][0];t++)//LASTVT(开始符)#{m=getIndex(last[0][t+1]);data[m][n]='';}data[n][n]='=';}voidfirstvt(charc)//求first集{inti,j,k,m,n;for(i=0;ir;i++){if(st[i][0]==c)break;}if(fflag[i]==0){n=first[i][0]+1;m=0;do{if(m==2||st[i][m]=='|')//P-a...则a属于first(P){if(isTerminator(st[i][m+1])){first[i][n]=st[i][m+1];n++;}else{if(isTerminator(st[i][m+2]))//或P-Qa....则a属于first(P){first[i][n]=st[i][m+2];n++;}if(st[i][m+1]!=c)//如a属于first(Q)且P-Q则a属于first(P){firstvt(st[i][m+1]);for(j=0;jr;j++){if(st[j][0]==st[i][m+1])break;}for(k=0;kfirst[j][0];k++){intt;for(t=0;tn;t++){if(first[i][t]==first[j][k+1])break;}if(t==n){first[i][n]=first[j][k+1];n++;}}}}}m