z_nfa.cpp

智能的词法分析

#include<iostream>
#include<set>
#include<map> 
#include "Z_nfa.h"
using namespace std;
/************* 判断操作符的优先级的 ************/
inline int Z_nfa:: priority(const char& c)const 
{  
  switch(c)    
  { 
    case '(':
    case ')': return 0;
    case '|' : return 1; 
    case '.' : return 2;           
    case '*' : return 3;
    default : return -1; // 表示出错，没有这个运算符          
  }        
}

/*******输入正则表达式到buf,只能输入一个正则表达式*******/     
int Z_nfa::input()
{
  fp=fopen(EXPRESS_PATH,"r");
  if(fp==NULL)     
   return -1;                 
  else 
  { 
    char temp[1000]; 
   // cout<<temp.c_str()<<endl;
  
    fscanf(fp,"%s",temp);
     printf("%s\n",temp);
    int j=0; 
    for(int i=0;temp[i];i++)
    {  
     if(is_opnum(temp[i])) opnum.insert(temp[i]); //形成正则表达式中的字母表 
         
       buf[j++]=temp[i]; 
       if(is_opnum(temp[i])&&is_opnum(temp[i+1]))       
          buf[j++]='.';        
                                                                    
       if(is_opnum(temp[i])&&temp[i+1]=='(')
        buf[j++]='.';
        
      if(temp[i]=='*' && ( temp[i+1]=='('||is_opnum(temp[i+1]) ) )
       {
         buf[j++]='.';                                          
       } 
       
      if(temp[i]==')'&&temp[i+1]=='(')
      buf[j++]='.';
                    
    }
    buf[j]=')';
    buf[++j]='\0';  
                  
  } 
  fclose(fp); 
  return 0;  
}

/**********看一个字符是不是操作数***********/ 
 bool inline Z_nfa::is_opnum(const char& a)const 
 {
   if((a<='z'&&a>='a')||(a<='9'&&a>='0')||(a<='Z'&&a>='A')||a=='_'||a=='<'
   ||a=='>'||a=='='||a=='!')
    return true;
   else  
    return   false; 
 } 
 
 /*********专门处理星闭包**************/ 
 int Z_nfa::caculate_xin(int begin,int end)
 {
    // 产生2个新状态，和 4条边      
       NFA.insert ( pair<int, wedge* >(++state_num,0) );
        int  state1=state_num; 
      NFA.insert ( pair<int, wedge* >(++state_num,0) );
       int state2=state_num;     
       wedge* s1=new wedge;
       s1->next=NFA[state1]; 
       s1->c='$';
       s1->state=begin;
       NFA[state1]=s1; 
      // 
       s1=new wedge;
       s1->next=NFA[state1]; 
       s1->c='$';
       s1->state=state2;
       NFA[state1]=s1;
       //
       s1=new wedge;
       s1->state=begin;
       s1->c='$';
       s1->next=NFA[end];
       NFA[end]=s1;
       
       //
       s1=new wedge;
       s1->state=state2;
       s1->c='$';
       s1->next=NFA[end];
       NFA[end]=s1;           
      return 0;    
 }
 
 /***********专门处理连接运算的****************/ 
 int Z_nfa::caculate_link(int begin1,int end1,int begin2,int end2)
 {  
       //连接状态数没有增加，就只是增加了一条边           
 
        wedge* temp=new wedge;        
        temp->state=begin2;
        temp->c='$';
        temp->next=NFA[end1];
        NFA[end1]=temp;               
        
        return 0;
  } 
  
   /***********专门处理或运算的****************/ 
 int Z_nfa::caculate_or(int begin1,int end1,int begin2,int end2)  
 {
        NFA.insert ( pair<int, wedge* >(++state_num,0) );
        int  state1=state_num; 
        NFA.insert ( pair<int, wedge* >(++state_num,0) );
        int state2=state_num;         
        //
        wedge* s1=new wedge;
        s1->state=begin1;
        s1->next=NFA[state1];
        s1->c='$';
        NFA[state1]=s1;
        // 
          s1=new wedge;
          s1->state=begin2;
          s1->c='$';
          s1->next=NFA[state1];
          NFA[state1]=s1;
          // 
           s1=new wedge;
           s1->state=state2;
           s1->c='$';
           s1->next=NFA[end1];
           NFA[end1]=s1;
           // 
           s1=new wedge;
           s1->c='$';  
           s1->state=state2; 
           s1->next=NFA[end2];
           NFA[end2]=s1;    
               
   return 0;   
 }
 
 /************专门用来算单个字母的************/ 
 int Z_nfa::caculate_char(const char& c)
 {
        NFA.insert ( pair<int, wedge* >(++state_num,0) );
        int  state1=state_num; 
        NFA.insert ( pair<int, wedge* >(++state_num,0) );
        int state2=state_num; 
        wedge* s1=new wedge;
        s1->state=state2;
        s1->c= c;
        s1->next=NFA[state1];
        NFA[state1]=s1;           
     return 0; 
 }
 
 /*******表达式到NFA的转化***********/ 
int Z_nfa::expression_NFA()
{
   for(int i=0;buf[i]!='\0';i++)
   {
     if(is_opnum(buf[i]))
      {
        
        caculate_char(buf[i]);
        start_end.push(state_num);
        start_end.push(state_num-1);
      }                       
     else 
      {
               
         while(op.size()>0&&priority(buf[i])<=priority(op.top()))
         { 
            if(buf[i]=='(')   //是左括号就直接退出  
               break;               
               
           char c=op.top();op.pop();
           
            if(c=='('&&buf[i]==')')
               break;
                                                                            
            switch(c)
            {
               case '*':
               {
                 int begin=start_end.top(); start_end.pop();
                 int end=start_end.top(); start_end.pop();   
                 caculate_xin(begin,end);
                 start_end.push(state_num);
                 start_end.push(state_num-1);
                 break;    
               }
               case '.':
               {
                  int begin2=start_end.top(); start_end.pop();
                  int end2=start_end.top(); start_end.pop();       
                  int begin1=start_end.top(); start_end.pop();
                  int end1=start_end.top(); start_end.pop();
                 caculate_link(begin1,end1, begin2, end2);   
                  start_end.push(end2);
                  start_end.push(begin1);
                  break;  
               } 
               case '|':
               {
                  int begin2=start_end.top(); start_end.pop();
                  int end2=start_end.top(); start_end.pop();       
                  int begin1=start_end.top(); start_end.pop();
                  int end1=start_end.top(); start_end.pop();
                  caculate_or(begin1,end1, begin2, end2);
                  start_end.push(state_num);
                  start_end.push(state_num-1);
                  break;     
               }  
               default:
                return -1;     
            }                                                           
         }         
        if(buf[i]!=')')
        op.push(buf[i]); 
          
      }                                      
   }    
  if(start_end.size()>2||op.size()>0)  
   return -1;
  else  
  { 
    NFAstart=start_end.top(); start_end.pop();
    NFAend=start_end.top(); start_end.pop(); 
  } 
  return 0; 
} 

/************NFA的释放***************/ 
int Z_nfa::freeNFA()
{
  map<int , wedge* >:: iterator it;
  wedge* p;
  for(it=NFA.begin();it!=NFA.end();it++)
  {     
      for(p=it->second; p!=NULL ; p = it->second)
      { 
        it->second = p->next; 
        delete p;                                   
      }
                                                                                 
  }  
  return 0;  
} 

/**********以文件形式输出NFA****************/
int Z_nfa::display_NFA()
{
  FILE* fp_NFA = fopen("NFA.txt","w");    
  map<int , wedge* >:: iterator it;