2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Is this a formal grammar or one fed into a parser generator? Which parsing automaton/algorithm is used? $\endgroup$ – Raphael Dec 6 '14 at 11:26
  • $\begingroup$ It's a formal language, I did this derivation by hand. $\endgroup$ – Xpl0 Dec 6 '14 at 12:29
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is the direction of parsing relevant? The tree that is obtained determines the syntax in this case, and the tree is evaluated bottom-up. $\endgroup$ – Hendrik Jan Dec 6 '14 at 12:57
  • $\begingroup$ @HendrikJan Yes, see previous comment. The parsing direction does not matter, and that is true even without building a parse tree, though it is always implicitly there. $\endgroup$ – babou Dec 6 '14 at 13:41
  • $\begingroup$ It's now all very clear, thanks babou (and also Raphael)! $\endgroup$ – Xpl0 Dec 6 '14 at 13:55
-3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ The order of the rules is merely a choice of presentation and makes no formal difference to the grammar. $\endgroup$ – David Richerby Dec 6 '14 at 10:25
  • $\begingroup$ @DavidRicherby care to give a reference? $\endgroup$ – user4275686 Dec 6 '14 at 10:32
  • $\begingroup$ en.wikipedia.org/wiki/Context-free_grammar#Formal_definitions $\endgroup$ – David Richerby Dec 6 '14 at 10:51
  • $\begingroup$ @user4275686 One way to read the rules of a context free grammar is as a set of equations where non-terminals are variables, terminals are constants, and these variables take their value in the set of languages over the given alphabet. As the name indicates, a set of equation is just a set, and need not be ordered. That is always true, afaik, of sets of equations, BTW, the language defined is the smallest solution for the variable corresponding to the initial symbol. $\endgroup$ – babou Dec 6 '14 at 17:13

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.