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

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.