cfgsimplified.cpp

CFG上下文无关文法的化简程序

// CFGSimplified.cpp : Defines the entry point for the console application.
//@author LiuHao ShenZhen University 刘浩 2008年11月1日

#include "stdafx.h"
#include "CFGSimplified.h"
#include <sstream>
#include   <stdio.h>   

void Simplify::InitParam(){//初始化,输入要化简的CFG
	int i=0;
	cout<<"请认真阅读完下面的说明后按提示操作"<<endl;
	cout<<"请输入非终结符号集N，每两个非终结符号间空一格，每两个字符都不能相等，全部输入完毕后再输入#回车"<<endl;
	cout<<"注意每个非终结符只能用一个字符表示，最好是大写的英文字母,可以输入最多10个字符"<<endl;
    while(true){
		cin>>N[++i];
		if (N[i]=='#'||i>=10) break;//输入#号表示输入完毕
			}
		NO_N=i;
       // cout<<"NO_N="<<NO_N<<endl;
 
		i=0;
		 fflush(stdin); //清除缓冲区
		cout<<"请输入终结符号集T，每两个终结符号间空一格，每两个字符都不能相等，全部输入完毕后再输入#回车"<<endl;
		cout<<"注意每个终结符只能用一个字符表示，最好是小写的英文字母和数字标点，且不能为#"<<endl;
		cout<<"可以输入最多10个字符"<<endl;
		while(true){
		cin>>T[++i];
		if (T[i]=='#'||i>=10) break;//输入#号表示输入完毕
			}
         NO_T=i;
	//	 cout<<"NO_T="<<NO_T<<endl;
		
		i=0;
			cout<<"请输入产生式集P，每输入完一个产生式回车，不要输入两个完全一样的产生式"<<endl;
		cout<<"注意产生式应当写成诸如S->AwB|BaV等合法的形式，→用->代替，若产生式已经输入完，则输入#回车"<<endl;
		cout<<"最多可以输入的产生式为20个"<<endl;
	    fflush(stdin); //清除缓冲区
		while(true){
	
		cout<<"请输入第"<<i+1<<"个产生式，每输入完一个产生式回车"<<endl;

		cin>>P[++i].value;
		//cout<<"子串"<<P[i].substr(1,2)<<endl;
		if(P[i].value.substr(1,2)!="->"&&P[i].value!="#"){
			cout<<"您输入的字符串不合法，请认真阅读上面的说明并重新输入！注意大小写"<<endl;
			i--;
									}
		if (P[i].value=="#"||i>=20)	break;//输入#号表示输入完毕
		}
        NO_P=i;
	//	 cout<<"NO_P="<<NO_P<<endl;

			
		fflush(stdin); //清除缓冲区
		cout<<"请输入开始符号集S回车"<<endl;
		cin>>S;

       int tmp=0;
		while(true){
			fflush(stdin); //清除缓冲区
		for(int j=1;j<=NO_N;j++){
			//cout<<"N["<<j<<"]="<<N[j]<<endl;
			if(N[j]==S) {
				tmp=1;	}     
								}
            if(tmp==1) break;
			cout<<"您输入的开始符号不在非终结符集里面，请检查后重新输入。注意大小写。"<<endl;
          
        	cout<<"请输入开始符号集S回车"<<endl;
			cin>>S;
		}
}
void Simplify::separate(){//将产生式中含'|'的通通分解，使最终的产生式不含'|'
	cout<<"下面为分解产生式，使之不含|的过程"<<endl;
	string str[20];
	int c=0;
	for(int m=1;m<=NO_P;m++){
		str[m]=P[m].value;}
	for(int m1=1;m1<=NO_P;m1++){
		if(str[m1].substr(0)=="#") break;
		while(true){
		int l=str[m1].find("|",3);
		if(l!=-1) 
		{P[++c].value=str[m1].substr(0,l);
		P[c].count=1;
		cout<<"产生式"<<P[c].value<<endl;
		str[m1].erase(3,l-2);}
		else
		{ P[++c].value=str[m1].substr(0);
		P[c].count=1;
			cout<<"产生式"<<P[c].value<<endl;
			break;}
		
		//cout<<"l="<<l<<endl;
		//cout<<"str="<<str[m1]<<endl;
		}//while
}//for m1
	NO_P=c;

	//更新产生式集P[NO_P]
		Produce str1[20];
		int c1=0;
		for(int q=1;q<=NO_P;q++){
			str1[q]=P[q];}
		for(int q1=1;q1<=NO_P;q1++){
		            
					P[++c1].flag=0;
					P[c1].value=str1[q1].value;
					P[c1].count=0;
		}//for q
			//	cout<<"P[1]="<<P[1].flag<<endl;
}

