dfa_dfamin.cpp

智能的词法分析

#include<iostream>
#include<vector> 
#include "DFA_DFAmin.h" 
using namespace std; 
 
/*********获得DFA，每个状态是一个整数**********/ 
int DFA_DFAmin::solve_DFA()
{ 
  
  map< set<int> ,node* > currDFA;
   Z_nfa::get_DFA(currDFA);
  map< set<int>, node* > :: iterator it;
  node* p;
  for(it=currDFA.begin(); it!=currDFA.end(); it++)
  { 
     if(set_int[it->first]==0) // 没有这个 状态 
      set_int[it->first]= ++DFAstatenum ;      
     int  prestate = set_int[it->first];  // 找出表头结点的 状态 int 
     if(it->second==0)  //为终态时 
     DFA.insert(pair<int, wedge* >(prestate,0));
     else 
     for(p = it->second; p!=NULL ; p= p ->next )
     {
       if(set_int[p->newstate]==0)  // 没有这个 状态  
        set_int[p->newstate]= ++DFAstatenum;  //加入这个状态 
       
         wedge* s1=new wedge;
         s1->c = p->c;
         s1->state = set_int[p->newstate] ; 
         s1->next = DFA[prestate];
         DFA[prestate] = s1;                                     
     } 
     
     // 释放由于currDFA是由深复制得来的 空间 
     for(node* p=it->second; p ; p=currDFA[it->first]) 
     {
        currDFA[it->first]=p->next;
        delete p;        
               
     }                                                                   
  }  
  return 0; 
  
}

/*******输出set_int*********/
int DFA_DFAmin::displayset_int()
{
  map< set<int>, int >:: iterator it;
  for(it=set_int.begin(); it!=set_int.end(); it++)
  {
    cout<<"( ";                      
    for(set<int>::iterator s_iter=it->first.begin(); s_iter!=it->first.end(); s_iter++)
    {
      cout<<*s_iter<<" ";                        
    }                        
    cout<<")     "<<it->second<<endl; 
  }  
    
  return 0;    
} 

/********得到DFA的初态*********/ 
int DFA_DFAmin::solve_DFAstart()
{
  DFAstart = set_int[Z_nfa::get_DFAstart()];    
  return 0;  
} 

/******得到DFA的终态，是一个集合***********/ 
int DFA_DFAmin::solve_DFAend()
{ 
  set<set<int> > currDFAend = Z_nfa::get_DFAend(); 
  set<set<int> > :: iterator it;  
   for(it=currDFAend.begin(); it!=currDFAend.end();  it++)
   {
      int state= set_int[*it];                                             
      DFAend.insert(state);                                             
   }   
   return 0;      
} 

/********以文件形式输出DFA，每一个状态是一个整数**************/  
int DFA_DFAmin::displayDFA()
{  
   FILE* fp=fopen("DFA_int.txt","w"); 
   // 先输出初态和 终态
   fprintf(fp,"%d\n",DFAstart);
   // 输出终态集 
   fprintf(fp,"( "); 
   for(set<int>::iterator it=DFAend.begin(); it!=DFAend.end();it++)
   { 
     fprintf(fp,"%d ",*it);                                                
   } 
   fprintf(fp,")\n"); 
   // 输出邻接表
  map<int, wedge* >:: iterator m_iter;
  for(m_iter=DFA.begin();m_iter!= DFA.end(); m_iter++)
  {
    fprintf(fp,"%d ",m_iter->first);                                
    for(wedge* p=m_iter->second; p!=NULL; p=p->next)
    {  
      fprintf(fp,"%c %d ",p->c,p->state);                  
    }          
    fprintf(fp,"\n");                  
  } 
    fclose(fp);
    return 0; 
} 

/*****来实现 map<int ,wedge* > NFA到minDFA之间的深复制 *****/ 
int DFA_DFAmin::map_map()
{
   map<int,wedge* > :: iterator it; 
  for(it=DFA.begin(); it!=DFA.end();it++)
  { 
     minDFA.insert(pair<int,wedge*>(it->first,0)); 
     for(wedge* p=it->second; p; p = p->next)                    
     {
        wedge* s1 = new wedge;
        s1->state = p->state;
        s1->c = p->c;
        s1->next = minDFA[it->first]; 
        minDFA[it->first] = s1;           
     }                 
  }   
  return 0;  
} 

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

