regex.C

/*
 * 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).
 */

#include <iostream>
#include <memory>
#include <algorithm>
#if !defined __GNUC__ || __GNUC__ > 2
#include <limits>
#else
#include <limits.h>
#endif

#include <archon/util/unicode.H>
#include <archon/util/nfa.H>
#include <archon/util/cfg.H>
#include <archon/util/lexer.H>
#include <archon/util/lr_parser_simple.H>
#include <archon/util/lr_parser_methods.H>

#include <archon/util/regex.H>

/*
 * Special codepoints used from the "Private Use Area" of the Unicode
 * character set.
 *
 * BOL(^)        0xE000
 * EOL($)        0xE001
 * BOW([[:<:]])  0xE002
 * EOW([[:>:]])  0xE003
 */

using namespace std;

namespace Archon
{
  namespace Utilities
  {
    string Regex::Altern::print(int p) const
    {
      string s = e1->print(0) + "|" + e2->print(0);
      return p <= 0 ? s : "(" + s + ")";
    }

    string Regex::Juxta::print(int p) const
    {
      string s = e1->print(1) + e2->print(1);
      return p <= 1 ? s : "(" + s + ")";
    }

    string Regex::Repeat::print(int p) const
    {
      string s = e->print(2) +
        (min == 0 ? max == -1 ? "*" : max == 1 ? "?" : max == 0 ? "{0}" : "{0," + Text::toString(max) + "}" :
         min == 1 ? max == -1 ? "+" : max == 1 ? "{1}" : "{1," + Text::toString(max) + "}" :
         max == min ? "{" + Text::toString(min) + "}" : max == -1 ? "{" + Text::toString(min) + ",}" :
         "{" + Text::toString(min) + "," + Text::toString(max) + "}");
      return p <= 2 ? s : "(" + s + ")";
    }

    string Regex::String::print(int p) const
    {
      const int l = s.size();
      ustring t;
      t.reserve(l+l/5);
      static const string specialChars("|(){\\$?*+.^[");
      for(int i=0; i<l; ++i)
      {
        const uchar c = s[i];
        if(c<128 && specialChars.find(static_cast<char>(c))!=string::npos) t+='\\';
        t += c;
      }
      const string u = Text::toString(t);
      return p <= (l==0 ? -1 : l==1 ? 3 : 1) ? u : "(" + u + ")";
    }

    string Regex::Class::print(int) const
    {
      string s = "[";
      if(invert) s+= "^";
      bool lbrack = false;
      for(unsigned i=0; i < ranges.size(); ++i)
      {
        const pair<uchar, uchar> &r = ranges[i];
        string f = Text::toString(ustring(1, r.first));
        if(r.first=='^' && i==0 && !invert ||
           r.first==']' && i>0 ||
           r.first=='-' && i>0 && (r.second!='-' || i<ranges.size()-1) ||
           (r.first=='.' || r.first=='=' || r.first==':') && lbrack)
          f = "[." + f + ".]";
        if(r.first == r.second) s += f;
        else
        {
          string t = Text::toString(ustring(1, r.second));
          if(r.second==']') t = "[." + t + ".]";
          s += f + "-" + t;
        }
        lbrack = r.second=='[';
      }
      for(unsigned i=0; i <= name_xdigit; ++i)
        if(namedClasses[i])
        {
          const string n =
            i == name_alnum ? "alnum" :
            i == name_alpha ? "alpha" :
            i == name_blank ? "blank" :
            i == name_cntrl ? "cntrl" :
            i == name_digit ? "digit" :
            i == name_graph ? "graph" :
            i == name_lower ? "lower" :
            i == name_print ? "print" :
            i == name_punct ? "punct" :
            i == name_space ? "space" :
            i == name_upper ? "upper" : "xdigit";
          s += "[:" + n + ":]";
        }
      return s == "[^" ? "." : s + "]";
    }

    string Regex::LineBegin::print(int) const
    {
      return "^";
    }

    string Regex::LineEnd::print(int) const
    {
      return "$";
    }

    string Regex::WordBegin::print(int) const
    {
      return "[[:<:]]";
    }

    string Regex::WordEnd::print(int) const
    {
      return "[[:>:]]";
    }

    typedef RefObject<ustring> UAttr;
    typedef RefObject<pair<int, int> > IPAttr;

    struct Regex::ParserContext: LrParserBase::Context
    {
      LexerBase *lexer;
      const Environment *env;
      Logger *logger;

      Ref<Class> bracket;

      ParserContext(LexerBase *lexer, const Environment *env, Logger *logger):
        lexer(lexer), env(env), logger(logger) {}

      void warning(string s)
      {
        if(logger) logger->log(s);
        else ARCHON_THROW1(ArgumentException, s);
      }

      void parserError()
      {
        if(lexer->getType() < 0)
          warning("Syntax error. Unexpected end of string.");
        else
          warning("Syntax error. Unexpected character " +
                  Text::toString(Text::escapeNonprintable(lexer->getText())) +
                  ".");
      }

