Context-free grammars and priority

Question

This grammar is supposed to give priority to multiplication:

• E -> E + T | T.
• T -> T * F | F.
• F -> x.

A derivation for "x + x * x" would be (unless I'm wrong):

E => E + T => T + T => F + T => x + T => x + T * F => x + F * F => x + x * F => x + x * x.

So how is multiplication given priority over addition? It appears that the addition is produced first.

Answer 1

You are correct that additions operator is produced first when you derive. But when you parse, you do the opposite (reduction), and the multiplications are recognized first, wich is precisely what you want.

THis need a bit of discussion, when you compare top-down and bottom up parsing, but basically the bottom of the tree must be know correct before the top can be.

More to the point, this is a consequence of the fact that the parse tree produced with such a grammar will be structured to conform the operator operand structure defined by priorities, up to idosyncrasies of a CF grammar definition, which are ironed out in an abstract syntax tree (AST). In other words, this gives the parse tree a shape that is close to the shape desired for the AST (Thanks to Raphael for suggesting comparison with the AST).

This is why such a grammatical definition is simpler to use to generate the AST. More importantly, it was much more convenient in older compilers and interpreters that did not use AST, as the parse tree reflected the priority structure.

For example, the parse tree for x + x * x is

   E
 / | \
E  +   T
|     /|\
T    T * F
|    |   |
F    F   x
|    |
x    x

And the AST for x + x * x is

   +
 /   \
x     *
     / \
    x   x

It is derivable from the parse tree by moving all operators up one edge on the preceding node, and then ignoring all non-terminals, making each linear downward path a single edge. Essentially the same shape.

This AST is the expression tree defined by the priorities, from which the meaning of the expression can be derived (by homomorphism), from which it can be evaluated or compiled.

Answer 2

I think this is the case of ambiguous grammar.In the rules' list addition is definitely above multiplication and that needs to be rectified,multiplication should go above addition.