source: CMT/v1r12p20020606/src/cmt_regexp.cxx @ 1

#include "cmt_std.h"
#include "cmt_regexp.h"
#include "cmt_vector.h"

//----------------------------------------------------------
//
//  Declarations
//
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_node
{
public:
  static cmt_node& null ();
  static int node_count ();
  
  cmt_node ();
  virtual ~cmt_node ();
  
  virtual const cmt_regexp::iterator match (const cmt_string& text, 
                                            int pos) const;
  virtual bool is_char () const;
  virtual bool is_many_node () const;
  
private:
  static int _node_count;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_char_node : public cmt_node
{
public:
  cmt_char_node (char c);
  
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
  
  bool is_char () const;
  operator char ();
  
private:
  char _c;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_string_node : public cmt_node
{
public:
  cmt_string_node (const cmt_string& s);
  
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
  
private:
  cmt_string _s;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_char_list_node : public cmt_node
{
public:
  cmt_char_list_node (cmt_string list);
  
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
  
protected:
  cmt_string _list;
  cmt_string _choices;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_not_char_list_node : public cmt_char_list_node
{
public:
  cmt_not_char_list_node (cmt_string list);
  
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_any_node : public cmt_node
{
public:
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_zero_one : public cmt_node
{
public:
  cmt_zero_one (cmt_node* n);
  ~cmt_zero_one ();
  
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
  
protected:
  cmt_node* _node;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_begin_node : public cmt_node
{
public:
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_end_node : public cmt_node
{
public:
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_node_set : public cmt_node
{
public:
  cmt_node_set ();
  cmt_node_set (cmt_node_set* father);
  ~cmt_node_set ();
  
  cmt_node_set* father ();
  void clear ();
  void push (cmt_node* n);
  cmt_node* pop ();
  cmt_node* top () const;
  int nodes () const;
  const cmt_node* nodeAt (int index) const;
  bool parentheses () const;
  void set_parentheses (bool value);
  virtual void reduce ();
  
protected:
  cmt_node_set* _father;
  cmt_vector<cmt_node*> _nodes;
  bool _parentheses;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_and_node : public cmt_node_set
{
public:
  cmt_and_node ();
  cmt_and_node (cmt_node_set* father);
  
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
  void reduce ();
  void fill (cmt_and_node& other, int start_index);
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_or_node : public cmt_node_set
{
public:
  cmt_or_node (cmt_node_set* father);
  
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_many_node : public cmt_node
{
public:
  bool is_many_node () const;
  void install (cmt_and_node& other, int index);
  void reduce ();
  
protected:
  cmt_many_node (cmt_node* n);
  virtual ~cmt_many_node ();
  cmt_node* _node;
  cmt_and_node _follower;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_zero_more : public cmt_many_node
{
public:
  cmt_zero_more (cmt_node* n);
  
  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
};
//----------------------------------------------------------

//----------------------------------------------------------
class cmt_one_more : public cmt_many_node
{
public:
  cmt_one_more (cmt_node* n);

  const cmt_regexp::iterator match (const cmt_string& text, int pos) const;
};
//----------------------------------------------------------

//----------------------------------------------------------
cmt_node& cmt_node::null ()
{
  static cmt_node null_instance;
  
  return (null_instance);
}
//----------------------------------------------------------



//----------------------------------------------------------
//
//  Implementation
//
//----------------------------------------------------------

//----------------------------------------------------------
cmt_node::cmt_node ()
{
  _node_count++;
}

cmt_node::~cmt_node ()
{
  _node_count--;
}

int cmt_node::node_count ()
{
  return (_node_count);
}

const cmt_regexp::iterator cmt_node::match (const cmt_string& /*text*/, 
                                            int /*pos*/) const
{
  return (cmt_regexp::iterator::null());
}

bool cmt_node::is_char () const
{
  return (false);
}

bool cmt_node::is_many_node () const
{
  return (false);
}

int cmt_node::_node_count = 0;
//----------------------------------------------------------

//----------------------------------------------------------
cmt_char_node::cmt_char_node (char c)
{
  _c = c;
}

const cmt_regexp::iterator cmt_char_node::match (const cmt_string& text, 
                                                 int pos) const
{
  if ((pos < 0) || (pos > text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  char c = text[pos];

  if (c == _c)
    {
      return (cmt_regexp::iterator (pos, 1));
    }
  
  return (cmt_regexp::iterator::null ());
}

bool cmt_char_node::is_char () const
{
  return (true);
}

cmt_char_node::operator char ()
{
  return (_c);
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_string_node::cmt_string_node (const cmt_string& s)
{
  _s = s;
}

const cmt_regexp::iterator cmt_string_node::match (const cmt_string& text, 
                                                  int pos) const
{
  if ((pos < 0) || (pos > text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  int length = _s.size ();
  
  cmt_string s = text.substr (pos, length);
  
  if ((length == 0) || (s == _s))
    {
      return (cmt_regexp::iterator (pos, length));
    }
  
  return (cmt_regexp::iterator::null ());
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_char_list_node::cmt_char_list_node (cmt_string list)
{
  _list = list;
  
  _choices = "";
  
  char c;
  int i;
  
  for (i = 0; i < list.size (); i++)
    {
      c = list[i];
      
      switch (c)
        {
          case '-':
            i++;
            {
              char c1 = _choices[_choices.size () - 1];
              char c2 = list[i];
              int j;
              int j0 = (c1 < c2) ? c1 : c2;
              int j1 = (c1 > c2) ? c1 : c2;
              for (j = j0; j <= j1; j++)
                {
                  _choices += j;
                }
            }
            break;
          case '\\':
            i++;
            c = list[i];
            switch (c)
              {
                case '[':
                case ']':
                case '(':
                case ')':
                case '.':
                case '*':
                case '?':
                case '^':
                case '$':
                case '\\':
                  break;
                case 'r':
                  c = '\r';
                  break;
                case 't':
                  c = '\t';
                  break;
                case 'n':
                  c = '\n';
                  break;
                default:
                  break;
              }
          default:
            _choices += c;
            break;
        }
    }
}

const cmt_regexp::iterator cmt_char_list_node::match (const cmt_string& text, 
                                                     int pos) const
{
  if ((pos < 0) || (pos > text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  char c = text[pos];

  int i;
  
  for (i = 0; i < _choices.size (); i++)
    {
      if (c == _choices[i]) return (cmt_regexp::iterator (pos, 1));
    }
  
  return (cmt_regexp::iterator::null ());
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_not_char_list_node::cmt_not_char_list_node (cmt_string list) : 
        cmt_char_list_node (list)
{
}

const cmt_regexp::iterator cmt_not_char_list_node::match (const cmt_string& text, 
                                                      int pos) const
{
  if ((pos < 0) || (pos > text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  char c = text[pos];

  int i;

  for (i = 0; i < _choices.size (); i++)
    {
      if (c == _choices[i]) return (cmt_regexp::iterator::null ());
    }
  
  return (cmt_regexp::iterator (pos, 1));
}
//----------------------------------------------------------

//----------------------------------------------------------
const cmt_regexp::iterator cmt_any_node::match (const cmt_string& text, 
                                            int pos) const
{
  if ((pos < 0) | (pos >= text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }
  
  return (cmt_regexp::iterator (pos, 1));
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_zero_one::cmt_zero_one (cmt_node* n) : _node (n)
{
}

cmt_zero_one::~cmt_zero_one ()
{
  delete _node;
}

const cmt_regexp::iterator cmt_zero_one::match (const cmt_string& text, 
                                               int pos) const
{
  if ((pos < 0) || (pos > text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  int total = 0;

  if (pos < text.size ())
    {
      const cmt_regexp::iterator it = _node->match (text, pos);
      if (it != cmt_regexp::iterator::null ())
        {
          total += it._length;
          pos += it._length;
        }
    }
  
  return (cmt_regexp::iterator (pos, total));
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_many_node::cmt_many_node (cmt_node* n) : _node (n)
{
}

bool cmt_many_node::is_many_node () const
{
  return (true);
}

cmt_many_node::~cmt_many_node ()
{
  delete _node;
}

void cmt_many_node::install (cmt_and_node& other, int start_index)
{
  _follower.fill (other, start_index);
}

void cmt_many_node::reduce ()
{
  _follower.reduce ();
}
//----------------------------------------------------------



//----------------------------------------------------------
cmt_zero_more::cmt_zero_more (cmt_node* n) : cmt_many_node (n)
{
}

const cmt_regexp::iterator cmt_zero_more::match (const cmt_string& text, 
                                             int pos) const
{
  if ((pos < 0) || (pos > text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  int total = 0;

  //
  // we are at : x*y
  //

  int saved_pos = -1;
  int saved_total = -1;

  do
    {
      const cmt_regexp::iterator itx = _node->match (text, pos);
      const cmt_regexp::iterator ity = _follower.match (text, pos);

      if ((itx == cmt_regexp::iterator::null ()) &&
          (ity == cmt_regexp::iterator::null ())) 
        {
          //
          // There is neither x nor y. We move back to the last 
          // succesful match for y.
          //
          if (saved_pos >= 0)
            {
              //
              // We had once a y.
              //
              pos = saved_pos;
              total = saved_total;
            }
          else
            {
              //
              // We never had any y !
              //
              return (cmt_regexp::iterator::null ());
            }

          break;
        }

      if (itx == cmt_regexp::iterator::null ())
        {
          //
          // There is a y but no x anymore, fine, we can quit.
          //
          total += ity._length;
          pos += ity._length;
          break;
        }

      if (ity != cmt_regexp::iterator::null ())
        {
          //
          //  We have both x and y. We save the current pos and total,
          // and then skip this x.
          //
          saved_total = total + ity._length;
          saved_pos = pos + ity._length;
        }
      total += itx._length;
      pos += itx._length;
    } while (true);
  
  return (cmt_regexp::iterator (pos, total));
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_one_more::cmt_one_more (cmt_node* n) : cmt_many_node (n)
{
}

const cmt_regexp::iterator cmt_one_more::match (const cmt_string& text, 
                                            int pos) const
{
  if ((pos < 0) || (pos > text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  int total = 0;

  //
  // we are at : x+y
  //

  int saved_pos = -1;
  int saved_total = -1;
  bool at_least_one = false;

  do
    {
      const cmt_regexp::iterator itx = _node->match (text, pos);
      const cmt_regexp::iterator ity = _follower.match (text, pos);

      if ((itx == cmt_regexp::iterator::null ()) &&
          (ity == cmt_regexp::iterator::null ())) 
        {
          //
          // There is neither x nor y. We move back to the last 
          // succesful match for y.
          //
          if (saved_pos >= 0)
            {
              //
              // We had once a y.
              //
              pos = saved_pos;
              total = saved_total;
            }
          else
            {
              //
              // We never had any y !
              //
              return (cmt_regexp::iterator::null ());
            }

          break;
        }

      if (itx == cmt_regexp::iterator::null ())
        {
          //
          // There is a y but no x anymore, fine, we can quit.
          //
          total += ity._length;
          pos += ity._length;
          break;
        }

      if (ity != cmt_regexp::iterator::null ())
        {
          //
          //  We have both x and y. We save the current pos and total,
          // and then skip this x.
          //
          saved_total = total + ity._length;
          saved_pos = pos + ity._length;
        }

      total += itx._length;
      pos += itx._length;

      at_least_one = true;
    } while (true);
  
  if (!at_least_one) return (cmt_regexp::iterator::null ());
  
  return (cmt_regexp::iterator (pos, total));
}
//----------------------------------------------------------



//----------------------------------------------------------
const cmt_regexp::iterator cmt_begin_node::match (const cmt_string& /*text*/, 
                                                 int pos) const
{
  if (pos == 0) return (cmt_regexp::iterator (pos, 0));
  return (cmt_regexp::iterator::null ());
}
//----------------------------------------------------------

//----------------------------------------------------------
const cmt_regexp::iterator cmt_end_node::match (const cmt_string& text,
                                                int pos) const
{
  if (pos == text.size ()) return (cmt_regexp::iterator (pos, 0));
  return (cmt_regexp::iterator::null ());
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_node_set::cmt_node_set () : _father (0)
{
  _parentheses = false;
}

cmt_node_set::cmt_node_set (cmt_node_set* father) : _father (father)
{
  if (father != 0) father->push (this);
  _parentheses = false;
}

cmt_node_set::~cmt_node_set ()
{
  clear ();
}

cmt_node_set* cmt_node_set::father ()
{
  return (_father);
}

void cmt_node_set::clear ()
{
  int i;
  
  for (i = 0; i < _nodes.size (); i++)
    {
      cmt_node* n = _nodes[i];
      delete n;
    }
  _nodes.clear ();
}

void cmt_node_set::push (cmt_node* n)
{
  _nodes.push_back (n);
}

cmt_node* cmt_node_set::pop ()
{
  if (_nodes.size () == 0) return (&cmt_node::null ());
  
  int index = _nodes.size () - 1;
  
  cmt_node* n = _nodes[index];
  _nodes.erase (index);
  
  return (n);
}

cmt_node* cmt_node_set::top () const
{
  if (_nodes.size () == 0) return (&cmt_node::null ());
  
  int index = _nodes.size () - 1;
  
  cmt_node* n = _nodes[index];
  
  return (n);
}

int cmt_node_set::nodes () const
{
  return (_nodes.size ());
}

const cmt_node* cmt_node_set::nodeAt (int index) const
{
  return (_nodes[index]);
}

bool cmt_node_set::parentheses () const
{
  return (_parentheses);
}

void cmt_node_set::set_parentheses (bool value)
{
  _parentheses = value;
}

void cmt_node_set::reduce ()
{
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_and_node::cmt_and_node () : cmt_node_set ()
{
}

cmt_and_node::cmt_and_node (cmt_node_set* father) : cmt_node_set (father)
{
}

const cmt_regexp::iterator cmt_and_node::match (const cmt_string& text, 
                                                int pos) const
{
  if ((pos < 0) || (pos > text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  if (_nodes.size () == 0) return (cmt_regexp::iterator (pos, 0));

  int i;
  int total = 0;
  int p = pos;
  
  for (i = 0; i < _nodes.size (); i++)
    {
      cmt_node* n = _nodes[i];
      
      const cmt_regexp::iterator it = n->match (text, p);
      
      if (it == cmt_regexp::iterator::null ()) return (it);
      
      total += it._length;
      p += it._length;
    }

    // All nodes match
  
  return (cmt_regexp::iterator (pos, total));
}

void cmt_and_node::reduce ()
{
  if (_nodes.size () < 2) return;
  
  char c = ' ';
  cmt_string s = "";
  cmt_vector<cmt_node*> new_nodes;

  //
  // We loop once too much in order to finish the possibly accumulated
  // string at the end.
  //
  for (int i = 0; i <= _nodes.size (); i++)
    {
      cmt_node* n = 0;

      if (i < _nodes.size ()) n = _nodes[i];

      if ((i >= _nodes.size ()) || (!n->is_char ()))
        {
          if (s.size () == 1)
            {
              //
              // Too bad there was only one char node to consider
              // let's put it back as a char node !
              //
              new_nodes.push_back (new cmt_char_node (c));
              s = "";
            }
          else if (s.size () > 1)
            {
              //
              // We have real reduction here sonce there was several
              // consecutive char nodes.
              //
              new_nodes.push_back (new cmt_string_node (s));
              s = "";
            }

          if (i >= _nodes.size ()) break;
        }

      if (n->is_char ())
        {
          //
          // We are now trying to compact those char nodes.
          //
          cmt_char_node& cn = *((cmt_char_node*) n);
          c = (char) cn;
          s += c;
          delete n;
          _nodes[i] = 0;
        }
      else if (n->is_many_node ())
        {
          cmt_many_node& mn = *((cmt_many_node*) n);
          mn.install (*this, i + 1);
          mn.reduce ();
          new_nodes.push_back (n);
          break;
        }
      else
        {
          new_nodes.push_back (n);
        }
    }
  
  _nodes = new_nodes;
}

void cmt_and_node::fill (cmt_and_node& other, int start_index)
{
  if ((start_index < 0) || (start_index > other.nodes ())) return;

  for (int i = start_index; i < other.nodes (); i++)
    {
      cmt_node* n = other._nodes[i];
      push (n);
    }
}
//----------------------------------------------------------

//----------------------------------------------------------
cmt_or_node::cmt_or_node (cmt_node_set* father) : cmt_node_set (father)
{
}

const cmt_regexp::iterator cmt_or_node::match (const cmt_string& text, 
                                               int pos) const
{
  if ((pos < 0) || (pos >= text.size ())) 
    {
      return (cmt_regexp::iterator::null ());
    }

  if (_nodes.size () == 0) return (cmt_regexp::iterator (pos, 0));
  
  int i;
  
  for (i = 0; i < _nodes.size (); i++)
    {
      const cmt_node* n = _nodes[i];
      
      const cmt_regexp::iterator it = n->match (text, pos);
      
        //        at least one or-ed expression matches
      if (it != cmt_regexp::iterator::null ()) return (it);
    }
  
  return (cmt_regexp::iterator::null ());
}
//----------------------------------------------------------













//----------------------------------------------------------
cmt_regexp::cmt_regexp (const cmt_string& expression)
{
  _root = 0;

    //
    // The root is the cmt_or_node which will be returned. It is
    // the top of the hierarchy.
    //
    //  top is the running cmt_and_node.
    //
  cmt_node_set* or_root = 0;
  cmt_node_set* top_and = 0;
  
    // abcd
    // ab|cd
    // a|b|cd
    // a|b*|cd
    // a|b*|cd?e
    //
    // exp     : and
    //         | exp '|' and
    //
    // and     : unary 
    //         | unary and
    //
    // unary   : primary '*'
    //         | primary '?'
    //
    // primary : '[' opt_begin opt_chars opt_end ']'
    //         | '^'
    //         | '$'
    //         | char
    //         | '(' exp ')'
    //
  
  {
      //
      // First we build an cmt_or_node (corresponding to the
      // first grammatical rule)
      //
      //  Then cmt_and_nodes are pushed into it.
      //  and standard nodes are pushed into the running (top_and) cmt_and_node
      //
    or_root = new cmt_or_node (0);
    top_and = new cmt_and_node (or_root);
  }
  
  int i;
  
  for (i = 0; i < expression.size (); i++)
    {
      char c = expression[i];
      switch (c)
        {
          case '[':
          {
              //
              // The case is 
              //
              //  exp   : '['     char ... ']'
              //  exp   : '[' '^' char ... ']'
              //

            if (i >= expression.size ()) 
              {
                  // syntax error : unbalanced '['
                delete or_root;
                return;
              }
            i++;
            
            int i0 = i;
            
            bool done = false;
            bool has_not = false;
            
            cmt_string choices = "";
            
            for (; i < expression.size (); i++)
              {
                c = expression[i];
                switch (c)
                  {
                    case ']':
                      done = true;
                      break;
                    case '^':
                      if (i == i0) has_not = true;
                      else choices += c;
                      break;
                    case '\\':
                      choices += c;
                      if (i >= expression.size ())
                        {
                            // syntax error : unbalanced '[' and unfinished
                            // escape sequence
                          delete or_root;
                          return;
                        }
                      i++;
                      c = expression[i];
                      choices += c;
                      break;
                    default:
                      choices += c;
                      break;
                  }
                if (done) break;
              }
            
            if (!done)
              {
                  // syntax error : unbalanced '['
                delete or_root;
                return;
              }
            if (has_not)
              top_and->push (new cmt_not_char_list_node (choices));
            else        
              top_and->push (new cmt_char_list_node (choices));
          }
          break;
          case '*':
          {
              //
              //  exp : exp '*'
              //
            if (top_and->nodes () == 0)
              {
                  // Syntax error : '*' is not preceded by an expression
                delete or_root;
                return;
              }
            
            cmt_node* n = top_and->pop ();
            top_and->push (new cmt_zero_more (n));
          }
          break;
          case '+':
          {
              //
              //  exp : exp '+'
              //
            if (top_and->nodes () == 0)
              {
                  // Syntax error : '+' is not preceded by an expression
                delete or_root;
                return;
              }
            
            cmt_node* n = top_and->pop ();
            top_and->push (new cmt_one_more (n));
          }
          break;
          case '?':
          {
              //
              //  exp : exp '?'
              //
            if (top_and->nodes () == 0)
              {
                  // Syntax error : '?' is not preceded by an expression
                delete or_root;
                return;
              }
            
            cmt_node* n = top_and->pop ();
            top_and->push (new cmt_zero_one (n));
          }
          break;
          case '.':
              //
              //  exp : '.'
              //
            top_and->push (new cmt_any_node ());
            break;
          case '(':
          {
              //
              //  exp : '(' exp ')'
              //
            if (top_and->parentheses ())
              {
                  // This should never happen.
                delete or_root;
                return;
              }
            
            top_and->set_parentheses (true);
            
              //
              // A new complete expression is started.
              //  -> do as for top_and parsing.
              //
            
            top_and = new cmt_and_node (new cmt_or_node (top_and));
          }
          break;
          case ')':
          {
              //
              //  exp : '(' exp ')'
              //
            
              // top_and is the cmt_and_node into which new nodes are pushed.
            cmt_node_set* or_node = top_and->father ();
            if (or_node == 0) 
              {
                  // This should never happen : top_and should always be
                  // at least an cmt_and_node hanging at an cmt_or_node
                delete or_root;
                return;
              }
            
              //
              // The last cmt_and_node was empty, thus we had either '()' or '(...|)'
              //
            
            if (top_and->nodes () == 0) 
              {
                delete (or_node->pop ());
              }
            else
              {
                top_and->reduce ();
              }
            
            top_and = or_node->father ();
            
            if (top_and == 0)
              {
                  // Syntax error : too many ')'
                delete or_root;
                return;
              }
            
              //
              // top_and is now the previous running cmt_and_node where the '(' 
              // was originally met its top_and node contains the parenthesized 
              // sub expression  If this one is empty, (due to an empty '()' 
              // expression) then it may simply be discarded.
              //
            
            if (!top_and->parentheses ())
              {
                  // Syntax error : too many ')'
                delete or_root;
                return;
              }
            
            top_and->set_parentheses (false);
            
            cmt_node* unique = 0;
            if (or_node->nodes () == 1)
              {
                cmt_node_set* and_node = (cmt_node_set*) or_node->top ();
                if (and_node->nodes () == 1)
                  {
                    unique = and_node->pop ();
                    delete (or_node->pop ());
                  }
                else if (and_node->nodes () == 0)
                  {
                    delete (or_node->pop ());
                  }
              }
            
            if (or_node->nodes () == 0) delete (top_and->pop ());
            if (unique != 0) top_and->push (unique);
          }
          
          break;
          case '|':
          {
              //
              //  exp : exp '|' exp
              //

            cmt_node_set* or_node = top_and->father ();
            
            top_and->reduce ();
            
              //
              // or is the father cmt_or_node, which only contains cmt_and_nodes
              //
            
            const cmt_node_set* and_node = (cmt_node_set*) or_node->top ();
            if (and_node->nodes () == 0)
              {
                  // the previous node was empty.
                  // we may discard it
                or_node->pop ();
              }
            
            top_and = new cmt_and_node (or_node);
          }
          break;
          case '^':
              //
              //  exp : '^'
              //
            top_and->push (new cmt_begin_node ());
            break;
          case '$':
              //
              //  exp : '$'
              //
            top_and->push (new cmt_end_node ());
            break;
          case '\\':
            if (i >= expression.size ())
              {
                delete or_root;
                return;
              }
            i++;
            c = expression[i];
            switch (c)
              {
                case '[':
                case ']':
                case '(':
                case ')':
                case '.':
                case '*':
                case '?':
                case '^':
                case '$':
                case '\\':
                  break;
                case 'r':
                  c = '\r';
                  break;
                case 't':
                  c = '\t';
                  break;
                case 'n':
                  c = '\n';
                  break;
                default:
                  break;
              }
          default:
            top_and->push (new cmt_char_node (c));
            break;
        }
    }
  
  if (or_root != 0)
    {
      cmt_node_set* and_node = (cmt_node_set*) or_root->top ();
      
      if (or_root->nodes () == 1)
        {
            //
            // Check whether there is at least one non-empty
            // cmt_and_node
            //
          if (and_node->nodes () == 0)
            {
              delete or_root;
              return;
            }
        }
      
      if (and_node != 0)
        {
          and_node->reduce ();
          
          if (and_node->parentheses ())
            {
              delete or_root;
              return;
            }
        }
    }
  
  _root = or_root;
}

cmt_regexp::~cmt_regexp ()
{
  if (_root != 0)
    {
      delete _root;
    }
}

bool cmt_regexp::is_valid () const
{
  if (_root != 0) return (true);
  else return (false);
}

cmt_regexp::iterator cmt_regexp::begin (const cmt_string& text, int pos)
{
  if (_root != 0)
    {
      int i;
      
      for (i = pos; i < text.size (); i++)
        {
          cmt_regexp::iterator it = _root->match (text, i);
          if (it != end ()) return (it);
        }
    }
  
  return (end ());
}

cmt_regexp::iterator cmt_regexp::end ()
{
  return (cmt_regexp::iterator::null ());
}

cmt_regexp::iterator cmt_regexp::begin (const cmt_string& text, int pos) const
{
  if (_root != 0)
    {
      int i;
      
      for (i = pos; i < text.size (); i++)
        {
          cmt_regexp::iterator it = _root->match (text, i);
          if (it != end ()) return (it);
        }
    }
  
  return (end ());
}

cmt_regexp::iterator cmt_regexp::end () const
{
  return (cmt_regexp::iterator::null ());
}

bool cmt_regexp::match (const cmt_string& text) const
{
  iterator it = begin (text);
  if (it == end ()) return (false);
  else return (true);
}
//----------------------------------------------------------

//----------------------------------------------------------
const cmt_regexp::iterator cmt_regexp::iterator::null ()
{
  static const iterator null_instance (-1, -1);
  
  return (null_instance);
}

cmt_regexp::iterator::iterator ()
{
  _pos = 0;
  _length = 0;
}

cmt_regexp::iterator::iterator (int pos, int length)
{
  _pos = pos;
  _length = length;
}

cmt_regexp::iterator::iterator (const iterator& other)
{
  _pos = other._pos;
  _length = other._length;
}

int cmt_regexp::iterator::operator != (const iterator& other) const
{
  return ((this->_pos != other._pos) ||
          (this->_length != other._length));
}

int cmt_regexp::iterator::operator == (const iterator& other) const
{
  return ((this->_pos == other._pos) &&
          (this->_length == other._length));
}
//----------------------------------------------------------