Compiler Design and Construction - Old Questions

4.  Translate the arithmetic expression a*-(b+c) into syntax tree. Explain the ambiguous grammar.

Syntax tree for given arithmetic expression is shown below:

a*-(b+c) 

If a same terminal string can be derived from the grammar using two or more distinct left-most derivation (or right most) then the grammar is said to be ambiguous i.e. from an ambiguous grammar, we can get two or more distinct parse tree for the same terminal string.

For example:

E → E+E | E*E | id

String: id+id*id

Derivation 1:

Derivation 2:

For the string id + id * id, the above grammar generates two parse trees or two distinct derivation. So the grammar is ambiguous.