Wednesday, August 1, 2007

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.

8 comments:

Anonymous said...

Hello. This post is likeable, and your blog is very interesting, congratulations :-). I will add in my blogroll =). If possible gives a last there on my blog, it is about the Wireless, I hope you enjoy. The address is http://wireless-brasil.blogspot.com. A hug.

davidb said...

Hello,

I find very interesting your blog too, because I have to prepare an exam related to automata theory languages and computation. I'm not able to solve some exercises on my own. If you will get this message could I ask you for your help to solve some of them (6 exercises).
This is the first one:
Prove the correctness of the construction of DFA minimization!
Hint: Let B the minimized DFA obtained by applying the TFG algorithm to DFA A. It is
already proved that L(A)=L(B). Suppose ont he contrary that there exists an automaton C
with fewer states than B such that L(C)=L(A). that Now run the TFG algorithm for BUC
and conclude with contraversary.

thank you in advance
David Bozic
Slovenija (EU)
e-mail: david.bozic@student.upr.si

Unknown said...

"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."

Your solution is wrong because it does not generate the language of the original grammar. For example, id+id*id+id can not be derived.

Unknown said...

I believe that what you meant to write was-
E -> E + T | T, T -> T * E | id

Kapil Shukla said...

I Like your blog....
You can visit my blog
Theory of Computation Material
Enjoy Learning

Kapil Shukla said...

I Have Posted some material for GATE-2012 Exam on
GATE - 2012 TOC Material

suresh reddy said...

Please help me ....

1. Consider the following grammar for Boolean expressions.
E ->E or E
E -> E and E
E -> not E
E -> (E)
E ->true
E -> false
E -> id
(a) Show that this grammar is ambiguous.
(b) Rewrite the grammar to remove the ambiguity and enforce the intended precedence order by introducing new nonterminals. Make sure that your revised grammar accepts the same language as the original.

abhilash said...

Helpful