fengsuyun.cpp

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

					DFA[x][y][sl]='\0';
				}//
				else if(!isupper(inpt[i+1])){
					DFA[x][y][sl++]=inpt[i+1];
					DFA[x][y][sl]='\0';
				}//else if
				else{
					t=dl=0;
					while(VNA[0][dl]!=inpt[i+1])dl++;
					while(FIRST[dl][t]!='\0'){
						DFA[x][y][sl++]=FIRST[dl][t++];
					}//while
					DFA[x][y][sl]='\0';
				}//else
				xam(DFA[x][y++],copy_digui_test);
			}//if
		}//for
	}//if
	return(1);
}//xam **

int yufa::DFA_Creat(char crt[10][50],int cishu){
	int i,j,n,reg,s,c,m,tx=0,tp=0,cs=0,point,it,rd=0;
	char temp[50],t[50][50],input[10][50];
	char xam_inpt[50];
	for(i=0;i<cishu;i++){
		strcpy(DFA[x][y++],crt[i]);
		xam_inpt[0]=crt[i][0];
		xam_inpt[1]='\0';
		xam(crt[i],xam_inpt); 
	}//for
	x++;
	if(x>=50){
		cout<<"数组越界，程序即将结束！"<<endl;
		exit(1);
	}//if
	n=y; y=0;  reg=x-1; 

	//将DFA[x-1]拷贝到t中
	for(i=0;i<50;i++)t[i][0]='\0';
	for(i=0;i<n;i++)
	strcpy(t[i],DFA[reg][i]);
	//////////////////////////////////////////////
	for(i=0;i<n;i++){//将项目集中的“.”后移一位
		j=3;
		while(t[i][j]!='.')j++;
		if(t[i][j+1]==','){//删除此产生式 
			rd=i;
			c=j+2;
			while(t[i][c]!='\0'){//写转换关系表
				relation[rl][0]=reg+'0';
				relation[rl][1]=t[i][c];
				t[i][j]='\0';
				m=0;
				while(strcmp(t[i],cwfbj[m])!=0)m++;
				relation[rl][2]=m+'0';
				relation[rl][3]='r';
				relation[rl][4]='\0';
				rl++;
				c++;
			}//while

			while(rd++<n-1)strcpy(t[rd-1],t[rd]);
			t[rd][0]='\0';
			i--;
			n--;
			//if(n==0){x--;}
			continue;
		}//if
		else{
			t[i][j]=t[i][j+1];
			t[i][j+1]='.';
		}//if else
		cs=0;tx=0;
		while(tx<tp){//查找是否有此字母
			if(t[i][j]==temp[tx]){cs=1;break;}
			tx++;
		}//while
		if(cs==0){temp[tp]=t[i][j];tp++;}
	}//for
	temp[tp]='\0';
	//////////////////////////////////////////////
	s=1;
	for(i=0;i<tp;i++){//产生tp个项目集
		s=strcmp(DFA[reg][0],t[i]);
		if(s==0){
			relation[rl][0]=relation[rl][2]=reg+'0';
			relation[rl][1]=temp[i];
			relation[rl][3]='s';
			relation[rl][4]='\0';
			rl++;
		}//if
		else{
			relation[rl][0]=reg+'0';
			relation[rl][1]=temp[i];
			relation[rl][2]=x+'0';
			relation[rl][3]='s';
			relation[rl][4]='\0';
			rl++;
		}//else
		it=0;
		for(j=0;j<n;j++){
			point=3;
			while(t[j][++point]!='.');
			if(t[j][point-1]==temp[i]&&(strcmp(t[j],DFA[reg][0])!=0)){
				strcpy(input[it++],t[j]);
			}//if
		}//for
		if(it==0)continue;
		DFA_Creat(input,it);
	}//for
		
	return(1);
}//DFA_Creat **

