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

Question

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

Source : Compilers: Principles, Techniques, & Tools -Aho & Ullman

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.