/**********求DFA的等价状态************/ 
int DFA_DFAmin::solve_equal_state()
{ 
  //mydeque中存的是等价状态  
    
  map<int,wedge* > :: iterator it; 
  set <char> :: iterator s_iter; 
  // 下面是为了获得非授受组 
  set<int> NF;// 非接受组
  set<int> :: iterator set_iter; 
  for(int i=1;i<=DFAstatenum;i++)
  {
     NF.insert(i);                  
  } 
  for(set_iter = DFAend.begin();set_iter!=DFAend.end();set_iter++)
  {
    NF.erase(*set_iter);             
  } 
  mydeque.push_back(NF) ;  //加入非接受状态组 
  mydeque.push_back(DFAend); // 加入接受状态组 
   
  deque<set<int> > curr_que;
  int que_ize = 0; 
  while(que_ize!=mydeque.size()) //当状态数不变时，表示所有的等价状态以经找出 
 { 
    que_ize = mydeque.size(); 
  for(s_iter = opnum.begin() ; s_iter != opnum.end(); s_iter++) //字母表遍历 
  { 
     for(int i=0;i<mydeque.size();i++) //每个状态组遍历 
    {
        if(mydeque[i].size()==1)
      { 
        curr_que.push_back(mydeque[i]); 
        continue; 
      } 
      else
      { 
        map< set<int>, link* > G;  //用来存到同一个状态组的元素的 
        set<int> temp; //用来存没有后继的状态的 
        for(set_iter=mydeque[i].begin();set_iter!=mydeque[i].end();set_iter++) //遍历每个集合中的元素  
        { 
          int newstate=0;// 定义一个新状态，为0表示未找到 ，也就是没有后继  
          for(wedge* p=DFA[*set_iter];p;p=p->next) //在邻接表中找经过字母 *s_iter 后产生的新状态 
          {
             if(p->c==*s_iter)
             {
               newstate=p->state;  
               break;               
             }         
          } 
          
            if(newstate==0) //没有后继 
           {
             temp.insert(*set_iter);            
           }
           else 
           for(int j=0;j<mydeque.size();j++) //对newstate ，在原来的分组中找 
          {    
             if(mydeque[j].find(newstate)!=mydeque[j].end()) //要是找到 ,有后继          
              { 
                //把该状态属于哪个分组记下来  
                link* s1=new link;
                s1->state = *set_iter;
                s1->next=G[mydeque[j]]; 
                G[mydeque[j]] = s1 ; 
                break;                                  
              }                   
          } 
                                                                
        } 
         int Glen=G.size();
         int temp_len=temp.size(); 
         if(Glen>1||(Glen==1&&temp_len>0)) // 要是有不在同一分组的时候，才要进行加入新组和删除旧组 
        { 
          for(map< set<int>, link* >::iterator m_iter=G.begin(); m_iter!=G.end();m_iter++)
          { 
           set<int> myset; 
           for(link* q=m_iter->second; q; q=m_iter->second)
           {   
             myset.insert(q->state); 
             m_iter->second=q->next;
             delete q;       
           }         
            curr_que.push_back(myset);                         
          }     
          if(temp_len>0)                     
          curr_que.push_back(temp);           
       } 
       else  //在同一分组 
       {
         curr_que.push_back(mydeque[i]);     
       } 
    }                      
      
  } 
   mydeque = curr_que;
   curr_que.clear(); 
 }
   
 } 
  return 0; 
} 

/********显示一下等价状态********/ 
int DFA_DFAmin::display_mydeque()
{ 
  FILE* fp=fopen("等价状态.txt","w"); 
  for(int i=0;i<mydeque.size();i++)
  {
    fprintf(fp,"this is a set\n") ; 
    for(set<int>::iterator it=mydeque[i].begin();it!=mydeque[i].end();it++) 
    {
      fprintf(fp,"%d ",*it); 
    }      
    fprintf(fp,"\n");      
  }     
  cout<<endl; 
  return 0;  
} 
/********用来查找minDFA中first这个状态有没有能过c和second这个状态相连******/ 
inline int DFA_DFAmin::find(const int &first,const char &c, const int & second)
{
  for(wedge* p=minDFA[first];p;p=p->next)
  {
    if(p->c==c&&p->state==second)
    return 1;                          
  }     
   return 0; 
}

 
/*****将DFA进行最小化，同时释放了mydeque*******/ 
int DFA_DFAmin::DFAmin()
{ 
  minDFAstart = DFAstart ; 
  // minDFA=DFA; // 这句采用的是浅复制，没有new空间，传的是指针, 在后面的操作中会出错 
   map_map(); // 采用深复制 
   minDFAstatenum=DFAstatenum; 
   while (!mydeque.empty())
  { 
    set<int>  temp = mydeque.front();  
    mydeque.pop_front();
    int len=temp.size(); 
    if(len<=1 )  //就一个状态   
    continue;    
    else  //有等价状态 
    { 
      minDFAstatenum-=len-1; 
      set<int>::iterator s_iter=temp.begin(); //等价状态中只留下这一个状态，其它的都删除
     
     if(temp.find(DFAstart)!=temp.end()) //要是该集合中包括了，DFA的初态
      {
         minDFAstart = (*temp.begin());                                    
      }  
       
    
      int start= *temp.begin() ; 
      for(++s_iter;s_iter!=temp.end();s_iter++)
      {
         for(wedge* p=minDFA[*s_iter];p;p=minDFA[*s_iter])
         { 
             minDFA[*s_iter]=p->next; // 指针的前进 
            if(temp.find(p->state)==temp.end()
            &&!find(start,p->c,p->state)) //只要和他连接的不是它的等价状态，且在留下来那没有重复的， 就把他加入到 留下的那个状态中 
            {
              p->next=minDFA[*temp.begin()] ; 
              minDFA[*temp.begin()]=p->next;                                   
            }                
         }  
          // 删除等价状态中其它多余的状态
         minDFA.erase(*s_iter) ;
         // 把表中的所有等价状态替换
         for(map<int,wedge* >::iterator it=minDFA.begin();it!=minDFA.end();it++)
         {
           for(wedge* p=minDFA[it->first];p;p=p->next)
           {
              if(temp.find(p->state)!=temp.end()) // 找到等价状态，就替换
              {
                 p->state = start;                                                                                      
              }           
           }                   
         }
                                                     
      }        
    }       
  }
    
  return 0;    
} 

