Dragon book says:

An ambiguous grammar can never be LR.

And then immediately further it says:

For example, consider the dangling-else grammar:

$\begin{align} stmt \rightarrow & \textbf{ if } expr \textbf{ then }stmt \\ &| \textbf{ if } expr \textbf{ then }stmt \textbf{ else } stmt \\ &|\textbf{ other} \end{align} $

If we have a shift reduce parser in configuration

$$ \begin{matrix} STACK & INPUT \\ ...\textbf{if }expr\textbf{ then }stmt & \textbf{else...} \end{matrix} $$

we cannot tell whether $\textbf{if }expr\textbf{ then }stmt$ is the handle, no matter what appears below it on the stack. Here there is a shiftl reduce conflict. Depending on what follows the $\textbf{else}$** on the input, it might be correct to reduce $\textbf{if }expr\textbf{ then }stmt$, or it might be correct to shift $\textbf{else}$ and then to look for another $stmt$ to complete the alternative $\textbf{if }expr\textbf{ then }stmt \textbf{ else } stmt$.

My question is quite simple one. The author starts with saying fact about "ambiguous" grammar but then he gives example of problem with same prefix of right sides of two productions (say non deterministic grammar) but not really related to the ambiguousness of grammar.

Am I right? Also what does that mean? LR grammar cannot work with both: Non deterministic and ambiguous grammars?


The grammar is really ambiguous.

$\textbf{ if } expr \textbf{ then if }expr \textbf{ then } stmt \textbf{ else } stmt$

has two possible parses with that grammar. (The $ \textbf{ else }$ can attach to either $\textbf{ if }$.)

As you say, determinism and ambiguity are orthogonal. Certainly, there are unambiguous grammars which are not LR. But no ambiguous grammar is LR and this is one such example.

  • $\begingroup$ Just need small clarifications, by "orthogonal", do you mean "unrelated"? Also above grammar is ambiguous, but does the example or explanation given demonstrates unsuitability of ambiguous grammar for LR parsing? Or it is demonstrating unsuitability of non determinism for LR parsing? $\endgroup$ – anir Nov 28 '18 at 16:49
  • 1
    $\begingroup$ @anlr: I don't think the example demonstrates anything. The demonstration that ambiguous grammars necessarily produce conflicts in the parsing table comes from a formal proof (if it is not in the Dragon book, it is easy to find elsewhere.) The example is simply an example which you can use to possibly better understand. And it is definitely intended as an example of an ambiguous grammar. Non-determinism is a much more complicated criterion... $\endgroup$ – rici Nov 28 '18 at 17:27
  • 1
    $\begingroup$ It should be clear that an ambiguous grammar cannot be deterministic. But the converse does not apply: an unambiguous grammar might or might not be deterministic. $\endgroup$ – rici Nov 28 '18 at 17:29
  • 1
    $\begingroup$ @VimalPatel: That statement is not as interesting as it looks. Yes, a right sentential form has exactly one handle. But the parser doesn't know what the right sentential form is. The parser is trying to deduce the derivation backwards, starting with the derived sentence. So it's true that if the grammar is unambiguous, there is only one possible next right derivation for a right sentential form. But that doesn't mean that each right sentential form has only one predecessor. And that's what makes a grammar non-deterministic. $\endgroup$ – rici Jan 19 at 5:11
  • 1
    $\begingroup$ @Vimal: Also, the parser cannot even see all of the derived sentence (or of the right sentential form). It can only see what's been read so far (plus $k$ lookaheads). So even if the grammar is deterministic, the parser might not have enough information to figure out where the next handle ends. $\endgroup$ – rici Jan 19 at 5:13

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.