Ambiguity in CFG

Something when having more meaning and confusion occurs when select appropriate mean for the selected condition called Ambiguity.

If a Context-Free Grammar can be drawn with more than one form then the ambiguity occurs. There are right most derivations and left the most derivation of parse trees can be formed from the grammar which can cause the ambiguities.

Problem:

Check whether the grammar G with production rules −.

S → S+S | S*S |S| b

is ambiguous or not.

 Solution:

Let’s find out the derivation tree for the string “b+b*b”. It has two leftmost derivations.

Derivation 1 − S → S+S → b +S → b+ S*S → b+b*S → b+b*b.

Parse tree 1 –:

Derivation 2 − S → S*S → S+S*S → b+ S*S → b+b*S → b+b*b.

Parse tree 2 –

CFG- Context-Free Grammar