int yufa::fenxi(){
	int i=0,j=0,k=0,t,t1,t2,m=0;
	char temp[10];
	//////// 检查是否为LR1文法///////////////////////
	for(i=0;i<rl;i++){
		for(j=i+1;j<rl;j++){
			if(relation[i][0]==relation[j][0]&&relation[i][1]==relation[j][1]){
				cout<<"\n此文法不是LR1文法！按任意键退出？"<<endl;
				//getchar();
				exit(0);
			}//if
		}//for
	}//for

	////////////////////////////////////////////////
	i=j=0;
	temp[0] ='\0';
	while(i<rl){
			if(!isupper(relation[i][1])){
				j=0;
				while(relation[i][1]!=VT[j])j++;
				t=relation[i][0]-'0';
				m=relation[i][2]-'0';
				if(relation[i][3]=='s')
					temp[0]='s';
				else
					temp[0]='r';
				if(m>=10){
					t1=m/10;
					t2=m%10;
					temp[1]=t1+'0';
					temp[2]=t2+'0';
					temp[3]='#';
					temp[4]='\0';
				}//if
				else{
					temp[1]=relation[i][2];
					temp[2]='#';
					temp[3]='\0';
				}//else
				strcpy(akt[t][j],temp);
				action[t][j]=akt[t][j];
				//printf("\n%s\n",action[t][j]);
				if(m==0&&temp[0]=='r')
					action[t][j]="acc";
			}//if
			else{
				j=0;
				while(relation[i][1]!=VNA[0][j])j++;
				t=relation[i][0]-'0';
				m=relation[i][2]-'0';
				goto1[t][j]=m;
			}//else
			i++;
	}//while
	return(1);
}//fenxi

