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!

[cadet1620]

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

[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?

[cadet1620]

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

[JG1993]

That's one small step closer to understanding how it works.  Thanks again.

[jrd]

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

[cadet1620]

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