remanage.h

识别正规式

#pragma once

#ifndef INCLUDE_REMANAGE_H
#define INCLUDE_REMANAGE_H

#include <string>
#include <vector>
#include <queue>
#include <list>
using namespace std;

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

typedef class _EDGE
{
public:
	size_t start;
	char input;
	size_t 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
{
	size_t start;
	size_t end;
}NFA;
class REManage
{
public:
	REManage();
	REManage(string re);
	virtual ~REManage();
	
	//处理输入
	void Process();
	
	//设置正规式
	bool setRE(string re);

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

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

	//判断输入的式子是否为正规式
	bool REJudge()const;

	//清空所有容器变量
	void clear();
	
private:
	//输出处理结果
	void OutputResult();

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

	unsigned state;		//计数状态
	unsigned 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<unsigned> input, vector<unsigned>&output,vector<EDGE> edge);

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

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

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

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

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

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

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


#endif