lib-src/automata/lrparser.cc

   1 // NOTICE:
   2 //
   3 // ADLib, Prop and their related set of tools and documentation are in the
   4 // public domain.   The author(s) of this software reserve no copyrights on
   5 // the source code and any code generated using the tools.  You are encouraged
   6 // to use ADLib and Prop to develop software, in both academic and commercial
   7 // settings, and are free to incorporate any part of ADLib and Prop into
   8 // your programs.
   9 //
  10 // Although you are under no obligation to do so, we strongly recommend that
  11 // you give away all software developed using our tools.
  12 //
  13 // We also ask that credit be given to us when ADLib and/or Prop are used in
  14 // your programs, and that this notice be preserved intact in all the source
  15 // code.
  16 //
  17 // This software is still under development and we welcome any suggestions
  18 // and help from the users.
  19 //
  20 // Allen Leung
  21 // 1994
  22 //////////////////////////////////////////////////////////////////////////////
  23
  24 #include <iostream.h>
  25 #include <string.h>
  26 #include <stdlib.h>
  27 #include <AD/automata/lrparser.h>
  28 #include <AD/contain/stack.h>
  29 #include <AD/strings/charesc.h>
  30
  31 //////////////////////////////////////////////////////////////////////////////
  32 //
  33 //  Make hidden types visible
  34 //
  35 //////////////////////////////////////////////////////////////////////////////
  36 typedef LR1Parser::Symbol           Symbol;
  37 typedef LR1Parser::ShortSymbol      ShortSymbol;
  38 typedef LR1Parser::State            State;
  39 typedef LR1Parser::Offset           Offset;
  40 typedef LR1Parser::Rule             Rule;
  41 typedef LR1Parser::ProductionLength ProductionLength;
  42
  43 //////////////////////////////////////////////////////////////////////////////
  44 //
  45 //  Constructor and destructor
  46 //
  47 //////////////////////////////////////////////////////////////////////////////
  48 LR1Parser:: LR1Parser( const Offset           base_table  [],
  49                        const State            check_table [],
  50                        const State            def_table   [],
  51                        const State            defact_table[],
  52                        const State            next_table  [],
  53                        const ProductionLength len_table   [],
  54                        const ProductionLength ncount_table[],
  55                        const ShortSymbol      lhs_table   [],
  56                        const unsigned short   equiv_table [],
  57                        Symbol                 error,
  58                        Symbol                 max_term,
  59                        Symbol                 max_nonterm
  60                      )
  61    : LR1(base_table,check_table,def_table,defact_table,next_table,
  62          len_table,ncount_table,lhs_table,equiv_table),
  63      error_token(error), max_terminal(max_term),
  64      max_non_terminal(max_nonterm), error_status(0) {}
  65
  66 LR1Parser::~LR1Parser() {}
  67
  68 //////////////////////////////////////////////////////////////////////////////
  69 //
  70 //  Default parsing actions
  71 //
  72 //////////////////////////////////////////////////////////////////////////////
  73 void LR1Parser::accept() {}
  74 void LR1Parser::parser_prefix() {}
  75 void LR1Parser::parser_suffix() {}
  76 void LR1Parser::adjust_stack(int) {}
  77 LR1Parser::ErrorAction LR1Parser::error_report(const char * message)
  78 {  cerr << message << '\n';
  79    return Abort;
  80 }
  81
  82 //////////////////////////////////////////////////////////////////////////////
  83 //
  84 //  Error repair method.  We'll just repeatedly discard input tokens until
  85 //  we reach a point when a non-error transition can be performed.
  86 //
  87 //////////////////////////////////////////////////////////////////////////////
  88 LR1Parser::ErrorAction LR1Parser::error_repair(ParserState& P)
  89 {  //
  90    //  Pop state stack until a state that shifts <error> is found.
  91    //
  92    ErrorAction my_action = error_report("parse error");
  93    error_status = &P;
  94    explain_error();
  95    State new_state;
  96    while (1)
  97    {  new_state = go(P.state,error_token);
  98       //cerr << "[state = " << P.state << "]";
  99       if (new_state != error_state &&
 100           (isShift(new_state) || isShiftReduce(new_state)))
 101          goto REPAIR_STATE_FOUND;
 102       if (P.top == 0) goto REPAIR_STATE_NOT_FOUND;
 103
 104       State old_state = P.state_stack[--P.top];
 105       Bool  pop_semantic_stack = true;
 106       for (Symbol c = EOF; c <= max_terminal; c++)
 107       {  State delta = go(old_state, c);
 108          if (delta != error_state &&
 109              ((isShift(delta) && delta == P.state) ||
 110               (isShiftReduce(delta) && state_of(delta) == P.state)))
 111          {  pop_semantic_stack = false; break; }
 112       }
 113       if (pop_semantic_stack)
 114       {  // cerr << "[pop stack]";
 115          adjust_stack(-1);
 116       }
 117       // else { cerr << "[don't pop stack]"; }
 118       P.state = old_state;
 119    }
 120
 121 REPAIR_STATE_FOUND:
 122    // Shift to the new state after <error>
 123    //cerr << "Repair state = " << new_state << '\n';
 124    if (isShift(new_state))
 125    {  // shift to new state
 126       P.state_stack[P.top++] = P.state;
 127       P.state = new_state;
 128    } else if (isShiftReduce(new_state))
 129    {  // shift to new state, then reduce immediately
 130       P.state_stack[P.top++] = P.state;
 131       P.state = state_of(new_state);
 132       new_state = defact[P.state];
 133       Rule rule = reduceRule(new_state);
 134       adjust_stack(-ncount[rule]);
 135       int length = len[rule];
 136       if (length > 0) { P.top -= length; P.state = P.state_stack[P.top]; }
 137    } else goto REPAIR_ERROR;
 138
 139    // Discard tokens until we find one that doesn't cause an error.
 140    while (1)
 141    {  Symbol token = P.token_count > 0 ? P.token_stack[--P.token_count]
 142                                        : get_token();
 143       new_state = go(P.state, token);
 144       if (new_state != error_state)
 145       {  P.token_stack[P.token_count++] = token;
 146          break;
 147       }
 148       if (token == EOF) goto REPAIR_NOT_POSSIBLE;
 149       //cerr << "[Discarding " << token << "]";
 150    }
 151
 152    return my_action;
 153
 154 REPAIR_STATE_NOT_FOUND:
 155    // error_report("Syntax error");
 156    return Abort;
 157 REPAIR_NOT_POSSIBLE:
 158    // error_report("Syntax error(no repair possible)");
 159    return Abort;
 160 REPAIR_ERROR:
 161    // error_report("Syntax error(error in repair)");
 162    return Abort;
 163 }
 164
 165 //////////////////////////////////////////////////////////////////////////////
 166 //
 167 //  Default symbol printing method.  Should be redefined by user.
 168 //
 169 //////////////////////////////////////////////////////////////////////////////
 170 void LR1Parser::print_symbol(ostream& f, Symbol S)
 171 {  if (S < 0) f << "<eof>";
 172    else if (S < 256) f << '\'' << print_char((char)S) << '\'';
 173    else if (S <= max_terminal) print_user_symbol(f,S);
 174    else f << "[token " << (int)S << "]";
 175 }
 176
 177 void LR1Parser::print_user_symbol(ostream& f, Symbol S)
 178 {  f << "[token " << (int)S << "]"; }
 179
 180 //////////////////////////////////////////////////////////////////////////////
 181 //
 182 //  Default method does not explain anything
 183 //
 184 //////////////////////////////////////////////////////////////////////////////
 185 void LR1Parser::explain_error()
 186 {
 187 }
 188
 189 //////////////////////////////////////////////////////////////////////////////
 190 //
 191 //  This method prints out the expected tokens.
 192 //
 193 //////////////////////////////////////////////////////////////////////////////
 194 void LR1Parser::nice_explain(ostream& f)
 195 {
 196    f << "expecting: ";
 197    for (Symbol c = 0; c <= max_terminal; c++)
 198    {  State delta = go(error_status->state, c);
 199       if (delta != error_state)
 200       {  // if (isShift(delta) || isShiftReduce(delta))
 201          {  print_symbol(f,c); f << ' '; }
 202       }
 203    }
 204 }
 205
 206 //////////////////////////////////////////////////////////////////////////////
 207 //
 208 //  This method explains things in great detail.
 209 //
 210 //////////////////////////////////////////////////////////////////////////////
 211 void LR1Parser::debug_explain(ostream& f)
 212 {  if (error_status == 0) return;
 213    int j;
 214
 215    f << "Tokens: ";
 216    for (j = error_status->token_count - 1; j >= 0; j--)
 217    {  print_symbol(f,error_status->token_stack[j]); f << " "; }
 218
 219    f << "\nState stack: ";
 220    for (j = error_status->top - 1; j >= 0; j--)
 221    {  f << "<" << error_status->state_stack[j] << "> "; }
 222
 223    f << "\nAt state <" << error_status->state << ">:\n";
 224
 225    Bool one_reduce = defact[error_status->state];
 226
 227    for (Symbol c = 0; c <= max_non_terminal; c++)
 228    {  State delta = go(error_status->state, c);
 229       if (delta != error_state)
 230       {  if (isShift(delta))
 231          {  f << "\tOn "; print_symbol(f,c);
 232             f << " shift, and goto state <" << delta << ">\n";
 233          } else if (isShiftReduce(delta))
 234          {  f << "\tOn "; print_symbol(f,c);
 235             Rule r = reduceRule(defaultAction(state_of(delta)));
 236             f << " shift, goto state <" << state_of(delta)
 237               << "> and reduce using rule {" << r
 238               << "}, lhs = " << lhs[r];
 239             f << " length = " << reduceLen(r) << "\n";
 240          } else if (! one_reduce)
 241          {  f << "\tOn "; print_symbol(f,c);
 242             Rule r = reduceRule(delta);
 243             f << " reduce using rule {" << r
 244               << "}, lhs = " << lhs[r];
 245             f << " length = " << reduceLen(r) << "\n";
 246          }
 247       }
 248    }
 249    if (one_reduce)
 250    {  Rule r = reduceRule(one_reduce);
 251       f << "\tOn <default> reduce using rule {"
 252         << reduceRule(one_reduce)
 253         << "}, lhs = " << lhs[r];
 254       f << " length = " << reduceLen(r) << "\n";
 255    }
 256    if (error_status->token_count > 0)
 257    {  Symbol token     = error_status->token_stack[error_status->token_count-1];
 258       State  new_state = go(error_status->state,token);
 259       f << "\tToken = "; print_symbol(f,token);
 260       f << "(" << token << ", equiv = " << equiv_classes[token-EOF] << ")";
 261       f << " new state = " << new_state << "\n";
 262       f << "\tMax_non_terminal = " << max_non_terminal << "\n";
 263       f << "\tMax_terminal = " << max_terminal << "\n";
 264    }
 265 }