I have the following basic BNF grammar:

<A>   -->  <id>  = <E>
<id>  -->  A | B | C | D | F
<E> --> <E> + <T> | <T>
<T> --> <T> * <F> | <F>
<F> --> <E> | <id>

Operator (*) should have higher precedence over (+). However, see this statement:

A = A + B + C + D * F

The leftmost derivation (and parse tree) indicate the opposite! i.e., (+) has higher precedence than (*) since it will show up lower in the parse tree!

What am I missing here?

  • $\begingroup$ Normally the last production would be <F> --> ( <E> ) | <id> in order to allow parenthesised expressions. As written, your grammar is highly ambiguous. $\endgroup$ – rici Jul 2 '18 at 15:06

Due to the path

<E>  ->  <T>  ->  <F>  ->  <id>,

you can completely circumvent the "check" for whether there are *.

Think about it in a bottom up manner: only if there's no * nearby can you parse a +.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.