java_cup.runtime
Class lr_parser

java.lang.Object
  java_cup.runtime.lr_parser

Direct Known Subclasses:

AnnotationParser, EvaluationParser, MusicParser, parser

public abstract class lr_parser
extends java.lang.Object

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

Version:

last updated: 7/3/96

Author:

Frank Flannery

See Also:

Symbol, Symbol, virtual_parse_stack

Constructor Summary

lr_parser()
Simple constructor.

lr_parser(Scanner s)
Constructor that sets the default scanner.

Method Summary

abstract short[][]	action_table() The action table (supplied by generated subclass).
void	debug_message(java.lang.String mess) Write a debugging message to System.err for the debugging version of the parser.
Symbol	debug_parse() Perform a parse with debugging output.
void	debug_reduce(int prod_num, int nt_num, int rhs_size) Do debug output for a reduce.
void	debug_shift(Symbol shift_tkn) Do debug output for shift.
void	debug_stack() Do debug output for stack state.
abstract Symbol	do_action(int act_num, lr_parser parser, java.util.Stack stack, int top) Perform a bit of user supplied action code (supplied by generated subclass).
void	done_parsing() This method is called to indicate that the parser should quit.
void	dump_stack() Dump the parse stack for debugging purposes.
abstract int	EOF_sym() The index of the end of file terminal Symbol (supplied by generated subclass).
abstract int	error_sym() The index of the special error Symbol (supplied by generated subclass).
Scanner	getScanner() Simple accessor method to get the default scanner.
Symbol	parse() This method provides the main parsing routine.
abstract short[][]	production_table() Table of production information (supplied by generated subclass).
abstract short[][]	reduce_table() The reduce-goto table (supplied by generated subclass).
void	report_error(java.lang.String message, java.lang.Object info) Report a non fatal error (or warning).
void	report_fatal_error(java.lang.String message, java.lang.Object info) Report a fatal error.
Symbol	scan() Get the next Symbol from the input (supplied by generated subclass).
void	setScanner(Scanner s) Simple accessor method to set the default scanner.
abstract int	start_production() The index of the start production (supplied by generated subclass).
abstract int	start_state() The index of the start state (supplied by generated subclass).
void	syntax_error(Symbol cur_token) This method is called when a syntax error has been detected and recovery is about to be invoked.
void	unrecovered_syntax_error(Symbol cur_token) This method is called if it is determined that syntax error recovery has been unsuccessful.
void	user_init() User code for initialization inside the parser.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

lr_parser

public lr_parser()

Simple constructor.

lr_parser

public lr_parser(Scanner s)

Constructor that sets the default scanner. [CSA/davidm]

Method Detail

production_table

public abstract short[][] production_table()

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.

action_table

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:

get_action(int, int)

reduce_table

public abstract short[][] reduce_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 Also:

get_reduce(int, int)

start_state

public abstract int start_state()

The index of the start state (supplied by generated subclass).

start_production

public abstract int start_production()

The index of the start production (supplied by generated subclass).

EOF_sym

public abstract int EOF_sym()

The index of the end of file terminal Symbol (supplied by generated subclass).

error_sym

public abstract int error_sym()

The index of the special error Symbol (supplied by generated subclass).

done_parsing

public void done_parsing()

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.

setScanner

public void setScanner(Scanner s)

Simple accessor method to set the default scanner.

getScanner

public Scanner getScanner()

Simple accessor method to get the default scanner.

do_action

public abstract Symbol do_action(int act_num,
                                 lr_parser parser,
                                 java.util.Stack stack,
                                 int top)
                          throws java.lang.Exception

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.

Throws:

java.lang.Exception

user_init

public void user_init()
               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.

Throws:

java.lang.Exception

scan

public Symbol scan()
            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.

Throws:

java.lang.Exception

report_fatal_error

public void report_fatal_error(java.lang.String message,
                               java.lang.Object info)
                        throws java.lang.Exception

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.

Throws:

java.lang.Exception

report_error

public void report_error(java.lang.String message,
                         java.lang.Object info)

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.

syntax_error

public void syntax_error(Symbol cur_token)

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.

unrecovered_syntax_error

public void unrecovered_syntax_error(Symbol cur_token)
                              throws java.lang.Exception

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.

Throws:

java.lang.Exception

parse

public Symbol parse()
             throws java.lang.Exception

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.

Throws:

java.lang.Exception

debug_message

public void debug_message(java.lang.String mess)

Write a debugging message to System.err for the debugging version of the parser.

Parameters:

mess - the text of the debugging message.

dump_stack

public void dump_stack()

Dump the parse stack for debugging purposes.

debug_reduce

public void debug_reduce(int prod_num,
                         int nt_num,
                         int rhs_size)

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.

debug_shift

public void debug_shift(Symbol shift_tkn)

Do debug output for shift.

Parameters:

shift_tkn - the Symbol being shifted onto the stack.

debug_stack

public void debug_stack()

Do debug output for stack state. [CSA]

debug_parse

public Symbol debug_parse()
                   throws java.lang.Exception

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.

Throws:

java.lang.Exception