antlr4

Semantic predicate false throws NoViableAltException in adaptivePredict(), then error recovery doesn't rewind _input.p

My grammar is

grammar Interpreter;

conditionalOrExpression : relationalRestriction ( OR relationalRestriction )* ;

relationalRestriction  : primary ( orRestriction )* ;

orRestriction : singleRestriction (OR annotation? singleRestriction)* ;

singleRestriction : operator primary ;

operator : EQUALS
         | {  _input.LT(1).getText().equals("customOperator") }? ID  // check custom operators using java util method
         ;

primary : INT
        | ID
        | '(' ID ')'
        | ID '(' ID ')'
        ;

annotation : AT ID ;

OR     :  '||';
ID     :  [a-zA-Z]+;
INT    :  '0'..'9'+;
EQUALS :  '==';
AT     :  '@';

WS     :  [ \t\r\n]+ -> skip;

(Sorry that the rules are not intuitive and not simplified well, but it required to reproduce the issue. The whole example is https://github.com/tkobayas/antlr-semantic-predicate-recovery)

Input is a == 5 || notCustomOperator(b) == 6. I expect that notCustomOperator results in false in the semantic predicate in operator rule, so it creates relationalRestriction a == 5 and relationalRestriction notCustomOperator(b) == 6 connected by OR || under conditionalOrExpression.

However, it results in line 1:10 no viable alternative at input 'notCustomOperator' and it doesn't take the alternative I expect above.

I read The prediction process also can't see through token references. Token references have the side effect of advancing the input one symbol. A predicate that tested the current input symbol would find itself out of sync if the parser shifted it over the token reference. in https://github.com/antlr/antlr4/blob/master/doc/predicates.md#finding-visible-predicates (and read other similar SO threads), but with a debugger, I actually see that the semantic predicate (operator_sempred()) is executed in ParserATNSimulator.adaptivePredict() in InterpreterParser.orRestriction(). The semantic predicate expectedly returns false and throws NoViableAltException, then it goes to DefaultErrorStrategy.recover(). I expect that it continues to look for alternatives, but a problem is that _input.p is not rewound to ||, so the current token is notCustomOperator, so it cannot match the expected alternative.

That said... probably my expectation was wrong and I have to rewrite the grammar. But I want to confirm if this is a designed behavior (= we cannot rely on semantic predicate for prediction in this case), because the semantic predicate is executed in contradiction to the documentation.

Solution

  • From your grammar it seems that your input is wrong. For input a == 5 || notCustomOperator(b) == 6 there's no path to match the ||. a matched as primary and orRestriction doesn't start with || but wants an operator first. So, ANTLR first tries to match EQUALS which fails for || and then runs the predicate, which also fails. This means there's no viable alt in operator, which in turns fails orRestriction.

    I'm not sure if error recovery even tries to find a missing or unwanted token. To me it looks as if that's beyond its abilities. Hence the error.