0001: package java_cup.runtime;
0002:
0003: import java.util.Stack;
0004:
0005: /** This class implements a skeleton table driven LR parser. In general,
0006: * LR parsers are a form of bottom up shift-reduce parsers. Shift-reduce
0007: * parsers act by shifting input onto a parse stack until the Symbols
0008: * matching the right hand side of a production appear on the top of the
0009: * stack. Once this occurs, a reduce is performed. This involves removing
0010: * the Symbols corresponding to the right hand side of the production
0011: * (the so called "handle") and replacing them with the non-terminal from
0012: * the left hand side of the production. <p>
0013: *
0014: * To control the decision of whether to shift or reduce at any given point,
0015: * the parser uses a state machine (the "viable prefix recognition machine"
0016: * built by the parser generator). The current state of the machine is placed
0017: * on top of the parse stack (stored as part of a Symbol object representing
0018: * a terminal or non terminal). The parse action table is consulted
0019: * (using the current state and the current lookahead Symbol as indexes) to
0020: * determine whether to shift or to reduce. When the parser shifts, it
0021: * changes to a new state by pushing a new Symbol (containing a new state)
0022: * onto the stack. When the parser reduces, it pops the handle (right hand
0023: * side of a production) off the stack. This leaves the parser in the state
0024: * it was in before any of those Symbols were matched. Next the reduce-goto
0025: * table is consulted (using the new state and current lookahead Symbol as
0026: * indexes) to determine a new state to go to. The parser then shifts to
0027: * this goto state by pushing the left hand side Symbol of the production
0028: * (also containing the new state) onto the stack.<p>
0029: *
0030: * This class actually provides four LR parsers. The methods parse() and
0031: * debug_parse() provide two versions of the main parser (the only difference
0032: * being that debug_parse() emits debugging trace messages as it parses).
0033: * In addition to these main parsers, the error recovery mechanism uses two
0034: * more. One of these is used to simulate "parsing ahead" in the input
0035: * without carrying out actions (to verify that a potential error recovery
0036: * has worked), and the other is used to parse through buffered "parse ahead"
0037: * input in order to execute all actions and re-synchronize the actual parser
0038: * configuration.<p>
0039: *
0040: * This is an abstract class which is normally filled out by a subclass
0041: * generated by the JavaCup parser generator. In addition to supplying
0042: * the actual parse tables, generated code also supplies methods which
0043: * invoke various pieces of user supplied code, provide access to certain
0044: * special Symbols (e.g., EOF and error), etc. Specifically, the following
0045: * abstract methods are normally supplied by generated code:
0046: * <dl compact>
0047: * <dt> short[][] production_table()
0048: * <dd> Provides a reference to the production table (indicating the index of
0049: * the left hand side non terminal and the length of the right hand side
0050: * for each production in the grammar).
0051: * <dt> short[][] action_table()
0052: * <dd> Provides a reference to the parse action table.
0053: * <dt> short[][] reduce_table()
0054: * <dd> Provides a reference to the reduce-goto table.
0055: * <dt> int start_state()
0056: * <dd> Indicates the index of the start state.
0057: * <dt> int start_production()
0058: * <dd> Indicates the index of the starting production.
0059: * <dt> int EOF_sym()
0060: * <dd> Indicates the index of the EOF Symbol.
0061: * <dt> int error_sym()
0062: * <dd> Indicates the index of the error Symbol.
0063: * <dt> Symbol do_action()
0064: * <dd> Executes a piece of user supplied action code. This always comes at
0065: * the point of a reduce in the parse, so this code also allocates and
0066: * fills in the left hand side non terminal Symbol object that is to be
0067: * pushed onto the stack for the reduce.
0068: * <dt> void init_actions()
0069: * <dd> Code to initialize a special object that encapsulates user supplied
0070: * actions (this object is used by do_action() to actually carry out the
0071: * actions).
0072: * </dl>
0073: *
0074: * In addition to these routines that <i>must</i> be supplied by the
0075: * generated subclass there are also a series of routines that <i>may</i>
0076: * be supplied. These include:
0077: * <dl>
0078: * <dt> Symbol scan()
0079: * <dd> Used to get the next input Symbol from the scanner.
0080: * <dt> Scanner getScanner()
0081: * <dd> Used to provide a scanner for the default implementation of
0082: * scan().
0083: * <dt> int error_sync_size()
0084: * <dd> This determines how many Symbols past the point of an error
0085: * must be parsed without error in order to consider a recovery to
0086: * be valid. This defaults to 3. Values less than 2 are not
0087: * recommended.
0088: * <dt> void report_error(String message, Object info)
0089: * <dd> This method is called to report an error. The default implementation
0090: * simply prints a message to System.err and where the error occurred.
0091: * This method is often replaced in order to provide a more sophisticated
0092: * error reporting mechanism.
0093: * <dt> void report_fatal_error(String message, Object info)
0094: * <dd> This method is called when a fatal error that cannot be recovered from
0095: * is encountered. In the default implementation, it calls
0096: * report_error() to emit a message, then throws an exception.
0097: * <dt> void syntax_error(Symbol cur_token)
0098: * <dd> This method is called as soon as syntax error is detected (but
0099: * before recovery is attempted). In the default implementation it
0100: * invokes: report_error("Syntax error", null);
0101: * <dt> void unrecovered_syntax_error(Symbol cur_token)
0102: * <dd> This method is called if syntax error recovery fails. In the default
0103: * implementation it invokes:<br>
0104: * report_fatal_error("Couldn't repair and continue parse", null);
0105: * </dl>
0106: *
0107: * @see java_cup.runtime.Symbol
0108: * @see java_cup.runtime.Symbol
0109: * @see java_cup.runtime.virtual_parse_stack
0110: * @version last updated: 7/3/96
0111: * @author Frank Flannery
0112: */
0113:
0114: public abstract class lr_parser {
0115:
0116: /*-----------------------------------------------------------*/
0117: /*--- Constructor(s) ----------------------------------------*/
0118: /*-----------------------------------------------------------*/
0119:
0120: /** Simple constructor. */
0121: public lr_parser() {
0122: /* nothing to do here */
0123: }
0124:
0125: /** Constructor that sets the default scanner. [CSA/davidm] */
0126: public lr_parser(Scanner s) {
0127: this (); /* in case default constructor someday does something */
0128: setScanner(s);
0129: }
0130:
0131: /*-----------------------------------------------------------*/
0132: /*--- (Access to) Static (Class) Variables ------------------*/
0133: /*-----------------------------------------------------------*/
0134:
0135: /** The default number of Symbols after an error we much match to consider
0136: * it recovered from.
0137: */
0138: protected final static int _error_sync_size = 3;
0139:
0140: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0141:
0142: /** The number of Symbols after an error we much match to consider it
0143: * recovered from.
0144: */
0145: protected int error_sync_size() {
0146: return _error_sync_size;
0147: }
0148:
0149: /*-----------------------------------------------------------*/
0150: /*--- (Access to) Instance Variables ------------------------*/
0151: /*-----------------------------------------------------------*/
0152:
0153: /** Table of production information (supplied by generated subclass).
0154: * This table contains one entry per production and is indexed by
0155: * the negative-encoded values (reduce actions) in the action_table.
0156: * Each entry has two parts, the index of the non-terminal on the
0157: * left hand side of the production, and the number of Symbols
0158: * on the right hand side.
0159: */
0160: public abstract short[][] production_table();
0161:
0162: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0163:
0164: /** The action table (supplied by generated subclass). This table is
0165: * indexed by state and terminal number indicating what action is to
0166: * be taken when the parser is in the given state (i.e., the given state
0167: * is on top of the stack) and the given terminal is next on the input.
0168: * States are indexed using the first dimension, however, the entries for
0169: * a given state are compacted and stored in adjacent index, value pairs
0170: * which are searched for rather than accessed directly (see get_action()).
0171: * The actions stored in the table will be either shifts, reduces, or
0172: * errors. Shifts are encoded as positive values (one greater than the
0173: * state shifted to). Reduces are encoded as negative values (one less
0174: * than the production reduced by). Error entries are denoted by zero.
0175: *
0176: * @see java_cup.runtime.lr_parser#get_action
0177: */
0178: public abstract short[][] action_table();
0179:
0180: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0181:
0182: /** The reduce-goto table (supplied by generated subclass). This
0183: * table is indexed by state and non-terminal number and contains
0184: * state numbers. States are indexed using the first dimension, however,
0185: * the entries for a given state are compacted and stored in adjacent
0186: * index, value pairs which are searched for rather than accessed
0187: * directly (see get_reduce()). When a reduce occurs, the handle
0188: * (corresponding to the RHS of the matched production) is popped off
0189: * the stack. The new top of stack indicates a state. This table is
0190: * then indexed by that state and the LHS of the reducing production to
0191: * indicate where to "shift" to.
0192: *
0193: * @see java_cup.runtime.lr_parser#get_reduce
0194: */
0195: public abstract short[][] reduce_table();
0196:
0197: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0198:
0199: /** The index of the start state (supplied by generated subclass). */
0200: public abstract int start_state();
0201:
0202: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0203:
0204: /** The index of the start production (supplied by generated subclass). */
0205: public abstract int start_production();
0206:
0207: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0208:
0209: /** The index of the end of file terminal Symbol (supplied by generated
0210: * subclass).
0211: */
0212: public abstract int EOF_sym();
0213:
0214: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0215:
0216: /** The index of the special error Symbol (supplied by generated subclass). */
0217: public abstract int error_sym();
0218:
0219: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0220:
0221: /** Internal flag to indicate when parser should quit. */
0222: protected boolean _done_parsing = false;
0223:
0224: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0225:
0226: /** This method is called to indicate that the parser should quit. This is
0227: * normally called by an accept action, but can be used to cancel parsing
0228: * early in other circumstances if desired.
0229: */
0230: public void done_parsing() {
0231: _done_parsing = true;
0232: }
0233:
0234: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0235: /* Global parse state shared by parse(), error recovery, and
0236: * debugging routines */
0237: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0238:
0239: /** Indication of the index for top of stack (for use by actions). */
0240: protected int tos;
0241:
0242: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0243:
0244: /** The current lookahead Symbol. */
0245: protected Symbol cur_token;
0246:
0247: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0248:
0249: /** The parse stack itself. */
0250: protected Stack stack = new Stack();
0251:
0252: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0253:
0254: /** Direct reference to the production table. */
0255: protected short[][] production_tab;
0256:
0257: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0258:
0259: /** Direct reference to the action table. */
0260: protected short[][] action_tab;
0261:
0262: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0263:
0264: /** Direct reference to the reduce-goto table. */
0265: protected short[][] reduce_tab;
0266:
0267: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0268:
0269: /** This is the scanner object used by the default implementation
0270: * of scan() to get Symbols. To avoid name conflicts with existing
0271: * code, this field is private. [CSA/davidm] */
0272: private Scanner _scanner;
0273:
0274: /**
0275: * Simple accessor method to set the default scanner.
0276: */
0277: public void setScanner(Scanner s) {
0278: _scanner = s;
0279: }
0280:
0281: /**
0282: * Simple accessor method to get the default scanner.
0283: */
0284: public Scanner getScanner() {
0285: return _scanner;
0286: }
0287:
0288: /*-----------------------------------------------------------*/
0289: /*--- General Methods ---------------------------------------*/
0290: /*-----------------------------------------------------------*/
0291:
0292: /** Perform a bit of user supplied action code (supplied by generated
0293: * subclass). Actions are indexed by an internal action number assigned
0294: * at parser generation time.
0295: *
0296: * @param act_num the internal index of the action to be performed.
0297: * @param parser the parser object we are acting for.
0298: * @param stack the parse stack of that object.
0299: * @param top the index of the top element of the parse stack.
0300: */
0301: public abstract Symbol do_action(int act_num, lr_parser parser,
0302: Stack stack, int top) throws java.lang.Exception;
0303:
0304: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0305:
0306: /** User code for initialization inside the parser. Typically this
0307: * initializes the scanner. This is called before the parser requests
0308: * the first Symbol. Here this is just a placeholder for subclasses that
0309: * might need this and we perform no action. This method is normally
0310: * overridden by the generated code using this contents of the "init with"
0311: * clause as its body.
0312: */
0313: public void user_init() throws java.lang.Exception {
0314: }
0315:
0316: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0317:
0318: /** Initialize the action object. This is called before the parser does
0319: * any parse actions. This is filled in by generated code to create
0320: * an object that encapsulates all action code.
0321: */
0322: protected abstract void init_actions() throws java.lang.Exception;
0323:
0324: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0325:
0326: /** Get the next Symbol from the input (supplied by generated subclass).
0327: * Once end of file has been reached, all subsequent calls to scan
0328: * should return an EOF Symbol (which is Symbol number 0). By default
0329: * this method returns getScanner().next_token(); this implementation
0330: * can be overriden by the generated parser using the code declared in
0331: * the "scan with" clause. Do not recycle objects; every call to
0332: * scan() should return a fresh object.
0333: */
0334: public Symbol scan() throws java.lang.Exception {
0335: Symbol sym = getScanner().next_token();
0336: return (sym != null) ? sym : new Symbol(EOF_sym());
0337: }
0338:
0339: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0340:
0341: /** Report a fatal error. This method takes a message string and an
0342: * additional object (to be used by specializations implemented in
0343: * subclasses). Here in the base class a very simple implementation
0344: * is provided which reports the error then throws an exception.
0345: *
0346: * @param message an error message.
0347: * @param info an extra object reserved for use by specialized subclasses.
0348: */
0349: public void report_fatal_error(String message, Object info)
0350: throws java.lang.Exception {
0351: /* stop parsing (not really necessary since we throw an exception, but) */
0352: done_parsing();
0353:
0354: /* use the normal error message reporting to put out the message */
0355: report_error(message, info);
0356:
0357: /* throw an exception */
0358: throw new Exception("Can't recover from previous error(s)");
0359: }
0360:
0361: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0362:
0363: /** Report a non fatal error (or warning). This method takes a message
0364: * string and an additional object (to be used by specializations
0365: * implemented in subclasses). Here in the base class a very simple
0366: * implementation is provided which simply prints the message to
0367: * System.err.
0368: *
0369: * @param message an error message.
0370: * @param info an extra object reserved for use by specialized subclasses.
0371: */
0372: public void report_error(String message, Object info) {
0373: System.err.print(message);
0374: if (info instanceof Symbol)
0375: if (((Symbol) info).left != -1)
0376: System.err.println(" at character "
0377: + ((Symbol) info).left + " of input");
0378: else
0379: System.err.println("");
0380: else
0381: System.err.println("");
0382: }
0383:
0384: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0385:
0386: /** This method is called when a syntax error has been detected and recovery
0387: * is about to be invoked. Here in the base class we just emit a
0388: * "Syntax error" error message.
0389: *
0390: * @param cur_token the current lookahead Symbol.
0391: */
0392: public void syntax_error(Symbol cur_token) {
0393: report_error("Syntax error", cur_token);
0394: }
0395:
0396: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0397:
0398: /** This method is called if it is determined that syntax error recovery
0399: * has been unsuccessful. Here in the base class we report a fatal error.
0400: *
0401: * @param cur_token the current lookahead Symbol.
0402: */
0403: public void unrecovered_syntax_error(Symbol cur_token)
0404: throws java.lang.Exception {
0405: report_fatal_error("Couldn't repair and continue parse",
0406: cur_token);
0407: }
0408:
0409: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0410:
0411: /** Fetch an action from the action table. The table is broken up into
0412: * rows, one per state (rows are indexed directly by state number).
0413: * Within each row, a list of index, value pairs are given (as sequential
0414: * entries in the table), and the list is terminated by a default entry
0415: * (denoted with a Symbol index of -1). To find the proper entry in a row
0416: * we do a linear or binary search (depending on the size of the row).
0417: *
0418: * @param state the state index of the action being accessed.
0419: * @param sym the Symbol index of the action being accessed.
0420: */
0421: protected final short get_action(int state, int sym) {
0422: short tag;
0423: int first, last, probe;
0424: short[] row = action_tab[state];
0425:
0426: /* linear search if we are < 10 entries */
0427: if (row.length < 20)
0428: for (probe = 0; probe < row.length; probe++) {
0429: /* is this entry labeled with our Symbol or the default? */
0430: tag = row[probe++];
0431: if (tag == sym || tag == -1) {
0432: /* return the next entry */
0433: return row[probe];
0434: }
0435: }
0436: /* otherwise binary search */
0437: else {
0438: first = 0;
0439: last = (row.length - 1) / 2 - 1; /* leave out trailing default entry */
0440: while (first <= last) {
0441: probe = (first + last) / 2;
0442: if (sym == row[probe * 2])
0443: return row[probe * 2 + 1];
0444: else if (sym > row[probe * 2])
0445: first = probe + 1;
0446: else
0447: last = probe - 1;
0448: }
0449:
0450: /* not found, use the default at the end */
0451: return row[row.length - 1];
0452: }
0453:
0454: /* shouldn't happened, but if we run off the end we return the
0455: default (error == 0) */
0456: return 0;
0457: }
0458:
0459: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0460:
0461: /** Fetch a state from the reduce-goto table. The table is broken up into
0462: * rows, one per state (rows are indexed directly by state number).
0463: * Within each row, a list of index, value pairs are given (as sequential
0464: * entries in the table), and the list is terminated by a default entry
0465: * (denoted with a Symbol index of -1). To find the proper entry in a row
0466: * we do a linear search.
0467: *
0468: * @param state the state index of the entry being accessed.
0469: * @param sym the Symbol index of the entry being accessed.
0470: */
0471: protected final short get_reduce(int state, int sym) {
0472: short tag;
0473: short[] row = reduce_tab[state];
0474:
0475: /* if we have a null row we go with the default */
0476: if (row == null)
0477: return -1;
0478:
0479: for (int probe = 0; probe < row.length; probe++) {
0480: /* is this entry labeled with our Symbol or the default? */
0481: tag = row[probe++];
0482: if (tag == sym || tag == -1) {
0483: /* return the next entry */
0484: return row[probe];
0485: }
0486: }
0487: /* if we run off the end we return the default (error == -1) */
0488: return -1;
0489: }
0490:
0491: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0492:
0493: /** This method provides the main parsing routine. It returns only when
0494: * done_parsing() has been called (typically because the parser has
0495: * accepted, or a fatal error has been reported). See the header
0496: * documentation for the class regarding how shift/reduce parsers operate
0497: * and how the various tables are used.
0498: */
0499: public Symbol parse() throws java.lang.Exception {
0500: /* the current action code */
0501: int act;
0502:
0503: /* the Symbol/stack element returned by a reduce */
0504: Symbol lhs_sym = null;
0505:
0506: /* information about production being reduced with */
0507: short handle_size, lhs_sym_num;
0508:
0509: /* set up direct reference to tables to drive the parser */
0510:
0511: production_tab = production_table();
0512: action_tab = action_table();
0513: reduce_tab = reduce_table();
0514:
0515: /* initialize the action encapsulation object */
0516: init_actions();
0517:
0518: /* do user initialization */
0519: user_init();
0520:
0521: /* get the first token */
0522: cur_token = scan();
0523:
0524: /* push dummy Symbol with start state to get us underway */
0525: stack.removeAllElements();
0526: stack.push(new Symbol(0, start_state()));
0527: tos = 0;
0528:
0529: /* continue until we are told to stop */
0530: for (_done_parsing = false; !_done_parsing;) {
0531: /* Check current token for freshness. */
0532: if (cur_token.used_by_parser)
0533: throw new Error(
0534: "Symbol recycling detected (fix your scanner).");
0535:
0536: /* current state is always on the top of the stack */
0537:
0538: /* look up action out of the current state with the current input */
0539: act = get_action(((Symbol) stack.peek()).parse_state,
0540: cur_token.sym);
0541:
0542: /* decode the action -- > 0 encodes shift */
0543: if (act > 0) {
0544: /* shift to the encoded state by pushing it on the stack */
0545: cur_token.parse_state = act - 1;
0546: cur_token.used_by_parser = true;
0547: stack.push(cur_token);
0548: tos++;
0549:
0550: /* advance to the next Symbol */
0551: cur_token = scan();
0552: }
0553: /* if its less than zero, then it encodes a reduce action */
0554: else if (act < 0) {
0555: /* perform the action for the reduce */
0556: lhs_sym = do_action((-act) - 1, this , stack, tos);
0557:
0558: /* look up information about the production */
0559: lhs_sym_num = production_tab[(-act) - 1][0];
0560: handle_size = production_tab[(-act) - 1][1];
0561:
0562: /* pop the handle off the stack */
0563: for (int i = 0; i < handle_size; i++) {
0564: stack.pop();
0565: tos--;
0566: }
0567:
0568: /* look up the state to go to from the one popped back to */
0569: act = get_reduce(((Symbol) stack.peek()).parse_state,
0570: lhs_sym_num);
0571:
0572: /* shift to that state */
0573: lhs_sym.parse_state = act;
0574: lhs_sym.used_by_parser = true;
0575: stack.push(lhs_sym);
0576: tos++;
0577: }
0578: /* finally if the entry is zero, we have an error */
0579: else if (act == 0) {
0580: /* call user syntax error reporting routine */
0581: syntax_error(cur_token);
0582:
0583: /* try to error recover */
0584: if (!error_recovery(false)) {
0585: /* if that fails give up with a fatal syntax error */
0586: unrecovered_syntax_error(cur_token);
0587:
0588: /* just in case that wasn't fatal enough, end parse */
0589: done_parsing();
0590: } else {
0591: lhs_sym = (Symbol) stack.peek();
0592: }
0593: }
0594: }
0595: return lhs_sym;
0596: }
0597:
0598: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0599:
0600: /** Write a debugging message to System.err for the debugging version
0601: * of the parser.
0602: *
0603: * @param mess the text of the debugging message.
0604: */
0605: public void debug_message(String mess) {
0606: System.err.println(mess);
0607: }
0608:
0609: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0610:
0611: /** Dump the parse stack for debugging purposes. */
0612: public void dump_stack() {
0613: if (stack == null) {
0614: debug_message("# Stack dump requested, but stack is null");
0615: return;
0616: }
0617:
0618: debug_message("============ Parse Stack Dump ============");
0619:
0620: /* dump the stack */
0621: for (int i = 0; i < stack.size(); i++) {
0622: debug_message("Symbol: "
0623: + ((Symbol) stack.elementAt(i)).sym + " State: "
0624: + ((Symbol) stack.elementAt(i)).parse_state);
0625: }
0626: debug_message("==========================================");
0627: }
0628:
0629: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0630:
0631: /** Do debug output for a reduce.
0632: *
0633: * @param prod_num the production we are reducing with.
0634: * @param nt_num the index of the LHS non terminal.
0635: * @param rhs_size the size of the RHS.
0636: */
0637: public void debug_reduce(int prod_num, int nt_num, int rhs_size) {
0638: debug_message("# Reduce with prod #" + prod_num + " [NT="
0639: + nt_num + ", " + "SZ=" + rhs_size + "]");
0640: }
0641:
0642: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0643:
0644: /** Do debug output for shift.
0645: *
0646: * @param shift_tkn the Symbol being shifted onto the stack.
0647: */
0648: public void debug_shift(Symbol shift_tkn) {
0649: debug_message("# Shift under term #" + shift_tkn.sym
0650: + " to state #" + shift_tkn.parse_state);
0651: }
0652:
0653: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0654:
0655: /** Do debug output for stack state. [CSA]
0656: */
0657: public void debug_stack() {
0658: StringBuffer sb = new StringBuffer("## STACK:");
0659: for (int i = 0; i < stack.size(); i++) {
0660: Symbol s = (Symbol) stack.elementAt(i);
0661: sb.append(" <state " + s.parse_state + ", sym " + s.sym
0662: + ">");
0663: if ((i % 3) == 2 || (i == (stack.size() - 1))) {
0664: debug_message(sb.toString());
0665: sb = new StringBuffer(" ");
0666: }
0667: }
0668: }
0669:
0670: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0671:
0672: /** Perform a parse with debugging output. This does exactly the
0673: * same things as parse(), except that it calls debug_shift() and
0674: * debug_reduce() when shift and reduce moves are taken by the parser
0675: * and produces various other debugging messages.
0676: */
0677: public Symbol debug_parse() throws java.lang.Exception {
0678: /* the current action code */
0679: int act;
0680:
0681: /* the Symbol/stack element returned by a reduce */
0682: Symbol lhs_sym = null;
0683:
0684: /* information about production being reduced with */
0685: short handle_size, lhs_sym_num;
0686:
0687: /* set up direct reference to tables to drive the parser */
0688: production_tab = production_table();
0689: action_tab = action_table();
0690: reduce_tab = reduce_table();
0691:
0692: debug_message("# Initializing parser");
0693:
0694: /* initialize the action encapsulation object */
0695: init_actions();
0696:
0697: /* do user initialization */
0698: user_init();
0699:
0700: /* the current Symbol */
0701: cur_token = scan();
0702:
0703: debug_message("# Current Symbol is #" + cur_token.sym);
0704:
0705: /* push dummy Symbol with start state to get us underway */
0706: stack.removeAllElements();
0707: stack.push(new Symbol(0, start_state()));
0708: tos = 0;
0709:
0710: /* continue until we are told to stop */
0711: for (_done_parsing = false; !_done_parsing;) {
0712: /* Check current token for freshness. */
0713: if (cur_token.used_by_parser)
0714: throw new Error(
0715: "Symbol recycling detected (fix your scanner).");
0716:
0717: /* current state is always on the top of the stack */
0718: //debug_stack();
0719: /* look up action out of the current state with the current input */
0720: act = get_action(((Symbol) stack.peek()).parse_state,
0721: cur_token.sym);
0722:
0723: /* decode the action -- > 0 encodes shift */
0724: if (act > 0) {
0725: /* shift to the encoded state by pushing it on the stack */
0726: cur_token.parse_state = act - 1;
0727: cur_token.used_by_parser = true;
0728: debug_shift(cur_token);
0729: stack.push(cur_token);
0730: tos++;
0731:
0732: /* advance to the next Symbol */
0733: cur_token = scan();
0734: debug_message("# Current token is " + cur_token);
0735: }
0736: /* if its less than zero, then it encodes a reduce action */
0737: else if (act < 0) {
0738: /* perform the action for the reduce */
0739: lhs_sym = do_action((-act) - 1, this , stack, tos);
0740:
0741: /* look up information about the production */
0742: lhs_sym_num = production_tab[(-act) - 1][0];
0743: handle_size = production_tab[(-act) - 1][1];
0744:
0745: debug_reduce((-act) - 1, lhs_sym_num, handle_size);
0746:
0747: /* pop the handle off the stack */
0748: for (int i = 0; i < handle_size; i++) {
0749: stack.pop();
0750: tos--;
0751: }
0752:
0753: /* look up the state to go to from the one popped back to */
0754: act = get_reduce(((Symbol) stack.peek()).parse_state,
0755: lhs_sym_num);
0756: debug_message("# Reduce rule: top state "
0757: + ((Symbol) stack.peek()).parse_state
0758: + ", lhs sym " + lhs_sym_num + " -> state "
0759: + act);
0760:
0761: /* shift to that state */
0762: lhs_sym.parse_state = act;
0763: lhs_sym.used_by_parser = true;
0764: stack.push(lhs_sym);
0765: tos++;
0766:
0767: debug_message("# Goto state #" + act);
0768: }
0769: /* finally if the entry is zero, we have an error */
0770: else if (act == 0) {
0771: /* call user syntax error reporting routine */
0772: syntax_error(cur_token);
0773:
0774: /* try to error recover */
0775: if (!error_recovery(true)) {
0776: /* if that fails give up with a fatal syntax error */
0777: unrecovered_syntax_error(cur_token);
0778:
0779: /* just in case that wasn't fatal enough, end parse */
0780: done_parsing();
0781: } else {
0782: lhs_sym = (Symbol) stack.peek();
0783: }
0784: }
0785: }
0786: return lhs_sym;
0787: }
0788:
0789: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0790: /* Error recovery code */
0791: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0792:
0793: /** Attempt to recover from a syntax error. This returns false if recovery
0794: * fails, true if it succeeds. Recovery happens in 4 steps. First we
0795: * pop the parse stack down to a point at which we have a shift out
0796: * of the top-most state on the error Symbol. This represents the
0797: * initial error recovery configuration. If no such configuration is
0798: * found, then we fail. Next a small number of "lookahead" or "parse
0799: * ahead" Symbols are read into a buffer. The size of this buffer is
0800: * determined by error_sync_size() and determines how many Symbols beyond
0801: * the error must be matched to consider the recovery a success. Next,
0802: * we begin to discard Symbols in attempt to get past the point of error
0803: * to a point where we can continue parsing. After each Symbol, we attempt
0804: * to "parse ahead" though the buffered lookahead Symbols. The "parse ahead"
0805: * process simulates that actual parse, but does not modify the real
0806: * parser's configuration, nor execute any actions. If we can parse all
0807: * the stored Symbols without error, then the recovery is considered a
0808: * success. Once a successful recovery point is determined, we do an
0809: * actual parse over the stored input -- modifying the real parse
0810: * configuration and executing all actions. Finally, we return the the
0811: * normal parser to continue with the overall parse.
0812: *
0813: * @param debug should we produce debugging messages as we parse.
0814: */
0815: protected boolean error_recovery(boolean debug)
0816: throws java.lang.Exception {
0817: if (debug)
0818: debug_message("# Attempting error recovery");
0819:
0820: /* first pop the stack back into a state that can shift on error and
0821: do that shift (if that fails, we fail) */
0822: if (!find_recovery_config(debug)) {
0823: if (debug)
0824: debug_message("# Error recovery fails");
0825: return false;
0826: }
0827:
0828: /* read ahead to create lookahead we can parse multiple times */
0829: read_lookahead();
0830:
0831: /* repeatedly try to parse forward until we make it the required dist */
0832: for (;;) {
0833: /* try to parse forward, if it makes it, bail out of loop */
0834: if (debug)
0835: debug_message("# Trying to parse ahead");
0836: if (try_parse_ahead(debug)) {
0837: break;
0838: }
0839:
0840: /* if we are now at EOF, we have failed */
0841: if (lookahead[0].sym == EOF_sym()) {
0842: if (debug)
0843: debug_message("# Error recovery fails at EOF");
0844: return false;
0845: }
0846:
0847: /* otherwise, we consume another Symbol and try again */
0848: // BUG FIX by Bruce Hutton
0849: // Computer Science Department, University of Auckland,
0850: // Auckland, New Zealand.
0851: // It is the first token that is being consumed, not the one
0852: // we were up to parsing
0853: if (debug)
0854: debug_message("# Consuming Symbol #" + lookahead[0].sym);
0855: restart_lookahead();
0856: }
0857:
0858: /* we have consumed to a point where we can parse forward */
0859: if (debug)
0860: debug_message("# Parse-ahead ok, going back to normal parse");
0861:
0862: /* do the real parse (including actions) across the lookahead */
0863: parse_lookahead(debug);
0864:
0865: /* we have success */
0866: return true;
0867: }
0868:
0869: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0870:
0871: /** Determine if we can shift under the special error Symbol out of the
0872: * state currently on the top of the (real) parse stack.
0873: */
0874: protected boolean shift_under_error() {
0875: /* is there a shift under error Symbol */
0876: return get_action(((Symbol) stack.peek()).parse_state,
0877: error_sym()) > 0;
0878: }
0879:
0880: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0881:
0882: /** Put the (real) parse stack into error recovery configuration by
0883: * popping the stack down to a state that can shift on the special
0884: * error Symbol, then doing the shift. If no suitable state exists on
0885: * the stack we return false
0886: *
0887: * @param debug should we produce debugging messages as we parse.
0888: */
0889: protected boolean find_recovery_config(boolean debug) {
0890: Symbol error_token;
0891: int act;
0892:
0893: if (debug)
0894: debug_message("# Finding recovery state on stack");
0895:
0896: /* Remember the right-position of the top symbol on the stack */
0897: int right_pos = ((Symbol) stack.peek()).right;
0898: int left_pos = ((Symbol) stack.peek()).left;
0899:
0900: /* pop down until we can shift under error Symbol */
0901: while (!shift_under_error()) {
0902: /* pop the stack */
0903: if (debug)
0904: debug_message("# Pop stack by one, state was # "
0905: + ((Symbol) stack.peek()).parse_state);
0906: left_pos = ((Symbol) stack.pop()).left;
0907: tos--;
0908:
0909: /* if we have hit bottom, we fail */
0910: if (stack.empty()) {
0911: if (debug)
0912: debug_message("# No recovery state found on stack");
0913: return false;
0914: }
0915: }
0916:
0917: /* state on top of the stack can shift under error, find the shift */
0918: act = get_action(((Symbol) stack.peek()).parse_state,
0919: error_sym());
0920: if (debug) {
0921: debug_message("# Recover state found (#"
0922: + ((Symbol) stack.peek()).parse_state + ")");
0923: debug_message("# Shifting on error to state #" + (act - 1));
0924: }
0925:
0926: /* build and shift a special error Symbol */
0927: error_token = new Symbol(error_sym(), left_pos, right_pos);
0928: error_token.parse_state = act - 1;
0929: error_token.used_by_parser = true;
0930: stack.push(error_token);
0931: tos++;
0932:
0933: return true;
0934: }
0935:
0936: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0937:
0938: /** Lookahead Symbols used for attempting error recovery "parse aheads". */
0939: protected Symbol lookahead[];
0940:
0941: /** Position in lookahead input buffer used for "parse ahead". */
0942: protected int lookahead_pos;
0943:
0944: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0945:
0946: /** Read from input to establish our buffer of "parse ahead" lookahead
0947: * Symbols.
0948: */
0949: protected void read_lookahead() throws java.lang.Exception {
0950: /* create the lookahead array */
0951: lookahead = new Symbol[error_sync_size()];
0952:
0953: /* fill in the array */
0954: for (int i = 0; i < error_sync_size(); i++) {
0955: lookahead[i] = cur_token;
0956: cur_token = scan();
0957: }
0958:
0959: /* start at the beginning */
0960: lookahead_pos = 0;
0961: }
0962:
0963: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0964:
0965: /** Return the current lookahead in our error "parse ahead" buffer. */
0966: protected Symbol cur_err_token() {
0967: return lookahead[lookahead_pos];
0968: }
0969:
0970: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0971:
0972: /** Advance to next "parse ahead" input Symbol. Return true if we have
0973: * input to advance to, false otherwise.
0974: */
0975: protected boolean advance_lookahead() {
0976: /* advance the input location */
0977: lookahead_pos++;
0978:
0979: /* return true if we didn't go off the end */
0980: return lookahead_pos < error_sync_size();
0981: }
0982:
0983: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
0984:
0985: /** Reset the parse ahead input to one Symbol past where we started error
0986: * recovery (this consumes one new Symbol from the real input).
0987: */
0988: protected void restart_lookahead() throws java.lang.Exception {
0989: /* move all the existing input over */
0990: for (int i = 1; i < error_sync_size(); i++)
0991: lookahead[i - 1] = lookahead[i];
0992:
0993: /* read a new Symbol into the last spot */
0994: // BUG Fix by Bruce Hutton
0995: // Computer Science Department, University of Auckland,
0996: // Auckland, New Zealand. [applied 5-sep-1999 by csa]
0997: // The following two lines were out of order!!
0998: lookahead[error_sync_size() - 1] = cur_token;
0999: cur_token = scan();
1000:
1001: /* reset our internal position marker */
1002: lookahead_pos = 0;
1003: }
1004:
1005: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1006:
1007: /** Do a simulated parse forward (a "parse ahead") from the current
1008: * stack configuration using stored lookahead input and a virtual parse
1009: * stack. Return true if we make it all the way through the stored
1010: * lookahead input without error. This basically simulates the action of
1011: * parse() using only our saved "parse ahead" input, and not executing any
1012: * actions.
1013: *
1014: * @param debug should we produce debugging messages as we parse.
1015: */
1016: protected boolean try_parse_ahead(boolean debug)
1017: throws java.lang.Exception {
1018: int act;
1019: short lhs, rhs_size;
1020:
1021: /* create a virtual stack from the real parse stack */
1022: virtual_parse_stack vstack = new virtual_parse_stack(stack);
1023:
1024: /* parse until we fail or get past the lookahead input */
1025: for (;;) {
1026: /* look up the action from the current state (on top of stack) */
1027: act = get_action(vstack.top(), cur_err_token().sym);
1028:
1029: /* if its an error, we fail */
1030: if (act == 0)
1031: return false;
1032:
1033: /* > 0 encodes a shift */
1034: if (act > 0) {
1035: /* push the new state on the stack */
1036: vstack.push(act - 1);
1037:
1038: if (debug)
1039: debug_message("# Parse-ahead shifts Symbol #"
1040: + cur_err_token().sym + " into state #"
1041: + (act - 1));
1042:
1043: /* advance simulated input, if we run off the end, we are done */
1044: if (!advance_lookahead())
1045: return true;
1046: }
1047: /* < 0 encodes a reduce */
1048: else {
1049: /* if this is a reduce with the start production we are done */
1050: if ((-act) - 1 == start_production()) {
1051: if (debug)
1052: debug_message("# Parse-ahead accepts");
1053: return true;
1054: }
1055:
1056: /* get the lhs Symbol and the rhs size */
1057: lhs = production_tab[(-act) - 1][0];
1058: rhs_size = production_tab[(-act) - 1][1];
1059:
1060: /* pop handle off the stack */
1061: for (int i = 0; i < rhs_size; i++)
1062: vstack.pop();
1063:
1064: if (debug)
1065: debug_message("# Parse-ahead reduces: handle size = "
1066: + rhs_size
1067: + " lhs = #"
1068: + lhs
1069: + " from state #" + vstack.top());
1070:
1071: /* look up goto and push it onto the stack */
1072: vstack.push(get_reduce(vstack.top(), lhs));
1073: if (debug)
1074: debug_message("# Goto state #" + vstack.top());
1075: }
1076: }
1077: }
1078:
1079: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
1080:
1081: /** Parse forward using stored lookahead Symbols. In this case we have
1082: * already verified that parsing will make it through the stored lookahead
1083: * Symbols and we are now getting back to the point at which we can hand
1084: * control back to the normal parser. Consequently, this version of the
1085: * parser performs all actions and modifies the real parse configuration.
1086: * This returns once we have consumed all the stored input or we accept.
1087: *
1088: * @param debug should we produce debugging messages as we parse.
1089: */
1090: protected void parse_lookahead(boolean debug)
1091: throws java.lang.Exception {
1092: /* the current action code */
1093: int act;
1094:
1095: /* the Symbol/stack element returned by a reduce */
1096: Symbol lhs_sym = null;
1097:
1098: /* information about production being reduced with */
1099: short handle_size, lhs_sym_num;
1100:
1101: /* restart the saved input at the beginning */
1102: lookahead_pos = 0;
1103:
1104: if (debug) {
1105: debug_message("# Reparsing saved input with actions");
1106: debug_message("# Current Symbol is #" + cur_err_token().sym);
1107: debug_message("# Current state is #"
1108: + ((Symbol) stack.peek()).parse_state);
1109: }
1110:
1111: /* continue until we accept or have read all lookahead input */
1112: while (!_done_parsing) {
1113: /* current state is always on the top of the stack */
1114:
1115: /* look up action out of the current state with the current input */
1116: act = get_action(((Symbol) stack.peek()).parse_state,
1117: cur_err_token().sym);
1118:
1119: /* decode the action -- > 0 encodes shift */
1120: if (act > 0) {
1121: /* shift to the encoded state by pushing it on the stack */
1122: cur_err_token().parse_state = act - 1;
1123: cur_err_token().used_by_parser = true;
1124: if (debug)
1125: debug_shift(cur_err_token());
1126: stack.push(cur_err_token());
1127: tos++;
1128:
1129: /* advance to the next Symbol, if there is none, we are done */
1130: if (!advance_lookahead()) {
1131: if (debug)
1132: debug_message("# Completed reparse");
1133:
1134: /* scan next Symbol so we can continue parse */
1135: // BUGFIX by Chris Harris <ckharris@ucsd.edu>:
1136: // correct a one-off error by commenting out
1137: // this next line.
1138: /*cur_token = scan();*/
1139:
1140: /* go back to normal parser */
1141: return;
1142: }
1143:
1144: if (debug)
1145: debug_message("# Current Symbol is #"
1146: + cur_err_token().sym);
1147: }
1148: /* if its less than zero, then it encodes a reduce action */
1149: else if (act < 0) {
1150: /* perform the action for the reduce */
1151: lhs_sym = do_action((-act) - 1, this , stack, tos);
1152:
1153: /* look up information about the production */
1154: lhs_sym_num = production_tab[(-act) - 1][0];
1155: handle_size = production_tab[(-act) - 1][1];
1156:
1157: if (debug)
1158: debug_reduce((-act) - 1, lhs_sym_num, handle_size);
1159:
1160: /* pop the handle off the stack */
1161: for (int i = 0; i < handle_size; i++) {
1162: stack.pop();
1163: tos--;
1164: }
1165:
1166: /* look up the state to go to from the one popped back to */
1167: act = get_reduce(((Symbol) stack.peek()).parse_state,
1168: lhs_sym_num);
1169:
1170: /* shift to that state */
1171: lhs_sym.parse_state = act;
1172: lhs_sym.used_by_parser = true;
1173: stack.push(lhs_sym);
1174: tos++;
1175:
1176: if (debug)
1177: debug_message("# Goto state #" + act);
1178:
1179: }
1180: /* finally if the entry is zero, we have an error
1181: (shouldn't happen here, but...)*/
1182: else if (act == 0) {
1183: report_fatal_error("Syntax error", lhs_sym);
1184: return;
1185: }
1186: }
1187:
1188: }
1189:
1190: /*-----------------------------------------------------------*/
1191:
1192: /** Utility function: unpacks parse tables from strings */
1193: protected static short[][] unpackFromStrings(String[] sa) {
1194: // Concatanate initialization strings.
1195: StringBuffer sb = new StringBuffer(sa[0]);
1196: for (int i = 1; i < sa.length; i++)
1197: sb.append(sa[i]);
1198: int n = 0; // location in initialization string
1199: int size1 = (((int) sb.charAt(n)) << 16)
1200: | ((int) sb.charAt(n + 1));
1201: n += 2;
1202: short[][] result = new short[size1][];
1203: for (int i = 0; i < size1; i++) {
1204: int size2 = (((int) sb.charAt(n)) << 16)
1205: | ((int) sb.charAt(n + 1));
1206: n += 2;
1207: result[i] = new short[size2];
1208: for (int j = 0; j < size2; j++)
1209: result[i][j] = (short) (sb.charAt(n++) - 2);
1210: }
1211: return result;
1212: }
1213: }
|