remanage.cpp

识别正规式

// REManage.cpp: implementation of the REManage class.
//
//////////////////////////////////////////////////////////////////////
#pragma warning(disable:4786)

#include "REManage.h"
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <windows.h>

using namespace std;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

REManage::REManage()
{
	out.open("Result.txt");
	this->state=1;
	this->isREUpdate=false;
	this->isNFAUpdate=false;
	this->isDFAUpdate=false;
}	
REManage::REManage(string re)
{
	this->state=1;
	this->re=re;
	this->isREUpdate=true;
}	
REManage::~REManage()
{	
}
void REManage::MakeNFA_S(char input,NFA* n,vector<EDGE>& edge)
{
	EDGE e;
	if(n->start==0&&n->end==0)
	{
		e.start=n->start=state;
		e.input=input;
		e.end=n->end=++state;
		
		state++;
	}
	else
	{
		e.start=n->start;
		e.input=input;
		e.end=n->end;
	}
	
	edge.push_back(e);
}
void REManage::MakeNFA_OR(NFA* result,NFA* left,NFA* right,vector<EDGE>& edge)
{
	NFA temp;
	result->start=temp.start=state;
	temp.end=left->start;
	MakeNFA_S('$',&temp,edge);	
	
	temp.start=state;
	temp.end=right->start;
	MakeNFA_S('$',&temp,edge);
	
	temp.start=left->end;
	temp.end=++state;
	MakeNFA_S('$',&temp,edge);
	
	temp.start=right->end;
	result->end=temp.end=state;
	MakeNFA_S('$',&temp,edge);
	
	state++;
}
void REManage::MakeNFA_AND(NFA* result,NFA* left,NFA* right,vector<EDGE>& edge)
{
	result->start=left->start;
	result->end=right->end;
	
	for(int i=0;i<edge.size();i++)
	{
		if(edge[i].start==right->start)
		{
			edge[i].start=left->end;
		}
	}
}
void REManage::MakeNFA_CL(NFA* result,NFA* op,vector<EDGE>& edge)
{
	NFA temp;
	result->start=temp.start=state;
	temp.end=op->start;
	MakeNFA_S('$',&temp,edge);
	
	temp.start=op->end;
	result->end=temp.end=++state;
	MakeNFA_S('$',&temp,edge);
	
	temp.start=op->end;
	temp.end=op->start;
	MakeNFA_S('$',&temp,edge);
	
	temp.start=result->start;
	temp.end=result->end;
	MakeNFA_S('$',&temp,edge);
	
	state++;	
}
int REManage::type(char re)
{
	if(re=='*'||re=='|')
		return OP;
	else if(re!='('&&re!=')')
		return OP_D;
	else
		return -1;
}

void REManage::ProcessREToNFA()
/*
===================
输入：
	  re
	  REInput
===================
输出：
	  NFA_EDGE
	  NFAInput
	  startNFA
	  endNFA
===================
*/
{
	stack<char> st;			//操作符堆栈，保存处理过程中遇到的操作符
	stack<NFA> sNFA;		//NFA堆栈，保存处理过程中产生的NFA

	NFA nfa,temp;
	NFA result;				//临时变量

	/**************************Process RE***********************/
	for(int i=0;i<re.length();i++)
	{
		if(re[i]=='(')
		{
			st.push(re[i]);
		}
		else if(type(re[i])==OP_D)
		{
			/************Get input of RE************/
			if(find(REInput.begin(),REInput.end(),re[i])==REInput.end())
				REInput.push_back(re[i]);	
			/******************End*******************/

			nfa.start=0;
			nfa.end=0;
			MakeNFA_S(re[i],&nfa,NFA_EDGE);

			sNFA.push(nfa);
			if(sNFA.size()>=2)
			{
				if(st.size()>0&&st.top()=='|')
				{
					st.pop();
					
					temp=sNFA.top();
					sNFA.pop();
					nfa=sNFA.top();
					sNFA.pop();
					
					MakeNFA_OR(&result,&nfa,&temp,NFA_EDGE);
					sNFA.push(result);
				}
				else if(i>0&&re[i-1]!='(')
				{
					temp=sNFA.top();
					sNFA.pop();
					nfa=sNFA.top();
					sNFA.pop();
					
					MakeNFA_AND(&result,&nfa,&temp,NFA_EDGE);
					sNFA.push(result);
				}
			}
		}
		else if(type(re[i])==OP)
		{
			if(re[i]=='*')
			{
				nfa=sNFA.top();
				sNFA.pop();
				MakeNFA_CL(&result,&nfa,NFA_EDGE);
				sNFA.push(result);
			}
			else if(re[i]=='|')
			{
				st.push(re[i]);
			}
		}
		else if(re[i]==')')
		{
			st.pop();
			if(sNFA.size()>=2)
			{	
				temp=sNFA.top();
				sNFA.pop();
				nfa=sNFA.top();
				sNFA.pop();
				
				MakeNFA_AND(&result,&nfa,&temp,NFA_EDGE);
				sNFA.push(result);
			}
		}
	}
	/*******************************End*********************************/

	/****************Get start and end state of NFA************/
	if(sNFA.size()>0)
	{
		startNFA.push_back(sNFA.top().start);
		endNFA.push_back(sNFA.top().end);
		//startNFA.start=sNFA.top().start;
		//startNFA.end=sNFA.top().end;
	}
	/**************************End**************************/

	/****************************Test**************************/
	/*cout<<"===============NFA==============="<<endl;
	cout<<"Start state: "<<startNFA[0]<<" ,End state:"<<endNFA[0]<<endl;
	//cout<<"Start state: "<<startNFA.start<<" ,End state:"<<startNFA.end<<endl;
	
	for(int j=0;j<NFA_EDGE.size();j++)
		cout<<"Edge "<<j<<": "<<NFA_EDGE[j].start
		<<"  "<<NFA_EDGE[j].input<<"  "
		<<"  "<<NFA_EDGE[j].end<<endl;
	
	for(int m=0;m<REInput.size();m++)
		cout<<REInput[m]<<" ";
	cout<<endl;*/
	/****************************Test**************************/
}

