predictiveparser.cpp

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

#include"PredictiveParser.h"//预测分析头文件
PrePar::PrePar(){
		scopy=Str=new char[r];
		do{
		if(WFinput()) break;
		}while(1);
		VN_NUM=strlen(VN);
		VT_NUM=strlen(VT);
		if(VN_NUM==0||VT_NUM==0){cout<<"终结符或非终结符为零,程序不能继续进行!"<<endl;exit(0);}
		table=new int[VN_NUM+3][r];	
		first=new struct FI_FOL [VN_NUM];
		follow=new struct FI_FOL [VN_NUM];
		for(int i=0;i<VN_NUM;i++){
			for(int d=0;d<=VT_NUM;d++)
			    	table[i][d]=0;
			first[i].element=new char[VT_NUM];
			follow[i].element=new char[VT_NUM];
			follow[i].element[0]=first[i].element[0]=0;
			first[i].text=(follow+i)->text=VN[i];
			first[i].cnt=follow[i].cnt=0;
			first[i].bo_link= new bool[VN_NUM];
			follow[i].bo_link=new bool[VN_NUM];
            for(int j=0;j<VN_NUM;j++)
				 first[i].bo_link[j]=follow[i].bo_link[j]=false;
		}
		
	}
PrePar::~PrePar(){
		delete []first;
		delete []follow;
		delete []table;
	}
int PrePar::Search_text(char s){
		int i;
		for(i=0;i<VN_NUM;i++)
			if(s==first[i].text)
			return i;
	}
bool PrePar:: Equal(char *p1,char *p){//判断p1中是否已经有p 了
	char *r;
	while(*p1){
	 r=p;
	 if(*p1==*r){
		 while(*r)
			 if(*p1!=*r) break;
			 else {p1++;r++;}
		 if(*r=='\0') return true;
	 }
      p1++;
	 
	}
    return false;
	
	}
 void PrePar::fo_fCat(struct FI_FOL *fo_f){//集合相等的都赋值
		int i,j,k,t;//循环变量和中间变量
		int cnt;
		do{cnt=0;
			for(i=0;i<VN_NUM;i++){
				fo_f[i].bo_link[i]=false;
				t=Test(fo_f,i);//测试i的bo_link
				if(t==VN_NUM){//全为假
					for(j=0;j<VN_NUM;j++)
						if(fo_f[j].bo_link[i]==true&&i!=j){//某个的bo_link指向全为假的这个(下标为i),就把他的所有element元素加到自己的element里
					           	if(!Equal(fo_f[j].element,fo_f[i].element)){
					             	strcat(fo_f[j].element,fo_f[i].element);
					 	            fo_f[j].cnt=strlen(fo_f[j].element);
					       	       fo_f[j].bo_link[i]=false;
						        }
					        	else fo_f[j].bo_link[i]=false;
						}
				}
				else
				  if(t==VN_NUM-1){//只有一个为真
					for(j=0;j<VN_NUM;j++)
						if(fo_f[i].bo_link[j]) k=j;//判断那个为真
					if(Test(fo_f,k)==VN_NUM-1&&fo_f[k].bo_link[i]==true){//K也有一个为真,并且是相对的
								char *temp=new char[80];
								strcpy(temp,fo_f[i].element);
								strcat(temp,fo_f[k].element);
								strcpy(fo_f[i].element,temp);
								strcpy(fo_f[k].element,temp);
								fo_f[i].cnt=fo_f[k].cnt=strlen(temp);
								fo_f[i].bo_link[k]=fo_f[k].bo_link[i]=false;
								delete []temp;
					}
				}				
			  }
			for(i=0;i<VN_NUM;i++)
				if(Test(fo_f,i)==VN_NUM)
					cnt++;
			if(cnt==VN_NUM) break;//所有元素的bo_link全为假时结束
		}while(1);
	}
void PrePar::Fin_first(void){//形成first集合
		int i,n;
		for(i=0;i<GZS;i++){//第一个文法规则判断一次
			n=Search_text(gz[i].gz_q);//查右部第一个子符是first集合的第几个
			if(gz[i].gz_h[0]>='A'&&gz[i].gz_h[0]<='Z'){//右部第一个非终结符的first是左部了first 
				int x=Search_text(gz[i].gz_h[0]);
				first[n].bo_link[x]=true;
				}
		  else{
		  int j=first[n].cnt;
		  first[n].element[j++]=gz[i].gz_h[0];
		  first[n].element[j]=0;
		  first[n].cnt=j;
		  }
		}
	  fo_fCat(first);//给element元素赋值
	}