      Ref<const Exp> altern(const Ref<const Exp> &l,
                            const Ref<const Exp> &r)
      {
        if(!l) return r; // An already detected error
        if(!r) return l; // An already detected error
        return new Altern(l, r);
      }

      Ref<const Exp> empty() { return new String(); }

      Ref<const Exp> str(const Ref<const UAttr> &s)
      {
        return new String(s->value);
      }

      Ref<const Exp> any()        { return new Class(); }
      Ref<const Exp> line_begin() { return new LineBegin(); }
      Ref<const Exp> line_end()   { return new LineEnd(); }

      Ref<const Exp> word_begin()
      {
        bracket = 0;
        return new WordBegin();
      }

      Ref<const Exp> word_end()
      {
        bracket = 0;
        return new WordEnd();
      }

      Ref<const Exp> juxta(const Ref<const Exp> &l,
                           const Ref<const Exp> &r)
      {
        if(!l) return r; // An already detected error
        if(!r) return l; // An already detected error
        return new Juxta(l, r);
      }

      Ref<const Exp> repeat(const Ref<const Exp> &e,
                            const Ref<const IPAttr> &r)
      {
        if(!e || !r) return 0; // An already detected error
        return new Repeat(e, r->value.first, r->value.second);
      }

      Ref<const IPAttr> plus()
      {
        return new IPAttr(make_pair(1, -1));
      }

      Ref<const IPAttr> star()
      {
        return new IPAttr(make_pair(0, -1));
      }

      Ref<const IPAttr> option()
      {
        return new IPAttr(make_pair(0, 1));
      }

      static int parseInt(ustring s)
      {
        int v = 0;
        for(unsigned i=0; i<s.size(); ++i)
        {
          v *= 10;
          v += s[i] - '0';
        }
        return v;
      }

      Ref<const IPAttr> repeat_range(const Ref<const UAttr> &f,
                                     const Ref<const UAttr> &t)
      {
        if(!f) return 0; // An already detected error
        int a = parseInt(f->value);
        int b = t ? f==t ? a : parseInt(t->value) : -1;
        if(t && a > b)
        {
          warning("Illegal repeat range {" + Text::toString(a) + "," +
                  Text::toString(b) + "}: Lower bound is greater "
                  "than upper bound");
          swap(a, b);
        }
        return new IPAttr(make_pair(a, b));
      }

      void new_bracket()
      {
        bracket = new Class();
      }

      Ref<const Class> pos_bracket()
      {
        Ref<Class> b = bracket;
        bracket = 0;
        bool f = true;
        for(unsigned i=0; i<=Class::name_xdigit; ++i)
          if(b->namedClasses[i])
          {
            f = false;
            break;
          }
        if(b->ranges.size()==0 && f) return 0; // An already detected error
        b->invert = false;
        return b;
      }

      Ref<const Class> neg_bracket()
      {
        Ref<Class> b = bracket;
        bracket = 0;
        return b;
      }

      void named_class(const Ref<const UAttr> &n)
      {
        if(!n)
        {
          warning("Empty character class name");
          return;
        }

        const string s = Text::toString(n->value);
        const int i =
          s == "alnum" ? Class::name_alnum :
          s == "alpha" ? Class::name_alpha :
          s == "blank" ? Class::name_blank :
          s == "cntrl" ? Class::name_cntrl :
          s == "digit" ? Class::name_digit :
          s == "graph" ? Class::name_graph :
          s == "lower" ? Class::name_lower :
          s == "print" ? Class::name_print :
          s == "punct" ? Class::name_punct :
          s == "space" ? Class::name_space :
          s == "upper" ? Class::name_upper :
          s == "xdigit" ? Class::name_xdigit : -1;
        if(i==-1)
        {
          warning("Illegal character class [:" + s + ":]: Unknown name");
          return;
        }
        bracket->namedClasses[i] = true;
      }

      void bracket_range(const Ref<const UAttr> &f, const Ref<const UAttr> &t)
      {
        if(!f || !t) return; // An already detected error
        uchar u = f->value[0];
        uchar v = t->value[0];
        if(u>v)
        {
          warning("Illegal range " + Text::toString(ustring(1, u)) + "-" +
                  Text::toString(ustring(1, v)) + ": Lower endpoint is greater "
                  "than upper endpoint");
          swap(u, v);
        }
        bracket->ranges.push_back(make_pair(u, v));
      }

      Ref<const UAttr> collate(const Ref<const UAttr> &e)
      {
        const ustring s(e->value, 0, e->value.size()-1);
        if(s.size() == 0)
        {
          warning("Empty collation element");
          return 0;
        }
        if(s.size() == 1) return new UAttr(s);
        warning("Illegal collation element [." + Text::toString(s) +
                ".]: Collation elements of more than one character are not "
                "supported yet");
        return 0;
      }

      void equiv(const Ref<const UAttr> &e)
      {
        const ustring s(e->value, 0, e->value.size()-1);
        if(s.size() == 0)
        {
          warning("Empty collation element in equivalince class");
          return;
        }
        warning("Illegal equivalence class [=" + Text::toString(s) +
                "=]: Equivalence classes are not supported yet");
      }

