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