Is the set of LL(*) grammars the same as the set of context-free grammars?
Static LL(*) grammar analysis is undecidable. In other words, there are some grammars that are LL(*) but we can't figure this out statically. ANTLR v3 fails over to backtracking in this case and therefore can exhibit the PEG A->a/ab problem where ab is dead code in the cases where grammar analysis failed.
In ANTLR v4, I'm introducing adaptive LL(*), which does all grammar analysis at runtime. Because I have an actual input stream in my paw, I can discover every LL(*) decision. I'm also including full LL context (vs Strong LL == SLL context which is weaker). Because I also rewrite all immediate left recursion on-the-fly, ANTLR v4 handles all CFG except for indirect left recursive ones. These are much less common than the immediate left recursive ones like expressions.
e : e '*' e | e '+' e | INT ;
This works fine in v4. operator precedence is assumed to go from highest to lowest for ambiguous alternatives.
No, since no
LL(*) grammar can be left-recursive and obviously there are context-free grammars which are left-recursive.
As requested: A sample of a left-recursive, context-free grammar (which is therefore not
S -> S x | ɛ
The language this grammar describes is one or more times the character 'x'.