语法分析器).txt

自己写的语法分析程序

#include<iostream.h>
#include<stdio.h>
#include <string.h>
char Vn[12][10]={"S0","T3","A12","F67","C45","+","$","*","i","(",")"};
char Vnn[12][10]={"S7","T01","A01","F34","C34","+","$","*","i","(",")"};      
int M=0;
int MM;
//char Vn[20];
char Vt[10][10]={"+","$","*","i","(",")"};
char Vnf[20][10];
char Vnl[10][10];
char Vns[10][10];
char Vnright[10][10];
char stack[20];
int flag[10];
int flagg[10];
char R[10][10]={"ST+A","A+TA","A$","TFC","C*FC","C$","Fi","F(S)"};
bool ISempty(char a[]){
	int m=strlen(a);
	bool flag=false;
	for(int i=0;i<m;i++){
		if(a[i]=='$')flag=true;
	}
	return flag;
}
int location(char a){
	int r;
	for(int i=0;i<=10;i++){
		if(a==Vn[i][0])r=i;
	}
	return r;
}
void add(char Vnf1[][10],int j,char a){
	int m=strlen(Vnf1[j]);
	int flag=0;
	for(int i=0;i<m;i++){
         if(Vnf1[j][i]==a)flag=1;
	}
	if(flag==0)Vnf1[j][m]=a;
	M=m;
}
void dofirst(char Vn2[][10],int i){
	//cout<<"ddd="<<Vn[i]<<"f="<<flag[i]<<endl;
	if(flag[i]==1)return;
	else{
		int m=strlen(Vn2[i]);                         
	//	cout<<"m="<<m<<endl;
		for(int j=1;j<=m-1;j++){
			int vn=Vn2[i][j]-'0';
	
		//	cout<<"vn="<<Vn2[i][j]<<vn<<endl;
			int mm=strlen(R[vn]);
		//	cout<<"mm="<<mm<<endl;
			int q;
			for(q=1;q<=mm-1;q++){
				if(!(R[vn][1]>='A'&&R[vn][1]<='Z')){add(Vnf,i,R[vn][1]);break;}
			    else{int r=location(R[vn][1]);
				      dofirst(Vn2,r);
					  int mmm=strlen(Vnf[r]);
					  for(int y=0;y<mmm;y++){
						  if(Vnf[r][y]!='$')add(Vnf,i,Vnf[r][y]);
					  }
					  if(!ISempty(Vnf[r]))break;
					  else
						  if(q==mm-1)add(Vnf,i,'$');
				}
			}
		}
		flag[i]=1;
	}
}
void dofollow(char Vnn1[][10],int i){
    if(flagg[i]==1)return;
	else{
		if(i==0)add(Vnl,i,'#');
		int m=strlen(Vnn1[i]);                         
		//cout<<"m="<<m<<endl;
		for(int j=1;j<=m-1;j++){
			int vn=Vnn1[i][j]-'0';
	
			//cout<<"vn="<<vn<<endl;
			int mm=strlen(R[vn]);
			//cout<<"mm="<<mm<<endl;
			int q;
			for(q=1;q<=mm-1;q++){             //第几个字符匹配         
				if(Vnn1[i][0]==R[vn][q])break;       
			    }
			//cout<<"q="<<q<<"MM-1="<<mm<<endl;
			int u;
			
			if(q==mm-1){
				if(!(R[vn][0]==Vnn1[i][0])){
                  int r=location(R[vn][0]);
				
			     	dofollow(Vnn1,r);
                   int mmm=strlen(Vnl[r]);
				  
			       for(int y=0;y<mmm;y++){
			       if(Vnl[r][y]!='$')add(Vnl,i,Vnl[r][y]);
				   }
				}
			}
		    else{
                u=q+1;
				//cout<<"u="<<u<<endl;
				for(;u<=mm-1;u++){	
					//cout<<"rr="<<R[vn]<<"123="<<R[vn][u]<<endl;
					int rr=location(R[vn][u]);
					
		
					int mmmm=strlen(Vnf[rr]);
					for(int tt=0;tt<mmmm;tt++){
						if(Vnf[rr][tt]!='$')add(Vnl,i,Vnf[rr][tt]);
						
					}
					if(!ISempty(Vnf[rr]))break;
				}
			
				/*if(u==mm){
                    int rrr1=location(R[vn][u-1]);
					if(ISempty(Vnf[rrr1])){
					int r11=location(R[vn][0]);
				     dofollow(Vnn1,r11);
                     int mmm=strlen(Vnl[r11]);
			         for(int y=0;y<mmm;y++){
			         if(Vnl[r11][y]!='$')add(Vnl,i,Vnl[r11][y]);

				}*/
				
			}
			
		}flag[i]=1;
	}
}
void firstright(int i){
      int m=strlen(R[i]);
	  for(int j=1;j<m;j++){
		  if(R[i][j]>='A'&&R[i][j]<='Z'){
			  int r=location(R[i][j]);
			  int mm=strlen(Vnf[r]);
			  for(int k=0;k<mm;k++){
				  if(Vnf[r][k]!='&')add(Vnright,i,Vnf[r][k]);
			  }
			  
			  if(!ISempty(Vnf[r]))break;
		  }
		  else {if(R[i][j]!='&')add(Vnright,i,R[i][j]);break;
		  }

	  }
	  if(j==m){
		  int rr=location(R[i][j-1]);
		  if(R[i][j-1]=='$'||ISempty(Vnf[rr])){
			  add(Vnright,i,'$');
		  }
	  }
}

