4

I haven't been able to find an answer to this yet. Are there grammars that are context free and non-ambiguous that can't be converted to LL(1)?

I found one production that I couldn't figure out how to convert into LL(1): the parameter-type-list production in C99:

parameter-type-list:
    parameter-list
    parameter-list , ...

Is this an example of an LR(k) grammar that doesn't have an LL(1) equivalent or am I doing something wrong?

edit: I copied the wrong name, I meant to copy parameter-declaration:

parameter-declaration:
    declaration-specifiers declarator
    declaration-specifiers abstract-declarator(opt)

the problem is with declarator and abstract declarator both having ( in their first set, but also being left recursive.

Bobby Sacamano
  • 540
  • 4
  • 15
  • It is recommended to put the example/code in your question instead of putting a link. – Ely Jul 17 '15 at 22:51
  • First question possibly answered here: http://stackoverflow.com/questions/8809545/example-of-an-lr-grammar-that-cannot-be-represented-by-ll –  Jul 17 '15 at 23:00
  • Full set of comparisons (no examples): https://cs.stackexchange.com/questions/43/language-theoretic-comparison-of-ll-and-lr-grammars/48#48 – o11c Jul 17 '15 at 23:19
  • @deniss the grammar that guy lists as non LL(1) is ambiguous, so it's not really conclusive – Bobby Sacamano Jul 17 '15 at 23:27
  • @Bobby Sacamano, why is it ambiguous? Bison with `canonical-lr` accepts it with no conflicts. –  Jul 17 '15 at 23:47
  • "aab has two different parse trees, with either of the first two alternatives of S at the root" - Gunther – Bobby Sacamano Jul 17 '15 at 23:58
  • @Bobby Sacamano, that claim is about old post version, where it was `S ::= a S b | a S | \epsilon` –  Jul 18 '15 at 00:00
  • oh I misread the timestamp. Is there a way to prove that there exists no LL(1) equivalent for this though? – Bobby Sacamano Jul 18 '15 at 00:10
  • @Bobby Sacamano, http://cs.stackexchange.com/questions/3350/is-this-language-ll1-parseable –  Jul 18 '15 at 00:54

1 Answers1

4

In general, LR(k) grammars are more powerful than LL(k). That means there are languages with LR(k) parser, but not LL(k).

One of the examples are language defined with grammar:

S -> a S 
S -> P
P -> a P b
P -> \epsilon

Or, in other words, string of a's, followed by the same or less number of b's. That follows from the fact that LL(k) parser must make a decision about every a encountered - is it paired with some b - looking ahead no more than k symbols of input, but they also can be a's, giving no useful information. For strict proof, look at the second part of accepted answer here https://cs.stackexchange.com/questions/3350/is-this-language-ll1-parseable

Your example, however, can be simply left factored in LL(1) grammar to be

parameter-type-list -> parameter-list optional-ellipsis
optional-ellipsis -> \epsilon
optional-ellipsis -> , ...

One note that FOLLOW set for parameter-list will contain , character, and this can cause FIRST-FOLLOW conflict. If it is the case, then we need to see parameter-list definition to fix this conflict too.

Edit: parameter-declaration rule seems very complicated to answer right away. You can try to perform left factorization by hands for all conflicting alternatives, or with some assistance tool, like ANTLR.

Community
  • 1
  • 1