Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Jakub Lédl Dec 23 '12 at 15:02
    
@HendrikJan Post as an answer? –  Yuval Filmus Dec 23 '12 at 19:18
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.