regulartonfa.cpp

编译原理---正则表达式到DFA的演示程序

#include "RegularToNFA.h"

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
void Stack::Push(stArc x)
{
	ListNode *TempNode;
	TempNode=new ListNode;
	TempNode->arc=x;
	TempNode->next=top;
	top=TempNode;
}//Push

stArc Stack:: Pop(void)
{
stArc y={0,0,0};
stArc x;
	ListNode *TempNode;
	if(top==NULL)               //栈
    return y ;
	else
	{
		TempNode=top;
		top=top->next;
		x=TempNode->arc;
		delete TempNode;
		return x;
		
	}
}//pop

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
int  IsAlphabet(char a)
{  
	if(('0'<=a && a<='9') || ('a'<=a && a<='z') || ('A'<=a && a<='Z'))
	{ 
		for(int i=1;i<=CharQuantity;i++)
		{
		if(AllChar[i]==a)
	        i=CharQuantity+1;
		}
	 if(i==CharQuantity+1)
	 {
	  AllChar[CharQuantity]=a;
	  CharQuantity++;         //接收字符个数，e除外 */
	 }

		
	 return 1;}
   else return 0;
}

char GetNextCh(int size)
{
	if(linepos<size)	
	   return string[linepos++];
	else return NULL;
}
/////////////////////////////////////////////////////////////////////
void Isnull(int ftn,int x ,int y,char z)
			
{  	
	Node *p,*p2; 
	p2=p=FirstTable[ftn];
	 while(p!=NULL)
	 {	 p2=p;
		 p=p->Next;
	 }
		Node* temp=new Node;
		temp->NeighborNode=x;
		temp->ConvertChar=z;
		temp->Next=NULL;
		temp->NodeState=y;
		p=temp;
		if(NULL==FirstTable[ftn])
			FirstTable[ftn]=p;
		else p2->Next=p;
 }

void RegularToNFA()
{
  int k=1,T=1,ST0=1,q=0;int ST1;
  char a;char sym; Stack sk;
  stArc s,arc;

  int size;
	size=strlen(string);
  a=GetNextCh(size);
  while(a!='#')
  {
     if(IsAlphabet(a))
	 {
		 sym=GetNextCh(size);
	 if (sym=='*')
	 {   Isnull(T,k+1,0,'@');
	 
		 Isnull(k+1,k+1,0,a);
		  
		 Isnull(k+1,k+2,0,'@') ;
		  
//		    cout<<"from:"<<T<<"-->"<<k+1<<"∈"<<endl;
//	        cout<<"from:"<<k+1<<"-->"<<k+1<<a<<endl; 
//	       cout<<"from:"<<k+1<<"-->"<<k+2<<"∈"<<endl; 
	  
    k+=2; T=k;
   a=GetNextCh(size);
        }
		else
		{    
			Isnull(T,k+1,0,a);
//			 cout<<"from:"<<T<<"-->"<<k+1<<a<<endl; 
	     
		   k=k+1;T=k;
		   a=sym;
         }
	 }
    switch(a)
	{ 
	   case '|':
	     {
			 if(q==0)
		    {
			 ST1=T;T=ST0;q=1;
			 }
			else
			{   Isnull(T,ST1,0,'@') ;
//				cout<<"from:"<<T<<"-->"<<ST1<<"∈"<<endl; 
				
			T=ST0;
			
			}
         a=GetNextCh(size);
         break;
		 }//case
		case'(':
		   {
			arc.ST0=ST0;arc.ST1=ST1;arc.q=q;sk.Push(arc);
			Isnull(T,k+1,0,'@') ;
//			cout<<"from:"<<T<<"-->"<<k+1<<"∈"<<endl; 
		   
			k=k+1;T=k;
			ST0=k;q=0;
			a=GetNextCh(size);  
			break;
			}//
			
		case ')':
		  {
		    if(q=1){Isnull(T,ST1,0,'@') ;
//				    cout<<"from:"<<T<<"-->"<<ST1<<"∈"<<endl; 
			         
				   T=ST1;
				   }
				   sym=GetNextCh(size);
			if(sym!='*')a=sym;
			else
			{    Isnull(T,ST0,0,'@') ;
			     Isnull(ST0,k+1,0,'@') ; 
//				cout<<"from:"<<T<<"-->"<<ST0<<"∈"<<endl; 
//			  cout<<"from:"<<ST0<<"-->"<<k+1<<"∈"<<endl; 
			  
			   k=k+1;T=k;
			   a=GetNextCh(size);
			   }
			 s=sk.Pop();
			ST0=s.ST0;   ST1=s.ST1;q=s.q;  		
			}//case
         }//switch
  }//while

      if(q==1)
	  {   Isnull(T,ST1,0,'@') ;
//		  cout<<"from:"<<T<<"-->"<<ST1<<"∈"<<endl; 
		 
		 T=ST1;
		 }
	  CharQuantity=CharQuantity-1;//接收字符个数，e除外 
	  FirstNodeQuantity=k;//邻接表行数
	  Node* L=new Node;
	  L->NeighborNode=1;
	  L->NodeState=-1;
	  L->ConvertChar='@';
	  L->Next=NULL;
	  FirstTable[0]=L;//	 FirstTable[L] 为始点
	  
	Node *pc;            //查终态结点
	for(int i=1;i<=FirstNodeQuantity;i++)
	{
		pc=FirstTable[i];	
		while(pc!=NULL)
		{   if (pc->NeighborNode==T)
			pc->NodeState=1;
			pc=pc->Next;
		}
	}

	 // cout<<CharQuantity<<endl;
  }//end

//从正则到NFA完********************************************************************