      Ref<const Exp> named_exp(const Ref<const UAttr> &n)
      {
        if(!n) return 0; // An already detected error
        const string s = Text::toString(n->value);
        if(!env)
        {
          warning("Illegal exression reference {" + s + "}: No environment");
          return 0;
        }
        map<string, Ref<const Exp> >::const_iterator i = env->m.find(s);
        if(i == env->m.end())
        {
          warning("Illegal expression reference {" + s + "}: Undefined name");
          return 0;
        }
        return i->second;
      }
    };

    struct Regex::Parser
    {
      struct Printer: LrParserBase::Printer
      {
        virtual string print(const RefAnyConst &a) const
        {
          if(!a) return "<null>";
          if(const UAttr *b = dynamic_cast<const UAttr *>(a.get()))
            return "\"" + Text::toString(b->value) + "\"";
          if(const IPAttr *b = dynamic_cast<const IPAttr *>(a.get()))
            return "(" + Text::toString(b->value.first) + "," +
              Text::toString(b->value.second) + ")";
          if(const Exp *b = dynamic_cast<const Exp *>(a.get()))
            return b->print();
          return "<unknown>";
        }
      };

      auto_ptr<LrParserBase::Actor<ParserContext> > actor;
      auto_ptr<Printer> printer;
      auto_ptr<SlrParser> lrParser;
      int terminalMap[128];

