wenfa.cpp

此为编译原理的作业中的预测分析表的生成的原代码

#include"wenfa.h"
#include<iostream.h>
#include<string.h>
#include <math.h>
#include<fstream.h> 
#include<stdlib.h>
WenFa::WenFa(){
		s=new char[number][len];
		VN=new char[len];
		VT=new char[len];
		gz=new GZ[1];
		fa=new FA[1];
		des=0;
	}
WenFa::~WenFa(){
		delete []s;
		delete []VN;
		delete []VT;
		delete []gz;
		delete []fa;
	}
void WenFa::ChuLi(int n,int n2){
		int i,j,cnt=0,m=0,k,cnt1=0;
		char *t=new char[len];
		GZS=n+n2;//为规则数
		gz=new GZ[GZS];//开辟空间放规则
        for(i=0;i<n;i++){m=0;
	       for(j=4;j<strlen(s[i]);j++)
		        if(s[i][j]=='|'){
				gz[cnt].gz_q=s[i][0];
			        t[m]=0;m=0;
                          gz[cnt].cnt=0;
                          gz[cnt].boolq=false;
                          gz[cnt].boolde=false;
					       strcpy(gz[cnt].gz_h,t);//后部赋值
						   for(k=0;k<strlen(t);k++){
							   gz[cnt].boolh[k]=0;
					          if(t[k]>='A'&&t[k]<='Z')
						      gz[cnt].cnt++;
						   }
				cnt++;
				}                    	
				else {t[m++]=s[i][j];}
	      gz[cnt].gz_q=s[i][0];
          t[m]=0;m=0;
          gz[cnt].cnt=0;
          gz[cnt].boolq=false;
		  gz[cnt].boolde=false;
       	  strcpy(gz[cnt].gz_h,t);//后部赋值
		  for(k=0;k<strlen(t);k++){
			  gz[cnt].boolh[k]=0;
					if(t[k]>='A'&&t[k]<='Z')
						 gz[cnt].cnt++;
		  }
	  cnt++;
        }
	if(cnt==GZS)  {cout<<"存入成功！"<<endl;display_Ys();}
	  else cout<<"未成功存放!"<<endl;
      delete []t;
      }//ChuLi结束

bool WenFa::WFinput(void){//文法输入
		int n1,i,j;
		int Cnt1=0;//"|"的个数;
		int Cnt=0;//文法规则行数
		bool b=false;
		cout<<"1---文件方式输入         2---键盘方式输入      0---退出"<<endl;
        cout<<"命令值是：";
		cin>>n1;
	 switch(n1)
		{
		default : {cout<<"命令值错误,程序被破中断!"<<endl;exit(1);}
		case 1:{fstream infile;
	         	int cnt=0;//统计行数
		        char *filename=new char [80];
	        	cout<<"请输入文件名:";
		        cin>>filename;
		        infile.open(filename,ios::in|ios::nocreate);//打开如果没有不创建
		        if(!infile) cout<<"文件没有找到!"<<endl;
		        else {	
					while(!infile.eof()){
						  infile.getline(s[cnt],len);
						  if(int(strlen(s[cnt]))>0)//不为空行时
						     cout<<s[cnt++]<<endl;
					}
				  
		          cout<<"录入成功! 共输入了"<<cnt<<"行文法规则"<<endl;
				}
                for(i=0;i<cnt;i++)
	               for(j=4;j<strlen(s[i]);j++)
		                if(s[i][j]=='|') Cnt1++;//统计‘|’的个数
				Cnt=cnt;
                delete []filename;
	        	infile.close(); 
				break;
			   }
			case 2:{ int i,j,n; 
			cout<<"你需要输入几行文法规则（范围1~10）：";
		    cin>>n;
	     	cout<<"请输入"<<n<<" 行规则:"<<endl;
            if(n>0&&n<=10)
				for(i=0;i<n;i++){
				     cin>>s[i];
					 for(j=4;j<strlen(s[i]);j++)
		                if(s[i][j]=='|') Cnt1++;//统计‘|’的个数
				}
			Cnt=n;
			break;
			}
		}
	    
		if(Cnt>0) {ChuLi(Cnt,Cnt1);return true;}
		else {cout<<"输入文法规则的个数为零!"<<endl;return false;}
	}
