gra.h

编译原理大新实验代码dfanfa转化实验要求等

#include "rule.h"
struct Rules
{
    Rule* rulez;
	Rules* nextrule;
	Rules()
	{rulez=new(Rule);
	nextrule=NULL;}
};
typedef struct {
char g[26];
int num;
}	GY;

class Gra:public Rule
{
private:
	Rules* rules;
	Rules* head;
	Rules* temp;
	int num;
	int num1;
	GY a[26][26];
	char t1[26];//前输入字母表组
	char t2[26];//前状态数组
	int t3[26],t4[26];
public:
	Gra();
	void input();
	void output();
	void outputs();
	void count();
	void signit(char idenc);//加标记
	void compress();//压缩
	void tofa();//转换为FA
	void del(){delete head;head=new(Rules);}
	void ConverToDfa();//NFA转换为DFA
};
Gra::Gra()
{
	rules=new(Rules);head=rules;temp=head;
	num=num1=0;
}
void Gra::input()
{
lab1:	cout<<"请输入标识符:";
	cin>>iden;
	while (cin.get()!='\n')
		continue;
	if (isalpha(iden)!=1)
	{cout<<"输入非大写字母,请重新输入!\n";
	goto lab1;}
cout<<"请输入规则的个数:";
	cin>>num;
	num1=num;
	rules->rulez->inputr();num--;
	while (num--!=0)
	{
		rules->nextrule=new(Rules);
		rules=rules->nextrule;
		rules->rulez->inputr();
		
	}
}
void Gra::output()
{
	
	cout<<"G["<<iden<<"]:"<<endl;
	temp=head;
	while (temp!=NULL)
	{
		if (temp->rulez->spilth==0)
		{temp->rulez->outputr();}
		temp=temp->nextrule;
	}
	temp=head;
	
	
}
void Gra::outputs()
{
	cout<<"G["<<iden<<"]:"<<endl;
	temp=head;
	while (temp!=NULL)
	{
		if (temp->rulez->spilth==1)
		{temp->rulez->outputr();}
		temp=temp->nextrule;
	}
	temp=head;
}
void Gra::signit(char idenc)
{
	for (int i=0;i<26;i++)
		{table[i]=0;table2[i]=0;}
	islid=1;
	while (islid==1)
	{temp=head;
	islid=0;
	while (temp!=NULL)
	{
		if (temp->rulez->spilth==0)
		{
			temp->rulez->sign(idenc);}
		temp=temp->nextrule;
	}}//对条件一的判断

	temp=head;
    while (temp!=NULL)
	{
		if (temp->rulez->spilth==0)
		{temp->rulez->isspilth();}
		temp=temp->nextrule;
	}//判断之后对规则加标记
	temp=head; 
	while (temp!=NULL)
	 {
		 if (temp->rulez->spilth==0)
		 {temp->rulez->sign21();}
		 temp=temp->nextrule;
	 }//对U::=u之左部非终结符号U加标记
	islid=1;
	while(islid==1)
	{
		temp=head;
		islid=0;
		while (temp!=NULL)
		{	
		    if (temp->rulez->spilth==0&&temp->rulez->lid2==0)
			{temp->rulez->sign22();}
			temp=temp->nextrule;
		}

	}//对右部仅包含终结符号与以加标记的非终结符号的规则之左部加标记
	temp=head;    
	while (temp!=NULL)
	{
		
		if (temp->rulez->spilth==0)
		{temp->rulez->isspilth2();}
		temp=temp->nextrule;
	}
	temp=head;
	while (temp!=NULL)
	{
		if (temp->rulez->spilth==0)
		{temp->rulez->dgz();}
		temp=temp->nextrule;
	}
	temp=head;    
	while (temp!=NULL)
	{
		if (temp->rulez->spilth==0)
		{temp->rulez->isspilth3();}
		temp=temp->nextrule;
	}
}
void Gra::compress()
{
	int k=0;
	do
	{
		k+=1;
		del1=0;
		temp=head;
		while (temp!=NULL)
		{
			if (temp->rulez->spilth==0)
			{
				temp->rulez->lid=0;
				temp->rulez->lid2=0;
				temp->rulez->lid3=1;
			}
				temp=temp->nextrule;
		}
		signit(iden);
		if (del1!=0)
			{cout<<"===压缩第"<<k<<"趟后的文法:===\n";
			output();cout<<"================\n";}
	}while (del1!=0);
}
void Gra::tofa()
{
	
	int n=0;
	int k=1;
	int cn=0;
	bool rg=false;
	int flag=1;//flag=1则表示为DFA,否则为NFA;
	temp=head;
	for (int i=0;i<26;i++)
		for (int j=0;j<26;j++)
			for (int q=0;q<26;q++)
			{a[i][j].g[q]='\0';a[i][j].num=0;}
	while (temp!=NULL)
	{
		if (temp->rulez->spilth==0)
		{
			rg=temp->rulez->isrg();
		}
		temp=temp->nextrule;
		if (rg==false)
			break;
	}
	if (rg==false)
	{cout<<"文法中有非正则文法,请重新输入!\n";return;}
	else
	{
		temp=head;
		t2[0]='S';
		while (temp!=NULL)
	{
		if (temp->rulez->spilth==0)
		{
		Rright* temprr=temp->rulez->head;
		Rright*	temph=temp->rulez->head;
		while (temprr!=NULL)
		{
			if ((temph->letter<'A'||temph->letter>'Z')&&temph->nextletter==NULL)//U::=u的情况
			{
				
				a['S'-65][temph->letter-97].g[temp->rulez->left-65]=temp->rulez->left;
				                     
				if (t3[temph->letter-97]!=1)//统计输入字母表
				{
					t1[n++]=temph->letter;
					t3[temph->letter-97]=1;//判断此字符是否已经存在
				}
			}
			else if (temprr->letter>='A'&&temprr->letter<='Z')
			{
			a[temprr->letter-65][temprr->nextletter->letter-97].g[temp->rulez->left-65]=temp->rulez->left;
			if (t4[temprr->letter-65]!=1)//统计状态
			{
				t2[k++]=temprr->letter;
				t4[temprr->letter-65]=1;
			}

			}
			if (temprr->letter>='a'&&temprr->letter<='z'&&temprr->nextletter==NULL)
			{
				if (t3[temprr->letter-97]!=1)//统计输入字母表
				{
					t1[n++]=temprr->letter;
					t3[temprr->letter-97]=1;
				}
			}
			temprr=temprr->nextletter;
		}
		
		}temp=temp->nextrule;
	}
	}
	t1[n]='\0';
	t2[k]='\0';
	int k1=k,n1=n;
	/*cout<<t1<<strlen(t1)<<endl;
	cout<<t2<<endl;*/
	for (i=0;i<26;i++)
		for (int j=0;j<26;j++)
		{
			for (int z=0;z<26;z++)
			{
				if (a[i][j].g[z]!='\0')
					a[i][j].num+=1;
			}
			if (a[i][j].num>1)
				flag=0;
		}
	if (flag==0)
	{
		cout<<"该规则对应的自动机为NFA:\n"
			<<"NFA N=({";
		while (k1!=0)
		{
			cout<<t2[k-k1];
			k1--;
			if (k1!=0)
				cout<<",";
		}//输出状态
		cout<<"},{";
		while (n1!=0)
		{
			cout<<t1[n-n1];
			n1--;
			if (n1!=0)
				cout<<",";
		}
		cout<<"},M,{S},{Z})\n";
		cout<<"其中M为:\n";
	}
	else
	{
		cout<<"该规则对应的自动机为DFA:\n"
			<<"DFA D=({";
		while (k1!=0)
		{
			cout<<t2[k-k1];
			k1--;
			if (k1!=0)
				cout<<",";
		}
		cout<<"},{";
		while (n1!=0)
		{
			cout<<t1[n-n1];
			n1--;
			if (n1!=0)
				cout<<",";
		}
		cout<<"},M,S,{Z})\n";
		cout<<"其中M为:\n";
	}
	for (i=0;i<strlen(t2);i++)
	{
		for (int j=0;j<strlen(t1);j++)
		{
			if (a[t2[i]-65][t1[j]-97].num>0)
			{
				cout<<"M("<<t2[i]<<","<<t1[j]<<")={";
				for (int z=0;z<26;z++)
					if (a[t2[i]-65][t1[j]-97].g[z]!='\0')
					{
						if (cn!=0)
							cout<<",";
						cout<<a[t2[i]-65][t1[j]-97].g[z];
						cn++;
					}
				cn=0;
				cout<<"}	";
			}
		}
		cout<<endl;
	}
	if (flag==0)//是否允许转换
	{
			char a;
			cout<<"此文法为NFA，请问是否转换为DFA？（y/n）";
			cin>>a;
			if (a!='y'&&a!='Y')
				return;
			ConverToDfa();
	}
}
void Gra::ConverToDfa()
{
	char* NewState[255];//存放转换后的状态
//	char* matrx[255][255];//存放转换后的矩阵
	char temp[255][255];//保存临时所转换出来的状态,和新状态所能达到的状态
	int isadd[255]={0};//用于查看该状态是否已经加入到NewState中.
	int statecount=0;//状态数字和用来标记
	int n=0;//temp计数
	int k=1;//NewState计数
	int q=0;
	NewState[0]="S\0";
	
	for (int v=0;v<sizeof(NewState);v++)
		for (int w=0;w<strlen(NewState[v]);w++)
			for (int j=0;j<strlen(t1);j++)
			{
				for (int z=0;z<26;z++)
				{
					if (a[NewState[v][w]-65][t1[j]-97].g[z]!='\0')//查询所有开始状态所能规约到的状态。
							{						 //并将所有的状态加入到temp数组中。
								temp[q][n++]=a[NewState[v][w]-65][t1[j]-97].g[z];
								statecount=statecount+a[NewState[v][w]-65][t1[j]-97].g[z]-65;
							}
					
				}
			temp[q][n]='\0';
			n=0;q++;
					if (isadd[statecount]!=1)//该状态尚未被加入到NewState数组中.
					{ 
						NewState[k++]=(char*)temp[q];
						isadd[statecount]=1;//标记该状态已加入到NewState数组中.
					}
			
			//matrx[v][t1[j]]=strcpy(matrx[v][t1[j]],temp[q]);
			}
		

	/*for (int r=0;r<k;r++)
		for (int j=0;j<strlen(t1);j++)
			cout<<matrx[r][t1[j]-97]<<"		";
		cout<<endl;*/

}