regulartonfa.h

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

struct Relation
{
 int CurrentState;
 int NextState;
 char TransitionElement;
};

struct TokenState
{
 int BeginState;
 int EndState;
 int preposition;
};

class RegularToNfa
{
public:
	int IsTransitionElement(char s);
	void NFADiagram(int position,int CurrentState,
				int NextState,char TransitionElement);
	int TokenDealing(int position,TokenState *token,int *Rtoken);//双目运算
    void ToNFA(int &max);
	void ToReversePolish(char *statement);
	int DfaInput[50][50];
private:
	Relation relation[25];
	char *string;//用来存放逆波兰式
};


int RegularToNfa::IsTransitionElement(char s)
{
 if (s=='0'||s=='1'||s=='$')
	 return 1;
 else return 0;
}

void RegularToNfa::NFADiagram(int position,int CurrentState,
				int NextState,char TransitionElement)
{
 relation[position].CurrentState=CurrentState;
 relation[position].NextState=NextState;
 relation[position].TransitionElement=TransitionElement;
 //cout<<"(       "<<CurrentState<<"      )"<<TransitionElement<<endl;
}

int RegularToNfa::TokenDealing(int position,TokenState *token,int *Rtoken)//双目运算
{
 
 
 if (IsTransitionElement(string[position])
	 &&IsTransitionElement(string[position-1]))
	 return 0;
 else  if (IsTransitionElement(string[position])
	       &&!IsTransitionElement(string[position-1]))
	 return 1;
 else 
 {
	 int firsttoken=token[Rtoken[position]].preposition;
	 if(IsTransitionElement(string[firsttoken-1]))
		 return 2;
	 else return 3;
 }
}

