Question

This BNF grammar defines expressions with three operations, *, -, and +, and the variables “a”, “b”, “c”, and “d”.

<expr> ::= <thing> | <thing> * <expr>
<object> ::= <element> | <element> – <object>
<thing> ::= <object> | <thing> + <object>
<element> ::= a|b|c|d|(<object>)

a) Give the order of precedence among the three operations.

b) Give the order (left-to-right or right-to-left) of execution for each operation.

c) Explain how the parentheses defined for the nonterminal <element> may be used in these expressions. Describe their limitations.

Answer 1

ANSWER:

For better understanding, re-writing the grammar as:

< expr >::=< thing > * < erpr > \ < thing > < thing >..=< thing > + < object > \ < object > < object >:<element > - < object > |<element > abjcId(< object >) < element >:

a)

If we draw the parse tree for an expression, ' - ' sign will occur at the bottom with ' + ' above it then ' * ' .

Since the rule producing ' - ' is at the lowest level, so it will have highest precedence, followed by ' + ' and then ' * ' .

b)

< expr >..=< thing > * < expr > < object >..=< element >-< object >

These productions are right recursive, so ' * ' and ' - ' are right recursive means their order of execution will be right to left.

< thing >::=< thing > + < object >

This production is left recursive so order of execution of '+' is left to right.

c)

Parenthesis can be used to give the expression inside the parenthesis higher order of precedence.

But on observing the grammar here (<object>), parenthesis can only contain expression involving subtractions as <object> can only produce subtraction part.

So limitation is that parenthesis can only have expressions that involve subtraction.