void REManage::Find_NULL_Closure(vector<int> input, 
								 vector<int>&output,
								 vector<EDGE> edge)
{
	stack<int> state;

	output.clear();

	sort(input.begin(),input.end());

	for(int i=0;i<input.size();i++)
		state.push(input[i]);
	int temp=0;

	while(state.size()>0)
	{		
		output.push_back(state.top());
		temp=state.top();
		state.pop();
		for(int j=0;j<NFA_EDGE.size();j++)
			if(edge[j].start==temp&&edge[j].input=='$')
				state.push(edge[j].end);
	}

	sort(output.begin(),output.end());
}

void REManage::Move(vector<int> input,char in,vector<int>&result,vector<EDGE> edge)
{
	vector<int> temp;
	temp.clear();
	result.clear();
	
	for(int i=0;i<input.size();i++)
	{
		for(int j=0;j<edge.size();j++)
			if(edge[j].start==input[i]&&edge[j].input==in)
				temp.push_back(edge[j].end);
	}
	
	Find_NULL_Closure(temp,result,edge);
}

void REManage::ProcessNFAToDFA()
/*
===================
输入：
	  NFA_EDGE
	  NFAInput
	  startNFA
	  endNFA
===================
输出：
	  startDFA
	  endDFA
	  nonEndDFA
	  DFA_EDGE
	  DFAStateGather
===================
*/
{
	EDGE edge;				//临时变量
	vector<int> DFAState;	//临时变量，保存某一状态集

	//vector<int> start;		//开始状态集，实际只有一个元素
	int	over=-1;			//标记已处理过的状态集
	
	//start.push_back(startNFA.start);		
	//Find_NULL_Closure(start, DFAState,NFA_EDGE);

	//由NFA得到初始状态集
	Find_NULL_Closure(startNFA, DFAState,NFA_EDGE);

	DFAStateGather.push_back(DFAState);
	startDFA=DFAStateGather.size()-1;	//得到初始状态
	
	/*=========================add=========================*/
	for(int m=0;m<endNFA.size();m++)
	{
		if(find(DFAState.begin(),DFAState.end(),endNFA[m])!=DFAState.end())
			break;
	}
	
	if(m<endNFA.size())
		endDFA.push_back(DFAStateGather.size()-1);
	else
		nonEndDFA.push_back(DFAStateGather.size()-1);
	/*=========================add=========================*/


	/*if(find(DFAState.begin(),DFAState.end(),startNFA.end)!=DFAState.end())
		endDFA.push_back(DFAStateGather.size()-1);
	else
		nonEndDFA.push_back(DFAStateGather.size()-1);*/

	/*****************Process NFA**********************/
	queue<vector<int> > tempState;
	tempState.push(DFAState);
	vector<vector<int> >::iterator iter;
	while(tempState.size()>0)
	{
		over++;

		edge.start=find(DFAStateGather.begin(),DFAStateGather.end(),
				tempState.front())-DFAStateGather.begin();

		for(int i=0;i<NFAInput.size();i++)
		{
			//求队列首状态集在输入为input[i]时的结果状态
			Move(tempState.front(),NFAInput[i],DFAState,NFA_EDGE);	
			if(DFAState.size()<1)
				break;
			//填充DFA的边					
			edge.input=NFAInput[i];
			
			iter=find(DFAStateGather.begin(),DFAStateGather.end(),DFAState);
			
			//如果所产生的状态集不在DFAStateGather中，则保存该状态集
			if(iter==DFAStateGather.end())
			{	
				DFAStateGather.push_back(DFAState);
				
				/*=========================add=========================*/
				for(int m=0;m<endNFA.size();m++)
				{
					if(find(DFAState.begin(),DFAState.end(),endNFA[m])!=DFAState.end())
						break;
				}
				
				if(m<endNFA.size())
					endDFA.push_back(DFAStateGather.size()-1);
				else
					nonEndDFA.push_back(DFAStateGather.size()-1);
				/*=========================add=========================*/

				/*//测试是否包含NFA的终态，产生DFA的终态集和非终态集
				if(find(DFAState.begin(),DFAState.end(),startNFA.end)!=DFAState.end())
					endDFA.push_back(DFAStateGather.size()-1);
				else
					nonEndDFA.push_back(DFAStateGather.size()-1);*/

				edge.end=DFAStateGather.size()-1;	
			}
			else
				edge.end=iter-DFAStateGather.begin();
			//保存边
			DFA_EDGE.push_back(edge);

			if(DFAState!=tempState.front()&&edge.end>over)
				tempState.push(DFAState);
		}
		tempState.pop();
	}
	/*************************End*******************************/
	
	/*************************Test******************************/
	/*for(int i=0;i<DFAStateGather.size();i++)
	{
		cout<<"Gather "<<i<<":";
		for(int j=0;j<DFAStateGather[i].size();j++)
			cout<<DFAStateGather[i][j]<<" ";
		cout<<endl;
	}
	
	cout<<"===============DFA==============="<<endl;

	cout<<"Start state:"<<startDFA<<endl;
	cout<<"End state gather: ";
	for(int i=0;i<endDFA.size();i++)
		cout<<endDFA[i]<<" ";
	cout<<endl;

	for(i=0;i<DFA_EDGE.size();i++)
	{
		cout<<"Edge "<<i<<": "<<DFA_EDGE[i].start<<"  "
			<<DFA_EDGE[i].input<<"  "
			<<DFA_EDGE[i].end<<"  "<<endl;
	}*/
	/*************************End******************************/
}