void PrePar::print(bool b){
		if(b){cout<<"FOLLOW集合:"<<endl;
			for(int i=0;i<VN_NUM;i++){
			cout<<follow[i].text<<"    "<<follow[i].cnt<<"    "<<follow[i].element<<endl;
			/* for(int j=0;j<VN_NUM;j++)
				 cout<<follow[i].bo_link[j]<<"  ";
			 cout<<endl;*/
		}
		}
		else{cout<<"FRIST集合:"<<endl;
		for(int i=0;i<VN_NUM;i++){
			cout<<first[i].text<<"    "<<first[i].cnt<<"    "<<first[i].element<<endl;
			/* for(int j=0;j<VN_NUM;j++)
			   cout<<first[i].bo_link[j]<<"  ";
		      cout<<endl;*/
		}
		}
	}
	
bool PrePar::bool_kou(char s){
		int n=Search_text(s);
		for(int i=0;i<first[n].cnt;i++)
			if(first[n].element[i]=='$') return true;
		return false;
	}
 void PrePar::Fin_follow(void){
		int i,j;//循环变量
		int n=Search_text(Sbf);//找识别符的编号
		strcpy(follow[n].element,"#");
		follow[n].cnt+=1;

		for(i=0;i<GZS;i++){//步骤2
		    int len=strlen(gz[i].gz_h);//每个规则右部的长度
			if(len>=2&&gz[i].gz_h[len-2]>='A'&&gz[i].gz_h[len-2]<='Z'){//右部长度大于2且到数第二个字符为非终结符
                      int x=Search_text(gz[i].gz_h[len-1]);
			          int x2=Search_text(gz[i].gz_h[len-2]);
					  if(gz[i].gz_h[len-1]>='A'&&gz[i].gz_h[len-1]<='Z'){//右部最后一个字符为非终结符把的first集合中除'$'的给它赋给
						for(j=0;j<first[x].cnt;j++)
						 if(first[x].element[j]!='$'){//不为空
							 for(int k=0;k<follow[x2].cnt;k++)
								 if(follow[x2].element[k]==first[x].element[j])  break;
							 if(k==follow[x2].cnt){//不存放已经有的符号
								follow[x2].element[follow[x2].cnt++]=first[x].element[j];
								follow[x2].element[follow[x2].cnt]=0;
							 }
						 }
					  }//if
						else{//最后一个是终结符
							follow[x2].element[follow[x2].cnt++]=gz[i].gz_h[len-1];
							follow[x2].element[follow[x2].cnt]=0;
						}//else
			}
					
		}//for 步骤2结束
		for(i=0;i<GZS;i++){//步骤3
			int len=strlen(gz[i].gz_h);//每个规则右部的长度
			int x=Search_text(gz[i].gz_h[len-1]);
			int x1=Search_text(gz[i].gz_q);
			if(gz[i].gz_h[len-1]>='A'&&gz[i].gz_h[len-1]<='Z'&&gz[i].gz_q!=gz[i].gz_h[len-1])				
				   follow[x].bo_link[x1]=true;
			if(len>=2)
			 for(j=len-1;j>=0;j--)
				if(gz[i].gz_h[j]>='A'&&gz[i].gz_h[j]<='Z'&&bool_kou(gz[i].gz_h[j]))//是否当前的非终结符的first集合含空规则
					  if(gz[i].gz_h[j-1]>='A'&&gz[i].gz_h[j-1]<='Z'&&gz[i].gz_q!=gz[i].gz_h[j-1]){
					    int x2=Search_text(gz[i].gz_h[j-1]);
				        follow[x2].bo_link[x1]=true;
					  }
					  else break;
			
				else break;
		}//for
    fo_fCat(follow);//给element元素赋值
  	}
 int PrePar::Test(struct FI_FOL *f,int a){
	 int cnt=0;
	 for(int i=0;i<VN_NUM;i++)
		 if(f[a].bo_link[i]==false) cnt++;
		 	 return cnt;
 }

 int PrePar::Search_VN(char ch){//在非终结符中找
	 int a;
	 for( a=0;a<VN_NUM;a++)
			 if(ch==VN[a])  return a;
	 
 }
 int PrePar::Search_VT(char c){
	 int i;
	 if(c=='#')
		 return VT_NUM;
   	for(i=0;i<VT_NUM;i++)
	   if(c==VT[i])  return i;
 }
	
 void PrePar::CreateTable(){
	 int i,j;
	 int q,l,r;//规则前部,table的行和列
	  for(i=0;i<GZS;i++){
		 q=l=Search_VN(gz[i].gz_q);
		 if(gz[i].gz_h[0]>='A'&&gz[i].gz_h[0]<='Z'){
			 int k=Search_text(gz[i].gz_h[0]);
			 for(j=0;j<first[k].cnt;j++){
             	r=Search_VT(first[k].element[j]);
				    table[l][r]=i+1;
				 }
				 
		 }//if
		 else if(gz[i].gz_h[0]=='$'){
				 int k=Search_text(gz[i].gz_q);
			     for(j=0;j<follow[k].cnt;j++){
					r=Search_VT(follow[k].element[j]);
					table[l][r]=i+1;				
				 }
			 }		 
		 else{ 
		 if(gz[i].gz_h[0]>='A'&&gz[i].gz_h[0]<='Z')
              r=Search_VN(gz[i].gz_h[0]);
	        else
		      r=Search_VT(gz[i].gz_h[0]);
			table[l][r]=i+1;
		 }
		
		
	 }
	 
 }//createTable
 void PrePar::PrintTable(){
	 int i,j;
	 cout<<"    ";
	 for(i=0;i<VT_NUM;i++){
		 if(VT[i]!='$')
		 cout<<"     "<<VT[i];
		 for(int j=i;j>=0;j--)
			 cout<<"  ";
	 }
	 cout<<"    #";
	 cout<<endl;
      for(i=0;i<VN_NUM;i++){
		  cout<<VN[i]<<"  |";
	    for(j=0;j<=VT_NUM;j++){
	         int k=table[i][j];
			 if(k!=0) 
				 cout<<gz[k-1].gz_q<<"::="<<gz[k-1].gz_h<<"     ";//
			 else cout<<"         ";
	  }
		 cout<<endl;
	  }
 }
 char PrePar::get(){//取字符
		if(*scopy) { char p=*scopy;scopy++;return p;}
		 else return '#';
	}
