5
$\begingroup$

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

$\endgroup$
4
  • $\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, 2012 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, 2012 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$ Apr 10, 2012 at 22:52
  • $\begingroup$ related: cs.stackexchange.com/questions/43/… $\endgroup$
    – Kaveh
    May 22, 2012 at 19:08

2 Answers 2

7
$\begingroup$

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'.

$\endgroup$
1
  • 2
    $\begingroup$ An example would improve this answer greatly. $\endgroup$
    – Raphael
    May 22, 2012 at 19:20
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.