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