/*****将minDFA状态重新命名，这样使得状态从1到minDFAstatenum***/ 
int DFA_DFAmin::re_minDFA()
{
  //因为map默认是按Key从小到大排序的 
  map<int,wedge* > :: iterator it;
  map<int,wedge* > :: iterator m_iter;
  int num=1; 
  for(it=minDFA.begin(); it!=minDFA.end()&&num<=minDFAstatenum;it++,num++)
  { 
    if(it->first==num)continue;
    else 
    {  //如果是初态，则初态更新 
       if(it->first==minDFAstart) minDFAstart=num;
       //如果是终态，终态更新
       if(minDFAend.find(it->first)!= minDFAend.end())
       {
         minDFAend.erase(it->first);
         minDFAend.insert(num);                               
       } 
       for(m_iter=minDFA.begin(); m_iter!=minDFA.end(); m_iter++)
       {// 把所有状态为it->first的，改为num，
         for(wedge* p=m_iter->second;p;p=p->next)
         {
            if(p->state==it->first)
             p->state=num;
                                      
         }      
       } 
          // 在把 minDFA[it->first]这个表删除，加入一个minDFA[num] 
           wedge* s=minDFA[it->first];
           minDFA[num]=s;
           minDFA.erase(it);                  
    } 
             
  }       
  return 0;   
} 

/********解决minDFA的终态******/
int DFA_DFAmin::solve_minDFAend()
{
    map<int,wedge* >:: iterator it;
   if(DFAend.size()==1) //DFA时只有一个终态一定是minDFA的终态 
   {
     minDFAend.insert(*(DFAend.begin()));
     return 0;
   } 
   for(it = minDFA.begin(); it != minDFA.end(); it++)
   {
     if(DFAend.find(it->first)!= DFAend.end())
     minDFAend.insert(it->first);                                            
   } 
   
    return 0; 
} 

/*********用来输出minDFA**********/ 
int DFA_DFAmin::dispalyminDFA()
{ 
    
   FILE* fp=fopen("minDFA.txt","w"); 
   //先输出总共有几个状态  
   fprintf(fp,"%d\n",minDFAstatenum); 
   // 先输出初态
   fprintf(fp,"%d\n",minDFAstart);  
   // 输出终态集 
   for(set<int>::iterator it=minDFAend.begin(); it!=minDFAend.end();it++)
   {
    
     fprintf(fp,"%d,",*it);                                                
   } 
   
   fprintf(fp,"\n",minDFAstart); 
   // 输出邻接表
  map<int, wedge* >:: iterator m_iter;
  for(m_iter=minDFA.begin();m_iter!= minDFA.end(); m_iter++)
  {
    if(m_iter->second) 
    fprintf(fp,"%d\n",m_iter->first);                                
    for(wedge* p=m_iter->second; p!=NULL; p=p->next)
    { 
      fprintf(fp,"%c,%d,",p->c,p->state);                  
    }          
    cout<<endl;
    fprintf(fp,"\n");                  
  } 
    fclose(fp);
    return 0;       
}

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

/******** 用该类时必须执行的 *******/ 
int DFA_DFAmin::run()
{ 
   //请注意顺序 
   DFA_DFAmin::solve_DFA(); 
   DFA_DFAmin::solve_DFAstart();
   DFA_DFAmin::solve_DFAend();  
   //  
   DFA_DFAmin::displayset_int(); 
   DFA_DFAmin::displayDFA(); 
   DFA_DFAmin::solve_equal_state(); 
   DFA_DFAmin::display_mydeque();
   DFA_DFAmin::DFAmin();
   DFA_DFAmin::solve_minDFAend(); //注意顺序 
   DFA_DFAmin::re_minDFA();  // 注意顺序
   DFA_DFAmin::dispalyminDFA();   
      
   return 0; 
}

/********接口用来获得minDFA********/ 
int DFA_DFAmin::get_minDFA(map<int,wedge* >& G)
{
  map<int,wedge* >:: iterator it;
  for(it=minDFA.begin();it!=minDFA.end();it++)
  { 
    G.insert(pair<int,wedge* >(it->first,0)) ; 
    for(wedge* p = it->second; p ;p=p->next)
    {
      wedge* s1=new wedge;
      s1->state = p->state;
      s1->c = p->c;
      s1->next=G[it->first];
      G[it->first]=s1;           
    }                                                                                       
  }   
   return 0;     
}
 
/*********析构函数***********/ 
DFA_DFAmin::~DFA_DFAmin()
{
  freeDFA();
  freeminDFA(); 
  cout<<"执行了DFA_DFAmin的析构函数"<<endl;                                           
}