Robust/cup/java_cup/runtime/lr_parser.java

   1
   2 package java_cup.runtime;
   3
   4 import java.util.Stack;
   5
   6 /** This class implements a skeleton table driven LR parser.  In general,
   7  *  LR parsers are a form of bottom up shift-reduce parsers.  Shift-reduce
   8  *  parsers act by shifting input onto a parse stack until the Symbols
   9  *  matching the right hand side of a production appear on the top of the
  10  *  stack.  Once this occurs, a reduce is performed.  This involves removing
  11  *  the Symbols corresponding to the right hand side of the production
  12  *  (the so called "handle") and replacing them with the non-terminal from
  13  *  the left hand side of the production.  <p>
  14  *
  15  *  To control the decision of whether to shift or reduce at any given point,
  16  *  the parser uses a state machine (the "viable prefix recognition machine"
  17  *  built by the parser generator).  The current state of the machine is placed
  18  *  on top of the parse stack (stored as part of a Symbol object representing
  19  *  a terminal or non terminal).  The parse action table is consulted
  20  *  (using the current state and the current lookahead Symbol as indexes) to
  21  *  determine whether to shift or to reduce.  When the parser shifts, it
  22  *  changes to a new state by pushing a new Symbol (containing a new state)
  23  *  onto the stack.  When the parser reduces, it pops the handle (right hand
  24  *  side of a production) off the stack.  This leaves the parser in the state
  25  *  it was in before any of those Symbols were matched.  Next the reduce-goto
  26  *  table is consulted (using the new state and current lookahead Symbol as
  27  *  indexes) to determine a new state to go to.  The parser then shifts to
  28  *  this goto state by pushing the left hand side Symbol of the production
  29  *  (also containing the new state) onto the stack.<p>
  30  *
  31  *  This class actually provides four LR parsers.  The methods parse() and
  32  *  debug_parse() provide two versions of the main parser (the only difference
  33  *  being that debug_parse() emits debugging trace messages as it parses).
  34  *  In addition to these main parsers, the error recovery mechanism uses two
  35  *  more.  One of these is used to simulate "parsing ahead" in the input
  36  *  without carrying out actions (to verify that a potential error recovery
  37  *  has worked), and the other is used to parse through buffered "parse ahead"
  38  *  input in order to execute all actions and re-synchronize the actual parser
  39  *  configuration.<p>
  40  *
  41  *  This is an abstract class which is normally filled out by a subclass
  42  *  generated by the JavaCup parser generator.  In addition to supplying
  43  *  the actual parse tables, generated code also supplies methods which
  44  *  invoke various pieces of user supplied code, provide access to certain
  45  *  special Symbols (e.g., EOF and error), etc.  Specifically, the following
  46  *  abstract methods are normally supplied by generated code:
  47  *  <dl compact>
  48  *  <dt> short[][] production_table()
  49  *  <dd> Provides a reference to the production table (indicating the index of
  50  *       the left hand side non terminal and the length of the right hand side
  51  *       for each production in the grammar).
  52  *  <dt> short[][] action_table()
  53  *  <dd> Provides a reference to the parse action table.
  54  *  <dt> short[][] reduce_table()
  55  *  <dd> Provides a reference to the reduce-goto table.
  56  *  <dt> int start_state()
  57  *  <dd> Indicates the index of the start state.
  58  *  <dt> int start_production()
  59  *  <dd> Indicates the index of the starting production.
  60  *  <dt> int EOF_sym()
  61  *  <dd> Indicates the index of the EOF Symbol.
  62  *  <dt> int error_sym()
  63  *  <dd> Indicates the index of the error Symbol.
  64  *  <dt> Symbol do_action()
  65  *  <dd> Executes a piece of user supplied action code.  This always comes at
  66  *       the point of a reduce in the parse, so this code also allocates and
  67  *       fills in the left hand side non terminal Symbol object that is to be
  68  *       pushed onto the stack for the reduce.
  69  *  <dt> void init_actions()
  70  *  <dd> Code to initialize a special object that encapsulates user supplied
  71  *       actions (this object is used by do_action() to actually carry out the
  72  *       actions).
  73  *  </dl>
  74  *
  75  *  In addition to these routines that <i>must</i> be supplied by the
  76  *  generated subclass there are also a series of routines that <i>may</i>
  77  *  be supplied.  These include:
  78  *  <dl>
  79  *  <dt> Symbol scan()
  80  *  <dd> Used to get the next input Symbol from the scanner.
  81  *  <dt> Scanner getScanner()
  82  *  <dd> Used to provide a scanner for the default implementation of
  83  *       scan().
  84  *  <dt> int error_sync_size()
  85  *  <dd> This determines how many Symbols past the point of an error
  86  *       must be parsed without error in order to consider a recovery to
  87  *       be valid.  This defaults to 3.  Values less than 2 are not
  88  *       recommended.
  89  *  <dt> void report_error(String message, Object info)
  90  *  <dd> This method is called to report an error.  The default implementation
  91  *       simply prints a message to System.err and where the error occurred.
  92  *       This method is often replaced in order to provide a more sophisticated
  93  *       error reporting mechanism.
  94  *  <dt> void report_fatal_error(String message, Object info)
  95  *  <dd> This method is called when a fatal error that cannot be recovered from
  96  *       is encountered.  In the default implementation, it calls
  97  *       report_error() to emit a message, then throws an exception.
  98  *  <dt> void syntax_error(Symbol cur_token)
  99  *  <dd> This method is called as soon as syntax error is detected (but
 100  *       before recovery is attempted).  In the default implementation it
 101  *       invokes: report_error("Syntax error", null);
 102  *  <dt> void unrecovered_syntax_error(Symbol cur_token)
 103  *  <dd> This method is called if syntax error recovery fails.  In the default
 104  *       implementation it invokes:<br>
 105  *         report_fatal_error("Couldn't repair and continue parse", null);
 106  *  </dl>
 107  *
 108  * @see     java_cup.runtime.Symbol
 109  * @see     java_cup.runtime.Symbol
 110  * @see     java_cup.runtime.virtual_parse_stack
 111  * @version last updated: 7/3/96
 112  * @author  Frank Flannery
 113  */
 114
 115 public abstract class lr_parser {
 116
 117   /*-----------------------------------------------------------*/
 118   /*--- Constructor(s) ----------------------------------------*/
 119   /*-----------------------------------------------------------*/
 120
 121   /** Simple constructor. */
 122   public lr_parser()
 123     {
 124       /* nothing to do here */
 125     }
 126
 127   /** Constructor that sets the default scanner. [CSA/davidm] */
 128   public lr_parser(Scanner s) {
 129     this(); /* in case default constructor someday does something */
 130     setScanner(s);
 131   }
 132
 133   /*-----------------------------------------------------------*/
 134   /*--- (Access to) Static (Class) Variables ------------------*/
 135   /*-----------------------------------------------------------*/
 136
 137   /** The default number of Symbols after an error we much match to consider
 138    *  it recovered from.
 139    */
 140   protected final static int _error_sync_size = 3;
 141
 142   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 143
 144   /** The number of Symbols after an error we much match to consider it
 145    *  recovered from.
 146    */
 147   protected int error_sync_size() {return _error_sync_size; }
 148
 149   /*-----------------------------------------------------------*/
 150   /*--- (Access to) Instance Variables ------------------------*/
 151   /*-----------------------------------------------------------*/
 152
 153   /** Table of production information (supplied by generated subclass).
 154    *  This table contains one entry per production and is indexed by
 155    *  the negative-encoded values (reduce actions) in the action_table.
 156    *  Each entry has two parts, the index of the non-terminal on the
 157    *  left hand side of the production, and the number of Symbols
 158    *  on the right hand side.
 159    */
 160   public abstract short[][] production_table();
 161
 162   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 163
 164   /** The action table (supplied by generated subclass).  This table is
 165    *  indexed by state and terminal number indicating what action is to
 166    *  be taken when the parser is in the given state (i.e., the given state
 167    *  is on top of the stack) and the given terminal is next on the input.
 168    *  States are indexed using the first dimension, however, the entries for
 169    *  a given state are compacted and stored in adjacent index, value pairs
 170    *  which are searched for rather than accessed directly (see get_action()).
 171    *  The actions stored in the table will be either shifts, reduces, or
 172    *  errors.  Shifts are encoded as positive values (one greater than the
 173    *  state shifted to).  Reduces are encoded as negative values (one less
 174    *  than the production reduced by).  Error entries are denoted by zero.
 175    *
 176    * @see java_cup.runtime.lr_parser#get_action
 177    */
 178   public abstract short[][] action_table();
 179
 180   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 181
 182   /** The reduce-goto table (supplied by generated subclass).  This
 183    *  table is indexed by state and non-terminal number and contains
 184    *  state numbers.  States are indexed using the first dimension, however,
 185    *  the entries for a given state are compacted and stored in adjacent
 186    *  index, value pairs which are searched for rather than accessed
 187    *  directly (see get_reduce()).  When a reduce occurs, the handle
 188    *  (corresponding to the RHS of the matched production) is popped off
 189    *  the stack.  The new top of stack indicates a state.  This table is
 190    *  then indexed by that state and the LHS of the reducing production to
 191    *  indicate where to "shift" to.
 192    *
 193    * @see java_cup.runtime.lr_parser#get_reduce
 194    */
 195   public abstract short[][] reduce_table();
 196
 197   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 198
 199   /** The index of the start state (supplied by generated subclass). */
 200   public abstract int start_state();
 201
 202   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 203
 204   /** The index of the start production (supplied by generated subclass). */
 205   public abstract int start_production();
 206
 207   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 208
 209   /** The index of the end of file terminal Symbol (supplied by generated
 210    *  subclass).
 211    */
 212   public abstract int EOF_sym();
 213
 214   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 215
 216   /** The index of the special error Symbol (supplied by generated subclass). */
 217   public abstract int error_sym();
 218
 219   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 220
 221   /** Internal flag to indicate when parser should quit. */
 222   protected boolean _done_parsing = false;
 223
 224   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 225
 226   /** This method is called to indicate that the parser should quit.  This is
 227    *  normally called by an accept action, but can be used to cancel parsing
 228    *  early in other circumstances if desired.
 229    */
 230   public void done_parsing()
 231     {
 232       _done_parsing = true;
 233     }
 234
 235   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 236   /* Global parse state shared by parse(), error recovery, and
 237    * debugging routines */
 238   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 239
 240   /** Indication of the index for top of stack (for use by actions). */
 241   protected int tos;
 242
 243   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 244
 245   /** The current lookahead Symbol. */
 246   protected Symbol cur_token;
 247
 248   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 249
 250   /** The parse stack itself. */
 251   protected Stack stack = new Stack();
 252
 253   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 254
 255   /** Direct reference to the production table. */
 256   protected short[][] production_tab;
 257
 258   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 259
 260   /** Direct reference to the action table. */
 261   protected short[][] action_tab;
 262
 263   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 264
 265   /** Direct reference to the reduce-goto table. */
 266   protected short[][] reduce_tab;
 267
 268   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 269
 270   /** This is the scanner object used by the default implementation
 271    *  of scan() to get Symbols.  To avoid name conflicts with existing
 272    *  code, this field is private. [CSA/davidm] */
 273   private Scanner _scanner;
 274
 275   /**
 276    * Simple accessor method to set the default scanner.
 277    */
 278   public void setScanner(Scanner s) { _scanner = s; }
 279
 280   /**
 281    * Simple accessor method to get the default scanner.
 282    */
 283   public Scanner getScanner() { return _scanner; }
 284
 285   /*-----------------------------------------------------------*/
 286   /*--- General Methods ---------------------------------------*/
 287   /*-----------------------------------------------------------*/
 288
 289   /** Perform a bit of user supplied action code (supplied by generated
 290    *  subclass).  Actions are indexed by an internal action number assigned
 291    *  at parser generation time.
 292    *
 293    * @param act_num   the internal index of the action to be performed.
 294    * @param parser    the parser object we are acting for.
 295    * @param stack     the parse stack of that object.
 296    * @param top       the index of the top element of the parse stack.
 297    */
 298   public abstract Symbol do_action(
 299     int       act_num,
 300     lr_parser parser,
 301     Stack     stack,
 302     int       top)
 303     throws java.lang.Exception;
 304
 305   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 306
 307   /** User code for initialization inside the parser.  Typically this
 308    *  initializes the scanner.  This is called before the parser requests
 309    *  the first Symbol.  Here this is just a placeholder for subclasses that
 310    *  might need this and we perform no action.   This method is normally
 311    *  overridden by the generated code using this contents of the "init with"
 312    *  clause as its body.
 313    */
 314   public void user_init() throws java.lang.Exception { }
 315
 316   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 317
 318   /** Initialize the action object.  This is called before the parser does
 319    *  any parse actions. This is filled in by generated code to create
 320    *  an object that encapsulates all action code.
 321    */
 322   protected abstract void init_actions() throws java.lang.Exception;
 323
 324   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 325
 326   /** Get the next Symbol from the input (supplied by generated subclass).
 327    *  Once end of file has been reached, all subsequent calls to scan
 328    *  should return an EOF Symbol (which is Symbol number 0).  By default
 329    *  this method returns getScanner().next_token(); this implementation
 330    *  can be overriden by the generated parser using the code declared in
 331    *  the "scan with" clause.  Do not recycle objects; every call to
 332    *  scan() should return a fresh object.
 333    */
 334   public Symbol scan() throws java.lang.Exception {
 335     Symbol sym = getScanner().next_token();
 336     return (sym!=null) ? sym : new Symbol(EOF_sym());
 337   }
 338
 339   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 340
 341   /** Report a fatal error.  This method takes a  message string and an
 342    *  additional object (to be used by specializations implemented in
 343    *  subclasses).  Here in the base class a very simple implementation
 344    *  is provided which reports the error then throws an exception.
 345    *
 346    * @param message an error message.
 347    * @param info    an extra object reserved for use by specialized subclasses.
 348    */
 349   public void report_fatal_error(
 350     String   message,
 351     Object   info)
 352     throws java.lang.Exception
 353     {
 354       /* stop parsing (not really necessary since we throw an exception, but) */
 355       done_parsing();
 356
 357       /* use the normal error message reporting to put out the message */
 358       report_error(message, info);
 359
 360       /* throw an exception */
 361       throw new Exception("Can't recover from previous error(s)");
 362     }
 363
 364   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 365
 366   /** Report a non fatal error (or warning).  This method takes a message
 367    *  string and an additional object (to be used by specializations
 368    *  implemented in subclasses).  Here in the base class a very simple
 369    *  implementation is provided which simply prints the message to
 370    *  System.err.
 371    *
 372    * @param message an error message.
 373    * @param info    an extra object reserved for use by specialized subclasses.
 374    */
 375   public void report_error(String message, Object info)
 376     {
 377       System.err.print(message);
 378       if (info instanceof Symbol)
 379         if (((Symbol)info).left != -1)
 380         System.err.println(" at character " + ((Symbol)info).left +
 381                            " of input");
 382         else System.err.println("");
 383       else System.err.println("");
 384     }
 385
 386   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 387
 388   /** This method is called when a syntax error has been detected and recovery
 389    *  is about to be invoked.  Here in the base class we just emit a
 390    *  "Syntax error" error message.
 391    *
 392    * @param cur_token the current lookahead Symbol.
 393    */
 394   public void syntax_error(Symbol cur_token)
 395     {
 396       report_error("Syntax error", cur_token);
 397     }
 398
 399   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 400
 401   /** This method is called if it is determined that syntax error recovery
 402    *  has been unsuccessful.  Here in the base class we report a fatal error.
 403    *
 404    * @param cur_token the current lookahead Symbol.
 405    */
 406   public void unrecovered_syntax_error(Symbol cur_token)
 407     throws java.lang.Exception
 408     {
 409       report_fatal_error("Couldn't repair and continue parse", cur_token);
 410     }
 411
 412   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 413
 414   /** Fetch an action from the action table.  The table is broken up into
 415    *  rows, one per state (rows are indexed directly by state number).
 416    *  Within each row, a list of index, value pairs are given (as sequential
 417    *  entries in the table), and the list is terminated by a default entry
 418    *  (denoted with a Symbol index of -1).  To find the proper entry in a row
 419    *  we do a linear or binary search (depending on the size of the row).
 420    *
 421    * @param state the state index of the action being accessed.
 422    * @param sym   the Symbol index of the action being accessed.
 423    */
 424   protected final short get_action(int state, int sym)
 425     {
 426       short tag;
 427       int first, last, probe;
 428       short[] row = action_tab[state];
 429
 430       /* linear search if we are < 10 entries */
 431       if (row.length < 20)
 432         for (probe = 0; probe < row.length; probe++)
 433           {
 434             /* is this entry labeled with our Symbol or the default? */
 435             tag = row[probe++];
 436             if (tag == sym || tag == -1)
 437               {
 438                 /* return the next entry */
 439                 return row[probe];
 440               }
 441           }
 442       /* otherwise binary search */
 443       else
 444         {
 445           first = 0;
 446           last = (row.length-1)/2 - 1;  /* leave out trailing default entry */
 447           while (first <= last)
 448             {
 449               probe = (first+last)/2;
 450               if (sym == row[probe*2])
 451                 return row[probe*2+1];
 452               else if (sym > row[probe*2])
 453                 first = probe+1;
 454               else
 455                 last = probe-1;
 456             }
 457
 458           /* not found, use the default at the end */
 459           return row[row.length-1];
 460         }
 461
 462       /* shouldn't happened, but if we run off the end we return the
 463          default (error == 0) */
 464       return 0;
 465     }
 466
 467   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 468
 469   /** Fetch a state from the reduce-goto table.  The table is broken up into
 470    *  rows, one per state (rows are indexed directly by state number).
 471    *  Within each row, a list of index, value pairs are given (as sequential
 472    *  entries in the table), and the list is terminated by a default entry
 473    *  (denoted with a Symbol index of -1).  To find the proper entry in a row
 474    *  we do a linear search.
 475    *
 476    * @param state the state index of the entry being accessed.
 477    * @param sym   the Symbol index of the entry being accessed.
 478    */
 479   protected final short get_reduce(int state, int sym)
 480     {
 481       short tag;
 482       short[] row = reduce_tab[state];
 483
 484       /* if we have a null row we go with the default */
 485       if (row == null)
 486         return -1;
 487
 488       for (int probe = 0; probe < row.length; probe++)
 489         {
 490           /* is this entry labeled with our Symbol or the default? */
 491           tag = row[probe++];
 492           if (tag == sym || tag == -1)
 493             {
 494               /* return the next entry */
 495               return row[probe];
 496             }
 497         }
 498       /* if we run off the end we return the default (error == -1) */
 499       return -1;
 500     }
 501
 502   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 503
 504   /** This method provides the main parsing routine.  It returns only when
 505    *  done_parsing() has been called (typically because the parser has
 506    *  accepted, or a fatal error has been reported).  See the header
 507    *  documentation for the class regarding how shift/reduce parsers operate
 508    *  and how the various tables are used.
 509    */
 510   public Symbol parse() throws java.lang.Exception
 511     {
 512       /* the current action code */
 513       int act;
 514
 515       /* the Symbol/stack element returned by a reduce */
 516       Symbol lhs_sym = null;
 517
 518       /* information about production being reduced with */
 519       short handle_size, lhs_sym_num;
 520
 521       /* set up direct reference to tables to drive the parser */
 522
 523       production_tab = production_table();
 524       action_tab     = action_table();
 525       reduce_tab     = reduce_table();
 526
 527       /* initialize the action encapsulation object */
 528       init_actions();
 529
 530       /* do user initialization */
 531       user_init();
 532
 533       /* get the first token */
 534       cur_token = scan();
 535
 536       /* push dummy Symbol with start state to get us underway */
 537       stack.removeAllElements();
 538       stack.push(new Symbol(0, start_state()));
 539       tos = 0;
 540
 541       /* continue until we are told to stop */
 542       for (_done_parsing = false; !_done_parsing; )
 543         {
 544           /* Check current token for freshness. */
 545           if (cur_token.used_by_parser)
 546             throw new Error("Symbol recycling detected (fix your scanner).");
 547
 548           /* current state is always on the top of the stack */
 549
 550           /* look up action out of the current state with the current input */
 551           act = get_action(((Symbol)stack.peek()).parse_state, cur_token.sym);
 552
 553           /* decode the action -- > 0 encodes shift */
 554           if (act > 0)
 555             {
 556               /* shift to the encoded state by pushing it on the stack */
 557               cur_token.parse_state = act-1;
 558               cur_token.used_by_parser = true;
 559               stack.push(cur_token);
 560               tos++;
 561
 562               /* advance to the next Symbol */
 563               cur_token = scan();
 564             }
 565           /* if its less than zero, then it encodes a reduce action */
 566           else if (act < 0)
 567             {
 568               /* perform the action for the reduce */
 569               lhs_sym = do_action((-act)-1, this, stack, tos);
 570
 571               /* look up information about the production */
 572               lhs_sym_num = production_tab[(-act)-1][0];
 573               handle_size = production_tab[(-act)-1][1];
 574
 575               /* pop the handle off the stack */
 576               for (int i = 0; i < handle_size; i++)
 577                 {
 578                   stack.pop();
 579                   tos--;
 580                 }
 581
 582               /* look up the state to go to from the one popped back to */
 583               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
 584
 585               /* shift to that state */
 586               lhs_sym.parse_state = act;
 587               lhs_sym.used_by_parser = true;
 588               stack.push(lhs_sym);
 589               tos++;
 590             }
 591           /* finally if the entry is zero, we have an error */
 592           else if (act == 0)
 593             {
 594               /* call user syntax error reporting routine */
 595               syntax_error(cur_token);
 596
 597               /* try to error recover */
 598               if (!error_recovery(false))
 599                 {
 600                   /* if that fails give up with a fatal syntax error */
 601                   unrecovered_syntax_error(cur_token);
 602
 603                   /* just in case that wasn't fatal enough, end parse */
 604                   done_parsing();
 605                 } else {
 606                   lhs_sym = (Symbol)stack.peek();
 607                 }
 608             }
 609         }
 610       return lhs_sym;
 611     }
 612
 613   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 614
 615   /** Write a debugging message to System.err for the debugging version
 616    *  of the parser.
 617    *
 618    * @param mess the text of the debugging message.
 619    */
 620   public void debug_message(String mess)
 621     {
 622       System.err.println(mess);
 623     }
 624
 625   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 626
 627   /** Dump the parse stack for debugging purposes. */
 628   public void dump_stack()
 629     {
 630       if (stack == null)
 631         {
 632           debug_message("# Stack dump requested, but stack is null");
 633           return;
 634         }
 635
 636       debug_message("============ Parse Stack Dump ============");
 637
 638       /* dump the stack */
 639       for (int i=0; i<stack.size(); i++)
 640         {
 641           debug_message("Symbol: " + ((Symbol)stack.elementAt(i)).sym +
 642                         " State: " + ((Symbol)stack.elementAt(i)).parse_state);
 643         }
 644       debug_message("==========================================");
 645     }
 646
 647   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 648
 649   /** Do debug output for a reduce.
 650    *
 651    * @param prod_num  the production we are reducing with.
 652    * @param nt_num    the index of the LHS non terminal.
 653    * @param rhs_size  the size of the RHS.
 654    */
 655   public void debug_reduce(int prod_num, int nt_num, int rhs_size)
 656     {
 657       debug_message("# Reduce with prod #" + prod_num + " [NT=" + nt_num +
 658                     ", " + "SZ=" + rhs_size + "]");
 659     }
 660
 661   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 662
 663   /** Do debug output for shift.
 664    *
 665    * @param shift_tkn the Symbol being shifted onto the stack.
 666    */
 667   public void debug_shift(Symbol shift_tkn)
 668     {
 669       debug_message("# Shift under term #" + shift_tkn.sym +
 670                     " to state #" + shift_tkn.parse_state);
 671     }
 672
 673   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 674
 675   /** Do debug output for stack state. [CSA]
 676    */
 677   public void debug_stack() {
 678       StringBuffer sb=new StringBuffer("## STACK:");
 679       for (int i=0; i<stack.size(); i++) {
 680           Symbol s = (Symbol) stack.elementAt(i);
 681           sb.append(" <state "+s.parse_state+", sym "+s.sym+">");
 682           if ((i%3)==2 || (i==(stack.size()-1))) {
 683               debug_message(sb.toString());
 684               sb = new StringBuffer("         ");
 685           }
 686       }
 687   }
 688
 689   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 690
 691   /** Perform a parse with debugging output.  This does exactly the
 692    *  same things as parse(), except that it calls debug_shift() and
 693    *  debug_reduce() when shift and reduce moves are taken by the parser
 694    *  and produces various other debugging messages.
 695    */
 696   public Symbol debug_parse()
 697     throws java.lang.Exception
 698     {
 699       /* the current action code */
 700       int act;
 701
 702       /* the Symbol/stack element returned by a reduce */
 703       Symbol lhs_sym = null;
 704
 705       /* information about production being reduced with */
 706       short handle_size, lhs_sym_num;
 707
 708       /* set up direct reference to tables to drive the parser */
 709       production_tab = production_table();
 710       action_tab     = action_table();
 711       reduce_tab     = reduce_table();
 712
 713       debug_message("# Initializing parser");
 714
 715       /* initialize the action encapsulation object */
 716       init_actions();
 717
 718       /* do user initialization */
 719       user_init();
 720
 721       /* the current Symbol */
 722       cur_token = scan();
 723
 724       debug_message("# Current Symbol is #" + cur_token.sym);
 725
 726       /* push dummy Symbol with start state to get us underway */
 727       stack.removeAllElements();
 728       stack.push(new Symbol(0, start_state()));
 729       tos = 0;
 730
 731       /* continue until we are told to stop */
 732       for (_done_parsing = false; !_done_parsing; )
 733         {
 734           /* Check current token for freshness. */
 735           if (cur_token.used_by_parser)
 736             throw new Error("Symbol recycling detected (fix your scanner).");
 737
 738           /* current state is always on the top of the stack */
 739           //debug_stack();
 740
 741           /* look up action out of the current state with the current input */
 742           act = get_action(((Symbol)stack.peek()).parse_state, cur_token.sym);
 743
 744           /* decode the action -- > 0 encodes shift */
 745           if (act > 0)
 746             {
 747               /* shift to the encoded state by pushing it on the stack */
 748               cur_token.parse_state = act-1;
 749               cur_token.used_by_parser = true;
 750               debug_shift(cur_token);
 751               stack.push(cur_token);
 752               tos++;
 753
 754               /* advance to the next Symbol */
 755               cur_token = scan();
 756               debug_message("# Current token is " + cur_token);
 757             }
 758           /* if its less than zero, then it encodes a reduce action */
 759           else if (act < 0)
 760             {
 761               /* perform the action for the reduce */
 762               lhs_sym = do_action((-act)-1, this, stack, tos);
 763
 764               /* look up information about the production */
 765               lhs_sym_num = production_tab[(-act)-1][0];
 766               handle_size = production_tab[(-act)-1][1];
 767
 768               debug_reduce((-act)-1, lhs_sym_num, handle_size);
 769
 770               /* pop the handle off the stack */
 771               for (int i = 0; i < handle_size; i++)
 772                 {
 773                   stack.pop();
 774                   tos--;
 775                 }
 776
 777               /* look up the state to go to from the one popped back to */
 778               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
 779               debug_message("# Reduce rule: top state " +
 780                              ((Symbol)stack.peek()).parse_state +
 781                              ", lhs sym " + lhs_sym_num + " -> state " + act);
 782
 783               /* shift to that state */
 784               lhs_sym.parse_state = act;
 785               lhs_sym.used_by_parser = true;
 786               stack.push(lhs_sym);
 787               tos++;
 788
 789               debug_message("# Goto state #" + act);
 790             }
 791           /* finally if the entry is zero, we have an error */
 792           else if (act == 0)
 793             {
 794               /* call user syntax error reporting routine */
 795               syntax_error(cur_token);
 796
 797               /* try to error recover */
 798               if (!error_recovery(true))
 799                 {
 800                   /* if that fails give up with a fatal syntax error */
 801                   unrecovered_syntax_error(cur_token);
 802
 803                   /* just in case that wasn't fatal enough, end parse */
 804                   done_parsing();
 805                 } else {
 806                   lhs_sym = (Symbol)stack.peek();
 807                 }
 808             }
 809         }
 810       return lhs_sym;
 811     }
 812
 813   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 814   /* Error recovery code */
 815   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 816
 817   /** Attempt to recover from a syntax error.  This returns false if recovery
 818    *  fails, true if it succeeds.  Recovery happens in 4 steps.  First we
 819    *  pop the parse stack down to a point at which we have a shift out
 820    *  of the top-most state on the error Symbol.  This represents the
 821    *  initial error recovery configuration.  If no such configuration is
 822    *  found, then we fail.  Next a small number of "lookahead" or "parse
 823    *  ahead" Symbols are read into a buffer.  The size of this buffer is
 824    *  determined by error_sync_size() and determines how many Symbols beyond
 825    *  the error must be matched to consider the recovery a success.  Next,
 826    *  we begin to discard Symbols in attempt to get past the point of error
 827    *  to a point where we can continue parsing.  After each Symbol, we attempt
 828    *  to "parse ahead" though the buffered lookahead Symbols.  The "parse ahead"
 829    *  process simulates that actual parse, but does not modify the real
 830    *  parser's configuration, nor execute any actions. If we can  parse all
 831    *  the stored Symbols without error, then the recovery is considered a
 832    *  success.  Once a successful recovery point is determined, we do an
 833    *  actual parse over the stored input -- modifying the real parse
 834    *  configuration and executing all actions.  Finally, we return the the
 835    *  normal parser to continue with the overall parse.
 836    *
 837    * @param debug should we produce debugging messages as we parse.
 838    */
 839   protected boolean error_recovery(boolean debug)
 840     throws java.lang.Exception
 841     {
 842       if (debug) debug_message("# Attempting error recovery");
 843
 844       /* first pop the stack back into a state that can shift on error and
 845          do that shift (if that fails, we fail) */
 846       if (!find_recovery_config(debug))
 847         {
 848           if (debug) debug_message("# Error recovery fails");
 849           return false;
 850         }
 851
 852       /* read ahead to create lookahead we can parse multiple times */
 853       read_lookahead();
 854
 855       /* repeatedly try to parse forward until we make it the required dist */
 856       for (;;)
 857         {
 858           /* try to parse forward, if it makes it, bail out of loop */
 859           if (debug) debug_message("# Trying to parse ahead");
 860           if (try_parse_ahead(debug))
 861             {
 862               break;
 863             }
 864
 865           /* if we are now at EOF, we have failed */
 866           if (lookahead[0].sym == EOF_sym())
 867             {
 868               if (debug) debug_message("# Error recovery fails at EOF");
 869               return false;
 870             }
 871
 872           /* otherwise, we consume another Symbol and try again */
 873           // BUG FIX by Bruce Hutton
 874           // Computer Science Department, University of Auckland,
 875           // Auckland, New Zealand.
 876           // It is the first token that is being consumed, not the one
 877           // we were up to parsing
 878           if (debug)
 879               debug_message("# Consuming Symbol #" + lookahead[ 0 ].sym);
 880           restart_lookahead();
 881         }
 882
 883       /* we have consumed to a point where we can parse forward */
 884       if (debug) debug_message("# Parse-ahead ok, going back to normal parse");
 885
 886       /* do the real parse (including actions) across the lookahead */
 887       parse_lookahead(debug);
 888
 889       /* we have success */
 890       return true;
 891     }
 892
 893   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 894
 895   /** Determine if we can shift under the special error Symbol out of the
 896    *  state currently on the top of the (real) parse stack.
 897    */
 898   protected boolean shift_under_error()
 899     {
 900       /* is there a shift under error Symbol */
 901       return get_action(((Symbol)stack.peek()).parse_state, error_sym()) > 0;
 902     }
 903
 904   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 905
 906   /** Put the (real) parse stack into error recovery configuration by
 907    *  popping the stack down to a state that can shift on the special
 908    *  error Symbol, then doing the shift.  If no suitable state exists on
 909    *  the stack we return false
 910    *
 911    * @param debug should we produce debugging messages as we parse.
 912    */
 913   protected boolean find_recovery_config(boolean debug)
 914     {
 915       Symbol error_token;
 916       int act;
 917
 918       if (debug) debug_message("# Finding recovery state on stack");
 919
 920       /* Remember the right-position of the top symbol on the stack */
 921       int right_pos = ((Symbol)stack.peek()).right;
 922       int left_pos  = ((Symbol)stack.peek()).left;
 923
 924       /* pop down until we can shift under error Symbol */
 925       while (!shift_under_error())
 926         {
 927           /* pop the stack */
 928           if (debug)
 929             debug_message("# Pop stack by one, state was # " +
 930                           ((Symbol)stack.peek()).parse_state);
 931           left_pos = ((Symbol)stack.pop()).left;
 932           tos--;
 933
 934           /* if we have hit bottom, we fail */
 935           if (stack.empty())
 936             {
 937               if (debug) debug_message("# No recovery state found on stack");
 938               return false;
 939             }
 940         }
 941
 942       /* state on top of the stack can shift under error, find the shift */
 943       act = get_action(((Symbol)stack.peek()).parse_state, error_sym());
 944       if (debug)
 945         {
 946           debug_message("# Recover state found (#" +
 947                         ((Symbol)stack.peek()).parse_state + ")");
 948           debug_message("# Shifting on error to state #" + (act-1));
 949         }
 950
 951       /* build and shift a special error Symbol */
 952       error_token = new Symbol(error_sym(), left_pos, right_pos);
 953       error_token.parse_state = act-1;
 954       error_token.used_by_parser = true;
 955       stack.push(error_token);
 956       tos++;
 957
 958       return true;
 959     }
 960
 961   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 962
 963   /** Lookahead Symbols used for attempting error recovery "parse aheads". */
 964   protected Symbol lookahead[];
 965
 966   /** Position in lookahead input buffer used for "parse ahead". */
 967   protected int lookahead_pos;
 968
 969   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 970
 971   /** Read from input to establish our buffer of "parse ahead" lookahead
 972    *  Symbols.
 973    */
 974   protected void read_lookahead() throws java.lang.Exception
 975     {
 976       /* create the lookahead array */
 977       lookahead = new Symbol[error_sync_size()];
 978
 979       /* fill in the array */
 980       for (int i = 0; i < error_sync_size(); i++)
 981         {
 982           lookahead[i] = cur_token;
 983           cur_token = scan();
 984         }
 985
 986       /* start at the beginning */
 987       lookahead_pos = 0;
 988     }
 989
 990   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 991
 992   /** Return the current lookahead in our error "parse ahead" buffer. */
 993   protected Symbol cur_err_token() { return lookahead[lookahead_pos]; }
 994
 995   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 996
 997   /** Advance to next "parse ahead" input Symbol. Return true if we have
 998    *  input to advance to, false otherwise.
 999    */
1000   protected boolean advance_lookahead()
1001     {
1002       /* advance the input location */
1003       lookahead_pos++;
1004
1005       /* return true if we didn't go off the end */
1006       return lookahead_pos < error_sync_size();
1007     }
1008
1009   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1010
1011   /** Reset the parse ahead input to one Symbol past where we started error
1012    *  recovery (this consumes one new Symbol from the real input).
1013    */
1014   protected void restart_lookahead() throws java.lang.Exception
1015     {
1016       /* move all the existing input over */
1017       for (int i = 1; i < error_sync_size(); i++)
1018         lookahead[i-1] = lookahead[i];
1019
1020       /* read a new Symbol into the last spot */
1021       // BUG Fix by Bruce Hutton
1022       // Computer Science Department, University of Auckland,
1023       // Auckland, New Zealand. [applied 5-sep-1999 by csa]
1024       // The following two lines were out of order!!
1025       lookahead[error_sync_size()-1] = cur_token;
1026       cur_token = scan();
1027
1028       /* reset our internal position marker */
1029       lookahead_pos = 0;
1030     }
1031
1032   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1033
1034   /** Do a simulated parse forward (a "parse ahead") from the current
1035    *  stack configuration using stored lookahead input and a virtual parse
1036    *  stack.  Return true if we make it all the way through the stored
1037    *  lookahead input without error. This basically simulates the action of
1038    *  parse() using only our saved "parse ahead" input, and not executing any
1039    *  actions.
1040    *
1041    * @param debug should we produce debugging messages as we parse.
1042    */
1043   protected boolean try_parse_ahead(boolean debug)
1044     throws java.lang.Exception
1045     {
1046       int act;
1047       short lhs, rhs_size;
1048
1049       /* create a virtual stack from the real parse stack */
1050       virtual_parse_stack vstack = new virtual_parse_stack(stack);
1051
1052       /* parse until we fail or get past the lookahead input */
1053       for (;;)
1054         {
1055           /* look up the action from the current state (on top of stack) */
1056           act = get_action(vstack.top(), cur_err_token().sym);
1057
1058           /* if its an error, we fail */
1059           if (act == 0) return false;
1060
1061           /* > 0 encodes a shift */
1062           if (act > 0)
1063             {
1064               /* push the new state on the stack */
1065               vstack.push(act-1);
1066
1067               if (debug) debug_message("# Parse-ahead shifts Symbol #" +
1068                        cur_err_token().sym + " into state #" + (act-1));
1069
1070               /* advance simulated input, if we run off the end, we are done */
1071               if (!advance_lookahead()) return true;
1072             }
1073           /* < 0 encodes a reduce */
1074           else
1075             {
1076               /* if this is a reduce with the start production we are done */
1077               if ((-act)-1 == start_production())
1078                 {
1079                   if (debug) debug_message("# Parse-ahead accepts");
1080                   return true;
1081                 }
1082
1083               /* get the lhs Symbol and the rhs size */
1084               lhs = production_tab[(-act)-1][0];
1085               rhs_size = production_tab[(-act)-1][1];
1086
1087               /* pop handle off the stack */
1088               for (int i = 0; i < rhs_size; i++)
1089                 vstack.pop();
1090
1091               if (debug)
1092                 debug_message("# Parse-ahead reduces: handle size = " +
1093                   rhs_size + " lhs = #" + lhs + " from state #" + vstack.top());
1094
1095               /* look up goto and push it onto the stack */
1096               vstack.push(get_reduce(vstack.top(), lhs));
1097               if (debug)
1098                 debug_message("# Goto state #" + vstack.top());
1099             }
1100         }
1101     }
1102
1103   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1104
1105   /** Parse forward using stored lookahead Symbols.  In this case we have
1106    *  already verified that parsing will make it through the stored lookahead
1107    *  Symbols and we are now getting back to the point at which we can hand
1108    *  control back to the normal parser.  Consequently, this version of the
1109    *  parser performs all actions and modifies the real parse configuration.
1110    *  This returns once we have consumed all the stored input or we accept.
1111    *
1112    * @param debug should we produce debugging messages as we parse.
1113    */
1114   protected void parse_lookahead(boolean debug)
1115     throws java.lang.Exception
1116     {
1117       /* the current action code */
1118       int act;
1119
1120       /* the Symbol/stack element returned by a reduce */
1121       Symbol lhs_sym = null;
1122
1123       /* information about production being reduced with */
1124       short handle_size, lhs_sym_num;
1125
1126       /* restart the saved input at the beginning */
1127       lookahead_pos = 0;
1128
1129       if (debug)
1130         {
1131           debug_message("# Reparsing saved input with actions");
1132           debug_message("# Current Symbol is #" + cur_err_token().sym);
1133           debug_message("# Current state is #" +
1134                         ((Symbol)stack.peek()).parse_state);
1135         }
1136
1137       /* continue until we accept or have read all lookahead input */
1138       while(!_done_parsing)
1139         {
1140           /* current state is always on the top of the stack */
1141
1142           /* look up action out of the current state with the current input */
1143           act =
1144             get_action(((Symbol)stack.peek()).parse_state, cur_err_token().sym);
1145
1146           /* decode the action -- > 0 encodes shift */
1147           if (act > 0)
1148             {
1149               /* shift to the encoded state by pushing it on the stack */
1150               cur_err_token().parse_state = act-1;
1151               cur_err_token().used_by_parser = true;
1152               if (debug) debug_shift(cur_err_token());
1153               stack.push(cur_err_token());
1154               tos++;
1155
1156               /* advance to the next Symbol, if there is none, we are done */
1157               if (!advance_lookahead())
1158                 {
1159                   if (debug) debug_message("# Completed reparse");
1160
1161                   /* scan next Symbol so we can continue parse */
1162                   // BUGFIX by Chris Harris <ckharris@ucsd.edu>:
1163                   //   correct a one-off error by commenting out
1164                   //   this next line.
1165                   /*cur_token = scan();*/
1166
1167                   /* go back to normal parser */
1168                   return;
1169                 }
1170
1171               if (debug)
1172                 debug_message("# Current Symbol is #" + cur_err_token().sym);
1173             }
1174           /* if its less than zero, then it encodes a reduce action */
1175           else if (act < 0)
1176             {
1177               /* perform the action for the reduce */
1178               lhs_sym = do_action((-act)-1, this, stack, tos);
1179
1180               /* look up information about the production */
1181               lhs_sym_num = production_tab[(-act)-1][0];
1182               handle_size = production_tab[(-act)-1][1];
1183
1184               if (debug) debug_reduce((-act)-1, lhs_sym_num, handle_size);
1185
1186               /* pop the handle off the stack */
1187               for (int i = 0; i < handle_size; i++)
1188                 {
1189                   stack.pop();
1190                   tos--;
1191                 }
1192
1193               /* look up the state to go to from the one popped back to */
1194               act = get_reduce(((Symbol)stack.peek()).parse_state, lhs_sym_num);
1195
1196               /* shift to that state */
1197               lhs_sym.parse_state = act;
1198               lhs_sym.used_by_parser = true;
1199               stack.push(lhs_sym);
1200               tos++;
1201
1202               if (debug) debug_message("# Goto state #" + act);
1203
1204             }
1205           /* finally if the entry is zero, we have an error
1206              (shouldn't happen here, but...)*/
1207           else if (act == 0)
1208             {
1209               report_fatal_error("Syntax error", lhs_sym);
1210               return;
1211             }
1212         }
1213
1214
1215     }
1216
1217   /*-----------------------------------------------------------*/
1218
1219   /** Utility function: unpacks parse tables from strings */
1220   protected static short[][] unpackFromStrings(String[] sa)
1221     {
1222       // Concatanate initialization strings.
1223       StringBuffer sb = new StringBuffer(sa[0]);
1224       for (int i=1; i<sa.length; i++)
1225         sb.append(sa[i]);
1226       int n=0; // location in initialization string
1227       int size1 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
1228       short[][] result = new short[size1][];
1229       for (int i=0; i<size1; i++) {
1230         int size2 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
1231         result[i] = new short[size2];
1232         for (int j=0; j<size2; j++)
1233           result[i][j] = (short) (sb.charAt(n++)-2);
1234       }
1235       return result;
1236     }
1237 }
1238