void RegularToNfa::ToNFA(int &max)
{
 TokenState token[20];
 int Rtoken[20];
 int tokeni=1,relationi=0;
 int secondtoken;
 bool start=false;
 token[0].BeginState=0;
 token[0].EndState=0;
 for (unsigned i=0;i<strlen(string);i++)
 {
  if (string[i]=='*' || string[i]=='|' || string[i]=='$')
	  start=true;
 }
 for (i=0;i<strlen(string);i++)
 {
  if (string[i]=='*')
  {
   Rtoken[i]=tokeni;
   if (IsTransitionElement(string[i-1]))
   {
	  token[tokeni].BeginState=token[tokeni-1].EndState+1;
	  token[tokeni].EndState=token[tokeni].BeginState + 1;
	  token[tokeni].preposition = i-1;
	  NFADiagram(relationi++,token[tokeni].BeginState,
                token[tokeni].EndState ,string[i-1]);
	  
     //cout<<"heloo       "<<Rtoken[i]<<endl;
   }
   else 
   {
    token[tokeni].BeginState=token[tokeni-1].BeginState;
	token[tokeni].EndState=token[tokeni-1].EndState;
	token[tokeni].preposition=token[tokeni-1].preposition;
   }
    
    NFADiagram(relationi++,token[tokeni].EndState,
              token[tokeni].BeginState , '$');
    NFADiagram(relationi++,token[tokeni].BeginState-1,
              token[tokeni].EndState + 1 , '$');
    NFADiagram(relationi++,token[tokeni].BeginState-1,
              token[tokeni].BeginState , '$');
    NFADiagram(relationi++,token[tokeni].EndState,
              token[tokeni].EndState+1 , '$');
   token[tokeni].BeginState = token[tokeni].BeginState -1 ;
   token[tokeni].EndState=token[tokeni].EndState + 1;
   tokeni++;
  }
  else if(string[i]=='+')
  {
   Rtoken[i]=tokeni;
   
   switch(TokenDealing(i-1,token,Rtoken))
   {
    case 0: token[tokeni].BeginState=token[tokeni-1].EndState+1;
			token[tokeni].EndState=token[tokeni].BeginState + 2;
			token[tokeni].preposition=i-2;
			
			NFADiagram(relationi++,token[tokeni].BeginState,
                       token[tokeni].BeginState+1 , string[i-2]);
         	NFADiagram(relationi++,token[tokeni].BeginState+1,
                       token[tokeni].EndState,string[i-1]);
			break;
	case 1: token[tokeni].BeginState=token[tokeni-1].EndState;
		    token[tokeni].EndState=token[tokeni].BeginState + 1;
			token[tokeni].preposition=token[tokeni-1].preposition;
			
			NFADiagram(relationi++,token[tokeni].BeginState,
                       token[tokeni].EndState , string[i-1]);
			token[tokeni].BeginState=token[tokeni-1].BeginState;
			break;
    case 2: 
		    token[tokeni].BeginState=token[tokeni-1].BeginState-1;
		    token[tokeni].EndState=token[tokeni-1].BeginState;			
			token[tokeni].preposition=token[tokeni-1].preposition-1;

			NFADiagram(relationi++,token[tokeni].BeginState,
                       token[tokeni].EndState , string[token[tokeni-1].preposition-1]);

			token[tokeni].EndState=token[tokeni-1].EndState;
			break;
	case 3: secondtoken=token[Rtoken[i-1]].preposition-1;
		    
		    token[tokeni].BeginState=token[Rtoken[secondtoken]].EndState;
			token[tokeni].EndState=token[tokeni-1].BeginState;
			token[tokeni].preposition=token[secondtoken].preposition;
            
		    NFADiagram(relationi++,token[tokeni].BeginState,
				       token[tokeni].EndState , '$');
			token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState;
			token[tokeni].EndState=token[tokeni-1].EndState;
			break;
   }
   tokeni++;
  }
  else if(string[i]=='|')
  {
   Rtoken[i]=tokeni;
   switch(TokenDealing(i-1,token,Rtoken))
   {
    case 0: token[tokeni].BeginState=token[tokeni-1].EndState+1;
	    	token[tokeni].EndState=token[tokeni].BeginState + 5;
			token[tokeni].preposition=i-2;
			NFADiagram(relationi++,token[tokeni].BeginState,
                       token[tokeni].BeginState+1 , '$');
         	NFADiagram(relationi++,token[tokeni].BeginState+1,
                       token[tokeni].BeginState+2 , string[i-2]);
			NFADiagram(relationi++,token[tokeni].BeginState,
                       token[tokeni].BeginState+3 , '$');
			NFADiagram(relationi++,token[tokeni].BeginState+3,
                       token[tokeni].BeginState+4 , string[i-1]);
			NFADiagram(relationi++,token[tokeni].BeginState+2,
                       token[tokeni].EndState , '$');
			NFADiagram(relationi++,token[tokeni].BeginState+4,
                       token[tokeni].EndState , '$');
			break;
	case 1: token[tokeni].BeginState=token[tokeni-1].BeginState-1;
		    token[tokeni].EndState=token[tokeni-1].EndState+3;
			token[tokeni].preposition=token[tokeni-1].preposition;
			NFADiagram(relationi++,token[tokeni].BeginState,
                       token[tokeni].BeginState+1 , '$');
			NFADiagram(relationi++,token[tokeni].BeginState,
                       token[tokeni].EndState+1 , '$');
			NFADiagram(relationi++,token[tokeni].EndState+1,
                       token[tokeni].EndState+2 , string[i-1]);
			NFADiagram(relationi++,token[tokeni].EndState,
                       token[tokeni].EndState+3 , '$');
			NFADiagram(relationi++,token[tokeni].EndState+2,
                       token[tokeni].EndState+3 , '$');
			break;
	case 2:token[tokeni].BeginState=token[tokeni-1].BeginState-1;
		   token[tokeni].EndState=token[tokeni-1].EndState+3;
           token[tokeni].preposition=token[Rtoken[i-1]].preposition-1; 
		   NFADiagram(relationi++,token[tokeni].BeginState,
                      token[tokeni].BeginState+1 , '$');
		   NFADiagram(relationi++,token[tokeni].BeginState,
                      token[tokeni].EndState-2 , '$');
		   NFADiagram(relationi++,token[tokeni].EndState-2,
                      token[tokeni].EndState-1 , string[token[Rtoken[i-1]].preposition-1]);
		   NFADiagram(relationi++,token[tokeni].EndState-1,
                      token[tokeni].EndState , '$');
		   NFADiagram(relationi++,token[tokeni].EndState-3,
                      token[tokeni].EndState , '$');
		   break;
	case 3:token[tokeni].EndState=token[tokeni-1].EndState+1;
		   secondtoken=token[Rtoken[i-1]].preposition-1;

		    token[tokeni].BeginState=token[Rtoken[secondtoken]].BeginState-1;
		    NFADiagram(relationi++,token[tokeni].BeginState,
                      token[Rtoken[secondtoken]].BeginState, '$');
			NFADiagram(relationi++,token[tokeni].BeginState,
                      token[tokeni-1].BeginState , '$');
			NFADiagram(relationi++,token[tokeni-1].EndState,
                      token[tokeni].EndState , '$');
			NFADiagram(relationi++,token[Rtoken[secondtoken]].EndState,
                      token[tokeni].EndState , '$');

		   break;
		   
   }
   tokeni++;
  }
 }
 int compare=10000;
 for (int j=0;j<relationi;j++)
 {
  if(relation[j].CurrentState<compare)
	  compare=relation[j].CurrentState;
  if (relation[j].NextState>max)
	  max=relation[j].NextState;
 }
 for (j=0;j<relationi;j++)
 {
   relation[j].CurrentState -= compare;
   relation[j].NextState -= compare;
 }
 max -= compare;
 /*
 cout<<"The Begin State is : 0"<<endl
	 <<"The End   State is : "<<max<<endl;*/
 int n;
 for (n=0;n<relationi;n++)
 {
  int current=relation[n].CurrentState;
  int next  = relation[n].NextState;
  if (relation[n].TransitionElement=='$')
  DfaInput[current][next]=2; 
  else if(relation[n].TransitionElement=='0')
	  DfaInput[current][next]=0;
  else DfaInput[current][next]=1;
 } 
 /*if (start)
 cout<<"The Set of TransitionElement is : 0,   1,   $"<<endl;
 else 
 cout<<"The Set of TransitionElement is : 0,   1"<<endl;
 cout<<"The Set of State is from 0 to "<<max<<" , "<<"in all "<<max+1<<" states"<<endl<<endl;*/
 /*for (j=0;j<relationi;j++)
 cout<<"From State: "<<relation[j].CurrentState<<"          "
     <<"To State  "<<relation[j].NextState<<"         "
	 <<"TransitionElement is :  "<<relation[j].TransitionElement<<endl;*/
}

