Mismatched input error: inaccurate list of expected tokens

[hackathlete]

It appears that the list of expected tokens can sometimes be inaccurate when a mismatched input is detected.

Following grammar can be used to reproduce the issue:

grammar ErrorReportingTest;

file
  : (assign)+ EOF
  ;
assign
  : aggregate LE expr SEMI
  ;
aggregate
  : LPAREN ( el_others | ( el+=expr ( COMMA el+=expr )* ( COMMA el_others )? ) ) RPAREN
  ;
el_others
  : OTHERS ARROW expr
  ;
expr
  : '-' expr
  | expr '*' expr
  | expr ('+'|'-') expr
  | ID
  | INT
  | '(' expr ')'
  ;

OTHERS : 'others';
LE     : '<=';
ARROW  : '=>';
COMMA  : ',';
SEMI   : ';';
LPAREN : '(';
RPAREN : ')';
INT    : [0-9]+;
ID     : LETTER (LETTER | [0-9])*;
fragment
LETTER : [a-zA-Z];
WS     : [ \t\n\r]+ -> skip;
SL_COMMENT : '//' .*? '\n' -> skip;

The following examples show valid code lines that illustrate the language described:

(t, e, r) <= 0;
(others => 9) <= 9;
(t, e, r, others => 9) <= 0;

If there is a "mismachted input" error in the code, then the expected tokens are reported in the error message.

Expected
The correct error message is displayed for the incomplete code snippet "(t, e, r)" as the only possible token is '<='.

(t, e, r)
line 2:0 mismatched input '<EOF>' expecting '<='

Unexpected
From my point of view, the error message for the incomplete code snippets "(others => 9)" and "(t, e, r, others => 9)" shall be the same as above. But, the expected token list contains other tokens and the '<=' is missing.

(others => 9)
line 2:0 mismatched input '<EOF>' expecting {'-', '*', '+', ')'}
(t, e, r, others => 9)
line 2:0 mismatched input '<EOF>' expecting {'-', '*', '+', ')'}

The RecognitionException gives back different offendingState numbers. I would expect that the offendingState is equal for all shown code lines.
To me, it seems as there may be a problem in the generated parser. However, has anybody a hint how to fix (work around) this issue in my grammar?

ANTLR4 version: v4.13.2
Target language: Java

[kaby76]

Reproduced.

The behavior varies with target. The expected token list is inconsistent for Dart, Java, PHP, Rust. The expected token listis only <= for Antlr4ng, Cpp, CSharp, Go, JavaScript, Python3, TypeScript. out.txt. Why are they different?

The tokens listed in the error message are computed by ATN.NextToken(). This fuction is called in RecoverInline(), using a constructor that depends on state information. Please refer to the CSharp and Java code.

antlr4/runtime/CSharp/src/DefaultErrorStrategy.cs

Line 574 in 594cf95

throw new InputMismatchException(recognizer);

)

antlr4/runtime/Java/src/org/antlr/v4/runtime/DefaultErrorStrategy.java

Line 485 in 594cf95

e = new InputMismatchException(recognizer, nextTokensState, nextTokensContext);

For Java, the offending state is 63; for CSharp, it is 18. For Java, nextTokensContext is not null, so new InputMismatchException(recognizer, nextTokensState, nextTokensContext) is called. nextTokenState is 63, and the context is the call stack. For CSharp, this.nextTokenState is 63, but it is not used in constructing the exception via new InputMismatchException(recognizer). State 63 corresponds to an NFA state in expr. State 18 corresponds to an NFA state in assign.

The code for Java was updated with 0803c74 in #1922. But, the code for CSharp was not updated. I don't know why the change wasn't propagated to all targets at the time of the bug fix. Or, as demonstrated by this Issue, whether the change really is actually correct. It seems plausible that the computation of nextTokensContext is wrong.

You can likely write a workaround by replacing the default error recovery class with one that suits your situation.

[ericvergnaud]

@kaby76 thanks for this detailed analysis!
So what's the correct output? Java?

[kaby76]

I would think that the output should say it's missing a '<=' or even LE, but not the list of tokens {'-', '*', '+', ')'. That's because it's in Match(LE); of public AssignContext assign() { ... } where the recognition exception is thrown. It's not in expr(), so the state info just seems wrong. But, we need to review what the change in the Java code was supposed to correct.

[kaby76]

The original problem was to fix the expected lookahead for this grammar, on input baa.

grammar Simple;
member : 'a';
body: member*;
file : body EOF;
B: 'b';

Parse:

$ ./bin/Debug/net8.0/Test.exe -input baa
line 1:0 mismatched input 'b' expecting <EOF>
CSharp 0 string0 fail 0.0210393
Total Time: 0.0692547

Observe the state diagram for rule file.

The error message should not be just be expecting <EOF>, but expecting <EOF>, 'a' because the language defined by the grammar is { '', 'a', 'aa', 'aaa', 'aaaa', ... }. Normally, at the time of the throw in Match(EOF); within method file(), the expected input is defined as lookahead of the closure of state 15 (i.e., ATN.NextTokens(15)`. But, the previous rule can derive epsilon, so the lookahead from that state also considered (or we just add in the lookahead of the closure for each state in the call context. The code is almost right, but not quite.

[hackathlete]

I would think that the output should say it's missing a '<=' or even LE, but not the list of tokens {'-', '*', '+', ')'. That's because it's in Match(LE); of public AssignContext assign() { ... } where the recognition exception is thrown. It's not in expr(), so the state info just seems wrong. But, we need to review what the change in the Java code was supposed to correct.

Thank you @kaby76 for your investigations!

I agree, the correct error message is matched input '<EOF>' expecting '<= and wrong is mismatched input '<EOF>' expecting {'-', '*', '+', ')'}.

Correct: C#, TypeScript, C++, Go, JavaScript
Incorrect: Dart, Java, PHP, Pyhton3, Rust

[hackathlete]

Reproduced.

The behavior varies with target. The expected token list is inconsistent for Dart, Java, PHP, Rust. The expected token listis only <= for Antlr4ng, Cpp, CSharp, Go, JavaScript, Python3, TypeScript. out.txt. Why are they different?

The tokens listed in the error message are computed by ATN.NextToken(). This fuction is called in RecoverInline(), using a constructor that depends on state information. Please refer to the CSharp and Java code.

antlr4/runtime/CSharp/src/DefaultErrorStrategy.cs

Line 574 in 594cf95
throw new InputMismatchException(recognizer);
)

antlr4/runtime/Java/src/org/antlr/v4/runtime/DefaultErrorStrategy.java

Line 485 in 594cf95
e = new InputMismatchException(recognizer, nextTokensState, nextTokensContext);

For Java, the offending state is 63; for CSharp, it is 18. For Java, nextTokensContext is not null, so new InputMismatchException(recognizer, nextTokensState, nextTokensContext) is called. nextTokenState is 63, and the context is the call stack. For CSharp, this.nextTokenState is 63, but it is not used in constructing the exception via new InputMismatchException(recognizer). State 63 corresponds to an NFA state in expr. State 18 corresponds to an NFA state in assign.

The code for Java was updated with 0803c74 in #1922. But, the code for CSharp was not updated. I don't know why the change wasn't propagated to all targets at the time of the bug fix. Or, as demonstrated by this Issue, whether the change really is actually correct. It seems plausible that the computation of nextTokensContext is wrong.

You can likely write a workaround by replacing the default error recovery class with one that suits your situation.

I am not sure, if I can work around this issue with my own ANTLRErrorStrategy class. I stepped trough the code with the debugger for the both inputs (t) and (others => 9).
I see the difference is that for input (t) there are two _errHandler.sync(this); on the way up from expr() [63] to assign() [18]. Whereas for input (others => 9) there is no _errHandler.sync(this); all the way up until match(LE); in assign(). So, on the way up the offendingState is never updated to [18] and stays at [63] in expr().

I do not understand the logic behind of when to input _errHandler.sync(this); in the generated parser and when not to. Comparing the generated parsers for two targets (e.g. Java and C#) may help to identify the problem?

[kaby76]

For Java, you can implement the equivalent to how the CSharp code works by subclassing DefaultErrorStrategy, then overriding how recoverInline() works, always calling new InputMismatchException(recognizer). The solution that was implemented doesn't work because the state information fed to the other form of the constructor for InputMismatchException is wrong.

I prototyped something that I thought would work (getting the eps-Closure of the inverse of the ATN's transitions), but it's complicated by the fact that the parser may have completed a parse for some part of the rule just prior to the state corresponding to the exception.

So, for example, with the grammar grammar Foo; s : a b EOF; a:'a'?; b:'b'; c:'c';, and input 'c', we get the error mismatched input 'c' expecting 'b', whereas we should see mismatched input 'c' expecting { 'a', 'b' } as possible (i.e., the whole point of #1922). But, for input 'ac', we should only see '{ 'b' }as a possible mismatch because the parser already parsed 'a' via rulea`.