$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?

  • $\begingroup$ I of course suspected the non-realizability of $S$ to be the culprit, after all, it's natural to assume that any algorithm might cease to work on a nonproductive grammar. The paper that mentions the relation $G_{LL(k)} \subset G_{LR(k)}$ (Properties of Deterministic Top-Down Grammars, theorem 14) however doesn't seem to mention productivity at all. $\endgroup$ Dec 23 '12 at 15:02
  • $\begingroup$ @HendrikJan Post as an answer? $\endgroup$ Dec 23 '12 at 19:18

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.


The book I have been consulting starts with the assumption: "let $G$ be a grammar without useless symbols". I could not immediately see where that is necessary in the analysis, but obviously your variables are useless, they do not generate terminal strings.

You are right, I could find no explicit note of that fact in the Rosenkrantz and Stearns paper you cite. Only in one of the constructions they note (page 229 top) "Remove all the symbols [..] and all productions [..] which cannot be used in deriving a terminal string [..]". But that is in the LL(1) analysis.

(originally posted as comment, as it is low on technical detail; moved following the suggestion by Yuval)


I did not see why we should consider a useless grammar such as

S ::= S

Are there meaningful implications? The easy thing we can do is to require that we should "remove all useless symbols and production rules before generating LL and LR parsers."


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.