Ambiguity of CFG

Context Free grammar is used in compiler design to make compilers. But there can be ambiguity in recognising the grammar by the compiler i.e., there will be 2 different derivation trees for the same string in a grammar.

For example:

The CFG for arithmetic expression only for addition and multiplication  will be

S   → id = S₁                     (id is another CFG for accepting identifiers)

S₁ → S₁ + S₁ | S₁ * S₁ | id

The derivation tree of this CFG can be in 2 ways

                               

 

Here either addition can be performed first or multiplication can be performed. But according to BODMAS rule multiplication has to be done first. So this kind of CFG generates an ambiguity. To solve this, the same CFG can be written using brackets in this form.

S → id = S₁                     (id is another CFG for accepting identifiers)

S₁ → S₁ + T | T

T → T * F | F

F → ( S₁ ) | id

This grammar removes ambiguity.

Another example

Write a grammar for condition statements of if and else used in C languages.

The grammar can be written as follows

S → i b { S } | i b { S } e { S } | id

Here

i is if.

b is the condition.

e is else

This grammar seems to be correct but it can generate ambiguous grammar.

Here the first if can correspond to the else of the nested if or the outer else. This causes the ambiguity. So the grammar can be written in this way to remove ambiguity

S → i b { S } e { S } | i b { S } | id

This removes the ambiguity by putting proper parenthesis.

Feel free to comment if you have any doubts related to this topic.

Recommended articles

Context Free Grammar

Regular Expressions

Introduction to finite automata