void select(int m){
    for(int i=0;i<m;i++){
           int m=strlen(Vnright[i]);
		   for(int j=0;j<m;j++){
			if(Vnright[i][j]!='$')add(Vns,i,Vnright[i][j]);
		   }
		   if(ISempty(Vnright[i])){
                  int r=location(R[i][0]);
                  int mm=strlen(Vnl[r]);
				  for(int g=0;g<mm;g++){
                      add(Vns,i,Vnl[r][g]);
					 
				  }
		   }
	}
}
bool ISVT(char a){
	bool flag=false;
    for(int i=0;i<6;i++){
		if(a==Vt[i][0]){
			flag=true;
			return flag;
		}
	}
	return flag;
}
bool IN(char a[],char x){
	int m=strlen(a);
	bool flag=false;
	for(int i=0;i<m;i++){
		if(a[i]==x){
			flag=true;
			return flag;
		}
	}
	return flag;
}

void analyst(char s[]){
      int loe,high=0;
	  int beg=0;
	  stack[high++]='#';
	  stack[high]=R[0][0];
	  bool flag=false;
	  bool find=false;
	  char X;
	  //cout<<"stack="<<stack<<endl;
	  while(!flag){
		  X=stack[high--];
		  //cout<<"X="<<X<<endl;
		  if(ISVT(X)){
			  if(X==s[beg]){beg++;}
			  
			  else{cout<<"error"<<endl;return;}
		  }
		  else {
			  if(X=='#'){
			  if(s[beg]==X)flag=true;
			  else{cout<<"error"<<endl;return;}
			  }
			  else{
				  for(int j=0;j<8;j++){
					  //cout<<"[beg]="<<s[beg];
					  if(X==R[j][0]&&IN(Vns[j],s[beg])){
					      //cout<<"d==="<<R[j]<<endl;
						  int mm=strlen(R[j]);
						  //cout<<"mm="<<mm<<endl;
                          find=true;
						  for(int k=mm-1;k>=1;k--){
							  if(R[j][k]!='$')stack[++high]=R[j][k];
							 
						  }
						  //cout<<"ffff="<<stack<<endl;
						  break;
					  }
					  
				  }
				  if(!find){
					  cout<<"error"<<endl;return;
				  }
			  }
		  }
	  }if(flag==true)cout<<"accept"<<endl;
}       

					  

void main()
{  cout<<Vn[10];
	for(int i=0;i<=4;i++){
	dofirst(Vn,i);
	cout<<"first("<<Vn[i][0]<<")={"<<Vnf[i]<<"}"<<endl;
	}
	for(int j=0;j<=5;j++){
	strcpy(Vnf[j+5],Vt[j]);
	cout<<"first("<<Vt[j][0]<<")={"<<Vnf[j+5]<<"}"<<endl;
	}
    for(int ii=0;ii<=4;ii++){
      dofollow(Vnn,ii);
	  cout<<"follow("<<Vn[ii][0]<<")={"<<Vnl[ii]<<"}"<<endl;
	}
	for(int k=0;k<8;k++){
		firstright(k);
		cout<<Vnright[k]<<endl;
	}


      select(8);
for(int h=0;h<8;h++){
	  cout<<Vns[h]<<endl;
	}
char ss[10];
int m;
do{
	cin>>ss;
	 m=strlen(ss);
}while(ss[m-1]!='#');
//cout<<"Ss="<<ss<<endl;
analyst(ss);

}