4
$\begingroup$

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

$\endgroup$

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
6
$\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$
  • 2
    $\begingroup$ An example would improve this answer greatly. $\endgroup$ – Raphael May 22 '12 at 19:20
6
$\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, privacy policy and cookie policy

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