Question

<expr> ::= <expr> + <expr> | <expr> - <expr> | <expr> * <expr> | <expr> / <expr> | <expr> ^ <expr> | <expr> ! | <expr> % | ( <expr> ) | ~ <expr> | <NUMBER> | E | PI |

Revise BNF grammar to qualify these requirements :

(i)

precedence

!,% >= ~ >= ^ >= *,/ >= +,−

(ii)

Left associativity : +, -, *, /

Right associativity : ^

Answer 1

Solution:

1. In order to preserve the precedence of operators the productions of BNF grammar must follow the order.

the high priority operator's expression must be specified in the rear production. Least priority operator expression is specified in the begining production,

for example. if E->E+E | E*E | id is the grammar and precedence order is * >= + then productions will be

E->E+T | T

T->T*F |F

F->id

2.if the operator is left associative then production of concerned expression must have left recursion , otherwise if the operator is right associative the production of concerned expression must have right recursion... in the above example +,* are left associative , because the productions have left recursion.

based on the least precedence and associativity the productions can be defined as follows.

3)    operators +, - are of least precedence and are left associative ,from steps 1 and 2,

<expr1>::=<expr1>+<expr2> | <expr1> - <expr2> | <expr2>

4)next least precedence is given to *, / and are left associative.

<expr2>::=<expr2>*<expr3> | <expr2> / <expr3> | <expr3>

5)next least precedence is given to ^ and is right associative hence the production is

<expr3> ::=<expr4> ^ <expr3> | <expr4> /*production contains right recursion */

6)in ascending order the next operator is ~ and its production can be

<expr4> ::=~<expr5> | <expr5>

7)the high priority operator is either ! or % the productions are

<expr5> ::= <expr5> ! | <expr5>% | <expr6>

8) the remain righthand sides can be written as

<expr6> ::=(<expr1>) | <NUMBER> | E | PI

based on above steps the given BNF grammar cab be converted in the following manner.

<expr1>::=<expr1>+<expr2> | <expr1> - <expr2> | <expr2>

<expr2>::=<expr2>*<expr3> | <expr2> / <expr3> | <expr3>   

<expr3> ::=<expr4> ^ <expr3> | <expr4>

<expr4> ::=~<expr5> | <expr5>

<expr5> ::= <expr5> ! | <expr5>% | <expr6>

<expr6> ::=(<expr1>) | <NUMBER> | E | PI