z_nfa.cpp

智能的词法分析

  wedge* p; 
  fprintf(fp_NFA,"%d %d\n",NFAstart,NFAend);
  //cout<<NFAstart<<" "<<NFAend<<endl;
  for(it=NFA.begin();it!=NFA.end();it++)
  {  
  //  cout<<it->first<<" ";
    fprintf(fp_NFA,"%d ",it->first); 
     for(p=it->second;p!=NULL;p=p->next)
     {
  //     cout<<p->c<<" "<<p->state<<" ";
       fprintf(fp_NFA,"%c %d ",p->c,p->state);                                      
     }  
 //    cout<<endl;                                    
    fprintf(fp_NFA,"\n");                                      
  }
  fclose(fp_NFA); 
  return 0;  
} 

/***********栈清空************/
int Z_nfa::clear_stack()
{
  while(!op.empty())
  {
    op.pop();                                  
  }    
  while(!start_end.empty())
  {
     start_end.pop();                         
  }  
  return 0; 
} 

/********$的闭包**************/
int Z_nfa::$_closure(set<int >& T )
{
  set<int>::iterator it;
  map<int, wedge* >::iterator m_iter;
  wedge* p; 
  stack < int >newstate;  
  for(it=T.begin();it!=T.end();it++)//把T中的元素全部入栈 
  {
     newstate.push(*it);                                                                     
  }     
  while(!newstate.empty())
  {
     int state=newstate.top(); newstate.pop();
     for(p=NFA[state]; p!=NULL; p=p->next )    
     { 
       //邻接表中遍历找到 $ 这条边且这个状态没有在集合出现过  
        if(p->c=='$'&&T.find(p->state)==T.end())                     
        {  // 则同时加入栈和 集合中 
           newstate.push(p->state);
           T.insert(p->state); 
        }              
                                   
     }                  
  }
  return 0;      
}

/*********状态T经过a得到的集合*************/ 
 int Z_nfa::move(set<int > &T,const char& a)
 { 
   int temp[BSIZE]={0};
   int n=0; 
   set<int >::iterator it=T.begin();
   for(;it!=T.end(); it++)
   {  
   
      for(wedge* p=NFA [*it] ;p!=NULL; p=p->next )                    
      {   
         if(p->c==a)
         temp[n++]=p->state;           
      }                   
   }    
   T.clear();
   for(int i=0;i<n;i++)
   {
      T.insert(temp[i]);  
   }   
   return 0;     
 }
  
/********NFA转为DFA**********/ 
int Z_nfa::NFA_DFA() 
{
   set<int > T;
   T.insert(NFAstart);      
   $_closure( T );
   DFAstart=T;
   DFAsumset.insert(DFAstart);
   stack<set<int> > newstate;
   newstate.push(DFAstart); 
   while(!newstate.empty())
   {
     set<int> pre_state =newstate.top(); newstate.pop();
     
     for(set<char >::iterator it=opnum.begin();it!=opnum.end(); it++)
     { 
           set<int>* temp=new (set<int> )(pre_state) ; 
           move(*temp,*it);
           if(temp->size()==0) // 为空就不用做 $闭包了 
           continue;
           else
          { 
             $_closure(*temp); 
             //  加入一条边
             node* s1=new node;
             s1->newstate=*temp;
             s1->c  = *it; 
             s1->next = DFA[pre_state];
             DFA[pre_state]=s1;   
            if(DFAsumset.find(*temp)==DFAsumset.end())  //没找到这个状态，即是一个新状态
            {
              newstate.push(*temp);
              DFAsumset.insert(*temp);                                                 
            }
          }   
          
          delete temp;     
     }                 
                       
   }  
   return 0; 
}

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


/************获得DFA的终态***************/
int Z_nfa::solve_DFAend()
{
  set<set<int> >:: iterator it=DFAsumset.begin();     
  for(;it!=DFAsumset.end(); it++)
  {
    if(it->find(NFAend)!= it->end() ) //包含了NFA的终态的集合 
     DFAend.insert(*it) ;                                               
  }  
  return 0;  
}
 
