Question about expression compilation

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question about expression compilation

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 + ...".
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question about expression compilation

Francisco José Tornay Mej
I see. Yes, it's an elegant solution.

Thanks for your reply, Warren.
dlk
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question about expression compilation

dlk
In reply to this post by Warren Toomey
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question about expression compilation

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