---

lr_parser Class Reference

Inheritance diagram for lr_parser:[legend]List of all members.

Public Methods
	lr_parser ()
	lr_parser (Scanner s)
abstract short[][]	action_table ()
void	debug_message (String mess)
Symbol	debug_parse () throws java.lang.Exception
void	debug_reduce (int prod_num, int nt_num, int rhs_size)
void	debug_shift (Symbol shift_tkn)
void	debug_stack ()
abstract Symbol	do_action (int act_num, lr_parser parser, Stack stack, int top) throws java.lang.Exception
void	done_parsing ()
void	dump_stack ()
abstract int	EOF_sym ()
abstract int	error_sym ()
Scanner	getScanner ()
Symbol	parse () throws java.lang.Exception
abstract short[][]	production_table ()
abstract short[][]	reduce_table ()
void	report_error (String message, Object info)
void	report_fatal_error (String message, Object info) throws java.lang.Exception
Symbol	scan () throws java.lang.Exception
void	setScanner (Scanner s)
abstract int	start_production ()
abstract int	start_state ()
void	syntax_error (Symbol cur_token)
void	unrecovered_syntax_error (Symbol cur_token) throws java.lang.Exception
void	user_init () throws java.lang.Exception
Protected Methods
boolean	advance_lookahead ()
Symbol	cur_err_token ()
boolean	error_recovery (boolean debug) throws java.lang.Exception
int	error_sync_size ()
boolean	find_recovery_config (boolean debug)
final short	get_action (int state, int sym)
final short	get_reduce (int state, int sym)
abstract void	init_actions () throws java.lang.Exception
void	parse_lookahead (boolean debug) throws java.lang.Exception
void	read_lookahead () throws java.lang.Exception
void	restart_lookahead () throws java.lang.Exception
boolean	shift_under_error ()
boolean	try_parse_ahead (boolean debug) throws java.lang.Exception
Static Protected Methods
short[][]	unpackFromStrings (String[] sa)
Protected Attributes
boolean	_done_parsing = false
int	tos
Symbol	cur_token
Stack	stack = new Stack()
short[][]	production_tab
short[][]	action_tab
short[][]	reduce_tab
Symbol	lookahead []
int	lookahead_pos
Static Protected Attributes
final int	_error_sync_size = 3
Private Attributes
Scanner	_scanner

---

Detailed Description

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);

See also:

java_cup.runtime.Symbol , java_cup.runtime.Symbol , java_cup.runtime.virtual_parse_stack

Version:

last updated: 7/3/96

Author:

Frank Flannery

Definition at line 147 of file lr_parser.java.

---

Constructor & Destructor Documentation

lr_parser::lr_parser (    )  [inline]

Simple constructor. Definition at line 216 of file lr_parser.java.

lr_parser::lr_parser (  Scanner   s )  [inline]

Constructor that sets the default scanner. [CSA/davidm] Definition at line 221 of file lr_parser.java.

---

Member Function Documentation

abstract int lr_parser::EOF_sym (    )  [pure virtual]

The index of the end of file terminal Symbol (supplied by generated subclass). Reimplemented in parser, and parser. Referenced by error_recovery(), and scan().

abstract short [][] lr_parser::action_table (    )  [pure virtual]

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_parserget_action Reimplemented in parser, and parser. Referenced by debug_parse(), and parse().

boolean lr_parser::advance_lookahead (    )  [inline, protected]

Advance to next "parse ahead" input Symbol. Return true if we have input to advance to, false otherwise. Definition at line 247 of file lr_parser.java. Referenced by parse_lookahead(), and try_parse_ahead().

Symbol lr_parser::cur_err_token (    )  [inline, protected]

Return the current lookahead in our error "parse ahead" buffer. Definition at line 258 of file lr_parser.java. Referenced by parse_lookahead(), and try_parse_ahead().

void lr_parser::debug_message (  String   mess )  [inline]

Write a debugging message to System.err for the debugging version of the parser. Parameters: mess   the text of the debugging message. Definition at line 266 of file lr_parser.java. Referenced by debug_parse(), debug_reduce(), debug_shift(), debug_stack(), dump_stack(), error_recovery(), find_recovery_config(), parse_lookahead(), and try_parse_ahead().

Symbol lr_parser::debug_parse (    )  [inline]

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. Definition at line 277 of file lr_parser.java.

