unambiguous grammar

Let’s see the solution of following question:
Problem:

Consider the grammar:
S -> aS | aSbS | epsilon
where S is the only non-terminal, and epsilon is the null string.

a) Show that the grammar is ambiguous, by giving two parse trees for the string aab.
b) Find an unambiguous grammar that generates these strings.

Solution:

Solution-(a)

The ambiguity is easy to show: you can derive the string aab as follows:
(at every step we expand the leftmost non-terminal);

S -> aSbS -> aaSbS -> aabS -> aab
S -> aS -> aaSbS -> aabS -> aab

These two parses correspond to associating the b with the first or the
second a.

Solution-(b)

We can disambiguate by using a similar approach to the dangling else, and
decide that each b should be associated with the nearest a. This means that
the expansion within an ab pair should always be balanced. This leads to
the following grammar:

S -> a S | S1 S | epsilon
S1 -> a S1 S1 b | epsilon

It is easy to verify that this generates the same strings as the original
grammar, and the parse tree is always unique, because one b is always associated
with the most recent a.

Note that the answer is not necessarily unique. If the grammar is ambiguous,
it means that we get to choose between possible parses, and each choice is
in a sense a different language. For example, given the ambiguous grammar
for expressions:

E -> E + E | E * E | id

We say that the unambiguous grammar we want is:

E -> E + T | T, T -> T * T | id

because it gives us the proper precedence between the two operators. But that
choice is in no way mandated by the grammar. We could just as well choose:

E -> E * T | T , T -> T + T | id

which generates the same strings, but gives the opposite precedence to
operators.

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.

Ambiguous Grammar

What does it mean for a grammar to be ambiguous?

A grammar is ambiguous iff there exists a string s in L(G) for which s has more than one parse tree.

·What is an example ambiguous grammar?

E → E '+' E | 'a'

·Prove that the previous grammar is ambiguous.

Given the input a+a+a, we can produce two different parse trees. The notation N(...) means we build the nonterminal N from the symbols (...)

a+a+a →* E(a)+E(a)+E(a) → E(E(a) + E(a)) + E(a) → E

and

a+a+a →* E(a)+E(a)+E(a) → E(a) + E(E(a) + E(a)) → E

For example:
The x+y*z is interpreted as
(x+y)*z

by this grammar (if we use leftmost derivations) and as

x+(y*z)

by G1 or G2.

That is, both G1 and G2 grammar handle the operator precedence correctly (since * has higher precedence than +), while the G3 grammar does not.

In next post, I will explain the most interesting part of context free grammars that is ambiguous grammar.

equivalent grammer

Consider the following grammar G1 again:
E ::= E + T | E - T | T
T ::= T * F | T / F | F
F ::= num | id

Consider now the following grammar G2

E ::= T + E | T – E | T
T ::= F * T | F / T | F
F ::= num | id

Consider now the following grammar G3:
E ::= E + E | E – E | E * E | E / E | num | id

Is this grammar equivalent to our original grammar G1?

Well, it recognizes the same language, but it constructs the wrong parse trees.

parse tree

Consider now the following grammar G2:

E ::= T + E | T – E | T
T ::= F * T | F / T | F
F ::= num | id

This is similar to our original grammar G1 (which we considered in our previous posts), but it is right associative when the leftmost derivation rules is used. That is, x-y-z is equivalent to x-(y-z) under G2, as we can see from its parse tree.