ag_regex.h

正则文法匹配检测器

		denoted by a sign. In regular expressions the concatenation
		is not denoted by ny sign so I will detect concatenation
		and insert a character 8 between operands.
	*/
	string ConcatExpand(string strRegEx);

	//! Creates Nondeterministic Finite Automata from a Regular Expression
	BOOL CreateNFA(string strRegEx);

	//! Calculates the Epsilon Closure 
	/*! Returns epsilon closure of all states
		given with the parameter.
	*/
	void EpsilonClosure(set<CAG_State*> T, set<CAG_State*> &Res); 

	//! Calculates all transitions on specific input char
	/*! Returns all states rechible from this set of states
		on an input character.
 	*/
	void Move(char chInput, set<CAG_State*> T, set<CAG_State*> &Res);

	//! Converts NFA to DFA using the Subset Construction Algorithm
	void ConvertNFAtoDFA();

	//! Optimizes the DFA
	/*! This function scanns DFA and checks for states that are not
		accepting states and there is no transition from that state
		to any other state. Then after deleting this state we need to
		go through the DFA and delete all transitions from other states
		to this one.
	*/
	void ReduceDFA();

	//! Cleans up the memory
	void CleanUp()
	{
		// Clean up all allocated memory for NFA
		for(int i=0; i<m_NFATable.size(); ++i)
			delete m_NFATable[i];
		m_NFATable.clear();

		// Clean up all allocated memory for DFA
		for(i=0; i<m_DFATable.size(); ++i)
			delete m_DFATable[i];
		m_DFATable.clear();

		// Reset the id tracking
		m_nNextStateID = 0;

		// Clear both stacks
		while(!m_OperandStack.empty())
			m_OperandStack.pop();
		while(!m_OperatorStack.empty())
			m_OperatorStack.pop();

		// Clean up the Input Character set
		m_InputSet.clear();

		// Clean up all pattern states
		list<CAG_PatternState*>::iterator iter;
		for(iter=m_PatternList.begin(); iter!=m_PatternList.end(); ++iter)
			delete *iter;
		m_PatternList.clear();
	};

	//! Searches the text for all occurences of the patterns
	/*! Returns TRUE if single pattern is found or FALSE if 
	    no pattern sis found.
	*/
	BOOL Find();

public:
	//! Default Constructor
	CAG_RegEx();

	//! Destructor
	virtual ~CAG_RegEx();

	//! Set Regular Expression
	/*! Set the string pattern to be searched for.
		Returns TRUE if success othewise it returns FALSE.
	*/
	BOOL SetRegEx(string strRegEx);

	//! Searches for the first occurence of a text pattern
	/*! If the pattern is found the function returns TRUE
		together with starting positions (vecPos) and the patterns
		(vecPattern) found. THIS FUNCTION MUST BE CALLED FIRST.
		The return value is TRUE if a pattern is found or FALSE
		if nothing is found.
	*/
	BOOL FindFirst(string strText, int &nPos, string &strPattern);

	//! Searches for the next occurence of a text pattern
	/*! If the pattern is found the function returns TRUE
		together with starting position array (vecPos) and the patterns
		(vecPattern) found. THIS FUNCTION MUST BE CALLED AFTER 
		THE FUNCTION FindFirst(...). 
		The return value is TRUE if a pattern is found or FALSE
		if nothing is found.
	*/
	BOOL FindNext(int &nPos, string &strPattern);