      Parser():
        actor(new LrParserBase::Actor<ParserContext>())
      {
        CFG g(actor.get());

        const int dollar   = g.defineTerminal("$");
        const int lpar     = g.defineTerminal("(");
        const int rpar     = g.defineTerminal(")");
        const int star     = g.defineTerminal("*");
        const int plus     = g.defineTerminal("+");
        const int comma    = g.defineTerminal(",");
        const int hyphen   = g.defineTerminal("-");
        const int flstop   = g.defineTerminal(".");
        const int colon    = g.defineTerminal(":");
        const int less     = g.defineTerminal("<");
        const int equal    = g.defineTerminal("=");
        const int greater  = g.defineTerminal(">");
        const int question = g.defineTerminal("?");
        const int lbrack   = g.defineTerminal("[");
        const int backsl   = g.defineTerminal("\\");
        const int rbrack   = g.defineTerminal("]");
        const int caret    = g.defineTerminal("^");
        const int undersc  = g.defineTerminal("_");
        const int lbrace   = g.defineTerminal("{");
        const int vbar     = g.defineTerminal("|");
        const int rbrace   = g.defineTerminal("}");
        const int ALPHA    = g.defineTerminal("ALPHA");
        const int DIGIT    = g.defineTerminal("DIGIT");
        const int OTHER    = g.defineTerminal("OTHER");

        const int exp            = g.defineNonterminal("exp");
        const int branch         = g.defineNonterminal("branch");
        const int atom           = g.defineNonterminal("atom");
        const int bracket        = g.defineNonterminal("bracket");
        const int br_pos         = g.defineNonterminal("br_pos");
        const int br_char_pos    = g.defineNonterminal("br_char_pos");
        const int br_char_common = g.defineNonterminal("br_char_common");
        const int common_char    = g.defineNonterminal("common_char");
        const int br_opt1        = g.defineNonterminal("br_opt1");
        const int br_start1      = g.defineNonterminal("br_start1");
        const int br_char1       = g.defineNonterminal("br_char1");
        const int br_opt2        = g.defineNonterminal("br_opt2");
        const int br_start2      = g.defineNonterminal("br_start2");
        const int br_char2       = g.defineNonterminal("br_char2");
        const int br_end         = g.defineNonterminal("br_end");
        const int br_char_end    = g.defineNonterminal("br_char_end");
        const int br_start3      = g.defineNonterminal("br_start3");
        const int br_start4      = g.defineNonterminal("br_start4");
        const int br_collate     = g.defineNonterminal("br_collate");
        const int br_collate1    = g.defineNonterminal("br_collate1");
        const int br_collate_ch  = g.defineNonterminal("br_collate_ch");
        const int br_collate2    = g.defineNonterminal("br_collate2");
        const int br_equiv       = g.defineNonterminal("br_equiv");
        const int br_equiv1      = g.defineNonterminal("br_equiv1");
        const int br_equiv_ch    = g.defineNonterminal("br_equiv_ch");
        const int br_equiv2      = g.defineNonterminal("br_equiv2");
        const int br_class       = g.defineNonterminal("br_class");
        const int id_char_seq    = g.defineNonterminal("id_char_seq");
        const int id_char        = g.defineNonterminal("id_char");
        const int id_char_init   = g.defineNonterminal("id_char_init");
        const int br_neg         = g.defineNonterminal("br_neg");
        const int br_char_neg    = g.defineNonterminal("br_char_neg");
        const int exp_name       = g.defineNonterminal("exp_name");
        const int any_char       = g.defineNonterminal("any_char");
        const int atom_char      = g.defineNonterminal("atom_char");
        const int branch2        = g.defineNonterminal("branch2");
        const int repeat         = g.defineNonterminal("repeat");
        const int repeat_range   = g.defineNonterminal("repeat_range");
        const int integer        = g.defineNonterminal("integer");

        const int a_altern        =
          actor->registerMethod("altern",        &ParserContext::altern);
        const int a_empty         =
          actor->registerMethod("empty",         &ParserContext::empty);
        const int a_string        =
          actor->registerMethod("string",        &ParserContext::str);
        const int a_any           =
          actor->registerMethod("any",           &ParserContext::any);
        const int a_line_begin    =
          actor->registerMethod("line_begin",    &ParserContext::line_begin);
        const int a_line_end      =
          actor->registerMethod("line_end",      &ParserContext::line_end);
        const int a_word_begin    =
          actor->registerMethod("word_begin",    &ParserContext::word_begin);
        const int a_word_end      =
          actor->registerMethod("word_end",      &ParserContext::word_end);
        const int a_juxta         =
          actor->registerMethod("juxta",         &ParserContext::juxta);
        const int a_repeat        =
          actor->registerMethod("repeat",        &ParserContext::repeat);
        const int a_option        =
          actor->registerMethod("option",        &ParserContext::option);
        const int a_star          =
          actor->registerMethod("star",          &ParserContext::star);
        const int a_plus          =
          actor->registerMethod("plus",          &ParserContext::plus);
        const int a_repeat_range  =
          actor->registerMethod("repeat_range",  &ParserContext::repeat_range);
        const int a_new_bracket   =
          actor->registerMethod("new_bracket",   &ParserContext::new_bracket);
        const int a_pos_bracket   =
          actor->registerMethod("pos_bracket",   &ParserContext::pos_bracket);
        const int a_neg_bracket   =
          actor->registerMethod("neg_bracket",   &ParserContext::neg_bracket);
        const int a_named_class   =
          actor->registerMethod("named_class",   &ParserContext::named_class);
        const int a_bracket_range =
          actor->registerMethod("bracket_range", &ParserContext::bracket_range);
        const int a_collate       =
          actor->registerMethod("collate",       &ParserContext::collate);
        const int a_equiv         =
          actor->registerMethod("equiv",         &ParserContext::equiv);
        const int a_named_exp     =
          actor->registerMethod("named_exp",     &ParserContext::named_exp);

        // exp
        g.addProd(exp, CFG::nont(branch));
        g.addProd(exp, CFG::nont(exp), CFG::term(vbar), CFG::nont(branch),
                  CFG::act(a_altern, 2, 0));

        // branch
        g.addProd(branch, CFG::nont(atom));
        g.addProd(branch, CFG::nont(atom), CFG::nont(branch2), CFG::copy(0));

        // atom
        g.addProd(atom, CFG::term(lpar), CFG::term(rpar), CFG::act(a_empty));
        g.addProd(atom, CFG::term(lpar), CFG::nont(exp),
                  CFG::term(rpar), CFG::copy(1));
        g.addProd(atom, CFG::term(lbrack), CFG::act(a_new_bracket),
                  CFG::nont(bracket), CFG::term(rbrack), CFG::copy(1));
        g.addProd(atom, CFG::term(lbrace), CFG::nont(exp_name), CFG::term(rbrace),
                  CFG::act(a_named_exp, 1));
        g.addProd(atom, CFG::term(backsl), CFG::nont(any_char),
                  CFG::act(a_string, 0));
        g.addProd(atom, CFG::term(flstop),    CFG::act(a_any));
        g.addProd(atom, CFG::term(caret),     CFG::act(a_line_begin));
        g.addProd(atom, CFG::term(dollar),    CFG::act(a_line_end));
        g.addProd(atom, CFG::nont(atom_char), CFG::act(a_string, 0));

        // bracket
        g.addProd(bracket, CFG::nont(br_pos), CFG::act(a_pos_bracket));
        g.addProd(bracket, CFG::term(caret), CFG::nont(br_neg),
                  CFG::act(a_neg_bracket));
        g.addProd(bracket, CFG::term(lbrack), CFG::term(colon), CFG::term(less),
                  CFG::term(colon), CFG::term(rbrack), CFG::act(a_word_begin));
        g.addProd(bracket, CFG::term(lbrack), CFG::term(colon), CFG::term(greater),
                  CFG::term(colon), CFG::term(rbrack), CFG::act(a_word_end));

        // br_pos
        g.addProd(br_pos, CFG::nont(br_char_pos), CFG::nont(br_opt1));
        g.addProd(br_pos, CFG::nont(br_opt2));

        // br_char_pos
        g.addProd(br_char_pos, CFG::nont(br_char_common));
        g.addProd(br_char_pos, CFG::term(rbrack));
        g.addProd(br_char_pos, CFG::term(hyphen));
        g.addProd(br_char_pos, CFG::term(flstop));
        g.addProd(br_char_pos, CFG::term(equal));
        g.addProd(br_char_pos, CFG::term(colon));

        // br_char_common
        g.addProd(br_char_common, CFG::nont(common_char));
        g.addProd(br_char_common, CFG::term(vbar));
        g.addProd(br_char_common, CFG::term(lpar));
        g.addProd(br_char_common, CFG::term(rpar));
        g.addProd(br_char_common, CFG::term(lbrace));
        g.addProd(br_char_common, CFG::term(backsl));
        g.addProd(br_char_common, CFG::term(dollar));
        g.addProd(br_char_common, CFG::term(question));
        g.addProd(br_char_common, CFG::term(star));
        g.addProd(br_char_common, CFG::term(plus));

        // common_char
        g.addProd(common_char, CFG::term(rbrace));
        g.addProd(common_char, CFG::term(undersc));
        g.addProd(common_char, CFG::term(comma));
        g.addProd(common_char, CFG::term(less));
        g.addProd(common_char, CFG::term(greater));
        g.addProd(common_char, CFG::term(DIGIT));
        g.addProd(common_char, CFG::term(ALPHA));
        g.addProd(common_char, CFG::term(OTHER));

        // br_opt1
        g.addProd(br_opt1, CFG::act(a_bracket_range, 0, 0), CFG::nont(br_start1));
        g.addProd(br_opt1, CFG::term(hyphen), CFG::nont(br_end));

        // br_start1
        g.addProd(br_start1);
        g.addProd(br_start1, CFG::nont(br_char1), CFG::nont(br_opt1));
        g.addProd(br_start1, CFG::nont(br_opt2));

        // br_char1
        g.addProd(br_char1, CFG::nont(br_char_common));
        g.addProd(br_char1, CFG::term(flstop));
        g.addProd(br_char1, CFG::term(equal));
        g.addProd(br_char1, CFG::term(colon));
        g.addProd(br_char1, CFG::term(caret));

        // br_opt2
        g.addProd(br_opt2, CFG::term(lbrack), CFG::act(a_bracket_range, 0, 0),
                  CFG::nont(br_start2));
        g.addProd(br_opt2, CFG::term(lbrack), CFG::term(hyphen),
                  CFG::nont(br_end));
        g.addProd(br_opt2, CFG::nont(br_collate), CFG::nont(br_opt1));
        g.addProd(br_opt2, CFG::nont(br_equiv), CFG::nont(br_start3));
        g.addProd(br_opt2, CFG::nont(br_class), CFG::nont(br_start3));

        // br_start2
        g.addProd(br_start2);
        g.addProd(br_start2, CFG::nont(br_char2), CFG::nont(br_opt1));
        g.addProd(br_start2, CFG::nont(br_opt2));

        // br_char2
        g.addProd(br_char2, CFG::nont(br_char_common));
        g.addProd(br_char2, CFG::term(caret));

        // br_end
        g.addProd(br_end, CFG::act(a_bracket_range, 1, 1),
                  CFG::act(a_bracket_range, 1, 1));
        g.addProd(br_end, CFG::nont(br_char_end), CFG::act(a_bracket_range, 2, 0),
                  CFG::nont(br_start3));
        g.addProd(br_end, CFG::term(lbrack), CFG::act(a_bracket_range, 2, 0),
                  CFG::nont(br_start4));
        g.addProd(br_end, CFG::nont(br_collate), CFG::act(a_bracket_range, 2, 0),
                  CFG::nont(br_start3));

        // br_char_end
        g.addProd(br_char_end, CFG::nont(br_char1));
        g.addProd(br_char_end, CFG::term(hyphen));

        // br_start3
        g.addProd(br_start3, CFG::term(hyphen), CFG::act(a_bracket_range, 0, 0));
        g.addProd(br_start3, CFG::nont(br_start1));

        // br_start4
        g.addProd(br_start4, CFG::term(hyphen), CFG::act(a_bracket_range, 0, 0));
        g.addProd(br_start4, CFG::nont(br_start2));

        // br_collate
        g.addProd(br_collate, CFG::term(lbrack), CFG::term(flstop),
                  CFG::nont(br_collate1), CFG::act(a_collate, 0));

        // br_collate1
        g.addProd(br_collate1, CFG::nont(br_collate_ch), CFG::nont(br_collate1),
                  CFG::concat(1, 0));
        g.addProd(br_collate1, CFG::term(flstop), CFG::nont(br_collate2),
                  CFG::concat(1, 0));
        g.addProd(br_collate1, CFG::term(rbrack),       CFG::nont(br_collate1),
                  CFG::concat(1, 0));

        // br_collate_ch
        g.addProd(br_collate_ch, CFG::nont(br_char_common));
        g.addProd(br_collate_ch, CFG::term(lbrack));
        g.addProd(br_collate_ch, CFG::term(hyphen));
        g.addProd(br_collate_ch, CFG::term(equal));
        g.addProd(br_collate_ch, CFG::term(colon));
        g.addProd(br_collate_ch, CFG::term(caret));

        // br_collate2
        g.addProd(br_collate2, CFG::nont(br_collate_ch), CFG::nont(br_collate1),
                  CFG::concat(1, 0));
        g.addProd(br_collate2, CFG::term(flstop), CFG::nont(br_collate2),
                  CFG::concat(1, 0));
        g.addProd(br_collate2, CFG::term(rbrack), CFG::null());

        // br_equiv
        g.addProd(br_equiv, CFG::term(lbrack), CFG::term(equal),
                  CFG::nont(br_equiv1), CFG::act(a_equiv, 0));

        // br_equiv1
        g.addProd(br_equiv1, CFG::nont(br_equiv_ch), CFG::nont(br_equiv1),
                  CFG::concat(1, 0));
        g.addProd(br_equiv1, CFG::term(equal), CFG::nont(br_equiv2),
                  CFG::concat(1, 0));
        g.addProd(br_equiv1, CFG::term(rbrack), CFG::nont(br_equiv1),
                  CFG::concat(1, 0));

        // br_equiv_ch
        g.addProd(br_equiv_ch, CFG::nont(br_char_common));
        g.addProd(br_equiv_ch, CFG::term(lbrack));
        g.addProd(br_equiv_ch, CFG::term(hyphen));
        g.addProd(br_equiv_ch, CFG::term(flstop));
        g.addProd(br_equiv_ch, CFG::term(colon));
        g.addProd(br_equiv_ch, CFG::term(caret));

        // br_equiv2
        g.addProd(br_equiv2, CFG::nont(br_equiv_ch), CFG::nont(br_equiv1),
                  CFG::concat(1, 0));
        g.addProd(br_equiv2, CFG::term(equal), CFG::nont(br_equiv2),
                  CFG::concat(1, 0));
        g.addProd(br_equiv2, CFG::term(rbrack), CFG::null());

        // br_class
        g.addProd(br_class, CFG::term(lbrack), CFG::term(colon),
                  CFG::nont(id_char_seq), CFG::term(colon), CFG::term(rbrack),
                  CFG::act(a_named_class, 2));

        // id_char_seq
        g.addProd(id_char_seq);
        g.addProd(id_char_seq, CFG::nont(id_char_seq), CFG::nont(id_char),
                  CFG::concat(1, 0));

        // id_char
        g.addProd(id_char, CFG::nont(id_char_init));
        g.addProd(id_char, CFG::term(DIGIT));

        // id_char_init
        g.addProd(id_char_init, CFG::term(undersc));
        g.addProd(id_char_init, CFG::term(ALPHA));

        // br_neg
        g.addProd(br_neg, CFG::nont(br_char_neg), CFG::nont(br_opt1));
        g.addProd(br_neg, CFG::nont(br_opt2));

        // br_char_neg
        g.addProd(br_char_neg, CFG::nont(br_char_pos));
        g.addProd(br_char_neg, CFG::term(caret));

        // exp_name
        g.addProd(exp_name, CFG::nont(id_char_init), CFG::nont(id_char_seq),
                  CFG::concat(1, 0));

        // any_char
        g.addProd(any_char, CFG::nont(br_char_neg));
        g.addProd(any_char, CFG::term(lbrack));

        // atom_char
        g.addProd(atom_char, CFG::nont(common_char));
        g.addProd(atom_char, CFG::term(rbrack));
        g.addProd(atom_char, CFG::term(hyphen));
        g.addProd(atom_char, CFG::term(colon));
        g.addProd(atom_char, CFG::term(equal));

        // branch2
        g.addProd(branch2, CFG::nont(branch), CFG::act(a_juxta, 1, 0));
        g.addProd(branch2, CFG::nont(repeat), CFG::act(a_repeat, 1, 0));
        g.addProd(branch2, CFG::nont(repeat), CFG::act(a_repeat, 1, 0),
                  CFG::nont(branch), CFG::act(a_juxta, 1, 0));

        // repeat
        g.addProd(repeat, CFG::term(question), CFG::act(a_option));
        g.addProd(repeat, CFG::term(star), CFG::act(a_star));
        g.addProd(repeat, CFG::term(plus), CFG::act(a_plus));
        g.addProd(repeat, CFG::term(lbrace), CFG::nont(repeat_range),
                  CFG::term(rbrace), CFG::copy(1));

        // repeat_range
        g.addProd(repeat_range, CFG::nont(integer),
                  CFG::act(a_repeat_range, 0, 0));
        g.addProd(repeat_range, CFG::nont(integer), CFG::term(comma),
                  CFG::act(a_repeat_range, 1, -1));
        g.addProd(repeat_range, CFG::nont(integer), CFG::term(comma),
                  CFG::nont(integer), CFG::act(a_repeat_range, 2, 0));

        // integer
        g.addProd(integer, CFG::nont(integer), CFG::term(DIGIT),
                  CFG::concat(1, 0));
        g.addProd(integer, CFG::term(DIGIT));

        printer = auto_ptr<Printer>(new Printer);
        lrParser = auto_ptr<SlrParser>(new SlrParser(g, actor.get(), printer.get()));

        for(int i=0; i<128; ++i) terminalMap[i] = OTHER;
        for(int i='0'; i<='9'; ++i) terminalMap[i] = DIGIT;
        for(int i='A'; i<='Z'; ++i) terminalMap[i] = ALPHA;
        for(int i='a'; i<='z'; ++i) terminalMap[i] = ALPHA;

        terminalMap[static_cast<int>('$')] = dollar;
        terminalMap[static_cast<int>('(')] = lpar;
        terminalMap[static_cast<int>(')')] = rpar;
        terminalMap[static_cast<int>('*')] = star;
        terminalMap[static_cast<int>('+')] = plus;
        terminalMap[static_cast<int>(',')] = comma;
        terminalMap[static_cast<int>('-')] = hyphen;
        terminalMap[static_cast<int>('.')] = flstop;
        terminalMap[static_cast<int>(':')] = colon;
        terminalMap[static_cast<int>('<')] = less;
        terminalMap[static_cast<int>('=')] = equal;
        terminalMap[static_cast<int>('>')] = greater;
        terminalMap[static_cast<int>('?')] = question;
        terminalMap[static_cast<int>('[')] = lbrack;
        terminalMap[static_cast<int>('\\')] = backsl;
        terminalMap[static_cast<int>(']')] = rbrack;
        terminalMap[static_cast<int>('^')] = caret;
        terminalMap[static_cast<int>('_')] = undersc;
        terminalMap[static_cast<int>('{')] = lbrace;
        terminalMap[static_cast<int>('|')] = vbar;
        terminalMap[static_cast<int>('}')] = rbrace;
      }
    };

