How do I remember the "op" symbol in the "op (expression)"?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

How do I remember the "op" symbol in the "op (expression)"?

Ichiro
Hi,

I am working on compiling the Square programs and having difficulties writing "op" commands when the op is followed by multiple parentheses.

My CompileExpression() is like this:
           CompileTerm()
           //CompilationEngine part
           while token[i] in op:
                    if token[i] =='<':
                       write(<symbol> + '<' + </symbol>)
                    elif
                    .....
                    else:
                       write(<symbol> + token[i] + </symbol>)
                    CompileTerm()
           //VMwriter part starts here
                    if token[i-l]=='+':
                       vm.write('Add')
                    .......

As shown above, token[i-l] is used to recall op symbols. When compiling the Seven Jack program, 'l' is fixed as 6 because '+' appears 6 before the end of (2*3).

The Square.jack program has more complex expressions like:
  if (((y+size)<254) & ((x+size)<510))
How can I recall '&' after compiling the following expression: ((x+size)<510)?

Please let me know if I have to elaborate on my issue.

Best Regards,
Ichiro
Reply | Threaded
Open this post in threaded view
|

Re: How do I remember the "op" symbol in the "op (expression)"?

WBahn
Administrator
The intent is to compile the program using recursion (the compiler design they are steering you towards is known as a "recursive descent" compiler.

Notice that the definition of an expression in the Jack grammar is

expression => term (op term)*

The (op term)* means that the sequence op term can appear zero or more times. Thus an expression could be

expression => term
expression => term op term
expression => term op term op term

and so on.

What you want your compiler to do is be able to have a function that can compile a term (note that CompileTerm() this is one of the functions in the API specification).

When you call CompileTerm(), its job is to generate the code for exactly one 'term' and put the result of evaluating that term on the top of the stack.

So when you call CompileExpression and you have

term1 op1 term2

the result should be that you call CompileTerm() and it handles term1. Then your CompileExpression() function recognizes op1 and so it remembers what op1 is and called CompileTerm() which will take care of term2. Once it is done, the result of term2 is on the top of the stack and the result of term1 is the next thing down. So now CompileExpression just needs to add the code to execute op1 on the top two things on the stack.

If you have a longer expression, such as

term1 op1 term2 op2 term2

then you can just stay in a loop doing the above tasks until your CompileExpression() function doesn't find an op. The result is that all of the operators become left associative. There are other ways to do it and the main alternative results in the operators all being right associative. The Jack language spec very carefully avoided defining operator precedence or associativity specifically to let you implement your compiler in whatever way is easiest for you. The result, however, is that Jack programs that do not use parens to force the desired order of operations for an expression may evaluate differently on different compilers.

Notice that there is nothing here that addresses parentheses. That's because parens are not involved in the grammar rules for an expression. They are dealt with at the 'term' level.

When you call CompileTerm(), it has to look at the next token and decide which of the grammar rules to process. When you have an open paren, there is only one possible rule, namely

term => '(' expression ')'

So when you see an open paren, you throw it away, call CompileExpression(), and then look for and throw away the following close paren, and return.

Done. That's all there is to it.

Don't make it harder than it is.


Reply | Threaded
Open this post in threaded view
|

Re: How do I remember the "op" symbol in the "op (expression)"?

Ichiro
I was making it harder than it is. I finally managed to make it.

I did not understand the local scope of Python and thought that op1 would be replaced by op2 or op3, etc. However, as op1 is the local variable within CompileExpression(), it will not be replaced by the new operator in another CompileExpression() when there are multiple operators.

Reply | Threaded
Open this post in threaded view
|

Re: How do I remember the "op" symbol in the "op (expression)"?

WBahn
Administrator
Glad you got it working. Even more valuable is the deeper understanding of recursion and how local variables work. You should be able to relate all of this to the function call stack and how information in one call to a function is kept physically distinct from the information is subsequent recursive calls to the same function.