10.3.对表达式的处理

发表于 更新于 分类于 ， 阅读次数： 本文字数： 397 阅读时长 ≈ 1 分钟

\(11.3.\)Handling Expression

1.Expressions definition review

2.Parse tree

  • infix: that's sort of ingrained into our brains in elementary school.
  • prefix: that's what we do when we define functions: we put the function name and then a list of operands or parameters or arguments.
  • postfix: that's closely related to the stack machine. Say we want to do an add operation, we push x, push y and finally pop, this is exactly postfix.

3.Generating code for expressions

  In high level language like Java, we declare expressions in infix, and the target language, so our compiler has to translate from infix to postfix. Here are two ways to do this:

  1. We generate a parse tree through the infix expression.
  2. The parser takes the source code and produces XML code from it.
  3. We go through every node in the parse tree in a certain order.

  To convert the parse tree into the VM code, we use the deep-first tree traversal algorithm:

  • We go all the way down, and when we hit a terminal leaf, we process it.

  However, the parse tree we have may be gigantic, so it may be better not to have the side effect. We will use the following code generation algorithm instead:

  • Whatever is the mapping of x is dictated by the symbol table which is always in the background of the co-generation algorithms.

  The nice thing about this algorithm is that not only does it capture the semantics of the input expression, it also computes the value of this expression. That is, in the runtime the value of the expression is going to be placed on the stack.

4.From parsing to code generation

  In the previous project, we develop a Jack Analyzer that generate static XML code, but in this part, the XML is completely irrelevant now. Instead, we generate actual executable VM code. And there are some general guidelines on what has to be done:

  • We have operator priority in some operation, such as mathematics operations (however, Jack doesn't have this). Since the compiler will ignore it, we ourselves must take this into consideration.
  • Once we have parenthesis in Jack, we have to take operator priority into consideration. We have to make the code write algorithm work in the proper order as dictated by the parenthesis.