FirstVT.rar_FIRSTVT

#include<iostream.h> #include<string.h> #include<stdio.h> typedef struct { char R; char r; int flag; }array; typedef struct { char E; char e; }charLode; typedef struct { charLode *base; int top; }charstack; char str[80][80],arr[80][80],brr[80][80]; array F[20]; int m,kk,p,ppp,FF=1; char r[10]; int crr[20][20],FLAG=0; char ccrr1[1][20],ccrr2[20][1]; void Initstack(charstack &s)//定义栈 { s.base=new charLode[20]; s.top=-1; } void push(charstack &s,charLode w) { s.top++; s.base[s.top].E=w.E; s.base[s.top].e=w.e; } void pop(charstack &s,charLode &w) { w.E=s.base[s.top].E; w.e=s.base[s.top].e; s.top--; } int IsEmpty(charstack s) { if(s.top==-1) return 1; else return 0; } int IsLetter(char ch) { if(ch>='A'&&ch<='Z') return 1; else return 0; } //judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法 int judge1(int n) { int j=3,flag=0; for(int i=0;i<=n;i++) while(str[i][j]!='\0') { char a=str[i][j]; char b=str[i][j+1]; if(IsLetter(a)&&IsLetter(b)) {flag=1;break;} else j++; } if(flag==1) return 0; else return 1; } //judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法 void judge2(int n) { for(int i=0;i<=n;i++) if(str[i][3]=='~'||judge1(n)==0||FLAG==1)//'~'代表空字 {cout<<"文法G不是算符优先文法!"<<endl;FF=0;break;} if(i>n) cout<<"文法G是算符优先文法!"<<endl; } //search1是查看存放终结符的数组r中是否含有重复的终结符 int search1(char r[],int kk,char a) { for(int i=0;i<kk;i++) if(r[i]==a) break; if(i==kk) return 0; else return 1; } //createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F数组是一个结构体 void createF(int n) { int k=0,i=1;char g; char t[10];//t数组用来存放非终结符 t[0]=str[0][0]; while(i<=n) { if(t[k]!=str[i][0]) {k++;t[k]=str[i][0];g=t[k];i++;} else i++; } kk=0; char c; for(i=0;i<=n;i++) { int j=3; while(str[i][j]!='\0') { c=str[i][j]; if(IsLetter(c)==0) { if(!search1(r,kk,c)) r[kk]=c;kk++;//r数组用来存放终结符 } j++; } } m=0; for(i=0;i<k;i++) for(int j=0;j<kk-1;j++) { F[m].R=t[i]; F[m].r=r[j]; F[m].flag=0; m++; } } //search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1 void search(charLode w) { for(int i=0;i<m;i++) if(F[i].R==w.E&&F[i].r==w.e) {F[i].flag=1;break;} } void FirstVT(int n)//求FirstVT { charstack sta; charLode w; int i=0; Initstack(sta); while(i<=n) { int k=3; w.E=str[i][0]; char a=str[i][k]; char b=str[i][k+1]; if(!IsLetter(a))//产生式的后选式的第一个字符就是终结符的情况 { w.e=a; push(sta,w); search(w); i++; } else if(IsLetter(a)&&b!='\0'&&!IsLetter(b))//产生式的后选式的第一个字符是非终结符的情况 { w.e=b; push(sta,w); search(w); i++; } else i++; } charLode ww; while(!IsEmpty(sta)) { pop(sta,ww); for(i=0;i<=n;i++) { w.E=str[i][0]; if(str[i][3]==ww.E&&str[i][4]=='\0') { w.e=ww.e; push(sta,w); search(w); break; } } } p=0;int k=1;i=1; while(i<m) { if(F[i-1].flag==1) { arr[p][0]=F[i-1].R; arr[p][k]=F[i-1].r; } while(F[i].flag==0&&i<m) i++; if(F[i].flag==1) { if(F[i].R==arr[p][0]) k++; else {arr[p][k+1]='\0';p++;k=1;} i++; } } } void LastVT(int n)//求LastVT { charstack sta; charLode w; for(int i=0;i<m;i++) F[i].flag=0; i=0; Initstack(sta); while(i<=n) { int k=strlen(str[i]); w.E=str[i][0]; char a=str[i][k-1]; char b=str[i][k-2]; if(!IsLetter(a)) { w.e=a; push(sta,w); search(w); i++; } else if(IsLetter(a)&&!IsLetter(b)) { w.e=b; push(sta,w); search(w); i++; } else i++; } charLode ee; while(!IsEmpty(sta)) { pop(sta,ee); for(i=0;i<=n;i++) { w.E=str[i][0]; if(str[i][3]==ee.E&&str[i][4]=='\0') { w.e=ee.e; push(sta,w); search(w); } } } int k=1;i=1; ppp=0; while(i<m) { if(F[i-1].flag==1) { brr[ppp][0]=F[i-1].R; brr[ppp][k]=F[i-1].r; } while(F[i].flag==0&&i<m) i++; if(F[i].flag==1) { if(F[i].R==arr[ppp][0]) k++; else {brr[ppp][k+1]='\0';ppp++;k=1;} i++; } } } void main() { int n,i,j; cout<<"请输入你要定义的文法G的产生式的个数n:"; cin>>n; for(i=0;i<n;i++) { gets(str[i]); j=strlen(str[i]); str[i][j]='\0'; } str[i][0]='Q'; str[i][1]='-'; str[i][2]='>'; str[i][3]='#'; str[i][4]=str[0][0]; str[i][5]='#'; str[i][6]='\0'; cout<<"你定义的产生式如下:"<<endl; for(i=0;i<=n;i++) cout<<str[i]<<endl; if(judge1(n)==0)//判断文法G是否为算符文法 cout<<"文法G不是算符文法!"<<endl; if(judge1(n)==1) { cout<<"文法G是算符文法!"<<endl; createF(n); FirstVT(n); LastVT(n); } judge2(n);//判断文法G是否为算符优先文法 if(FLAG==0) { for(i=0;i<=p;i++)//打印FirstVT { cout<<"FirstVT("<<arr[i][0]<<")={"; for(int l=1;arr[i][l+1]!='\0';l++) cout<<arr[i][l]<<","; cout<<arr[i][l]<<"}"<<endl; } cout<<"FirstVT(Q)={#}"<<endl; for(i=0;i<=ppp;i++)//打印LastVT { cout<<"LastVT("<<arr[i][0]<<")={"; for(int l=1;brr[i][l+1]!='\0';l++) cout<<brr[i][l]<<","; cout<<brr[i][l]<<"}"<<endl; } cout<<"LastVT(Q)={#}"<<endl; } }