3
$\begingroup$

I have following grammar:

$$A \to a A a \mid \varepsilon$$

This grammar is not ambiguous because it has no more than one parse tree from the any sentence generated by this grammar, but there is a shift-reduce conflict in LR(1) on this grammar.

Why does there exist an conflict even though it is not ambiguous grammar?

$\endgroup$
  • 1
    $\begingroup$ Unambiguous context-free grammar are not necessarily LR(1), but I'd like to know why you think this one is not. $\endgroup$ – AProgrammer Apr 28 '17 at 8:02
  • $\begingroup$ Here's a clue: A -> e | A a a $\endgroup$ – Pseudonym Apr 28 '17 at 8:13
8
$\begingroup$

All $LR(1)$ grammars -- indeed, all $LR(k)$ grammars -- are unambiguous, by definition. But the converse is not true: the fact that a grammar is unambiguous does not say anything about whether it can be parsed with an $LR(k)$ parser.

The grammar you present is not $LR(1)$, although the language itself is. (In fact, the language is regular: $(aa)^*$.) But that's not true for the language of even-length palindromes which has a rather similar unambiguous CFG:

$$\begin{align} S &\to \epsilon \\ S &\to a S a \\ S &\to b S b \end{align}$$

Intuitively, the problem with parsing palindromes deterministically is that you have to start popping the stack at the middle of the sentence. But you can't tell where the middle of the sentence is until you reach the end, and since there is no limit on the length of a sentence, the end could be arbitrarily distant from the middle. So no finite lookahead is sufficient to make the decision.

A context-free language is $LR(k)$ precisely if it is deterministic. For the outline of a proof of the non-determinism of the language of even-length palindromes, see: prove no DPDA accepts language of even-lengthed palindromes

$\endgroup$

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.