fengsuyun.cpp

本程序主要是用于编译原理中的语法分析用的是vc++语言

#include <iostream.h>//本软件用于面向对象（Visual C++）软件的质量度量
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
int wfnum,x,y,z,rl;
int fst,f;
class yufa{
//private:
       //int wfnum,x,y,z,rl;
      // int fst,f;
public:
      char wenfa[50][50],wenfa_old[50][50],cwf[50][50],cwfbj[50][50];
      char DFA[50][50][50];
      char VNA[2][50],VT[50];
      char relation[200][5];
      char FIRST[50][50];
      char *action[50][50],akt[50][50][10];
      int goto1[50][50];
      int initlize();
      int check(char x);
      int VN_test(char tv[50][50]);
      int VN_first(char n,char tx[50][50],char test[20]);
      int FIRST_creat(char tm[50][50]);
	  int input();
	  int DFA_opt(char ll[50][50][50],int p);
      int DFA_Creat(char crt[10][50],int cishu);
      int xam(char inpt[50],char digui_test[50]);
	  int A_Creat(char crt[10][50],int cishu);
	  int fenxi();
	  int fenxi_opt();
	  int LR1();
};
int yufa:: initlize(){//初始化wenfa[50][50],wenfa_old[50][50]和DFA[50][50][50]
	int i,j,k;
	for(i=0;i<50;i++)
		for(j=0;j<50;j++)
			for(k=0;k<50;k++)
				DFA[i][j][k]='\0';
    for(i=0;i<50;i++)
		for(j=0;j<50;j++){
			wenfa[i][j]='\0';
			wenfa_old[i][j]='\0';
			cwfbj[i][j]='\0';
		}//for
	for(i=0;i<50;i++)
		for(j=0;j<50;j++){
			FIRST[i][j]='\0';
			action[i][j]="NULL";
			goto1[i][j]=0;
		}//for
	return(1);
}//initlize
int yufa::check(char x){
	//if(isalpha(x)||isdigit(x)||x=='+'||x=='-'||x=='*'||x=='/'||x=='('||x==')'||x=='#'||x=='\n'||x=='\0'||x=='>'||x==' ')
	if(x=='@'||x==',')
		return (0);
	else
		return (1);
}//check