void RegularToNfa::ToReversePolish(char *statement)
{
  int Si=0,top=0,RPSi=0;
  char stack[15];
  while(statement[Si]!='\0')
  {
   if (IsTransitionElement(statement[Si]))
   {
	   if ((statement[Si-1]=='0' || statement[Si-1]=='1' 
		  || statement[Si-1] ==')' || statement[Si-1]=='$'
		  || statement[Si-1] =='*') && Si-1>=0)
	   {
        top--;
    	while((stack[top]=='+' || stack[top]=='*') && top>=0)
		{
         string[RPSi]=stack[top];
         top--;
         RPSi++;
		}
	    top++;
		stack[top]='+';
		top++;
	   }
	   string[RPSi]=statement[Si];
	   RPSi++;
	   Si++;
   }
   else if (statement[Si]=='(')
   {
	   if ((statement[Si-1]=='0' || statement[Si-1]==')' 
		  || statement[Si-1]=='1'||statement[Si-1]=='$'
		  || statement[Si-1] =='*') && Si-1>=0)
	   {
        top--;
    	while((stack[top]=='+' || stack[top]=='*') && top>=0)
		{
         string[RPSi]=stack[top];
         top--;
         RPSi++;
		}
	    top++;
		stack[top]='+';
		top++;
	   }
	   stack[top]=statement[Si];
       top++;
	   Si++;
   }
   else if (statement[Si]==')')
   {
    top--;
	while (stack[top]!='(')
	{
      string[RPSi]=stack[top];
      top--;
      RPSi++;
	}
	Si++;
   }
   else if (statement[Si]=='*')
   {    
	top--;
	while(stack[top]=='*' && top>=0)
	{
      string[RPSi]=stack[top];
      top--;
      RPSi++;
	}
	top++;
	stack[top]=statement[Si];
	Si++;
	top++;
   }
   else if (statement[Si]=='|')
   {
    top--;
	while((stack[top]=='*' || stack[top]== '+' || stack[top]== '|') && top>=0)
	{
      string[RPSi]=stack[top];
      top--;
      RPSi++;
	}
	top++;
	stack[top]=statement[Si];
	Si++;
	top++;
   }
  }
  top--;
  while(top>=0)
  {
   string[RPSi]=stack[top];
   top--;
   RPSi++;
  }
  string[RPSi]='\0';
}