1 /*******************************************************************************
2 * Copyright (c) 2000, 2004 IBM Corporation and others.
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Common Public License v1.0
5 * which accompanies this distribution, and is available at
6 * http://www.eclipse.org/legal/cpl-v10.html
9 * IBM Corporation - initial API and implementation
10 *******************************************************************************/
11 package org.eclipse.jdt.internal.compiler.parser.diagnose;
13 import org.eclipse.jdt.core.compiler.CharOperation;
14 import org.eclipse.jdt.internal.compiler.parser.Parser;
15 import org.eclipse.jdt.internal.compiler.parser.ParserBasicInformation;
16 import org.eclipse.jdt.internal.compiler.parser.TerminalTokens;
17 import org.eclipse.jdt.internal.compiler.problem.ProblemReporter;
19 public class DiagnoseParser implements ParserBasicInformation, TerminalTokens {
20 private static final boolean DEBUG = false;
22 private static final String EMPTY_STRING = ""; //$NON-NLS-1$
23 private static final int STACK_INCREMENT = 256;
25 // private static final int ERROR_CODE = 1;
26 private static final int BEFORE_CODE = 2;
27 private static final int INSERTION_CODE = 3;
28 private static final int INVALID_CODE = 4;
29 private static final int SUBSTITUTION_CODE = 5;
30 private static final int DELETION_CODE = 6;
31 private static final int MERGE_CODE = 7;
32 private static final int MISPLACED_CODE = 8;
33 private static final int SCOPE_CODE = 9;
34 private static final int SECONDARY_CODE = 10;
35 private static final int EOF_CODE = 11;
37 private static final int BUFF_UBOUND = 31;
38 private static final int BUFF_SIZE = 32;
39 private static final int MAX_DISTANCE = 30;
40 private static final int MIN_DISTANCE = 3;
42 private LexStream lexStream;
43 private int errorToken;
44 private int errorTokenStart;
46 private int currentToken = 0;
48 private int stackLength;
49 private int stateStackTop;
52 private int[] locationStack;
53 private int[] locationStartStack;
55 private int tempStackTop;
56 private int[] tempStack;
58 private int prevStackTop;
59 private int[] prevStack;
60 private int nextStackTop;
61 private int[] nextStack;
63 private int scopeStackTop;
64 private int[] scopeIndex;
65 private int[] scopePosition;
67 int[] list = new int[NUM_SYMBOLS + 1];
68 int[] buffer = new int[BUFF_SIZE];
70 private static final int NIL = -1;
74 StateInfo[] statePool;
76 private Parser parser;
78 private class RepairCandidate {
82 public RepairCandidate(){
88 private class PrimaryRepairInfo {
90 public int misspellIndex;
92 public int bufferPosition;
95 public PrimaryRepairInfo(){
97 this.misspellIndex = 0;
99 this.bufferPosition = 0;
103 public PrimaryRepairInfo copy(){
104 PrimaryRepairInfo c = new PrimaryRepairInfo();
105 c.distance = this.distance;
106 c.misspellIndex = this.misspellIndex;
108 c.bufferPosition = this .bufferPosition;
109 c.symbol = this.symbol;
115 private class SecondaryRepairInfo {
118 public int bufferPosition;
119 public int stackPosition;
120 public int numDeletions;
123 boolean recoveryOnNextStack;
126 private class StateInfo {
130 public StateInfo(int state, int next){
136 public DiagnoseParser(Parser parser, int firstToken, int start, int end) {
137 this(parser, firstToken, start, end, new int[0], new int[0], new int[0]);
140 public DiagnoseParser(Parser parser, int firstToken, int start, int end, int[] intervalStartToSkip, int[] intervalEndToSkip, int[] intervalFlagsToSkip) {
141 this.parser = parser;
142 this.lexStream = new LexStream(BUFF_SIZE, parser.scanner, intervalStartToSkip, intervalEndToSkip, intervalFlagsToSkip, firstToken, start, end);
145 private ProblemReporter problemReporter(){
146 return parser.problemReporter();
149 private void reallocateStacks() {
150 int old_stack_length = stackLength;
152 stackLength += STACK_INCREMENT;
154 if(old_stack_length == 0){
155 stack = new int[stackLength];
156 locationStack = new int[stackLength];
157 locationStartStack = new int[stackLength];
158 tempStack = new int[stackLength];
159 prevStack = new int[stackLength];
160 nextStack = new int[stackLength];
161 scopeIndex = new int[stackLength];
162 scopePosition = new int[stackLength];
164 System.arraycopy(stack, 0, stack = new int[stackLength], 0, old_stack_length);
165 System.arraycopy(locationStack, 0, locationStack = new int[stackLength], 0, old_stack_length);
166 System.arraycopy(locationStartStack, 0, locationStartStack = new int[stackLength], 0, old_stack_length);
167 System.arraycopy(tempStack, 0, tempStack = new int[stackLength], 0, old_stack_length);
168 System.arraycopy(prevStack, 0, prevStack = new int[stackLength], 0, old_stack_length);
169 System.arraycopy(nextStack, 0, nextStack = new int[stackLength], 0, old_stack_length);
170 System.arraycopy(scopeIndex, 0, scopeIndex = new int[stackLength], 0, old_stack_length);
171 System.arraycopy(scopePosition, 0, scopePosition = new int[stackLength], 0, old_stack_length);
177 public void diagnoseParse() {
180 currentToken = lexStream.getToken();
185 int act = START_STATE;
193 stack[stateStackTop] = act;
195 int tok = lexStream.kind(currentToken);
196 locationStack[stateStackTop] = currentToken;
197 locationStartStack[stateStackTop] = lexStream.start(currentToken);
199 boolean forceRecoveryAfterLBracketMissing = false;
200 // int forceRecoveryToken = -1;
203 // Process a terminal
207 // Synchronize state stacks and update the location stack
216 tempStackTop = stateStackTop - 1;
217 for (int i = 0; i <= stateStackTop; i++)
218 tempStack[i] = stack[i];
220 act = Parser.tAction(act, tok);
222 // When a reduce action is encountered, we compute all REDUCE
223 // and associated goto actions induced by the current token.
224 // Eventually, a SHIFT, SHIFT-REDUCE, ACCEPT or ERROR action is
227 while (act <= NUM_RULES) {
229 tempStackTop -= (Parser.rhs[act]-1);
230 act = Parser.ntAction(tempStack[tempStackTop], Parser.lhs[act]);
231 } while(act <= NUM_RULES);
233 // ... Update the maximum useful position of the
234 // (STATE_)STACK, push goto state into stack, and
235 // compute next action on current symbol ...
237 if (tempStackTop + 1 >= stackLength)
239 pos = pos < tempStackTop ? pos : tempStackTop;
240 tempStack[tempStackTop + 1] = act;
241 act = Parser.tAction(act, tok);
245 // At this point, we have a shift, shift-reduce, accept or error
246 // action. STACK contains the configuration of the state stack
247 // prior to executing any action on curtok. next_stack contains
248 // the configuration of the state stack after executing all
249 // reduce actions induced by curtok. The variable pos indicates
250 // the highest position in STACK that is still useful after the
251 // reductions are executed.
253 while(act > ERROR_ACTION || act < ACCEPT_ACTION) { // SHIFT-REDUCE action or SHIFT action ?
254 nextStackTop = tempStackTop + 1;
255 for (int i = next_pos + 1; i <= nextStackTop; i++)
256 nextStack[i] = tempStack[i];
258 for (int i = pos + 1; i <= nextStackTop; i++) {
259 locationStack[i] = locationStack[stateStackTop];
260 locationStartStack[i] = locationStartStack[stateStackTop];
264 // If we have a shift-reduce, process it as well as
265 // the goto-reduce actions that follow it.
267 if (act > ERROR_ACTION) {
270 nextStackTop -= (Parser.rhs[act]-1);
271 act = Parser.ntAction(nextStack[nextStackTop], Parser.lhs[act]);
272 } while(act <= NUM_RULES);
273 pos = pos < nextStackTop ? pos : nextStackTop;
276 if (nextStackTop + 1 >= stackLength)
279 tempStackTop = nextStackTop;
280 nextStack[++nextStackTop] = act;
281 next_pos = nextStackTop;
284 // Simulate the parser through the next token without
285 // destroying STACK or next_stack.
287 currentToken = lexStream.getToken();
288 tok = lexStream.kind(currentToken);
289 act = Parser.tAction(act, tok);
290 while(act <= NUM_RULES) {
292 // ... Process all goto-reduce actions following
293 // reduction, until a goto action is computed ...
296 int lhs_symbol = Parser.lhs[act];
298 System.out.println(Parser.name[Parser.non_terminal_index[lhs_symbol]]);
300 tempStackTop -= (Parser.rhs[act]-1);
301 act = (tempStackTop > next_pos
302 ? tempStack[tempStackTop]
303 : nextStack[tempStackTop]);
304 act = Parser.ntAction(act, lhs_symbol);
305 } while(act <= NUM_RULES);
308 // ... Update the maximum useful position of the
309 // (STATE_)STACK, push GOTO state into stack, and
310 // compute next action on current symbol ...
312 if (tempStackTop + 1 >= stackLength)
315 next_pos = next_pos < tempStackTop ? next_pos : tempStackTop;
316 tempStack[tempStackTop + 1] = act;
317 act = Parser.tAction(act, tok);
320 // if((tok != TokenNameRBRACE || (forceRecoveryToken != currentToken && (lexStream.flags(currentToken) & LexStream.LBRACE_MISSING) != 0))
321 // && (lexStream.flags(currentToken) & LexStream.IS_AFTER_JUMP) !=0) {
322 // act = ERROR_ACTION;
323 // if(forceRecoveryToken != currentToken
324 // && (lexStream.flags(currentToken) & LexStream.LBRACE_MISSING) != 0) {
325 // forceRecoveryAfterLBracketMissing = true;
326 // forceRecoveryToken = currentToken;
331 // No error was detected, Read next token into
332 // PREVTOK element, advance CURTOK pointer and
335 if (act != ERROR_ACTION) {
336 prevStackTop = stateStackTop;
337 for (int i = prev_pos + 1; i <= prevStackTop; i++)
338 prevStack[i] = stack[i];
341 stateStackTop = nextStackTop;
342 for (int i = pos + 1; i <= stateStackTop; i++)
343 stack[i] = nextStack[i];
344 locationStack[stateStackTop] = currentToken;
345 locationStartStack[stateStackTop] = lexStream.start(currentToken);
351 // At this stage, either we have an ACCEPT or an ERROR
354 if (act == ERROR_ACTION) {
356 // An error was detected.
358 RepairCandidate candidate = errorRecovery(currentToken, forceRecoveryAfterLBracketMissing);
360 forceRecoveryAfterLBracketMissing = false;
362 if(parser.reportOnlyOneSyntaxError) {
366 if(this.parser.problemReporter().options.maxProblemsPerUnit < this.parser.compilationUnit.compilationResult.problemCount) {
370 act = stack[stateStackTop];
373 // If the recovery was successful on a nonterminal candidate,
374 // parse through that candidate and "read" the next token.
376 if (candidate.symbol == 0) {
378 } else if (candidate.symbol > NT_OFFSET) {
379 int lhs_symbol = candidate.symbol - NT_OFFSET;
381 System.out.println(Parser.name[Parser.non_terminal_index[lhs_symbol]]);
383 act = Parser.ntAction(act, lhs_symbol);
384 while(act <= NUM_RULES) {
385 stateStackTop -= (Parser.rhs[act]-1);
386 act = Parser.ntAction(stack[stateStackTop], Parser.lhs[act]);
388 stack[++stateStackTop] = act;
389 currentToken = lexStream.getToken();
390 tok = lexStream.kind(currentToken);
391 locationStack[stateStackTop] = currentToken;
392 locationStartStack[stateStackTop] = lexStream.start(currentToken);
394 tok = candidate.symbol;
395 locationStack[stateStackTop] = candidate.location;
396 locationStartStack[stateStackTop] = lexStream.start(candidate.location);
399 } while (act != ACCEPT_ACTION);
405 // This routine is invoked when an error is encountered. It
406 // tries to diagnose the error and recover from it. If it is
407 // successful, the state stack, the current token and the buffer
408 // are readjusted; i.e., after a successful recovery,
409 // state_stack_top points to the location in the state stack
410 // that contains the state on which to recover; curtok
411 // identifies the symbol on which to recover.
413 // Up to three configurations may be available when this routine
414 // is invoked. PREV_STACK may contain the sequence of states
415 // preceding any action on prevtok, STACK always contains the
416 // sequence of states preceding any action on curtok, and
417 // NEXT_STACK may contain the sequence of states preceding any
418 // action on the successor of curtok.
420 private RepairCandidate errorRecovery(int error_token, boolean forcedError) {
421 this.errorToken = error_token;
422 this.errorTokenStart = lexStream.start(error_token);
424 int prevtok = lexStream.previous(error_token);
425 int prevtokKind = lexStream.kind(prevtok);
428 int name_index = Parser.terminal_index[TokenNameLBRACE];
430 reportError(INSERTION_CODE, name_index, prevtok, prevtok);
432 RepairCandidate candidate = new RepairCandidate();
433 candidate.symbol = TokenNameLBRACE;
434 candidate.location = error_token;
435 lexStream.reset(error_token);
437 stateStackTop = nextStackTop;
438 for (int j = 0; j <= stateStackTop; j++) {
439 stack[j] = nextStack[j];
441 locationStack[stateStackTop] = error_token;
442 locationStartStack[stateStackTop] = lexStream.start(error_token);
448 // Try primary phase recoveries. If not successful, try secondary
449 // phase recoveries. If not successful and we are at end of the
450 // file, we issue the end-of-file error and quit. Otherwise, ...
452 RepairCandidate candidate = primaryPhase(error_token);
453 if (candidate.symbol != 0) {
457 candidate = secondaryPhase(error_token);
458 if (candidate.symbol != 0) {
462 if (lexStream.kind(error_token) == EOFT_SYMBOL) {
463 reportError(EOF_CODE,
464 Parser.terminal_index[EOFT_SYMBOL],
467 candidate.symbol = 0;
468 candidate.location = error_token;
473 // At this point, primary and (initial attempt at) secondary
474 // recovery did not work. We will now get into "panic mode" and
475 // keep trying secondary phase recoveries until we either find
476 // a successful recovery or have consumed the remaining input
479 while(lexStream.kind(buffer[BUFF_UBOUND]) != EOFT_SYMBOL) {
480 candidate = secondaryPhase(buffer[MAX_DISTANCE - MIN_DISTANCE + 2]);
481 if (candidate.symbol != 0) {
487 // We reached the end of the file while panicking. Delete all
488 // remaining tokens in the input.
491 for (i = BUFF_UBOUND; lexStream.kind(buffer[i]) == EOFT_SYMBOL; i--){/*empty*/}
493 reportError(DELETION_CODE,
494 Parser.terminal_index[prevtokKind],//Parser.terminal_index[lexStream.kind(prevtok)],
498 candidate.symbol = 0;
499 candidate.location = buffer[i];
505 // This function tries primary and scope recovery on each
506 // available configuration. If a successful recovery is found
507 // and no secondary phase recovery can do better, a diagnosis is
508 // issued, the configuration is updated and the function returns
509 // "true". Otherwise, it returns "false".
511 private RepairCandidate primaryPhase(int error_token) {
512 PrimaryRepairInfo repair = new PrimaryRepairInfo();
513 RepairCandidate candidate = new RepairCandidate();
516 // Initialize the buffer.
518 int i = (nextStackTop >= 0 ? 3 : 2);
519 buffer[i] = error_token;
521 for (int j = i; j > 0; j--)
522 buffer[j - 1] = lexStream.previous(buffer[j]);
524 for (int k = i + 1; k < BUFF_SIZE; k++)
525 buffer[k] = lexStream.next(buffer[k - 1]);
528 // If NEXT_STACK_TOP > 0 then the parse was successful on CURTOK
529 // and the error was detected on the successor of CURTOK. In
530 // that case, first check whether or not primary recovery is
531 // possible on next_stack ...
533 if (nextStackTop >= 0) {
534 repair.bufferPosition = 3;
535 repair = checkPrimaryDistance(nextStack, nextStackTop, repair);
539 // ... Next, try primary recovery on the current token...
541 PrimaryRepairInfo new_repair = repair.copy();
543 new_repair.bufferPosition = 2;
544 new_repair = checkPrimaryDistance(stack, stateStackTop, new_repair);
545 if (new_repair.distance > repair.distance || new_repair.misspellIndex > repair.misspellIndex) {
550 // Finally, if prev_stack_top >= 0 then try primary recovery on
551 // the prev_stack configuration.
554 if (prevStackTop >= 0) {
555 new_repair = repair.copy();
556 new_repair.bufferPosition = 1;
557 new_repair = checkPrimaryDistance(prevStack,prevStackTop, new_repair);
558 if (new_repair.distance > repair.distance || new_repair.misspellIndex > repair.misspellIndex) {
564 // Before accepting the best primary phase recovery obtained,
565 // ensure that we cannot do better with a similar secondary
568 if (nextStackTop >= 0) {// next_stack available
569 if (secondaryCheck(nextStack,nextStackTop,3,repair.distance)) {
573 else if (secondaryCheck(stack, stateStackTop, 2, repair.distance)) {
578 // First, adjust distance if the recovery is on the error token;
579 // it is important that the adjustment be made here and not at
580 // each primary trial to prevent the distance tests from being
581 // biased in favor of deferred recoveries which have access to
582 // more input tokens...
584 repair.distance = repair.distance - repair.bufferPosition + 1;
587 // ...Next, adjust the distance if the recovery is a deletion or
588 // (some form of) substitution...
590 if (repair.code == INVALID_CODE ||
591 repair.code == DELETION_CODE ||
592 repair.code == SUBSTITUTION_CODE ||
593 repair.code == MERGE_CODE) {
598 // ... After adjustment, check if the most successful primary
599 // recovery can be applied. If not, continue with more radical
602 if (repair.distance < MIN_DISTANCE) {
607 // When processing an insertion error, if the token preceeding
608 // the error token is not available, we change the repair code
609 // into a BEFORE_CODE to instruct the reporting routine that it
610 // indicates that the repair symbol should be inserted before
613 if (repair.code == INSERTION_CODE) {
614 if (buffer[repair.bufferPosition - 1] == 0) {
615 repair.code = BEFORE_CODE;
620 // Select the proper sequence of states on which to recover,
621 // update stack accordingly and call diagnostic routine.
623 if (repair.bufferPosition == 1) {
624 stateStackTop = prevStackTop;
625 for (int j = 0; j <= stateStackTop; j++) {
626 stack[j] = prevStack[j];
628 } else if (nextStackTop >= 0 && repair.bufferPosition >= 3) {
629 stateStackTop = nextStackTop;
630 for (int j = 0; j <= stateStackTop; j++) {
631 stack[j] = nextStack[j];
633 locationStack[stateStackTop] = buffer[3];
634 locationStartStack[stateStackTop] = lexStream.start(buffer[3]);
637 return primaryDiagnosis(repair);
642 // This function checks whether or not a given state has a
643 // candidate, whose string representaion is a merging of the two
644 // tokens at positions buffer_position and buffer_position+1 in
645 // the buffer. If so, it returns the candidate in question;
646 // otherwise it returns 0.
648 private int mergeCandidate(int state, int buffer_position) {
649 char[] name1 = lexStream.name(buffer[buffer_position]);
650 char[] name2 = lexStream.name(buffer[buffer_position + 1]);
652 int len = name1.length + name2.length;
654 char[] str = CharOperation.concat(name1, name2);
656 for (int k = Parser.asi(state); Parser.asr[k] != 0; k++) {
657 int l = Parser.terminal_index[Parser.asr[k]];
659 if (len == Parser.name[l].length()) {
660 char[] name = Parser.name[l].toCharArray();
662 if (CharOperation.equals(str, name, false)) {
663 return Parser.asr[k];
673 // This procedure takes as arguments a parsing configuration
674 // consisting of a state stack (stack and stack_top) and a fixed
675 // number of input tokens (starting at buffer_position) in the
676 // input BUFFER; and some reference arguments: repair_code,
677 // distance, misspell_index, candidate, and stack_position
678 // which it sets based on the best possible recovery that it
679 // finds in the given configuration. The effectiveness of a
680 // a repair is judged based on two criteria:
682 // 1) the number of tokens that can be parsed after the repair
683 // is applied: distance.
684 // 2) how close to perfection is the candidate that is chosen:
686 // When this procedure is entered, distance, misspell_index and
687 // repair_code are assumed to be initialized.
689 private PrimaryRepairInfo checkPrimaryDistance(int stck[], int stack_top, PrimaryRepairInfo repair) {
690 int i, j, k, next_state, max_pos, act, root, symbol, tok;
693 // First, try scope and manual recovery.
695 PrimaryRepairInfo scope_repair = scopeTrial(stck, stack_top, repair.copy());
696 if (scope_repair.distance > repair.distance)
697 repair = scope_repair;
700 // Next, try merging the error token with its successor.
702 if(buffer[repair.bufferPosition] != 0 && buffer[repair.bufferPosition + 1] != 0) {// do not merge the first token
703 symbol = mergeCandidate(stck[stack_top], repair.bufferPosition);
705 j = parseCheck(stck, stack_top, symbol, repair.bufferPosition+2);
706 if ((j > repair.distance) || (j == repair.distance && repair.misspellIndex < 10)) {
707 repair.misspellIndex = 10;
708 repair.symbol = symbol;
710 repair.code = MERGE_CODE;
716 // Next, try deletion of the error token.
721 lexStream.kind(buffer[repair.bufferPosition + 1]),
722 repair.bufferPosition + 2);
723 if (lexStream.kind(buffer[repair.bufferPosition]) == EOLT_SYMBOL &&
724 lexStream.afterEol(buffer[repair.bufferPosition+1])) {
729 if (j > repair.distance || (j == repair.distance && k > repair.misspellIndex)) {
730 repair.misspellIndex = k;
731 repair.code = DELETION_CODE;
736 // Update the error configuration by simulating all reduce and
737 // goto actions induced by the error token. Then assign the top
738 // most state of the new configuration to next_state.
740 next_state = stck[stack_top];
742 tempStackTop = stack_top - 1;
744 tok = lexStream.kind(buffer[repair.bufferPosition]);
745 lexStream.reset(buffer[repair.bufferPosition + 1]);
746 act = Parser.tAction(next_state, tok);
747 while(act <= NUM_RULES) {
749 tempStackTop -= (Parser.rhs[act]-1);
750 symbol = Parser.lhs[act];
751 act = (tempStackTop > max_pos
752 ? tempStack[tempStackTop]
753 : stck[tempStackTop]);
754 act = Parser.ntAction(act, symbol);
755 } while(act <= NUM_RULES);
756 max_pos = max_pos < tempStackTop ? max_pos : tempStackTop;
757 tempStack[tempStackTop + 1] = act;
759 act = Parser.tAction(next_state, tok);
763 // Next, place the list of candidates in proper order.
766 for (i = Parser.asi(next_state); Parser.asr[i] != 0; i++) {
767 symbol = Parser.asr[i];
768 if (symbol != EOFT_SYMBOL && symbol != ERROR_SYMBOL) {
770 list[symbol] = symbol;
772 list[symbol] = list[root];
779 if (stck[stack_top] != next_state) {
780 for (i = Parser.asi(stck[stack_top]); Parser.asr[i] != 0; i++) {
781 symbol = Parser.asr[i];
782 if (symbol != EOFT_SYMBOL && symbol != ERROR_SYMBOL && list[symbol] == 0) {
784 list[symbol] = symbol;
786 list[symbol] = list[root];
799 // Next, try insertion for each possible candidate available in
800 // the current state, except EOFT and ERROR_SYMBOL.
804 if (symbol == EOLT_SYMBOL && lexStream.afterEol(buffer[repair.bufferPosition])) {
809 j = parseCheck(stck, stack_top, symbol, repair.bufferPosition);
810 if (j > repair.distance) {
811 repair.misspellIndex = k;
813 repair.symbol = symbol;
814 repair.code = INSERTION_CODE;
815 } else if (j == repair.distance && k > repair.misspellIndex) {
816 repair.misspellIndex = k;
818 repair.symbol = symbol;
819 repair.code = INSERTION_CODE;
820 } else if (j == repair.distance && k == repair.misspellIndex && isBetterSymbol(symbol, repair.symbol)) {
821 repair.misspellIndex = k;
823 repair.symbol = symbol;
824 repair.code = INSERTION_CODE;
827 symbol = list[symbol];
831 // Next, Try substitution for each possible candidate available
832 // in the current state, except EOFT and ERROR_SYMBOL.
836 if(buffer[repair.bufferPosition] != 0) {// do not replace the first token
838 if (symbol == EOLT_SYMBOL && lexStream.afterEol(buffer[repair.bufferPosition+1])) {
841 k = misspell(symbol, buffer[repair.bufferPosition]);
843 j = parseCheck(stck, stack_top, symbol, repair.bufferPosition+1);
844 if (j > repair.distance) {
845 repair.misspellIndex = k;
847 repair.symbol = symbol;
848 repair.code = SUBSTITUTION_CODE;
849 } else if (j == repair.distance && k > repair.misspellIndex) {
850 repair.misspellIndex = k;
851 repair.symbol = symbol;
852 repair.code = SUBSTITUTION_CODE;
853 } else if (j == repair.distance && k > repair.misspellIndex && isBetterSymbol(symbol, repair.symbol)) {
854 repair.misspellIndex = k;
855 repair.symbol = symbol;
856 repair.code = SUBSTITUTION_CODE;
859 symbol = list[symbol];
860 list[i] = 0; // reset element
866 // Next, we try to insert a nonterminal candidate in front of the
867 // error token, or substituting a nonterminal candidate for the
868 // error token. Precedence is given to insertion.
870 for (i = Parser.nasi(stck[stack_top]); Parser.nasr[i] != 0; i++) {
871 symbol = Parser.nasr[i] + NT_OFFSET;
872 j = parseCheck(stck, stack_top, symbol, repair.bufferPosition+1);
873 if (j > repair.distance) {
874 repair.misspellIndex = 0;
876 repair.symbol = symbol;
877 repair.code = INVALID_CODE;
880 j = parseCheck(stck, stack_top, symbol, repair.bufferPosition);
881 if ((j > repair.distance) || (j == repair.distance && repair.code == INVALID_CODE)) {
882 repair.misspellIndex = 0;
884 repair.symbol = symbol;
885 repair.code = INSERTION_CODE;
894 // This procedure is invoked to issue a diagnostic message and
895 // adjust the input buffer. The recovery in question is either
896 // the insertion of one or more scopes, the merging of the error
897 // token with its successor, the deletion of the error token,
898 // the insertion of a single token in front of the error token
899 // or the substitution of another token for the error token.
901 private RepairCandidate primaryDiagnosis(PrimaryRepairInfo repair) {
907 int prevtok = buffer[repair.bufferPosition - 1];
908 int curtok = buffer[repair.bufferPosition];
910 switch(repair.code) {
913 if (repair.symbol > NT_OFFSET)
914 name_index = getNtermIndex(stack[stateStackTop],
916 repair.bufferPosition);
917 else name_index = getTermIndex(stack,
920 repair.bufferPosition);
922 int t = (repair.code == INSERTION_CODE ? prevtok : curtok);
923 reportError(repair.code, name_index, t, t);
927 name_index = getNtermIndex(stack[stateStackTop],
929 repair.bufferPosition + 1);
930 reportError(repair.code, name_index, curtok, curtok);
933 case SUBSTITUTION_CODE: {
934 if (repair.misspellIndex >= 6)
935 name_index = Parser.terminal_index[repair.symbol];
938 name_index = getTermIndex(stack, stateStackTop,
940 repair.bufferPosition + 1);
941 if (name_index != Parser.terminal_index[repair.symbol])
942 repair.code = INVALID_CODE;
944 reportError(repair.code, name_index, curtok, curtok);
948 reportError(repair.code,
949 Parser.terminal_index[repair.symbol],
951 lexStream.next(curtok));
955 for (int i = 0; i < scopeStackTop; i++) {
956 reportError(repair.code,
958 locationStack[scopePosition[i]],
960 Parser.non_terminal_index[Parser.scope_lhs[scopeIndex[i]]]);
963 repair.symbol = Parser.scope_lhs[scopeIndex[scopeStackTop]] + NT_OFFSET;
964 stateStackTop = scopePosition[scopeStackTop];
965 reportError(repair.code,
966 -scopeIndex[scopeStackTop],
967 locationStack[scopePosition[scopeStackTop]],
969 getNtermIndex(stack[stateStackTop],
971 repair.bufferPosition)
975 default: {// deletion
976 reportError(repair.code, Parser.terminal_index[ERROR_SYMBOL], curtok, curtok);
983 RepairCandidate candidate = new RepairCandidate();
984 switch (repair.code) {
988 candidate.symbol = repair.symbol;
989 candidate.location = buffer[repair.bufferPosition];
990 lexStream.reset(buffer[repair.bufferPosition]);
994 case SUBSTITUTION_CODE: {
995 candidate.symbol = repair.symbol;
996 candidate.location = buffer[repair.bufferPosition];
997 lexStream.reset(buffer[repair.bufferPosition + 1]);
1001 candidate.symbol = repair.symbol;
1002 candidate.location = buffer[repair.bufferPosition];
1003 lexStream.reset(buffer[repair.bufferPosition + 2]);
1006 default: {// deletion
1007 candidate.location = buffer[repair.bufferPosition + 1];
1009 lexStream.kind(buffer[repair.bufferPosition + 1]);
1010 lexStream.reset(buffer[repair.bufferPosition + 2]);
1020 // This function takes as parameter an integer STACK_TOP that
1021 // points to a STACK element containing the state on which a
1022 // primary recovery will be made; the terminal candidate on which
1023 // to recover; and an integer: buffer_position, which points to
1024 // the position of the next input token in the BUFFER. The
1025 // parser is simulated until a shift (or shift-reduce) action
1026 // is computed on the candidate. Then we proceed to compute the
1027 // the name index of the highest level nonterminal that can
1028 // directly or indirectly produce the candidate.
1030 private int getTermIndex(int stck[], int stack_top, int tok, int buffer_position) {
1032 // Initialize stack index of temp_stack and initialize maximum
1033 // position of state stack that is still useful.
1035 int act = stck[stack_top],
1036 max_pos = stack_top,
1037 highest_symbol = tok;
1039 tempStackTop = stack_top - 1;
1042 // Compute all reduce and associated actions induced by the
1043 // candidate until a SHIFT or SHIFT-REDUCE is computed. ERROR
1044 // and ACCEPT actions cannot be computed on the candidate in
1045 // this context, since we know that it is suitable for recovery.
1047 lexStream.reset(buffer[buffer_position]);
1048 act = Parser.tAction(act, tok);
1049 while(act <= NUM_RULES) {
1051 // Process all goto-reduce actions following reduction,
1052 // until a goto action is computed ...
1055 tempStackTop -= (Parser.rhs[act]-1);
1056 int lhs_symbol = Parser.lhs[act];
1057 act = (tempStackTop > max_pos
1058 ? tempStack[tempStackTop]
1059 : stck[tempStackTop]);
1060 act = Parser.ntAction(act, lhs_symbol);
1061 } while(act <= NUM_RULES);
1064 // Compute new maximum useful position of (STATE_)stack,
1065 // push goto state into the stack, and compute next
1066 // action on candidate ...
1068 max_pos = max_pos < tempStackTop ? max_pos : tempStackTop;
1069 tempStack[tempStackTop + 1] = act;
1070 act = Parser.tAction(act, tok);
1074 // At this stage, we have simulated all actions induced by the
1075 // candidate and we are ready to shift or shift-reduce it. First,
1076 // set tok and next_ptr appropriately and identify the candidate
1077 // as the initial highest_symbol. If a shift action was computed
1078 // on the candidate, update the stack and compute the next
1079 // action. Next, simulate all actions possible on the next input
1080 // token until we either have to shift it or are about to reduce
1081 // below the initial starting point in the stack (indicated by
1082 // max_pos as computed in the previous loop). At that point,
1083 // return the highest_symbol computed.
1085 tempStackTop++; // adjust top of stack to reflect last goto
1086 // next move is shift or shift-reduce.
1087 int threshold = tempStackTop;
1089 tok = lexStream.kind(buffer[buffer_position]);
1090 lexStream.reset(buffer[buffer_position + 1]);
1092 if (act > ERROR_ACTION) { // shift-reduce on candidate?
1093 act -= ERROR_ACTION;
1095 tempStack[tempStackTop + 1] = act;
1096 act = Parser.tAction(act, tok);
1099 while(act <= NUM_RULES) {
1101 // Process all goto-reduce actions following reduction,
1102 // until a goto action is computed ...
1105 tempStackTop -= (Parser.rhs[act]-1);
1107 if (tempStackTop < threshold) {
1108 return (highest_symbol > NT_OFFSET
1109 ? Parser.non_terminal_index[highest_symbol - NT_OFFSET]
1110 : Parser.terminal_index[highest_symbol]);
1113 int lhs_symbol = Parser.lhs[act];
1114 if (tempStackTop == threshold)
1115 highest_symbol = lhs_symbol + NT_OFFSET;
1116 act = (tempStackTop > max_pos
1117 ? tempStack[tempStackTop]
1118 : stck[tempStackTop]);
1119 act = Parser.ntAction(act, lhs_symbol);
1120 } while(act <= NUM_RULES);
1122 tempStack[tempStackTop + 1] = act;
1123 act = Parser.tAction(act, tok);
1126 return (highest_symbol > NT_OFFSET
1127 ? Parser.non_terminal_index[highest_symbol - NT_OFFSET]
1128 : Parser.terminal_index[highest_symbol]);
1132 // This function takes as parameter a starting state number:
1133 // start, a nonterminal symbol, A (candidate), and an integer,
1134 // buffer_position, which points to the position of the next
1135 // input token in the BUFFER.
1136 // It returns the highest level non-terminal B such that
1137 // B =>*rm A. I.e., there does not exists a nonterminal C such
1138 // that C =>+rm B. (Recall that for an LALR(k) grammar if
1139 // C =>+rm B, it cannot be the case that B =>+rm C)
1141 private int getNtermIndex(int start, int sym, int buffer_position) {
1142 int highest_symbol = sym - NT_OFFSET,
1143 tok = lexStream.kind(buffer[buffer_position]);
1144 lexStream.reset(buffer[buffer_position + 1]);
1147 // Initialize stack index of temp_stack and initialize maximum
1148 // position of state stack that is still useful.
1151 tempStack[tempStackTop] = start;
1153 int act = Parser.ntAction(start, highest_symbol);
1154 if (act > NUM_RULES) { // goto action?
1155 tempStack[tempStackTop + 1] = act;
1156 act = Parser.tAction(act, tok);
1159 while(act <= NUM_RULES) {
1161 // Process all goto-reduce actions following reduction,
1162 // until a goto action is computed ...
1165 tempStackTop -= (Parser.rhs[act]-1);
1166 if (tempStackTop < 0)
1167 return Parser.non_terminal_index[highest_symbol];
1168 if (tempStackTop == 0)
1169 highest_symbol = Parser.lhs[act];
1170 act = Parser.ntAction(tempStack[tempStackTop], Parser.lhs[act]);
1171 } while(act <= NUM_RULES);
1172 tempStack[tempStackTop + 1] = act;
1173 act = Parser.tAction(act, tok);
1176 return Parser.non_terminal_index[highest_symbol];
1179 private boolean isBetterSymbol(int symbol, int actualSymbol) {
1180 // switch (actualSymbol) {
1181 // case TokenNameinterface :
1182 // if(symbol == TokenNameclass) {
1191 // Check whether or not there is a high probability that a
1192 // given string is a misspelling of another.
1193 // Certain singleton symbols (such as ":" and ";") are also
1194 // considered to be misspelling of each other.
1196 private int misspell(int sym, int tok) {
1202 char[] name = Parser.name[Parser.terminal_index[sym]].toCharArray();
1203 int n = name.length;
1204 char[] s1 = new char[n + 1];
1205 for (int k = 0; k < n; k++) {
1207 s1[k] = Character.toLowerCase(c);
1214 char[] tokenName = lexStream.name(tok);
1215 int len = tokenName.length;
1216 int m = len < MAX_NAME_LENGTH ? len : MAX_NAME_LENGTH;
1217 char[] s2 = new char[m + 1];
1218 for (int k = 0; k < m; k++) {
1219 char c = tokenName[k];
1220 s2[k] = Character.toLowerCase(c);
1225 // Singleton mispellings:
1236 if (n == 1 && m == 1) {
1237 if ((s1[0] == ';' && s2[0] == ',') ||
1238 (s1[0] == ',' && s2[0] == ';') ||
1239 (s1[0] == ';' && s2[0] == ':') ||
1240 (s1[0] == ':' && s2[0] == ';') ||
1241 (s1[0] == '.' && s2[0] == ',') ||
1242 (s1[0] == ',' && s2[0] == '.') ||
1243 (s1[0] == '\'' && s2[0] == '\"') ||
1244 (s1[0] == '\"' && s2[0] == '\'')) {
1250 // Scan the two strings. Increment "match" count for each match.
1251 // When a transposition is encountered, increase "match" count
1252 // by two but count it as an error. When a typo is found, skip
1253 // it and count it as an error. Otherwise we have a mismatch; if
1254 // one of the strings is longer, increment its index, otherwise,
1255 // increment both indices and continue.
1257 // This algorithm is an adaptation of a boolean misspelling
1258 // algorithm proposed by Juergen Uhl.
1261 int prefix_length = 0;
1266 while ((i < n) && (j < m)) {
1267 if (s1[i] == s2[j]) {
1271 if (num_errors == 0) {
1274 } else if (s1[i+1] == s2[j] && s1[i] == s2[j+1]) {
1279 } else if (s1[i+1] == s2[j+1]) {
1284 if ((n - i) > (m - j)) {
1286 } else if ((m - j) > (n - i)) {
1299 if (num_errors > ((n < m ? n : m) / 6 + 1))
1300 count = prefix_length;
1302 return(count * 10 / ((n < len ? len : n) + num_errors));
1305 private PrimaryRepairInfo scopeTrial(int stck[], int stack_top, PrimaryRepairInfo repair) {
1306 stateSeen = new int[stackLength];
1307 for (int i = 0; i < stackLength; i++)
1311 statePool = new StateInfo[stackLength];
1313 scopeTrialCheck(stck, stack_top, repair, 0);
1318 repair.code = SCOPE_CODE;
1319 repair.misspellIndex = 10;
1324 private void scopeTrialCheck(int stck[], int stack_top, PrimaryRepairInfo repair, int indx) {
1325 if(indx > 20) return; // avoid too much recursive call to improve performance
1327 int act = stck[stack_top];
1329 for (int i = stateSeen[stack_top]; i != NIL; i = statePool[i].next) {
1330 if (statePool[i].state == act) return;
1333 int old_state_pool_top = statePoolTop++;
1334 if(statePoolTop >= statePool.length) {
1335 System.arraycopy(statePool, 0, statePool = new StateInfo[statePoolTop * 2], 0, statePoolTop);
1338 statePool[old_state_pool_top] = new StateInfo(act, stateSeen[stack_top]);
1339 stateSeen[stack_top] = old_state_pool_top;
1341 for (int i = 0; i < SCOPE_SIZE; i++) {
1343 // Use the scope lookahead symbol to force all reductions
1344 // inducible by that symbol.
1346 act = stck[stack_top];
1347 tempStackTop = stack_top - 1;
1348 int max_pos = stack_top;
1349 int tok = Parser.scope_la[i];
1350 lexStream.reset(buffer[repair.bufferPosition]);
1351 act = Parser.tAction(act, tok);
1352 while(act <= NUM_RULES) {
1354 // ... Process all goto-reduce actions following
1355 // reduction, until a goto action is computed ...
1358 tempStackTop -= (Parser.rhs[act]-1);
1359 int lhs_symbol = Parser.lhs[act];
1360 act = (tempStackTop > max_pos
1361 ? tempStack[tempStackTop]
1362 : stck[tempStackTop]);
1363 act = Parser.ntAction(act, lhs_symbol);
1364 } while(act <= NUM_RULES);
1365 if (tempStackTop + 1 >= stackLength)
1367 max_pos = max_pos < tempStackTop ? max_pos : tempStackTop;
1368 tempStack[tempStackTop + 1] = act;
1369 act = Parser.tAction(act, tok);
1373 // If the lookahead symbol is parsable, then we check
1374 // whether or not we have a match between the scope
1375 // prefix and the transition symbols corresponding to
1376 // the states on top of the stack.
1378 if (act != ERROR_ACTION) {
1380 k = Parser.scope_prefix[i];
1381 for (j = tempStackTop + 1;
1382 j >= (max_pos + 1) &&
1383 Parser.in_symbol(tempStack[j]) == Parser.scope_rhs[k]; j--) {
1388 j >= 1 && Parser.in_symbol(stck[j]) == Parser.scope_rhs[k];
1394 // If the prefix matches, check whether the state
1395 // newly exposed on top of the stack, (after the
1396 // corresponding prefix states are popped from the
1397 // stack), is in the set of "source states" for the
1398 // scope in question and that it is at a position
1399 // below the threshold indicated by MARKED_POS.
1401 int marked_pos = (max_pos < stack_top ? max_pos + 1 : stack_top);
1402 if (Parser.scope_rhs[k] == 0 && j < marked_pos) { // match?
1403 int stack_position = j;
1404 for (j = Parser.scope_state_set[i];
1405 stck[stack_position] != Parser.scope_state[j] &&
1406 Parser.scope_state[j] != 0;
1409 // If the top state is valid for scope recovery,
1410 // the left-hand side of the scope is used as
1411 // starting symbol and we calculate how far the
1412 // parser can advance within the forward context
1413 // after parsing the left-hand symbol.
1415 if (Parser.scope_state[j] != 0) { // state was found
1416 int previous_distance = repair.distance;
1417 int distance = parseCheck(stck,
1419 Parser.scope_lhs[i]+NT_OFFSET,
1420 repair.bufferPosition);
1422 // if the recovery is not successful, we
1423 // update the stack with all actions induced
1424 // by the left-hand symbol, and recursively
1425 // call SCOPE_TRIAL_CHECK to try again.
1426 // Otherwise, the recovery is successful. If
1427 // the new distance is greater than the
1428 // initial SCOPE_DISTANCE, we update
1429 // SCOPE_DISTANCE and set scope_stack_top to INDX
1430 // to indicate the number of scopes that are
1431 // to be applied for a succesful recovery.
1432 // NOTE that this procedure cannot get into
1433 // an infinite loop, since each prefix match
1434 // is guaranteed to take us to a lower point
1435 // within the stack.
1437 if ((distance - repair.bufferPosition + 1) < MIN_DISTANCE) {
1438 int top = stack_position;
1439 act = Parser.ntAction(stck[top], Parser.scope_lhs[i]);
1440 while(act <= NUM_RULES) {
1441 top -= (Parser.rhs[act]-1);
1442 act = Parser.ntAction(stck[top], Parser.lhs[act]);
1447 act = stck[top]; // save
1448 stck[top] = j; // swap
1449 scopeTrialCheck(stck, top, repair, indx+1);
1450 stck[top] = act; // restore
1451 } else if (distance > repair.distance) {
1452 scopeStackTop = indx;
1453 repair.distance = distance;
1456 if (lexStream.kind(buffer[repair.bufferPosition]) == EOFT_SYMBOL &&
1457 repair.distance == previous_distance) {
1458 scopeStackTop = indx;
1459 repair.distance = MAX_DISTANCE;
1463 // If this scope recovery has beaten the
1464 // previous distance, then we have found a
1465 // better recovery (or this recovery is one
1466 // of a list of scope recoveries). Record
1467 // its information at the proper location
1468 // (INDX) in SCOPE_INDEX and SCOPE_STACK.
1470 if (repair.distance > previous_distance) {
1471 scopeIndex[indx] = i;
1472 scopePosition[indx] = stack_position;
1481 // This function computes the ParseCheck distance for the best
1482 // possible secondary recovery for a given configuration that
1483 // either deletes none or only one symbol in the forward context.
1484 // If the recovery found is more effective than the best primary
1485 // recovery previously computed, then the function returns true.
1486 // Only misplacement, scope and manual recoveries are attempted;
1487 // simple insertion or substitution of a nonterminal are tried
1488 // in CHECK_PRIMARY_DISTANCE as part of primary recovery.
1490 private boolean secondaryCheck(int stck[], int stack_top, int buffer_position, int distance) {
1493 for (top = stack_top - 1; top >= 0; top--) {
1494 j = parseCheck(stck, top,
1495 lexStream.kind(buffer[buffer_position]),
1496 buffer_position + 1);
1497 if (((j - buffer_position + 1) > MIN_DISTANCE) && (j > distance))
1501 PrimaryRepairInfo repair = new PrimaryRepairInfo();
1502 repair.bufferPosition = buffer_position + 1;
1503 repair.distance = distance;
1504 repair = scopeTrial(stck, stack_top, repair);
1505 if ((repair.distance - buffer_position) > MIN_DISTANCE && repair.distance > distance)
1512 // Secondary_phase is a boolean function that checks whether or
1513 // not some form of secondary recovery is applicable to one of
1514 // the error configurations. First, if "next_stack" is available,
1515 // misplacement and secondary recoveries are attempted on it.
1516 // Then, in any case, these recoveries are attempted on "stack".
1517 // If a successful recovery is found, a diagnosis is issued, the
1518 // configuration is updated and the function returns "true".
1519 // Otherwise, the function returns false.
1521 private RepairCandidate secondaryPhase(int error_token) {
1522 SecondaryRepairInfo repair = new SecondaryRepairInfo();
1523 SecondaryRepairInfo misplaced = new SecondaryRepairInfo();
1525 RepairCandidate candidate = new RepairCandidate();
1528 int next_last_index = 0;
1531 candidate.symbol = 0;
1534 repair.distance = 0;
1535 repair.recoveryOnNextStack = false;
1537 misplaced.distance = 0;
1538 misplaced.recoveryOnNextStack = false;
1541 // If the next_stack is available, try misplaced and secondary
1542 // recovery on it first.
1544 if (nextStackTop >= 0) {
1547 buffer[2] = error_token;
1548 buffer[1] = lexStream.previous(buffer[2]);
1549 buffer[0] = lexStream.previous(buffer[1]);
1551 for (k = 3; k < BUFF_UBOUND; k++)
1552 buffer[k] = lexStream.next(buffer[k - 1]);
1554 buffer[BUFF_UBOUND] = lexStream.badtoken();// elmt not available
1557 // If we are at the end of the input stream, compute the
1558 // index position of the first EOFT symbol (last useful
1561 for (next_last_index = MAX_DISTANCE - 1;
1562 next_last_index >= 1 &&
1563 lexStream.kind(buffer[next_last_index]) == EOFT_SYMBOL;
1564 next_last_index--){/*empty*/}
1565 next_last_index = next_last_index + 1;
1567 save_location = locationStack[nextStackTop];
1568 int save_location_start = locationStartStack[nextStackTop];
1569 locationStack[nextStackTop] = buffer[2];
1570 locationStartStack[nextStackTop] = lexStream.start(buffer[2]);
1571 misplaced.numDeletions = nextStackTop;
1572 misplaced = misplacementRecovery(nextStack, nextStackTop,
1575 if (misplaced.recoveryOnNextStack)
1576 misplaced.distance++;
1578 repair.numDeletions = nextStackTop + BUFF_UBOUND;
1579 repair = secondaryRecovery(nextStack, nextStackTop,
1582 if (repair.recoveryOnNextStack)
1585 locationStack[nextStackTop] = save_location;
1586 locationStartStack[nextStackTop] = save_location_start;
1587 } else { // next_stack not available, initialize ...
1588 misplaced.numDeletions = stateStackTop;
1589 repair.numDeletions = stateStackTop + BUFF_UBOUND;
1593 // Try secondary recovery on the "stack" configuration.
1595 buffer[3] = error_token;
1597 buffer[2] = lexStream.previous(buffer[3]);
1598 buffer[1] = lexStream.previous(buffer[2]);
1599 buffer[0] = lexStream.previous(buffer[1]);
1601 for (k = 4; k < BUFF_SIZE; k++)
1602 buffer[k] = lexStream.next(buffer[k - 1]);
1604 for (last_index = MAX_DISTANCE - 1;
1605 last_index >= 1 && lexStream.kind(buffer[last_index]) == EOFT_SYMBOL;
1606 last_index--){/*empty*/}
1609 misplaced = misplacementRecovery(stack, stateStackTop,
1613 repair = secondaryRecovery(stack, stateStackTop,
1614 last_index, repair, false);
1617 // If a successful misplaced recovery was found, compare it with
1618 // the most successful secondary recovery. If the misplaced
1619 // recovery either deletes fewer symbols or parse-checks further
1620 // then it is chosen.
1622 if (misplaced.distance > MIN_DISTANCE) {
1623 if (misplaced.numDeletions <= repair.numDeletions ||
1624 (misplaced.distance - misplaced.numDeletions) >=
1625 (repair.distance - repair.numDeletions)) {
1626 repair.code = MISPLACED_CODE;
1627 repair.stackPosition = misplaced.stackPosition;
1628 repair.bufferPosition = 2;
1629 repair.numDeletions = misplaced.numDeletions;
1630 repair.distance = misplaced.distance;
1631 repair.recoveryOnNextStack = misplaced.recoveryOnNextStack;
1636 // If the successful recovery was on next_stack, update: stack,
1637 // buffer, location_stack and last_index.
1639 if (repair.recoveryOnNextStack) {
1640 stateStackTop = nextStackTop;
1641 for (i = 0; i <= stateStackTop; i++)
1642 stack[i] = nextStack[i];
1644 buffer[2] = error_token;
1645 buffer[1] = lexStream.previous(buffer[2]);
1646 buffer[0] = lexStream.previous(buffer[1]);
1648 for (k = 3; k < BUFF_UBOUND; k++)
1649 buffer[k] = lexStream.next(buffer[k - 1]);
1651 buffer[BUFF_UBOUND] = lexStream.badtoken();// elmt not available
1653 locationStack[nextStackTop] = buffer[2];
1654 locationStartStack[nextStackTop] = lexStream.start(buffer[2]);
1655 last_index = next_last_index;
1659 // Next, try scope recoveries after deletion of one, two, three,
1660 // four ... buffer_position tokens from the input stream.
1662 if (repair.code == SECONDARY_CODE || repair.code == DELETION_CODE) {
1663 PrimaryRepairInfo scope_repair = new PrimaryRepairInfo();
1665 scope_repair.distance = 0;
1666 for (scope_repair.bufferPosition = 2;
1667 scope_repair.bufferPosition <= repair.bufferPosition &&
1668 repair.code != SCOPE_CODE; scope_repair.bufferPosition++) {
1669 scope_repair = scopeTrial(stack, stateStackTop, scope_repair);
1670 j = (scope_repair.distance == MAX_DISTANCE
1672 : scope_repair.distance);
1673 k = scope_repair.bufferPosition - 1;
1674 if ((j - k) > MIN_DISTANCE && (j - k) > (repair.distance - repair.numDeletions)) {
1675 repair.code = SCOPE_CODE;
1676 i = scopeIndex[scopeStackTop]; // upper bound
1677 repair.symbol = Parser.scope_lhs[i] + NT_OFFSET;
1678 repair.stackPosition = stateStackTop;
1679 repair.bufferPosition = scope_repair.bufferPosition;
1685 // If no successful recovery is found and we have reached the
1686 // end of the file, check whether or not scope recovery is
1687 // applicable at the end of the file after discarding some
1690 if (repair.code == 0 && lexStream.kind(buffer[last_index]) == EOFT_SYMBOL) {
1691 PrimaryRepairInfo scope_repair = new PrimaryRepairInfo();
1693 scope_repair.bufferPosition = last_index;
1694 scope_repair.distance = 0;
1695 for (top = stateStackTop;
1696 top >= 0 && repair.code == 0; top--)
1698 scope_repair = scopeTrial(stack, top, scope_repair);
1699 if (scope_repair.distance > 0)
1701 repair.code = SCOPE_CODE;
1702 i = scopeIndex[scopeStackTop]; // upper bound
1703 repair.symbol = Parser.scope_lhs[i] + NT_OFFSET;
1704 repair.stackPosition = top;
1705 repair.bufferPosition = scope_repair.bufferPosition;
1711 // If a successful repair was not found, quit! Otherwise, issue
1712 // diagnosis and adjust configuration...
1714 if (repair.code == 0)
1717 secondaryDiagnosis(repair);
1720 // Update buffer based on number of elements that are deleted.
1722 switch(repair.code) {
1723 case MISPLACED_CODE:
1724 candidate.location = buffer[2];
1725 candidate.symbol = lexStream.kind(buffer[2]);
1726 lexStream.reset(lexStream.next(buffer[2]));
1731 candidate.location = buffer[repair.bufferPosition];
1733 lexStream.kind(buffer[repair.bufferPosition]);
1734 lexStream.reset(lexStream.next(buffer[repair.bufferPosition]));
1738 default: // SCOPE_CODE || SECONDARY_CODE
1739 candidate.symbol = repair.symbol;
1740 candidate.location = buffer[repair.bufferPosition];
1741 lexStream.reset(buffer[repair.bufferPosition]);
1751 // This boolean function checks whether or not a given
1752 // configuration yields a better misplacement recovery than
1753 // the best misplacement recovery computed previously.
1755 private SecondaryRepairInfo misplacementRecovery(int stck[], int stack_top, int last_index, SecondaryRepairInfo repair, boolean stack_flag) {
1756 int previous_loc = buffer[2];
1757 int stack_deletions = 0;
1759 for (int top = stack_top - 1; top >= 0; top--) {
1760 if (locationStack[top] < previous_loc) {
1763 previous_loc = locationStack[top];
1765 int j = parseCheck(stck, top, lexStream.kind(buffer[2]), 3);
1766 if (j == MAX_DISTANCE) {
1769 if ((j > MIN_DISTANCE) && (j - stack_deletions) > (repair.distance - repair.numDeletions)) {
1770 repair.stackPosition = top;
1771 repair.distance = j;
1772 repair.numDeletions = stack_deletions;
1773 repair.recoveryOnNextStack = stack_flag;
1782 // This boolean function checks whether or not a given
1783 // configuration yields a better secondary recovery than the
1784 // best misplacement recovery computed previously.
1786 private SecondaryRepairInfo secondaryRecovery(int stck[],int stack_top, int last_index, SecondaryRepairInfo repair, boolean stack_flag) {
1788 int stack_deletions = 0;
1790 previous_loc = buffer[2];
1791 for (int top = stack_top; top >= 0 && repair.numDeletions >= stack_deletions; top--) {
1792 if (locationStack[top] < previous_loc) {
1795 previous_loc = locationStack[top];
1798 i <= (last_index - MIN_DISTANCE + 1) &&
1799 (repair.numDeletions >= (stack_deletions + i - 1)); i++) {
1800 int j = parseCheck(stck, top, lexStream.kind(buffer[i]), i + 1);
1802 if (j == MAX_DISTANCE) {
1805 if ((j - i + 1) > MIN_DISTANCE) {
1806 int k = stack_deletions + i - 1;
1807 if ((k < repair.numDeletions) ||
1808 (j - k) > (repair.distance - repair.numDeletions) ||
1809 ((repair.code == SECONDARY_CODE) && (j - k) == (repair.distance - repair.numDeletions))) {
1810 repair.code = DELETION_CODE;
1811 repair.distance = j;
1812 repair.stackPosition = top;
1813 repair.bufferPosition = i;
1814 repair.numDeletions = k;
1815 repair.recoveryOnNextStack = stack_flag;
1819 for (int l = Parser.nasi(stck[top]); l >= 0 && Parser.nasr[l] != 0; l++) {
1820 int symbol = Parser.nasr[l] + NT_OFFSET;
1821 j = parseCheck(stck, top, symbol, i);
1822 if (j == MAX_DISTANCE) {
1825 if ((j - i + 1) > MIN_DISTANCE) {
1826 int k = stack_deletions + i - 1;
1827 if (k < repair.numDeletions || (j - k) > (repair.distance - repair.numDeletions)) {
1828 repair.code = SECONDARY_CODE;
1829 repair.symbol = symbol;
1830 repair.distance = j;
1831 repair.stackPosition = top;
1832 repair.bufferPosition = i;
1833 repair.numDeletions = k;
1834 repair.recoveryOnNextStack = stack_flag;
1846 // This procedure is invoked to issue a secondary diagnosis and
1847 // adjust the input buffer. The recovery in question is either
1848 // an automatic scope recovery, a manual scope recovery, a
1849 // secondary substitution or a secondary deletion.
1851 private void secondaryDiagnosis(SecondaryRepairInfo repair) {
1852 switch(repair.code) {
1854 if (repair.stackPosition < stateStackTop) {
1855 reportError(DELETION_CODE,
1856 Parser.terminal_index[ERROR_SYMBOL],
1857 locationStack[repair.stackPosition],
1860 for (int i = 0; i < scopeStackTop; i++) {
1861 reportError(SCOPE_CODE,
1863 locationStack[scopePosition[i]],
1865 Parser.non_terminal_index[Parser.scope_lhs[scopeIndex[i]]]);
1868 repair.symbol = Parser.scope_lhs[scopeIndex[scopeStackTop]] + NT_OFFSET;
1869 stateStackTop = scopePosition[scopeStackTop];
1870 reportError(SCOPE_CODE,
1871 -scopeIndex[scopeStackTop],
1872 locationStack[scopePosition[scopeStackTop]],
1874 getNtermIndex(stack[stateStackTop],
1876 repair.bufferPosition)
1881 reportError(repair.code,
1882 (repair.code == SECONDARY_CODE
1883 ? getNtermIndex(stack[repair.stackPosition],
1885 repair.bufferPosition)
1886 : Parser.terminal_index[ERROR_SYMBOL]),
1887 locationStack[repair.stackPosition],
1888 buffer[repair.bufferPosition - 1]);
1889 stateStackTop = repair.stackPosition;
1898 // Try to parse until first_token and all tokens in BUFFER have
1899 // been consumed, or an error is encountered. Return the number
1900 // of tokens that were expended before the parse blocked.
1902 private int parseCheck(int stck[], int stack_top, int first_token, int buffer_position) {
1909 // Initialize pointer for temp_stack and initialize maximum
1910 // position of state stack that is still useful.
1912 act = stck[stack_top];
1913 if (first_token > NT_OFFSET) {
1914 tempStackTop = stack_top;
1915 max_pos = stack_top;
1916 indx = buffer_position;
1917 ct = lexStream.kind(buffer[indx]);
1918 lexStream.reset(lexStream.next(buffer[indx]));
1919 int lhs_symbol = first_token - NT_OFFSET;
1920 act = Parser.ntAction(act, lhs_symbol);
1921 if (act <= NUM_RULES) {
1923 tempStackTop -= (Parser.rhs[act]-1);
1924 lhs_symbol = Parser.lhs[act];
1925 act = (tempStackTop > max_pos
1926 ? tempStack[tempStackTop]
1927 : stck[tempStackTop]);
1928 act = Parser.ntAction(act, lhs_symbol);
1929 } while(act <= NUM_RULES);
1931 max_pos = max_pos < tempStackTop ? max_pos : tempStackTop;
1934 tempStackTop = stack_top - 1;
1935 max_pos = tempStackTop;
1936 indx = buffer_position - 1;
1938 lexStream.reset(buffer[buffer_position]);
1941 process_terminal: for (;;) {
1942 if (++tempStackTop >= stackLength) // Stack overflow!!!
1944 tempStack[tempStackTop] = act;
1946 act = Parser.tAction(act, ct);
1948 if (act <= NUM_RULES) { // reduce action
1950 } else if (act < ACCEPT_ACTION || // shift action
1951 act > ERROR_ACTION) { // shift-reduce action
1952 if (indx == MAX_DISTANCE)
1955 ct = lexStream.kind(buffer[indx]);
1956 lexStream.reset(lexStream.next(buffer[indx]));
1957 if (act > ERROR_ACTION) {
1958 act -= ERROR_ACTION;
1960 continue process_terminal;
1962 } else if (act == ACCEPT_ACTION) { // accept action
1963 return MAX_DISTANCE;
1965 return indx; // error action
1968 process_non_terminal:
1970 tempStackTop -= (Parser.rhs[act]-1);
1971 int lhs_symbol = Parser.lhs[act];
1972 act = (tempStackTop > max_pos
1973 ? tempStack[tempStackTop]
1974 : stck[tempStackTop]);
1975 act = Parser.ntAction(act, lhs_symbol);
1976 } while(act <= NUM_RULES);
1978 max_pos = max_pos < tempStackTop ? max_pos : tempStackTop;
1979 } // process_terminal;
1981 private void reportError(int msgCode, int nameIndex, int leftToken, int rightToken) {
1982 reportError(msgCode, nameIndex, leftToken, rightToken, 0);
1985 private void reportError(int msgCode, int nameIndex, int leftToken, int rightToken, int scopeNameIndex) {
1986 int lToken = (leftToken > rightToken ? rightToken : leftToken);
1988 if (lToken < rightToken) {
1989 reportSecondaryError(msgCode, nameIndex, lToken, rightToken, scopeNameIndex);
1991 reportPrimaryError(msgCode, nameIndex, rightToken, scopeNameIndex);
1994 private void reportPrimaryError(int msgCode, int nameIndex, int token, int scopeNameIndex) {
1996 if (nameIndex >= 0) {
1997 name = Parser.readableName[nameIndex];
1999 name = EMPTY_STRING;
2002 int errorStart = lexStream.start(token);
2003 int errorEnd = lexStream.end(token);
2004 int currentKind = lexStream.kind(token);
2005 String errorTokenName = Parser.name[Parser.terminal_index[lexStream.kind(token)]];
2006 char[] errorTokenSource = lexStream.name(token);
2010 problemReporter().parseErrorInsertBeforeToken(
2018 case INSERTION_CODE:
2019 problemReporter().parseErrorInsertAfterToken(
2028 problemReporter().parseErrorDeleteToken(
2036 if (name.length() == 0) {
2037 problemReporter().parseErrorReplaceToken(
2045 problemReporter().parseErrorInvalidToken(
2054 case SUBSTITUTION_CODE:
2055 problemReporter().parseErrorReplaceToken(
2064 StringBuffer buf = new StringBuffer();
2065 for (int i = Parser.scope_suffix[- nameIndex]; Parser.scope_rhs[i] != 0; i++) {
2066 buf.append(Parser.readableName[Parser.scope_rhs[i]]);
2067 if (Parser.scope_rhs[i + 1] != 0) // any more symbols to print?
2072 if (scopeNameIndex != 0) {
2073 problemReporter().parseErrorInsertToComplete(
2077 Parser.readableName[scopeNameIndex]);
2079 problemReporter().parseErrorInsertToCompleteScope(
2087 problemReporter().parseErrorUnexpectedEnd(
2092 problemReporter().parseErrorMergeTokens(
2097 case MISPLACED_CODE:
2098 problemReporter().parseErrorMisplacedConstruct(
2103 if (name.length() == 0) {
2104 problemReporter().parseErrorNoSuggestion(
2111 problemReporter().parseErrorReplaceToken(
2123 private void reportSecondaryError(int msgCode, int nameIndex, int leftToken, int rightToken, int scopeNameIndex) {
2125 if (nameIndex >= 0) {
2126 name = Parser.readableName[nameIndex];
2128 name = EMPTY_STRING;
2131 int errorStart = -1;
2132 if(lexStream.isInsideStream(leftToken)) {
2133 if(leftToken == 0) {
2134 errorStart = lexStream.start(leftToken + 1);
2136 errorStart = lexStream.start(leftToken);
2139 if(leftToken == errorToken) {
2140 errorStart = errorTokenStart;
2142 for (int i = 0; i <= stateStackTop; i++) {
2143 if(locationStack[i] == leftToken) {
2144 errorStart = locationStartStack[i];
2148 if(errorStart == -1) {
2149 errorStart = lexStream.start(rightToken);
2152 int errorEnd = lexStream.end(rightToken);
2155 case MISPLACED_CODE:
2156 problemReporter().parseErrorMisplacedConstruct(
2161 // error start is on the last token start
2162 errorStart = lexStream.start(rightToken);
2164 StringBuffer buf = new StringBuffer();
2165 for (int i = Parser.scope_suffix[- nameIndex]; Parser.scope_rhs[i] != 0; i++) {
2166 buf.append(Parser.readableName[Parser.scope_rhs[i]]);
2167 if (Parser.scope_rhs[i+1] != 0)
2170 if (scopeNameIndex != 0) {
2171 problemReporter().parseErrorInsertToComplete(
2175 Parser.readableName[scopeNameIndex]);
2177 problemReporter().parseErrorInsertToCompletePhrase(
2184 problemReporter().parseErrorMergeTokens(
2190 problemReporter().parseErrorDeleteTokens(
2195 if (name.length() == 0) {
2196 problemReporter().parseErrorNoSuggestionForTokens(
2200 problemReporter().parseErrorReplaceTokens(
2209 public String toString() {
2210 StringBuffer res = new StringBuffer();
2212 res.append(lexStream.toString());
2214 return res.toString();