int yufa:: VN_test(char tv[50][50]){
	char del_VN,test_VNA[50];
	int i,j,vna=0,t=0,s=0,wfgs,d=0,b=0,m=0;
	int count=0;
	for(i=0;i<=wfnum;i++){//找出文法里面所有的非终结符
		j=0;
		while(tv[i][j]!='\0'){
			if(isupper(tv[i][j])){
				s=0;t=0;
				while(t<vna){
					if(VNA[0][t]==tv[i][j]){
						s=1;
						break;
					}//if
					t++;
				}//while
				if(s==0)VNA[0][vna++]=tv[i][j];
			}//if
			j++;
		}//while
	}//for
	for(i=0;i<vna;i++)VNA[1][i]='w';
	VNA[0][vna]=VNA[1][vna]='\0';
	/////////////////////////////////////////
	s=0;
	for(i=0;i<=wfnum;i++){
		if(tv[i][3]=='\0'){s=1;
		break;}
	}//for
	if(s==0){
		for(i=0;i<vna;i++)VNA[1][i]='N';
		return(1);
	}//if
	//////////////////////////////////////////
	wfgs=wfnum;
	for(i=0;i<=wfgs;i++){//若含有VT则删除之
		j=3;
		while(tv[i][j]!='\0'&&tv[i][0]!='\0'){
			if(!isupper(tv[i][j])){
				del_VN=tv[i][0];
				strcpy(tv[i],tv[wfgs]);
				tv[wfgs][0]='\0';
				wfgs--;i--;
				if(wfgs==-1)return(1);
				s=0;j=0;
				while(j<=wfgs){
					if(tv[j][0]==del_VN){
						s=1;
						break;
					}//if
					j++;
				}//while
				if(s==0){
					t=0;
					while(VNA[0][t++]!=del_VN);
					VNA[1][t-1]='N';
				}//if
				break;
			}//if
			j++;
		}//while
	}//for
	////////////////////////////////////////////
	for(i=0;i<=wfgs;i++){//若能推出空则将所有以此VN开头的产生式删除
		if(tv[i][3]=='\0'&&tv[i][0]!='\0'){
			t=0;
			while(VNA[0][t]!=tv[i][0])t++;
			VNA[1][t]='Y';
			for(j=0;j<=wfgs;j++)
				if(tv[j][0]==VNA[0][t])
					tv[j][0]='\0';
		}//if
	}//for
	//////////////////////////////////////////
	do{
		for(i=0;i<=wfgs;i++){
			if(strlen(tv[i])==0)continue;
			j=3;
			while(tv[i][j]!='\0'){
				t=0;
				while(VNA[0][t]!=tv[i][j])t++;
				if(VNA[1][t]=='Y'){
					t=j;
					while(tv[i][t]!='\0'){
						tv[i][t]=tv[i][t+1];
						t++;
					}//while
					if(tv[i][3]=='\0'){//若这使得产生式右部为空
						if(tv[i][0]=='^')continue;
						t=0;
						while(VNA[0][t++]!=tv[i][0]);
						VNA[1][t-1]='Y';
						for(d=0;d<=wfgs;d++)
							if(tv[d][0]==VNA[0][t-1])
								tv[d][0]='\0';
						break;
					}//if
					continue;
				}//if
				if(VNA[1][t]=='N'){
					del_VN=tv[i][0];
					tv[i][0]='\0';
					s=0;
					for(d=0;d<=wfgs;d++){
						if(tv[d][0]==del_VN){
							s=1;
							break;
						}//if
					}//for
					if(s==0){
						d=0;
						while(VNA[0][d++]!=del_VN);
						VNA[1][d-1]='N';
					}//if
				}//if
				j++;
			}//while
		}//for
		if(strcmp(VNA[1],test_VNA)==0)break;
		else
			strcpy(test_VNA,VNA[1]);
		count++;
		if(count>=200)break;			
	}while(1);
	////处理递归///////////////////
	m=0;s=0;
	while(VNA[1][m]!='\0'){
		if(VNA[1][m]=='w'){s=1;break;}
		m++;
	}//while
	m=0;
	if(s==1){
		while(VNA[1][m]!='\0'){
		if(VNA[1][m]=='w')VNA[1][m]='N';
		m++;
		}//while
	}//if
	///////////////////////////////////

	return(1);
}//VN_test **

int yufa::VN_first(char n,char tx[50][50],char test[20]){//输入一个非终结符,产生它的first集，存放于FIRST[50][50]中
	int i,j,k,l,s,d,vl,tst=0;	
	char ctx[50][50],ctest[20];//tx,test的副件
	strcpy(ctest,test);
	////////复制拓广以后的文法到ctx///////
	for(i=0;i<=wfnum;i++)
		strcpy(ctx[i],tx[i]);
	ctx[i][0]='\0';
	//////////////////////////////////////
	i=0;
	while(VNA[0][i]!=n)i++;
	for(j=0;j<=wfnum;j++){
		if(tx[j][0]==VNA[0][i]){
			while(ctest[tst]!='\0')tst++;
			ctest[tst++]=tx[j][0];
			ctest[tst]='\0';
			k=3;
			while(tx[j][k]!='\0'){
				if(!isupper(tx[j][k])){
					d=0;s=0;
					while(d<f){
						if(FIRST[fst][d++]==tx[j][k]){
							s=1;
							break;
						}//if
					}//while
					if(s==0)FIRST[fst][f++]=tx[j][k];
					break;
				}//if
				else{
					l=0;vl=strlen(VNA[0]);
					while(VNA[0][l]!=tx[j][k]&&l<vl)l++;
					if(VNA[0][l]!=tx[j][k]){cout<<"\nerror!!"<<endl;return(0);}
					
					if(VNA[1][l]=='Y'){
						if(tx[j][k]==tx[j][0])break;//若存在直接递归
						tst=0;s=0;
						while(ctest[tst]!='\0'){
							if(ctest[tst]==tx[j][k]){s=1;break;}
							tst++;
						}//while
						if(s==1){k++;continue;}
						VN_first(tx[j][k],ctx,ctest);
						k++;
						continue;
					}//if
					else if(VNA[1][l]='N'){
						if(tx[j][k]==tx[j][0])break;
						tst=0;s=0;
						while(ctest[tst]!='\0'){
							if(ctest[tst]==tx[j][k]){s=1;break;}
							tst++;
						}//while
						if(s==1)break;
						VN_first(tx[j][k],ctx,ctest);
						break;
					}//else if
					else{
						cout<<"ERROR!"<<endl;
						exit(1);
					}//else if else
				}//if else
				k++;
			}//while
		}//if
	}//for
	return(1);
}//VN_first **

