Expression evalution and operator priority

7 messages
Open this post in threaded view
|

Expression evalution and operator priority

 Hi, I am just trying to understand the expression evaluation and RPN. I am a little bit confused with example in the picture below.   If I correctly understand from the chapter 9, there is no operator priority. So shouldn't then the above example be like this: push x push 2 push y push z neg call g add push 5 call multiply i.e. we add the x+g(2,y,-z) first and then multiply it by 5? Thanks!
Open this post in threaded view
|

Re: Expression evalution and operator priority

 Administrator Your evaluation is correct for strictly left-to-right precedence. "No priority" really means undefined. From 9.2.5 in the book: Order of evaluation and operator priority: Operator priority is not defined by the language, except that expressions in parentheses are evaluated first. Thus an expression like 2+3*4 may yield either 20 or 14, whereas 2+(3*4) is guaranteed to yield 14. It's even uglier: -2+3 can be evaluated as (-2)+3 = 1 or -(2+3) = -5!   It looks like the parse tree represented in figure 11.4 is for standard arithmetic precedence. The good news is that if you use the recursive descent parsing/compiling technique presented in chapter 10, you don't actually need to build and traverse parse treesâ€”the call stack is effectively the tree and the program flow the traversal. --Mark
Open this post in threaded view
|

Re: Expression evalution and operator priority

 So if I had that expression in a code, I would compile the way I did it with the left-to-right precedence, right?
Open this post in threaded view
|

Re: Expression evalution and operator priority

 Administrator Yes, that would be OK (and that's what my compiler does by default). Over the years, I have added a number of options to my compiler, including options for standard arithmetic precedence and warnings about missing () in the default precedence mode. --Mark
Open this post in threaded view
|

Re: Expression evalution and operator priority

 That's one small step closer to understanding how it works.  Thanks again.
 Administrator In a Recursive Descent compiler, the parsing and compiling functions are one and the same. That is why the parsing routines recommended in chapter 10 are named "CompileEtc". Here's pseudocode for my CompileExpression(): ``` void CompileExpression() { /* Compiles := ( )* ENTRY: Tokenizer positioned on the start of the expression. EXIT: Tokenizer positioned after the expression. */ // Parse and compile the first . CompileTerm() while current token is an { // Save the operator for code generation. operator = token.symbol token.next() // Parse and compile the next . CompileTerm() // Generate code for . switch (operator) { case '+': vmWriter.WriteArithmetic(OP_ADD) case '-': vmWriter.WriteArithmetic(OP_SUB) // more code writers... } } ``` This code results in simple left-to-right operator precedence. If you want to compile standard precedence, you need to redefine syntax to reflect the desired precedence and write appropriate CompileSum(), CompileProduct(), etc. functions. See this post. --Mark