void Simplify::Step1(){//找出有用的非终结符

		cout<<"下面为找出有用的非终结符(即所有能直接或间接推出终结符串的非终结符)的过程"<<endl;
//	cout<<"NO_P="<<NO_P<<endl;
		int acount=0;//统计次数
	for(int i=1;i<=NO_P;i++){
	
		if (P[i].value=="#") break;
		for(int j=1;j<=NO_T;j++){//能直接推出终结符的有用，并加上标记
			stringstream ss;
			ss<<T[j];//将Char转换为string
			string s=ss.str();
			if(P[i].value.substr(3)==s&&s!="#") 
			{
				cout<<"产生式"<<P[i].value<<"有用"<<endl;
			P[i].flag=1;//标记为step1
			acount++;
			}
								}

	
							}


for(int t=1;t<=NO_P;t++){//所有有用产生式的个数不会超过产生式的个数，因此t不会超过NO_P
//cout<<"t="<<t<<endl;
	for(int n=1;n<=NO_P;n++){
				
				for(int k=1;k<=NO_P;k++){//能间接推出终结符的有用，加上标记
						 if(P[n].flag==1&&k!=i){
					if((P[k].value.find(P[n].value.substr(0,1),3)!=-1)&&P[k].count!=1) 
					{		cout<<"产生式"<<P[k].value<<"有用"<<endl;
							P[k].count=1;//已经加入了有用产生式的集合，不必第二次加入		
						P[k].flag=1;//标记为step1
						acount++;
						//cout<<P[k].value<<P[k].flag<<endl;
					}//if P[n] substr
														
			 }// if p[n] flag
	

			
										}//for k


						}//for n
}//for t

	//更新产生式集P[NO_P]
		Produce str2[20];
		
//	cout<<"NO_P="<<NO_P<<endl;
		for(int b=1;b<=NO_P;b++){
		str2[b]=P[b];
	
		//cout<<"str2["<<b<<"]="<<str2[b].value<<endl;
	//	cout<<"str2["<<b<<"]="<<str2[b].flag<<endl;
		}//for
		int b1=1;
		int c2=0;
	while(true){
			if(str2[b1].flag==1&&str2[b1].value.substr(3)!="#") {
					P[++c2].flag=str2[b1].flag;
					P[c2].value=str2[b1].value;
					P[c2].count=0;
						}
			b1++;
			if(b1>NO_P) break;
		}//while
	       NO_P=acount;
		//	cout<<"NO_P="<<NO_P<<endl;
	
        
}

