编译原理 LL(1)文法 两个版本

//判空已经是完美的，follow集也已经设标志位方法，是我最完美的LL1文法！ #include <stdlib.h>//#include <stdio.h> #include <conio.h> #include<iostream> #include<string> #include<fstream> #include<iomanip> using namespace std; const int MaxVnNum = 10; const int MaxVtNum = 10; const int MaxPLength = 20; const int MaxStackDepth = 20; typedef struct /*此结构用来存储文法的所有产生式*/ { char p[50][10]; /*P数组用来存储产生式*/ int length; /*产生式个数*/ }G; typedef struct /*此结构用来存储终结符*/ { char id[20]; /*所有终结符名称*/ int length; /*终结符个数*/ }VT; typedef struct /*此结构用来存储非终结符*/ { char id[20]; /*所有非终结符*/ int empty[20]; /*是否可以推出空，1表示可以推出空，0表示不可以推出空，-1表示待定*/ int length; /*非终结符个数*/ }VN; typedef struct /*此结构为关系图中的结点类型*/ { char id; /*结点名称*/ char tn; /*标志终结符还是非终结符，t表示终结符，n表示非终结符*/ int style; /*若是非终结符的话，用来标识first集,1表示first，0表示follow*/ }node; typedef struct /*此结构为关系图的数据结构*/ { node n[60]; /*一维数组存储顶点信息*/ int length; /*顶点个数*/ int s[60][60]; /*存储顶点之间的关系*/ }rela; G *g; VT *vt; VN *vn; rela *r; int first[20][20]; /*存储first集*/ int follow[20][20]; /*存储follow集*/ int select[20][20]; /*存储select集*/ int analyseTable[20][20]; /*存储select集（预测分析表）analyseTable*/ char digui='S';int icount=0; int followFlag[10]; char ch; /*符号或string ch;*/ string st; /*要分析的符号串*/ char stack[MaxStackDepth]; int top; void input(); char menu(); void printg(); int vnnum(char c) /*查找非终结符c在数组vn中所对应的编号*/ { int i; for(i=0;vn->id[i]!=c&&i<vn->length;i++); if(i!=vn->length) return(i); else return(-1); } int vtnum(char c) /*查找终结符c在数组vt中所对应的编号*/ { int i; for(i=0;vt->id[i]!=c&&i<vt->length;i++); if(i!=vt->length) return(i); else return(-1); } int rvtnum(char c) /*在关系图中查找终结符c的编号*/ { int i; for(i=0;r->n[i].id!=c&&i<r->length;i++); if(i!=r->length) return(i); else return(-1); } int rvnnum(char c,int s) /*在关系图中查找非终结符c的编号，s表示是first集还是follow集*/ { int i=0; for(i=0;(r->n[i].id!=c||r->n[i].style!=s)&&i<r->length;i++); if(i!=r->length) return i; else return(-1); } void make_rela() /*构造关系图*/ { int i,j,k; /*连接first关系*/ for(i=0;i<g->length;i++) { for(j=3;g->p[i][j]!='\0';j++) { if(g->p[i][j]<'A'||g->p[i][j]>'Z') { r->s[rvnnum(g->p[i][0],1)][rvtnum(g->p[i][j])]=1; break; } else if(g->p[i][0]!=g->p[i][j]) { r->s[rvnnum(g->p[i][0],1)][rvnnum(g->p[i][j],1)]=1; if(vn->empty[vnnum(g->p[i][j])]!=1) break; else continue; } } if(g->p[i][j]=='\0') r->s[rvnnum(g->p[i][0],1)][rvtnum('@')]=1; } /*连接follow关系*/ r->s[rvnnum(vn->id[0],0)][rvtnum('#')]=1; for(i=0;i<g->length;i++) { for(j=3;g->p[i][j]!='\0';j++) { if(g->p[i][j]>='A'&&g->p[i][j]<='Z') { for(k=j+1;g->p[i][k]!='\0';k++) { if(g->p[i][k]<'A'||g->p[i][k]>'Z')//终结符 { r->s[rvnnum(g->p[i][j],0)][rvtnum(g->p[i][k])]=1; break; } else { r->s[rvnnum(g->p[i][j],0)][rvnnum(g->p[i][k],1)]=1; if(vn->empty[vnnum(g->p[i][k])]==0) break; //if(vn->empty[vnnum(g->p[i][k])]!=1) 对比一下吧 else continue; } }//for if(g->p[i][k]=='\0') r->s[rvnnum(g->p[i][j],0)][rvnnum(g->p[i][0],0)]=1; } } } // getchar(); } void outputfir_fol_sel(int a[20][20],int length) /*输出函数*/ { int i,j; printf("\n\n"); for(i=0;i< length;i++) { if(length==vn->length) printf("\t %c的集为: ",vn->id[i]); else printf("\t(%d) %s 的select集: ",i,g->p[i]); for(j=0;j<vt->length ;j++) { if(a[i][j]==1) { printf("\t %c ",vt->id[j]); } } printf("\n"); } } void diguifirst(int left0,char c,int s,int a[20][20]) { int j,left,right; left=rvnnum(c,s); for(j=0; j< r->length; j++) { if(r->s[left][j]==1) { if(r->n[j].tn=='t'&& r->n[j].id!='@' ) { //printf("\n %c \n",r->n[j].id); right=vtnum(r->n[j].id); a[left0][right]=1; } else if(r->n[j].tn=='n'&& r->n[j].style==1) {//first diguifirst(left0, r->n[j].id,r->n[j].style,a); } else if(r->n[j].tn=='n'&& r->n[j].style==0 &&followFlag[vnnum(r->n[j].id)]==0) {//follow followFlag[vnnum(r->n[j].id)]=1; //icount++; diguifirst(left0, r->n[j].id,r->n[j].style,a); } } } } void pfirst() /* 遍历关系图表,存储first集 */ { int i,j,left,right,left0; for(i=0;i<r->length;i++) { if(r->n[i].tn=='n'&&r->n[i].style==1) { left0=vnnum(r->n[i].id); left=rvnnum(r->n[i].id,1); // diguifirst(left0, r->n[i].id); for(j=0; j< r->length; j++) { if(r->s[left][j]==1) { if(r->n[j].tn=='t') { //printf("\n %c \n",r->n[j].id); right=vtnum(r->n[j].id); first[left0][right]=1; } else if(r->n[j].tn=='n') {//麻烦啊 diguifirst(left0, r->n[j].id,1,first); } }//if end }//for } } system("cls"); printf("\n\n\t3.输出非终结符的First集\n"); outputfir_fol_sel(first,vn->length); } void pfollow() /* 遍历关系图表,存储follow集 */ { int i,j,left,right,left0; for(i=0;i<r->length;i++) { if(r->n[i].tn=='n'&& r->n[i].style==0) { left0=vnnum(r->n[i].id); left=rvnnum(r->n[i].id,0); // diguifirst(left0, r->n[i].id); for(j=0; j< r->length; j++) { if(r->s[left][j]==1) { if(r->n[j].tn=='t') { //printf("\n %c \n",r->n[j].id); right=vtnum(r->n[j].id); follow[left0][right]=1; } else if(r->n[j].tn=='n'&& r->n[j].style==1) {//first diguifirst(left0, r->n[j].id,r->n[j].style,follow); } else if(r->n[j].tn=='n'&& r->n[j].style==0 ) {//follow followFlag[vnnum(r->n[j].id)]=1; diguifirst(left0, r->n[j].id,r->n[j].style,follow); for(int m=0; m<vn->length; m++ ) followFlag[m]=0;//记得清0 } }//if end } } } system("cls");printf("\n\n\t4.输出非终结符的Follow集\n"); outputfir_fol_sel(follow,vn->length); } void pselect() { int i,j,k; pfirst(); pfollow(); for(i=0;i<g->length;i++) { for(j=3;g->p[i][j]!='\0';j++) { if(g->p[i][j]=='@')//follow { for(k=0; k< vt->length ; k++) { if(follow[vnnum(g->p[i][0])][k]==1) select[i][k] =1; } break; } else if(g->p[i][j]<'A'||g->p[i][j]>'Z')//是终结符 { select[i][vtnum(g->p[i][j])]=1; break; } else if(g->p[i][j]>='A'&&g->p[i][j]<='Z')//是非终结符//fisrt-@ { //copy 一下 for(k=0; k< vt->length ; k++) { if(first[vnnum(g->p[i][j])][k]==1 && vt->id[k]!='@') select[i][k] =1; } if(vn->empty[vnnum(g->p[i][j])]!=1) break; else continue; } } if(g->p[i][j]=='\0'){ for(k=0; k< vt->length ; k++) { if(follow[vnnum(g->p[i][0])][k]==1) select[i][k] =1; }} } system("cls"); } void output_LL1_sel(int a[20][20],int length) /*输出函数*/ { int i,j; printf("\n\n "); for(j=0;j< vt->length; j++) //修改 cout<<" "<<vt->id[j]<<" "; cout<<endl; for(i=0;i< length;i++) { cout<<" "<<vn->id[i]<<" "; for(j=0;j<vt->length ;j++)