Expression evalution and operator priority

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

Expression evalution and operator priority

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

Re: Expression evalution and operator priority

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

Re: Expression evalution and operator priority

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

Re: Expression evalution and operator priority

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

Re: Expression evalution and operator priority

JG1993
That's one small step closer to understanding how it works.  Thanks again.
jrd
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Expression evalution and operator priority

jrd
In reply to this post by cadet1620
Mark et al:

Is it possible for you to elaborate on this comment?

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

I'm having real trouble understanding the programming technique to implement the RPN/required stack processing.

To explain my confusion, my existing parser/XML writer/compilation engine generally reads each current token (in sequential order), calls whatever function required to process it, and outputs whatever the applicable result.  

However, for the first time in the overall compiler project, it doesn't seem possible to use my existing program - without adding alot of additional (and awkward code) to read entire expressions (or group of tokens as a larger unit to analyze them first) BEFORE resequencing them to process/write required RPM stack processing codes in correct order.  

In effect, I'm finding that I need to read full clusters of tokens all at once before correctly ordering/processing them - as opposed to the prior modules, where I could process tokens as they were read and using function recursion.  When I look at my latest code, it seems rather inelegant and hacked together, as opposed to continuing the flow of previous chapters and modules.

Any insight into this would be appreciated?  Also, any basic programming examples to get me properly oriented would be extremely helpful.

Thanks.

- JRD
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Expression evalution and operator priority

cadet1620
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 <expression> := <term> (<op> <term>)*

        ENTRY: Tokenizer positioned on the start of the expression.
        EXIT:  Tokenizer positioned after the expression.
        */
        
        // Parse and compile the first <term>.
        CompileTerm()

        while current token is an <op> {
            // Save the operator for code generation.
            operator = token.symbol
            token.next()
            
            // Parse and compile the next <term>.
            CompileTerm()

            // Generate code for <op>.
            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 <expression> syntax to reflect the desired precedence and write appropriate CompileSum(), CompileProduct(), etc. functions. See this post.

--Mark

Loading...