include/AD/automata/lr1.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef LR1_parser_h
  26 #define LR1_parser_h
  27
  28 #include <iostream.h>
  29 #include <AD/generic/generic.h>    // generic definitions
  30 #include <AD/automata/dfatable.h>  // Compressed DFA tables
  31
  32 //////////////////////////////////////////////////////////////////////////////
  33 //  Class |LR1| represents a bareboned LR(1) parser driver.
  34 //  The compression algorithm is assumed to be the one as implemented
  35 //  in class DenseDFA.
  36 //////////////////////////////////////////////////////////////////////////////
  37
  38 class LR1 : public DFATables {
  39
  40    LR1(const LR1&);                // no copy constructor
  41    void operator = (const LR1&);   // no assignment
  42
  43 public:
  44
  45    ///////////////////////////////////////////////////////////////////////////
  46    //  Import some types
  47    ///////////////////////////////////////////////////////////////////////////
  48    typedef DFATables               Super;
  49    typedef Super::Symbol           Symbol;
  50    typedef Super::Offset           Offset;
  51    typedef Super::State            State;
  52    typedef Super::ShortSymbol      ShortSymbol;
  53    typedef Super::Rule             Rule;
  54    typedef Super::ProductionLength ProductionLength;
  55
  56    ///////////////////////////////////////////////////////////////////////////
  57    //  Parsing actions:
  58    //    (i)   parse error encountered
  59    //    (ii)  a complete parse has been constructed
  60    //    (iii) shift token onto parse stack
  61    //    (iv)  reduce using production
  62    ///////////////////////////////////////////////////////////////////////////
  63    enum Action { Error, Accept, Shift, Reduce };
  64
  65    ///////////////////////////////////////////////////////////////////////////
  66    // Common states
  67    // and other common constants
  68    ///////////////////////////////////////////////////////////////////////////
  69    enum LR1_constants { error_state           = 0,
  70                         start_state           = 1,
  71                         Parse_stack_size      = 2048,
  72                         Parse_stack_increment = 1024
  73                       };
  74
  75 protected:
  76
  77    ///////////////////////////////////////////////////////////////////////////
  78    //  Compressed state and transition tables.
  79    //
  80    //  A note concerning the interpretation of these tables:
  81    //
  82    //    base[]   is indexed by the state number.
  83    //    check[]  is indexed by the state number.
  84    //    next[]   is the next transition state indexed by the offset.
  85    //
  86    //   The offset of state 's' with input symbol 'c' is
  87    //       base[s] + c   iff    check[base[s] + c] == s
  88    //
  89    //  Notice that the next[] table is actually a combination of the
  90    //  ``action'' and ``goto'' table in LR parsing, and
  91    //  should be interpreted in the following manner:
  92    //
  93    //  Let n = next[base[s] + c]
  94    //     (a) n == 0                parse error
  95    //     (b) n > 0 && n < 32768    shift symbol and goto state n
  96    //     (c) n >= 32768
  97    //        reduce using production rule r = n - 32768 and where
  98    //        len[r] is the length of the production.
  99    ///////////////////////////////////////////////////////////////////////////
 100
 101    const Offset           * const base;
 102    const State            * const check;
 103    const State            * const def;
 104    const State            * const defact;
 105    const State            * const next;
 106    const ProductionLength * const len;
 107    const ProductionLength * const ncount;
 108    const ShortSymbol      * const lhs;
 109    const unsigned short   * const equiv_classes;
 110
 111 public:
 112
 113    ///////////////////////////////////////////////////////////////////////////
 114    //  Constructor and destructor
 115    ///////////////////////////////////////////////////////////////////////////
 116    inline
 117    LR1( const Offset           base_table  [],
 118         const State            check_table [],
 119         const State            def_table   [],
 120         const State            defact_table[],
 121         const State            next_table  [],
 122         const ProductionLength len_table   [],
 123         const ProductionLength ncount_table[],
 124         const ShortSymbol      lhs_table   [],
 125         const unsigned short   equiv_table []
 126       )
 127      : base(base_table), check(check_table), def(def_table),
 128        defact(defact_table), next(next_table), len(len_table),
 129        ncount(ncount_table), lhs(lhs_table),
 130        equiv_classes(equiv_table) {}
 131
 132    ///////////////////////////////////////////////////////////////////////////
 133    // Our convention:
 134    //    State 0 is the unique error state.
 135    //    State n, n < 32768 are shifting actions.
 136    //    State n, n >= 32768 are reducing actions.
 137    //    State n, n >= 32768 + 16384 are single reducing actions.
 138    ///////////////////////////////////////////////////////////////////////////
 139    inline static Bool isShift          (State s) { return s < 0x4000; }
 140    inline static Bool isReduce         (State s) { return s >= 0x8000; }
 141    inline static Bool isSingleReduce   (State s) { return s >= 0xc000; }
 142    inline static Bool isShiftReduce    (State s) { return s & 0x4000; }
 143    inline static Bool isError          (State s) { return s == 0; }
 144    inline static Rule reduceRule       (State s) { return s & 0x3fff; }
 145    inline static Rule singleReduceRule (State s) { return s & 0x3fff; }
 146    inline static State state_of        (State s) { return s & 0x3fff; }
 147    inline int  reduceLen        (Rule  r) const { return len[r]; }
 148    inline int  reduceNcount     (Rule  r) const { return ncount[r]; }
 149    inline State  defaultAction  (State s) const { return defact[s]; }
 150
 151    ///////////////////////////////////////////////////////////////////////////
 152    //  State transitions
 153    ///////////////////////////////////////////////////////////////////////////
 154    inline State go (State s, Symbol c) const
 155    {  register int offset;
 156       register int disp  = equiv_classes[c-EOF];
 157       register int state = s;
 158       while (check[offset = base[state] + disp] != state)
 159       {  register int new_state = def[state];
 160          if (new_state == error_state) return defact[s];
 161          state = new_state;
 162       }
 163       return ((state = next[offset]) == error_state) ? defact[s] : state;
 164    }
 165    inline State go_rule (State s, Rule r) const
 166    {  register int offset;
 167       register int disp  = lhs[r];
 168       register int state = s;
 169       while (check[offset = base[state] + disp] != state)
 170       {  register int new_state = def[state];
 171          if (new_state == error_state) return defact[s];
 172          state = new_state;
 173       }
 174       return ((state = next[offset]) == error_state) ? defact[s] : state;
 175    }
 176 };
 177
 178 #endif