编译原理实验3

北京电子科技学院（BESTI）实验报告课程：编译原理班级：1322姓名：李鹏举学号：201322001成绩：指导教师：周知扬实验日期：2016.5.16实验密级：预习程度：实验时间：9：00—11：30仪器组次：必修/选修：必修实验序号：三实验名称：语法分析器2实验目的与要求：掌握自下而上的语法分析方法，构造算符优先分析程序。实验仪器：名称型号数量PCDell1一、实验目的掌握自下而上的语法分析方法，构造算符优先分析程序。二、实验内容1．按所给文法构造FIRSTVT集合和LASTVT集合；2．构造优先矩阵；3．构造算符优先分析的总控程序；4．利用优先矩阵、分析栈和总控程序对源程序进行自下而上的语法分析测试；5．输出整个语法分析过程中栈的变化过程及分析结果，如符合语法规则输出“正确”，否则输出“错误”。6．分析SPL表达式序列的语法分析程序。三、实验设备及工具1．硬件：PC机Pentium100以上。2．软件：Win2000或WinXP、BC++、VC++或JAVA开发环境。四、实验说明本次实验要求编制能够识别下面给定文法的算符优先分析器，其中所需的集合与分析表的构造可以手工实现，也可以编写自动生成程序。算符优文法G(赋值语句):赋值语句变量=算术表达式算术表达式项|算术表达式+项|算术表达式-项项因式|项*因式|项/因式因式变量|整数|（算术表达式）变量标识符五、实验步骤1．构造FIRSTVT和LASTVT集合；2.构造算符优先矩阵；3.编写算符优先分析程序；4.测试语句：(1)price=perimeter*2+height*5/7(2)result:=3*radius*(radius+2*height)(3)其他错误的语句5.写出各句的分析过程中栈和输入串的变化。6.分析SPL表达式序列的语法分析程序实现过程，特别关注语法树的构建与生成。六、实验源代码#includestdio.h#includestdlib.h#includeiostreamchardata[20][20];//算符优先关系chars[100];//模拟符号栈scharw[100];charchu[100];charlable[20];//文法终极符集charinput[100];//文法输入符号串charstring[20][10];//用于输入串的分析intk;chara;intj;charq;intr;//文法规则个数intr1;//转化后文法规则个数charst[10][30];//用来存储文法规则charfirst[10][10];//文法非终结符FIRSTVT集charlast[10][10];//文法非终结符LASTVT集intfflag[10]={0};//标志第i个非终结符的FIRSTVT集是否已求出intlflag[10]={0};//标志第i个非终结符的LASTVT集是否已求出intdeal();//对输入串的分析intzhongjie(charc);//判断字符c是否是终极符intxiabiao(charc);//求字符c在算符优先关系表中的下标voidout(intj,intk,char*s);//打印s栈voidfirstvt(charc);//求非终结符c的FIRSTVT集voidlastvt(charc);//求非终结符c的LASTVT集voidtable();//创建文法优先关系表intmain(){FILE*wen,*fen;inti,j,k=0;printf(请输入文法规则数：);scanf(%d,&r);printf(请输入文法规则所在文件：\n);scanf(%s,&w);getchar();printf(请输入分析矩阵输出文件：\n);scanf(%s,&chu);getchar();wen=fopen(w,r);fen=fopen(chu,w);for(i=0;ir;i++){fscanf(wen,%s,st[i]);//存储文法规则，初始化FIRSTVT集和LASTVT集*/first[i][0]=0;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')&&j!=1&&j!=2&&st[i][j]!='|')lable[k++]=st[i][j];}}lable[k]='#';lable[k+1]='\0';table();printf(每个非终结符的FIRSTVT集为：\n);//输出每个非终结符的FIRSTVT集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]);fprintf(fen,\t%c,lable[i]);}fprintf(fen,\n);printf(\n);for(i=0;ik+1;i++){printf(%c\t,lable[i]);fprintf(fen,%c\t,lable[i]);for(j=0;jk+1;j++){printf(%c\t,data[i][j]);fprintf(fen,%c\t,data[i][j]);}printf(\n);fprintf(fen,\n);}fclose(fen);printf(请输入文法输入符号串以#结束:);intt=0;while((input[t]=getchar())!='#'){if(input[t]==''||input[t]=='\n'){;}elset++;}printf(\n);deal();}voidtable(){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(zhongjie(text[i][j])&&zhongjie(text[i][j+1])){m=xiabiao(text[i][j]);n=xiabiao(text[i][j+1]);data[m][n]='=';}if(text[i][j+2]!='\0'&&zhongjie(text[i][j])&&zhongjie(text[i][j+2])&&!zhongjie(text[i][j+1])){m=xiabiao(text[i][j]);n=xiabiao(text[i][j+2]);data[m][n]='=';}if(zhongjie(text[i][j])&&!zhongjie(text[i][j+1])){for(k=0;kr;k++){if(st[k][0]==text[i][j+1])break;}m=xiabiao(text[i][j]);for(t=0;tfirst[k][0];t++){n=xiabiao(first[k][t+1]);data[m][n]='';}}if(!zhongjie(text[i][j])&&zhongjie(text[i][j+1])){for(k=0;kr;k++){if(st[k][0]==text[i][j])break;}n=xiabiao(text[i][j+1]);for(t=0;tlast[k][0];t++){m=xiabiao(last[k][t+1]);data[m][n]='';}}}}m=xiabiao('#');for(t=0;tfirst[0][0];t++){n=xiabiao(first[0][t+1]);data[m][n]='';}n=xiabiao('#');for(t=0;tlast[0][0];t++){m=xiabiao(last[0][t+1]);data[m][n]='';}data[n][n]='=';}voidfirstvt(charc)//求FIRSTVT集{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]=='|'){if(zhongjie(st[i][m+1])){first[i][n]=st[i][m+1];n++;}else{if(zhongjie(st[i][m+2])){first[i][n]=st[i][m+2];n++;}if(st[i][m+1]!=c){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++;}while(st[i][m]!='\0');first[i][n]='\0';first[i][0]=--n;fflag[i]=1;}}voidlastvt(charc)//求LASTVT集{inti,j,k,m,n;for(i=0;ir;i++){if(st[i][0]==c)break;}if(lflag[i]==0){n=last[i][0]+1;m=0;do{if(st[i][m+1]=='\0'||st[i][