(MySQL-Oracle) The antlr4 error recovery seems working exceptionally bad on SELECT statement?

[OnMYLai]

I've read that antlr4 would do single token insertion or deletion as an error recovery measure, but when I try it on SELECT statement it always fail:

SELECT FROM t;    //no viable alternative at input 'SELECT FROM'
SELECT * * FROM t;    //mismatched input '*' expecting ';' (only expecting semicolon?)

these are obvious cases of missing one and having one extra token, and neither can trigger the corresponding error recovery method and be prased into a complete SELECT statement. Antlr simply gives up on the point of error and doesnt even bother parsing the tokens afterwards.

Same test done on INSERT statement:

INSERT INTO VALUES (1);    //mismatched input 'VALUES' expecting {...}
INSERT INTO t t VALUES (1);    //extraneous input 't' expecting {...}

While only the extra token case has the correct error message, both have the token after the error point parsed successfully.

[kaby76]

For this input SELECT FROM t; , the point of error is at line 1, column 7 because of the missing '*'. But, the default error recovery starts recovery at token index 0 because the entire selectStatement is assumed invalid. The default recovery doesn't insert tokens at all. It calls Consume() for the entire selectStatement until it can resync. https://github.com/antlr/antlr4/blob/6a15cc32dea4e1ec4aa2abbdc90e1b54cf288c58/runtime/CSharp/src/DefaultErrorStrategy.cs#L212

I am unsure of the error recovery mechanism in the Oracle sources (https://github.com/mysql/mysql-shell-plugins/tree/8928ada7d9e37a4075291880738983752b315fee/gui/frontend/src/parsing/mysql). It may involve token insertion, i.e., a minimal distance error strategy. @mike-lischke

[OnMYLai]

Yeah the default recovery method of ANTLR is consume tokens until resync some node in the higher structure, it is like the ultimate move of ANTLR to deal with errors, but it also has an recoverInLine function that attempts to "fix" errors by adding or removing one token, it is documented in its definite reference book. Yet in the SELECT statement case I'm not sure in what condition it would get called.

[kaby76]

RecoverInLine() is only called from Parser.Match() or from ParserInterpreter.VisitState(). ParserInterpreter isn't even involved because it's not called here, and the class hiearachy for the parser doesn't involve ParserInterpreter. For testing performance and ambiguous tree enumeration, the template driver apps in grammars-v4 utilize ParserInterpreter; however, it is not used for a simple parse.

The parser exception, NoViableAltException, is raised by AdaptivePredict():

>	Antlr4.Runtime.Standard.dll!Antlr4.Runtime.Atn.ParserATNSimulator.ExecATN(Antlr4.Runtime.Dfa.DFA dfa, Antlr4.Runtime.Dfa.DFAState s0, Antlr4.Runtime.ITokenStream input, int startIndex, Antlr4.Runtime.ParserRuleContext outerContext) Line 155	C#
 	Antlr4.Runtime.Standard.dll!Antlr4.Runtime.Atn.ParserATNSimulator.AdaptivePredict(Antlr4.Runtime.ITokenStream input, int decision, Antlr4.Runtime.ParserRuleContext outerContext) Line 110	C#
 	Test.dll!MySQLParser.selectStatement() Line 14891	C#
 	Test.dll!MySQLParser.simpleStatement() Line 1502	C#
 	Test.dll!MySQLParser.query() Line 1128	C#
 	Test.dll!MySQLParser.queries() Line 1067	C#
 	Test.dll!Program.DoParse(Antlr4.Runtime.ICharStream str, string input_name, int row_number) Line 332	C#
 	Test.dll!Program.ParseFilename(string input, int row_number) Line 281	C#
 	Test.dll!Program.Main(string[] args) Line 236	C#

In AdaptivePredict(), it enters an error transition for the DFA state, then reports the error. After printing out an error message, the parser does the parse over again, starting from SELECT because it still needs to decide as to what to do for selectStatement.

selectStatement
    : queryExpression lockingClauseList?
    | selectStatementWithInto
    ;

selectStatement(), and AdaptivePredict(), must make a choice still, because the current token index is at the SELECT, not after. There is no token insertion because AdaptivePredict() does not do token insertion.

There are two problems here. First, it arises because selectStatement is not left-factored, so it cannot make a choice because either alternative can begin with SELECT. The grammar is flawed because non-left-factoring grammars cause large max-k's. As a side effect of the flaw, error recovery is messed up because it exploits a second problem. The second problem is with AdaptivePredict() and/or the class structure for the generated MySQLParser class. It does not perform error recovery using token insertion when a decision is required.

[OnMYLai]

Thank you very much for the very detailed explanation, I did trace through the parsing process and saw it getting an exception created in the predict process of selectItemList, but it didnt throw the exception out because the Alt value predicted is 2 instead of INVALID_ALT_NUMBER, and it returned all the way back up to query, and trigger error recovery when it attempt to match for a semicolon.
So I guess a custom error strategy won't help in this situation, welp time for more head banging🙈