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