void WenFa::display_GZ(void){//显示规则
		 int cnt=0,i;
		 bool boolsave;
		 char ch;
		 do{
		 cout<<"是否将该文法以文件的形式保存(Y/N):";
		 cin>>ch;
		 if(ch=='Y'||ch=='y') {char *filename=new char[80];
		                       fstream out;
		                       cout<<"请输入文件名:(例c:[\\\\路径名\\\\]xx.txt):";
							   cin>>filename;
                               if(strlen(filename)>0 ){
								   out.open(filename,ios::out);
								   for( i=0;i<GZS;i++)
		                           out<<gz[i].gz_q<<"::="<<gz[i].gz_h<<endl;
								delete []filename;
							    out.close;   
							   }
								   else cout<<"文件名不能为空,保存失败!";
                               break;
		 }
		 else if(ch=='N'||ch=='n')  break;
		 }while(1);
		 for( i=0;i<GZS;i++){
		      cout<<gz[i].gz_q<<"::="<<gz[i].gz_h<<"     ";cnt++;
							if(cnt%3==0)  cout<<endl;
		 }
	     cout<<endl;
	          cout<<"非终结符Vn={ ";
	     for(i=0;i<strlen(VN);i++)
		cout<<VN[i]<<"、";
	     cout<<'\b'<<" }共有:"<<strlen(VN)<<"个;"<<endl;
             cout<<"终结符Vt={ ";
	     for(i=0;i<strlen(VT);i++)
		cout<<VT[i]<<"、";
	     cout<<'\b'<<" }共有:"<<strlen(VT)<<"个;"<<endl;
			
             }//display_GZ结束
void WenFa::display_Ys(void){//显示元素
                int i,j,k,cnt1=0,cnt2=0;
                bool bool1,bool2;
                for(i=0;i<GZS;i++){
                     bool1=false;
                     for(j=0;j<cnt1;j++)
                         if(VN[j]==gz[i].gz_q) {bool1=true;break;}
                     if(!bool1) VN[cnt1++]=gz[i].gz_q;
                     for(j=0;j<strlen(gz[i].gz_h);j++){
						 if(!(gz[i].gz_h[j]>='A'&&gz[i].gz_h[j]<='Z')&&gz[i].gz_h[j]!=' '){
                              bool2=false;
                              for(k=0;k<strlen(VT);k++)
                                 if(VT[k]==gz[i].gz_h[j])  {bool2=true;break;}
								 if(bool2==false) VT[cnt2++]=gz[i].gz_h[j];}
                      }
                }
             VN[cnt1]=VT[cnt2]=0;
             cout<<endl;
        
     Sbf=VN[0];
	 cout<<"识别符为:"<<Sbf<<endl;
        }//display_ys结束*/
   //压缩文法等价规则
