程序1.cpp

编译原理 语义分析 c++ vc6.0 可用作本科课程设计、毕业设计等

				{   // 如果是闭包
					//p->next[k]=p;
					//p->throught[k]=tmp->throught[j];
				}
				else
				{   
					nfa->nodetable[i]->next[j]=p;
				}
				k++;
			}
		}
	}
	for(i=0;nfa->nodetable[i]!=tmp;i++);
	while(nfa->nodetable[i+1]!=NULL){
		nfa->nodetable[i]=nfa->nodetable[i+1];
		i++;
	}nfa->nodetable[i]=NULL;
	nfa->nodenumber--;
	//print(nfa);
}
////////////////////////////////////////////////////////////////////////////
// 主转化函数2----------------将非确定有穷自动机NFA转化成确定有穷自动机DFA
nfapoin *TurnDFAiniteAutomata(nfapoin *&nfa)
{
	int flag=1,i=0,j=0,k=0,m=0,n=0,pp=0,qq=0,x=0,y=0;
	while(flag)
	{
		for(int i=0;i<nfa->nodenumber;i++)
		{   // 操作每一个结点
			flag=0;
			for(j=0;nfa->nodetable[i]->next[j]!=NULL;j++)
			{   // 扫描结点的每一个子
                if( nfa->nodetable[i]==nfa->nodetable[i]->next[j] && nfa->nodetable[i]->throught[j]==' ' ){
					deletn(nfa->nodetable[i]);
					//print(nfa);
					break;
				}
				if(nfa->nodetable[i]->throught[j]==' ')
				{					
					//cout<<"------------------------------------------------d--p "<<nfa->nodetable[i]->number<<endl;
					//cout<<"------------------------------------------------d--p->next "<<nfa->nodetable[i]->next[j]->number<<endl;
					deletd(nfa->nodetable[i]);
					deletd(nfa->nodetable[i]->next[j]);
					//cout<<"--------------------------------------------------------d--p "<<nfa->nodetable[i]->number<<endl;
					//cout<<"--------------------------------------------------------d--p->next "<<nfa->nodetable[i]->next[j]->number<<endl;
					merge(nfa->nodetable[i],nfa->nodetable[i]->next[j],nfa);
				    flag=1;
					//print(nfa);
					break;
				}
			}
			if(flag==1){break;}
		}
	}//print(nfa);
	for(i=0;i<nfa->nodenumber;i++)
	{   // 扫描每一个结点  对结点重新编号
	    deletd(nfa->nodetable[i]);
		deletn(nfa->nodetable[i]);
		nfa->nodetable[i]->number=i+1;
	}//print(nfa);
    ////////////////////////////////////////////////////////////////////////
    // 确定化
	node *p=NULL,*q=NULL,*r=NULL;i=0;j=0;k=0;flag=1;
	while(flag)
	{
		flag=0;
		for(i=0;i<nfa->nodenumber;i++)
		{   // 扫描每一个结点
			//cout<<"=====1============ i="<<i<<"  j="<<j<<"  k="<<k<<endl;
			for(j=0;nfa->nodetable[i]->next[j]!=NULL;j++)
			{   // 操作每一个子
				//cout<<"=====2============= i="<<i<<"  j="<<j<<"  k="<<k<<endl;
				for(k=j+1;nfa->nodetable[i]->next[k]!=NULL;k++)
				{   // 与其它子比较
					//cout<<"=====3============= i="<<i<<"  j="<<j<<"  k="<<k<<endl;
					if(nfa->nodetable[i]->throught[k]==nfa->nodetable[i]->throught[j])
					{   // 找到两条不确定的边 j k
						//cout<<"=====4============= i="<<i<<"  j="<<j<<"  k="<<k<<endl;
						p=nfa->nodetable[i]->next[j];
						q=nfa->nodetable[i]->next[k];
						if( p!=nfa->nodetable[i] && q!=nfa->nodetable[i] && p!=q )
						{   // p q nfa->nodetable[i] 互不相同
							//cout<<"=====5============= i="<<i<<"  j="<<j<<"  k="<<k<<endl;
							// 1:增加结点r
							r=new node;
							initnode(r);
							r->number=nfa->nodenumber+1;
							if(p->state=='e'||q->state=='e'){r->state='e';}
							nfa->nodetable[nfa->nodenumber]=r;
							nfa->nodenumber++;
							//print(nfa);

							// 2:-a->r
							for(m=0;nfa->nodetable[i]->next[m]!=NULL;m++);
							nfa->nodetable[i]->next[m]=r;
							nfa->nodetable[i]->throught[m]=nfa->nodetable[i]->throught[j];
							//print(nfa);

							// 3: p q 的所有子给 r
							for(m=0;r->next[m]!=NULL;m++);
							for(n=0;p->next[n]!=NULL;n++,m++)
							{
								r->next[m]=p->next[n];
								r->throught[m]=p->throught[n];
							}
							for(n=0;q->next[n]!=NULL;n++,m++)
							{
								r->next[m]=q->next[n];
								r->throught[m]=q->throught[n];
							}
							//print(nfa);

							// 4:删除 k j 边
							if(k<j){x=k;y=j;}else{x=j;y=k;}
							for(m=y;nfa->nodetable[i]->next[m]!=NULL;m++)
							{
								nfa->nodetable[i]->next[m]=nfa->nodetable[i]->next[m+1];
								nfa->nodetable[i]->throught[m]=nfa->nodetable[i]->throught[m+1];
							}nfa->nodetable[i]->next[m]=NULL;
							nfa->nodetable[i]->throught[m]='\0';
							for(m=x;nfa->nodetable[i]->next[m]!=NULL;m++)
							{
								nfa->nodetable[i]->next[m]=nfa->nodetable[i]->next[m+1];
								nfa->nodetable[i]->throught[m]=nfa->nodetable[i]->throught[m+1];
							}nfa->nodetable[i]->next[m]=NULL;
							nfa->nodetable[i]->throught[m]='\0';
							//print(nfa);

							// 5:删除 p q 结点
							pp=0;qq=0;
							for(m=0;p->next[m]!=NULL;m++)
							{   // 标记
								if(p->next[m]==q){pp=1;break;}
							}
							for(m=0;q->next[m]!=NULL;m++)
							{   // 标记
								if(q->next[m]==p){qq=1;break;}
							}
							if(pp==0&&qq==0)
							{   // 删除 p 和 q
								//cout<<"----------------------------------p-q"<<endl;
								if(p->number<q->number){x=p->number;y=q->number;}else{x=q->number;y=p->number;}
								for(m=y-1;nfa->nodetable[m]!=NULL;m++)
								{
									nfa->nodetable[m]=nfa->nodetable[m+1];
								}nfa->nodetable[m]=NULL;
								nfa->nodenumber--;
								for(m=x-1;nfa->nodetable[m]!=NULL;m++)
								{
									nfa->nodetable[m]=nfa->nodetable[m+1];
								}nfa->nodetable[m]=NULL;
								nfa->nodenumber--;
							}
							if(pp==1&&qq==0)
							{   // 只删除 p
								//cout<<"------------------------------------p"<<endl;
								for(m=p->number-1;nfa->nodetable[m]!=NULL;m++)
								{
									nfa->nodetable[m]=nfa->nodetable[m+1];
								}nfa->nodetable[m]=NULL;
								nfa->nodenumber--;							
							}
							if(pp=0&&qq==1)
							{   // 只删除 q
								//cout<<"------------------------------------q"<<endl;
								for(m=q->number-1;nfa->nodetable[m]!=NULL;m++)
								{
									nfa->nodetable[m]=nfa->nodetable[m+1];
								}nfa->nodetable[m]=NULL;
								nfa->nodenumber--;							
							}
							pp=0;qq=0;
							//print(nfa);

							for(m=0;m<nfa->nodenumber;m++)
							{   // 扫描每一个结点  对结点重新编号
								deletd(nfa->nodetable[m]);
								deletn(nfa->nodetable[m]);
								nfa->nodetable[m]->number=m+1;
							}//print(nfa);

							flag=1;
							i=0;j=0;k=1;
							break;
						}//if
						//if( (p==nfa->nodetable[i]||q==nfa->nodetable[i]) && p!=q )
						//{   // p q nfa->nodetable[i] 互不相同
							//cout<<"=====6============= i="<<i<<"  j="<<j<<"  k="<<k<<endl;
							//flag=1;
							//i=0;j=0;k=1;
							//break;
						//}//if
					}//if
				}//for k
				if(flag==1){break;}
			}// for j
			if(flag==1){break;}
		}// for i
	}//print(nfa);
	////////////////////////////////////////////////////////////////////////////////////////
	for(i=0;i<nfa->nodenumber;i++)
	{   // 扫描每一个结点  对结点重新编号
	    deletd(nfa->nodetable[i]);
		deletn(nfa->nodetable[i]);
		nfa->nodetable[i]->number=i+1;
	}//print(nfa);
	node *t=NULL;int dd=0,ff=0;
	if(nfa->nodetable[0]->state!='s'||nfa->nodetable[0]->state!='d'){   // 把s或d结点放在最前面
		for(i=1;nfa->nodetable[i]!=NULL;i++){
			if(nfa->nodetable[i]->state=='s'||nfa->nodetable[i]->state=='d'){
				ff=i;
				t=nfa->nodetable[i];
				nfa->nodetable[i]=nfa->nodetable[0];
				nfa->nodetable[0]=t;
				dd=nfa->nodetable[i]->number;
				nfa->nodetable[i]->number=nfa->nodetable[0]->number;
				nfa->nodetable[0]->number=dd;
				break;
			}
		}
	}//print(nfa);
	for(i=1;nfa->nodetable[i]!=NULL;i++);
	k=i-1;
	if(nfa->nodetable[k]->state!='e'){   // 把e结点放在最后面
		for(i=k-1;i>0;i--){
			if(nfa->nodetable[i]->state=='e'){
				if(ff==i){nfa->nodetable[ff]->state='d';break;}
				t=nfa->nodetable[i];
				nfa->nodetable[i]=nfa->nodetable[k];
				nfa->nodetable[k]=t;
				dd=nfa->nodetable[i]->number;
				nfa->nodetable[i]->number=nfa->nodetable[k]->number;
				nfa->nodetable[k]->number=dd;
				break;
			}
		}
	}//print(nfa);cout<<"------------------------------------------------------"<<endl;//cin>>i;
	return nfa;
}
////////////////////////////////////////////////////////////////////////////
nfapoin *mer(nfapoin *p[])
{   // 合并n个DFA	
	for(int i=1;p[i]!=NULL;i++)
	{   // 扫描p[1]~p[n]
		if(p[i]->nodetable[0]->state=='e'||p[i]->nodetable[0]->state=='d'){
			p[0]->nodetable[0]->state='d';
		}
		for(int j=0;p[0]->nodetable[0]->next[j]!=NULL;j++);
		for(int k=0;p[i]->nodetable[0]->next[k]!=NULL;k++,j++)// 把p[1]~p[n]结点给p[0]作子
		{   // 扫描p[i]的所有子
			if(p[i]->nodetable[0]->next[k]!=p[i]->nodetable[0]){
				p[0]->nodetable[0]->next[j]=p[i]->nodetable[0]->next[k];
				p[0]->nodetable[0]->throught[j]=p[i]->nodetable[0]->throught[k];
			}
			else{// 如果是闭包
				p[0]->nodetable[0]->next[j]=p[0]->nodetable[0];
				p[0]->nodetable[0]->throught[j]=p[i]->nodetable[0]->throught[k];
			}
		}
	}//print(p[0]);cout<<"------------------------------------1"<<endl;
	for(i=1;p[i]!=NULL;i++)
	{   // 扫描p[1]~p[n]
		for(int j=1;j<p[i]->nodenumber;j++)
		{   // 把p[1]~p[n]的所有子结点给p[0]
			// cout<<"-----"<<p[i]->nodenumber<<endl;
			p[0]->nodetable[p[0]->nodenumber]=p[i]->nodetable[j];
			p[0]->nodenumber++;		
		}
	}//print(p[0]);cout<<"------------------------------------2"<<endl;
	for(i=1;p[i]!=NULL;i++)
	{   // 扫描p[1]~p[n]
		for(int j=1;p[i]->nodetable[j]!=NULL;j++)
		{   // 把p[1]~p[n]->nodetable[0]的所有父给p[0]->nodetable[0]  除闭包外
			for(int k=0;p[i]->nodetable[j]->next[k]!=NULL;k++)
			{   // 扫描p[i]->nodetable[j]的所有子
				if(p[i]->nodetable[j]->next[k]==p[i]->nodetable[0])
				{
					p[i]->nodetable[j]->next[k]=p[0]->nodetable[0];
					p[i]->nodetable[j]->throught[k]=p[i]->nodetable[j]->throught[k];
				}	
			}		
		}
	}//print(p[0]);cout<<"------------------------------------3"<<endl;
	for(i=0;i<p[0]->nodenumber;i++)
	{   // 扫描每一个结点  对结点重新编号
	    deletd(p[0]->nodetable[i]);
		deletn(p[0]->nodetable[i]);
		p[0]->nodetable[i]->number=i+1;
	}//print(p[0]);cout<<"------------------------------------4"<<endl;
	return p[0];
}
////////////////////////////////////////////////////////////////////////////
// 主转化函数3---------------------------将确定有穷自动机DFA最小化为MINDFA
nfapoin *TurnMINDFAiniteAutomata()
{
	int i=0,j=0,flag=0;
	char RegularExpression[MAXCHILDREN][MAXCHILDREN];
	for(i=0;i<MAXCHILDREN;i++){
		for(int j=0;j<MAXCHILDREN;j++)
			RegularExpression[i][j]='\0';
	}

	FILE *fp=fopen("RegularExpression.txt","r");
	if ( !fp )  
	{   // 若打不开原文件，提示错误
		printf("打开文件RegularExpression.txt失败！\n");
		return 0;
	}
	char ch;i=0;j=0;
	while((ch=fgetc(fp))!=EOF)
	{   // 读文件 
		//printf("%c",ch);
		if(ch!=13&&ch!=10){RegularExpression[i][j]=ch;}
		j++;
		if(ch==10){i++;j=0;}		
	}//cout<<endl;
	fclose(fp);
//	for(i=0;i<MAXCHILDREN;i++){
//		for(int j=0;j<MAXCHILDREN;j++)
//			if(RegularExpression[i][j]!='\0'){
//				cout<<RegularExpression[i][j];
//			}
//	}
	for(i=0;i<MAXREG;i++){// 检查文件里是否有有效的正则表达式
		if(RegularExpression[i][0]!='\0'){flag=1;}}
	if(flag==0)
	{   // 提示错误
		printf("erorr!(文件里无有效的正则表达式)\n");
		return 0;
	}
	nfapoin *nfa=NULL;
	nfapoin *dfa=NULL;
	nfapoin *tmp[MAXREG];
	for(i=0;i<MAXREG;i++){
		tmp[i]=NULL;
	}int d=0;
	for(j=0;RegularExpression[j][0]!='\0';j++);
    for(i=0;i<j;i++){
		nfa=TurnNFAiniteAutomata(&RegularExpression[i][0]);
		//cout<<"-------------------------------NFA-"<<i<<endl;
		//print(nfa);
		tmp[i]=dfa=TurnDFAiniteAutomata(nfa);
		//cout<<"-------------------------------DFA-"<<i<<endl;
		//print(dfa);
	}
	dfa=mer(tmp);
	//print(dfa);
	//dfa=TurnDFAiniteAutomata(dfa);
    ////////////////////////////////////////////////////////////////////////
	return  dfa;
}
////////////////////////////////////////////////////////////////////////////
char cases(int a)
{
	switch (a)
	{
		case 1: return '1';
		case 2: return '2';
		case 3: return '3';
		case 4: return '4';
		case 5: return '5';
		case 6: return '6';
		case 7: return '7';
		case 8: return '8';
		case 9: return '9';
		case 0: return '0';
	}
	return 'e';
}
////////////////////////////////////////////////////////////////////////////
char *inttochars(int inter,char *ch)
{
	int i,j,k;
    for(i=0;inter>0;i++){
	    *(ch+i)=cases(inter%10);
		inter=inter/10;
	}for(k=i;k<10;k++){*(ch+k)='\0';}
	i--;
	for(j=0;j<i;j++,i--){
	    k=*(ch+j);
		*(ch+j)=*(ch+i);
		*(ch+i)=k;
	}
	return ch;
}
////////////////////////////////////////////////////////////////////////////
void printfile(nfapoin *nfa)
{   // 把有穷自动机写到文件里
	//cout<<"----------------------------------------------------------------------"<<endl;
	char ch[10];
	FILE *fp=fopen("Automata.txt","w+");
	fputs(inttochars(nfa->nodenumber,ch),fp);// 写入结点数
	fputc(13,fp);fputc(10,fp);// 回车换行
	//cout<<inttochars(nfa->nodenumber,ch)<<endl;//

	for(int i=0;nfa->nodetable[i]!=NULL;i++)
	{   // 依次写入每个结点以及它的每条边
		if(nfa->nodetable[i]->state!='\0')
		{   // 如果是普通结点则
			fputs(inttochars(nfa->nodetable[i]->number,ch),fp);
			fputc(nfa->nodetable[i]->state,fp);
			fputc(' ',fp);fputc(' ',fp);
			//cout<<inttochars(nfa->nodetable[i]->number,ch)<<nfa->nodetable[i]->state<<"  ";//
		}else{
			fputs(inttochars(nfa->nodetable[i]->number,ch),fp);fputc(' ',fp);fputc(' ',fp);fputc(' ',fp);
			//cout<<inttochars(nfa->nodetable[i]->number,ch)<<"   ";//
		}
		for(int k=0;nfa->nodetable[i]->next[k]!=NULL;k++)
		{
			fputc(' ',fp);fputc('-',fp);
			fputc(nfa->nodetable[i]->throught[k],fp);
			fputc('-',fp);fputc('>',fp);
			fputs(inttochars(nfa->nodetable[i]->next[k]->number,ch),fp);
			fputc(' ',fp);fputc(' ',fp);fputc(' ',fp);fputc(' ',fp);
			//cout<<" -"<<nfa->nodetable[i]->throught[k]<<"->"<<inttochars(nfa->nodetable[i]->next[k]->number,ch)<<"    ";//
		}
		fputc(13,fp);fputc(10,fp);// 回车换行
		//cout<<endl;
	}
	//fputc(13,fp);fputc(10,fp);// 回车换行
	//cout<<endl;
	fclose(fp);
}
////////////////////////////////////////////////////////////////////////////
int main(void)
{
	nfapoin *mindfa=TurnMINDFAiniteAutomata();
	mindfa=TurnDFAiniteAutomata(mindfa); // 再次确定化

	print(mindfa);
	printfile(mindfa);
	cout<<"---------------------"<<endl;
	cout<<"ok! 有穷自动机已生成!"<<endl;
	delete mindfa; 
	system("pause");
	return 1;
}