regex.H

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

/*

Features:

- Syntactically identical to POSIX 1003.2 regular expressions except
for the added ability to include a reference to a previously named
expression in 'Lex' style - eg. '({foo}|{bar})*' where 'foo' and
'bar' are previously defined expressions.

- Is Unicode enabled.

*/

#ifndef ARCHON_UTILITIES_REGEX_H
#define ARCHON_UTILITIES_REGEX_H

#include <string>
#include <vector>
#include <map>

#include <archon/util/unicode.H>
#include <archon/util/ref.H>
#include <archon/util/logger.H>

namespace Archon
{
  namespace Utilities
  {
    using namespace std;

    class NFA; // See "nfa.H"

    class Regex
    {
      friend struct NFA;
      struct Lexer;
      struct Parser;
      struct ParserContext;

      struct Exp: virtual RefObjectBase
      {
        virtual string print(int contextPrecedence) const = 0;
        string print() const { return print(0); }
      };

      struct Altern: Exp
      {
        Ref<const Exp> e1, e2;

        Altern(Ref<const Exp> e1, Ref<const Exp> e2): e1(e1), e2(e2) {}
        string print(int) const;
      };

      struct Juxta: Exp
      {
        Ref<const Exp> e1, e2;

        Juxta(Ref<const Exp> e1, Ref<const Exp> e2): e1(e1), e2(e2) {}
        string print(int) const;
      };

      struct Repeat: Exp
      {
        Ref<const Exp> e;
        int min;
        int max; // -1 if no max

        Repeat(Ref<const Exp> e, int min, int max): e(e), min(min), max(max) {}
        string print(int) const;
      };

      struct String: Exp
      {
        ustring s;

        String(ustring s): s(s) {}

        String() {}

        string print(int) const;
      };

      struct Class: Exp
      {
        enum Name
        {
          name_alnum = 0,
          name_alpha,
          name_blank,
          name_cntrl,
          name_digit,
          name_graph,
          name_lower,
          name_print,
          name_punct,
          name_space,
          name_upper,
          name_xdigit
        };

        vector<pair<uchar, uchar> > ranges;
        vector<bool> namedClasses;
        bool invert;

        Class(const vector<pair<uchar, uchar> > ranges,
              const vector<bool> namedClasses, bool invert):
          ranges(ranges), namedClasses(namedClasses), invert(invert) {}

        Class(): namedClasses(name_xdigit+1), invert(true) {}

        string print(int) const;
      };

      struct LineBegin: Exp
      {
        string print(int) const;
      };

      struct LineEnd: Exp
      {
        string print(int) const;
      };

      struct WordBegin: Exp
      {
        string print(int) const;
      };

      struct WordEnd: Exp
      {
        string print(int) const;
      };

    public:
      static Regex altern(Regex r1, Regex r2)
      {
        return Regex(new Altern(r1.exp, r2.exp));
      }

      static Regex juxta(Regex r1, Regex r2)
      {
        return Regex(new Juxta(r1.exp, r2.exp));
      }

      static Regex repeat(Regex r, int min, int max);

      static Regex repeat(Regex r, int n, bool orMore);

      static Regex star(Regex r) { return Regex(new Repeat(r.exp, 0, -1)); }
      static Regex plus(Regex r) { return Regex(new Repeat(r.exp, 1, -1)); }
      static Regex option(Regex r) { return Regex(new Repeat(r.exp, 0, 1)); }

      static Regex str(ustring s) { return Regex(new String(s)); }

      static Regex str(string s) { return Regex(new String(Unicode::decodeUtf8(s))); }

      static Regex empty() { return Regex(new String()); }

      /*
       * Recognized class names are:
       *   alnum, alpha, blank, cntrl,
       *   digit, graph, lower, print,
       *   punct, space, upper, xdigit
       *
       * Each range must have a first component less than or equal to
       * its second component.
       *
       * It is illegal to request a non-inverted bracket with no ranges
       * and no named classes.
       */
      static Regex bracket(const vector<pair<uchar, uchar> > &ranges,
                           const vector<string> &namedClasses,
                           bool invert=false);

      static Regex range(uchar from, uchar to, bool invert=false)
      {
        vector<pair<uchar, uchar> > r;
        r.push_back(make_pair(from, to));
        vector<string> n;
        return bracket(r, n, invert);
      }

      static Regex namedClass(string name, bool invert=false)
      {
        vector<pair<uchar, uchar> > r;
        vector<string> n;
        n.push_back(name);
        return bracket(r, n, invert);
      }

      static Regex anyChar() { return Regex(new Class()); }

      static Regex lineBegin() { return Regex(new LineBegin()); }
      static Regex lineEnd()   { return Regex(new LineEnd()); }
      static Regex wordBegin() { return Regex(new WordBegin()); }
      static Regex wordEnd()   { return Regex(new WordEnd()); }


      class Environment
      {
        friend class ParserContext;
        map<string, Ref<const Exp> > m;

      public:
        void define(string name, const Regex &r)
        {
          m[name] = r.exp;
        }
      };

      Regex(ustring s, Logger *l=0)
      {
        parse(s, l, 0);
      }

      Regex(ustring s, const Environment &e, Logger *l=0)
      {
        parse(s, l, &e);
      }

      Regex(string s, Logger *l=0)
      {
        parse(Unicode::decodeUtf8(s), l, 0);
      }

      Regex(string s, const Environment &e, Logger *l=0)
      {
        parse(Unicode::decodeUtf8(s), l, &e);
      }

      string print() const { return exp->print(); }

    private:
      Ref<const Exp> exp;

      Regex(Ref<const Exp> exp): exp(exp) {}

      static const Parser &getParser();

      void parse(ustring, Logger *, const Environment *);

      void makeNfa(NFA &, const Exp *, int context) const;
      void makeNfa(NFA &) const;
    };
  }
}

#endif // ARCHON_UTILITIES_REGEX_H

---