dfa.h

来自「输入一个正则表达式」· C头文件 代码 · 共 53 行

#ifndef _DFA_H_
#define _DFA_H_

#include "NFA.h"

class DFA
{
private:
	typedef int							*StateItem;
	typedef vector <StateItem>			StateTranTable;
	typedef StateTranTable::iterator	StateTranIt;

	// Destroy STT
	void	destroySTT();

	// Create a new item, return the index of the new item
	int		newItem();

	// add stateSet ss into STT[i][j], using setVec and nfa start set:nfaF.
	void	addItem(StateSet &ss, int i, int j, vector <StateSet> &setVec, StateSet &nfaF);

	// if State[i] and State[j] is the same state
	int		isSameState(int i, int j);
	
	// merge State[b] into state[a], and delete [b]
	void	mergeState(int a, int b);

protected:
	int				alphaSize;
	int				*rawMap;

	StateSet		F;
	int				Q;
	StateTranTable	STT;
	int				STTSize;

public:
	DFA(NFA *n, int *_rawMap);
	~DFA();

	// build a DFA from an NFA
	void	buildDFA(NFA *n);
	
	// minimize the DFA
	void	minimize();

	// identify if the string is the language of this DFA
	int		identify(const char *str);

	friend ostream& operator<<(ostream &os, DFA *d);
};

#endif