int yufa::FIRST_creat(char tm[50][50]){//产生文法tm的FIRST集
	int i=0,j;
	char ctm[50][50],temp[20];
	////////复制拓广以后的文法到cwf////////////////////
	for(i=0;i<=wfnum;i++)
		strcpy(ctm[i],tm[i]);
	cwf[i][0]='\0';
	/////////////////////////////////////////////////////////
	i=0;
	VN_test(ctm);
	while(VNA[0][i]!='\0'){
		f=0;
		////////复制拓广以后的文法到ctm////////////////////
		for(j=0;j<=wfnum;j++)
			strcpy(ctm[j],tm[j]);
		cwf[j][0]='\0';
		/////////////////////////////////////////////////////////
		if(VNA[1][i]=='Y'){
			FIRST[fst][f++]='@';
		}//if
		temp[0]='\0';
		if(!VN_first(VNA[0][i],ctm,temp)){
			cout<<"line 204 error!"<<endl;
			exit(1);
		}//if
		FIRST[i][f]='\0';
		i++;
		fst=i;
	}//while
	return(1);
}//FIRST_creat **


int yufa::input(){//负责文法的输入及处理
	int i,j,k,ck,ck1,ck2,t1,t2,t;
	char temp='^',chk1[30],chk2[30];
	t=j=k=ck=ck1=ck2=t1=t2=0;   i=1;

	cout<<"请输入文法(以 # 结束）："<<endl;
	while(temp!='#'){
		temp='^';
		while(temp!='\n'&&temp!='#'){
		cin>>wenfa[i][j];
			if(!check(wenfa[i][j])){
				cout<<"输入非法字符 %c ,请重新输入！"<<wenfa[i][j]<<endl;
				return(0);
			}//if
			if(j>=3&&!isupper(wenfa[i][j])&&wenfa[i][j]!='\0'&&wenfa[i][j]!='\n'){
				t=t1=0;
				while(t1<t2){
					if(wenfa[i][j]==VT[t1++]){t=1;
					break;}
				}//while
				if(t==0)VT[t2++]=wenfa[i][j];
			}//if
			if(j==0&&isupper(wenfa[i][j])){chk1[ck1]=wenfa[i][j];ck1++;}
			if(j>=3&&isupper(wenfa[i][j])){chk2[ck2]=wenfa[i][j];ck2++;}
			temp=wenfa[i][j];
			j++;
			if(temp==' ')j--;// 忽略空格
		}//while
		wenfa[i][j-1]='\0';
		i++;j=0;
		if(strlen(wenfa[i-1])==0)i--;
	}//while
	VT[t2]='\0';
	chk1[ck1]='\0';
	chk2[ck2]='\0';
	//////////////////以下为查错措施代码////////////////////////////////////////////
	for(t2=0;t2<ck2;t2++){
		for(t1=0;t1<ck1;t1++){
			ck=0;
			if(chk1[t1]==chk2[t2]){ck=1;break;}
		}//for
		if(ck==1)continue;
		else{
			cout<<"文法错误：非终结符%c出现在产生式的右部，但没有以它开头的产生式!"<<chk2[t2]<<endl;
			cout<<"请重新输入!"<<endl;
			return(0);
		}//if else
	}//for
	k=wfnum=i-1;
	i=1;j=0;
	for(i=1;i<=wfnum;i++){
		if(wenfa[i][0]<'A'||wenfa[i][0]>'Z') {
			cout<<"文法错误：文法最左部只能含有大写字母!"<<endl;
			cout<<"请重新输入!"<<endl;
			return(0);
		}//if
		if(wenfa[i][1]!='-'||wenfa[i][2]!='>'){
			cout<<"所输入的文法中有非法产生式!"<<endl;
			cout<<"请重新输入!"<<endl;
			return(0);
		}//if
	}//for
	//////////////////////////////////////////////////////////////////////////
	wenfa[0][0]='^';wenfa[0][1]='-';wenfa[0][2]='>';wenfa[0][3]=wenfa[1][0];wenfa[0][4]='\0';
	for(i=0;i<=wfnum;i++)
		strcpy(cwfbj[i],wenfa[i]);
	cout<<"拓广后文法为:"<<endl;
	for(i=0;i<=k;i++){
		while(wenfa[i][j]!='\0'){
            cout<<wenfa[i][j]<<endl;
			j++;
		}//while
		cout<<endl;
		j=0;
	}//for
	
	
	////////复制拓广以后的文法到wenfa_old////////////////////
	for(i=0;i<=wfnum;i++)
		strcpy(wenfa_old[i],wenfa[i]);
	/////////////////////////////////////////////////////////
	//对文法进行规范化 
	for(i=0;i<=wfnum;i++){   
		for(j=strlen(wenfa[i]);j>=3;j--)
			wenfa[i][j]=wenfa[i][j-1];
			wenfa[i][3]='.';
	}//for
	////////////////////////////////////////
	j=0;  //此段可以删除
	cout<<"规范化以后为："<<endl;
	for(i=0;i<=k;i++){
		while(wenfa[i][j]!='\0'){
            cout<<wenfa[i][j]<<endl;
			j++;
		}//while
		cout<<endl;
		j=0;
	}//for
	cout<<endl;
	//////////////////////////////////////
	return(1);
}//input**

