nfa_epsilon.h

一个类似STL的自动机的源代码库

  State duplicate_state(const State & s) {
    return State(s);
  }

  bool final(const State & s) const {
///		cout << "nfa_epsilon::final : tag = " << tag(s) << " et tag nul = " << tag_nul << endl;
    return (this->tag(s) > tag_nul);
  }


  Tag& tag(State & s) {
    return (*(s.begin()))->_leTag ;
  }

  const Tag& tag(const State & s) const {
    return (*(s.begin()))->_leTag ;
  }

  Tag& tag(p_state p) {
    return (p->_leTag);
  }

  const Tag& tag(p_state p) const {
    return (p->_leTag);
  }

  State epsilon_closure(const State & s) const
  {
    State r;
    _state *t;

    State::const_iterator itb = s.begin();
    State::const_iterator ite = s.end() ; 

    for(; itb != ite ; ++itb)  
      closure.push_back(*itb);

//    cout << "epsilon cloture: tags = ";
    for(; ! closure.empty();)
    {
      t = closure.back();
      closure.pop_back();
      if (t->_aim2)    // epsilon trans ?
        closure.push_back(t->_aim2);
//      cout << t->_leTag << " ";
      if (t->_leTag != tag_nul || t->_laLettre != lettre_nulle || t->default_t)
        r.insert(t);
      if (t->_laLettre == lettre_nulle && t->_aim1)
        closure.push_back(t->_aim1);
    }

//    cout << endl;
    return r;
  }
      
  /*
  State epsilon_closure(const State & s) const
  {
    State r;
    _state *t;

    State::const_iterator itb = s.begin();
    State::const_iterator ite = s.end() ; 

    for(; itb != ite ; ++itb)  
      closure.push_back(*itb);

    for(; ! closure.empty();)
    {
      t = closure.back();
      closure.pop_back();
      if (t->_laLettre == lettre_nulle) 
      {
	if (t->_aim2)  // des epsilon transitions ?
	{
	  closure.push_back(t-> _aim2);
	  if (t->_aim1)
	    closure.push_back(t-> _aim1);

          if (t->default_t != NULL)
            r.insert(t);
	}
	else  // lettre nulle + pas d epsilon trans =>
	  r.insert(t);
      }
      else
      {
	r.insert(t);
	if (t->_aim2)
	  closure.push_back(t-> _aim2);
      }
    }
    return r;
  }
*/

  State delta1_default(const State & s) const
  { 
    
    State r;

    State::const_iterator itb = s.begin();
    State::const_iterator ite = s.end() ; 

    for(; itb != ite ; ++itb)  
      if ((*itb)->default_t != NULL)         // default trans
	      r.insert((*itb)->default_t);

    return (epsilon_closure(r));
  }
    /*
    for(; ! closure.empty();)
    {
      t = closure.back();
      closure.pop_back();
      ///      r.insert(t);   				  

      if (t->_laLettre == lettre_nulle) 
      {
	if (t->_aim2)
        {
	  closure.push_back(t-> _aim2);
	  if (t->_aim1)
	    closure.push_back(t-> _aim1);
	  if (t->default_t)
	    r.insert(t);
        }
	else
	  r.insert(t);
      }
      else
      {
	if (t->_aim2)
	  closure.push_back(t-> _aim2);
	r.insert(t);
      }
    }
    return  r;
  }
*/
  State delta1(const State & s, const Alphabet &l) const
  { 
    
    State r;

    State::const_iterator itb = s.begin();
    State::const_iterator ite = s.end() ; 

    for(; itb != ite ; ++itb)  
      if ((*itb)->_laLettre == l )
    	  r.insert((*itb)->_aim1);
/////      else
/////	      if ((*itb)->default_t != NULL)         // default trans
/////	        r.insert((*itb)->default_t);
/////   remplace par:
		if (r.empty())
			return (delta1_default(s));

    return (epsilon_closure(r));
  }
    /*
    for(; ! closure.empty();)
    {
      t = closure.back();
      closure.pop_back();
      ///      r.insert(t);   				  

      if (t->_laLettre == lettre_nulle) 
      {
	if (t->_aim2)
        {
	  closure.push_back(t-> _aim2);
	  if (t->_aim1)
	    closure.push_back(t-> _aim1);
	  if (t->default_t)
	    r.insert(t);
        }
	else
	  r.insert(t);
      }
      else
      {
	r.insert(t);
	if (t->_aim2)
	  closure.push_back(t-> _aim2);
      }
    }
    return  r;
  }
*/
  Edges delta2(const State & s) const
  {
    State q;
    vector<Alphabet> v;
    State::const_iterator first, last = s.end();
    for(first = s.begin(); first != last; ++first)
      if ((*first)->_laLettre != lettre_nulle)
      {
//				cout << "lettre nulle == " << lettre_nulle << " et la lettre = " << (*first)->_laLettre << endl;
//		cout << "delta2:test de l'etat " << *first << "   1er but = " << (*first)->_aim1 << endl;
	q.insert(*first);
	v.push_back((*first)->_laLettre);
      }
///////      else
//////	if  ((*first)->default_t)
///////	  q.insert(*first);
   
    return Edges(q, this, v);
  }
      
  State initial() const {
    return (I);
  }

  void initial(const State & i) {
    I = epsilon_closure(i);
  }

  unsigned long state_count() const {
    return (_state_count);
  }

  unsigned long trans_count() const {
    return (_trans_count);
  }

  const_iterator begin() const {
    return (Q.begin());
  }

  const_iterator end() const {
    return (Q.end());
  }
};