void Simplify::Step2(){//找出有用符号
cout<<"下面为找出有用符号，删除开始符号无法到达的符号与产生式的过程"<<endl;
int bcount=0;//统计次数

	for(int i1=1;i1<=NO_P;i1++){
		if(P[i1].value.substr(3)=="#") break;
			P[i1].count=0;
			stringstream ss1;
			ss1<<S;//将Char转换为string
			string s1=ss1.str();
			//cout<<"s1="<<s<<endl;
			//开始符号能直接到达的有用
			//cout<<P[i1].value.substr(0,1)<<endl;
			if(P[i1].value.substr(0,1)==s1){ P[i1].flag=2;//标记为step2
														P[i1].count=1;
													cout<<"产生式"<<P[i1].value<<"有用"<<endl;
														bcount++;}
	}//for i1

for(int t1=1;t1<=NO_P;t1++){//所有有用产生式的个数不会超过产生式的个数，因此t1不会超过NO_P
	for(int j1=1;j1<=NO_P;j1++){//P[j]直接可达
		for(int k1=1;k1<=NO_P;k1++){
			for(int n1=1;n1<=NO_N;n1++){
				stringstream ss2;
				ss2<<N[n1];//将Char转换为string
				string s2=ss2.str();
					//开始符号能间接到达的有用
				if((P[j1].value.find(s2,3)!=-1)&&P[j1].flag==2&&P[j1].value.substr(3)!="#"){
					if(P[k1].value.substr(0,1)==s2&&P[k1].count==0&&k1!=j1){
										P[k1].flag=2;//标记为step2
										P[k1].count=1;
										cout<<"产生式"<<P[k1].value<<"有用"<<endl;
										bcount++;
					}//if  P[k1]
				}//if P[1j]
			}//for n1
		}//for k1
	}//for j1
}//for t1


	//更新产生式集P[NO_P]
		Produce str2[20];
		
//	cout<<"NO_P="<<NO_P<<endl;
		for(int b=1;b<=NO_P;b++){
		str2[b]=P[b];
	
		//cout<<"str2["<<b<<"]="<<str2[b].value<<endl;
	//	cout<<"str2["<<b<<"]="<<str2[b].flag<<endl;
		}//for
		int b1=1;
		int c2=0;
	while(true){
			if(str2[b1].flag==2&&str2[b1].value.substr(3)!="#") {
					P[++c2].flag=str2[b1].flag;
					P[c2].value=str2[b1].value;
					P[c2].count=0;
						}
			b1++;
			if(b1>NO_P) break;
		}//while
	       NO_P=bcount;
			//cout<<"NO_P="<<NO_P<<endl;

}
void Simplify::Step3(){//消除ε产生式
	cout<<"下面为消除ε产生式的过程，为便于输入用^代替ε"<<endl;
	cout<<"若出现小写的s，则加入了新的产生式，s为新的开始符号"<<endl;
	//找出所有能导出ε产生式的非终结符
	string str[30];
	int T=0;
	for(int i=1;i<=NO_P;i++){
		if(P[i].value.substr(3)=="#") break;
			P[i].count=0;
		if(P[i].value.substr(3)=="^"){
			P[i].count=1;
			stringstream sst;
				sst<<S;//将Char转换为string
				string st=sst.str();
			cout<<P[i].value.substr(0,1)<<"能推出ε"<<endl;
			if(P[i].value.substr(0,1)!=st) cout<<"应当删除"<<endl;
			str[++T]=P[i].value.substr(0,1);}
	}//for i

	for(int m=1;m<=NO_P;m++){
	for(int j=1;j<=NO_P;j++){
		if(P[j].value.substr(3)=="#") break;
	
			int tmp=0;
			for(int k=1;k<=T;k++){
					if(str[k]!=P[j].value.substr(0,1)){
					tmp++;
				}//if
			}
			
			if (tmp>=T) tmp=1;
			for(k=1;k<=T;k++){
					if(str[k]==P[j].value.substr(3)&&P[j].count!=1&&tmp==1){
					P[j].count=1;
						cout<<P[k].value.substr(0,1)<<"能推出ε"<<endl;
					str[++T]=P[k].value.substr(0,1);
				}//if
				
			}//for k
		

	}//for j
	}//for m

	//消去除初始符号推出的ε产生式
				int	T1=0;
			stringstream ss1;
			ss1<<S;//将Char转换为string
			string s1=ss1.str();//开始符号
	for(int n=1;n<=T;n++){
		if(str[n]!=s1){//非开始符号
			for(int v=1;v<=NO_P;v++){
				if(str[n]==P[v].value.substr(0,1)&&P[v].value.substr(3)!="^"){
					P[v].flag=3;
					cout<<"产生式"<<P[v].value<<"加入消除ε后的产生式"<<endl;
					T1++;}
			}//for v
		}//if str[n]!=
		else{//开始符号S推出ε，则引入新的开始符号s能推出S和ε

				for(int v1=1;v1<=NO_P;v1++){
				if(str[n]==P[v1].value.substr(0,1)&&P[v1].value.substr(3)!="^"){
					P[v1].flag=3;
					cout<<"产生式"<<P[v1].value<<"加入消除ε后的产生式"<<endl;
					T1++;}
			}//for v1
			N[++NO_N]='s';
			P[++NO_P].value ="s->^";
				P[NO_P].flag=3;
					T1++;
				cout<<"产生式"<<P[NO_P].value<<"加入消除ε后的产生式"<<endl;
			P[++NO_P].value="s->"+s1;
				P[NO_P].flag=3;
					T1++;
				cout<<"产生式"<<P[NO_P].value<<"加入消除ε后的产生式"<<endl;
		}//else
	}//for n

		//更新产生式集P[NO_P]
		Produce str2[20];
		
//	cout<<"NO_P="<<NO_P<<endl;
		for(int b=1;b<=NO_P;b++){
		str2[b]=P[b];
	
		//cout<<"str2["<<b<<"]="<<str2[b].value<<endl;
	//	cout<<"str2["<<b<<"]="<<str2[b].flag<<endl;
		}//for
		int b1=1;
		int c2=0;
	while(true){
			if(str2[b1].flag==3&&str2[b1].value.substr(3)!="#") {
					P[++c2].flag=str2[b1].flag;
					P[c2].value=str2[b1].value;
					P[c2].count=0;
						}
			b1++;
			if(b1>NO_P) break;
		}//while
	       NO_P=T1;
			//cout<<"NO_P="<<NO_P<<endl;
}

int main()
{
	Simplify sim;
     sim.InitParam();//初始化,输入要化简的CFG
	 sim.separate();//将产生式中含'|'的通通分解，使最终的产生式不含'|'
	 sim.Step1();//找出有用的非终结符
	 sim.Step2();//找出有用符号
	 sim.Step3();//消除ε产生式

	 cout<<"输出结束，回车将退出";
	 getchar();   //保存屏幕输出
	return 0;
}