bool WenFa::BoolAll(void){
 for(int i=0;i<GZS;i++)
   if(gz[i].boolq==false&&!gz[i].boolde)  return false;
 if(i==GZS) return true;

}//
bool WenFa::TiaoJ1(){//条件1
     int i=0,j,k,cnt=0;
	 bool boolbj=false;//是否加过标记
	 while(1){
       if(gz[i].boolde==false&&gz[i].boolq==true){//没有加删除标记并且是加了标记的非终结符
              if(gz[i].cnt>0)//右部有非终结符
                  for(j=0;j<strlen(gz[i].gz_h);j++)
                      if(gz[i].gz_h[j]>='A'&&gz[i].gz_h[j]<='Z'&&gz[i].boolh[j]==false){
						  gz[i].boolh[j]=true;
                            for(k=0;k<GZS;k++)//与该非终结符相同并且没加标记的全加
                                 if(!gz[k].boolde&&k!=i&&gz[k].gz_q==gz[i].gz_h[j]&&gz[k].boolq==false)
								    gz[k].boolq=true;//cout<<k<<gz[k].gz_q<<"  ";//******注意******
								    boolbj=true;
					  }
              }// i=0;
	 if(BoolAll()) break;//全加标记
	 else if(boolbj==false)   break;//最后一次没加"}
      i++;
	  if((i=(i%GZS))==0) boolbj=false;
     }
			  for(i=0;i<GZS;i++){
				  if(!gz[i].boolq&&!gz[i].boolde) {gz[i].boolde=true;cnt++;}
				  gz[i].boolq=false;
				  for(int j=0;j<strlen(gz[i].gz_h);j++)
					  if(gz[i].cnt>0) gz[i].boolh[j]=false;
			  }
	  if(cnt>0) {des+=cnt; return true;}
			     else if(cnt==0)  return false;
			
}//Tiaoj1结束
bool WenFa::TiaoJ2(void){
	int i=0,j,k,k1,cnt1=0;
	bool boolbj=true;
    
	while(1){
		if(!gz[i].boolde&&gz[i].cnt>0){
			for(j=0;j<strlen(gz[i].gz_h);j++)
				if(gz[i].gz_h[j]>='A'&&gz[i].gz_h[j]<='Z'&&gz[i].boolh[j]==false)//是非终结符并且没加了标记
					             break;
			if(j==int(strlen(gz[i].gz_h))&&!gz[i].boolq){//判定都加了标记
				gz[i].boolq=true; boolbj=true;
			    for(k=0;k<GZS;k++)
			    	if(i!=k&&!gz[k].boolde&&gz[k].cnt>0)
					   for(k1=0;k1<strlen(gz[k].gz_h);k1++)
						if(gz[k].gz_h[k1]==gz[i].gz_q&&gz[k].boolh[k1]==false)
								 gz[k].boolh[k1]=true;
			}
					
			
			
		}
		if(BoolAll()) break;//全加标记"
		else if(boolbj==false)  break;//最近一次没加"
      i++;
	  i=i%GZS;
	 if(i==0) boolbj=false;
	}

    for(i=0;i<GZS;i++){
		  if(!gz[i].boolq&&!gz[i].boolde) {gz[i].boolde=true;cnt1++;}
				    gz[i].boolq=false;
				  for(int j=0;j<strlen(gz[i].gz_h);j++)
					  if(gz[i].cnt>0) gz[i].boolh[j]=false;
			  }
 if(cnt1>0) {des+=cnt1; return true;}
	    else if(cnt1==0)   return false;
		
}//Tiaoj2结束