void  PrePar::Error(){
		cout<<endl<<"推导失败!";
		cout<<endl<<Str<<"不是该方法的句子!"<<endl;
        exit(1);
	}
 void PrePar::Fenxi(){
	 Stack s;
	 cout<<"请输入一个需要判断的字符串:";
	 cin>>Str;
	 strcpy(scopy,Str);
	 s.Push('#');s.Push(Sbf);
	 char X;
	 char sym=get();
	 bool Flag=true;
	 while(Flag){
		 X=s.Top();
		 cout<<"栈顶元素:"<<X<<endl;
		 cout<<"当前输入字符:"<<sym<<endl;
		 if(!(X>='A'&&X<='Z'))
			 if(X==sym)
				 if(sym=='#') Flag=false;
				 else{s.Pop();sym=get();}
			 else Error();

		 else{ 
				 int l=Search_VN(X);
				 int r=Search_VT(sym);
				 int e=table[l][r];//第几个规则
				 if(e>0){//该位置有规则
					 s.Pop();
					 cout<<"所有规则为:"<<gz[e-1].gz_q<<"::="<<gz[e-1].gz_h<<endl;
					 if(gz[e-1].gz_h[0]!='$')//不是型如:E::=$
						 for(int i=strlen(gz[e-1].gz_h)-1;i>=0;i--)
							 s.Push(gz[e-1].gz_h[i]);
				 }
				 else Error();
			 }
		 if(Flag==false) cout<<Str<<"是该文法的句子."<<endl;
	 }
 }
 void PrePar::Init(){//初始化
	 char ch;
    cout<<"是否输入First和Follow集合:(Y/N)";
    cin>>ch;
    Fin_first();
	if(ch=='Y'||ch=='y')
    print(false);
	Fin_follow();
   if(ch=='Y'||ch=='y')
	print(true);
	CreateTable();
    PrintTable();
	}