/*消除DFA中的无用状态*/
void REManage::RemoveFutility()
/*
===================
输入：
	  miniStartDFA
	  miniEndDFA
      miniNonEndDFA
	  MiniDFA_EDGE
	  miniStateGather
===================
输出：
	  miniStartDFA
	  miniEndDFA
      miniNonEndDFA
	  MiniDFA_EDGE
	  miniStateGather	  
===================
*/
{

	vector<int>	reachedState;
	queue<int>	reached;

	vector<int> startGather;
	vector<int>	endGather;

	reachedState.clear();	


	/****************Generate reached state*******************/
	reached.push(miniStartDFA);
	reachedState.push_back(miniStartDFA);

	while(reached.size()>0)
	{
		int front=reached.front();
		reached.pop();

		for(int i=0;i<MiniDFA_EDGE.size();i++)
		{
			if(find(DFAInput.begin(),DFAInput.end(),MiniDFA_EDGE[i].input)
				==DFAInput.end())
				DFAInput.push_back(MiniDFA_EDGE[i].input);

			if(MiniDFA_EDGE[i].start==front)
			{
				if(find(reachedState.begin(),reachedState.end(),MiniDFA_EDGE[i].end)
					==reachedState.end())
				{
					reachedState.push_back(MiniDFA_EDGE[i].end);
					reached.push(MiniDFA_EDGE[i].end);
				}
			}
		}
	}
	sort(reachedState.begin(),reachedState.end());
	/*****************************end******************************/

	/****************Update the edge of DFA*******************/
	vector<EDGE>::iterator iterEDGE;
	
	for(int i=0;i<MiniDFA_EDGE.size();i++)
	{
		if(find(reachedState.begin(),reachedState.end(),MiniDFA_EDGE[i].start)
			==reachedState.end())
		{
			iterEDGE=MiniDFA_EDGE.begin()+i;
			MiniDFA_EDGE.erase(iterEDGE++);
			i--;
		}
	}
	/*****************************end******************************/

	/****************Update the end state of DFA*******************/
	vector<int>::iterator iterEnd;
	for(i=0;i<miniEndDFA.size();i++)
	{
		if(find(reachedState.begin(),reachedState.end(),miniEndDFA[i])
			==reachedState.end())
		{
			iterEnd=miniEndDFA.begin()+i;
			miniEndDFA.erase(iterEnd++);
			i--;
		}
	}
	/*****************************end******************************/
	
	/******************remove not end state************************/	
	int initSize=reachedState.size()+1;

	while(reachedState.size()<initSize)
	{
		initSize=reachedState.size();

		startGather.clear();
		endGather.clear();

		for(int m=0;m<MiniDFA_EDGE.size();m++)
		{
			if(find(startGather.begin(),startGather.end(),MiniDFA_EDGE[m].start)
				==startGather.end())
				startGather.push_back(MiniDFA_EDGE[m].start);