| Methods Summary |
|---|
| public abstract int | EOF_sym()The index of the end of file terminal Symbol (supplied by generated
subclass).
|
| 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.
|
| protected boolean | advance_lookahead()Advance to next "parse ahead" input Symbol. Return true if we have
input to advance to, false otherwise.
/* advance the input location */
lookahead_pos++;
/* return true if we didn't go off the end */
return lookahead_pos < error_sync_size();
|
| protected com.sun.java_cup.internal.runtime.Symbol | cur_err_token()Return the current lookahead in our error "parse ahead" buffer. return lookahead[lookahead_pos];
|
| public void | debug_message(java.lang.String mess)Write a debugging message to System.err for the debugging version
of the parser.
System.err.println(mess);
|
| public com.sun.java_cup.internal.runtime.Symbol | debug_parse()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.
/* 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(((Symbol)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(((Symbol)stack.peek()).parse_state, lhs_sym_num);
debug_message("# Reduce rule: top state " +
((Symbol)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 = (Symbol)stack.peek();
}
}
}
return lhs_sym;
|
| public void | debug_reduce(int prod_num, int nt_num, int rhs_size)Do debug output for a reduce.
debug_message("# Reduce with prod #" + prod_num + " [NT=" + nt_num +
", " + "SZ=" + rhs_size + "]");
|
| public void | debug_shift(com.sun.java_cup.internal.runtime.Symbol shift_tkn)Do debug output for shift.
debug_message("# Shift under term #" + shift_tkn.sym +
" to state #" + shift_tkn.parse_state);
|
| public void | debug_stack()Do debug output for stack state. [CSA]
StringBuffer sb=new StringBuffer("## STACK:");
for (int i=0; i<stack.size(); i++) {
Symbol s = (Symbol) stack.elementAt(i);
sb.append(" <state "+s.parse_state+", sym "+s.sym+">");
if ((i%3)==2 || (i==(stack.size()-1))) {
debug_message(sb.toString());
sb = new StringBuffer(" ");
}
}
|
| public abstract com.sun.java_cup.internal.runtime.Symbol | do_action(int act_num, com.sun.java_cup.internal.runtime.lr_parser parser, java.util.Stack stack, int top)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.
|
| 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.
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
_done_parsing = true;
|
| public void | dump_stack()Dump the parse stack for debugging purposes.
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: " + ((Symbol)stack.elementAt(i)).sym +
" State: " + ((Symbol)stack.elementAt(i)).parse_state);
}
debug_message("==========================================");
|
| protected boolean | error_recovery(boolean debug)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.
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;
|
| 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.
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
return _error_sync_size;
|
| protected boolean | find_recovery_config(boolean 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. If no suitable state exists on
the stack we return false
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 = ((Symbol)stack.peek()).right;
int left_pos = ((Symbol)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 # " +
((Symbol)stack.peek()).parse_state);
left_pos = ((Symbol)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(((Symbol)stack.peek()).parse_state, error_sym());
if (debug)
{
debug_message("# Recover state found (#" +
((Symbol)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;
|
| public com.sun.java_cup.internal.runtime.Scanner | getScanner()Simple accessor method to get the default scanner. return _scanner;
|
| protected final short | get_action(int state, int sym)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).
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;
|
| protected final short | get_reduce(int state, int sym)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.
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;
|
| protected abstract void | init_actions()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.
|
| public com.sun.java_cup.internal.runtime.Symbol | parse()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.
/* 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(((Symbol)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(((Symbol)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 = (Symbol)stack.peek();
}
}
}
return lhs_sym;
|
| protected void | parse_lookahead(boolean debug)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.
/* 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 #" +
((Symbol)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(((Symbol)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(((Symbol)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;
}
}
|
| 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.
|
| protected void | read_lookahead()Read from input to establish our buffer of "parse ahead" lookahead
Symbols.
/* 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;
|
| 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.
|
| 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.
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("");
|
| public void | report_fatal_error(java.lang.String message, java.lang.Object info)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.
/* 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)");
|
| 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).
/* 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;
|
| public com.sun.java_cup.internal.runtime.Symbol | scan()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.
return getScanner().next_token();
|
| public void | setScanner(com.sun.java_cup.internal.runtime.Scanner s)Simple accessor method to set the default scanner.
_scanner = s;
|
| 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.
/* is there a shift under error Symbol */
return get_action(((Symbol)stack.peek()).parse_state, error_sym()) > 0;
|
| 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(com.sun.java_cup.internal.runtime.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.
report_error("Syntax error", cur_token);
|
| protected boolean | try_parse_ahead(boolean debug)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.
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());
}
}
|
| protected static short[][] | unpackFromStrings(java.lang.String[] sa)Utility function: unpacks parse tables from strings
// Concatanate initialization strings.
StringBuffer sb = new StringBuffer(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;
|
| public void | unrecovered_syntax_error(com.sun.java_cup.internal.runtime.Symbol 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.
report_fatal_error("Couldn't repair and continue parse", cur_token);
|
| public void | user_init()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.
|
