0001: /*******************************************************************************
0002: * Copyright (c) 2000, 2006 IBM Corporation and others.
0003: * All rights reserved. This program and the accompanying materials
0004: * are made available under the terms of the Eclipse Public License v1.0
0005: * which accompanies this distribution, and is available at
0006: * http://www.eclipse.org/legal/epl-v10.html
0007: *
0008: * Contributors:
0009: * IBM Corporation - initial API and implementation
0010: *******************************************************************************/package org.eclipse.jdt.internal.compiler.parser.diagnose;
0011:
0012: import org.eclipse.jdt.core.compiler.CharOperation;
0013: import org.eclipse.jdt.internal.compiler.impl.CompilerOptions;
0014: import org.eclipse.jdt.internal.compiler.parser.Parser;
0015: import org.eclipse.jdt.internal.compiler.parser.ParserBasicInformation;
0016: import org.eclipse.jdt.internal.compiler.parser.RecoveryScanner;
0017: import org.eclipse.jdt.internal.compiler.parser.ScannerHelper;
0018: import org.eclipse.jdt.internal.compiler.parser.TerminalTokens;
0019: import org.eclipse.jdt.internal.compiler.problem.ProblemReporter;
0020: import org.eclipse.jdt.internal.compiler.util.Util;
0021:
0022: public class DiagnoseParser implements ParserBasicInformation,
0023: TerminalTokens {
0024: private static final boolean DEBUG = false;
0025: private boolean DEBUG_PARSECHECK = false;
0026:
0027: private static final int STACK_INCREMENT = 256;
0028:
0029: // private static final int ERROR_CODE = 1;
0030: private static final int BEFORE_CODE = 2;
0031: private static final int INSERTION_CODE = 3;
0032: private static final int INVALID_CODE = 4;
0033: private static final int SUBSTITUTION_CODE = 5;
0034: private static final int DELETION_CODE = 6;
0035: private static final int MERGE_CODE = 7;
0036: private static final int MISPLACED_CODE = 8;
0037: private static final int SCOPE_CODE = 9;
0038: private static final int SECONDARY_CODE = 10;
0039: private static final int EOF_CODE = 11;
0040:
0041: private static final int BUFF_UBOUND = 31;
0042: private static final int BUFF_SIZE = 32;
0043: private static final int MAX_DISTANCE = 30;
0044: private static final int MIN_DISTANCE = 3;
0045:
0046: private CompilerOptions options;
0047:
0048: private LexStream lexStream;
0049: private int errorToken;
0050: private int errorTokenStart;
0051:
0052: private int currentToken = 0;
0053:
0054: private int stackLength;
0055: private int stateStackTop;
0056: private int[] stack;
0057:
0058: private int[] locationStack;
0059: private int[] locationStartStack;
0060:
0061: private int tempStackTop;
0062: private int[] tempStack;
0063:
0064: private int prevStackTop;
0065: private int[] prevStack;
0066: private int nextStackTop;
0067: private int[] nextStack;
0068:
0069: private int scopeStackTop;
0070: private int[] scopeIndex;
0071: private int[] scopePosition;
0072:
0073: int[] list = new int[NUM_SYMBOLS + 1];
0074: int[] buffer = new int[BUFF_SIZE];
0075:
0076: private static final int NIL = -1;
0077: int[] stateSeen;
0078:
0079: int statePoolTop;
0080: StateInfo[] statePool;
0081:
0082: private Parser parser;
0083:
0084: private RecoveryScanner recoveryScanner;
0085:
0086: private boolean reportProblem;
0087:
0088: private static class RepairCandidate {
0089: public int symbol;
0090: public int location;
0091:
0092: public RepairCandidate() {
0093: this .symbol = 0;
0094: this .location = 0;
0095: }
0096: }
0097:
0098: private static class PrimaryRepairInfo {
0099: public int distance;
0100: public int misspellIndex;
0101: public int code;
0102: public int bufferPosition;
0103: public int symbol;
0104:
0105: public PrimaryRepairInfo() {
0106: this .distance = 0;
0107: this .misspellIndex = 0;
0108: this .code = 0;
0109: this .bufferPosition = 0;
0110: this .symbol = 0;
0111: }
0112:
0113: public PrimaryRepairInfo copy() {
0114: PrimaryRepairInfo c = new PrimaryRepairInfo();
0115: c.distance = this .distance;
0116: c.misspellIndex = this .misspellIndex;
0117: c.code = this .code;
0118: c.bufferPosition = this .bufferPosition;
0119: c.symbol = this .symbol;
0120: return c;
0121:
0122: }
0123: }
0124:
0125: static class SecondaryRepairInfo {
0126: public int code;
0127: public int distance;
0128: public int bufferPosition;
0129: public int stackPosition;
0130: public int numDeletions;
0131: public int symbol;
0132:
0133: boolean recoveryOnNextStack;
0134: }
0135:
0136: private static class StateInfo {
0137: int state;
0138: int next;
0139:
0140: public StateInfo(int state, int next) {
0141: this .state = state;
0142: this .next = next;
0143: }
0144: }
0145:
0146: public DiagnoseParser(Parser parser, int firstToken, int start,
0147: int end, CompilerOptions options) {
0148: this (parser, firstToken, start, end, Util.EMPTY_INT_ARRAY,
0149: Util.EMPTY_INT_ARRAY, Util.EMPTY_INT_ARRAY, options);
0150: }
0151:
0152: public DiagnoseParser(Parser parser, int firstToken, int start,
0153: int end, int[] intervalStartToSkip,
0154: int[] intervalEndToSkip, int[] intervalFlagsToSkip,
0155: CompilerOptions options) {
0156: this .parser = parser;
0157: this .options = options;
0158: this .lexStream = new LexStream(BUFF_SIZE, parser.scanner,
0159: intervalStartToSkip, intervalEndToSkip,
0160: intervalFlagsToSkip, firstToken, start, end);
0161: this .recoveryScanner = parser.recoveryScanner;
0162: }
0163:
0164: private ProblemReporter problemReporter() {
0165: return parser.problemReporter();
0166: }
0167:
0168: private void reallocateStacks() {
0169: int old_stack_length = stackLength;
0170:
0171: stackLength += STACK_INCREMENT;
0172:
0173: if (old_stack_length == 0) {
0174: stack = new int[stackLength];
0175: locationStack = new int[stackLength];
0176: locationStartStack = new int[stackLength];
0177: tempStack = new int[stackLength];
0178: prevStack = new int[stackLength];
0179: nextStack = new int[stackLength];
0180: scopeIndex = new int[stackLength];
0181: scopePosition = new int[stackLength];
0182: } else {
0183: System.arraycopy(stack, 0, stack = new int[stackLength], 0,
0184: old_stack_length);
0185: System.arraycopy(locationStack, 0,
0186: locationStack = new int[stackLength], 0,
0187: old_stack_length);
0188: System.arraycopy(locationStartStack, 0,
0189: locationStartStack = new int[stackLength], 0,
0190: old_stack_length);
0191: System.arraycopy(tempStack, 0,
0192: tempStack = new int[stackLength], 0,
0193: old_stack_length);
0194: System.arraycopy(prevStack, 0,
0195: prevStack = new int[stackLength], 0,
0196: old_stack_length);
0197: System.arraycopy(nextStack, 0,
0198: nextStack = new int[stackLength], 0,
0199: old_stack_length);
0200: System.arraycopy(scopeIndex, 0,
0201: scopeIndex = new int[stackLength], 0,
0202: old_stack_length);
0203: System.arraycopy(scopePosition, 0,
0204: scopePosition = new int[stackLength], 0,
0205: old_stack_length);
0206: }
0207: return;
0208: }
0209:
0210: public void diagnoseParse(boolean record) {
0211: this .reportProblem = true;
0212: boolean oldRecord = false;
0213: if (this .recoveryScanner != null) {
0214: oldRecord = this .recoveryScanner.record;
0215: this .recoveryScanner.record = record;
0216: }
0217: try {
0218: lexStream.reset();
0219:
0220: currentToken = lexStream.getToken();
0221:
0222: int prev_pos;
0223: int pos;
0224: int next_pos;
0225: int act = START_STATE;
0226:
0227: reallocateStacks();
0228:
0229: //
0230: // Start parsing
0231: //
0232: stateStackTop = 0;
0233: stack[stateStackTop] = act;
0234:
0235: int tok = lexStream.kind(currentToken);
0236: locationStack[stateStackTop] = currentToken;
0237: locationStartStack[stateStackTop] = lexStream
0238: .start(currentToken);
0239:
0240: boolean forceRecoveryAfterLBracketMissing = false;
0241: // int forceRecoveryToken = -1;
0242:
0243: //
0244: // Process a terminal
0245: //
0246: do {
0247: //
0248: // Synchronize state stacks and update the location stack
0249: //
0250: prev_pos = -1;
0251: prevStackTop = -1;
0252:
0253: next_pos = -1;
0254: nextStackTop = -1;
0255:
0256: pos = stateStackTop;
0257: tempStackTop = stateStackTop - 1;
0258: for (int i = 0; i <= stateStackTop; i++)
0259: tempStack[i] = stack[i];
0260:
0261: act = Parser.tAction(act, tok);
0262: //
0263: // When a reduce action is encountered, we compute all REDUCE
0264: // and associated goto actions induced by the current token.
0265: // Eventually, a SHIFT, SHIFT-REDUCE, ACCEPT or ERROR action is
0266: // computed...
0267: //
0268: while (act <= NUM_RULES) {
0269: do {
0270: tempStackTop -= (Parser.rhs[act] - 1);
0271: act = Parser.ntAction(tempStack[tempStackTop],
0272: Parser.lhs[act]);
0273: } while (act <= NUM_RULES);
0274: //
0275: // ... Update the maximum useful position of the
0276: // (STATE_)STACK, push goto state into stack, and
0277: // compute next action on current symbol ...
0278: //
0279: if (tempStackTop + 1 >= stackLength)
0280: reallocateStacks();
0281: pos = pos < tempStackTop ? pos : tempStackTop;
0282: tempStack[tempStackTop + 1] = act;
0283: act = Parser.tAction(act, tok);
0284: }
0285:
0286: //
0287: // At this point, we have a shift, shift-reduce, accept or error
0288: // action. STACK contains the configuration of the state stack
0289: // prior to executing any action on curtok. next_stack contains
0290: // the configuration of the state stack after executing all
0291: // reduce actions induced by curtok. The variable pos indicates
0292: // the highest position in STACK that is still useful after the
0293: // reductions are executed.
0294: //
0295: while (act > ERROR_ACTION || act < ACCEPT_ACTION) { // SHIFT-REDUCE action or SHIFT action ?
0296: nextStackTop = tempStackTop + 1;
0297: for (int i = next_pos + 1; i <= nextStackTop; i++)
0298: nextStack[i] = tempStack[i];
0299:
0300: for (int i = pos + 1; i <= nextStackTop; i++) {
0301: locationStack[i] = locationStack[stateStackTop];
0302: locationStartStack[i] = locationStartStack[stateStackTop];
0303: }
0304:
0305: //
0306: // If we have a shift-reduce, process it as well as
0307: // the goto-reduce actions that follow it.
0308: //
0309: if (act > ERROR_ACTION) {
0310: act -= ERROR_ACTION;
0311: do {
0312: nextStackTop -= (Parser.rhs[act] - 1);
0313: act = Parser.ntAction(
0314: nextStack[nextStackTop],
0315: Parser.lhs[act]);
0316: } while (act <= NUM_RULES);
0317: pos = pos < nextStackTop ? pos : nextStackTop;
0318: }
0319:
0320: if (nextStackTop + 1 >= stackLength)
0321: reallocateStacks();
0322:
0323: tempStackTop = nextStackTop;
0324: nextStack[++nextStackTop] = act;
0325: next_pos = nextStackTop;
0326:
0327: //
0328: // Simulate the parser through the next token without
0329: // destroying STACK or next_stack.
0330: //
0331: currentToken = lexStream.getToken();
0332: tok = lexStream.kind(currentToken);
0333: act = Parser.tAction(act, tok);
0334: while (act <= NUM_RULES) {
0335: //
0336: // ... Process all goto-reduce actions following
0337: // reduction, until a goto action is computed ...
0338: //
0339: do {
0340: int lhs_symbol = Parser.lhs[act];
0341: if (DEBUG) {
0342: System.out
0343: .println(Parser.name[Parser.non_terminal_index[lhs_symbol]]);
0344: }
0345: tempStackTop -= (Parser.rhs[act] - 1);
0346: act = (tempStackTop > next_pos ? tempStack[tempStackTop]
0347: : nextStack[tempStackTop]);
0348: act = Parser.ntAction(act, lhs_symbol);
0349: } while (act <= NUM_RULES);
0350:
0351: //
0352: // ... Update the maximum useful position of the
0353: // (STATE_)STACK, push GOTO state into stack, and
0354: // compute next action on current symbol ...
0355: //
0356: if (tempStackTop + 1 >= stackLength)
0357: reallocateStacks();
0358:
0359: next_pos = next_pos < tempStackTop ? next_pos
0360: : tempStackTop;
0361: tempStack[tempStackTop + 1] = act;
0362: act = Parser.tAction(act, tok);
0363: }
0364:
0365: // if((tok != TokenNameRBRACE || (forceRecoveryToken != currentToken && (lexStream.flags(currentToken) & LexStream.LBRACE_MISSING) != 0))
0366: // && (lexStream.flags(currentToken) & LexStream.IS_AFTER_JUMP) !=0) {
0367: // act = ERROR_ACTION;
0368: // if(forceRecoveryToken != currentToken
0369: // && (lexStream.flags(currentToken) & LexStream.LBRACE_MISSING) != 0) {
0370: // forceRecoveryAfterLBracketMissing = true;
0371: // forceRecoveryToken = currentToken;
0372: // }
0373: // }
0374:
0375: //
0376: // No error was detected, Read next token into
0377: // PREVTOK element, advance CURTOK pointer and
0378: // update stacks.
0379: //
0380: if (act != ERROR_ACTION) {
0381: prevStackTop = stateStackTop;
0382: for (int i = prev_pos + 1; i <= prevStackTop; i++)
0383: prevStack[i] = stack[i];
0384: prev_pos = pos;
0385:
0386: stateStackTop = nextStackTop;
0387: for (int i = pos + 1; i <= stateStackTop; i++)
0388: stack[i] = nextStack[i];
0389: locationStack[stateStackTop] = currentToken;
0390: locationStartStack[stateStackTop] = lexStream
0391: .start(currentToken);
0392: pos = next_pos;
0393: }
0394: }
0395:
0396: //
0397: // At this stage, either we have an ACCEPT or an ERROR
0398: // action.
0399: //
0400: if (act == ERROR_ACTION) {
0401: //
0402: // An error was detected.
0403: //
0404: RepairCandidate candidate = errorRecovery(
0405: currentToken,
0406: forceRecoveryAfterLBracketMissing);
0407:
0408: forceRecoveryAfterLBracketMissing = false;
0409:
0410: if (parser.reportOnlyOneSyntaxError) {
0411: return;
0412: }
0413:
0414: if (this .parser.problemReporter().options.maxProblemsPerUnit < this .parser.compilationUnit.compilationResult.problemCount) {
0415: if (this .recoveryScanner == null
0416: || !this .recoveryScanner.record)
0417: return;
0418: this .reportProblem = false;
0419: }
0420:
0421: act = stack[stateStackTop];
0422:
0423: //
0424: // If the recovery was successful on a nonterminal candidate,
0425: // parse through that candidate and "read" the next token.
0426: //
0427: if (candidate.symbol == 0) {
0428: break;
0429: } else if (candidate.symbol > NT_OFFSET) {
0430: int lhs_symbol = candidate.symbol - NT_OFFSET;
0431: if (DEBUG) {
0432: System.out
0433: .println(Parser.name[Parser.non_terminal_index[lhs_symbol]]);
0434: }
0435: act = Parser.ntAction(act, lhs_symbol);
0436: while (act <= NUM_RULES) {
0437: stateStackTop -= (Parser.rhs[act] - 1);
0438: act = Parser.ntAction(stack[stateStackTop],
0439: Parser.lhs[act]);
0440: }
0441: stack[++stateStackTop] = act;
0442: currentToken = lexStream.getToken();
0443: tok = lexStream.kind(currentToken);
0444: locationStack[stateStackTop] = currentToken;
0445: locationStartStack[stateStackTop] = lexStream
0446: .start(currentToken);
0447: } else {
0448: tok = candidate.symbol;
0449: locationStack[stateStackTop] = candidate.location;
0450: locationStartStack[stateStackTop] = lexStream
0451: .start(candidate.location);
0452: }
0453: }
0454: } while (act != ACCEPT_ACTION);
0455: } finally {
0456: if (this .recoveryScanner != null) {
0457: this .recoveryScanner.record = oldRecord;
0458: }
0459: }
0460: return;
0461: }
0462:
0463: //
0464: // This routine is invoked when an error is encountered. It
0465: // tries to diagnose the error and recover from it. If it is
0466: // successful, the state stack, the current token and the buffer
0467: // are readjusted; i.e., after a successful recovery,
0468: // state_stack_top points to the location in the state stack
0469: // that contains the state on which to recover; curtok
0470: // identifies the symbol on which to recover.
0471: //
0472: // Up to three configurations may be available when this routine
0473: // is invoked. PREV_STACK may contain the sequence of states
0474: // preceding any action on prevtok, STACK always contains the
0475: // sequence of states preceding any action on curtok, and
0476: // NEXT_STACK may contain the sequence of states preceding any
0477: // action on the successor of curtok.
0478: //
0479: private RepairCandidate errorRecovery(int error_token,
0480: boolean forcedError) {
0481: this .errorToken = error_token;
0482: this .errorTokenStart = lexStream.start(error_token);
0483:
0484: int prevtok = lexStream.previous(error_token);
0485: int prevtokKind = lexStream.kind(prevtok);
0486:
0487: if (forcedError) {
0488: int name_index = Parser.terminal_index[TokenNameLBRACE];
0489:
0490: reportError(INSERTION_CODE, name_index, prevtok, prevtok);
0491:
0492: RepairCandidate candidate = new RepairCandidate();
0493: candidate.symbol = TokenNameLBRACE;
0494: candidate.location = error_token;
0495: lexStream.reset(error_token);
0496:
0497: stateStackTop = nextStackTop;
0498: for (int j = 0; j <= stateStackTop; j++) {
0499: stack[j] = nextStack[j];
0500: }
0501: locationStack[stateStackTop] = error_token;
0502: locationStartStack[stateStackTop] = lexStream
0503: .start(error_token);
0504:
0505: return candidate;
0506: }
0507:
0508: //
0509: // Try primary phase recoveries. If not successful, try secondary
0510: // phase recoveries. If not successful and we are at end of the
0511: // file, we issue the end-of-file error and quit. Otherwise, ...
0512: //
0513: RepairCandidate candidate = primaryPhase(error_token);
0514: if (candidate.symbol != 0) {
0515: return candidate;
0516: }
0517:
0518: candidate = secondaryPhase(error_token);
0519: if (candidate.symbol != 0) {
0520: return candidate;
0521: }
0522:
0523: if (lexStream.kind(error_token) == EOFT_SYMBOL) {
0524: reportError(EOF_CODE, Parser.terminal_index[EOFT_SYMBOL],
0525: prevtok, prevtok);
0526: candidate.symbol = 0;
0527: candidate.location = error_token;
0528: return candidate;
0529: }
0530:
0531: //
0532: // At this point, primary and (initial attempt at) secondary
0533: // recovery did not work. We will now get into "panic mode" and
0534: // keep trying secondary phase recoveries until we either find
0535: // a successful recovery or have consumed the remaining input
0536: // tokens.
0537: //
0538: while (lexStream.kind(buffer[BUFF_UBOUND]) != EOFT_SYMBOL) {
0539: candidate = secondaryPhase(buffer[MAX_DISTANCE
0540: - MIN_DISTANCE + 2]);
0541: if (candidate.symbol != 0) {
0542: return candidate;
0543: }
0544: }
0545:
0546: //
0547: // We reached the end of the file while panicking. Delete all
0548: // remaining tokens in the input.
0549: //
0550: int i;
0551: for (i = BUFF_UBOUND; lexStream.kind(buffer[i]) == EOFT_SYMBOL; i--) {/*empty*/
0552: }
0553:
0554: reportError(DELETION_CODE, Parser.terminal_index[prevtokKind],//Parser.terminal_index[lexStream.kind(prevtok)],
0555: error_token, buffer[i]);
0556:
0557: candidate.symbol = 0;
0558: candidate.location = buffer[i];
0559:
0560: return candidate;
0561: }
0562:
0563: //
0564: // This function tries primary and scope recovery on each
0565: // available configuration. If a successful recovery is found
0566: // and no secondary phase recovery can do better, a diagnosis is
0567: // issued, the configuration is updated and the function returns
0568: // "true". Otherwise, it returns "false".
0569: //
0570: private RepairCandidate primaryPhase(int error_token) {
0571: PrimaryRepairInfo repair = new PrimaryRepairInfo();
0572: RepairCandidate candidate = new RepairCandidate();
0573:
0574: //
0575: // Initialize the buffer.
0576: //
0577: int i = (nextStackTop >= 0 ? 3 : 2);
0578: buffer[i] = error_token;
0579:
0580: for (int j = i; j > 0; j--)
0581: buffer[j - 1] = lexStream.previous(buffer[j]);
0582:
0583: for (int k = i + 1; k < BUFF_SIZE; k++)
0584: buffer[k] = lexStream.next(buffer[k - 1]);
0585:
0586: //
0587: // If NEXT_STACK_TOP > 0 then the parse was successful on CURTOK
0588: // and the error was detected on the successor of CURTOK. In
0589: // that case, first check whether or not primary recovery is
0590: // possible on next_stack ...
0591: //
0592: if (nextStackTop >= 0) {
0593: repair.bufferPosition = 3;
0594: repair = checkPrimaryDistance(nextStack, nextStackTop,
0595: repair);
0596: }
0597:
0598: //
0599: // ... Next, try primary recovery on the current token...
0600: //
0601: PrimaryRepairInfo new_repair = repair.copy();
0602:
0603: new_repair.bufferPosition = 2;
0604: new_repair = checkPrimaryDistance(stack, stateStackTop,
0605: new_repair);
0606: if (new_repair.distance > repair.distance
0607: || new_repair.misspellIndex > repair.misspellIndex) {
0608: repair = new_repair;
0609: }
0610:
0611: //
0612: // Finally, if prev_stack_top >= 0 then try primary recovery on
0613: // the prev_stack configuration.
0614: //
0615:
0616: if (prevStackTop >= 0) {
0617: new_repair = repair.copy();
0618: new_repair.bufferPosition = 1;
0619: new_repair = checkPrimaryDistance(prevStack, prevStackTop,
0620: new_repair);
0621: if (new_repair.distance > repair.distance
0622: || new_repair.misspellIndex > repair.misspellIndex) {
0623: repair = new_repair;
0624: }
0625: }
0626:
0627: //
0628: // Before accepting the best primary phase recovery obtained,
0629: // ensure that we cannot do better with a similar secondary
0630: // phase recovery.
0631: //
0632: if (nextStackTop >= 0) {// next_stack available
0633: if (secondaryCheck(nextStack, nextStackTop, 3,
0634: repair.distance)) {
0635: return candidate;
0636: }
0637: } else if (secondaryCheck(stack, stateStackTop, 2,
0638: repair.distance)) {
0639: return candidate;
0640: }
0641:
0642: //
0643: // First, adjust distance if the recovery is on the error token;
0644: // it is important that the adjustment be made here and not at
0645: // each primary trial to prevent the distance tests from being
0646: // biased in favor of deferred recoveries which have access to
0647: // more input tokens...
0648: //
0649: repair.distance = repair.distance - repair.bufferPosition + 1;
0650:
0651: //
0652: // ...Next, adjust the distance if the recovery is a deletion or
0653: // (some form of) substitution...
0654: //
0655: if (repair.code == INVALID_CODE || repair.code == DELETION_CODE
0656: || repair.code == SUBSTITUTION_CODE
0657: || repair.code == MERGE_CODE) {
0658: repair.distance--;
0659: }
0660:
0661: //
0662: // ... After adjustment, check if the most successful primary
0663: // recovery can be applied. If not, continue with more radical
0664: // recoveries...
0665: //
0666: if (repair.distance < MIN_DISTANCE) {
0667: return candidate;
0668: }
0669:
0670: //
0671: // When processing an insertion error, if the token preceeding
0672: // the error token is not available, we change the repair code
0673: // into a BEFORE_CODE to instruct the reporting routine that it
0674: // indicates that the repair symbol should be inserted before
0675: // the error token.
0676: //
0677: if (repair.code == INSERTION_CODE) {
0678: if (buffer[repair.bufferPosition - 1] == 0) {
0679: repair.code = BEFORE_CODE;
0680: }
0681: }
0682:
0683: //
0684: // Select the proper sequence of states on which to recover,
0685: // update stack accordingly and call diagnostic routine.
0686: //
0687: if (repair.bufferPosition == 1) {
0688: stateStackTop = prevStackTop;
0689: for (int j = 0; j <= stateStackTop; j++) {
0690: stack[j] = prevStack[j];
0691: }
0692: } else if (nextStackTop >= 0 && repair.bufferPosition >= 3) {
0693: stateStackTop = nextStackTop;
0694: for (int j = 0; j <= stateStackTop; j++) {
0695: stack[j] = nextStack[j];
0696: }
0697: locationStack[stateStackTop] = buffer[3];
0698: locationStartStack[stateStackTop] = lexStream
0699: .start(buffer[3]);
0700: }
0701:
0702: return primaryDiagnosis(repair);
0703: }
0704:
0705: //
0706: // This function checks whether or not a given state has a
0707: // candidate, whose string representaion is a merging of the two
0708: // tokens at positions buffer_position and buffer_position+1 in
0709: // the buffer. If so, it returns the candidate in question;
0710: // otherwise it returns 0.
0711: //
0712: private int mergeCandidate(int state, int buffer_position) {
0713: char[] name1 = lexStream.name(buffer[buffer_position]);
0714: char[] name2 = lexStream.name(buffer[buffer_position + 1]);
0715:
0716: int len = name1.length + name2.length;
0717:
0718: char[] str = CharOperation.concat(name1, name2);
0719:
0720: for (int k = Parser.asi(state); Parser.asr[k] != 0; k++) {
0721: int l = Parser.terminal_index[Parser.asr[k]];
0722:
0723: if (len == Parser.name[l].length()) {
0724: char[] name = Parser.name[l].toCharArray();
0725:
0726: if (CharOperation.equals(str, name, false)) {
0727: return Parser.asr[k];
0728: }
0729: }
0730: }
0731:
0732: return 0;
0733: }
0734:
0735: //
0736: // This procedure takes as arguments a parsing configuration
0737: // consisting of a state stack (stack and stack_top) and a fixed
0738: // number of input tokens (starting at buffer_position) in the
0739: // input BUFFER; and some reference arguments: repair_code,
0740: // distance, misspell_index, candidate, and stack_position
0741: // which it sets based on the best possible recovery that it
0742: // finds in the given configuration. The effectiveness of a
0743: // a repair is judged based on two criteria:
0744: //
0745: // 1) the number of tokens that can be parsed after the repair
0746: // is applied: distance.
0747: // 2) how close to perfection is the candidate that is chosen:
0748: // misspell_index.
0749: // When this procedure is entered, distance, misspell_index and
0750: // repair_code are assumed to be initialized.
0751: //
0752: private PrimaryRepairInfo checkPrimaryDistance(int stck[],
0753: int stack_top, PrimaryRepairInfo repair) {
0754: int i, j, k, next_state, max_pos, act, root, symbol, tok;
0755:
0756: //
0757: // First, try scope and manual recovery.
0758: //
0759: PrimaryRepairInfo scope_repair = scopeTrial(stck, stack_top,
0760: repair.copy());
0761: if (scope_repair.distance > repair.distance)
0762: repair = scope_repair;
0763:
0764: //
0765: // Next, try merging the error token with its successor.
0766: //
0767: if (buffer[repair.bufferPosition] != 0
0768: && buffer[repair.bufferPosition + 1] != 0) {// do not merge the first token
0769: symbol = mergeCandidate(stck[stack_top],
0770: repair.bufferPosition);
0771: if (symbol != 0) {
0772: j = parseCheck(stck, stack_top, symbol,
0773: repair.bufferPosition + 2);
0774: if ((j > repair.distance)
0775: || (j == repair.distance && repair.misspellIndex < 10)) {
0776: repair.misspellIndex = 10;
0777: repair.symbol = symbol;
0778: repair.distance = j;
0779: repair.code = MERGE_CODE;
0780: }
0781: }
0782: }
0783:
0784: //
0785: // Next, try deletion of the error token.
0786: //
0787: j = parseCheck(stck, stack_top, lexStream
0788: .kind(buffer[repair.bufferPosition + 1]),
0789: repair.bufferPosition + 2);
0790: if (lexStream.kind(buffer[repair.bufferPosition]) == EOLT_SYMBOL
0791: && lexStream
0792: .afterEol(buffer[repair.bufferPosition + 1])) {
0793: k = 10;
0794: } else {
0795: k = 0;
0796: }
0797: if (j > repair.distance
0798: || (j == repair.distance && k > repair.misspellIndex)) {
0799: repair.misspellIndex = k;
0800: repair.code = DELETION_CODE;
0801: repair.distance = j;
0802: }
0803:
0804: //
0805: // Update the error configuration by simulating all reduce and
0806: // goto actions induced by the error token. Then assign the top
0807: // most state of the new configuration to next_state.
0808: //
0809: next_state = stck[stack_top];
0810: max_pos = stack_top;
0811: tempStackTop = stack_top - 1;
0812:
0813: tok = lexStream.kind(buffer[repair.bufferPosition]);
0814: lexStream.reset(buffer[repair.bufferPosition + 1]);
0815: act = Parser.tAction(next_state, tok);
0816: while (act <= NUM_RULES) {
0817: do {
0818: tempStackTop -= (Parser.rhs[act] - 1);
0819: symbol = Parser.lhs[act];
0820: act = (tempStackTop > max_pos ? tempStack[tempStackTop]
0821: : stck[tempStackTop]);
0822: act = Parser.ntAction(act, symbol);
0823: } while (act <= NUM_RULES);
0824: max_pos = max_pos < tempStackTop ? max_pos : tempStackTop;
0825: tempStack[tempStackTop + 1] = act;
0826: next_state = act;
0827: act = Parser.tAction(next_state, tok);
0828: }
0829:
0830: //
0831: // Next, place the list of candidates in proper order.
0832: //
0833: root = 0;
0834: for (i = Parser.asi(next_state); Parser.asr[i] != 0; i++) {
0835: symbol = Parser.asr[i];
0836: if (symbol != EOFT_SYMBOL && symbol != ERROR_SYMBOL) {
0837: if (root == 0) {
0838: list[symbol] = symbol;
0839: } else {
0840: list[symbol] = list[root];
0841: list[root] = symbol;
0842: }
0843: root = symbol;
0844: }
0845: }
0846:
0847: if (stck[stack_top] != next_state) {
0848: for (i = Parser.asi(stck[stack_top]); Parser.asr[i] != 0; i++) {
0849: symbol = Parser.asr[i];
0850: if (symbol != EOFT_SYMBOL && symbol != ERROR_SYMBOL
0851: && list[symbol] == 0) {
0852: if (root == 0) {
0853: list[symbol] = symbol;
0854: } else {
0855: list[symbol] = list[root];
0856: list[root] = symbol;
0857: }
0858: root = symbol;
0859: }
0860: }
0861: }
0862:
0863: i = list[root];
0864: list[root] = 0;
0865: root = i;
0866:
0867: //
0868: // Next, try insertion for each possible candidate available in
0869: // the current state, except EOFT and ERROR_SYMBOL.
0870: //
0871: symbol = root;
0872: while (symbol != 0) {
0873: if (symbol == EOLT_SYMBOL
0874: && lexStream
0875: .afterEol(buffer[repair.bufferPosition])) {
0876: k = 10;
0877: } else {
0878: k = 0;
0879: }
0880: j = parseCheck(stck, stack_top, symbol,
0881: repair.bufferPosition);
0882: if (j > repair.distance) {
0883: repair.misspellIndex = k;
0884: repair.distance = j;
0885: repair.symbol = symbol;
0886: repair.code = INSERTION_CODE;
0887: } else if (j == repair.distance && k > repair.misspellIndex) {
0888: repair.misspellIndex = k;
0889: repair.distance = j;
0890: repair.symbol = symbol;
0891: repair.code = INSERTION_CODE;
0892: } else if (j == repair.distance
0893: && k == repair.misspellIndex
0894: && isBetterSymbol(symbol, repair.symbol)) {
0895: repair.misspellIndex = k;
0896: repair.distance = j;
0897: repair.symbol = symbol;
0898: repair.code = INSERTION_CODE;
0899: }
0900:
0901: symbol = list[symbol];
0902: }
0903:
0904: //
0905: // Next, Try substitution for each possible candidate available
0906: // in the current state, except EOFT and ERROR_SYMBOL.
0907: //
0908: symbol = root;
0909:
0910: if (buffer[repair.bufferPosition] != 0) {// do not replace the first token
0911: while (symbol != 0) {
0912: if (symbol == EOLT_SYMBOL
0913: && lexStream
0914: .afterEol(buffer[repair.bufferPosition + 1])) {
0915: k = 10;
0916: } else {
0917: k = misspell(symbol, buffer[repair.bufferPosition]);
0918: }
0919: j = parseCheck(stck, stack_top, symbol,
0920: repair.bufferPosition + 1);
0921: if (j > repair.distance) {
0922: repair.misspellIndex = k;
0923: repair.distance = j;
0924: repair.symbol = symbol;
0925: repair.code = SUBSTITUTION_CODE;
0926: } else if (j == repair.distance
0927: && k > repair.misspellIndex) {
0928: repair.misspellIndex = k;
0929: repair.symbol = symbol;
0930: repair.code = SUBSTITUTION_CODE;
0931: } else if (j == repair.distance
0932: && k > repair.misspellIndex
0933: && isBetterSymbol(symbol, repair.symbol)) {
0934: repair.misspellIndex = k;
0935: repair.symbol = symbol;
0936: repair.code = SUBSTITUTION_CODE;
0937: }
0938: i = symbol;
0939: symbol = list[symbol];
0940: list[i] = 0; // reset element
0941: }
0942: }
0943:
0944: //
0945: // Next, we try to insert a nonterminal candidate in front of the
0946: // error token, or substituting a nonterminal candidate for the
0947: // error token. Precedence is given to insertion.
0948: //
0949: for (i = Parser.nasi(stck[stack_top]); Parser.nasr[i] != 0; i++) {
0950: symbol = Parser.nasr[i] + NT_OFFSET;
0951: j = parseCheck(stck, stack_top, symbol,
0952: repair.bufferPosition + 1);
0953: if (j > repair.distance) {
0954: repair.misspellIndex = 0;
0955: repair.distance = j;
0956: repair.symbol = symbol;
0957: repair.code = INVALID_CODE;
0958: }
0959:
0960: j = parseCheck(stck, stack_top, symbol,
0961: repair.bufferPosition);
0962: if ((j > repair.distance)
0963: || (j == repair.distance && repair.code == INVALID_CODE)) {
0964: repair.misspellIndex = 0;
0965: repair.distance = j;
0966: repair.symbol = symbol;
0967: repair.code = INSERTION_CODE;
0968: }
0969: }
0970:
0971: return repair;
0972: }
0973:
0974: //
0975: // This procedure is invoked to issue a diagnostic message and
0976: // adjust the input buffer. The recovery in question is either
0977: // the insertion of one or more scopes, the merging of the error
0978: // token with its successor, the deletion of the error token,
0979: // the insertion of a single token in front of the error token
0980: // or the substitution of another token for the error token.
0981: //
0982: private RepairCandidate primaryDiagnosis(PrimaryRepairInfo repair) {
0983: int name_index;
0984:
0985: //
0986: // Issue diagnostic.
0987: //
0988: int prevtok = buffer[repair.bufferPosition - 1];
0989: int curtok = buffer[repair.bufferPosition];
0990:
0991: switch (repair.code) {
0992: case INSERTION_CODE:
0993: case BEFORE_CODE: {
0994: if (repair.symbol > NT_OFFSET)
0995: name_index = getNtermIndex(stack[stateStackTop],
0996: repair.symbol, repair.bufferPosition);
0997: else
0998: name_index = getTermIndex(stack, stateStackTop,
0999: repair.symbol, repair.bufferPosition);
1000:
1001: int t = (repair.code == INSERTION_CODE ? prevtok : curtok);
1002: reportError(repair.code, name_index, t, t);
1003: break;
1004: }
1005: case INVALID_CODE: {
1006: name_index = getNtermIndex(stack[stateStackTop],
1007: repair.symbol, repair.bufferPosition + 1);
1008: reportError(repair.code, name_index, curtok, curtok);
1009: break;
1010: }
1011: case SUBSTITUTION_CODE: {
1012: if (repair.misspellIndex >= 6)
1013: name_index = Parser.terminal_index[repair.symbol];
1014: else {
1015: name_index = getTermIndex(stack, stateStackTop,
1016: repair.symbol, repair.bufferPosition + 1);
1017: if (name_index != Parser.terminal_index[repair.symbol])
1018: repair.code = INVALID_CODE;
1019: }
1020: reportError(repair.code, name_index, curtok, curtok);
1021: break;
1022: }
1023: case MERGE_CODE: {
1024: reportError(repair.code,
1025: Parser.terminal_index[repair.symbol], curtok,
1026: lexStream.next(curtok));
1027: break;
1028: }
1029: case SCOPE_CODE: {
1030: for (int i = 0; i < scopeStackTop; i++) {
1031: reportError(
1032: repair.code,
1033: -scopeIndex[i],
1034: locationStack[scopePosition[i]],
1035: prevtok,
1036: Parser.non_terminal_index[Parser.scope_lhs[scopeIndex[i]]]);
1037: }
1038:
1039: repair.symbol = Parser.scope_lhs[scopeIndex[scopeStackTop]]
1040: + NT_OFFSET;
1041: stateStackTop = scopePosition[scopeStackTop];
1042: reportError(repair.code, -scopeIndex[scopeStackTop],
1043: locationStack[scopePosition[scopeStackTop]],
1044: prevtok, getNtermIndex(stack[stateStackTop],
1045: repair.symbol, repair.bufferPosition));
1046: break;
1047: }
1048: default: {// deletion
1049: reportError(repair.code,
1050: Parser.terminal_index[ERROR_SYMBOL], curtok, curtok);
1051: }
1052: }
1053:
1054: //
1055: // Update buffer.
1056: //
1057: RepairCandidate candidate = new RepairCandidate();
1058: switch (repair.code) {
1059: case INSERTION_CODE:
1060: case BEFORE_CODE:
1061: case SCOPE_CODE: {
1062: candidate.symbol = repair.symbol;
1063: candidate.location = buffer[repair.bufferPosition];
1064: lexStream.reset(buffer[repair.bufferPosition]);
1065: break;
1066: }
1067: case INVALID_CODE:
1068: case SUBSTITUTION_CODE: {
1069: candidate.symbol = repair.symbol;
1070: candidate.location = buffer[repair.bufferPosition];
1071: lexStream.reset(buffer[repair.bufferPosition + 1]);
1072: break;
1073: }
1074: case MERGE_CODE: {
1075: candidate.symbol = repair.symbol;
1076: candidate.location = buffer[repair.bufferPosition];
1077: lexStream.reset(buffer[repair.bufferPosition + 2]);
1078: break;
1079: }
1080: default: {// deletion
1081: candidate.location = buffer[repair.bufferPosition + 1];
1082: candidate.symbol = lexStream
1083: .kind(buffer[repair.bufferPosition + 1]);
1084: lexStream.reset(buffer[repair.bufferPosition + 2]);
1085: break;
1086: }
1087: }
1088:
1089: return candidate;
1090: }
1091:
1092: //
1093: // This function takes as parameter an integer STACK_TOP that
1094: // points to a STACK element containing the state on which a
1095: // primary recovery will be made; the terminal candidate on which
1096: // to recover; and an integer: buffer_position, which points to
1097: // the position of the next input token in the BUFFER. The
1098: // parser is simulated until a shift (or shift-reduce) action
1099: // is computed on the candidate. Then we proceed to compute the
1100: // the name index of the highest level nonterminal that can
1101: // directly or indirectly produce the candidate.
1102: //
1103: private int getTermIndex(int stck[], int stack_top, int tok,
1104: int buffer_position) {
1105: //
1106: // Initialize stack index of temp_stack and initialize maximum
1107: // position of state stack that is still useful.
1108: //
1109: int act = stck[stack_top], max_pos = stack_top, highest_symbol = tok;
1110:
1111: tempStackTop = stack_top - 1;
1112:
1113: //
1114: // Compute all reduce and associated actions induced by the
1115: // candidate until a SHIFT or SHIFT-REDUCE is computed. ERROR
1116: // and ACCEPT actions cannot be computed on the candidate in
1117: // this context, since we know that it is suitable for recovery.
1118: //
1119: lexStream.reset(buffer[buffer_position]);
1120: act = Parser.tAction(act, tok);
1121: while (act <= NUM_RULES) {
1122: //
1123: // Process all goto-reduce actions following reduction,
1124: // until a goto action is computed ...
1125: //
1126: do {
1127: tempStackTop -= (Parser.rhs[act] - 1);
1128: int lhs_symbol = Parser.lhs[act];
1129: act = (tempStackTop > max_pos ? tempStack[tempStackTop]
1130: : stck[tempStackTop]);
1131: act = Parser.ntAction(act, lhs_symbol);
1132: } while (act <= NUM_RULES);
1133:
1134: //
1135: // Compute new maximum useful position of (STATE_)stack,
1136: // push goto state into the stack, and compute next
1137: // action on candidate ...
1138: //
1139: max_pos = max_pos < tempStackTop ? max_pos : tempStackTop;
1140: tempStack[tempStackTop + 1] = act;
1141: act = Parser.tAction(act, tok);
1142: }
1143:
1144: //
1145: // At this stage, we have simulated all actions induced by the
1146: // candidate and we are ready to shift or shift-reduce it. First,
1147: // set tok and next_ptr appropriately and identify the candidate
1148: // as the initial highest_symbol. If a shift action was computed
1149: // on the candidate, update the stack and compute the next
1150: // action. Next, simulate all actions possible on the next input
1151: // token until we either have to shift it or are about to reduce
1152: // below the initial starting point in the stack (indicated by
1153: // max_pos as computed in the previous loop). At that point,
1154: // return the highest_symbol computed.
1155: //
1156: tempStackTop++; // adjust top of stack to reflect last goto
1157: // next move is shift or shift-reduce.
1158: int threshold = tempStackTop;
1159:
1160: tok = lexStream.kind(buffer[buffer_position]);
1161: lexStream.reset(buffer[buffer_position + 1]);
1162:
1163: if (act > ERROR_ACTION) { // shift-reduce on candidate?
1164: act -= ERROR_ACTION;
1165: } else {
1166: tempStack[tempStackTop + 1] = act;
1167: act = Parser.tAction(act, tok);
1168: }
1169:
1170: while (act <= NUM_RULES) {
1171: //
1172: // Process all goto-reduce actions following reduction,
1173: // until a goto action is computed ...
1174: //
1175: do {
1176: tempStackTop -= (Parser.rhs[act] - 1);
1177:
1178: if (tempStackTop < threshold) {
1179: return (highest_symbol > NT_OFFSET ? Parser.non_terminal_index[highest_symbol
1180: - NT_OFFSET]
1181: : Parser.terminal_index[highest_symbol]);
1182: }
1183:
1184: int lhs_symbol = Parser.lhs[act];
1185: if (tempStackTop == threshold)
1186: highest_symbol = lhs_symbol + NT_OFFSET;
1187: act = (tempStackTop > max_pos ? tempStack[tempStackTop]
1188: : stck[tempStackTop]);
1189: act = Parser.ntAction(act, lhs_symbol);
1190: } while (act <= NUM_RULES);
1191:
1192: tempStack[tempStackTop + 1] = act;
1193: act = Parser.tAction(act, tok);
1194: }
1195:
1196: return (highest_symbol > NT_OFFSET ? Parser.non_terminal_index[highest_symbol
1197: - NT_OFFSET]
1198: : Parser.terminal_index[highest_symbol]);
1199: }
1200:
1201: //
1202: // This function takes as parameter a starting state number:
1203: // start, a nonterminal symbol, A (candidate), and an integer,
1204: // buffer_position, which points to the position of the next
1205: // input token in the BUFFER.
1206: // It returns the highest level non-terminal B such that
1207: // B =>*rm A. I.e., there does not exists a nonterminal C such
1208: // that C =>+rm B. (Recall that for an LALR(k) grammar if
1209: // C =>+rm B, it cannot be the case that B =>+rm C)
1210: //
1211: private int getNtermIndex(int start, int sym, int buffer_position) {
1212: int highest_symbol = sym - NT_OFFSET, tok = lexStream
1213: .kind(buffer[buffer_position]);
1214: lexStream.reset(buffer[buffer_position + 1]);
1215:
1216: //
1217: // Initialize stack index of temp_stack and initialize maximum
1218: // position of state stack that is still useful.
1219: //
1220: tempStackTop = 0;
1221: tempStack[tempStackTop] = start;
1222:
1223: int act = Parser.ntAction(start, highest_symbol);
1224: if (act > NUM_RULES) { // goto action?
1225: tempStack[tempStackTop + 1] = act;
1226: act = Parser.tAction(act, tok);
1227: }
1228:
1229: while (act <= NUM_RULES) {
1230: //
1231: // Process all goto-reduce actions following reduction,
1232: // until a goto action is computed ...
1233: //
1234: do {
1235: tempStackTop -= (Parser.rhs[act] - 1);
1236: if (tempStackTop < 0)
1237: return Parser.non_terminal_index[highest_symbol];
1238: if (tempStackTop == 0)
1239: highest_symbol = Parser.lhs[act];
1240: act = Parser.ntAction(tempStack[tempStackTop],
1241: Parser.lhs[act]);
1242: } while (act <= NUM_RULES);
1243: tempStack[tempStackTop + 1] = act;
1244: act = Parser.tAction(act, tok);
1245: }
1246:
1247: return Parser.non_terminal_index[highest_symbol];
1248: }
1249:
1250: private boolean isBetterSymbol(int symbol, int actualSymbol) {
1251: // switch (actualSymbol) {
1252: // case TokenNameinterface :
1253: // if(symbol == TokenNameclass) {
1254: // return true;
1255: // }
1256: // break;
1257: // }
1258: return false;
1259: }
1260:
1261: //
1262: // Check whether or not there is a high probability that a
1263: // given string is a misspelling of another.
1264: // Certain singleton symbols (such as ":" and ";") are also
1265: // considered to be misspelling of each other.
1266: //
1267: private int misspell(int sym, int tok) {
1268:
1269: //
1270: //
1271: //
1272: char[] name = Parser.name[Parser.terminal_index[sym]]
1273: .toCharArray();
1274: int n = name.length;
1275: char[] s1 = new char[n + 1];
1276: for (int k = 0; k < n; k++) {
1277: char c = name[k];
1278: s1[k] = ScannerHelper.toLowerCase(c);
1279: }
1280: s1[n] = '\0';
1281:
1282: //
1283: //
1284: //
1285: char[] tokenName = lexStream.name(tok);
1286: int len = tokenName.length;
1287: int m = len < MAX_NAME_LENGTH ? len : MAX_NAME_LENGTH;
1288: char[] s2 = new char[m + 1];
1289: for (int k = 0; k < m; k++) {
1290: char c = tokenName[k];
1291: s2[k] = ScannerHelper.toLowerCase(c);
1292: }
1293: s2[m] = '\0';
1294:
1295: //
1296: // Singleton mispellings:
1297: //
1298: // ; <----> ,
1299: //
1300: // ; <----> :
1301: //
1302: // . <----> ,
1303: //
1304: // ' <----> "
1305: //
1306: //
1307: if (n == 1 && m == 1) {
1308: if ((s1[0] == ';' && s2[0] == ',')
1309: || (s1[0] == ',' && s2[0] == ';')
1310: || (s1[0] == ';' && s2[0] == ':')
1311: || (s1[0] == ':' && s2[0] == ';')
1312: || (s1[0] == '.' && s2[0] == ',')
1313: || (s1[0] == ',' && s2[0] == '.')
1314: || (s1[0] == '\'' && s2[0] == '\"')
1315: || (s1[0] == '\"' && s2[0] == '\'')) {
1316: return 3;
1317: }
1318: }
1319:
1320: //
1321: // Scan the two strings. Increment "match" count for each match.
1322: // When a transposition is encountered, increase "match" count
1323: // by two but count it as an error. When a typo is found, skip
1324: // it and count it as an error. Otherwise we have a mismatch; if
1325: // one of the strings is longer, increment its index, otherwise,
1326: // increment both indices and continue.
1327: //
1328: // This algorithm is an adaptation of a boolean misspelling
1329: // algorithm proposed by Juergen Uhl.
1330: //
1331: int count = 0;
1332: int prefix_length = 0;
1333: int num_errors = 0;
1334:
1335: int i = 0;
1336: int j = 0;
1337: while ((i < n) && (j < m)) {
1338: if (s1[i] == s2[j]) {
1339: count++;
1340: i++;
1341: j++;
1342: if (num_errors == 0) {
1343: prefix_length++;
1344: }
1345: } else if (s1[i + 1] == s2[j] && s1[i] == s2[j + 1]) {
1346: count += 2;
1347: i += 2;
1348: j += 2;
1349: num_errors++;
1350: } else if (s1[i + 1] == s2[j + 1]) {
1351: i++;
1352: j++;
1353: num_errors++;
1354: } else {
1355: if ((n - i) > (m - j)) {
1356: i++;
1357: } else if ((m - j) > (n - i)) {
1358: j++;
1359: } else {
1360: i++;
1361: j++;
1362: }
1363: num_errors++;
1364: }
1365: }
1366:
1367: if (i < n || j < m)
1368: num_errors++;
1369:
1370: if (num_errors > ((n < m ? n : m) / 6 + 1))
1371: count = prefix_length;
1372:
1373: return (count * 10 / ((n < len ? len : n) + num_errors));
1374: }
1375:
1376: private PrimaryRepairInfo scopeTrial(int stck[], int stack_top,
1377: PrimaryRepairInfo repair) {
1378: stateSeen = new int[stackLength];
1379: for (int i = 0; i < stackLength; i++)
1380: stateSeen[i] = NIL;
1381:
1382: statePoolTop = 0;
1383: statePool = new StateInfo[stackLength];
1384:
1385: scopeTrialCheck(stck, stack_top, repair, 0);
1386:
1387: stateSeen = null;
1388: statePoolTop = 0;
1389:
1390: repair.code = SCOPE_CODE;
1391: repair.misspellIndex = 10;
1392:
1393: return repair;
1394: }
1395:
1396: private void scopeTrialCheck(int stck[], int stack_top,
1397: PrimaryRepairInfo repair, int indx) {
1398: if (indx > 20)
1399: return; // avoid too much recursive call to improve performance
1400:
1401: int act = stck[stack_top];
1402:
1403: for (int i = stateSeen[stack_top]; i != NIL; i = statePool[i].next) {
1404: if (statePool[i].state == act)
1405: return;
1406: }
1407:
1408: int old_state_pool_top = statePoolTop++;
1409: if (statePoolTop >= statePool.length) {
1410: System.arraycopy(statePool, 0,
1411: statePool = new StateInfo[statePoolTop * 2], 0,
1412: statePoolTop);
1413: }
1414:
1415: statePool[old_state_pool_top] = new StateInfo(act,
1416: stateSeen[stack_top]);
1417: stateSeen[stack_top] = old_state_pool_top;
1418:
1419: next: for (int i = 0; i < SCOPE_SIZE; i++) {
1420: //
1421: // Use the scope lookahead symbol to force all reductions
1422: // inducible by that symbol.
1423: //
1424: act = stck[stack_top];
1425: tempStackTop = stack_top - 1;
1426: int max_pos = stack_top;
1427: int tok = Parser.scope_la[i];
1428: lexStream.reset(buffer[repair.bufferPosition]);
1429: act = Parser.tAction(act, tok);
1430: while (act <= NUM_RULES) {
1431: //
1432: // ... Process all goto-reduce actions following
1433: // reduction, until a goto action is computed ...
1434: //
1435: do {
1436: tempStackTop -= (Parser.rhs[act] - 1);
1437: int lhs_symbol = Parser.lhs[act];
1438: act = (tempStackTop > max_pos ? tempStack[tempStackTop]
1439: : stck[tempStackTop]);
1440: act = Parser.ntAction(act, lhs_symbol);
1441: } while (act <= NUM_RULES);
1442: if (tempStackTop + 1 >= stackLength)
1443: return;
1444: max_pos = max_pos < tempStackTop ? max_pos
1445: : tempStackTop;
1446: tempStack[tempStackTop + 1] = act;
1447: act = Parser.tAction(act, tok);
1448: }
1449:
1450: //
1451: // If the lookahead symbol is parsable, then we check
1452: // whether or not we have a match between the scope
1453: // prefix and the transition symbols corresponding to
1454: // the states on top of the stack.
1455: //
1456: if (act != ERROR_ACTION) {
1457: int j, k;
1458: k = Parser.scope_prefix[i];
1459: for (j = tempStackTop + 1; j >= (max_pos + 1)
1460: && Parser.in_symbol(tempStack[j]) == Parser.scope_rhs[k]; j--) {
1461: k++;
1462: }
1463: if (j == max_pos) {
1464: for (j = max_pos; j >= 1
1465: && Parser.in_symbol(stck[j]) == Parser.scope_rhs[k]; j--) {
1466: k++;
1467: }
1468: }
1469: //
1470: // If the prefix matches, check whether the state
1471: // newly exposed on top of the stack, (after the
1472: // corresponding prefix states are popped from the
1473: // stack), is in the set of "source states" for the
1474: // scope in question and that it is at a position
1475: // below the threshold indicated by MARKED_POS.
1476: //
1477: int marked_pos = (max_pos < stack_top ? max_pos + 1
1478: : stack_top);
1479: if (Parser.scope_rhs[k] == 0 && j < marked_pos) { // match?
1480: int stack_position = j;
1481: for (j = Parser.scope_state_set[i]; stck[stack_position] != Parser.scope_state[j]
1482: && Parser.scope_state[j] != 0; j++) {/*empty*/
1483: }
1484: //
1485: // If the top state is valid for scope recovery,
1486: // the left-hand side of the scope is used as
1487: // starting symbol and we calculate how far the
1488: // parser can advance within the forward context
1489: // after parsing the left-hand symbol.
1490: //
1491: if (Parser.scope_state[j] != 0) { // state was found
1492: int previous_distance = repair.distance;
1493: int distance = parseCheck(stck, stack_position,
1494: Parser.scope_lhs[i] + NT_OFFSET,
1495: repair.bufferPosition);
1496: //
1497: // if the recovery is not successful, we
1498: // update the stack with all actions induced
1499: // by the left-hand symbol, and recursively
1500: // call SCOPE_TRIAL_CHECK to try again.
1501: // Otherwise, the recovery is successful. If
1502: // the new distance is greater than the
1503: // initial SCOPE_DISTANCE, we update
1504: // SCOPE_DISTANCE and set scope_stack_top to INDX
1505: // to indicate the number of scopes that are
1506: // to be applied for a succesful recovery.
1507: // NOTE that this procedure cannot get into
1508: // an infinite loop, since each prefix match
1509: // is guaranteed to take us to a lower point
1510: // within the stack.
1511: //
1512: if ((distance - repair.bufferPosition + 1) < MIN_DISTANCE) {
1513: int top = stack_position;
1514: act = Parser.ntAction(stck[top],
1515: Parser.scope_lhs[i]);
1516: while (act <= NUM_RULES) {
1517: if (Parser.rules_compliance[act] > this .options.sourceLevel) {
1518: continue next;
1519: }
1520: top -= (Parser.rhs[act] - 1);
1521: act = Parser.ntAction(stck[top],
1522: Parser.lhs[act]);
1523: }
1524: top++;
1525:
1526: j = act;
1527: act = stck[top]; // save
1528: stck[top] = j; // swap
1529: scopeTrialCheck(stck, top, repair, indx + 1);
1530: stck[top] = act; // restore
1531: } else if (distance > repair.distance) {
1532: scopeStackTop = indx;
1533: repair.distance = distance;
1534: }
1535:
1536: if (lexStream
1537: .kind(buffer[repair.bufferPosition]) == EOFT_SYMBOL
1538: && repair.distance == previous_distance) {
1539: scopeStackTop = indx;
1540: repair.distance = MAX_DISTANCE;
1541: }
1542:
1543: //
1544: // If this scope recovery has beaten the
1545: // previous distance, then we have found a
1546: // better recovery (or this recovery is one
1547: // of a list of scope recoveries). Record
1548: // its information at the proper location
1549: // (INDX) in SCOPE_INDEX and SCOPE_STACK.
1550: //
1551: if (repair.distance > previous_distance) {
1552: scopeIndex[indx] = i;
1553: scopePosition[indx] = stack_position;
1554: return;
1555: }
1556: }
1557: }
1558: }
1559: }
1560: }
1561:
1562: //
1563: // This function computes the ParseCheck distance for the best
1564: // possible secondary recovery for a given configuration that
1565: // either deletes none or only one symbol in the forward context.
1566: // If the recovery found is more effective than the best primary
1567: // recovery previously computed, then the function returns true.
1568: // Only misplacement, scope and manual recoveries are attempted;
1569: // simple insertion or substitution of a nonterminal are tried
1570: // in CHECK_PRIMARY_DISTANCE as part of primary recovery.
1571: //
1572: private boolean secondaryCheck(int stck[], int stack_top,
1573: int buffer_position, int distance) {
1574: int top, j;
1575:
1576: for (top = stack_top - 1; top >= 0; top--) {
1577: j = parseCheck(stck, top, lexStream
1578: .kind(buffer[buffer_position]), buffer_position + 1);
1579: if (((j - buffer_position + 1) > MIN_DISTANCE)
1580: && (j > distance))
1581: return true;
1582: }
1583:
1584: PrimaryRepairInfo repair = new PrimaryRepairInfo();
1585: repair.bufferPosition = buffer_position + 1;
1586: repair.distance = distance;
1587: repair = scopeTrial(stck, stack_top, repair);
1588: if ((repair.distance - buffer_position) > MIN_DISTANCE
1589: && repair.distance > distance)
1590: return true;
1591: return false;
1592: }
1593:
1594: //
1595: // Secondary_phase is a boolean function that checks whether or
1596: // not some form of secondary recovery is applicable to one of
1597: // the error configurations. First, if "next_stack" is available,
1598: // misplacement and secondary recoveries are attempted on it.
1599: // Then, in any case, these recoveries are attempted on "stack".
1600: // If a successful recovery is found, a diagnosis is issued, the
1601: // configuration is updated and the function returns "true".
1602: // Otherwise, the function returns false.
1603: //
1604: private RepairCandidate secondaryPhase(int error_token) {
1605: SecondaryRepairInfo repair = new SecondaryRepairInfo();
1606: SecondaryRepairInfo misplaced = new SecondaryRepairInfo();
1607:
1608: RepairCandidate candidate = new RepairCandidate();
1609:
1610: int i, j, k, top;
1611: int next_last_index = 0;
1612: int last_index;
1613:
1614: candidate.symbol = 0;
1615:
1616: repair.code = 0;
1617: repair.distance = 0;
1618: repair.recoveryOnNextStack = false;
1619:
1620: misplaced.distance = 0;
1621: misplaced.recoveryOnNextStack = false;
1622:
1623: //
1624: // If the next_stack is available, try misplaced and secondary
1625: // recovery on it first.
1626: //
1627: if (nextStackTop >= 0) {
1628: int save_location;
1629:
1630: buffer[2] = error_token;
1631: buffer[1] = lexStream.previous(buffer[2]);
1632: buffer[0] = lexStream.previous(buffer[1]);
1633:
1634: for (k = 3; k < BUFF_UBOUND; k++)
1635: buffer[k] = lexStream.next(buffer[k - 1]);
1636:
1637: buffer[BUFF_UBOUND] = lexStream.badtoken();// elmt not available
1638:
1639: //
1640: // If we are at the end of the input stream, compute the
1641: // index position of the first EOFT symbol (last useful
1642: // index).
1643: //
1644: for (next_last_index = MAX_DISTANCE - 1; next_last_index >= 1
1645: && lexStream.kind(buffer[next_last_index]) == EOFT_SYMBOL; next_last_index--) {/*empty*/
1646: }
1647: next_last_index = next_last_index + 1;
1648:
1649: save_location = locationStack[nextStackTop];
1650: int save_location_start = locationStartStack[nextStackTop];
1651: locationStack[nextStackTop] = buffer[2];
1652: locationStartStack[nextStackTop] = lexStream
1653: .start(buffer[2]);
1654: misplaced.numDeletions = nextStackTop;
1655: misplaced = misplacementRecovery(nextStack, nextStackTop,
1656: next_last_index, misplaced, true);
1657: if (misplaced.recoveryOnNextStack)
1658: misplaced.distance++;
1659:
1660: repair.numDeletions = nextStackTop + BUFF_UBOUND;
1661: repair = secondaryRecovery(nextStack, nextStackTop,
1662: next_last_index, repair, true);
1663: if (repair.recoveryOnNextStack)
1664: repair.distance++;
1665:
1666: locationStack[nextStackTop] = save_location;
1667: locationStartStack[nextStackTop] = save_location_start;
1668: } else { // next_stack not available, initialize ...
1669: misplaced.numDeletions = stateStackTop;
1670: repair.numDeletions = stateStackTop + BUFF_UBOUND;
1671: }
1672:
1673: //
1674: // Try secondary recovery on the "stack" configuration.
1675: //
1676: buffer[3] = error_token;
1677:
1678: buffer[2] = lexStream.previous(buffer[3]);
1679: buffer[1] = lexStream.previous(buffer[2]);
1680: buffer[0] = lexStream.previous(buffer[1]);
1681:
1682: for (k = 4; k < BUFF_SIZE; k++)
1683: buffer[k] = lexStream.next(buffer[k - 1]);
1684:
1685: for (last_index = MAX_DISTANCE - 1; last_index >= 1
1686: && lexStream.kind(buffer[last_index]) == EOFT_SYMBOL; last_index--) {/*empty*/
1687: }
1688: last_index++;
1689:
1690: misplaced = misplacementRecovery(stack, stateStackTop,
1691: last_index, misplaced, false);
1692:
1693: repair = secondaryRecovery(stack, stateStackTop, last_index,
1694: repair, false);
1695:
1696: //
1697: // If a successful misplaced recovery was found, compare it with
1698: // the most successful secondary recovery. If the misplaced
1699: // recovery either deletes fewer symbols or parse-checks further
1700: // then it is chosen.
1701: //
1702: if (misplaced.distance > MIN_DISTANCE) {
1703: if (misplaced.numDeletions <= repair.numDeletions
1704: || (misplaced.distance - misplaced.numDeletions) >= (repair.distance - repair.numDeletions)) {
1705: repair.code = MISPLACED_CODE;
1706: repair.stackPosition = misplaced.stackPosition;
1707: repair.bufferPosition = 2;
1708: repair.numDeletions = misplaced.numDeletions;
1709: repair.distance = misplaced.distance;
1710: repair.recoveryOnNextStack = misplaced.recoveryOnNextStack;
1711: }
1712: }
1713:
1714: //
1715: // If the successful recovery was on next_stack, update: stack,
1716: // buffer, location_stack and last_index.
1717: //
1718: if (repair.recoveryOnNextStack) {
1719: stateStackTop = nextStackTop;
1720: for (i = 0; i <= stateStackTop; i++)
1721: stack[i] = nextStack[i];
1722:
1723: buffer[2] = error_token;
1724: buffer[1] = lexStream.previous(buffer[2]);
1725: buffer[0] = lexStream.previous(buffer[1]);
1726:
1727: for (k = 3; k < BUFF_UBOUND; k++)
1728: buffer[k] = lexStream.next(buffer[k - 1]);
1729:
1730: buffer[BUFF_UBOUND] = lexStream.badtoken();// elmt not available
1731:
1732: locationStack[nextStackTop] = buffer[2];
1733: locationStartStack[nextStackTop] = lexStream
1734: .start(buffer[2]);
1735: last_index = next_last_index;
1736: }
1737:
1738: //
1739: // Next, try scope recoveries after deletion of one, two, three,
1740: // four ... buffer_position tokens from the input stream.
1741: //
1742: if (repair.code == SECONDARY_CODE
1743: || repair.code == DELETION_CODE) {
1744: PrimaryRepairInfo scope_repair = new PrimaryRepairInfo();
1745:
1746: scope_repair.distance = 0;
1747: for (scope_repair.bufferPosition = 2; scope_repair.bufferPosition <= repair.bufferPosition
1748: && repair.code != SCOPE_CODE; scope_repair.bufferPosition++) {
1749: scope_repair = scopeTrial(stack, stateStackTop,
1750: scope_repair);
1751: j = (scope_repair.distance == MAX_DISTANCE ? last_index
1752: : scope_repair.distance);
1753: k = scope_repair.bufferPosition - 1;
1754: if ((j - k) > MIN_DISTANCE
1755: && (j - k) > (repair.distance - repair.numDeletions)) {
1756: repair.code = SCOPE_CODE;
1757: i = scopeIndex[scopeStackTop]; // upper bound
1758: repair.symbol = Parser.scope_lhs[i] + NT_OFFSET;
1759: repair.stackPosition = stateStackTop;
1760: repair.bufferPosition = scope_repair.bufferPosition;
1761: }
1762: }
1763: }
1764:
1765: //
1766: // If no successful recovery is found and we have reached the
1767: // end of the file, check whether or not scope recovery is
1768: // applicable at the end of the file after discarding some
1769: // states.
1770: //
1771: if (repair.code == 0
1772: && lexStream.kind(buffer[last_index]) == EOFT_SYMBOL) {
1773: PrimaryRepairInfo scope_repair = new PrimaryRepairInfo();
1774:
1775: scope_repair.bufferPosition = last_index;
1776: scope_repair.distance = 0;
1777: for (top = stateStackTop; top >= 0 && repair.code == 0; top--) {
1778: scope_repair = scopeTrial(stack, top, scope_repair);
1779: if (scope_repair.distance > 0) {
1780: repair.code = SCOPE_CODE;
1781: i = scopeIndex[scopeStackTop]; // upper bound
1782: repair.symbol = Parser.scope_lhs[i] + NT_OFFSET;
1783: repair.stackPosition = top;
1784: repair.bufferPosition = scope_repair.bufferPosition;
1785: }
1786: }
1787: }
1788:
1789: //
1790: // If a successful repair was not found, quit! Otherwise, issue
1791: // diagnosis and adjust configuration...
1792: //
1793: if (repair.code == 0)
1794: return candidate;
1795:
1796: secondaryDiagnosis(repair);
1797:
1798: //
1799: // Update buffer based on number of elements that are deleted.
1800: //
1801: switch (repair.code) {
1802: case MISPLACED_CODE:
1803: candidate.location = buffer[2];
1804: candidate.symbol = lexStream.kind(buffer[2]);
1805: lexStream.reset(lexStream.next(buffer[2]));
1806:
1807: break;
1808:
1809: case DELETION_CODE:
1810: candidate.location = buffer[repair.bufferPosition];
1811: candidate.symbol = lexStream
1812: .kind(buffer[repair.bufferPosition]);
1813: lexStream.reset(lexStream
1814: .next(buffer[repair.bufferPosition]));
1815:
1816: break;
1817:
1818: default: // SCOPE_CODE || SECONDARY_CODE
1819: candidate.symbol = repair.symbol;
1820: candidate.location = buffer[repair.bufferPosition];
1821: lexStream.reset(buffer[repair.bufferPosition]);
1822:
1823: break;
1824: }
1825:
1826: return candidate;
1827: }
1828:
1829: //
1830: // This boolean function checks whether or not a given
1831: // configuration yields a better misplacement recovery than
1832: // the best misplacement recovery computed previously.
1833: //
1834: private SecondaryRepairInfo misplacementRecovery(int stck[],
1835: int stack_top, int last_index, SecondaryRepairInfo repair,
1836: boolean stack_flag) {
1837: int previous_loc = buffer[2];
1838: int stack_deletions = 0;
1839:
1840: for (int top = stack_top - 1; top >= 0; top--) {
1841: if (locationStack[top] < previous_loc) {
1842: stack_deletions++;
1843: }
1844: previous_loc = locationStack[top];
1845:
1846: int j = parseCheck(stck, top, lexStream.kind(buffer[2]), 3);
1847: if (j == MAX_DISTANCE) {
1848: j = last_index;
1849: }
1850: if ((j > MIN_DISTANCE)
1851: && (j - stack_deletions) > (repair.distance - repair.numDeletions)) {
1852: repair.stackPosition = top;
1853: repair.distance = j;
1854: repair.numDeletions = stack_deletions;
1855: repair.recoveryOnNextStack = stack_flag;
1856: }
1857: }
1858:
1859: return repair;
1860: }
1861:
1862: //
1863: // This boolean function checks whether or not a given
1864: // configuration yields a better secondary recovery than the
1865: // best misplacement recovery computed previously.
1866: //
1867: private SecondaryRepairInfo secondaryRecovery(int stck[],
1868: int stack_top, int last_index, SecondaryRepairInfo repair,
1869: boolean stack_flag) {
1870: int previous_loc;
1871: int stack_deletions = 0;
1872:
1873: previous_loc = buffer[2];
1874: for (int top = stack_top; top >= 0
1875: && repair.numDeletions >= stack_deletions; top--) {
1876: if (locationStack[top] < previous_loc) {
1877: stack_deletions++;
1878: }
1879: previous_loc = locationStack[top];
1880:
1881: for (int i = 2; i <= (last_index - MIN_DISTANCE + 1)
1882: && (repair.numDeletions >= (stack_deletions + i - 1)); i++) {
1883: int j = parseCheck(stck, top,
1884: lexStream.kind(buffer[i]), i + 1);
1885:
1886: if (j == MAX_DISTANCE) {
1887: j = last_index;
1888: }
1889: if ((j - i + 1) > MIN_DISTANCE) {
1890: int k = stack_deletions + i - 1;
1891: if ((k < repair.numDeletions)
1892: || (j - k) > (repair.distance - repair.numDeletions)
1893: || ((repair.code == SECONDARY_CODE) && (j - k) == (repair.distance - repair.numDeletions))) {
1894: repair.code = DELETION_CODE;
1895: repair.distance = j;
1896: repair.stackPosition = top;
1897: repair.bufferPosition = i;
1898: repair.numDeletions = k;
1899: repair.recoveryOnNextStack = stack_flag;
1900: }
1901: }
1902:
1903: for (int l = Parser.nasi(stck[top]); l >= 0
1904: && Parser.nasr[l] != 0; l++) {
1905: int symbol = Parser.nasr[l] + NT_OFFSET;
1906: j = parseCheck(stck, top, symbol, i);
1907: if (j == MAX_DISTANCE) {
1908: j = last_index;
1909: }
1910: if ((j - i + 1) > MIN_DISTANCE) {
1911: int k = stack_deletions + i - 1;
1912: if (k < repair.numDeletions
1913: || (j - k) > (repair.distance - repair.numDeletions)) {
1914: repair.code = SECONDARY_CODE;
1915: repair.symbol = symbol;
1916: repair.distance = j;
1917: repair.stackPosition = top;
1918: repair.bufferPosition = i;
1919: repair.numDeletions = k;
1920: repair.recoveryOnNextStack = stack_flag;
1921: }
1922: }
1923: }
1924: }
1925: }
1926:
1927: return repair;
1928: }
1929:
1930: //
1931: // This procedure is invoked to issue a secondary diagnosis and
1932: // adjust the input buffer. The recovery in question is either
1933: // an automatic scope recovery, a manual scope recovery, a
1934: // secondary substitution or a secondary deletion.
1935: //
1936: private void secondaryDiagnosis(SecondaryRepairInfo repair) {
1937: switch (repair.code) {
1938: case SCOPE_CODE: {
1939: if (repair.stackPosition < stateStackTop) {
1940: reportError(DELETION_CODE,
1941: Parser.terminal_index[ERROR_SYMBOL],
1942: locationStack[repair.stackPosition], buffer[1]);
1943: }
1944: for (int i = 0; i < scopeStackTop; i++) {
1945: reportError(
1946: SCOPE_CODE,
1947: -scopeIndex[i],
1948: locationStack[scopePosition[i]],
1949: buffer[1],
1950: Parser.non_terminal_index[Parser.scope_lhs[scopeIndex[i]]]);
1951: }
1952:
1953: repair.symbol = Parser.scope_lhs[scopeIndex[scopeStackTop]]
1954: + NT_OFFSET;
1955: stateStackTop = scopePosition[scopeStackTop];
1956: reportError(SCOPE_CODE, -scopeIndex[scopeStackTop],
1957: locationStack[scopePosition[scopeStackTop]],
1958: buffer[1], getNtermIndex(stack[stateStackTop],
1959: repair.symbol, repair.bufferPosition));
1960: break;
1961: }
1962: default: {
1963: reportError(repair.code,
1964: (repair.code == SECONDARY_CODE ? getNtermIndex(
1965: stack[repair.stackPosition], repair.symbol,
1966: repair.bufferPosition)
1967: : Parser.terminal_index[ERROR_SYMBOL]),
1968: locationStack[repair.stackPosition],
1969: buffer[repair.bufferPosition - 1]);
1970: stateStackTop = repair.stackPosition;
1971: }
1972: }
1973: }
1974:
1975: //
1976: // Try to parse until first_token and all tokens in BUFFER have
1977: // been consumed, or an error is encountered. Return the number
1978: // of tokens that were expended before the parse blocked.
1979: //
1980: private int parseCheck(int stck[], int stack_top, int first_token,
1981: int buffer_position) {
1982: int max_pos;
1983: int indx;
1984: int ct;
1985: int act;
1986:
1987: //
1988: // Initialize pointer for temp_stack and initialize maximum
1989: // position of state stack that is still useful.
1990: //
1991: act = stck[stack_top];
1992: if (first_token > NT_OFFSET) {
1993: tempStackTop = stack_top;
1994: if (DEBUG_PARSECHECK) {
1995: System.out.println(tempStackTop);
1996: }
1997: max_pos = stack_top;
1998: indx = buffer_position;
1999: ct = lexStream.kind(buffer[indx]);
2000: lexStream.reset(lexStream.next(buffer[indx]));
2001: int lhs_symbol = first_token - NT_OFFSET;
2002: act = Parser.ntAction(act, lhs_symbol);
2003: if (act <= NUM_RULES) {
2004: // same loop as 'process_non_terminal'
2005: do {
2006: tempStackTop -= (Parser.rhs[act] - 1);
2007:
2008: if (DEBUG_PARSECHECK) {
2009: System.out.print(tempStackTop);
2010: System.out.print(" ("); //$NON-NLS-1$
2011: System.out.print(-(Parser.rhs[act] - 1));
2012: System.out.print(") [max:"); //$NON-NLS-1$
2013: System.out.print(max_pos);
2014: System.out.print("]\tprocess_non_terminal\t"); //$NON-NLS-1$
2015: System.out.print(act);
2016: System.out.print("\t"); //$NON-NLS-1$
2017: System.out
2018: .print(Parser.name[Parser.non_terminal_index[Parser.lhs[act]]]);
2019: System.out.println();
2020: }
2021:
2022: if (Parser.rules_compliance[act] > this .options.sourceLevel) {
2023: return 0;
2024: }
2025: lhs_symbol = Parser.lhs[act];
2026: act = (tempStackTop > max_pos ? tempStack[tempStackTop]
2027: : stck[tempStackTop]);
2028: act = Parser.ntAction(act, lhs_symbol);
2029: } while (act <= NUM_RULES);
2030:
2031: max_pos = max_pos < tempStackTop ? max_pos
2032: : tempStackTop;
2033: }
2034: } else {
2035: tempStackTop = stack_top - 1;
2036:
2037: if (DEBUG_PARSECHECK) {
2038: System.out.println(tempStackTop);
2039: }
2040:
2041: max_pos = tempStackTop;
2042: indx = buffer_position - 1;
2043: ct = first_token;
2044: lexStream.reset(buffer[buffer_position]);
2045: }
2046:
2047: process_terminal: for (;;) {
2048: if (DEBUG_PARSECHECK) {
2049: System.out.print(tempStackTop + 1);
2050: System.out.print(" (+1) [max:"); //$NON-NLS-1$
2051: System.out.print(max_pos);
2052: System.out.print("]\tprocess_terminal \t"); //$NON-NLS-1$
2053: System.out.print(ct);
2054: System.out.print("\t"); //$NON-NLS-1$
2055: System.out
2056: .print(Parser.name[Parser.terminal_index[ct]]);
2057: System.out.println();
2058: }
2059:
2060: if (++tempStackTop >= stackLength) // Stack overflow!!!
2061: return indx;
2062: tempStack[tempStackTop] = act;
2063:
2064: act = Parser.tAction(act, ct);
2065:
2066: if (act <= NUM_RULES) { // reduce action
2067: tempStackTop--;
2068:
2069: if (DEBUG_PARSECHECK) {
2070: System.out.print(tempStackTop);
2071: System.out.print(" (-1) [max:"); //$NON-NLS-1$
2072: System.out.print(max_pos);
2073: System.out.print("]\treduce"); //$NON-NLS-1$
2074: System.out.println();
2075: }
2076: } else if (act < ACCEPT_ACTION || // shift action
2077: act > ERROR_ACTION) { // shift-reduce action
2078: if (indx == MAX_DISTANCE)
2079: return indx;
2080: indx++;
2081: ct = lexStream.kind(buffer[indx]);
2082: lexStream.reset(lexStream.next(buffer[indx]));
2083: if (act > ERROR_ACTION) {
2084: act -= ERROR_ACTION;
2085:
2086: if (DEBUG_PARSECHECK) {
2087: System.out.print(tempStackTop);
2088: System.out.print("\tshift reduce"); //$NON-NLS-1$
2089: System.out.println();
2090: }
2091: } else {
2092: if (DEBUG_PARSECHECK) {
2093: System.out.println("\tshift"); //$NON-NLS-1$
2094: }
2095: continue process_terminal;
2096: }
2097: } else if (act == ACCEPT_ACTION) { // accept action
2098: return MAX_DISTANCE;
2099: } else {
2100: return indx; // error action
2101: }
2102:
2103: // same loop as first token initialization
2104: // process_non_terminal:
2105: do {
2106: tempStackTop -= (Parser.rhs[act] - 1);
2107:
2108: if (DEBUG_PARSECHECK) {
2109: System.out.print(tempStackTop);
2110: System.out.print(" ("); //$NON-NLS-1$
2111: System.out.print(-(Parser.rhs[act] - 1));
2112: System.out.print(") [max:"); //$NON-NLS-1$
2113: System.out.print(max_pos);
2114: System.out.print("]\tprocess_non_terminal\t"); //$NON-NLS-1$
2115: System.out.print(act);
2116: System.out.print("\t"); //$NON-NLS-1$
2117: System.out
2118: .print(Parser.name[Parser.non_terminal_index[Parser.lhs[act]]]);
2119: System.out.println();
2120: }
2121:
2122: if (act <= NUM_RULES) {
2123: if (Parser.rules_compliance[act] > this .options.sourceLevel) {
2124: return 0;
2125: }
2126: }
2127: int lhs_symbol = Parser.lhs[act];
2128: act = (tempStackTop > max_pos ? tempStack[tempStackTop]
2129: : stck[tempStackTop]);
2130: act = Parser.ntAction(act, lhs_symbol);
2131: } while (act <= NUM_RULES);
2132:
2133: max_pos = max_pos < tempStackTop ? max_pos : tempStackTop;
2134: } // process_terminal;
2135: }
2136:
2137: private void reportError(int msgCode, int nameIndex, int leftToken,
2138: int rightToken) {
2139: reportError(msgCode, nameIndex, leftToken, rightToken, 0);
2140: }
2141:
2142: private void reportError(int msgCode, int nameIndex, int leftToken,
2143: int rightToken, int scopeNameIndex) {
2144: int lToken = (leftToken > rightToken ? rightToken : leftToken);
2145:
2146: if (lToken < rightToken) {
2147: reportSecondaryError(msgCode, nameIndex, lToken,
2148: rightToken, scopeNameIndex);
2149: } else {
2150: reportPrimaryError(msgCode, nameIndex, rightToken,
2151: scopeNameIndex);
2152: }
2153: }
2154:
2155: private void reportPrimaryError(int msgCode, int nameIndex,
2156: int token, int scopeNameIndex) {
2157: String name;
2158: if (nameIndex >= 0) {
2159: name = Parser.readableName[nameIndex];
2160: } else {
2161: name = Util.EMPTY_STRING;
2162: }
2163:
2164: int errorStart = lexStream.start(token);
2165: int errorEnd = lexStream.end(token);
2166: int currentKind = lexStream.kind(token);
2167: String errorTokenName = Parser.name[Parser.terminal_index[lexStream
2168: .kind(token)]];
2169: char[] errorTokenSource = lexStream.name(token);
2170:
2171: int addedToken = -1;
2172: if (recoveryScanner != null) {
2173: if (nameIndex >= 0) {
2174: addedToken = Parser.reverse_index[nameIndex];
2175: }
2176: }
2177: switch (msgCode) {
2178: case BEFORE_CODE:
2179: if (recoveryScanner != null) {
2180: if (addedToken > -1) {
2181: recoveryScanner.insertToken(addedToken, -1,
2182: errorStart);
2183: } else {
2184: int[] template = getNTermTemplate(-addedToken);
2185: if (template != null) {
2186: recoveryScanner.insertTokens(template, -1,
2187: errorStart);
2188: }
2189: }
2190: }
2191: if (this .reportProblem)
2192: problemReporter().parseErrorInsertBeforeToken(
2193: errorStart, errorEnd, currentKind,
2194: errorTokenSource, errorTokenName, name);
2195: break;
2196: case INSERTION_CODE:
2197: if (recoveryScanner != null) {
2198: if (addedToken > -1) {
2199: recoveryScanner.insertToken(addedToken, -1,
2200: errorEnd);
2201: } else {
2202: int[] template = getNTermTemplate(-addedToken);
2203: if (template != null) {
2204: recoveryScanner.insertTokens(template, -1,
2205: errorEnd);
2206: }
2207: }
2208: }
2209: if (this .reportProblem)
2210: problemReporter().parseErrorInsertAfterToken(
2211: errorStart, errorEnd, currentKind,
2212: errorTokenSource, errorTokenName, name);
2213: break;
2214: case DELETION_CODE:
2215: if (recoveryScanner != null) {
2216: recoveryScanner.removeTokens(errorStart, errorEnd);
2217: }
2218: if (this .reportProblem)
2219: problemReporter().parseErrorDeleteToken(errorStart,
2220: errorEnd, currentKind, errorTokenSource,
2221: errorTokenName);
2222: break;
2223: case INVALID_CODE:
2224: if (name.length() == 0) {
2225: if (recoveryScanner != null) {
2226: recoveryScanner.removeTokens(errorStart, errorEnd);
2227: }
2228: if (this .reportProblem)
2229: problemReporter().parseErrorReplaceToken(
2230: errorStart, errorEnd, currentKind,
2231: errorTokenSource, errorTokenName, name);
2232: } else {
2233: if (recoveryScanner != null) {
2234: if (addedToken > -1) {
2235: recoveryScanner.replaceTokens(addedToken,
2236: errorStart, errorEnd);
2237: } else {
2238: int[] template = getNTermTemplate(-addedToken);
2239: if (template != null) {
2240: recoveryScanner.replaceTokens(template,
2241: errorStart, errorEnd);
2242: }
2243: }
2244: }
2245: if (this .reportProblem)
2246: problemReporter().parseErrorInvalidToken(
2247: errorStart, errorEnd, currentKind,
2248: errorTokenSource, errorTokenName, name);
2249: }
2250: break;
2251: case SUBSTITUTION_CODE:
2252: if (recoveryScanner != null) {
2253: if (addedToken > -1) {
2254: recoveryScanner.replaceTokens(addedToken,
2255: errorStart, errorEnd);
2256: } else {
2257: int[] template = getNTermTemplate(-addedToken);
2258: if (template != null) {
2259: recoveryScanner.replaceTokens(template,
2260: errorStart, errorEnd);
2261: }
2262: }
2263: }
2264: if (this .reportProblem)
2265: problemReporter().parseErrorReplaceToken(errorStart,
2266: errorEnd, currentKind, errorTokenSource,
2267: errorTokenName, name);
2268: break;
2269: case SCOPE_CODE:
2270: StringBuffer buf = new StringBuffer();
2271:
2272: int[] addedTokens = null;
2273: int addedTokenCount = 0;
2274: if (this .recoveryScanner != null) {
2275: addedTokens = new int[Parser.scope_rhs.length
2276: - Parser.scope_suffix[-nameIndex]];
2277: }
2278:
2279: for (int i = Parser.scope_suffix[-nameIndex]; Parser.scope_rhs[i] != 0; i++) {
2280: buf.append(Parser.readableName[Parser.scope_rhs[i]]);
2281: if (Parser.scope_rhs[i + 1] != 0) // any more symbols to print?
2282: buf.append(' ');
2283:
2284: if (addedTokens != null) {
2285: int tmpAddedToken = Parser.reverse_index[Parser.scope_rhs[i]];
2286: if (tmpAddedToken > -1) {
2287: int length = addedTokens.length;
2288: if (addedTokenCount == length) {
2289: System.arraycopy(addedTokens, 0,
2290: addedTokens = new int[length * 2],
2291: 0, length);
2292: }
2293: addedTokens[addedTokenCount++] = tmpAddedToken;
2294: } else {
2295: int[] template = getNTermTemplate(-tmpAddedToken);
2296: if (template != null) {
2297: for (int j = 0; j < template.length; j++) {
2298: int length = addedTokens.length;
2299: if (addedTokenCount == length) {
2300: System
2301: .arraycopy(
2302: addedTokens,
2303: 0,
2304: addedTokens = new int[length * 2],
2305: 0, length);
2306: }
2307: addedTokens[addedTokenCount++] = template[j];
2308: }
2309: } else {
2310: addedTokenCount = 0;
2311: addedTokens = null;
2312: }
2313: }
2314: }
2315: }
2316:
2317: if (addedTokenCount > 0) {
2318: System.arraycopy(addedTokens, 0,
2319: addedTokens = new int[addedTokenCount], 0,
2320: addedTokenCount);
2321:
2322: int completedToken = -1;
2323: if (scopeNameIndex != 0) {
2324: completedToken = -Parser.reverse_index[scopeNameIndex];
2325: }
2326: this .recoveryScanner.insertTokens(addedTokens,
2327: completedToken, errorEnd);
2328: }
2329:
2330: if (scopeNameIndex != 0) {
2331: if (this .reportProblem)
2332: problemReporter().parseErrorInsertToComplete(
2333: errorStart, errorEnd, buf.toString(),
2334: Parser.readableName[scopeNameIndex]);
2335: } else {
2336: if (this .reportProblem)
2337: problemReporter().parseErrorInsertToCompleteScope(
2338: errorStart, errorEnd, buf.toString());
2339: }
2340:
2341: break;
2342: case EOF_CODE:
2343: if (this .reportProblem)
2344: problemReporter().parseErrorUnexpectedEnd(errorStart,
2345: errorEnd);
2346: break;
2347: case MERGE_CODE:
2348: if (recoveryScanner != null) {
2349: if (addedToken > -1) {
2350: recoveryScanner.replaceTokens(addedToken,
2351: errorStart, errorEnd);
2352: } else {
2353: int[] template = getNTermTemplate(-addedToken);
2354: if (template != null) {
2355: recoveryScanner.replaceTokens(template,
2356: errorStart, errorEnd);
2357: }
2358: }
2359: }
2360: if (this .reportProblem)
2361: problemReporter().parseErrorMergeTokens(errorStart,
2362: errorEnd, name);
2363: break;
2364: case MISPLACED_CODE:
2365: if (recoveryScanner != null) {
2366: recoveryScanner.removeTokens(errorStart, errorEnd);
2367: }
2368: if (this .reportProblem)
2369: problemReporter().parseErrorMisplacedConstruct(
2370: errorStart, errorEnd);
2371: break;
2372: default:
2373: if (name.length() == 0) {
2374: if (recoveryScanner != null) {
2375: recoveryScanner.removeTokens(errorStart, errorEnd);
2376: }
2377: if (this .reportProblem)
2378: problemReporter().parseErrorNoSuggestion(
2379: errorStart, errorEnd, currentKind,
2380: errorTokenSource, errorTokenName);
2381: } else {
2382: if (recoveryScanner != null) {
2383: if (addedToken > -1) {
2384: recoveryScanner.replaceTokens(addedToken,
2385: errorStart, errorEnd);
2386: } else {
2387: int[] template = getNTermTemplate(-addedToken);
2388: if (template != null) {
2389: recoveryScanner.replaceTokens(template,
2390: errorStart, errorEnd);
2391: }
2392: }
2393: }
2394: if (this .reportProblem)
2395: problemReporter().parseErrorReplaceToken(
2396: errorStart, errorEnd, currentKind,
2397: errorTokenSource, errorTokenName, name);
2398: }
2399: break;
2400: }
2401: }
2402:
2403: private void reportSecondaryError(int msgCode, int nameIndex,
2404: int leftToken, int rightToken, int scopeNameIndex) {
2405: String name;
2406: if (nameIndex >= 0) {
2407: name = Parser.readableName[nameIndex];
2408: } else {
2409: name = Util.EMPTY_STRING;
2410: }
2411:
2412: int errorStart = -1;
2413: if (lexStream.isInsideStream(leftToken)) {
2414: if (leftToken == 0) {
2415: errorStart = lexStream.start(leftToken + 1);
2416: } else {
2417: errorStart = lexStream.start(leftToken);
2418: }
2419: } else {
2420: if (leftToken == errorToken) {
2421: errorStart = errorTokenStart;
2422: } else {
2423: for (int i = 0; i <= stateStackTop; i++) {
2424: if (locationStack[i] == leftToken) {
2425: errorStart = locationStartStack[i];
2426: }
2427: }
2428: }
2429: if (errorStart == -1) {
2430: errorStart = lexStream.start(rightToken);
2431: }
2432: }
2433: int errorEnd = lexStream.end(rightToken);
2434:
2435: int addedToken = -1;
2436: if (recoveryScanner != null) {
2437: if (nameIndex >= 0) {
2438: addedToken = Parser.reverse_index[nameIndex];
2439: }
2440: }
2441:
2442: switch (msgCode) {
2443: case MISPLACED_CODE:
2444: if (recoveryScanner != null) {
2445: recoveryScanner.removeTokens(errorStart, errorEnd);
2446: }
2447: if (this .reportProblem)
2448: problemReporter().parseErrorMisplacedConstruct(
2449: errorStart, errorEnd);
2450: break;
2451: case SCOPE_CODE:
2452: // error start is on the last token start
2453: errorStart = lexStream.start(rightToken);
2454:
2455: StringBuffer buf = new StringBuffer();
2456:
2457: int[] addedTokens = null;
2458: int addedTokenCount = 0;
2459: if (this .recoveryScanner != null) {
2460: addedTokens = new int[Parser.scope_rhs.length
2461: - Parser.scope_suffix[-nameIndex]];
2462: }
2463:
2464: for (int i = Parser.scope_suffix[-nameIndex]; Parser.scope_rhs[i] != 0; i++) {
2465:
2466: buf.append(Parser.readableName[Parser.scope_rhs[i]]);
2467: if (Parser.scope_rhs[i + 1] != 0)
2468: buf.append(' ');
2469:
2470: if (addedTokens != null) {
2471: int tmpAddedToken = Parser.reverse_index[Parser.scope_rhs[i]];
2472: if (tmpAddedToken > -1) {
2473: int length = addedTokens.length;
2474: if (addedTokenCount == length) {
2475: System.arraycopy(addedTokens, 0,
2476: addedTokens = new int[length * 2],
2477: 0, length);
2478: }
2479: addedTokens[addedTokenCount++] = tmpAddedToken;
2480: } else {
2481: int[] template = getNTermTemplate(-tmpAddedToken);
2482: if (template != null) {
2483: for (int j = 0; j < template.length; j++) {
2484: int length = addedTokens.length;
2485: if (addedTokenCount == length) {
2486: System
2487: .arraycopy(
2488: addedTokens,
2489: 0,
2490: addedTokens = new int[length * 2],
2491: 0, length);
2492: }
2493: addedTokens[addedTokenCount++] = template[j];
2494: }
2495: } else {
2496: addedTokenCount = 0;
2497: addedTokens = null;
2498: }
2499: }
2500: }
2501: }
2502: if (addedTokenCount > 0) {
2503: System.arraycopy(addedTokens, 0,
2504: addedTokens = new int[addedTokenCount], 0,
2505: addedTokenCount);
2506: int completedToken = -1;
2507: if (scopeNameIndex != 0) {
2508: completedToken = -Parser.reverse_index[scopeNameIndex];
2509: }
2510: this .recoveryScanner.insertTokens(addedTokens,
2511: completedToken, errorEnd);
2512: }
2513: if (scopeNameIndex != 0) {
2514: if (this .reportProblem)
2515: problemReporter().parseErrorInsertToComplete(
2516: errorStart, errorEnd, buf.toString(),
2517: Parser.readableName[scopeNameIndex]);
2518: } else {
2519: if (this .reportProblem)
2520: problemReporter().parseErrorInsertToCompletePhrase(
2521: errorStart, errorEnd, buf.toString());
2522: }
2523: break;
2524: case MERGE_CODE:
2525: if (recoveryScanner != null) {
2526: if (addedToken > -1) {
2527: recoveryScanner.replaceTokens(addedToken,
2528: errorStart, errorEnd);
2529: } else {
2530: int[] template = getNTermTemplate(-addedToken);
2531: if (template != null) {
2532: recoveryScanner.replaceTokens(template,
2533: errorStart, errorEnd);
2534: }
2535: }
2536: }
2537: if (this .reportProblem)
2538: problemReporter().parseErrorMergeTokens(errorStart,
2539: errorEnd, name);
2540: break;
2541: case DELETION_CODE:
2542: if (recoveryScanner != null) {
2543: recoveryScanner.removeTokens(errorStart, errorEnd);
2544: }
2545: if (this .reportProblem)
2546: problemReporter().parseErrorDeleteTokens(errorStart,
2547: errorEnd);
2548: break;
2549: default:
2550: if (name.length() == 0) {
2551: if (recoveryScanner != null) {
2552: recoveryScanner.removeTokens(errorStart, errorEnd);
2553: }
2554: if (this .reportProblem)
2555: problemReporter().parseErrorNoSuggestionForTokens(
2556: errorStart, errorEnd);
2557: } else {
2558: if (recoveryScanner != null) {
2559: if (addedToken > -1) {
2560: recoveryScanner.replaceTokens(addedToken,
2561: errorStart, errorEnd);
2562: } else {
2563: int[] template = getNTermTemplate(-addedToken);
2564: if (template != null) {
2565: recoveryScanner.replaceTokens(template,
2566: errorStart, errorEnd);
2567: }
2568: }
2569: }
2570: if (this .reportProblem)
2571: problemReporter().parseErrorReplaceTokens(
2572: errorStart, errorEnd, name);
2573: }
2574: }
2575: return;
2576: }
2577:
2578: private int[] getNTermTemplate(int sym) {
2579: int templateIndex = Parser.recovery_templates_index[sym];
2580: if (templateIndex > 0) {
2581: int[] result = new int[Parser.recovery_templates.length];
2582: int count = 0;
2583: for (int j = templateIndex; Parser.recovery_templates[j] != 0; j++) {
2584: result[count++] = Parser.recovery_templates[j];
2585: }
2586: System.arraycopy(result, 0, result = new int[count], 0,
2587: count);
2588: return result;
2589: } else {
2590: return null;
2591: }
2592: }
2593:
2594: public String toString() {
2595: StringBuffer res = new StringBuffer();
2596:
2597: res.append(lexStream.toString());
2598:
2599: return res.toString();
2600: }
2601: }
|