expression evaluation into vminstructions not that straightforward to me

[Rather Iffy]

When i try to use my compilationengine from project 10 in an extremely  straightforward way to translate a Jack expression
i get the VM instructions in infix order and not in postfix order. So it isn't that simple!

I am trying to figure out what to do next.
Some thoughts.

The production for "expression" in the Jack grammar is:
    expression : term(op term)*                       ( see page 209)

Yet the expression evaluation procedure codeWrite(exp) seems to be based on the idea that a Jack expression,
for instance with a binary operation, is decomposable in a left and a right sub-expression with the binary operator in between  :
    expression : expression1 op expression2   (see page 232)

I could use another grammar for Jack expressions , but when i take the one suggested by the codeWrite procedure,
i end up with a problematic left recursive grammar.

Or should i let my compilationengine built a tree while parsing an expression , like the one at page 231 ?
Then at leaving CompileExpression i could traverse the tree in post-order and produce the vm instructions in the right order.
This seems quite a lot of work. And i am not so familiar with trees.

Am i overlooking a simple solution?
I would like to get some suggestions on this.
--Chrit

 

[ybakos]

I first took the tree approach and I backed out, because it revealed more challenges during code generation.

It sounds like you've understood the grammar, but I'm not sure why it seems so problematic. I'm not in front of my code, but, given that your parser detects an expression, you would:

writeTerm(term1); // and term could itself be an expression
writeTerm(term2); // same for the right term
writeOp(op);

Each respective writeTerm operation may indeed recurse, but that's a good thing, no? Each will continue to pars their terms until they reach no sub-expressions, and return.

Let me know if I'm not making sense.

[cadet1620]

[Corrected per WBahn's response below.  (Thanks for spotting that in the textbook.)]

Since operator precedence is expressly undefined (9.2.5), you are free to parse expressions left to right in a loop:

    CompileExpression()
    {
        /* Compiles <expression> :=
                <term> (op <term)*
    
            ENTRY: Tokenizer positioned on the expression.
            EXIT:  Tokenizer positioned after the expression.
        */
        CompileTerm()
        while tokenizer.tokenType is TK_SYMBOL and tokenizer.symbol is one of "+-*/&|<>="
        {
            operator = tokenizer.symbol;
            tokenizer.NextToken()
            CompileTerm()
            CompileOperator(operator)
        }
    }

This will result in left-to-right operator precedence, except that the unary operators '-' and '~' will have precedence over the binary operators.

--Mark

[Rather Iffy]

Thank you for your code example.
The "trick"  that i was looking for is clearly in it:
Storing the op_code and resume processing it right after compiling the upcoming term.
I take your word on it that it works correctly in this particular " expression : term (op term)* " case.

I much prefer recursion above iteration in this case because the procedure call structure of the recursive descent parsing algorithm mimics the Jack grammar exactly, 1 to 1.
The grammar guides my programming completely , so i can not make mistakes.
And i trust the grammar.

So my compileExpression procedure is still recursive, follows the Jack grammar literally,
incorporates your leapfrogging solution, and uses a stack for storing the op_codes and  for popping them at the right time.
And it works, the translation of project 11 case SEVEN is getting better and better.  

Thanks for your help.

--Chrit

[Rather Iffy]

The Jack language grammar for the Jack expression at page 209  is:
     expression: term(op term)*

The codeWrite code example at page 232 suggested to me to try an alternative production :
     expression: expression op expression

That production is left recursive. "Expression" recurs as the first, most left, symbol in the right hand side of the production

In a recursive descent parser the corresponding procedure compileExpression would look like this:
    compileExpression()
          compileExpression()
          compileOp()
          compileExpression()

The problem with this procedure it that it first calls itself and then again calls itself and then again calls itself ...
Because there is no call to the tokenizer the scanningproces makes no progress so that the situation will never change
so the calling will go on forever.

That is why i cannot use that alternate production for a Jack expression.

But re-reading the codeWrite code example i understand now that "expression" is used here to mean  "expression or term"
which is in the context of programming a compiler for the Jack language ,
which makes clear distinction between "expressions" and "terms", rather confusing.

Thanks for your help.

[cadet1620]

Rather Iffy wrote

The Jack language grammar for the Jack expression at page 209  is:
     expression: term(op term)*

The codeWrite code example at page 232 suggested to me to try an alternative production :
     expression: expression op expression

...

But re-reading the codeWrite code example i understand now that "expression" is used here to mean  "expression or term"
which is in the context of programming a compiler for the Jack language ,
which makes clear distinction between "expressions" and "terms", rather confusing.

This confusion between the grammar elements and common English is why I like to use <> quoting for grammar elements.

I think that the grammar that reflects the structure and specified precedence of Jack expressions might be:
    <expression> := <term> | ( <expression> <op> <term> )

[Back when I was learning this we still used typewriters, so we didn't have any font options. We had to be careful to make the distinction clear. I still use =variable= to quote variable names and function() to refer to functions in code comments.]

--Mark

[WBahn]

Several times in this thread it has been stated that there is a specified precedence for evaluating expressions. But the authors very explicitly state that there is no such specification. The algorithm they suggest (p231) results in a right-to-left evaluation of operations. But this is only a suggested algorithm (and very arguably the simplest implementation).