# How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?

$\textbf{stmt} \to$ $\textbf{if}$expr$\textbf{then}$ stmt $\mid$ $\textbf{if}$ expr $\textbf{then}$ stmt$\textbf{else}$ stmt $\mid \textbf{other}$

This grammar is called as Dangling Else Problem . However the ambiguity is resolved by parser as described as follows

In all programming languages with conditional statements of this form, the first parse tree is preferred. The general rule is, "Match each else with the closest unmatched then"

It is rarely built into productions

$\textbf{stmt} \to$ $\textbf{matched_stmt}$ $\mid$ $\textbf{open_stmt}$

$\textbf{matched_stmt} \to$ $\textbf{if}$expr$\textbf{then}$ matched_stmt $\textbf{else}$ matched_stmt $\mid$ $\textbf{other}$

$\textbf{open_stmt} \to$ $\textbf{if}$expr$\textbf{then}$ stmt $\mid$ $\textbf{if}$ expr $\textbf{then}$ matched_stmt$\textbf{else}$ open_stmt

However this grammar is also ambiguous . Moreover no grammar is there that could eliminate ambiguity problem of Dangling else problem . Hence we can say that dangling else problem in also inherently ambiguous

My question is How to prove that Ambiguity is still present in this resolved Production of Dangling Else Problem ? What I know is that if two different parse trees are possible then the grammar in ambiguous . Does any such parse trees possible for the resolved grammar ? If so could u please give an example parse tree for the same

• What makes you think the second grammar is ambiguous? – rici Nov 28 '16 at 13:36
• @rici , Because Dangling else problem is inherently ambiguous . so there will not be any unambiguous grammar . Moreover he , himself has mentioned in the book – Akhil Nadh PC Nov 28 '16 at 13:58
• The problem of ambiguity is in general undecidable. Maybe you try to find an example which can be parsed into two different parse-trees. – mruether Nov 28 '16 at 14:36
• I seriously doubt that the grammar of C is inherently ambiguous. Indeed, it can be parsed using an LALR parser, which is a deterministic push-down automaton. – Yuval Filmus Nov 28 '16 at 14:48
• @akhil it is not inherently ambiguous and the dragon book does not say that it is. 2nd edition, p. 211, example 4.16: "we can rewrite the dangling else grammar as the following unambiguous grammar..." (emphasis added). – rici Nov 28 '16 at 16:42

A grammar $G$ for a language $L$ is ambiguous if there is a string $w \in L$ which has two different parse trees (with respect to $G$). Hence in order to show that ambiguity is still present, all you have to do is to come up with a string generated by your grammar that has two different parse trees.

• true enough but "all you have to do" is a bit optimistic given that no algorithm exists :) (Leaving aside the issue that the given grammar is in fact unambiguous making the search for an ambiguous parse an exercise in futility.) – rici Nov 28 '16 at 16:47
• I know this is the procedure but im not able to find 2 parse trees for the resolved grammar . I need help in finding parse tree for (resolved) grammar – Akhil Nadh PC Dec 4 '16 at 7:22

First, we know that there are unambiguous grammars for this language. Let's ignore that.

A language isn't just defined by the grammar. It's defined by the grammar, plus our rules how to generate parse trees. The usual rule is "find every possible parse tree". With that rule some grammar might be ambiguous because we can find two or more parse trees.

If a compiler uses a different set of rules, and with those rules there is only one parse tree, then the combination of grammar and rules is not ambiguous. That's what's happened here: The compiler says "in case of ambiguity we decide to use one parse tree and not the other". That makes the language created by grammar + compiler rules unambiguous.

As an example, we often have a grammar and try to produce lets say an LR-1 parser for the grammar, and trying to produce that parser might fail (because at some point there are two different productions that could be used, especially if the grammar is ambiguous). But we can always produce a non-deterministic parser, and turn it into a deterministic parser by picking one production wherever the non-deterministic parser would give us a choice. We now have a deterministic, unambiguous parser, derived from the grammar, which will parse some language in an unambiguous way.

While the first grammar is ambiguous, the second is not.

We can see that the first is ambiguous by considering the string

$$\mathbf{if} \; \mathit{expr} \; \mathbf{then} \; \mathbf{if} \; \mathit{expr} \; \mathbf{then} \; \mathbf{other} \; \mathbf{else} \; \mathbf{other}$$

which has two left-most derivations with the first grammar.

We can prove that the second is not ambiguous by showing that it is LALR; this we can do by compiling the following file with bison.

%start stmt
%token IF THEN ELSE EXPR OTHER
%%

stmt : matched_stmt
| open_stmt ;
matched_stmt : IF EXPR THEN matched_stmt ELSE matched_stmt
| OTHER ;
open_stmt : IF EXPR THEN stmt
| IF EXPR THEN matched_stmt ELSE open_stmt ;


No conflicts are reported, so the grammar is LALR, and hence it is unambiguous.

As @rici pointed out in the comments, the Aho et al. book does not claim that the second grammar is ambiguous.

In my copy (1986, corrected) the following grammar is claimed to be ambiguous in an exercise.

$$\mathit{stmt} \rightarrow \mathbf{if} \; \mathit{expr} \; \mathbf{then} \; \mathit{stmt} \mid \mathit{matched\_stmt}$$ $$\mathit{matched\_stmt} \rightarrow \mathbf{if} \; \mathit{expr} \; \mathbf{then} \; \mathit{matched\_stmt} \; \mathbf{else} \; \mathit{stmt} \mid \mathbf{other}$$

And it is.

To prove some Grammar is Ambiguous You have find Atleast 2 or more $LMD or RMD$(Left or right most derivative tree) for a string $w$ which belongs to the grammar.

There is small catch here, it is not necessary that if a string has two derivation it will produce a ambiguity but if the derivation of the string has more than two parse tree it surely produce ambiguity.

If we talk about the Inherently ambiguous here are some explanation given by friend Rahul I think Its worth reading it.

let's say we have

$S \to A\mid B$

A generates all the strings where m=n

B generates all the strings where n=p

Now, we can observe that both A and B can generate common strings which are m=n=p.

So while deriving such strings we can either go by

$S \to A$

Or

$S \to B$

We have two possible derivations (LMD or RMD doesn't matter because in either case we derive only one non-terminal). Hence it is inherently ambiguous.

We can have 2 parse trees to generate the common strings. Remember this rule of thumb,

If you find a production of the form

$S\to A \mid B$

Of a grammar that generates a language AND A&B can generate strings that are common AND you can't MODIfy the grammar to eliminate this commonality then it is inherently ambiguous.

• Something wrong with my answer. Please let me know. – iambruv Nov 29 '16 at 1:43
• To start with, the second part of your answer (Rahul's explanation) is missing some context: it is about the language $\{ a^mb^nc^p : m=n \text{ or } n = p\}$, but this is not mentioned anywhere. Also, in the beginning you mention leftmost and rightmost derivations as types of parse trees, which is misleading. – Yuval Filmus Nov 29 '16 at 10:30
• @YuvalFilmus Thank you yuval for pointing that out. So should need to delete my answer or corrections are allowed ? – iambruv Nov 29 '16 at 10:39
• It's up to you. You can definitely edit your answer to improve it. – Yuval Filmus Nov 29 '16 at 10:40