编译原理语法分析中的算符优先编译原理语法分析中的算符优先

/* 对于书证p110页例6.3中的文法 * 该文法服从算符优先文法的定义 * 该文法多对应的算符优先关系系数关系表在书中p111页 * 该算法在书中117页 */ #include "stdio.h" #include "string.h" #include "malloc.h" #define maxsize 128 FILE *fp; char check (char a[]) { if(strcmp(a,"E+E")==0) return 'E'; else if(strcmp(a,"E-E")==0) return 'E'; else if(strcmp(a,"E*E")==0) return 'E'; else if(strcmp(a,"E/E")==0) return 'E'; else if(strcmp(a,"E^E")==0) return 'E'; else if(strcmp(a,"(E)")==0) return 'E'; else if(strcmp(a,"i")==0) return 'E'; else return 'G'; //错误控制 } typedef struct node { char data[maxsize]; int top; }seqstack; void setnull(seqstack *s) //置空栈 { s->top=-1; } seqstack * push (seqstack *s,char x) //进栈 { if(s->top==maxsize-1) { printf("overflow!\n"); return NULL; } else { s->top++; s->data[s->top]=x; return s; } } void pop (seqstack *s) //出栈 { if(s->top<0) printf("underflow!\n"); else s->top--; } char top(seqstack *s) //取栈顶元素 { if(s->top==-1) { printf("stack is empty!\n"); return NULL; } else return (s->data[s->top]); } int myequal (char a) { if(a=='+') return 0; else if(a=='-') return 1; else if(a=='*') return 2; else if(a=='/') return 3; else if(a=='^') return 4; else if(a=='(') return 5; else if(a==')') return 6; else if(a=='i') return 7; else if(a=='#') return 8; else return -1; } void printseqstack(seqstack *s) //打印出路径 { int temp; temp=s->top; while (temp>=0) { printf("%c",s->data[temp]); fputc(s->data[temp],fp); temp--; } } int isvt(char a[],int n,char x) { int i; for(i=0;i<n;i++) { if(x==a[i]) break; } if(i>=n) return 0; //不是该集合中的元素 else return 1; //是该集合中的元素 } void main(void) { if((fp=fopen("sign-frist.txt","w"))==NULL) { printf("File open fail!\n"); return; } printf("\t\t**************算符优先关系矩阵*****************\n"); fputs("\t\t**************算符优先关系矩阵*****************\n",fp); int i,j,sum=0,k,temp,a[9][9]={{1,1,-1,-1,-1,-1,1,-1,1},{1,1,-1,-1,-1,-1,1,-1,1},{1,1,1,1,-1,-1,1,-1,1},{1,1,1,1,-1,-1,1,-1,1},{1,1,1,1,-1,-1,1,-1,1},{-1,-1,-1,-1,-1,-1,0,-1,2},{1,1,1,1,1,2,1,2,1},{1,1,1,1,1,2,1,2,1},{-1,-1,-1,-1,-1,-1,2,-1,0}}; char input[maxsize],ch1,ch2,VT[9]={'+','-','*','/','^','(',')','i','#'},Q; char V[10]={'+','-','*','/','^','(',')','i','#','E'}; //定义所有的终结符和非终结符的集合 seqstack *s1,*s2; for (i=0;i<9;i++) { printf("\t"); fputs("\t",fp); for (j=0;j<9;j++) { if(a[i][j]==2) { printf ("\t"); fputs("\t",fp); } else if(a[i][j]==0) { fputs("=\t",fp); printf("=\t"); } else if(a[i][j]==-1) { printf("<\t"); fputs("<\t",fp); } else if(a[i][j]==1) { printf(">\t"); fputs(">\t",fp); } } printf("\n"); fputs("\n",fp); } printf("Please input the string that you want to check:\n"); gets(input); fputs("input:\t",fp); fputs(input,fp); fputs("\n",fp); s1=(seqstack *)malloc(sizeof(seqstack)); s2=(seqstack *)malloc(sizeof(seqstack)); setnull(s1); setnull(s2); s1=push(s1,'#'); s2=push(s2,'#'); i=0;sum=0; while(input[i]!='\0') { sum++; i++; } while(sum>0) { s2=push(s2,input[--sum]); } printf("归约的中间过程为:\n"); fputs("归约的中间过程为:\n",fp); ch1=top(s1); ch2=top(s2); i=myequal(ch1); j=myequal(ch2); while (1) { a: printseqstack(s1); printf("\t\t"); fputs("\t\t",fp); printseqstack(s2); printf("\n"); fputs("\n",fp); if(s1->data[s1->top]=='G' || isvt(V,10,s2->data[s2->top])==0) //错误控制 goto c; if(isvt(VT,9,ch1)==1) k=s1->top; else if(isvt(VT,9,ch1)==0) k=s1->top-1; if(a[myequal(s1->data[k])][j]!=1) { if(a[myequal(s1->data[k])][j]==-1) { b: pop(s2); s1=push(s1,ch2); ch2=top(s2); j=myequal(ch2); ch1=top(s1); goto a; } else { if(a[myequal(s1->data[k])][j]!=0) { c: printf("ERROR!\n"); fputs("ERROR!\n",fp); break; } else { if(ch2=='#') { printf("Congratulations!\n"); fputs("Congratulations!\n",fp); break; } else { goto b; } } } } else { do{ Q=s1->data[k]; if(isvt(VT,9,s1->data[k-1])==1) k=k-1; else k=k-2; j=myequal(Q); }while(!(a[myequal(s1->data[k])][j]==-1)); sum=0; for(temp=k+1;temp<=s1->top;temp++) { input[sum]=s1->data[temp]; sum++; } input[sum]='\0'; ch1=check(input); s1->top=k; s1=push(s1,ch1); ch1=top(s1); ch2=top(s2); j=myequal(ch2); goto a; } } gets(input); fclose(fp); }