Ambiguity in CFG

Advertisement

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

Advertisement

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 –:

Parse tree

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

Parse tree 2 –

Parse tree 2

CFG- Context-Free Grammar

Advertisement

Zitoc

We are a team of writers, researchers, and editors who are passionate about helping others live their best lives. We believe that life is a beautiful gift. We try to live our lives to the fullest and enjoy every moment. We are always learning and growing, and we cherish the relationships we have with our family and friends.