content: 
  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 Symbol 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 Symbol 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).
   * </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>Symbol scan()
   * <dd>Used to get the next input Symbol from the scanner.
   * <dt>Scanner getScanner()
   * <dd>Used to provide a scanner for the default implementation of scan().
   * <dt>int error_sync_size()
   * <dd>This determines how many Symbols 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 where the error occurred. 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(Symbol 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(Symbol 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 Symbol
   * @see Symbol
   * @see virtual_parse_stack
   * @version last updated: 7/3/96
   * @author Frank Flannery
   */
  @SuppressWarnings("unchecked" )
  public abstract class lr_parser {
      /*-----------------------------------------------------------*/
      /*--- Constructor(s) ----------------------------------------*/
      /*-----------------------------------------------------------*/
  
      /**
       * Simple constructor.
       */
      public lr_parser() {
          symbolFactory = new DefaultSymbolFactory();
      }
  
      /**
       * Constructor that sets the default scanner. [CSA/davidm]
       */
      public lr_parser(Scanner s) {
          this(s, new DefaultSymbolFactory()); // TUM 20060327 old cup v10 Symbols
                                              // as default
      }
  
      /**
       * Constructor that sets the default scanner and a SymbolFactory
       */
      public lr_parser(Scanner s, SymbolFactory symfac) {
          this(); // in case default constructor someday does something
          symbolFactory = symfac;
          setScanner(s);
      }
  
      public SymbolFactory symbolFactory;// = new DefaultSymbolFactory();
  
      /**
       * Whenever creation of a new Symbol is necessary, one should use this factory.
       */
      public SymbolFactory getSymbolFactory() {
          return symbolFactory;
      }
      /*-----------------------------------------------------------*/
      /*--- (Access to) Static (Class) Variables ------------------*/
      /*-----------------------------------------------------------*/
  
      /**
       * The default number of Symbols after an error we much match to consider it
       * recovered from.
       */
      protected final static int _error_sync_size = 3;
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * The number of Symbols 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 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 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 Symbol. */
      protected Symbol    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;
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * This is the scanner object used by the default implementation of scan() to
       * get Symbols. To avoid name conflicts with existing code, this field is
       * private. [CSA/davidm]
       */
      private Scanner     _scanner;
  
      /**
       * Simple accessor method to set the default scanner.
       */
      public void setScanner(Scanner s) {
          _scanner = s;
      }
  
      /**
       * Simple accessor method to get the default scanner.
       */
      public Scanner getScanner() {
          return _scanner;
      }
  
      /*-----------------------------------------------------------*/
      /*--- 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<Symbol> 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 Symbol. 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 Symbol from the input (supplied by generated subclass). Once end
       * of file has been reached, all subsequent calls to scan should return an EOF
       * Symbol (which is Symbol number 0). By default this method returns
       * getScanner().next_token(); this implementation can be overridden by the
       * generated parser using the code declared in the "scan with" clause. Do not
       * recycle objects; every call to scan() should return a fresh object.
       */
      public Symbol scan() throws java.lang.Exception {
          Symbol sym = getScanner().next_token();
          return (sym != null) ? sym : getSymbolFactory().newSymbol("END_OF_FILE", EOF_sym());
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * 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.print(message);
          System.err.flush();
          if (info instanceof Symbol)
              if (((Symbol) info).left != -1)
                  System.err.println(" at character " + ((Symbol) info).left + " of input");
              else
                  System.err.println("");
          else
              System.err.println("");
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * 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 Symbol.
       */
      public void syntax_error(Symbol cur_token) throws Exception {
          report_error("Syntax error", cur_token);
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * 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 Symbol.
       */
      public void unrecovered_syntax_error(Symbol cur_token) throws java.lang.Exception {
          report_fatal_error("Couldn't repair and continue parse", cur_token);
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Fetch an action from the action table. The table is broken up into rows, one
       * per state (rows are indexed directly by state number). Within each row, a
       * list of index, value pairs are given (as sequential entries in the table),
       * and the list is terminated by a default entry (denoted with a Symbol index of
       * -1). To find the proper entry in a row we do a linear or binary search
       * (depending on the size of the row).
       *
       * @param state the state index of the action being accessed.
       * @param sym the Symbol index of the action being accessed.
       */
      protected final short get_action(int state, int sym) {
          short tag;
          int first, last, probe;
          short[] row = action_tab[state];
  
          /* linear search if we are < 10 entries */
          if (row.length < 20)
              for (probe = 0; probe < row.length; probe++) {
                  /* is this entry labeled with our Symbol or the default? */
                  tag = row[probe++];
                  if (tag == sym || tag == -1) {
                      /* return the next entry */
                      return row[probe];
                  }
              }
          /* otherwise binary search */
          else {
              first = 0;
              last = (row.length - 1) / 2 - 1; /* leave out trailing default entry */
              while (first <= last) {
                  probe = (first + last) / 2;
                  if (sym == row[probe * 2])
                      return row[probe * 2 + 1];
                  else if (sym > row[probe * 2])
                      first = probe + 1;
                  else
                      last = probe - 1;
              }
  
              /* not found, use the default at the end */
              return row[row.length - 1];
          }
  
          /*
           * shouldn't happened, but if we run off the end we return the default (error ==
           * 0)
           */
          return 0;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Fetch a state from the reduce-goto table. The table is broken up into rows,
       * one per state (rows are indexed directly by state number). Within each row, a
       * list of index, value pairs are given (as sequential entries in the table),
       * and the list is terminated by a default entry (denoted with a Symbol index of
       * -1). To find the proper entry in a row we do a linear search.
       *
       * @param state the state index of the entry being accessed.
       * @param sym the Symbol index of the entry being accessed.
       */
      protected final short get_reduce(int state, int sym) {
          short tag;
          short[] row = reduce_tab[state];
  
          /* if we have a null row we go with the default */
          if (row == null)
              return -1;
  
          for (int probe = 0; probe < row.length; probe++) {
              /* is this entry labeled with our Symbol or the default? */
              tag = row[probe++];
              if (tag == sym || tag == -1) {
                  /* return the next entry */
                  return row[probe];
              }
          }
          /*
           * if we run off the end we return the default (error == -1)
           */
          return -1;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * This method provides the main parsing routine. It returns only when
       * done_parsing() has been called (typically because the parser has accepted, or
       * a fatal error has been reported). See the header documentation for the class
       * regarding how shift/reduce parsers operate and how the various tables are
       * used.
       */
      public Symbol parse() throws java.lang.Exception {
          /* the current action code */
          int act;
  
          /* the Symbol/stack element returned by a reduce */
          Symbol lhs_sym = null;
  
          /* information about production being reduced with */
          short handle_size, lhs_sym_num;
  
          /* set up direct reference to tables to drive the parser */
  
          production_tab = production_table();
          action_tab = action_table();
          reduce_tab = reduce_table();
  
          /* initialize the action encapsulation object */
          init_actions();
  
          /* do user initialization */
          user_init();
  
          /* get the first token */
          cur_token = scan();
  
          /* push dummy Symbol with start state to get us underway */
          stack.removeAllElements();
          stack.push(getSymbolFactory().startSymbol("START", 0, start_state()));
          tos = 0;
  
          /* continue until we are told to stop */
          for (_done_parsing = false; !_done_parsing;) {
              /* Check current token for freshness. */
              if (cur_token.used_by_parser)
                  throw new Error("Symbol recycling detected (fix your scanner).");
  
              /* current state is always on the top of the stack */
  
              /*
               * look up action out of the current state with the current input
               */
              act = get_action(((Symbol) stack.peek()).parse_state, cur_token.sym);
  
              /* decode the action -- > 0 encodes shift */
              if (act > 0) {
                  /* shift to the encoded state by pushing it on the stack */
                  cur_token.parse_state = act - 1;
                  cur_token.used_by_parser = true;
                  stack.push(cur_token);
                  tos++;
  
                  /* advance to the next Symbol */
                  cur_token = scan();
              }
              /* if its less than zero, then it encodes a reduce action */
              else if (act < 0) {
                  /* perform the action for the reduce */
                  lhs_sym = do_action((-act) - 1, this, stack, tos);
  
                  /* look up information about the production */
                  lhs_sym_num = production_tab[(-act) - 1][0];
                  handle_size = production_tab[(-act) - 1][1];
  
                  /* pop the handle off the stack */
                  for (int i = 0; i < handle_size; i++) {
                      stack.pop();
                      tos--;
                  }
  
                  /* look up the state to go to from the one popped back to */
                  act = get_reduce(((Symbol) stack.peek()).parse_state, lhs_sym_num);
  
                  /* shift to that state */
                  lhs_sym.parse_state = act;
                  lhs_sym.used_by_parser = true;
                  stack.push(lhs_sym);
                  tos++;
              }
              /* finally if the entry is zero, we have an error */
              else if (act == 0) {
                  /* call user syntax error reporting routine */
                  syntax_error(cur_token);
  
                  /* try to error recover */
                  if (!error_recovery(false)) {
                      /* if that fails give up with a fatal syntax error */
                      unrecovered_syntax_error(cur_token);
  
                      /* just in case that wasn't fatal enough, end parse */
                      done_parsing();
                  } else {
                      lhs_sym = (Symbol) stack.peek();
                  }
              }
          }
          return lhs_sym;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Write a debugging message to System.err for the debugging version of the
       * parser.
       *
       * @param mess the text of the debugging message.
       */
      public void debug_message(String mess) {
          System.err.println(mess);
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /** Dump the parse stack for debugging purposes. */
      public void dump_stack() {
          if (stack == null) {
              debug_message("# Stack dump requested, but stack is null");
              return;
          }
  
          debug_message("============ Parse Stack Dump ============");
  
          /* dump the stack */
          for (int i = 0; i < stack.size(); i++) {
              debug_message("Symbol: " + ((Symbol) stack.elementAt(i)).sym + " State: " + ((Symbol) stack.elementAt(i)).parse_state);
          }
          debug_message("==========================================");
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Do debug output for a reduce.
       *
       * @param prod_num the production we are reducing with.
       * @param nt_num the index of the LHS non terminal.
       * @param rhs_size the size of the RHS.
       */
      public void debug_reduce(int prod_num, int nt_num, int rhs_size) {
          debug_message("# Reduce with prod #" + prod_num + " [NT=" + nt_num + ", " + "SZ=" + rhs_size + "]");
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Do debug output for shift.
       *
       * @param shift_tkn the Symbol being shifted onto the stack.
       */
      public void debug_shift(Symbol shift_tkn) {
          debug_message("# Shift under term #" + shift_tkn.sym + " to state #" + shift_tkn.parse_state);
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Do debug output for stack state. [CSA]
       */
      public void debug_stack() {
          StringBuffer sb = new StringBuffer("## STACK:");
          for (int i = 0; i < stack.size(); i++) {
              Symbol s = (Symbol) stack.elementAt(i);
              sb.append(" <state " + s.parse_state + ", sym " + s.sym + ">");
              if ((i % 3) == 2 || (i == (stack.size() - 1))) {
                  debug_message(sb.toString());
                  sb = new StringBuffer("         ");
              }
          }
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Perform a parse with debugging output. This does exactly the same things as
       * parse(), except that it calls debug_shift() and debug_reduce() when shift and
       * reduce moves are taken by the parser and produces various other debugging
       * messages.
       */
      public Symbol debug_parse() throws java.lang.Exception {
          /* the current action code */
          int act;
  
          /* the Symbol/stack element returned by a reduce */
          Symbol lhs_sym = null;
  
          /* information about production being reduced with */
          short handle_size, lhs_sym_num;
  
          /* set up direct reference to tables to drive the parser */
          production_tab = production_table();
          action_tab = action_table();
          reduce_tab = reduce_table();
  
          debug_message("# Initializing parser");
  
          /* initialize the action encapsulation object */
          init_actions();
  
          /* do user initialization */
          user_init();
  
          /* the current Symbol */
          cur_token = scan();
  
          debug_message("# Current Symbol is #" + cur_token.sym);
  
          /* push dummy Symbol with start state to get us underway */
          stack.removeAllElements();
          stack.push(getSymbolFactory().startSymbol("START", 0, start_state()));
          tos = 0;
  
          /* continue until we are told to stop */
          for (_done_parsing = false; !_done_parsing;) {
              /* Check current token for freshness. */
              if (cur_token.used_by_parser)
                  throw new Error("Symbol recycling detected (fix your scanner).");
  
              /* current state is always on the top of the stack */
              // debug_stack();
  
              /*
               * look up action out of the current state with the current input
               */
              act = get_action(((Symbol) stack.peek()).parse_state, cur_token.sym);
  
              /* decode the action -- > 0 encodes shift */
              if (act > 0) {
                  /* shift to the encoded state by pushing it on the stack */
                  cur_token.parse_state = act - 1;
                  cur_token.used_by_parser = true;
                  debug_shift(cur_token);
                  stack.push(cur_token);
                  tos++;
  
                  /* advance to the next Symbol */
                  cur_token = scan();
                  debug_message("# Current token is " + cur_token);
              }
              /* if its less than zero, then it encodes a reduce action */
              else if (act < 0) {
                  /* perform the action for the reduce */
                  lhs_sym = do_action((-act) - 1, this, stack, tos);
  
                  /* look up information about the production */
                  lhs_sym_num = production_tab[(-act) - 1][0];
                  handle_size = production_tab[(-act) - 1][1];
  
                  debug_reduce((-act) - 1, lhs_sym_num, handle_size);
  
                  /* pop the handle off the stack */
                  for (int i = 0; i < handle_size; i++) {
                      stack.pop();
                      tos--;
                  }
  
                  /* look up the state to go to from the one popped back to */
                  act = get_reduce(((Symbol) stack.peek()).parse_state, lhs_sym_num);
                  debug_message("# Reduce rule: top state " + ((Symbol) stack.peek()).parse_state + ", lhs sym " + lhs_sym_num + " -> state " + act);
  
                  /* shift to that state */
                  lhs_sym.parse_state = act;
                  lhs_sym.used_by_parser = true;
                  stack.push(lhs_sym);
                  tos++;
  
                  debug_message("# Goto state #" + act);
              }
              /* finally if the entry is zero, we have an error */
              else if (act == 0) {
                  /* call user syntax error reporting routine */
                  syntax_error(cur_token);
  
                  /* try to error recover */
                  if (!error_recovery(true)) {
                      /* if that fails give up with a fatal syntax error */
                      unrecovered_syntax_error(cur_token);
  
                      /* just in case that wasn't fatal enough, end parse */
                      done_parsing();
                  } else {
                      lhs_sym = (Symbol) stack.peek();
                  }
              }
          }
          return lhs_sym;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
      /* Error recovery code */
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Attempt to recover from a syntax error. This returns false if recovery fails,
       * true if it succeeds. Recovery happens in 4 steps. First we pop the parse
       * stack down to a point at which we have a shift out of the top-most state on
       * the error Symbol. This represents the initial error recovery configuration.
       * If no such configuration is found, then we fail. Next a small number of
       * "lookahead" or "parse ahead" Symbols are read into a buffer. The size of this
       * buffer is determined by error_sync_size() and determines how many Symbols
       * beyond the error must be matched to consider the recovery a success. Next, we
       * begin to discard Symbols in attempt to get past the point of error to a point
       * where we can continue parsing. After each Symbol, we attempt to "parse ahead"
       * though the buffered lookahead Symbols. The "parse ahead" process simulates
       * that actual parse, but does not modify the real parser's configuration, nor
       * execute any actions. If we can parse all the stored Symbols without error,
       * then the recovery is considered a success. Once a successful recovery point
       * is determined, we do an actual parse over the stored input -- modifying the
       * real parse configuration and executing all actions. Finally, we return the
       * the normal parser to continue with the overall parse.
       *
       * @param debug should we produce debugging messages as we parse.
       */
      protected boolean error_recovery(boolean debug) throws java.lang.Exception {
          if (debug)
              debug_message("# Attempting error recovery");
  
          /*
           * first pop the stack back into a state that can shift on error and do that
           * shift (if that fails, we fail)
           */
          if (!find_recovery_config(debug)) {
              if (debug)
                  debug_message("# Error recovery fails");
              return false;
          }
  
          /*
           * read ahead to create lookahead we can parse multiple times
           */
          read_lookahead();
  
          /*
           * repeatedly try to parse forward until we make it the required dist
           */
          for (;;) {
              /* try to parse forward, if it makes it, bail out of loop */
              if (debug)
                  debug_message("# Trying to parse ahead");
              if (try_parse_ahead(debug)) {
                  break;
              }
  
              /* if we are now at EOF, we have failed */
              if (lookahead[0].sym == EOF_sym()) {
                  if (debug)
                      debug_message("# Error recovery fails at EOF");
                  return false;
              }
  
              /* otherwise, we consume another Symbol and try again */
              // BUG FIX by Bruce Hutton
              // Computer Science Department, University of Auckland,
              // Auckland, New Zealand.
              // It is the first token that is being consumed, not the one
              // we were up to parsing
              if (debug)
                  debug_message("# Consuming Symbol #" + lookahead[0].sym);
              restart_lookahead();
          }
  
          /* we have consumed to a point where we can parse forward */
          if (debug)
              debug_message("# Parse-ahead ok, going back to normal parse");
  
          /*
           * do the real parse (including actions) across the lookahead
           */
          parse_lookahead(debug);
  
          /* we have success */
          return true;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Determine if we can shift under the special error Symbol out of the state
       * currently on the top of the (real) parse stack.
       */
      protected boolean shift_under_error() {
          /* is there a shift under error Symbol */
          return get_action(((Symbol) stack.peek()).parse_state, error_sym()) > 0;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Put the (real) parse stack into error recovery configuration by popping the
       * stack down to a state that can shift on the special error Symbol, then doing
       * the shift. If no suitable state exists on the stack we return false
       *
       * @param debug should we produce debugging messages as we parse.
       */
      protected boolean find_recovery_config(boolean debug) {
          Symbol error_token;
          int act;
  
          if (debug)
              debug_message("# Finding recovery state on stack");
  
          /*
           * Remember the right-position of the top symbol on the stack
           */
          Symbol right = ((Symbol) stack.peek());// TUM 20060327 removed .right
          Symbol left = right;// TUM 20060327 removed .left
  
          /* pop down until we can shift under error Symbol */
          while (!shift_under_error()) {
              /* pop the stack */
              if (debug)
                  debug_message("# Pop stack by one, state was # " + ((Symbol) stack.peek()).parse_state);
              left = ((Symbol) stack.pop()); // TUM 20060327 removed .left
              tos--;
  
              /* if we have hit bottom, we fail */
              if (stack.empty()) {
                  if (debug)
                      debug_message("# No recovery state found on stack");
                  return false;
              }
          }
  
          /*
           * state on top of the stack can shift under error, find the shift
           */
          act = get_action(((Symbol) stack.peek()).parse_state, error_sym());
          if (debug) {
              debug_message("# Recover state found (#" + ((Symbol) stack.peek()).parse_state + ")");
              debug_message("# Shifting on error to state #" + (act - 1));
          }
  
          /* build and shift a special error Symbol */
          error_token = getSymbolFactory().newSymbol("ERROR", error_sym(), left, right);
          error_token.parse_state = act - 1;
          error_token.used_by_parser = true;
          stack.push(error_token);
          tos++;
  
          return true;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Lookahead Symbols used for attempting error recovery "parse aheads".
       */
      protected Symbol lookahead[];
  
      /**
       * Position in lookahead input buffer used for "parse ahead".
       */
      protected int    lookahead_pos;
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Read from input to establish our buffer of "parse ahead" lookahead Symbols.
       */
      protected void read_lookahead() throws java.lang.Exception {
          /* create the lookahead array */
          lookahead = new Symbol[error_sync_size()];
  
          /* fill in the array */
          for (int i = 0; i < error_sync_size(); i++) {
              lookahead[i] = cur_token;
              cur_token = scan();
          }
  
          /* start at the beginning */
          lookahead_pos = 0;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Return the current lookahead in our error "parse ahead" buffer.
       */
      protected Symbol cur_err_token() {
          return lookahead[lookahead_pos];
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Advance to next "parse ahead" input Symbol. Return true if we have input to
       * advance to, false otherwise.
       */
      protected boolean advance_lookahead() {
          /* advance the input location */
          lookahead_pos++;
  
          /* return true if we didn't go off the end */
          return lookahead_pos < error_sync_size();
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Reset the parse ahead input to one Symbol past where we started error
       * recovery (this consumes one new Symbol from the real input).
       */
      protected void restart_lookahead() throws java.lang.Exception {
          /* move all the existing input over */
          for (int i = 1; i < error_sync_size(); i++)
              lookahead[i - 1] = lookahead[i];
  
          /* read a new Symbol into the last spot */
          // BUG Fix by Bruce Hutton
          // Computer Science Department, University of Auckland,
          // Auckland, New Zealand. [applied 5-sep-1999 by csa]
          // The following two lines were out of order!!
          lookahead[error_sync_size() - 1] = cur_token;
          cur_token = scan();
  
          /* reset our internal position marker */
          lookahead_pos = 0;
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Do a simulated parse forward (a "parse ahead") from the current stack
       * configuration using stored lookahead input and a virtual parse stack. Return
       * true if we make it all the way through the stored lookahead input without
       * error. This basically simulates the action of parse() using only our saved
       * "parse ahead" input, and not executing any actions.
       *
       * @param debug should we produce debugging messages as we parse.
       */
      protected boolean try_parse_ahead(boolean debug) throws java.lang.Exception {
          int act;
          short lhs, rhs_size;
  
          /* create a virtual stack from the real parse stack */
          virtual_parse_stack vstack = new virtual_parse_stack(stack);
  
          /* parse until we fail or get past the lookahead input */
          for (;;) {
              /*
               * look up the action from the current state (on top of stack)
               */
              act = get_action(vstack.top(), cur_err_token().sym);
  
              /* if its an error, we fail */
              if (act == 0)
                  return false;
  
              /* > 0 encodes a shift */
              if (act > 0) {
                  /* push the new state on the stack */
                  vstack.push(act - 1);
  
                  if (debug)
                      debug_message("# Parse-ahead shifts Symbol #" + cur_err_token().sym + " into state #" + (act - 1));
  
                  /*
                   * advance simulated input, if we run off the end, we are done
                   */
                  if (!advance_lookahead())
                      return true;
              }
              /* < 0 encodes a reduce */
              else {
                  /*
                   * if this is a reduce with the start production we are done
                   */
                  if ((-act) - 1 == start_production()) {
                      if (debug)
                          debug_message("# Parse-ahead accepts");
                      return true;
                  }
  
                  /* get the lhs Symbol and the rhs size */
                  lhs = production_tab[(-act) - 1][0];
                  rhs_size = production_tab[(-act) - 1][1];
  
                  /* pop handle off the stack */
                  for (int i = 0; i < rhs_size; i++)
                      vstack.pop();
  
                  if (debug)
                      debug_message("# Parse-ahead reduces: handle size = " + rhs_size + " lhs = #" + lhs + " from state #" + vstack.top());
  
                  /* look up goto and push it onto the stack */
                  vstack.push(get_reduce(vstack.top(), lhs));
                  if (debug)
                      debug_message("# Goto state #" + vstack.top());
              }
          }
      }
  
      /*
       * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
       */
  
      /**
       * Parse forward using stored lookahead Symbols. In this case we have already
       * verified that parsing will make it through the stored lookahead Symbols and
       * we are now getting back to the point at which we can hand control back to the
       * normal parser. Consequently, this version of the parser performs all actions
       * and modifies the real parse configuration. This returns once we have consumed
       * all the stored input or we accept.
       *
       * @param debug should we produce debugging messages as we parse.
       */
      protected void parse_lookahead(boolean debug) throws java.lang.Exception {
          /* the current action code */
          int act;
  
          /* the Symbol/stack element returned by a reduce */
          Symbol lhs_sym = null;
  
          /* information about production being reduced with */
          short handle_size, lhs_sym_num;
  
          /* restart the saved input at the beginning */
          lookahead_pos = 0;
  
          if (debug) {
              debug_message("# Reparsing saved input with actions");
              debug_message("# Current Symbol is #" + cur_err_token().sym);
              debug_message("# Current state is #" + ((Symbol) stack.peek()).parse_state);
          }
  
          /*
           * continue until we accept or have read all lookahead input
           */
          while (!_done_parsing) {
              /* current state is always on the top of the stack */
  
              /*
               * look up action out of the current state with the current input
               */
              act = get_action(((Symbol) stack.peek()).parse_state, cur_err_token().sym);
  
              /* decode the action -- > 0 encodes shift */
              if (act > 0) {
                  /* shift to the encoded state by pushing it on the stack */
                  cur_err_token().parse_state = act - 1;
                  cur_err_token().used_by_parser = true;
                  if (debug)
                      debug_shift(cur_err_token());
                  stack.push(cur_err_token());
                  tos++;
  
                  /*
                   * advance to the next Symbol, if there is none, we are done
                   */
                  if (!advance_lookahead()) {
                      if (debug)
                          debug_message("# Completed reparse");
  
                      /* scan next Symbol so we can continue parse */
                      // BUGFIX by Chris Harris <ckharris@ucsd.edu>:
                      // correct a one-off error by commenting out
                      // this next line.
                      /* cur_token = scan(); */
  
                      /* go back to normal parser */
                      return;
                  }
  
                  if (debug)
                      debug_message("# Current Symbol is #" + cur_err_token().sym);
              }
              /* if its less than zero, then it encodes a reduce action */
              else if (act < 0) {
                  /* perform the action for the reduce */
                  lhs_sym = do_action((-act) - 1, this, stack, tos);
  
                  /* look up information about the production */
                  lhs_sym_num = production_tab[(-act) - 1][0];
                  handle_size = production_tab[(-act) - 1][1];
  
                  if (debug)
                      debug_reduce((-act) - 1, lhs_sym_num, handle_size);
  
                  /* pop the handle off the stack */
                  for (int i = 0; i < handle_size; i++) {
                      stack.pop();
                      tos--;
                  }
  
                  /* look up the state to go to from the one popped back to */
                  act = get_reduce(((Symbol) stack.peek()).parse_state, lhs_sym_num);
  
                  /* shift to that state */
                  lhs_sym.parse_state = act;
                  lhs_sym.used_by_parser = true;
                  stack.push(lhs_sym);
                  tos++;
  
                  if (debug)
                      debug_message("# Goto state #" + act);
  
              }
              /*
               * finally if the entry is zero, we have an error (shouldn't happen here,
               * but...)
               */
              else if (act == 0) {
                  report_fatal_error("Syntax error", lhs_sym);
                  return;
              }
          }
  
      }
  
      /*-----------------------------------------------------------*/
  
      /** Utility function: unpacks parse tables from strings */
      protected static short[][] unpackFromStrings(String[] sa) {
          // Concatanate initialization strings.
          StringBuffer sb = new StringBuffer(sa[0]);
          for (int i = 1; i < sa.length; i++)
              sb.append(sa[i]);
          int n = 0; // location in initialization string
          int size1 = ((sb.charAt(n)) << 16) | (sb.charAt(n + 1));
          n += 2;
          short[][] result = new short[size1][];
          for (int i = 0; i < size1; i++) {
              int size2 = ((sb.charAt(n)) << 16) | (sb.charAt(n + 1));
              n += 2;
              result[i] = new short[size2];
              for (int j = 0; j < size2; j++)
                  result[i][j] = (short) (sb.charAt(n++) - 2);
          }
          return result;
      }
  }
  