    struct Regex::Lexer: LexerBase
    {
      ustring s;
      unsigned i;
      const Parser &p;
      ustring text;
      int type;

      Lexer(ustring s, const Parser &p): s(s), i(0), p(p) {}

      void getNext(LexerBase::Lexeme &l)
      {
        if(i == s.size())
        {
          l.type = type = -1;
          return;
        }
        uchar c = s[i++];
        text = ustring(1, c);
        l.type  = type = p.terminalMap[c < 128 ? c : 0];
        l.value = new RefObject<ustring>(text);
      }

      ustring getText() const
      {
        return text;
      }

      int getType() const
      {
        return type;
      }
    };

    const Regex::Parser &Regex::getParser()
    {
      static Parser p;
      return p;
    } 

    void Regex::parse(ustring s, Logger *logger, const Environment *e)
    {
      const Parser &parser = getParser();
      Lexer lexer(s, parser);
      ParserContext context(&lexer, e, logger);
      parser.lrParser->parse(lexer, context, exp, logger); // Comment in the logger for debugging
      if(!exp) ARCHON_THROW1(ArgumentException,
                             "Could not make any sense of input. "
                             "Problems were reported to the logger.");
    }

    Regex Regex::repeat(Regex r, int min, int max)
    {
      if(min < 0) ARCHON_THROW1(ArgumentException, "'min' was negative");
      if(max < min) ARCHON_THROW1(ArgumentException, "'max' was less than 'min'");
      return Regex(new Repeat(r.exp, min, max));
    }

