Is there an LR (k) grammar without an LL (1) equivalent
I haven't been able to find an answer yet. Are there grammars that are contextual and unambiguous that cannot be converted to LL (1)?
I found one piece I could not figure out how to convert to LL (1): creation parameter-type-list
in C99:
parameter-type-list:
parameter-list
parameter-list , ...
Is this an example of an LR (k) grammar that has no LL (1) equivalent, or am I doing something wrong?
edit: I copied the wrong name, I wanted to copy the parameter-declaration:
parameter-declaration:
declaration-specifiers declarator
declaration-specifiers abstract-declarator(opt)
the problem is the declarator and the abstract declarator both have (in their first set, but also remain recursive.
source to share
In general, grammars are LR(k)
more powerful than LL(k)
. This means that there are languages with a parser LR(k)
, but not LL(k)
.
One example is a grammar-defined language:
S -> a S
S -> P
P -> a P b
P -> \epsilon
Or, in other words, the string a
's followed by the same number or less b
. This follows from the fact that the parser LL(k)
has to make a decision about every one it encounters a
- it is paired with some b
- looks ahead at no more than k
input characters, but they can also be a
's without giving any useful information. For a strong proof take a look at the second part of the accepted answer here https://cs.stackexchange.com/questions/3350/is-this-language-ll1-parseable
Your example, however, might just be left factored in the LL (1) grammar to be
parameter-type-list -> parameter-list optional-ellipsis
optional-ellipsis -> \epsilon
optional-ellipsis -> , ...
One thing to note is that FOLLOW
for parameter-list
will contain a character ,
and this can cause a conflict FIRST-FOLLOW
. If so, then we need to see the definition parameter-list
to correct this conflict.
Edit: It parameter-declaration
seems very difficult to answer right away. You can try to do left factorization by hand for all conflicting alternatives or with some help tool like ANTLR .
source to share