/**********以文件形式输出DFA************/
int Z_nfa::displayDFA()
{
    
  FILE* fp_DFA= fopen("DFA.txt","w");
  map< set<int>, node* > :: iterator it;
  set<int>:: iterator s_iter;
  node* p;   
  //输出初态 
  //cout<<"( ";
  fprintf(fp_DFA,"( ");
  for(s_iter =DFAstart.begin(); s_iter!=DFAstart.end();s_iter++)
  {
  //   cout<<*s_iter<<" ";
     fprintf(fp_DFA,"%d ",*s_iter);               
  }
 // cout<<")"<<endl;
  fprintf(fp_DFA,")\n");
  //输出终态个数和终态  ，一个集合一行 
  set< set<int> > ::iterator ss_iter;
  cout<<DFAend.size()<<endl; 
  fprintf(fp_DFA,"%d\n",DFAend.size()); 
   for(ss_iter =DFAend.begin(); ss_iter!=DFAend.end();ss_iter++)
  {  
   //  cout<<"( ";
     fprintf(fp_DFA,"( ");
    for(s_iter=ss_iter->begin(); s_iter!=ss_iter->end(); s_iter++)
    {
     //  cout<<*s_iter<<" ";
       fprintf(fp_DFA,"%d ",*s_iter);  
    }
   // cout<<")"<<endl;
    fprintf(fp_DFA,")\n");           
  }
  // 输出DFA一行 表示一个邻接表 
  map<set<int> ,node* >:: iterator m_iter;
  for(m_iter=DFA.begin(); m_iter!=DFA.end(); m_iter++)
  { 
  //  cout<<"(";
    fprintf(fp_DFA,"( ");                    
    for(s_iter=m_iter->first.begin(); s_iter!=m_iter->first.end(); s_iter++)
    {
       //输出集合元素 也就是表中的第一个状态
  //     cout<<*s_iter<<" ";                                    
       fprintf(fp_DFA,"%d ",*s_iter);                                
    }                          
 //    cout<<")"<<endl;
     fprintf(fp_DFA,")\n");
     //下面输出与第一个状态连接的状态
     for(node* p=m_iter->second; p; p=p->next)
     {
  //      cout<<p->c<<" ";
        fprintf(fp_DFA,"%c ",p->c); 
    //    cout<<"(";
        fprintf(fp_DFA,"( "); 
         for(s_iter=p->newstate.begin(); s_iter!= p->newstate.end(); s_iter++)
        {  
    //      cout<<*s_iter<<" ";                                    
          fprintf(fp_DFA,"%d ",*s_iter);                                
        }              
    //     cout<<")"<<endl;
         fprintf(fp_DFA,")\n");         
     }                     
  } 
   fclose(fp_DFA); 
   return 0;     
} 
  /***********获得DFA的图************/
 int Z_nfa::get_DFA(map<set<int>, node*>& G)
 {
      map<set<int>, node* > :: iterator it; 
        for(it=DFA.begin(); it!=DFA.end();it++)
        { 
             G.insert(pair<set<int>,node*>(it->first,0)); 
           for(node* p=it->second; p; p = p->next)                    
           {
               node* s1 = new node;
               s1->newstate = p->newstate;
               s1->c = p->c;
               s1->next = G[it->first]; 
               G[it->first] = s1;           
           }                 
       }                                                
      return 0 ;    
 } 
 

/********析构函数释放资源**********/ 
Z_nfa::~Z_nfa()
{
   clear_stack();
   freeNFA(); 
   DFAfree();
   fp=0; 
   cout<<"调用了Z_nfa类的析构函数"<<endl;             
} 

/********应该类初始化时应该运行的程序********/ 
int Z_nfa::run()
{
   Z_nfa::input();      
   Z_nfa::expression_NFA(); 
   Z_nfa::get_NFAstart();
   Z_nfa::display_NFA(); 
   Z_nfa::NFA_DFA(); 
   Z_nfa::solve_DFAend(); 
   Z_nfa::displayDFA();
   
   return 0; 
}