nfa.cpp

输入一个正则表达式

#include "NFA.h"

//////////////////////////////////////////////////////////////////////////
//	set operations
//
// test if set A intersect set B
int intersect(StateSet &A, StateSet &B)
{
	StateIt	it;
	for(it = B.begin();it != B.end();it ++)	
	{
		if(A.find(*it) != A.end()) return 1;
	}
	return 0;
}
// Do a complement to A
void complement(StateSet &A, int size)
{
	int		j;

	for(j = 0;j < size;j ++)
	{
		if(A.find(j) != A.end())	// exist element j
		{
			A.erase(j);
		}
		else						// not exist
		{
			A.insert(j);
		}
	}
}
//////////////////////////////////////////////////////////////////////////
// NFA
// Constructor
NFA::NFA(int _alphaSize)
{
	alphaSize = _alphaSize;
	STTSize = 0;
}
// Destructor
NFA::~NFA()
{
	destroySTT();
}
// Destroy STT
void NFA::destroySTT()
{
	int i;

	for(i = 0;i < STTSize;i ++)
	{
		if(STT[i]) delete [](STT[i]);
	}
}
// Out state set
ostream& operator<<(ostream &os, StateSet &ss)
{
	StateIt	it;

	os << "{";
	for(it = ss.begin();it != ss.end();it ++)
	{
		os << 'q' << *it << " ";
	}
	os << "}";
	return os;
}

// Out NFA State Transition Table(STT)
ostream& operator<<(ostream &os, NFA *n)
{
	int	i, j;
	
	for(i = 0;i < n->STTSize;i ++)
	{
		if(n->STT[i])
		{
			os << 'q' << i << "\t";
			for(j = 0;j < n->alphaSize;j ++)
			{
				os << n->STT[i][j];
			}
			os << endl;
		}
	}
	os << "Q = " << n->Q << endl
	   << "F = " << n->F << endl;

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

	STT.push_back(arrStateSet);
	return STTSize ++;
}
// add a new item from another one, return the index of the new item
int NFA::addItem(StateItem si)
{
	STT.push_back(si);
	return STTSize ++;
}
// add a fix number to each element of the set
void NFA::addSet(StateSet &ss, int num)
{
	StateIt it;

	for(it = ss.begin();it != ss.end();it ++)
	{
		*it += num;
	}
}

// merge a NFA connected to this, and modify the state sequence
void NFA::merge(NFA *n)
{
	int	i, j, newStart = STTSize;

	for(i = 0;i < n->STTSize;i ++)
	{
		if(n->STT[i])
		{			
			for(j = 0;j < n->alphaSize;j ++)
			{
				addSet(n->STT[i][j], newStart);
			}
			addItem(n->STT[i]);
			n->STT[i] = NULL;
		}
	}
	addSet(n->Q, newStart);
	addSet(n->F, newStart);
}
// get Item connected to ss
NFA::StateItem NFA::getConnect(StateSet &ss)
{
	int			j;
	StateIt		it;
	StateItem	result = new StateSet[alphaSize];

	for(it = ss.begin();it != ss.end();it ++)
	{
		for(j = 0;j < alphaSize;j ++)
		{
			StateSet &tss = STT[*it][j];
			result[j].insert(tss.begin(), tss.end());
		}
	}
	return result;
}
// add Item si to all elements in ss
void NFA::addConnect(StateSet &ss, StateItem si)
{
	int			j;
	StateIt		it;

	for(it = ss.begin();it != ss.end();it ++)
	{
		for(j = 0;j < alphaSize;j ++)
		{
			STT[*it][j].insert(si[j].begin(), si[j].end());
		}
	}
}
// copy the connection of src to dest
void NFA::copyConnection(StateSet &dest, StateSet &src)
{
	StateItem	si;

	si = getConnect(src);
	addConnect(dest, si);
	delete []si;
}
// Make a dead state item that all connection point to itself
int NFA::newDeadItem()
{
	int j, k = newItem();

	for(j = 0;j < alphaSize;j ++)
	{
		STT[k][j].insert(k);
	}
	return k;
}
// Make a dead state that all empty sets are connected to
int NFA::makeDeadState()
{
	int	k = -1, i, j;

	for(i = 0;i < STTSize;i ++)
	{
		for(j = 0;j < alphaSize;j ++)
		{
			if(STT[i][j].empty()) 
			{
				if(k == -1) {
					k = newDeadItem();
				}
				STT[i][j].insert(k);
			}
		}
	}
	return k;
}

// basic NFA of regular expression
void NFA::emptyStr()
{
	int i = newItem();

	Q.insert(i);
	F.insert(i);
}
void NFA::emptySet()
{
	int i = newItem(), j = newItem();

	Q.insert(i);
	F.insert(j);
}
void NFA::alphabet(int c)
{
	int i = newItem(), j = newItem();

	Q.insert(i);
	F.insert(j);
	STT[i][c].insert(j);
}

// NFA operation
void NFA::unionSet(NFA *n)
{
	merge(n);
	F.insert(n->F.begin(), n->F.end());
	Q.insert(n->Q.begin(), n->Q.end());
}
void NFA::intersectionSet(NFA *n)
{
	// Not support yet
}
void NFA::join(NFA *n)
{
	merge(n);
	copyConnection(F, n->Q);
	if(intersect(n->F, n->Q))
	{
		F.insert(n->F.begin(), n->F.end());
	}
	else
	{
		F = n->F;
	}
}
void NFA::complementSet()
{
	makeDeadState();
	complement(F, STTSize);
}
void NFA::closure()
{
	int			i;
	StateSet	ss;

	copyConnection(F, Q);
	
	i = newItem();
	ss.insert(i);
	copyConnection(ss, Q);

	Q = ss;
	F.insert(i);
}