void lr_parser::debug_reduce (  int   prod_num, int   nt_num, int   rhs_size )  [inline]

Do debug output for a reduce. Parameters: prod_num   the production we are reducing with. nt_num   the index of the LHS non terminal. rhs_size   the size of the RHS. Definition at line 401 of file lr_parser.java. Referenced by debug_parse(), and parse_lookahead().

void lr_parser::debug_shift (  Symbol   shift_tkn )  [inline]

Do debug output for shift. Parameters: shift_tkn   the Symbol being shifted onto the stack. Definition at line 412 of file lr_parser.java. Referenced by debug_parse(), and parse_lookahead().

void lr_parser::debug_stack (    )  [inline]

Do debug output for stack state. [CSA] Definition at line 421 of file lr_parser.java.

abstract Symbol lr_parser::do_action (  int   act_num, lr_parser   parser, Stack   stack, int   top )  [pure virtual]

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. Parameters: act_num   the internal index of the action to be performed. parser   the parser object we are acting for. stack   the parse stack of that object. top   the index of the top element of the parse stack. Referenced by debug_parse(), parser::do_action(), parse(), and parse_lookahead().

void lr_parser::done_parsing (    )  [inline]

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. Definition at line 457 of file lr_parser.java. Referenced by debug_parse(), actions::do_action(), parse(), and report_fatal_error().

void lr_parser::dump_stack (    )  [inline]

Dump the parse stack for debugging purposes. Definition at line 464 of file lr_parser.java.

boolean lr_parser::error_recovery (  boolean   debug )  [inline, protected]

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. Parameters: debug   should we produce debugging messages as we parse. Definition at line 514 of file lr_parser.java. Referenced by debug_parse(), and parse().

abstract int lr_parser::error_sym (    )  [pure virtual]

The index of the special error Symbol (supplied by generated subclass). Reimplemented in parser, and parser. Referenced by find_recovery_config(), and shift_under_error().

int lr_parser::error_sync_size (    )  [inline, protected]

The number of Symbols after an error we much match to consider it recovered from. Definition at line 576 of file lr_parser.java. Referenced by advance_lookahead(), read_lookahead(), and restart_lookahead().

boolean lr_parser::find_recovery_config (  boolean   debug )  [inline, protected]

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 Parameters: debug   should we produce debugging messages as we parse. Definition at line 586 of file lr_parser.java. Referenced by error_recovery().

Scanner lr_parser::getScanner (    )  [inline]

Simple accessor method to get the default scanner. Definition at line 724 of file lr_parser.java. Referenced by actions::do_action(), parser::report_error(), and scan().

final short lr_parser::get_action (  int   state, int   sym )  [inline, protected]

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). Parameters: state   the state index of the action being accessed. sym   the Symbol index of the action being accessed. Definition at line 645 of file lr_parser.java. Referenced by debug_parse(), find_recovery_config(), parse(), parse_lookahead(), shift_under_error(), and try_parse_ahead().

final short lr_parser::get_reduce (  int   state, int   sym )  [inline, protected]

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. Parameters: state   the state index of the entry being accessed. sym   the Symbol index of the entry being accessed. Definition at line 699 of file lr_parser.java. Referenced by debug_parse(), parse(), parse_lookahead(), and try_parse_ahead().

abstract void lr_parser::init_actions (    )  [protected, pure virtual]

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. Reimplemented in parser, and parser. Referenced by debug_parse(), and parse().

Symbol lr_parser::parse (    )  [inline]

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. Definition at line 740 of file lr_parser.java.

void lr_parser::parse_lookahead (  boolean   debug )  [inline, protected]

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. Parameters: debug   should we produce debugging messages as we parse. Definition at line 853 of file lr_parser.java. Referenced by error_recovery().

abstract short [][] lr_parser::production_table (    )  [pure virtual]

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. Reimplemented in parser, and parser. Referenced by debug_parse(), and parse().

void lr_parser::read_lookahead (    )  [inline, protected]

Read from input to establish our buffer of "parse ahead" lookahead Symbols. Definition at line 972 of file lr_parser.java. Referenced by error_recovery().

abstract short [][] lr_parser::reduce_table (    )  [pure virtual]

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 also: java_cup.runtime.lr_parserget_reduce Reimplemented in parser, and parser. Referenced by debug_parse(), and parse().

