remanage.h

识别正规式

// REManage.h: interface for the REManage class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_REMANAGE_H__5B8C1C6A_7551_4DF0_B01E_1D40C5481F88__INCLUDED_)
#define AFX_REMANAGE_H__5B8C1C6A_7551_4DF0_B01E_1D40C5481F88__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <fstream>
using namespace std;

const int OP=0;		//操作符
const int OP_D=1;	//操作数

typedef class _EDGE
{
public:
	int start;
	char input;
	int end;
	friend bool operator == (const _EDGE& a,const _EDGE& b)
	{
		return (a.start==b.start)&&(a.input==b.input)&&(a.end==b.end);
	}
}EDGE;		//自动机的边

typedef struct _NFA
{
	int start;
	int end;
}NFA;		//

class REManage  
{
public:
	REManage();
	REManage(string re);
	virtual ~REManage();
	
	//处理新的输入
	void Process();

	//测试输入字符串，判断能否由生成的DFA识别
	bool TestString(string str);
	
	//设置正规式
	void setRE(string re);

	//设置NFA
	void setNFA(vector<EDGE> edge,vector<int> start,vector<int> end);

	//设置DFA
	void setDFA(vector<EDGE> edge,int start,vector<int> end);

	
private:
	//清空所有容器变量
	void clear();

	//输出处理结果
	void OutputResult();

	/********************分析RE函数**********************/
	/*正规式到NFA的转换*/
	void ProcessREToNFA();

	int state;		//计数状态
	int type(char re);		//判断输入字符的类型: OP,OP_D
	/********************End*****************************/

	/********************RE到NFA转换有关函数*************************/
	/*对单个输入字符构造相应的NFA*/
	void MakeNFA_S(char input,NFA* n,vector<EDGE>& edge);

	/*构造某个NFA的闭包*/
	void MakeNFA_CL(NFA* result,NFA* op,vector<EDGE>& edge);

	/*构造两个NFA的或运算*/
	void MakeNFA_OR(NFA* result,NFA* left,NFA* right,vector<EDGE>& edge);

	/*构造两个NFA的与运算*/
	void MakeNFA_AND(NFA* result,NFA* left,NFA* right,vector<EDGE>& edge);
	/******************************End*******************************/

	/********************************NFA到DFA转换有关函数*************************/
	/*NFA到DFA的转换*/
	void ProcessNFAToDFA();

	/*找到集合input的$闭包，结果保存在集合output中*/
	void Find_NULL_Closure(vector<int> input, vector<int>&output,vector<EDGE> edge);

	/*计算集合input在输入为in时的所能达到的状态集合result*/
	void Move(vector<int> input,char in,vector<int>&result,vector<EDGE> edge);
	/***************************************End***********************************/

	/********************************DFA最小化有关函数*************************/
	/*最小化DFA*/
	void MinimizeDFA();

	/*在DFA中当初态为start，输入为input时，返回终态*/
	int MovdDFA(int start,char input);

	/*找到输入终态end所在的集合*/
	int FindGather(int end,vector<vector<int> > gather);

	/*消除DFA中的无用状态*/
	void RemoveFutility();

	/*合并DFA中的等价状态*/
	void CombineEquality();
	/*************************************End**********************************/
	
	ofstream out;
	
	//正规式对应的变量
	string re;				//输入的正规式
	vector<char> REInput;		//正规式的输入符
	bool isREUpdate;		//正规式是否已更新
	
	//NFA对应的变量
	vector<char> NFAInput;	//NFA的输入符
	vector<int>	startNFA;	//NFA的起始状态集
	vector<int>	endNFA;		//NFA的终态集
	vector<EDGE> NFA_EDGE;		//构造出的NFA的所有边的集合
	bool isNFAUpdate;		//NFA是否已更新
	
	//DFA对应的变量
	vector<char> DFAInput;	//DFA的输入符
	int startDFA;			//DFA的起始状态
	vector<int> endDFA;		//DFA的终态集
	vector<int> nonEndDFA;	//DFA的非终态集	
	vector<EDGE> DFA_EDGE;	//由NFA所构造成的DFA的边的集合
	vector<vector<int> > DFAStateGather;		//DFA中各个状态对应于NFA中的状态集
	bool isDFAUpdate;		//DFA是否已更新

	//DFA最小化后对应的变量
	vector<char> miniDFAInput;	//最小化后DFA的输入符
	int miniStartDFA;			//最小化后DFA的起始状态
	vector<int> miniEndDFA;		//最小化后DFA的终态集
	vector<int> miniNonEndDFA;	//最小化后DFA的非终态集
	vector<EDGE> MiniDFA_EDGE;	//最小化后DFA中的边的集合
	vector<vector<int> > miniStateGather;	//最小化后DFA中各个状态对应于初始DFA中的状态集
};

#endif // !defined(AFX_REMANAGE_H__5B8C1C6A_7551_4DF0_B01E_1D40C5481F88__INCLUDED_)