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