void lr_parser::report_error (  String   message, Object   info )  [inline]

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. Parameters: message   an error message. info   an extra object reserved for use by specialized subclasses. Reimplemented in parser, and parser. Definition at line 1014 of file lr_parser.java. Referenced by report_fatal_error(), and syntax_error().

void lr_parser::report_fatal_error (  String   message, Object   info )  [inline]

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. Parameters: message   an error message. info   an extra object reserved for use by specialized subclasses. Definition at line 1034 of file lr_parser.java. Referenced by parse_lookahead(), and unrecovered_syntax_error().

void lr_parser::restart_lookahead (    )  [inline, protected]

Reset the parse ahead input to one Symbol past where we started error recovery (this consumes one new Symbol from the real input). Definition at line 1053 of file lr_parser.java. Referenced by error_recovery().

Symbol lr_parser::scan (    )  [inline]

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. Definition at line 1080 of file lr_parser.java. Referenced by debug_parse(), parse(), read_lookahead(), and restart_lookahead().

void lr_parser::setScanner (  Scanner   s )  [inline]

Simple accessor method to set the default scanner. Definition at line 1087 of file lr_parser.java. Referenced by lr_parser().

boolean lr_parser::shift_under_error (    )  [inline, protected]

Determine if we can shift under the special error Symbol out of the state currently on the top of the (real) parse stack. Definition at line 1093 of file lr_parser.java. Referenced by find_recovery_config().

abstract int lr_parser::start_production (    )  [pure virtual]

The index of the start production (supplied by generated subclass). Reimplemented in parser, and parser. Referenced by try_parse_ahead().

abstract int lr_parser::start_state (    )  [pure virtual]

The index of the start state (supplied by generated subclass). Reimplemented in parser, and parser. Referenced by debug_parse(), and parse().

void lr_parser::syntax_error (  Symbol   cur_token )  [inline]

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. Parameters: cur_token   the current lookahead Symbol. Definition at line 1114 of file lr_parser.java. Referenced by debug_parse(), and parse().

boolean lr_parser::try_parse_ahead (  boolean   debug )  [inline, protected]

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. Parameters: debug   should we produce debugging messages as we parse. Definition at line 1129 of file lr_parser.java. Referenced by error_recovery().

short [][] lr_parser::unpackFromStrings (  String   sa[] )  [inline, static, protected]

Utility function: unpacks parse tables from strings Definition at line 1191 of file lr_parser.java.

void lr_parser::unrecovered_syntax_error (  Symbol   cur_token )  [inline]

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. Parameters: cur_token   the current lookahead Symbol. Definition at line 1215 of file lr_parser.java. Referenced by debug_parse(), and parse().

void lr_parser::user_init (    )  [inline]

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. Definition at line 1229 of file lr_parser.java. Referenced by debug_parse(), and parse().

---

Member Data Documentation

boolean lr_parser::_done_parsing = false [protected]

Internal flag to indicate when parser should quit. Definition at line 161 of file lr_parser.java.

final int lr_parser::_error_sync_size = 3 [static, protected]

The default number of Symbols after an error we much match to consider it recovered from. Definition at line 156 of file lr_parser.java.

Scanner lr_parser::_scanner [private]

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] Definition at line 201 of file lr_parser.java.

short [][] lr_parser::action_tab [protected]

Direct reference to the action table. Definition at line 189 of file lr_parser.java.

Symbol lr_parser::cur_token [protected]

The current lookahead Symbol. Definition at line 174 of file lr_parser.java.

Symbol lr_parser::lookahead[] [protected]

Lookahead Symbols used for attempting error recovery "parse aheads". Definition at line 206 of file lr_parser.java.

int lr_parser::lookahead_pos [protected]

Position in lookahead input buffer used for "parse ahead". Definition at line 209 of file lr_parser.java.

short [][] lr_parser::production_tab [protected]

Direct reference to the production table. Definition at line 184 of file lr_parser.java.

short [][] lr_parser::reduce_tab [protected]

Direct reference to the reduce-goto table. Definition at line 194 of file lr_parser.java.

Stack lr_parser::stack = new Stack() [protected]

The parse stack itself. Definition at line 179 of file lr_parser.java.

int lr_parser::tos [protected]

Indication of the index for top of stack (for use by actions). Definition at line 169 of file lr_parser.java.

---

The documentation for this class was generated from the following file:

• lr_parser.java

---