Is the set of LL(*) grammars the same as the set of context-free grammars?


migrated from cstheory.stackexchange.com May 22 '12 at 19:05

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ @reinierpost: thank you. The reason I asked though was because extensive Google searching yielded no results. The + operator is also deprecated in favor of inferior "Verbatim" search, fyi. I shall ask future such questions at cs.stackexchange $\endgroup$ – ninjagecko Apr 10 '12 at 21:27
  • $\begingroup$ It seems that the post linked by Alex states that unlimited lookahead with LL(*) does not magically allow for left-recursion, which was the heart of my question. $\endgroup$ – ninjagecko Apr 10 '12 at 21:41
  • $\begingroup$ An example of a rather nasty non-LL(*) grammar is EPAL: $S \rightarrow a S a | b S b | aa | bb$. I've tried this myself and ANTLR v3.0 doesn't accept this grammar. Maybe @TerenceParr can shed some light on whether ANTLR v4.0 does parse this grammar correctly? $\endgroup$ – Alex ten Brink Apr 10 '12 at 22:52
  • $\begingroup$ related: cs.stackexchange.com/questions/43/… $\endgroup$ – Kaveh May 22 '12 at 19:08

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 LL(*)) :

S -> S x
   | ɛ

The language this grammar describes is one or more times the character 'x'.

  • 2
    $\begingroup$ An example would improve this answer greatly. $\endgroup$ – Raphael May 22 '12 at 19:20

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .