+++ /dev/null
-
-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 java_cup.runtime.Symbol
- * @see java_cup.runtime.Symbol
- * @see java_cup.runtime.virtual_parse_stack
- * @version last updated: 7/3/96
- * @author Frank Flannery
- */
-
-public abstract class lr_parser {
-
- /*-----------------------------------------------------------*/
- /*--- Constructor(s) ----------------------------------------*/
- /*-----------------------------------------------------------*/
-
- /** Simple constructor. */
- public lr_parser()
- {
- /* nothing to do here */
- }
-
- /** Constructor that sets the default scanner. [CSA/davidm] */
- public lr_parser(Scanner s) {
- this(); /* in case default constructor someday does something */
- setScanner(s);
- }
-
- /*-----------------------------------------------------------*/
- /*--- (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 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 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 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 overriden 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 : new Symbol(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);
- 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)
- {
- 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(new Symbol(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(new Symbol(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 */
- int right_pos = ((Symbol)stack.peek()).right;
- int left_pos = ((Symbol)stack.peek()).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_pos = ((Symbol)stack.pop()).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 = new Symbol(error_sym(), left_pos, right_pos);
- 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 = (((int)sb.charAt(n))<<16) | ((int)sb.charAt(n+1)); n+=2;
- short[][] result = new short[size1][];
- for (int i=0; i<size1; i++) {
- int size2 = (((int)sb.charAt(n))<<16) | ((int)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;
- }
-}
-
projects / IRC.git / blobdiff