dfa.cpp

输入一个正则表达式

#include <memory.h>
#include "DFA.h"

// Constructor
DFA::DFA(NFA *n, int *_rawMap)
{
	alphaSize = n->alphaSize;
	rawMap = _rawMap;
	STTSize = 0;
	// skip state 0, for 0 is  used for dead state
	newItem();
	buildDFA(n);
}
// Destructor
DFA::~DFA()
{
	destroySTT();
}
// Destroy STT
void DFA::destroySTT()
{
	int i;

	for(i = 0;i < STTSize;i ++)
	{
		if(STT[i]) delete [](STT[i]);
	}
}
ostream& operator<<(ostream &os, DFA *d)
{
	int	i, j;

	for(i = 0;i < d->STTSize;i ++)
	{
		if(d->STT[i])
		{
			os << 'q' << i << "\t";
			for(j = 0;j < d->alphaSize;j ++)
			{
				os << 'q' << d->STT[i][j] << " ";
			}
			os << endl;
		}
	}
	os << "Q = q" << d->Q << endl
		<< "F = " << d->F << endl;

	return os;
}
// Create a new item, return the index of the new item
int DFA::newItem()
{
	StateItem arrStateSet = new int[alphaSize];

    memset(arrStateSet, 0, sizeof(int) * alphaSize);
	STT.push_back(arrStateSet);
	return STTSize ++;
}
// add stateSet ss into STT[i][j], using setVec
void DFA::addItem(StateSet &ss, int i, int j, vector <StateSet> &setVec, StateSet &nfaF)
{
	int k;	
	// find if there exists ss in setVec, otherwise k point to end()
	for(k = 1;k < STTSize;k ++)
	{
		if(setVec[k] == ss) break;
	}
	if(k == STTSize) // not found
	{
		k = newItem();
		setVec.push_back(ss);
		if(intersect(nfaF, ss)) F.insert(k);
	}
	STT[i][j] = k;
}
// build a DFA from an NFA
void DFA::buildDFA(NFA *n)
{
	// temporary set vector
	vector <StateSet>	setVec(1);
	NFA::StateItem		nfaSI;
	int i, j;

	newItem();
	setVec.push_back(n->Q);
	if(intersect(n->F, n->Q)) F.insert(1);

	for(i = 1;i < STTSize;i ++)
	{
		nfaSI = n->getConnect(setVec[i]);
		for(j = 0;j < alphaSize;j ++)
		{
			addItem(nfaSI[j], i, j, setVec, n->F);
		}
		delete []nfaSI;
	}
	Q = 1;
	minimize();
}
// if State[i] and State[j] is the same state
int DFA::isSameState(int i, int j)
{
	int	con1, con2, con3, k;

	con1 = con2 = con3 = 1;
	for(k = 0;k < alphaSize;k ++)
	{
		if(con1 && (STT[i][k] != STT[j][k])) {
			con1 = 0;
		}
		if(con2 &&(STT[i][k] != i || STT[j][k] != j)) {
			con2 = 0;
		}
		if(con3 && (STT[i][k] != j || STT[j][k] != i)) {
			con3 = 0;
		}
	}
	return(con1 || con2 || con3);
}
// merge State[b] into state[a], and delete [b], Rubish code
void DFA::mergeState(int a, int b)
{
	StateIt	it, it2;
	int	i, j, t;
	
	for(i = 0;i < STTSize;i ++)
	{
		for(j = 0;j < alphaSize;j ++)
		{
			if(i >= b && i < STTSize - 1) STT[i][j] = STT[i + 1][j];
			if(STT[i][j] == b) STT[i][j] = a;
			else if(STT[i][j] > b) --STT[i][j];
		}
	}
	--STTSize;
	if(a > b) --a;
	if(Q == b) Q = a;
	for(it = F.begin();it != F.end();)
	{
		it2 = it ++;
		t = *it2;
		if(t == b) {
			F.erase(it2);
		}else if(*it2 > b) {
			F.erase(it2);
			F.insert(t - 1);
		}
	}
}
// minimize the DFA
void DFA::minimize()
{
	int	i, j, iF, jF;
	
	for(i = 0;i < STTSize - 1;i ++)
	{
		for(j = i + 1;j < STTSize;)
		{
			iF = (F.find(i) != F.end());
			jF = (F.find(j) != F.end());
			if(iF == jF && isSameState(i, j))
			{
				mergeState(i, j);
			}
			else
			{
				++j;
			}
		}
	}
}
// identify if the string is the language of this DFA
int DFA::identify(const char *str)
{
	int i = Q, c;

	while(i != 0 && *str)
	{
		if((c = rawMap[*str++ - '0']) == -1) return 0;
		i = STT[i][c];
	}
	return(F.find(i) != F.end());
}