CUP Parser Generator for Java 10k · java_cup.runtime.lr_parser

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.

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.

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.

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:

short[][] production_table(): 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).
short[][] action_table(): Provides a reference to the parse action table.
short[][] reduce_table(): Provides a reference to the reduce-goto table.
int start_state(): Indicates the index of the start state.
int start_production(): Indicates the index of the starting production.
int EOF_sym(): Indicates the index of the EOF Symbol.
int error_sym(): Indicates the index of the error Symbol.
Symbol do_action(): 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.
void init_actions(): Code to initialize a special object that encapsulates user supplied actions (this object is used by do_action() to actually carry out the actions).

In addition to these routines that must be supplied by the generated subclass there are also a series of routines that may be supplied. These include:

Symbol scan(): Used to get the next input Symbol from the scanner.
Scanner getScanner(): Used to provide a scanner for the default implementation of scan().
int error_sync_size(): 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.
void report_error(String message, Object info): 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.
void report_fatal_error(String message, Object info): 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.
void syntax_error(Symbol cur_token): 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);
void unrecovered_syntax_error(Symbol cur_token): This method is called if syntax error recovery fails. In the default implementation it invokes:
report_fatal_error("Couldn't repair and continue parse", null);

Field Summary

Modifier and Type	Field and Description
protected boolean	_done_parsing Internal flag to indicate when parser should quit.
protected static final int	_error_sync_size The default number of Symbols after an error we much match to consider it recovered from.
private Scanner	_scanner This is the scanner object used by the default implementation of scan() to get Symbols.
protected short[][]	action_tab Direct reference to the action table.
protected Symbol	cur_token The current lookahead Symbol.
protected Symbol[]	lookahead Lookahead Symbols used for attempting error recovery "parse aheads".
protected int	lookahead_pos Position in lookahead input buffer used for "parse ahead".
protected short[][]	production_tab Direct reference to the production table.
protected short[][]	reduce_tab Direct reference to the reduce-goto table.
protected Stack<E>	stack The parse stack itself.
protected int	tos Indication of the index for top of stack (for use by actions).

Constructor Summary

Access	Constructor and Description
public	lr_parser() Simple constructor.
public	lr_parser(Scanner s) Constructor that sets the default scanner.

Method Summary

