I've found plenty of ANTLR4 performance related questions (particularily this one, it links to many others) and the answers frequently point to the need of two stage parsing. I've even read tech report and while there is plenty of it I don't quite understand yet, this one is clear: "If, however, SLL mode finds a syntax error, it might have found an SLL weakness or a real syntax error, so we have to retry the entire input using optimized LL mode, which is stage two."
The problem is "entire input" might not exist (f.e. while processing live stream of status event logs from remote hardware) or it might be too big to keep in memory and slow to recreate (like result of a script translating complex database query). Also sometimes parser performance on (potentially) invalid input is relevant (editor with intellisense or just regression tests). Generally the idea to run slower parsing mode when syntax-or-weakness is found is odd - if there is any rule in the grammar that requires ALL(*) mode to parse then likelihood of it being needed increases with size of input. So not only long inputs take longer to parse, they are more likely to take a lot longer.
It seems like making grammar SLL ready is the best way to go. It is however not always possible and/or easy, it is time consuming and most likely not neutral. F.e. if some rule is used in more than one place, original non-SLL version will produce single context class for this rule, which means you can easily have single visit routine handling result of such rule. Once the rule is inlined into various use contexts and reduced to make it SLL, the code that handled it has to be spread across different visits.
The alternative would be to run the parse always in ALL(*) mode - it is very convenient and it does not seem to impact performance too much with exception of some cases when it does (and once it does it is BIG). F.e. it is particularily bad on classic if-else conflict, especially the following form kills it quickly:
stmt
:
some_stmt1
|
some_stmt2
|
...
|
'if' '(' expr ')' stmt
( 'else' 'if' '(' expr ')' stmt )*
( 'else' stmt )?
;
Thankfully with use of predicate you can block the 'if' alternative in stmt call after last 'else' which helps a lot with performance, does not disrupt the rule too much and can be applied even if stmt rule does not call itself directly.
Two questions arise:
Is there a way of limiting what "entire input" means? F.e. I'd like to run "catch and switch to ALL(*)" on no more than a single statement. Once the statement that didn't properly parse in SLL parses in ALL(*) I'd want to switch the mode back to SLL and continue from there. Is that possible? My doubt comes from observations that ANTLR sometimes does ridiculously long lookaheads for no apparent reason so it could "jump" out of the statement during prediction even if there is a guarding semicolon that cannot show up inside the statement.
The behaviour on if-else and how the predicate helps there leads me to the following question. Is there a way to tell ANTLR to stop considering other alternatives once it reaches certain point? Assuming it "runs" all the alternatives in parallel during prediction starting from the topmost alternative, if I could tell it to choose the road it checked first it would help in if-else and a lot more cases.
During testing the if-else case I've found one more peculiar behaviour of ANTLR.
if (a)
if (b) c; else d;
else
if (e) f; else g;
When first 'else' is encountered it might fit to first or second 'if'. Once second 'else' is encountered the only alternative alive should be the one that matches first 'else' with second 'if' and just encountered second 'else' with first 'if'. I'd expect ANTLR to stop predicting there in the middle of the rule and just run this route potentially running into (actual) syntax error later if there was one after second 'else'. The problem is the "deepest" lookahead (reported by ANTLR plugin for IntelliJ IDEA) spans from first 'else' to the semicolon after f. This suggests that ANTLR continues with predicting the only viable alternative until the point when it can successfully finish it. Why is it doing so? My guess is it is somehow related to error recovery. Is there a way to make it work as I expected?
Update: I was doing some experiments with hacky "trapdoor" predicate (that returns true only first time it is asked, then false until it is reset). It didn't work. But in the meantime I've noticed the predicate solution for if-elseif-else problem presented at the start does not work either. I still have the console with results from before changes opened and it clearly shows that solution did work. I tried to revert my test grammar back to what it was but I can't make that solution work again - no idea what happened, what kind of mistake I've made before. It now behaves as if predicates are not executed during prediction. I thought it's better to tell about it here in case someone else tried it and expected it to work.
At least solution where stmt rule is cut into separate if_elseif_else and stmt_no_if parts and only the latter is called after last else still works ok. Too bad with absence of rule inlining that solution is adding superfluous contexts.