#ifdef _DEBUG
	//! For Debuging purposes only
	void SaveNFATable()
	{
		CString strNFATable;

		// First line are input characters
		set<char>::iterator iter;
		for(iter = m_InputSet.begin(); iter != m_InputSet.end(); ++iter)
			strNFATable += "\t\t" + CString(*iter);
		// add epsilon
		strNFATable += "\t\tepsilon";
		strNFATable += "\n";

		// Now go through each state and record the transitions
		for(int i=0; i<m_NFATable.size(); ++i)
		{
			CAG_State *pState = m_NFATable[i];
			
			// Save the state id
			strNFATable += pState->GetStateID();

			// now write all transitions for each character
			vector<CAG_State*> State;
			for(iter = m_InputSet.begin(); iter != m_InputSet.end(); ++iter)
			{
				pState->GetTransition(*iter, State);
				CString strState;
				if(State.size()>0)
				{
					strState = State[0]->GetStateID();
					for(int i=1; i<State.size(); ++i)
						strState += "," + State[i]->GetStateID();
				}
				strNFATable += "\t\t" + strState;
			}

			// Add all epsilon transitions
			pState->GetTransition(0, State);
			CString strState;
			if(State.size()>0)
			{
				strState = State[0]->GetStateID();
				for(int i=1; i<State.size(); ++i)
					strState += "," + State[i]->GetStateID();
			}
			strNFATable += "\t\t" + strState + "\n";
		}

		// Save table to the file
		CStdioFile f;
		if(f.Open("C:\\NFATable.txt", CFile::modeCreate | CFile::modeWrite))
		{
			f.WriteString(strNFATable);
			f.Close();
		}
		else AfxMessageBox(_T("Could not save NFA Table to c:\\NFATable.txt"));
	};

	//! For Debuging purposes only
	void SaveDFATable()
	{
		CString strDFATable;

		// First line are input characters
		set<char>::iterator iter;
		for(iter = m_InputSet.begin(); iter != m_InputSet.end(); ++iter)
			strDFATable += "\t\t" + CString(*iter);
		strDFATable += "\n";

		// Now go through each state and record the transitions
		for(int i=0; i<m_DFATable.size(); ++i)
		{
			CAG_State *pState = m_DFATable[i];
			
			// Save the state id
			strDFATable += pState->GetStateID();

			// now write all transitions for each character
			vector<CAG_State*> State;
			for(iter = m_InputSet.begin(); iter != m_InputSet.end(); ++iter)
			{
				pState->GetTransition(*iter, State);
				CString strState;
				if(State.size()>0)
				{
					strState = State[0]->GetStateID();
					for(int i=1; i<State.size(); ++i)
						strState += "," + State[i]->GetStateID();
				}
				strDFATable += "\t\t" + strState;
			}
			strDFATable += "\n";
		}

		// Save table to the file
		CStdioFile f;
		if(f.Open("C:\\DFATable.txt", CFile::modeCreate | CFile::modeWrite))
		{
			f.WriteString(strDFATable);
			f.Close();
		}
		else AfxMessageBox(_T("Could not save DFA Table to c:\\DFATable.txt"));
	};

	void SaveNFAGraph() 
	{
		CString strNFAGraph = _T("digraph{\n");

		// Final states are double circled
		for(int i=0; i<m_NFATable.size(); ++i)
		{
			CAG_State *pState = m_NFATable[i];
			if(pState->m_bAcceptingState)
			{
				CString strStateID = pState->GetStateID();
				strStateID.Remove('{'); strStateID.Remove('}');
				strNFAGraph += _T("\t") + strStateID + _T("\t[shape=doublecircle];\n");
			}
		}
		
		strNFAGraph += _T("\n");

		// Record transitions
		for(i=0; i<m_NFATable.size(); ++i)
		{
			CAG_State *pState = m_NFATable[i];
			vector<CAG_State*> State;

			pState->GetTransition(0, State);
			for(int j=0; j<State.size(); ++j)
			{
				// Record transition
				CString strStateID1 = pState->GetStateID();
				CString strStateID2 = State[j]->GetStateID();
				strStateID1.Remove('{'); strStateID1.Remove('}');
				strStateID2.Remove('{'); strStateID2.Remove('}');
				strNFAGraph += _T("\t") + strStateID1 + _T(" -> ") + strStateID2;
				strNFAGraph += _T("\t[label=\"epsilon\"];\n");
			}

			set<char>::iterator iter;
			for(iter = m_InputSet.begin(); iter != m_InputSet.end(); ++iter)
			{
				pState->GetTransition(*iter, State);
				for(int j=0; j<State.size(); ++j)
				{
					// Record transition
					CString strStateID1 = pState->GetStateID();
					CString strStateID2 = State[j]->GetStateID();
					strStateID1.Remove('{'); strStateID1.Remove('}');
					strStateID2.Remove('{'); strStateID2.Remove('}');
					strNFAGraph += _T("\t") + strStateID1 + _T(" -> ") + strStateID2;
					strNFAGraph += _T("\t[label=\"") + CString(*iter) + _T("\"];\n");
				}
			}
		}

		strNFAGraph += _T("}");

		// Save table to the file
		CStdioFile f;
		if(f.Open("C:\\NFAGraph.dot", CFile::modeCreate | CFile::modeWrite))
		{
			f.WriteString(strNFAGraph);
			f.Close();
		}
		else AfxMessageBox(_T("Could not save NFA Graph to c:\\NFAGraph.txt"));
	};
	
	void SaveDFAGraph()
	{
		CString strDFAGraph = _T("digraph{\n");

		// Final states are double circled
		for(int i=0; i<m_DFATable.size(); ++i)
		{
			CAG_State *pState = m_DFATable[i];
			if(pState->m_bAcceptingState)
			{
				CString strStateID = pState->GetStateID();
				strStateID.Remove('{'); strStateID.Remove('}');
				strDFAGraph += _T("\t") + strStateID + _T("\t[shape=doublecircle];\n");
			}
		}
		
		strDFAGraph += _T("\n");

		// Record transitions
		for(i=0; i<m_DFATable.size(); ++i)
		{
			CAG_State *pState = m_DFATable[i];
			vector<CAG_State*> State;

			pState->GetTransition(0, State);
			for(int j=0; j<State.size(); ++j)
			{
				// Record transition
				CString strStateID1 = pState->GetStateID();
				CString strStateID2 = State[j]->GetStateID();
				strStateID1.Remove('{'); strStateID1.Remove('}');
				strStateID2.Remove('{'); strStateID2.Remove('}');
				strDFAGraph += _T("\t") + strStateID1 + _T(" -> ") + strStateID2;
				strDFAGraph += _T("\t[label=\"epsilon\"];\n");
			}

			set<char>::iterator iter;
			for(iter = m_InputSet.begin(); iter != m_InputSet.end(); ++iter)
			{
				pState->GetTransition(*iter, State);
				for(int j=0; j<State.size(); ++j)
				{
					// Record transition
					CString strStateID1 = pState->GetStateID();
					CString strStateID2 = State[j]->GetStateID();
					strStateID1.Remove('{'); strStateID1.Remove('}');
					strStateID2.Remove('{'); strStateID2.Remove('}');
					strDFAGraph += _T("\t") + strStateID1 + _T(" -> ") + strStateID2;
					strDFAGraph += _T("\t[label=\"") + CString(*iter) + _T("\"];\n");
				}
			}
		}

		strDFAGraph += _T("}");

		// Save table to the file
		CStdioFile f;
		if(f.Open("C:\\DFAGraph.dot", CFile::modeCreate | CFile::modeWrite))
		{
			f.WriteString(strDFAGraph);
			f.Close();
		}
		else AfxMessageBox(_T("Could not save DFA Graph to c:\\DFAGraph.txt"));
	};
#else
	void SaveNFATable() { } ;
	void SaveDFATable() { } ;
	void SaveNFAGraph() { } ;
	void SaveDFAGraph() { } ;
#endif
};