Question

Convert an example EBNF grammar into a BNF grammar. For an example BNF grammar, determine if it is ambiguous.Rewrite an ambiguous grammar so that it is unambiguous.

Answer 1

Lets take an example of EBNF grammar:

.BNF

<expr>   :: =            <expr> + <term>

                                 | <expr> - <term>

                                 | <term>

<term> :: =            <term> * <factor>

                                | <term> / <factor>

                                | <factor>

Lets take an example of EBNF grammar:

Syntax for EBNF:-

.EBNF

<expr> :: =      <term> { (+ | -) <term> }

<term> :: =     <factor> { ( * | / ) <factor> }

<factor> :: = <exp> { ^<exp> }

<exp>       :: = (<expr> ) | id | literal

Above symbols denotes as:-

A| B      Either A or B

A*        Zero or more instance of A

A+        One or more instances of A

A?         Zero or one instance of A

For example: -

<expr> :: =      <term> { (+ | -) <term> }

<term> :: =     <factor> { ( * | / ) <factor> }

<factor> :: = <exp> { ^<exp> }

<exp>       :: = (<expr> ) | id | literal

Ex: -    (8+z )– (2*a)

Converting this to BNF grammar:-

<expr>   :: =            <expr> + <term>

                                 | <expr> - <term>

                                 | <term>

<term> :: =            <term> * <factor>

                                | <term> / <factor>

                                | <factor>

Ex:- -    (8+z )– (2*a)

For an example BNF grammar,

Now we will determine if it is ambiguous.Rewrite an ambiguous grammar so that it is unambiguous.

Let a grammar be:

E :: = E + E | E * E

E :: = id

Then with the help of this diagram we will see it is ambiguous.

For an example BNF grammar,

Now we will determine if it is ambiguous.Rewrite an ambiguous grammar so that it is unambiguous.

Let a grammar be:

E :: = E + E | E * E

E :: = id

Then with the help of this diagram we will see it is ambiguous.

Id+ id = id

It has 2 operator on either side of it.Which operator should we associate this with?

So there is an ambiguity.

So we can make write this ambiguous grammar into unambiguous:

E :: = E + T/T

T :: = T * F/ F

F :: = id

id + id * id