[Solved]: Is this grammar really LL(1) while not being LR(1)?

Problem Detail: 

$S \rightarrow S$, $L(G) = \{\}$

LL(1) analysis:

We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$. $FIRST(S)$ doesn't contain ε, so the parse table looks like this:

+---+---+ |   | $ | +---+---+ | S |   | +---+---+ 

and correctly rejects any input including ε.

LR(1) analysis:

We start with the initial state 0:

$S' \rightarrow \bullet S [\$]$

calculate its closure:

$S' \rightarrow \bullet S [\$]$

$S \rightarrow \bullet S [\$]$

and the only transition, which leads to state 1 on S:

$S' \rightarrow S \bullet [\$]$

$S \rightarrow S \bullet [\$]$

State 1 has a reduce/reduce conflict.

Now, obviously there must be something I'm missing, since LL(k) grammars are a proper subset of LR(k) grammars. Would anyone care to point out the error?

Asked By : Jakub Lédl

Answered By : Alex ten Brink

I've just consulted a parsing book, and it indeed requires that $S \Rightarrow^+ S$ be impossible, if $S$ is the starting symbol, before a grammar is considered $LR(k)$. As you said yourself, this is not required for a grammar to be $LL(k)$.

Usually, it is implicitly assumed grammars 'behave' when we make statements about them, such as $LL(k) \subset LR(k)$. For instance, $S \Rightarrow^+ S$, absence of symbols not derivable from $S$, and absence of symbols not deriving terminal strings are all properties of 'well behaved' context free grammars.

If we assume these things, we are spared some weird oddities of context-free grammars: for example, if we have some grammar with starting symbol $S$, by adding a nonterminal $T$ and productions $T \to \epsilon$, $S \to T S$, we can force the grammar to have infinitely many parse trees for every string in the language it represents. In contrast, if we do assume 'well behaved' grammars, we are guaranteed only finitely many parse trees exist for any input.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7560