int yufa::DFA_opt(char ll[50][50][50],int p){//输出DFA，其中p为项目集的个数
	int i=0,j=0,a=0;
	cout<<"项目族规范集为："<<endl;
	for(a=0;a<p;a++){
		cout<<"I[%d]:\t"<<a<<endl;
		while(strlen(ll[a][i])!=0){
			if(i>=3&&(i%3)==0)cout<<endl;
			while(ll[a][i][j]!='\0'){
				cout<<ll[a][i][j]<<endl;
				j++;
			}//while
			cout<<endl;
			i++;j=0;
		}//while
		i=0;
		cout<<endl;
	}//for
	return(1);
}//DFA_opt **
			
int yufa::xam(char inpt[50],char digui_test[50]){//输入一个产生式，生成一个项目集
	int i=3,m=0,sl,dl,t,j,s;
	char copy_digui_test[50];
	strcpy(copy_digui_test,digui_test);
	while(inpt[i++]!='.');
	if(inpt[i]<'A'||inpt[i]>'Z')return (1);
	/////////////////////////////////////////////	
	//if(inpt[0]==inpt[4]&&inpt[3]=='.')return(1);//处理直接左递归
	///////////////处理间接递归//////////////////
	j=0;s=0;
	while(copy_digui_test[j]!='\0'){
		if(copy_digui_test[j]==inpt[i]&&strlen(copy_digui_test)!=1){s=1;break;}
		j++;
	}//while
	if(s==1)return(1);
	///////改写测试字符串//////
	j=0;
	while(copy_digui_test[j]!='\0')j++;	
	copy_digui_test[j++]=inpt[i];
	copy_digui_test[j]='\0';
	/////////////////////////////////
	if(inpt[i]>='A'&&inpt[i]<='Z'){
		for(m=0;m<=wfnum;m++){
			if(wenfa[m][0]==inpt[i]){
				strcpy(DFA[x][y],wenfa[m]);
				sl=strlen(wenfa[m]);
				DFA[x][y][sl++]=',';					
				if(inpt[i]==inpt[0]){
					dl=0;
					while(inpt[dl++]!=',');
					while(inpt[dl]!='\0'){
						DFA[x][y][sl++]=inpt[dl++];
					}//while
					DFA[x][y][sl]='\0';
				}// if
				else if(inpt[i+1]==','){
					DFA[x][y][sl++]='#';