byyf2.cpp

实现DFA转化为NFA

// byyf.cpp : 定义控制台应用程序的入口点。
//


#include "stdafx.h"
#include <stdlib.h>  
#include <stdio.h>
#include <malloc.h>


#define max 9  //转换函数个数
//状态集
int statuscol_NFA[4]={100,101,102,103};
//字母表
int tableL_NFA[2]={0,1};
//状态标志含义：0表示非终态和初态，1表示终态，2表示初态，3表示即是初态也是终态
//转换函数
int function_NFA[max][4]={
{100,0,101,2},
{100,1,102,2},
{101,0,103,0},
{101,1,102,0},
{102,0,101,0},
{102,0,102,0},
{102,1,103,0},
{103,0,101,1},
{103,0,103,1}};
//初态集合
int status_A_NFA={100};
//终态集合
int status_B_NFA={103};

//DFA项目
struct item_DFA{
	int status_number;//DFA状态编号
	int number;//该状态包含的NFA状态
	int item_NFA[8];//DFA包含的NFA的状态集合
	int token[2];//面临的文法符号, 其中的2为字母表元素个数
	int status_number_next[2];//DFA面临文法符号到达的下一DFA状态的编号,其中的2为字母表元素个数
	int flag;//判断集合是否处理过
	struct item_DFA* next;
}*head_item_DFA,*tem_id,*last_id,*now_id;//头结点,临时结点,末结点,当前结点
//状态编号
int static_status_number=0;
//存放状态的临时集合
int tc[10];
int tc_number=-1;
int _tmain(int argc, _TCHAR* argv[])
{
	int i=0,j=0,tflag=0,k=0;
	//生成DFA的初态
	//添加一个集合项目,指针赋给*head,flag=0;item1-8都赋值为0
	//在tableNFA中逐项搜索状态标志为2或者3的状态项目,每搜索到一个NFA的状态项目,则填入到当前collection中的itemX中,number加1
	//完成后,得到DFA的初态

	//赋初值
	tem_id=(struct item_DFA *)malloc(sizeof(struct item_DFA));
	head_item_DFA=tem_id;

	//DFA状态编号0
	tem_id->status_number=static_status_number;

	tem_id->number=-1;	
	for(i=0;i<8;i++)
		tem_id->item_NFA[i]=-1;

	tem_id->token[0]=-1;	
	tem_id->token[1]=-1; 
	tem_id->status_number_next[0]=-1;	
	tem_id->status_number_next[1]=-1; 

	tem_id->flag=0;	

	tem_id->next=NULL;

	static_status_number=static_status_number+1;
	//向DFA添加NFA状态,形成DFA初态
	for(i=0;i<max;i++)
	{
		if(function_NFA[i][3]==2 || function_NFA[i][3]==3) //如果是初态
		{
			if(tem_id->number == -1)
			{
			tem_id->number=tem_id->number+1;
			tem_id->item_NFA[i]=function_NFA[i][0];
			}
			if(tem_id->number >= 0)
			{
				for(j=0;j<=tem_id->number;j++)
				{
					if(tem_id->item_NFA[j] == function_NFA[i][0])
					{
						tflag=1;
						break;
					}
				}
				if(tflag==0)
				{
					tem_id->number=tem_id->number+1;
					tem_id->item_NFA[i]=function_NFA[i][0];
				}
				else
					tflag=0;
			}
		}
	}
	
	//生成DFA的其它状态及其函数关系
	tem_id=head_item_DFA;
	last_id=head_item_DFA;
	now_id=head_item_DFA;	
	int temstatus;
Loop1:	//当前状态集没有处理过,进行处理
	if(now_id->flag == 0) 
	{		
		//修改当前的结点为处理过
		now_id->flag=1;
		//对每个输入符号做处理;2为本例输入符号个数,一个为0,一个为1
		for(i=0;i<2;i++)
		{
			//Move(tem_id,tableL_NFA[i])
			for(j=0;j <= now_id->number ;j++)
			{	//获取当前集合的每一项
				temstatus=now_id->item_NFA[j];			
				for(k=0;k < max;k++)
				{
					if(function_NFA[k][0] == temstatus && function_NFA[k][1] == tableL_NFA[i])
						{	
							//产生的集合放在tc数组中,相同元素不加入
							int temcou,temflag;
							temflag=0;
							for(temcou=0;temcou<10;temcou++)
							{
								if(function_NFA[k][2] ==tc[temcou])
								{
									temflag=1;
									break;
								}								
							}
							if(temflag==0)
							{
								tc_number=tc_number+1;
								tc[tc_number]=function_NFA[k][2];
							}
								
						}
				}
			}
			//有的DFA状态产生,判断tc集合是否在链表中有相同项,如果有则不生成新的状态
			int sameflag=0;//0为新的,1为在链表中有相同的
			if(tc_number>=0)
			{
				tem_id=head_item_DFA;
Loop3:
				if(tc_number != tem_id->number )
				{
					goto Loop5;
				}
				for(j=0;j<=tc_number;j++)
				{
					sameflag=0;					
					for(k=0;k<=tem_id->number;k++)
					{
						if(tc[j] != tem_id->item_NFA[k])
							sameflag=0;
						if(tc[j] == tem_id->item_NFA[k] )
						{
							sameflag=1;
							break;
						}
					}	
					if(sameflag==0 )//若没有找到,则表明该DFA状态为新状态
						break;
				}
Loop5:
				if(sameflag ==1 )//若已经找到与已有的DFA状态匹配,不用再做搜索
					goto Loop4;
				if (tem_id->next != NULL )
				{
					tem_id=tem_id->next ;
					goto Loop3;
				}
				else 
					goto Loop4;
			}
Loop4:
			if(sameflag==1)//未产生新的DFA状态
			{
				//修改当前结点信息
				//DFA下一个状态
				//tc数组存放已经存在的DFA状态
				//now_id->status_number_next[i]=static_status_number;
				now_id->status_number_next[i]=tem_id->status_number;
				now_id->token[i]=tableL_NFA[i];
				//tc_number=-1;
				//for(k=0;k<10;k++)
				//{
				//	tc[k]=-1;
				//}
			}

			if(sameflag == 0 && tc_number>=0)//产生新的DFA状态
				{
					//修改当前结点信息
					//DFA下一个状态
					now_id->status_number_next[i]=static_status_number;
					now_id->token[i]=tableL_NFA[i];

					//添加新结点
					tem_id=(struct item_DFA *)malloc(sizeof(struct item_DFA));	
					//初始化新结点
					tem_id->number=tc_number;	
					for(j=0;j<8;j++)
						tem_id->item_NFA[j]=-1;
					tem_id->token[0]=-1;	tem_id->token[1]=-1; tem_id->status_number=static_status_number;			
					static_status_number=static_status_number+1;	tem_id->flag=0;	
					tem_id->status_number_next[0]=-1; tem_id->status_number_next[0]=-1;
					for(j=0;j<=tc_number;j++)
						tem_id->item_NFA[j]=tc[j];
				
					//不能直接加入,察看是否为新的DFA状态,如果是加入新状态,补代码
					last_id->next=tem_id;
					tem_id->next=NULL;
					last_id=tem_id;	
				}
				tc_number=-1;
				for(k=0;k<10;k++)
				{
					tc[k]=-1;
				}

				int mtm;
				mtm=0;
			}
		if (now_id->next != NULL)
		{
			now_id=now_id->next ;
			goto Loop1;
		}
		else
			goto Loop2;
	}
Loop2:
	//printf("analysis over");
	getchar();

	return 0;
}