    Regex Regex::repeat(Regex r, int n, bool orMore)
    {
      if(n < 0) ARCHON_THROW1(ArgumentException, "'n' was negative");
      return Regex(new Repeat(r.exp, n, orMore ? -1 : n));
    }

    Regex Regex::bracket(const vector<pair<uchar, uchar> > &ranges,
                         const vector<string> &namedClasses,
                         bool invert)
    {
      for(unsigned i=0; i<ranges.size(); ++i)
      {
        const pair<uchar, uchar> &p = ranges[i];
        if(p.second < p.first)
          ARCHON_THROW1(ArgumentException,
                        "A range has a first component greater that "
                        "its second component");
      }
      vector<bool> n(Class::name_xdigit+1);
      for(unsigned i=0; i<namedClasses.size(); ++i)
      {
        const string &s = namedClasses[i];
        const int j =
          s == "alnum" ? Class::name_alnum :
          s == "alpha" ? Class::name_alpha :
          s == "blank" ? Class::name_blank :
          s == "cntrl" ? Class::name_cntrl :
          s == "digit" ? Class::name_digit :
          s == "graph" ? Class::name_graph :
          s == "lower" ? Class::name_lower :
          s == "print" ? Class::name_print :
          s == "punct" ? Class::name_punct :
          s == "space" ? Class::name_space :
          s == "upper" ? Class::name_upper :
          s == "xdigit" ? Class::name_xdigit : -1;
        if(j==-1)
          ARCHON_THROW1(ArgumentException, "Unknown class name \"" + s + "\"");
        n[j] = true;
      }
      if(!invert && ranges.size() == 0 && namedClasses.size() == 0)
        ARCHON_THROW1(ArgumentException, "Empty positive bracket");
      return Regex(new Class(ranges, n, invert));
    }

