regulartodfa.h

编译原理中的正则式匹配算法

int DfaStateCount=0;

class DFA
{
	public:
		void add(int S[],int N)
		{
			for(int i=0;i<N;i++) s[i]=S[i];
			n=N;
			DfaStateCount++;
		}
		int s[100];
		int n;
		int next0;
		int next1;
};

template <class Elem> class stack
{
	private:
		int size;
		int top;
		Elem *listArray;
	public:
		stack(int sz=100)
		{	size=sz;top=0;listArray=new Elem[sz];}
		~stack()
		{	delete []listArray;}
		bool push(const Elem& item)
		{
			if(top==size) return false;
			else {listArray[top++]=item;return true;}
		}
		bool pop(Elem& it)
		{
			if(top==0) return false;
			else {it=listArray[--top];return true;}
		}
		int length() const {return top;}
};

class RegularToDfa:public RegularToNfa
{
public:
	RegularToDfa();

    void order(int stateset[],int n);
	void closure(int& totlestate,int Start,
			 int stateset[],int& staten);
	void closure(int& totlestate,int move[],
			 int movei,int stateset[],int& staten);
	bool eq(DFA a,DFA b);
	void ToDfa(int &totlestate);
	void IsDfa(char *string);
	DFA  dfa[100];
private:
	int DfaBegin;
	int DfaEnd[10];
	int DfaEndi;

};

RegularToDfa::RegularToDfa()
{
 for (int i=0;i<50;i++)
     for (int j=0;j<50;j++)
	   DfaInput[i][j]=-1;
 DfaEndi=0;
}


void RegularToDfa::order(int stateset[],int statei)
{
	for(int i=1;i<statei;i++)
		for(int j=i;(j>0)&&(stateset[j]<stateset[j-1]);j--)
		{
			int temp=stateset[j];
			stateset[j]=stateset[j-1];
			stateset[j-1]=temp;
		}
}

/*void out(int s[],int &n)
{
	for(int i=0;i<n-1;i++)
		if(s[i]==s[i+1])
		{
			for(int j=i;j<n-1;j++) s[j]=s[j+1];
			n--;
			i--;
		}
}*/

void RegularToDfa::closure(int& totlestate,int move[],
			 int movei,int stateset[],int& staten)
{
	stack<int>stk;
	int i=0;
	for(int m=0;m<movei;m++)
	{
		stk.push(move[m]);
		stateset[i++]=move[m];
	}
	int a,mark=0;
	while(stk.length())
	{
		stk.pop(a);
		for(int j=0;j<totlestate;j++)
			if(DfaInput[a][j]==2)
			{
				mark=0;
				for(int k=0;k<i;k++) if(stateset[k]==j) mark=1;
				if(mark==0)
				{
					stateset[i++]=j;
					stk.push(j);
				}
			}
	}
	staten=i;
	order(stateset,i);
}

void RegularToDfa::closure(int& totlestate,int Start,
			 int stateset[],int& staten)
{
	stack<int> stk;
	int i=0;
	stk.push(Start);
	stateset[i++]=Start;
	int state,mark=0;
	while(stk.length ())
	{
		stk.pop(state);
		for(int j=0;j<totlestate;j++)
			if(DfaInput[state][j]==2)
			{
				mark=0;
				for(int k=0;k<i;k++) if(stateset[k]==j) mark=1;
				if(mark==0)
				{
					stateset[i++]=j;
					stk.push(j);
				}
			}
	}
	staten=i;
	order(stateset,i);
}


