Assignment #2

#2. Explain what is an ambigous grammar..
Ambiguous grammar
From Wikipedia, the free encyclopedia.
In computer science, a grammar is said to be an ambiguous grammar if there is some string that it can generate in more than one way (i.e., the string has more than one parse tree or more than one leftmost derivation). A language is inherently ambiguous if it can only be generated by ambiguous grammars.
For programming languages, ambiguous grammars can lead to difficulties for some compilers.
[edit]

Example
The context free grammar
A → A + A A − A a
is ambiguous since there are two leftmost derivations for the string a + a − a:

A
→ A + A

A
→ A − A

→ a + A

→ A + A − A

→ a + A − A

→ a + A − A

→ a + a − A

→ a + a − A

→ a + a − a

→ a + a − a
Equivalently, it is ambiguous since there are two parse trees for the string a + a − a:

The language that it generates, however, is not inherently ambiguous; the following is a non-ambiguous grammar generating the same language:
A → A + a A − a a
[edit]