include/AD/automata/lrparser.h.old

   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_full_parser_h
  26 #define LR1_full_parser_h
  27
  28 #include <iostream.h>
  29 #include <AD/automata/lr1.h>
  30
  31 //////////////////////////////////////////////////////////////////////////////
  32 //  This base class is an abstract datatype representing a full LR(1)-based
  33 //  parser with semantics stack manipulation methods.
  34 //////////////////////////////////////////////////////////////////////////////
  35 class LR1Parser : public LR1 {
  36
  37    LR1Parser(const LR1Parser&);          // no copy constructor
  38    void operator = (const LR1Parser&);   // no assignment
  39
  40 public:
  41
  42    ///////////////////////////////////////////////////////////////////////////
  43    //  Make inherited types visible
  44    ///////////////////////////////////////////////////////////////////////////
  45    typedef LR1                     Super;
  46    typedef Super::Symbol           Symbol;
  47    typedef Super::State            State;
  48    typedef Super::Offset           Offset;
  49    typedef Super::Rule             Rule;
  50    typedef Super::ProductionLength ProductionLength;
  51    enum ErrorAction
  52    {  Abort,
  53       Retry
  54    };
  55
  56    struct ParserState
  57    {  int      token_count;  // tokens on stack
  58       Symbol * token_stack;  // token stack
  59       State    state;        // current state
  60       int      top;          // top of the state stack
  61       State  * state_stack;  // state stack
  62    };
  63
  64 public:
  65
  66    ///////////////////////////////////////////////////////////////////////////
  67    // Parsing actions (overridable by derived classes)
  68    ///////////////////////////////////////////////////////////////////////////
  69    virtual void accept();               // accept the parse
  70    virtual ErrorAction error_report(const char * message);
  71    virtual ErrorAction error_repair(ParserState&);
  72    virtual void        adjust_stack(int);
  73
  74 protected:
  75
  76    virtual void parser_prefix();
  77    virtual void parser_suffix();
  78    Symbol  error_token;
  79
  80 public:
  81
  82    ///////////////////////////////////////////////////////////////////////////
  83    //  Constructor and destructor
  84    ///////////////////////////////////////////////////////////////////////////
  85
  86    LR1Parser( const Offset           base_table  [],
  87               const State            check_table [],
  88               const State            defact_table[],
  89               const State            next_table  [],
  90               const ProductionLength len_table   [],
  91               const ProductionLength ncount_table[],
  92               const ShortSymbol      lhs_table   [],
  93               const unsigned short   equiv_table [],
  94               Symbol                 error
  95             );
  96
  97    virtual ~LR1Parser();
  98    inline Symbol error_symbol() const { return error_token; }
  99    virtual int get_token () = 0;
 100
 101    ///////////////////////////////////////////////////////////////////////////
 102    //  Parsing
 103    ///////////////////////////////////////////////////////////////////////////
 104    virtual void parse() = 0;
 105 };
 106
 107 template <class P, LR1Parser::State final_state>
 108 class LR1ParserDriver
 109 {
 110 public:
 111    void driver
 112    (P&                                parser,
 113     const LR1Parser::Offset           base  [],
 114     const LR1Parser::State            check [],
 115     const LR1Parser::State            defact[],
 116     const LR1Parser::State            next  [],
 117     const LR1Parser::ProductionLength len   [],
 118     const LR1Parser::ProductionLength ncount[],
 119     const LR1Parser::ShortSymbol      lhs   [],
 120     const unsigned short              equiv []
 121    );
 122 };
 123
 124 //////////////////////////////////////////////////////////////////////////////
 125 //
 126 //  LR(1) parser driver method
 127 //
 128 //////////////////////////////////////////////////////////////////////////////
 129 template <class P, LR1Parser::State final_state>
 130 inline void LR1ParserDriver<P,final_state>::driver
 131    (P&                                parser,
 132     const LR1Parser::Offset           base  [],
 133     const LR1Parser::State            check [],
 134     const LR1Parser::State            defact[],
 135     const LR1Parser::State            next  [],
 136     const LR1Parser::ProductionLength len   [],
 137     const LR1Parser::ProductionLength ncount[],
 138     const LR1Parser::ShortSymbol      lhs   [],
 139     const unsigned short              equiv []
 140    )
 141 {  typedef LR1Parser::Symbol Symbol;
 142    typedef LR1Parser::State  State;
 143    typedef LR1Parser::Offset Offset;
 144    typedef LR1Parser::Rule   Rule;
 145
 146    int    token_count;        // tokens on stack
 147    Symbol token_stack[256];   // token stack
 148    State  state;              // current state
 149    int    top;                // top of the state stack
 150    State  state_stack[1024];  // state stack
 151
 152    ///////////////////////////////////////////////////////////////////////////
 153    // Initialization
 154    ///////////////////////////////////////////////////////////////////////////
 155    state       = LR1Parser::start_state;
 156    token_count = 0;
 157    top         = 0;
 158
 159    ///////////////////////////////////////////////////////////////////////////
 160    // The parsing loop
 161    ///////////////////////////////////////////////////////////////////////////
 162    for (;;)
 163    {  Symbol token = token_count > 0 ? token_stack[--token_count]
 164                                      : parser.get_token();
 165       State  new_state = parser.go(state, token);
 166       Bool   shift_state = false;
 167
 168       // Process state
 169       for (;;)
 170       {  if (new_state == LR1Parser::error_state)
 171          {  // parse error
 172             LR1Parser::ParserState parser_state;
 173             token_stack[token_count++] = token;
 174             parser_state.token_count = token_count;
 175             parser_state.token_stack = token_stack;
 176             parser_state.state       = state;
 177             parser_state.top         = top;
 178             parser_state.state_stack = state_stack;
 179             switch (parser.error_repair(parser_state))
 180             {  case LR1Parser::Abort: goto FINISH;
 181                default:;
 182             }
 183             token_count = parser_state.token_count;
 184             state       = parser_state.state;
 185             top         = parser_state.top;
 186             break;
 187          } else if (new_state == final_state)
 188          {  // parse succeeds
 189             goto DONE;
 190          } else if (LR1::isShift(new_state))
 191          {  // shift token
 192             if (shift_state) state_stack[top++] = state;
 193             state = new_state;
 194             break;
 195          } else
 196          {  if (LR1::isShiftReduce(new_state))
 197             {  // shift token then immediately reduce.
 198                // no token to save.
 199                if (shift_state) state_stack[top++] = state;
 200                new_state = LR1::state_of(new_state);
 201                new_state = defact[new_state];
 202                //state = LR1::state_of(new_state);
 203                //new_state = defact[state];
 204             } else
 205             {  // reduce only.
 206                // save lookahead token.
 207                //state = state_stack[--top];
 208                token_stack[token_count++] = token;
 209             }
 210             Rule rule = parser.reduceRule(new_state);
 211             parser.action_driver(rule);
 212             int length = ncount[rule];
 213             if (length > 0) { top -= length; state = state_stack[top]; }
 214             Offset offset;
 215             if (check[offset = base[state] + lhs[rule]] == state)
 216                new_state = next[offset];
 217             else
 218                new_state = defact[state];
 219             shift_state = true;
 220          }
 221       }
 222    }
 223 DONE:
 224    parser.accept();
 225 FINISH:
 226    ;
 227 }
 228
 229 #endif