bool RegularToDfa::eq(DFA a,DFA b)
{
	if(a.n!=b.n) return false;
	else
	{
		for(int i=0;i<a.n;i++) if(a.s[i]!=b.s[i]) return false;
	}
	return true;
}
void RegularToDfa::ToDfa(int &totlestate)
{   
	int i,j;
	int Start=0;
	int stateset[100],staten,move[100],k,l,movei=0,sign;

	closure(totlestate,Start,stateset,staten);
	DFA dfatemp,dfatemp2;
	for(i=0;i<100;i++) dfa[i].next0=dfa[i].next1=-1;
	dfa[DfaStateCount].add(stateset,staten);
	stack<DFA> stk;
	stk.push(dfa[0]);
	while(stk.length())
	{
		stk.pop(dfatemp);
		for(i=0;i<2;i++)
		{
			for(j=0;j<dfatemp.n;j++)
				for(k=0;k<totlestate;k++)
					if(DfaInput[(dfatemp.s[j])][k]==i)
					{
						move[movei++]=k;
						//continue;
					}
			closure(totlestate,move,movei,stateset,staten);
			dfatemp2.add(stateset,staten);
			DfaStateCount--;
			for(l=0;!(eq(dfatemp2,dfa[l]))&&(l<DfaStateCount);l++);
			if(l==DfaStateCount) sign=0;
			else sign=1;
			if(sign==0)
			{
				dfa[DfaStateCount].add(stateset,staten);
				stk.push(dfa[DfaStateCount-1]);
			}
			for(int m=0;!(eq(dfatemp,dfa[m]));m++);
			if((i==0)&&(sign==1)) dfa[m].next0=l;
			else if((i==1)&&(sign==1)) dfa[m].next1=l;
			else if((i==0)&&(sign==0)) dfa[m].next0=DfaStateCount-1;
			else if((i==1)&&(sign==0)) dfa[m].next1=DfaStateCount-1;
			movei=0;		
		}
	}
	for(i=0;i<DfaStateCount;i++)
		if(dfa[i].n==0)
		{
			for(j=i;j<DfaStateCount-1;j++)
			{
				dfa[j].n=dfa[j+1].n;
				dfa[j].next0=dfa[j+1].next0;
				dfa[j].next1=dfa[j+1].next1;
				for(k=0;k<dfa[j].n;k++) dfa[j].s[k]=dfa[j+1].s[k];
			}
			for(k=0;k<DfaStateCount;k++)
			{
				if(dfa[k].next0==i) dfa[k].next0=-1;
				if(dfa[k].next1==i) dfa[k].next1=-1;
				if(dfa[k].next0>i) dfa[k].next0--;
				if(dfa[k].next1>i) dfa[k].next1--;
			}
			i--;
			DfaStateCount--;
		}
	///获得DFA开始状态	
	for(i=0;i<DfaStateCount;i++)
		for(j=0;j<dfa[i].n;j++)
			if(dfa[i].s[j]==Start) DfaBegin=i;
	for(i=0;i<DfaStateCount;i++)
		for(j=0;j<dfa[i].n;j++)
				if(dfa[i].s[j]==totlestate-1) DfaEnd[DfaEndi++]=i;
/*		cout<<"*************************************************************************"<<endl<<endl;
	cout<<"1.状态的集合："<<endl;
	for(i=0;i<DfaStateCount;i++)
	{
		cout<<"DFA状态"<<i<<":"<<"{ ";
		for(j=0;j<dfa[i].n;j++) cout<<dfa[i].s[j]<<" ";
		cout<<"}"<<endl;
	}
	cout<<endl;
	cout<<"2.输入符号集合："<<endl<<"{ 0 1 }"<<endl<<endl;
	cout<<"3.关系："<<endl;
	cout<<"状态\t"<<"输入符号\t"<<endl<<'\t'<<"0\t"<<"1\t"<<endl;
	for(i=0;i<DfaStateCount;i++)
	{
		cout<<i<<'\t';
		if(dfa[i].next0!=-1) cout<<dfa[i].next0<<'\t';
		else cout<<"无\t";
		if(dfa[i].next1!=-1) cout<<dfa[i].next1<<endl;
		else cout<<"无"<<endl;
	}
	cout<<endl;
	cout<<"4.开始状态："<<endl<<"{ ";
	for(i=0;i<DfaStateCount;i++)
		for(j=0;j<dfa[i].n;j++)
			if(dfa[i].s[j]==Start) cout<<i<<" ";
	cout<<"}"<<endl<<endl;
	cout<<"5.终止状态："<<endl<<"{ ";
	l=0;
	for(i=0;i<DfaStateCount;i++)
		for(j=0;j<dfa[i].n;j++)
			for(k=0;k<1;k++)
			{
				if(dfa[i].s[j]==totlestate-1) stateset[l++]=i;
			}
	order(stateset,l);

	for(i=0;i<l;i++) cout<<stateset[i]<<" ";
	cout<<"}"<<endl;*/
}

void RegularToDfa::IsDfa(char *string)
{
 int nextDfaState;
 nextDfaState=DfaBegin;
 for (unsigned i=0;i<strlen(string);i++)
 {
  if (string[i]=='0')
	  nextDfaState=dfa[nextDfaState].next0;
  else 
	  nextDfaState=dfa[nextDfaState].next1;
  for (int j=0;j<DfaEndi;j++)
	  if (nextDfaState==DfaEnd[j])
	  {
		  cout<<"the string is match the regular"<<endl;
		  return;
	  }
 }
 if (i>=strlen(string))
	 cout<<"no such a string can match the regular"<<endl;
}