实验4-算符优先分析法

实验名称：实验任务：对下述描述算符表达式的算符优先文法G[E],给出算符优先分析的实验结果。实验内容：有上下无关文法如下：E->E+T|E-T|TT->T*F|T/F|FF->(E)|i说明：优先关系矩阵的构造过程：（1）=关系由产生式F->(E)知‘（’=‘）’FIRSTVT集及LASTVT集FIRSTVT(E)={+,-,*,/,(,i}FIRSTVT(F)={(,i}FIRSTVT(T)={*,/,(,i}LASTVT(E)={+,-,*,/,),i}LASTVT(F)={),i}LASTVT(T)={*,/,),i}(2)<关系+T则有：+<FIRSTVT(T)-T则有：-<FIRSTVT(T)*F则有：*<FIRSTVT(F)/F则有：/<FIRSTVT(F)(E则有：(<FIRSTVT(E)(3)>关系E+则有：LASTVT(E)>+E-则有：LASTVT(E)>-T*则有：LASTVT(T)>*T/则有：LASTVT(T)>/E)则有：LASTVT(E)>)(4)请大家画出优先关系矩阵终结符之间的优先关系是唯一的，所以该文法是算符优先文法。程序的功能描述：程序由文件读入字符串（以#结束），然后进行算符优先分析，分析过程中如有错误，则终止程序并报告错误位置，最终向屏幕输出移近——规约过程。 last[i][0]=0; } for(i=0;i<r;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;i<r;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'; table(); printf("每个非终结符的FIRSTVT集为：\n");//输出每个非终结符的FIRSTVT集 for(i=0;i<r;i++) { printf("%c:",st[i][0]); for(j=0;j<first[i][0];j++) { printf("%c",first[i][j+1]); } printf("\n"); } printf("每个非终结符的LASTVT集为：\n");//输出每个非终结符的LASTVT集 for(i=0;i<r;i++) { printf("%c:",st[i][0]); for(j=0;j<last[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;i<k+1;i++) { printf("%c\t",lable[i]); for(j=0;j<k+1;j++) { printf("%c\t",data[i][j]); } printf("\n"); } printf("请输入文法输入符号串以#结束:"); scanf("%s",input); deal();}voidtable(){ chartext[20][10]; inti,j,k,t,l,x=0,y=0; intm,n; x=0; for(i=0;i<r;i++) { firstvt(st[i][0]); lastvt(st[i][0]); } for(i=0;i<r;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;i<x;i++)//输出转化后的文法规则串 { printf("%s\n",text[i]); } for(i=0;i<x;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;i<x;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;k<r;k++) { if(st[k][0]==text[i][j+1]) break; } m=xiabiao(text[i][j]); for(t=0;t<first[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;k<r;k++) { if(st[k][0]==text[i][j]) break; } n=xiabiao(text[i][j+1]); for(t=0;t<last[k][0];t++) { m=xiabiao(last[k][t+1]); data[m][n]='>'; } } } } m=xiabiao('#'); for(t=0;t<first[0][0];t++) { n=xiabiao(first[0][t+1]); data[m][n]='<'; } n=xiabiao('#'); for(t=0;t<last[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;i<r;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;j<r;j++) { if(st[j][0]==st[i][m+1]) break; } for(k=0;k<first[j][0];k++) { intt; for(t=0;t<n;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;i<r;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][m+1]=='|') { if(zhongjie(st[i][m])) { last[i][n]=st[i][m]; n++; } else { if(zhongjie(st[i][m-1])) { last[i][n]=st[i][m-1]; n++; } if(st[i][m]!=c) { lastvt(st[i][m]); for(j=0;j<r;j++) { if(st[j][0]==st[i][m]) break; } for(k=0;k<last[j][0];k++) { intt; for(t=0;t<n;t++) { if(last[i][t]==last[j][k+1]) break; } if(t==n) { last[i][n]=last[j][k+1]; n++; } } } } } m++; }while(st[i][m]!='\0'); last[i][n]='\0'; last[i][0]=--n; lflag[i]=1; }}intdeal(){ inti,j; intx,y; intz;//输入串的长度 k=1; s[k]='#';//栈置初值 for(i=0;input[i]!='\0';i++);//计算输入串的长度 z=i--; i=0; while((a=input[i])!='\0') { if(zhongjie(s[k])) j=k; else j=k-1; x=xiabiao(s[j]); y=xiabiao(a); if(data[x][y]=='>') { out(1,k,s); printf("%c",a); out(i+1,z,input); printf("规约\n"); do { q=s[j]; if(zhongjie(s[j-1])) j=j-1; elsej=j-2; x=xiabiao(s[j]); y=xiabiao(q); }while(data[x][y]!='<'); intm,n,N; for(m=j+1;m<=k;m++) { for(N=0;N<r1;N++) for(n=1;string[N][n]!='\0';n++) { if(!zhongjie(s[m])&&!zhongjie(string[N][n])){if(zhongjie(s[m+1])&&zhongjie(string[N][n+1])&&s[m+1]==string[N][n+1]) { s[j+1]=string[N][0]; break; } } else if(zhongjie(s[m])) if(s[m]==string[N][n]) { s[j+1]=string[N][0]; break; } } }k=j+1; if(k==2&&a=='#') { out(1,k,s); printf("%c",a); out(i+1,z,input); printf("结束\n"); printf("输入串符合文法的定义！\n"); return1;