Logo Search packages:      
Sourcecode: jasmin-sable version File versions  Download package

java_cup::runtime::lr_parser Class Reference

Inheritance diagram for java_cup::runtime::lr_parser:

jasmin::parser java_cup::parser java_cup::simple_calc::parser

List of all members.

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:



last updated: 7/3/96
Frank Flannery

Definition at line 115 of file lr_parser.java.

Public Member Functions

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 ()
 lr_parser (Scanner s)
 lr_parser ()
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 Member Functions

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 Member Functions

static short[][] unpackFromStrings (String[] sa)

Protected Attributes

boolean _done_parsing = false
short[][] action_tab
Symbol cur_token
Symbol lookahead []
int lookahead_pos
short[][] production_tab
short[][] reduce_tab
Stack stack = new Stack()
int tos

Static Protected Attributes

static final int _error_sync_size = 3

Private Attributes

Scanner _scanner

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

Generated by  Doxygen 1.6.0   Back to index