template <class NFA, class InputIterator>
class t_iterator : public iterator<input_iterator_tag, NFA::Tag>
{
  InputIterator where;
  const NFA &nfa;

public:
  t_iterator(InputIterator i, const NFA &_nfa) : where(i), nfa(_nfa)
  { }

  t_iterator(const t_iterator &x) : where(x.where), nfa(x.nfa)
  { }

  const NFA::Tag& operator * () const {
    return (nfa.tag(*where));
  }

  t_iterator& operator ++ () {
    ++where;
    return (*this);
  }

  t_iterator operator ++ (int) {
    t_iterator tmp = *this;
    ++(*this);
    return (tmp);
  }

  bool operator == (const t_iterator &x) const {
    return (where == x.where);
  }

  bool operator != (const t_iterator &x) const {
    return (!(*this == x));
  }
};

template <class _DFA, class Sigma, class Tag>
void nfa_epsilon_to_dfa(const NFA_Epsilon<Sigma, Tag> &nfa,
                        DFA_default<_DFA> &dfa)
{
  typedef NFA_Epsilon<Sigma, Tag> NFA;
  typedef DFA_default<_DFA> DFA;
  NFA::State Q = nfa.initial();
  if (Q == nfa.null_state)
    return;
  DFA::State q = dfa.new_state(), p;
  dfa.initial(q);
//	cout << "dterminisation de l'etat initial" << endl;
  tag_traits<NFA::Tag>::tag_determinize(t_iterator<NFA, NFA::State::const_iterator>(Q.begin(), nfa),
                                        t_iterator<NFA, NFA::State::const_iterator>(Q.end(), nfa),
                                        dfa.tag(q));         
  map<NFA::State, DFA::State> mapping;
  typedef map<NFA::State, DFA::State>::iterator it;
  it where, where_to;
  it path[10240];
  it *top = path;

  // cout << "Q (initial) size = " << Q.size() << endl;
  *top = mapping.insert(make_pair(Q, q)).first;
  //  path.push_back((mapping.insert(make_pair(Q, q))).first);
  //  cout << "titi" << endl;
  ++top;
  pair<NFA::Alphabet, NFA::State> trans;
  while (top != path)
  {
    //  cout << "top != path" << endl;
    --top;
    // cout << "Q size = " << (**top).first.size() << endl;
    where = *top;
    q = (*where).second;

    //  cout << "(*where).second = " << q << endl; 
    // default transitions:
//		cout << "transitions par defaut" << endl;
    Q = nfa.delta1_default((*where).first);
    if (!(Q == nfa.null_state))
    {
      //      cout << "dans default Q size = " << Q.size() << endl;
      where_to = mapping.find(Q);
      if (where_to != mapping.end())
      {
	///	cout << "dfa set default trans" << endl;
        dfa.set_trans(q, dfa.default_letter, (*where_to).second);
      }
      else
      {
	//	cout << "default:creating state " << ( p = dfa.new_state()) << endl;
        p = dfa.new_state();
        tag_traits<NFA::Tag>::tag_determinize(t_iterator<NFA, NFA::State::const_iterator>(Q.begin(), nfa),
                                              t_iterator<NFA, NFA::State::const_iterator>(Q.end(), nfa),
                                              dfa.tag(p));         
        dfa.set_trans(q, dfa.default_letter, p);
        dfa.final(p) = nfa.final(Q);
        *top = mapping.insert(make_pair(Q, p)).first;
	++top;
	//       path.push_back((mapping.insert(make_pair(Q, p))).first);
      }
    }

    // normal transition:
//		cout << "transitions normales" << endl;
    NFA::Edges edges = nfa.delta2((*where).first);
    NFA::Edges::const_iterator first, last = edges.end();
    for(first = edges.begin(); first != last; ++first)
    {
//			cout << "lettre = " << (*first).first << endl;
      trans = *first;
      where_to = mapping.find(trans.second);
      if (where_to != mapping.end())
        dfa.set_trans(q, trans.first, (*where_to).second);
      else
      {
      	p = dfa.new_state();
        tag_traits<NFA::Tag>::tag_determinize(t_iterator<NFA, NFA::State::const_iterator>(trans.second.begin(), nfa),
                                              t_iterator<NFA, NFA::State::const_iterator>(trans.second.end(), nfa),
                                              dfa.tag(p));         
	//	cout << "set_trans(" << q << ", " << trans.first << ", " << p << ")" << endl;
        dfa.set_trans(q, trans.first, p);
        dfa.final(p) = nfa.final(trans.second);
        *top = (mapping.insert(make_pair(trans.second, p))).first;
	++top;
	//        path.push_back((mapping.insert(make_pair(trans.second, p))).first);
      }
    }
  }
}


#endif // ASTL_NFA_Epsilon