Modifier and Type	Method and Description
public abstract short[][]	action_table() The action table (supplied by generated subclass).
protected boolean	advance_lookahead() Advance to next "parse ahead" input Symbol.
protected Symbol	cur_err_token() Return the current lookahead in our error "parse ahead" buffer.
public void	debug_message(String the text of the debugging message. mess) Write a debugging message to System.err for the debugging version of the parser.
public Symbol	debug_parse() Perform a parse with debugging output.
public void	debug_reduce(int the production we are reducing with. prod_num, int the index of the LHS non terminal. nt_num, int the size of the RHS. rhs_size) Do debug output for a reduce.
public void	debug_shift(Symbol the Symbol being shifted onto the stack. shift_tkn) Do debug output for shift.
public void	debug_stack() Do debug output for stack state.
public abstract Symbol	do_action(int the internal index of the action to be performed. act_num, lr_parser the parser object we are acting for. parser, Stack<E> the parse stack of that object. stack, int the index of the top element of the parse stack. top) Perform a bit of user supplied action code (supplied by generated subclass).
public void	done_parsing() This method is called to indicate that the parser should quit.
public void	dump_stack() Dump the parse stack for debugging purposes.
public abstract int	EOF_sym() The index of the end of file terminal Symbol (supplied by generated subclass).
protected boolean	error_recovery(boolean should we produce debugging messages as we parse. debug) Attempt to recover from a syntax error.
public abstract int	error_sym() The index of the special error Symbol (supplied by generated subclass).
protected int	error_sync_size() The number of Symbols after an error we much match to consider it recovered from.
protected boolean	find_recovery_config(boolean should we produce debugging messages as we parse. debug) 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.
protected final short	get_action(int the state index of the action being accessed. state, int the Symbol index of the action being accessed. sym) Fetch an action from the action table.
protected final short	get_reduce(int the state index of the entry being accessed. state, int the Symbol index of the entry being accessed. sym) Fetch a state from the reduce-goto table.
public Scanner	getScanner() Simple accessor method to get the default scanner.
protected abstract void	init_actions() Initialize the action object.
public Symbol	parse() This method provides the main parsing routine.
protected void	parse_lookahead(boolean should we produce debugging messages as we parse. debug) Parse forward using stored lookahead Symbols.
public abstract short[][]	production_table() Table of production information (supplied by generated subclass).
protected void	read_lookahead() Read from input to establish our buffer of "parse ahead" lookahead Symbols.
public abstract short[][]	reduce_table() The reduce-goto table (supplied by generated subclass).
public void	report_error(String an error message. message, Object an extra object reserved for use by specialized subclasses. info) Report a non fatal error (or warning).
public void	report_fatal_error(String an error message. message, Object an extra object reserved for use by specialized subclasses. info) Report a fatal error.
protected void	restart_lookahead() Reset the parse ahead input to one Symbol past where we started error recovery (this consumes one new Symbol from the real input).
public Symbol	scan() Get the next Symbol from the input (supplied by generated subclass).
public void	setScanner(Scanner s) Simple accessor method to set the default scanner.
protected boolean	shift_under_error() Determine if we can shift under the special error Symbol out of the state currently on the top of the (real) parse stack.
public abstract int	start_production() The index of the start production (supplied by generated subclass).
public abstract int	start_state() The index of the start state (supplied by generated subclass).
public void	syntax_error(Symbol the current lookahead Symbol. cur_token) This method is called when a syntax error has been detected and recovery is about to be invoked.
protected boolean	try_parse_ahead(boolean should we produce debugging messages as we parse. debug) Do a simulated parse forward (a "parse ahead") from the current stack configuration using stored lookahead input and a virtual parse stack.
protected static short[][]	unpackFromStrings(String[] sa) Utility function: unpacks parse tables from strings
public void	unrecovered_syntax_error(Symbol the current lookahead Symbol. cur_token) This method is called if it is determined that syntax error recovery has been unsuccessful.
public void	user_init() User code for initialization inside the parser.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

_done_parsing	back to summary
protected boolean _done_parsing Internal flag to indicate when parser should quit.

_error_sync_size	back to summary
protected static final int _error_sync_size The default number of Symbols after an error we much match to consider it recovered from.

_scanner	back to summary
private Scanner _scanner 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]

action_tab	back to summary
protected short[][] action_tab Direct reference to the action table.

cur_token	back to summary
protected Symbol cur_token The current lookahead Symbol.

lookahead	back to summary
protected Symbol[] lookahead Lookahead Symbols used for attempting error recovery "parse aheads".

lookahead_pos	back to summary
protected int lookahead_pos Position in lookahead input buffer used for "parse ahead".

production_tab	back to summary
protected short[][] production_tab Direct reference to the production table.

reduce_tab	back to summary
protected short[][] reduce_tab Direct reference to the reduce-goto table.

stack	back to summary
protected Stack<E> stack The parse stack itself.

tos	back to summary
protected int tos Indication of the index for top of stack (for use by actions).

Constructor Detail

lr_parser	back to summary
public lr_parser() Simple constructor.

lr_parser	back to summary
public lr_parser(Scanner s) Constructor that sets the default scanner. [CSA/davidm]

Method Detail

action_table back to summary

action_table	back to summary
public abstract short[][] action_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 Also `java_cup.runtime.lr_parser#get_action`

public abstract short[][] action_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 Also: java_cup.runtime.lr_parser#get_action

advance_lookahead	back to summary
protected boolean advance_lookahead() Advance to next "parse ahead" input Symbol. Return true if we have input to advance to, false otherwise.

cur_err_token	back to summary
protected Symbol cur_err_token() Return the current lookahead in our error "parse ahead" buffer.

debug_message	back to summary
public void debug_message(String mess) Write a debugging message to System.err for the debugging version of the parser. Parameters mess:String the text of the debugging message.