int yufa::fenxi_opt(){
	char t;
	int i,j,k,m,n;
	i=strlen(VT);
	j=strlen(VNA[0]);
	if(i+j>=8){
		cout<<"该文法中的非终结符和终结符的个数太多，如果输出可能引起界面混乱，是否继续输出分析表?"<<endl;
		cout<<"如果是请按'y'，否则请按'n'(y or n):"<<endl;
		do{cout<<"请输入一字符！"<<endl;
		   cin>>t;
			//t=getchar();
			if(t=='n'||t=='N'||t=='y'||t=='Y')break;
		}while(1);
		while(t!='\n');
		if(t=='n'||t=='N')return(0);
	}//if
	for(k=0;k<(i+j)/2;k++)
		cout<<endl;
	cout<<"LR1预测分析表"<<endl;
	for(k=0;k<i+j;k++)
	cout<<"_________";
	cout<<endl;
	for(k=0;k<=i/2;k++)
	cout<<endl;
	cout<<"ACTION";
	for(k=0;k<i/2;k++)
	cout<<endl;
	for(k=0;k<j/2;k++)
		cout<<endl;
	cout<<"GOTO"<<endl;
	for(k=0;k<i+j;k++)
	   cout<<"_________"<<endl;
	cout<< "状态"<<endl;
	for(k=0;k<i;k++)
		cout<<VT[k]<<endl;
	for(k=0;k<j;k++)
		cout<<VNA[0][k]<<endl;
	for(k=0;k<i+j;k++)
		cout<<"_________";
	
	for(m=0;m<x;m++){
	cout<<m<<endl;
		for(n=0;n<i+j;n++){
			if(n<i){
				if(strcmp(action[m][n],"NULL")==0)
					cout<<endl;
				else
					cout<<action[m][n]<<endl;
			}//if
			else{
				if(goto1[m][n-i]==0)
					cout<<"\t";
				else
					cout<<"\t"<<goto1[m][n-i];
			}//else
		}//for
	}//for
	cout<<endl;
	for(k=0;k<i+j;k++)
	cout<<"_________";
	cout<<endl;
	return(1);
}//fenxi_opt **

				
int yufa:: LR1(){
	int a[50];//定义状态栈
    char b[50],c[50],c1;//b[50]为符号栈，c[50]为字符串栈
    int top1,top2,top3,top,m,n;
	char *LR[50],reinput_test;
	for(m=0;m<=wfnum;m++)
		LR[m]=wenfa_old[m];
	LR[m]="\0";

	int g,h,i,j,k,l,p,y,z,count,w,t;
	char x,copy[50],copy1[50];
	top1=top2=top3=top=0;
	a[0]=0;y=a[0];b[0]='#';
	count=0;z=0;
	//while(getchar()!='\n');
	cout<<"请输入要测试的字符串:";
	do{
		cin>>c1;
		if(c1=='\n'||c1==' ')continue;
		c[top3++]=c1;
	}while(c1!='#');
	c[top3]='\0';
	cout<<"\n步骤\t状态栈\t\t符号栈\t\t输入串\t\tACTION\tGOTO"<<endl;
	do{
		y=z;m=0;n=0;                      /*y,z指向状态栈栈顶*/
		g=top;j=0;k=0;
		x=c[top];
		count++;
		cout<<endl;
		if(count>100){
			cout<<"程序出错, 是否重新输入测试字符串?\n如果是请按y,否则请按n(y or n)"<<endl;
			do{
				cin>>reinput_test;
				if(reinput_test=='y'||reinput_test=='n'||reinput_test=='Y'||reinput_test=='N')break;
				else continue;
			}while(1);
			if(reinput_test=='y'||reinput_test=='Y')return (0);
			else return(1);
		}//if
		while(m<=top1){                    /*输出状态栈*/
			cout<<a[m];
            m++;
		}//while

		if(top1>=7)
			cout<<"\t";
		else
			cout<<"\t\t";

		while(n<=top2){                    /*输出符号栈*/
			cout<<b[n];
            n++;
		}//while

		if(top2>=7)
			cout<<"\t";
		else
			cout<<"\t\t";

		t=top3-g;
		while(g<=top3){                    /*输出输入串*/
			cout<<c[g];
            g++;
		}//while
		if(t>=7)
			cout<<"\t";
		else
			cout<<"\t\t";
		w=strlen(VT);
		while(x!=VT[j]&&j<w) j++;
		if(x!=VT[j]){ 
			cout<<"error"<<endl;
		    cout<<"此字符串不是该文法的句子，是否继续测试其它字符串？\n如果是请按y,否则请按n(y or n):";
			do{
				cin>>reinput_test;
				if(reinput_test=='y'||reinput_test=='n'||reinput_test=='Y'||reinput_test=='N')break;
				else continue;
			}while(1);
			if(reinput_test=='y'||reinput_test=='Y')return (0);
			else return(1);
		}//if
        if(action[y][j]=="NULL"){
			cout<<"error"<<endl;
			cout<<"此字符串不是该文法的句子，是否继续测试其它字符串？\n如果是请按y,否则请按n(y or n):";
			do{
				cin>>reinput_test;
				if(reinput_test=='y'||reinput_test=='n'||reinput_test=='Y'||reinput_test=='N')break;
				else continue;
			}while(1);
			if(reinput_test=='y'||reinput_test=='Y')return (0);
			else return(1);
		
		}//if
		else
			strcpy(copy,action[y][j]);
		if(copy[0]=='s'){                      /*处理移进*/
			if(strlen(copy)>3){
				z=(copy[1]-'0')*10+copy[2]-'0';
			}//if
			else
			    z=copy[1]-'0';
            top1++;
			top2++;
			a[top1]=z;
			b[top2]=x;//x为当前的输入符号
			top++;
			i=0;
			while(copy[i]!='#'){//输出ACTION[y][j]
				cout<<copy[i];
				i++;
			}
			cout<<endl;
		}//if
		if(copy[0]=='r'){                      /*处理归约*/
			i=0;
			while(copy[i]!='#'){
				cout<<copy[i];
				i++;
			}
			if(strlen(copy)>3){
				h=(copy[1]-'0')*10+copy[2]-'0';
			}//if
			else{
			    h=copy[1]-'0';
			}//else
			strcpy(copy1,LR[h]);	//将文法中第h个产生式，复制到copy1中
			while(copy1[0]!=VNA[0][k]) k++;
			l=strlen(LR[h])-3;
			top1=top1-l;
			top2=top2-l;
			y=a[top1];
			p=goto1[y][k];
			a[top1+1]=p;//将goto1[y][k]赋予a[top1+1]
			b[top2+1]=copy1[0];
			z=p;
			top1++;
			top2++;
			cout<<"\t"<<endl;
			cout<<endl;
		}//if
	}while(action[y][j]!="acc");
	cout<<"acc\n分析成功!"<<endl;
	cout<<"是否继续测试其它字符串？\n如果是请按y,否则请按n(y or n):";
	do{
		cin>>reinput_test;
		if(reinput_test=='y'||reinput_test=='n'||reinput_test=='Y'||reinput_test=='N')break;
		else continue;
	}while(1);
	if(reinput_test=='y'||reinput_test=='Y')return (0);
	else return(1);
}//LR1 **



