

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


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 righthand 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 + ...".


I see. Yes, it's an elegant solution.
Thanks for your reply, Warren.


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 leftassociativity 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...


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.

