package java_cup.runtime;import java.util.Stack;/** This class implements a skeleton table driven LR parser.  In general, *  LR parsers are a form of bottom up shift-reduce parsers.  Shift-reduce *  parsers act by shifting input onto a parse stack until the symbols  *  matching the right hand side of a production appear on the top of the  *  stack.  Once this occurs, a reduce is performed.  This involves removing *  the symbols corresponding to the right hand side of the production *  (the so called "handle") and replacing them with the non-terminal from *  the left hand side of the production.  <p> * *  To control the decision of whether to shift or reduce at any given point,  *  the parser uses a state machine (the "viable prefix recognition machine"  *  built by the parser generator).  The current state of the machine is placed *  on top of the parse stack (stored as part of a symbol object representing *  a terminal or non terminal).  The parse action table is consulted  *  (using the current state and the current lookahead token as indexes) to  *  determine whether to shift or to reduce.  When the parser shifts, it  *  changes to a new state by pushing a new symbol (containing a new state)  *  onto the stack.  When the parser reduces, it pops the handle (right hand  *  side of a production) off the stack.  This leaves the parser in the state  *  it was in before any of those symbols were matched.  Next the reduce-goto  *  table is consulted (using the new state and current lookahead token as  *  indexes) to determine a new state to go to.  The parser then shifts to  *  this goto state by pushing the left hand side symbol of the production  *  (also containing the new state) onto the stack.<p> * *  This class actually provides four LR parsers.  The methods parse() and  *  debug_parse() provide two versions of the main parser (the only difference  *  being that debug_parse() emits debugging trace messages as it parses).   *  In addition to these main parsers, the error recovery mechanism uses two  *  more.  One of these is used to simulate "parsing ahead" in the input  *  without carrying out actions (to verify that a potential error recovery  *  has worked), and the other is used to parse through buffered "parse ahead"  *  input in order to execute all actions and re-synchronize the actual parser  *  configuration.<p> * *  This is an abstract class which is normally filled out by a subclass *  generated by the JavaCup parser generator.  In addition to supplying *  the actual parse tables, generated code also supplies methods which  *  invoke various pieces of user supplied code, provide access to certain *  special symbols (e.g., EOF and error), etc.  Specifically, the following *  abstract methods are normally supplied by generated code: *  <dl compact> *  <dt> short[][] production_table() *  <dd> Provides a reference to the production table (indicating the index of *       the left hand side non terminal and the length of the right hand side *       for each production in the grammar). *  <dt> short[][] action_table() *  <dd> Provides a reference to the parse action table. *  <dt> short[][] reduce_table() *  <dd> Provides a reference to the reduce-goto table. *  <dt> int start_state()       *  <dd> Indicates the index of the start state. *  <dt> int start_production()  *  <dd> Indicates the index of the starting production. *  <dt> int EOF_sym()  *  <dd> Indicates the index of the EOF symbol. *  <dt> int error_sym()  *  <dd> Indicates the index of the error symbol. *  <dt> symbol do_action()  *  <dd> Executes a piece of user supplied action code.  This always comes at  *       the point of a reduce in the parse, so this code also allocates and  *       fills in the left hand side non terminal symbol object that is to be  *       pushed onto the stack for the reduce. *  <dt> void init_actions() *  <dd> Code to initialize a special object that encapsulates user supplied *       actions (this object is used by do_action() to actually carry out the  *       actions). *  <dt> token scan() *  <dd> Used to get the next input token from the scanner. *  </dl> *   *  In addition to these routines that <i>must</i> be supplied by the  *  generated subclass there are also a series of routines that <i>may</i>  *  be supplied.  These include: *  <dl> *  <dt> int error_sync_size() *  <dd> This determines how many tokens past the point of an error  *       must be parsed without error in order to consider a recovery to  *       be valid.  This defaults to 3.  Values less than 2 are not  *       recommended. *  <dt> void report_error(String message, Object info) *  <dd> This method is called to report an error.  The default implementation *       simply prints a message to System.err and ignores its second parameter. *       This method is often replaced in order to provide a more sophisticated *       error reporting mechanism. *  <dt> void report_fatal_error(String message, Object info) *  <dd> This method is called when a fatal error that cannot be recovered from *       is encountered.  In the default implementation, it calls  *       report_error() to emit a message, then throws an exception. *  <dt> void syntax_error(token cur_token) *  <dd> This method is called as soon as syntax error is detected (but *       before recovery is attempted).  In the default implementation it  *       invokes: report_error("Syntax error", null); *  <dt> void unrecovered_syntax_error(token cur_token) *  <dd> This method is called if syntax error recovery fails.  In the default *       implementation it invokes:<br>  *         report_fatal_error("Couldn't repair and continue parse", null); *  </dl> * * @see     java_cup.runtime.symbol * @see     java_cup.runtime.token * @see     java_cup.runtime.virtual_parse_stack * @version last updated: 11/25/95 * @author  Scott Hudson */public abstract class lr_parser {  /*-----------------------------------------------------------*/  /*--- Constructor(s) ----------------------------------------*/  /*-----------------------------------------------------------*/  /** Simple constructor. */  public lr_parser()    {      /* nothing to do here */    }  /*-----------------------------------------------------------*/  /*--- (Access to) Static (Class) Variables ------------------*/  /*-----------------------------------------------------------*/  /** The default number of tokens after an error we much match to consider    *  it recovered from.    */  protected final static int _error_sync_size = 3;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The number of tokens after an error we much match to consider it    *  recovered from.    */  protected int error_sync_size() {return _error_sync_size; }  /*-----------------------------------------------------------*/  /*--- (Access to) Instance Variables ------------------------*/  /*-----------------------------------------------------------*/  /** Table of production information (supplied by generated subclass).   *  This table contains one entry per production and is indexed by    *  the negative-encoded values (reduce actions) in the action_table.     *  Each entry has two parts, the index of the non-terminal on the    *  left hand side of the production, and the number of symbols    *  on the right hand side.    */  public abstract short[][] production_table();  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The action table (supplied by generated subclass).  This table is   *  indexed by state and terminal number indicating what action is to   *  be taken when the parser is in the given state (i.e., the given state    *  is on top of the stack) and the given terminal is next on the input.     *  States are indexed using the first dimension, however, the entries for    *  a given state are compacted and stored in adjacent index, value pairs    *  which are searched for rather than accessed directly (see get_action()).     *  The actions stored in the table will be either shifts, reduces, or    *  errors.  Shifts are encoded as positive values (one greater than the    *  state shifted to).  Reduces are encoded as negative values (one less    *  than the production reduced by).  Error entries are denoted by zero.    *    * @see java_cup.runtime.lr_parser#get_action   */  public abstract short[][] action_table();  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The reduce-goto table (supplied by generated subclass).  This   *  table is indexed by state and non-terminal number and contains   *  state numbers.  States are indexed using the first dimension, however,   *  the entries for a given state are compacted and stored in adjacent   *  index, value pairs which are searched for rather than accessed    *  directly (see get_reduce()).  When a reduce occurs, the handle    *  (corresponding to the RHS of the matched production) is popped off    *  the stack.  The new top of stack indicates a state.  This table is    *  then indexed by that state and the LHS of the reducing production to    *  indicate where to "shift" to.    *   * @see java_cup.runtime.lr_parser#get_reduce   */  public abstract short[][] reduce_table();  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The index of the start state (supplied by generated subclass). */  public abstract int start_state();  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The index of the start production (supplied by generated subclass). */  public abstract int start_production();  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The index of the end of file terminal symbol (supplied by generated    *  subclass).    */  public abstract int EOF_sym();  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The index of the special error symbol (supplied by generated subclass). */  public abstract int error_sym();  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Internal flag to indicate when parser should quit. */  protected boolean _done_parsing = false;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** This method is called to indicate that the parser should quit.  This is    *  normally called by an accept action, but can be used to cancel parsing    *  early in other circumstances if desired.    */  public void done_parsing()    {      _done_parsing = true;    }  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /* Global parse state shared by parse(), error recovery, and    * debugging routines */  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Indication of the index for top of stack (for use by actions). */  protected int tos;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The current lookahead token. */  protected token cur_token;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** The parse stack itself. */  protected Stack stack = new Stack();  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Direct reference to the production table. */   protected short[][] production_tab;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Direct reference to the action table. */  protected short[][] action_tab;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Direct reference to the reduce-goto table. */  protected short[][] reduce_tab;  /*-----------------------------------------------------------*/  /*--- General Methods ---------------------------------------*/  /*-----------------------------------------------------------*/  /** Perform a bit of user supplied action code (supplied by generated    *  subclass).  Actions are indexed by an internal action number assigned   *  at parser generation time.   *   * @param act_num   the internal index of the action to be performed.   * @param parser    the parser object we are acting for.   * @param stack     the parse stack of that object.   * @param top       the index of the top element of the parse stack.   */  public abstract symbol do_action(    int       act_num,     lr_parser parser,     Stack     stack,     int       top)     throws java.lang.Exception;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** User code for initialization inside the parser.  Typically this    *  initializes the scanner.  This is called before the parser requests   *  the first token.  Here this is just a placeholder for subclasses that    *  might need this and we perform no action.   This method is normally   *  overridden by the generated code using this contents of the "init with"   *  clause as its body.   */  public void user_init() throws java.lang.Exception { }  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Initialize the action object.  This is called before the parser does   *  any parse actions. This is filled in by generated code to create   *  an object that encapsulates all action code.    */   protected abstract void init_actions() throws java.lang.Exception;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Get the next token from the input (supplied by generated subclass).   *  Once end of file has been reached, all subsequent calls to scan    *  should return an EOF token (which is symbol number 0).  This method   *  is supplied by the generator using using the code declared in the    *  "scan with" clause.   */  public abstract token scan() throws java.lang.Exception;  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Report a fatal error.  This method takes a  message string and an    *  additional object (to be used by specializations implemented in    *  subclasses).  Here in the base class a very simple implementation    *  is provided which reports the error then throws an exception.    *   * @param message an error message.   * @param info    an extra object reserved for use by specialized subclasses.   */  public void report_fatal_error(    String   message,     Object   info)    throws java.lang.Exception    {      /* stop parsing (not really necessary since we throw an exception, but) */      done_parsing();      /* use the normal error message reporting to put out the message */      report_error(message, info);      /* throw an exception */      throw new Exception("Can't recover from previous error(s)");    }  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** Report a non fatal error (or warning).  This method takes a message    *  string and an additional object (to be used by specializations    *  implemented in subclasses).  Here in the base class a very simple    *  implementation is provided which simply prints the message to    *  System.err.    *   * @param message an error message.   * @param info    an extra object reserved for use by specialized subclasses.   */  public void report_error(String message, Object info)    {      System.err.println(message);    }  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** This method is called when a syntax error has been detected and recovery    *  is about to be invoked.  Here in the base class we just emit a    *  "Syntax error" error message.     *   * @param cur_token the current lookahead token.   */  public void syntax_error(token cur_token)    {      report_error("Syntax error", null);    }  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/  /** This method is called if it is determined that syntax error recovery    *  has been unsuccessful.  Here in the base class we report a fatal error.    *   * @param cur_token the current lookahead token.   */  public void unrecovered_syntax_error(token cur_token)    throws java.lang.Exception    {      report_fatal_error("Couldn't repair and continue parse", null);    }