void WenFa::YaSou(void){
	int i,k,k1,j;
	
       for( i=0;i<GZS;i++)
			if(gz[i].cnt==1&&strlen(gz[i].gz_h)==1&&gz[i].gz_h[0]==gz[i].gz_q)
			{gz[i].boolde=true;des++;}
	 do{ for(i=0;i<GZS;i++)
		    if(gz[i].gz_q==gz[0].gz_q)
		     gz[i].boolq=true;//给识别符加标记
	     bool TJ1=TiaoJ1();
        

	     //为右部都是终结符的规则左部加标记
	   
	for(i=0;i<GZS;i++){
	       if(!gz[i].boolde&&gz[i].cnt==0){//没有非终结符并且没有被删除
				 gz[i].boolq=true;
             for(k=0;k<GZS;k++)
				if(!gz[k].boolde&&gz[k].cnt>0)
							for(k1=0;k1<strlen(gz[k].gz_h);k1++)
								if(!gz[k].boolde&&gz[k].gz_h[k1]==gz[i].gz_q&&gz[k].boolh[k1]==false)
									gz[k].boolh[k1]=true;
				}
						
			}//for
	 bool TJ2=TiaoJ2();
	 if(!TJ2&&!TJ1)  break;
 
			}while(1);
    int cnt=0;//为了换行 
	cout<<"最后的压缩结果为："<<endl;
	for( i=0;i<GZS;i++){
			if(!gz[i].boolde)
				{cout<<gz[i].gz_q<<"::="<<gz[i].gz_h<<"     ";cnt++;}
			if(cnt%3==0)  cout<<endl;
		 }
	cout<<endl;
}//Yasou结束
void WenFa::Find(FA *f){
	int i,j,cnt,k,k1;
	char s[3];
	for(i=0;i<strlen(VT);i++){
		cnt=0;
		for(j=0;j<strlen(f->fa_q);j++){
			if(j==0&&f->fa_q[j]=='S') {s[0]=VT[i];s[1]=0;}
			else {s[0]=f->fa_q[j];s[1]=VT[i];s[2]=0;}
			for(k=0;k<GZS;k++)
				if(strcmp(gz[k].gz_h,s)==0){
					for( k1=0;k1<strlen(f->fa_h[i]);k1++)
						if(f->fa_h[i][k1]==gz[k].gz_q) break;
					if(k1==strlen(f->fa_h[i])) f->fa_h[i][cnt++]=gz[k].gz_q;
				}
		}
		f->fa_h[i][cnt]=0;
		//给每一个字符排序避免重复
		int n=strlen(f->fa_h[i]);
		 if(n>1) {for(j=0;j<n;j++)
	             for(k=0;k<n;k++)
		         if((f->fa_h[i][j])<(f->fa_h[i][k]))
		         {char w=f->fa_h[i][j];f->fa_h[i][j]=f->fa_h[i][k];f->fa_h[i][k]=w;}
		         }
		
	}

}//find结束
void WenFa::NchD(void){
	int cnt=1,i,j,k;
	int n=int(strlen(VN))+1;
	int m=int(pow(2,n)-1);
	if(m<=0) {cout<<"状态个数小于等于零出错！";return;}
	 else{
	      fa=new FA[m];
		  if(!fa) cout<<"存储空间分配失败"<<endl;
	      strcpy(fa[0].fa_q,"S");
	      for(i=0;i<m;i++)
		      if(strlen(fa[i].fa_q)!=0){
		      	      for(int k1=0;k1<strlen(VT);k1++)
		      	        fa[i].fa_h[i][0]=0;
		                Find(fa+i);
		               for(j=0;j<strlen(VT);j++)
		                  if(strlen(fa[i].fa_h[j])!=0){
		                  	for(k=0;k<cnt;k++)				
				               if(strcmp(fa[k].fa_q,fa[i].fa_h[j])==0) break;
				            if(k==cnt)  strcpy(fa[cnt++].fa_q,fa[i].fa_h[j]);
				          }
		     }
		     else break; //没有可用状态

	OutNchD(cnt);
	}
}//NchD结束
void WenFa::OutNchD(int s){	//规范化输出
	 int cnt=s;
	 int i,j,k;
	 char *Ls=new char[cnt];//临时存放替换符
	 bool *bl=new bool[cnt];//临时存放识别符
     for(i=0;i<cnt;i++){//为替换字符设初值
     	bl[i]=false;
     	for(int i1=0;i1<strlen(fa[i].fa_q);i1++)
     	    if(fa[i].fa_q[i1]==Sbf) //等于识别符时
     	      {bl[i]=true; break;}
     	    	 Ls[i]=65+i;
     }
     Ls[0]='S';
     cout<<"(注:替换形式)  ";
	 for(i=1;i<cnt;i++) 
		  cout<<Ls[i]<<"-->"<<fa[i].fa_q<<"  ";		
	  cout<<endl;
	 cout<<"转化后的DFA D=｛Ｋ，∑，Ｍ，Ｓ，Ｚ｝其中:"<<endl;
	 cout<<"Ｋ＝｛";
	 for(i=0;i<cnt;i++)
		 cout<<Ls[i]<<"、";
         cout<<'\b'<<" ｝"<<endl;
         cout<<"∑＝｛";
      for(i=0;i<strlen(VT);i++)
		  cout<<VT[i]<<"、";
	     cout<<'\b'<<" ｝"<<endl;
     cout<<"Ｍ:"<<endl;;
	 for(i=0;i<cnt;i++){
		for(j=0;j<strlen(VT);j++)
		  if(strlen(fa[i].fa_h[j])!=0)
		      {for(k=0;k<cnt;k++)
		        if(strcmp(fa[k].fa_q,fa[i].fa_h[j])==0)
		          break;
		      cout<<"Ｍ（"<<fa[i].fa_q<<"，"<<VT[j]<<"）＝"<<fa[i].fa_h[j]<<"   ";
		      }
	cout<<endl;
	 }
	 cout<<"Ｓ＝｛　"<<Ls[0]<<"　｝"<<endl;
	 cout<<"Ｚ＝｛　";
	 for(i=0;i<cnt;i++)
	     if(bl[i])
	       cout<<Ls[i]<<"、";
	 cout<<'\b'<<" ｝"<<endl;
	 //输出结束
	delete []Ls;
	delete []bl;
}