void main(){
	int i,t;
	char wfinpt[10][50],pause,a;
	yufa s;
	cout<<"			    LR1文法编辑器	"<<endl;
	cout<<"程序说明："<<endl;
	cout<<"1.本程序用于处理2型文法!"<<endl;
	cout<<"2.输入文法中可以含有除了“@ ”，“,”，“.”,“^”以外的任意字符。"<<endl;
	cout<<"3.若S能推出空，则用S->表示。"<<endl;
	cout<<"4.本程序用于生成输入文法的FIRST集，项目族规范集，预测分析表(LR1)。"<<endl;
	cout<<"5.对于输入的任何字符串能够分析出该字符串是否为该文法的句子，并显示分析步骤。"<<endl;
    cout<<"6.输入的文法或字符串以#结束。\n"<<endl;
	
	do{
		i=0;
	    s.initlize();
		if(!s.input()) {cin>>a;
			while(a!='\n') ;
			i=1;
		}
	}while(i);
	/////////////////////
	cout<<"按回车继续(press enter to continue)！"<<endl;
	cin>>pause;
	while(pause!='\n')cin>>pause;
	cin>>pause;	
	////////复制拓广以后的文法到wenfa_old////////////////////
	for(i=0;i<=wfnum;i++)
		strcpy(s.cwf[i],s.wenfa_old[i]);
	s.cwf[i][0]='\0';
	////////////输出非终结符及其状态/////////////////////////
	s.FIRST_creat(s.cwf);
	t=0;
	cout<<"FIRST集如下(@表示空串)："<<endl;
	while(s.FIRST[t][0]!='\0'){
		cout<<"FIRST[%C]:"<<s.VNA[0][t];
		cout<<s.FIRST[t++]<<endl;
	}//while
	t=0;
	cout<<"非终结符的状态为(Y表示能推出空串，N表示不能)："<<endl;
	cout<<"VN:\t";
	while(s.VNA[0][t]!='\0')
		cout<<s.VNA[0][t++]<<endl;
	t=0;
	cout<<"Action:\t";
	while(s.VNA[1][t]!='\0')
		cout<<s.VNA[1][t++];
        cout<<endl;
	//////////////////////////////////////////////////////
	cout<<"按回车继续(press enter to continue)！"<<endl;
	cin>>pause;
	//////////////////////////////////////////////////////
	strcpy(wfinpt[0],s.wenfa[0]);
	wfinpt[1][0]='\0';
	i=strlen(s.wenfa[0]);
	wfinpt[0][i++]=',';
	wfinpt[0][i++]='#';
	wfinpt[0][i]='\0';
	s.DFA_Creat(wfinpt,1);
	///////////////////////
	s.DFA_opt(s.DFA,x);
	cout<<"按回车继续(press enter to continue)!"<<endl;
	cin>>pause;
	/////////////////////////
	s.fenxi();
	s.fenxi_opt();
	///////////////////////////////
	while(!s.LR1());
	cout<<"\nsuccess"<<endl;
	
}