remanage.cpp

识别正规式

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

using namespace std;

REManage::REManage()
{
	this->state=1;
}	
REManage::REManage(string re)
{
	this->state=1;
	this->re=re;
}	
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(unsigned 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,temp2;

	temp.start=state;
	temp.end = op->start;
	MakeNFA_S('$',&temp,edge);

	temp2.start = op->end;
	temp2.end = temp.start;
	MakeNFA_S('$',&temp2,edge);

	result->start = temp2.start = ++state;
	temp2.end = temp.start;
	MakeNFA_S('$',&temp2,edge);
	
	result->end = temp2.start = ++state;
	temp.end = temp2.start;
	MakeNFA_S('$',&temp,edge);	

	state++;
}

unsigned 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
===================
*/
{
	int AND_flag1=0,AND_flag2=0;			//是否应该做连接操作的标志
	stack<char> st;			//操作符堆栈，保存处理过程中遇到的操作符
	stack<NFA> sNFA;		//NFA堆栈，保存处理过程中产生的NFA

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

	for(unsigned i=0;i<re.length();i++)
	{
		if(re[i]=='(')
		{
			st.push(re[i]);
			if(i>0&&re[i-1] != '|'&&re[i-1] != '(')
			{
				AND_flag2 = 1;
				cout<<"连接标志置1"<<endl;
			}
			cout<<"左括号压栈"<<endl;
		}
		else if(type(re[i])==OP_D)
		{
			if(find(REInput.begin(),REInput.end(),re[i])==REInput.end())
				REInput.push_back(re[i]);	

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

			sNFA.push(nfa);
			cout<<"生成单NFA"<<endl;
			if(sNFA.size()>=2)
			{
				if(i>0&&re[i-1]!='('&&
					(i == re.length()-1||re[i+1] != '*')
					&&re[i-1] != '|')
				{
					temp=sNFA.top();
					sNFA.pop();
					nfa=sNFA.top();
					sNFA.pop();
					
					MakeNFA_AND(&result,&nfa,&temp,NFA_EDGE);
					sNFA.push(result);
					cout<<"生成连接NFA"<<endl;
					if(st.size()>0&&st.top() == '|'&&
					i == re.length()-1)
					{
						st.pop();
						
						temp=sNFA.top();
						sNFA.pop();
						nfa=sNFA.top();
						sNFA.pop();
						
						MakeNFA_OR(&result,&nfa,&temp,NFA_EDGE);
						sNFA.push(result);
						cout<<"生成或NFA"<<endl;
					}
				}
				else if(st.size()>0&&st.top() == '|'&&
					i == re.length()-1)
				{
					st.pop();
					
					temp=sNFA.top();
					sNFA.pop();
					nfa=sNFA.top();
					sNFA.pop();
					
					MakeNFA_OR(&result,&nfa,&temp,NFA_EDGE);
					sNFA.push(result);
					cout<<"生成或NFA"<<endl;
				}
				
				else if(i>0&&re[i-1]!='('
					&&re[i+1] == '*'&&re[i-1] != '|')
				{
					AND_flag1 = 1;
					cout<<"连接标志置1"<<endl;
				}
			}
		}
		else if(type(re[i])==OP)
		{
			if(re[i]=='*')
			{
				nfa=sNFA.top();
				sNFA.pop();
				MakeNFA_CL(&result,&nfa,NFA_EDGE);
				sNFA.push(result);
				cout<<"生成闭包NFA"<<endl;
				if((AND_flag2 == 1&&st.size()>0&&st.top() == ')')
					||AND_flag1 == 1)
				{
					if(AND_flag2 == 1&&st.size()>0&&st.top() == ')')
					{
						AND_flag2 = 0;
						st.pop();
						st.pop();
					}
					if(AND_flag1 == 1)AND_flag1 = 0;
					temp=sNFA.top();
					sNFA.pop();
					nfa=sNFA.top();
					sNFA.pop();
					
					MakeNFA_AND(&result,&nfa,&temp,NFA_EDGE);
					sNFA.push(result);
					cout<<"生成连接NFA"<<endl;
				}
				if(i == re.length()-1&&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);
					cout<<"生成或NFA"<<endl;
				}
			}
			else if(re[i]=='|')
			{
				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);
					cout<<"生成或NFA"<<endl;
				}
				st.push(re[i]);
				cout<<"\'|\'运算符压栈"<<endl;
			}
		}
		else if(re[i]==')')
		{
			if(st.size()>0&&st.top() == '|')
			{
				temp=sNFA.top();
				sNFA.pop();
				nfa=sNFA.top();
				sNFA.pop();
				
				MakeNFA_OR(&result,&nfa,&temp,NFA_EDGE);
				sNFA.push(result);
				cout<<"生成或NFA"<<endl;
				if(i != re.length()-1&&re[i+1] != '*')
				{
					st.pop();
					st.pop();
				}
			}
			st.push(re[i]);
			if(sNFA.size()>=2)
			{	
				if(i != re.length()-1&&re[i+1] == '*')
				{
					if(AND_flag2 == 0)
					{
						st.pop();
						st.pop();
					}
					continue;
				}
				if(AND_flag2 == 1)
				{
					AND_flag2 = 0;
					temp=sNFA.top();
					sNFA.pop();
					nfa=sNFA.top();
					sNFA.pop();
					
					MakeNFA_AND(&result,&nfa,&temp,NFA_EDGE);
					sNFA.push(result);
					cout<<"生成连接NFA"<<endl;
				}
				if(i == re.length()-1&&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);
					cout<<"生成或NFA"<<endl;
				}				
			}
		}
	}
	if(sNFA.size()>0)
	{
		startNFA.push_back(sNFA.top().start);
		endNFA.push_back(sNFA.top().end);
	}

}

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

	output.clear();

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

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

	while(state.size()>0)
	{
		if(find(output.begin(),output.end(),state.top())
			!= output.end())
		{
			state.pop();
			continue;
		}
		output.push_back(state.top());
		temp=state.top();
		state.pop();
		for(unsigned 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<unsigned> input,char in,vector<unsigned>&result,vector<EDGE> edge)
{
	vector<unsigned> temp;
	temp.clear();
	result.clear();
	
	for(unsigned i=0;i<input.size();i++)
	{
		for(unsigned 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<unsigned> DFAState;	//临时变量，保存某一状态集

	unsigned over=-1;			//标记已处理过的状态集
	unsigned m;

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

	DFAStateGather.push_back(DFAState);
	startDFA=DFAStateGather.size()-1;	//得到初始状态

	for(m=0;m<endNFA.size();m++)
	{
		if(find(DFAState.begin(),DFAState.end(),endNFA[m])!=DFAState.end())
			break;
	}

	if(m<endNFA.size())
		endDFA.push_back((unsigned)(DFAStateGather.size()-1));
	else
		nonEndDFA.push_back((unsigned)(DFAStateGather.size()-1));

	queue<vector<unsigned> > tempState;
	tempState.push(DFAState);
	vector<vector<unsigned> >::iterator iter;
	while(tempState.size()>0)
	{
		over++;
		edge.start=find(DFAStateGather.begin(),DFAStateGather.end(),
				tempState.front())-DFAStateGather.begin();

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