    void Regex::makeNfa(NFA &a, const Exp *e, int context) const
    {
      if(const Altern *f = dynamic_cast<const Altern *>(e))
      {
        if(context != 2)
        {
          makeNfa(a, f->e1.get(), context);
          makeNfa(a, f->e2.get(), 1);
          return;
        }

        NFA b;
        makeNfa(b, f->e1.get(), 0);
        makeNfa(b, f->e2.get(), 1);
        a.concat(b);
        return;
      }

      if(const Juxta *f = dynamic_cast<const Juxta *>(e))
      {
        if(context != 1)
        {
          makeNfa(a, f->e1.get(), context);
          makeNfa(a, f->e2.get(), 2);
          return;
        }

        NFA b;
        makeNfa(b, f->e1.get(), 0);
        makeNfa(b, f->e2.get(), 2);
        a.altern(b);
        return;
      }

      if(const Repeat *f = dynamic_cast<const Repeat *>(e))
      {
        //  x{n}    =  xx{n-1}      or
        //  x{n,}   =  xx{n-1,}     or
        //  x{n,m}  =  xx{n-1,m-1}  where 0 < n <= m
        if(f->min > 0)
        {
          Ref<Juxta> g =
            new Juxta(f->e, new Repeat(f->e, f->min-1, f->max == -1 ? -1 : f->max-1));
          makeNfa(a, g.get(), context);
          return;
        }

        //  x{0,n}  =  ()|xx{0,n-1}  where 0 < n
        if(f->max > 0)
        {
          Ref<Altern> g =
            new Altern(new String(), new Juxta(f->e, new Repeat(f->e, 0, f->max-1)));
          makeNfa(a, g.get(), context);
          return;
        }

        // Handle  x{0}
        if(f->max == 0) return;


        // Handle  x{0,}

        if(context == 0)
        {
          makeNfa(a, f->e.get(), 0);
          a.repeat(true);
          return;
        }

        NFA b;
        makeNfa(b, f->e.get(), 0);
        b.repeat(true);
        if(context == 1) a.altern(b);
        else a.concat(b);
        return;
      }

      if(const String *f = dynamic_cast<const String *>(e))
      {
        NFA b(f->s); // Well - its actually a coincidence that unsigned == uchar
        switch(context)
        {
        case 0: a = b;       break;
        case 1: a.altern(b); break;
        case 2: a.concat(b);  break;
        }
        return;
      }

      if(const Class *f = dynamic_cast<const Class *>(e))
      {
        for(unsigned i=0; i<f->namedClasses.size(); ++i)
          if(f->namedClasses[i])
            ARCHON_THROW1(ArgumentException, "Named classes supported yet");

        vector<pair<unsigned, unsigned> > ranges;

        if(f->invert)
        {
          ranges.push_back(make_pair(0u, 0xDFFFu));
#if !defined __GNUC__ || __GNUC__ > 2
          ranges.push_back(make_pair(0xF900, numeric_limits<unsigned>::max()));
#else
          ranges.push_back(make_pair(0xF900, UINT_MAX));
#endif
          for(unsigned i=0; i<f->ranges.size(); ++i)
          {
            const pair<uchar, uchar> &r = f->ranges[i];
            unsigned j=0;
            while(j<ranges.size() && ranges[j].second < r.first) ++j;
            if(j == ranges.size()) continue;
            if(ranges[j].first < r.first)
            {
              if(ranges[j].second > r.second)
              {
                ranges.insert(ranges.begin()+j+1, make_pair(r.second+1, ranges[j].second));
                ranges[j].second = r.first-1;
                continue;
              }
              ranges[j].second = r.first-1;
              ++j;
              if(j == ranges.size()) continue;
            }
            while(j<ranges.size() && ranges[j].second <= r.second)
              ranges.erase(ranges.begin()+j);
            if(j == ranges.size()) continue;
            if(ranges[j].first > r.second) continue;
            ranges[j].first = r.second+1;
          }
        }
        else
        {
          for(unsigned i=0; i<f->ranges.size(); ++i)
          {
            const pair<uchar, uchar> &r = f->ranges[i];
            ranges.push_back(make_pair(r.first, r.second));
          }
        }

        NFA b(ranges);

        switch(context)
        {
        case 0: a = b;       break;
        case 1: a.altern(b); break;
        case 2: a.concat(b);  break;
        }
        return;
      }

      if(dynamic_cast<const LineBegin *>(e))
      {
        NFA b(0xE000, 0xE000);
        switch(context)
        {
        case 0: a = b;       break;
        case 1: a.altern(b); break;
        case 2: a.concat(b);  break;
        }
        return;
      }


      if(dynamic_cast<const LineEnd *>(e))
      {
        NFA b(0xE001, 0xE001);
        switch(context)
        {
        case 0: a = b;       break;
        case 1: a.altern(b); break;
        case 2: a.concat(b);  break;
        }
        return;
      }

      if(dynamic_cast<const WordBegin *>(e))
      {
        NFA b(0xE002, 0xE002);
        switch(context)
        {
        case 0: a = b;       break;
        case 1: a.altern(b); break;
        case 2: a.concat(b);  break;
        }
        return;
      }


      if(dynamic_cast<const WordEnd *>(e))
      {
        NFA b(0xE003, 0xE003);
        switch(context)
        {
        case 0: a = b;       break;
        case 1: a.altern(b); break;
        case 2: a.concat(b);  break;
        }
        return;
      }

      ARCHON_THROW1(ArgumentException, "Unsupported elements in Regex");
    }

    void Regex::makeNfa(NFA &a) const
    {
      makeNfa(a, exp.get(), 0);
    }
  }
}

---