Write context free grammar for if-then-else statement

A context free grammar(CFG)[is sometime called Backus-Naur Form(BNF)] is a tuple where:

a. T is a set of terminals
b. N is a set of non-terminals
c. S is the start symbol in N
d. P is a set of production of the form

The grammar is:- ::=ifthen | ifthenelse

Consider the following grammar describing if/then/else statements .

S -> if E then S

S -> if E then S else S

S -> other

"other" just means some other kind of statement that is not an if/then/else statement.

Now consider input of the form

if e1 then if e2 then s1 else s2

Note that e1, e2 represent strings of terminal symbols generated by the E production, and s1 and s2 represent strings of terminal symbols generated by the E production.

The grammar is ambiguous because there are two possible parse trees for the input.

Consider the following derivations of the input:

Note: leftmost derivations

Derivation 1
=============
S S -> if E then S
if E then S S -> if E then S else S
if E then if E then S else S

Derivation 2
=============
S S -> if E then S else S
if E then S else S S -> if E then S
if E then if E then S else S

Here are the parse trees:

Generally, the first parse tree is the one we want: an else should always be matched with the closest unmatched then.

Someone can fix the problem by rewriting the grammar:

S -> M

S -> O

M -> if E then M else M

M -> other

O -> if E then S

O -> if E then M else O

The M nonterminal means a "matched" statement in which there are no occurrences of then that are not matched by an else.

--------------------------------------------------------
Human do error, please email:- webmaster@piyadas-world.com if you find any. Please visit http://www.piyadas-world.com for more resource.