Dangling Else Problem

In this post, we will see dangling else problem. It is the best example of ambiguous grammar.

Dangling Else Problem:
The dangling else is a well-known problem in computer programming in which a seemingly well defined grammar can become ambiguous. In many programming languages you can write code like this:

if a then if b then s1 else s2

which can be understood in two ways. Either as

if a then
if b then
s1
else
s2
or as
if a then
if b then
s1
else
s2

It can be solved either at the implementation level, by telling the parse the right way to solve the ambiguity, or at the grammar level by using a parsing expression grammar or equivalent.

In next post , I will give an example which will cover all topics related to ambiguous grammar

ambiguous grammar examples

In the last post, We saw 2 possible parse trees for a+a+a. How many are there for a+a+a+a?

There are 5 possible parses:

(a)+((a+a)+a),

(a)+(a+(a+a)),

(a+a)+(a+a),

((a+a)+a)+(a),

(a+(a+a))+(a)


While in general it may be difficult to prove a grammar is ambiguous, the demonstration of two distinct parse trees for the same terminal string is sufficient proof that a grammar is ambiguous.