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

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

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.

## 0 comments

Post a Comment