Back to index...

	/*
	* Copyright (c) 2003, 2017, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/


	package com.sun.java_cup.internal.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 com.sun.java_cup.internal.runtime.Symbol
	* @see com.sun.java_cup.internal.runtime.Symbol
	* @see com.sun.java_cup.internal.runtime.virtual_parse_stack
	* @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 com.sun.java_cup.internal.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 com.sun.java_cup.internal.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<Symbol> 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 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 {
	return getScanner().next_token();
	}

	/. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ./

	/** 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((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((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 = 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: " + (stack.get(i)).sym +
	" State: " + (stack.get(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() {
	StringBuilder sb=new StringBuilder("## STACK:");
	for (int i=0; i<stack.size(); i++) {
	Symbol s = stack.get(i);
	sb.append(" <state "+s.parse_state+", sym "+s.sym+">");
	if ((i%3)==2 \|\| (i==(stack.size()-1))) {
	debug_message(sb.toString());
	sb = new StringBuilder(" ");
	}
	}
	}

	/. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ./

	/** 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((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((stack.peek()).parse_state, lhs_sym_num);
	debug_message("# Reduce rule: top state " +
	(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 = 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 */
	if (debug)
	debug_message("# Consuming Symbol #" + cur_err_token().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((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 = (stack.peek()).right;
	int left_pos = (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 # " +
	(stack.peek()).parse_state);
	left_pos = 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((stack.peek()).parse_state, error_sym());
	if (debug)
	{
	debug_message("# Recover state found (#" +
	(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 */
	cur_token = scan();
	lookahead[error_sync_size()-1] = cur_token;

	/* 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 #" +
	(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((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((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.
	StringBuilder sb = new StringBuilder(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;
	}
	}

Back to index...