Question about expression compilation

[Francisco José Tornay Mej]

The book gives a tree traversing algorithm for compiling expressions in the case that no implicit operator priority exists. I was wondering about an elegant way of implementing this with implicit priority. Could anyone help?

Thanks

[Warren Toomey]

You can modify the original grammar to insert the implicit operator precedence. I will use BNF style below. Instead of defining a rule for an expression using all the operators, we could do:

level1expression: level2expression
                          | level2expression '+' level1expression
                          | level2expression '-' level1expression

level2expression: term
                          | term '*' level2expression
                          | term '/' level2expression

term: integerConstant | ......

Now, given the input "2 + 5 * 3", we would see that "2 + " matches the level1expression rule, but the right-hand side of the '+' is a level2expression "5 * 3". We would descend to the code to parse the level2expression "5 * 3" before we complete the parsing of the "2 + ...".

[Francisco José Tornay Mej]

I see. Yes, it's an elegant solution.

Thanks for your reply, Warren.

[dlk]

Those definitions seem to give right associativity rather than left associativity,
e.g. 'x - y + 2' would be interpreted as 'x - (y + 2)' rather than '(x - y) + 2'.
To represent the desired left-associativity one would use

level1expression: level2expression
                          | level1expression '+' level2expression
                          | level1expression '-' level2expression

level2expression: term
                          | level2expression '*' term
                          | level2expression '/' term

term: integerConstant | ......

However, then one has to worry about infinite regress if one makes a naive
recursive descent parser -- e.g., when parsing a level1expression, it may start
with a level1expression...

[dlk]

I think I missed the subtlety that even the associativity of expressions like 'x - y + 2' is undefined / implementation dependent for the Jack language ... so right associativity is probably OK.
Most programming languages that I'm used to choose left associativity for equal precedence operators.