从0到1构建计算机(9/12)--实现编译器

本篇实现Jack的编译器，也是从0到1构建计算机系列最复杂的一篇。编译器的实现本身是非常复杂的，但得益于Jack超简洁的语法，我们回避掉了很多复杂的问题。总体上Jack编译器是一个完整的编译器，它包括词法分析，语法分析，语义分析，代码生成等重要主题。

高级语言为什么能够被编译器理解和编译？因为高级语言是按照某种规则的语法（上下文无关语法）组织的，结构上层次化的语言。程序的每个类，每条语句都是符合某种语法规则的，所以我们反过来能够使用这些语法规则对其进行准确地解析，而我们日常使用的自然语言则不太受语法的严格的约束，所以用算法解释自然语言会更困难。

词法分析

程序基本上由语句组成，语句由单词和符号组成，每个单词或符号都有它要表达的含义：或是某种预算操作，或是某块内存的指针，或是指明当前语句是那种类型等等。编译器要做的第一件事情就是把语句拆解成一个个单词或符号，即词法分析。

Jack语法由一下五类单词构成：

关键字：多用于指明当前语句的类型、属性。
符号：算数逻辑运算符号、功能符号等。
整型数字：0...32767
字符创：“”括起来的字符串。
字面量：类名、变量名等。

下面以一个程序举例：

实现

词法分析的过程并不复杂。先删除输入程序中的注释代码，然后通过使用Ruby的StringScanner工具和一些正则操作把源程序拆解成以上五种类型的单词即可。我们用JackTokenizer来实现Jack的词法分析：

JackTokenizer接口设计：

constructor：输入源程序，完成词法分析
hasMoreToken：是否还是token
advance：token游标前进一位
tokenType：当前token类型
keyword：返回当前关键字类型的token
symbol：返回当前symbol类型的token
intValue：返回当前int类型的token
stringValue：返回当前string类型的token
indentifier：返回当前indentifier类型的token

词法分析关键代码如下：

$KEYWORDS = ["class", "method", "function", "constructor", "int", "boolean", "char", "void", "var", "static", "field", "let", "do", "if", "else", "while", "return", "true", "false", "null", "this"]
$SYMBOL = ["{", "}", "(", ")", "[", "]", ".", ",", ";", "+", "-", "*", "/", "&", "|", "<", ">", "=", "~"]

class JackTokenizer

def analysizeFile(file)
  #删除所有注释
  file = file.gsub(/((?:\/\*(?:[^*]|(?:\*+[^*\/]))*\*+\/)|(?:\/\/.*))/, '').split.join(' ')

  #代码转成token
  @tokens = self.scanTextToToken(file)
  self.writeTokensTofile(@tokens)
end

def scanTextToToken(text)
  tokens = []
  scanner = StringScanner.new(text)
  while !scanner.eos?
    # 扫描字符串类型
    stringToken = scanner.scan(/"[^"]*"/)
    if stringToken
      tokens << stringToken
      scanner.scan(/\s+/)
      next
    end

    # 扫描symbol
    symbolToken = scanner.scan(/\{|\}|\(|\)|\[|\]|\.|\,|\;|\+|\-|\*|\/|\&|\||\<|\>|\=|\~/)
    if symbolToken
      tokens << symbolToken
      scanner.scan(/\s+/)
      next
    end

    # 扫描其他tokenotherToken
    otherToken = scanner.scan_until(/\s+|\{|\}|\(|\)|\[|\]|\.|\,|\;|\+|\-|\*|\/|\&|\||\<|\>|\=|\~/)
    if otherToken
      otherToken = otherToken[0..otherToken.length-2]
      scanner.pos = scanner.pos-1
      tokens << otherToken
      scanner.scan(/\s+/)
      next
    end
  end

  return tokens
end

def writeTokensTofile(tokens)
  @tokenOutputFile.write("<tokens>\n")
  tokens.each do |token|
    if self.isKeyword(token)
      @tokenOutputFile.write("<keyword> #{token} </keyword>\n")
    elsif self.isString(token)
      token = token[1..token.length-2]
      @tokenOutputFile.write("<stringConstant> #{token} </stringConstant>\n")
    elsif self.isSymbol(token)
      token = self.convertSymbol(token)
      @tokenOutputFile.write("<symbol> #{token} </symbol>\n")
    elsif self.isNumber(token)
      @tokenOutputFile.write("<integerConstant> #{token} </integerConstant>\n")
    else
      @tokenOutputFile.write("<identifier> #{token} </identifier>\n")
    end
  end

  @tokenOutputFile.write("</tokens>\n")
  @tokenOutputFile.close()
end

def isKeyword(token)
  return $KEYWORDS.include? token
end

def isSymbol(token)
  return $SYMBOL.include? token
end

def isNumber(token)
  return token.match(/\d+/)
end

def isString(token)
  return token.match(/"[^"]*"/)
end

end

语法分析

我们的编译器很聪明，已经掌握了Jack的单词，接下来该学习语法了。语法分析的任务是分析源程序类、方法的结构和每条语句的组成，分析的结果以抽象语法树的方式呈现，有的编译器会显示地构造出抽象语法树（用于进一步代码生成和错误报告），有的编译器则隐式地构造抽象语法树，即实时的生成代码和错误报告，不必在内存中维护整个树的数据结构，我们的编译器属于后者（但我们在实现的过程中仍会生成一个xml格式的抽象语法树，用于验证我们的语法分析程序是否正确）。

上下文无关语法

几乎所有的编程语言，以及大多数用于描述复杂文件的其他形式的语言，都可以使用上下文无关语法描述。上下文无关语法是一组递归式的，树状结构的语法规则，用来指定语法中的语法元素如何由更简单的元素组成。上下文无关语法由终结符和非终结符两种元素构成，例如针对语句：while (count <= 100) { count ++; …}。while、(、count、++ 等符号都属于终结符，因为它们已经无法再继续分割，是上下文无关语法世界的原子级存在；同时终结符也可以互相组合成更高级的非终结符，例如 count <= 100 组成了一个expression，count ++; 组成了一个statement，多个statement又可以组成statementSequence等，expression、statement、statementSequence都属于非终结符，他们是可以再向下分割的。语法分析过程就是揭示程序中非终结符与非终结符，非终结符与终结符关系的过程。

Jack非终结符

Jack的终结符比较简单，我们主要来了解一下非终结符，Jack的非终结符主要可以分为3类：程序结构类、语句类、表达式类。

程序结构类的非终结符用于分析class的结构，变量声明的结构，函数声明、函数实现等的结构：

先声明类名，然后是若干变量声明（classVarDec），然后是若干函数的几个（subroutineDec）。
classVarDec由变量属性、变量类型、变量名三个终结符构成
subroutineDec由3种函数声明，参数列表，函数体实现（subroutineBody）构成
函数体实现由若干局部变量声明和若干语句构成
省略…参考下图

语句类的非终结符用于分析语句，包括：if, while, let, do, return 5中语句。

表达式类的非终结符用于分析表达式，表达式是Jack三种非终结符最复杂的一种。一个表达式可以有一个项或多个项构成；每个项可能是数字、字符串、关键字、变量、数组、或者是函数调用，甚至是用括号括起来的另一个表达式。

递归下降算法

有很多算法可以用来构建语法分析树，递归下降算法是比较明显和简单的一种。递归下降算法自顶向下地构建抽象语法树，碰到语法中的非终结符时，用相应的语法分析函数对其进行处理。例如下图中，处理while语句时，先调用compileWhileStatement函数，代表语法树生成了一个while语句节点，然后处理while语句的具体实现，由于while中又包含了其他非终结符，所以需要继续递归的调用其他语法分析函数，知道非终结符全部由终结符组成时return。

实现

语法分析程序从左到右的读取词法分析器的token输出，遇到非终结符则对其进行展开，如果该非终结符仍由其他非终结符构成，则深度优先的递归展开这些非终结符，直至非终结符全部由终结符构成为止。语法分析部分完整的实现较长，这里仅举几个非终结符的语法分析过程。

class CompilationEngine
  #compile method
  #编译整个类
  def compileClass
    @outputfile.write("<class>\n")
    @tokenizer.advance()
    self.writeKeyword() #class
    @tokenizer.advance()
    self.writeIndentifier() #className
    @tokenizer.advance()
    self.writeSymbol() #{
    @tokenizer.advance()
    self.compileClassVarDec() #classVarDec*
    self.compileSubroutine() #subroutine*
    self.writeSymbol() #}
    @outputfile.write("</class>\n")
  end

  #编译静态变量或成员变量的声明
  def compileClassVarDec
    isVar = @tokenizer.tokenType == "KEYWORD" && (@tokenizer.keyword() == "static" || @tokenizer.keyword() == "field")
    while isVar
      @outputfile.write("<classVarDec>\n")
      self.writeKeyword() #(static|field)
      @tokenizer.advance()
      self.writeType()
      @tokenizer.advance()
      self.writeVar() #varName or varNames
      @tokenizer.advance()
      isVar = @tokenizer.tokenType == "KEYWORD" && (@tokenizer.keyword() == "static" || @tokenizer.keyword() == "field")
      @outputfile.write("</classVarDec>\n")
    end
    return
  end

  #编译局部变量
  def compileVarDec
  ...
  end

  def compileSubroutine
    isSubroutine = @tokenizer.tokenType == "KEYWORD" && (@tokenizer.keyword() == "constructor" || @tokenizer.keyword() == "function" || @tokenizer.keyword() == "method")
    while isSubroutine
      @outputfile.write("<subroutineDec>\n")
      self.writeKeyword() #(method type)
      @tokenizer.advance()
      if @tokenizer.tokenType == "KEYWORD" && (@tokenizer.keyword() == "int" || @tokenizer.keyword() == "char" || @tokenizer.keyword() == "boolean" || @tokenizer.keyword() == "void")
        self.writeKeyword() #(basic type)
      elsif @tokenizer.tokenType == "IDENTIFIER"
        self.writeIndentifier() #(class type)
      end
      @tokenizer.advance()
      self.writeIndentifier() #method name
      @tokenizer.advance()
      self.writeSymbol() #(
      @tokenizer.advance()
      self.compileParameterList() #parameterList
      self.writeSymbol() #)
      @tokenizer.advance()
      self.compileSubroutineBody() #subroutineBody
      @outputfile.write("</subroutineDec>\n")

      @tokenizer.advance()
      isSubroutine = @tokenizer.tokenType == "KEYWORD" && (@tokenizer.keyword() == "constructor" || @tokenizer.keyword() == "function" || @tokenizer.keyword() == "method")
    end

    return
  end

  #编译参数列表
  def compileParameterList()
  ...
  end

  #编译函数体
  def compileSubroutineBody()
  ...
  end

  def compileStatements
  ...
  end

  def compileLet
  ...
  end

  def compileIF
  ...
  end

  def compileWhile
  ...
  end

  def compileReturn
    @outputfile.write("<returnStatement>\n")
    self.writeKeyword() #return
    @tokenizer.advance()
    if @tokenizer.symbol() == ";" #数组
      self.writeSymbol() #;
    else
      self.compileExpression()
      self.writeSymbol() #;
    end
    @outputfile.write("</returnStatement>\n")
  end

  def compileDo
  ...
  end

  def compileSubroutineCall
    self.writeIndentifier() #方法名或类对象或实例对象
    @tokenizer.advance()
    if @tokenizer.symbol() == "(" #调内部方法分支
      self.writeSymbol() #(
      @tokenizer.advance()
      self.compileExpressionList()
      self.writeSymbol() #)
      @tokenizer.advance()
      self.writeSymbol() #;
    elsif @tokenizer.symbol() == "." #调外部方法分支
      self.writeSymbol() #.
      @tokenizer.advance()
      self.writeIndentifier() #方法名
      @tokenizer.advance()
      self.writeSymbol() #()
      @tokenizer.advance()
      self.compileExpressionList()
      self.writeSymbol() #)
      @tokenizer.advance()
      self.writeSymbol() #;
    end
  end

  def compileExpression
    @outputfile.write("<expression>\n")
    self.compileTerm()
    termEnd = !($OPETATOR.include? @tokenizer.symbol())
    if !termEnd
      self.writeSymbol() #操作符
      @tokenizer.advance()
      self.compileTerm()
      termEnd = !($OPETATOR.include? @tokenizer.symbol())
    end
    @outputfile.write("</expression>\n")
  end

  def compileExpressionList
  ...
  end

  def compileTerm
  ...
  end
end

语义分析和代码生成

语法分析也是语义分析的一部分，我们知道了语法的类型就知道了它所要表达的一部分含义，例如我们知道了它是if或while语法，就知道将要进行一系列的分支跳转操作；知道了它是let语法，就知道了需要进行赋值操作；知道了它是do语法，就知道了需要进行函数调用操作。但语法分析表达的语义还不完全，例如let语句中赋值的对象是成员变量还是静态变量？do语法中调用的函数是类方法还是实例方法？这些都需要我们在语义分析过程中来进一步判断。当我们分析出一个语句的语义的时候，就可以生成对应的虚拟机代码了（在这里虚拟机语言充当了中间语言，本章的编译器是编译器的前端，虚拟机则是编译器的后端），且语义分析和代码生成是可以同时进行的。

程序的本质就是一系列对数据的操作，所以把高级语言编译成较低级的语言主要涉及两个主题：数据的翻译和命令的翻译。

数据翻译

变量

变量名代表了内存中的某个地址，是高级语言访问内存的接口。在Jack中变量类型包括：静态变量、成员变量、局部变量和参数变量。在高级语言中，变量名用字面量表示（identifier），而虚拟机语言并不认识这些符号，虚拟机语言只认识 static 0、static 1、local 0、argument 1、this 0 等符号，所以数据翻译部分的工作就是把高级语言中的变量名翻译成“段名 + index”的格式。

符号表

变量翻译的过程又涉及到了符号表。在编译过程中，我们先把符号加入符号表，然后在后续的编译过程中如果遇到了符号就去符号表查找符号对应的type（变量类型）, kind（属于哪个段）和index。

符号表中key(符号)和value的对应关系如下：

局部变量分配到 local 段
静态变量分配到 static 段
参数变量分配到 argument 段
通过 this index 的方式来访问成员变量
通过 that index 的方式来访问数组

符号表实现

符号表的实现比较简单，主要是支持符号的新增和查询功能，且需要管理每个段的index（段中新增了变量后index需要+1）。

startSubroutine：符号表重置，开辟新的子程序作用域
define         ：新增一条符号
varCount       ：符号表中某Kind的变量数量
kindOf         ：某符号的kind
typeOf         ：某符号的type
indexOf        ：某符号的index

class SymbolTable
  def initialize()
    @classTable = {}
    @subroutineTable = {}
    @symbolTableDic = {"static" => @classTable, "field" => @classTable, "arg" => @subroutineTable, "var" => @subroutineTable}
    @segementDic = {"static" => "static", "field" => "field", "arg" => "argument", "var" => "local"}
    @symbolIndex = {"static" => 0, "field" => 0, "arg" => 0, "var" => 0}
  end

  def startSubroutine()
    @subroutineTable.clear() #清空subroutineTable，开始编译下一个方法
    @symbolIndex["arg"] = 0
    @symbolIndex["var"] = 0
  end

  def define(name, type, kind)
    puts "存入符号表, name:#{name}, type:#{type}, kind:#{kind}"
    symbolTable = @symbolTableDic[kind]
    symbolTable[name] = [type, kind, @symbolIndex[kind]]
    @symbolIndex[kind] = @symbolIndex[kind] + 1
  end

  def varCount(kind)
    count = 0
    @classTable.each do |name, values|
      if values[1] == kind
        count = count + 1
      end
    end
    @subroutineTable.each do |name, values|
      if values[1] == kind
        count = count + 1
      end
    end
    return count
  end

  def kindOf(name)
    valus = self.findSymbol(name)
    return @segementDic[valus[1]]
  end

  def typeOf(name)
    valus = self.findSymbol(name)
    return valus[0]
  end

  def indexOf(name)
    valus = self.findSymbol(name)
    return valus[2]
  end

  def findSymbol(name)
    if @subroutineTable.key?(name)
      return @subroutineTable[name]
    end

    if @classTable.key?(name)
      return @classTable[name]
    end

    return ["NONE", "NONE", "NONE"]
  end

  def printSymbols
    puts "classTable: #{@classTable}"
    puts "subroutineTable: #{@subroutineTable}"
    puts "symbolIndex: #{@symbolIndex}"
  end
end

由于Jack的适当设计，我们不会遇到在嵌套的作用域中使用变量的情况，所以不会遇到变量冲突的问题。在其他高级语言中，我们可能会随时开辟一个新的作用域（例如用{}括起来），这时候我们需要用符号表的链表这种数据结构来解决这个问题，每增加一层作用域都会新增一个新的符号表节点。

处理符号

下面截取了一段符号处理的实现（把符号加入符号表），可以看到语义分析和代码生成的阶段是融合在语法分析的过程当中的，是对语法分析程序的扩展。在语法分析过程中，当我们遇到一个新符号，我们先解析它的type和kind，然后把它写到符号表中。

#编译静态变量或成员变量的声明
def compileClassVarDec
  varCount = 0
  isVar = @tokenizer.tokenType == "KEYWORD" && (@tokenizer.keyword() == "static" || @tokenizer.keyword() == "field")
  while isVar
    kind = getKeyword()
    @tokenizer.advance()
    type = getType()
    @tokenizer.advance()
    varCount = varCount + self.writeVarToSymbolTable(kind, type)
    @tokenizer.advance()
    isVar = @tokenizer.tokenType == "KEYWORD" && (@tokenizer.keyword() == "static" || @tokenizer.keyword() == "field")
  end
  return
end

#编译局部变量
def compileVarDec
  varCount = 0
  isVar = @tokenizer.tokenType == "KEYWORD" && @tokenizer.keyword() == "var"
  while isVar
    kind = getKeyword()
    @tokenizer.advance()
    type = getType()
    @tokenizer.advance()
    varCount = varCount + self.writeVarToSymbolTable(kind, type)
    @tokenizer.advance()
    isVar = @tokenizer.tokenType == "KEYWORD" && @tokenizer.keyword() == "var"
  end
  return varCount
end

def writeVarToSymbolTable(kind, type)
  varCount = 0
  firstVarName = self.getIndentifier()
  @symbolTable.define(firstVarName, type, kind)
  varCount = varCount + 1
  @tokenizer.advance()
  isSemicolon = @tokenizer.tokenType == "SYMBOL" && @tokenizer.symbol() == ";"
  while !isSemicolon
    @tokenizer.advance()
    nextVarName = self.getIndentifier()
    @symbolTable.define(nextVarName, type, kind)
    varCount = varCount + 1
    @tokenizer.advance()
    isSemicolon = @tokenizer.tokenType == "SYMBOL" && @tokenizer.symbol() == ";"
  end
  return varCount
end

命令翻译

命令翻译部分，我们需要处理两类命令：表达式求值和程序流程控制

表达式求值

表达式求值就是计算形如：x+g(x,y,-z)*5的计算式，计算这种表达式可以用经典的后缀表示法来处理（RPN，逆波兰表示法），即通过后序遍历的方式结合栈的使用来计算表达式。

用程序表达后缀表达式的算法如下：

compileExpression(exp)
{
if exp 是数字 n                  then push n
if exp 是变量 v                  then push v
if exp = (exp1 op exp2)         then compileExpression(exp1), compileExpression(exp2), compile op 
if exp = op(exp1)               then compileExpression(exp1), compile op 
if exp = f(exp1 ... expN)       then compileExpression(exp1), ..., compileExpression(expn), call f
}

表达式实现

用程序表达后缀表达式的算法本身比较简答，但表达式本身比较复杂，在Jack中很多符号或符号的组合都可以被当做一个表达式，例如一个表达式可以是一个关键字，一个数字，一个变量；也可以是数组中的某个值；也可以是函数调用；也可以是用（）括起来的另一个表达式等，我们把这些可能的方式都统称为一个term。表达式实现的关键代码如下：

def compileExpression
  self.compileTerm()
  termEnd = !($OPETATOR.include? @tokenizer.symbol())
  if !termEnd
    opretator = $OPTOCMD[self.getSymbol()] #操作符
    @tokenizer.advance()
    self.compileTerm()
    @vmWriter.writeArithmetic(opretator)
    termEnd = !($OPETATOR.include? @tokenizer.symbol())
  end
end

def compileTerm
  if @tokenizer.symbol() == "-" || @tokenizer.symbol() == "~" #unary term
    opetator = $UNARYCMD[self.getSymbol()] 
    @tokenizer.advance()
    self.compileTerm()
    @vmWriter.writeArithmetic(opetator)
  elsif @tokenizer.tokenType == "KEYWORD"
    keyword = self.getKeyword()
    if keyword == "false" || keyword == "null"
      @vmWriter.writePushNumber("0")
    elsif keyword == "true"
      @vmWriter.writePushNumber("0")
      @vmWriter.writeArithmetic("not") #-1代表true
    elsif keyword == "this"
      @vmWriter.writePush("pointer", 0)
    else
      raise "#{keyword}是不可识别符号（只识别ture, false, null）"
    end
    @tokenizer.advance()
  elsif @tokenizer.tokenType == "INT-CONST"
    number = self.getNumber()
    @vmWriter.writePushNumber(number)
    @tokenizer.advance()
  elsif @tokenizer.tokenType == "STRING-CONST"
    string = self.getString()
    puts "发现string：#{string}"
    self.processString(string)
    @tokenizer.advance()
  elsif @tokenizer.symbol() == "(" #(expression)
    @tokenizer.advance()
    self.compileExpression()
    @tokenizer.advance()
  else #varName | varName[expression] | subroutineCall
    firstToken = @tokenizer.identifier()
    @tokenizer.advance()
    secondToken = @tokenizer.symbol()
    @tokenizer.backward()
    if secondToken != "[" && secondToken != "(" && secondToken != "." #varName
      varName = self.getIndentifier()
      self.pushVarName(varName)
      @tokenizer.advance()
    elsif secondToken == "[" #varName[expression]
      varName = self.getIndentifier()
      @tokenizer.advance()
      @tokenizer.advance()
      self.compileExpression()
      self.pushVarName(varName)
      @vmWriter.writeArithmetic("add")
      @vmWriter.writePop("pointer", 1) #修改That
      @vmWriter.writePush("that", 0)
      @tokenizer.advance()
    elsif secondToken == "(" || secondToken == "." #subroutineCall
      firstSymbol = self.getIndentifier()
      @tokenizer.advance()
      if @tokenizer.symbol() == "(" #调内部方法分支
        @tokenizer.advance()
        paramCount = self.compileExpressionList()
        methodName = "#{@className}.#{firstSymbol}"
        @vmWriter.writePush("pointer", 0) #调用实例方法，先push自己
        @vmWriter.writeCall(methodName, paramCount + 1)
        @tokenizer.advance()
      elsif @tokenizer.symbol() == "." #调外部方法分支
        @tokenizer.advance()
        className = firstSymbol
        methodName = self.getIndentifier() 
        @tokenizer.advance()
        @tokenizer.advance()
        symbolKind = @symbolTable.kindOf(firstSymbol)
        symbolIndex = @symbolTable.indexOf(firstSymbol)
        isInstanceMethod = symbolKind != "NONE" && symbolIndex != "NONE"
        if  isInstanceMethod #调用实例的方法
          if symbolKind == "field"
            @vmWriter.writePush("this", symbolIndex) #push this
          else
            if @curFunctionType == "method" && symbolKind == "argument"
              symbolIndex = symbolIndex + 1
            end
            @vmWriter.writePush(symbolKind, symbolIndex)
          end
          className = @symbolTable.typeOf(firstSymbol)
        end
        paramCount = self.compileExpressionList()
        if isInstanceMethod
          paramCount = paramCount + 1
        end
        callName = "#{className}.#{methodName}"
        @vmWriter.writeCall(callName, paramCount)
        @tokenizer.advance()
      end
    end
  end
end

分支流程控制

这里的分支流程控制指的就是Jack中的if语句和while语句。分支流程控制的编译相对更直观一点，就是把if和while语句编译成更低级的goto和if-goto语句。它们的实现算法如下：

关键代码实现如下，这里值得思考的是：如何保证label L1, label L2等label名不互相冲突；且if和while是可以具备嵌套结构的，我们也需要确保进入或退出时更深一级if或while语句时，label的对应关系不会混乱。

def compileIF
  @ifBackTrace << @ifCount
  @ifTotle = @ifTotle + 1
  @ifCount = @ifTotle
  @tokenizer.advance()
  @tokenizer.advance()
  self.compileExpression()
  @vmWriter.writeIf("IF_TRUE#{@ifCount}")
  @vmWriter.writeGoto("IF_FALSE#{@ifCount}")
  @vmWriter.writeLabel("IF_TRUE#{@ifCount}")
  @tokenizer.advance()
  @tokenizer.advance()
  self.compileStatements()
  @tokenizer.advance()
  if @tokenizer.keyword() == "else" #compile else
    @vmWriter.writeGoto("IF_END#{@ifCount}")
    @vmWriter.writeLabel("IF_FALSE#{@ifCount}")
    @tokenizer.advance()
    @tokenizer.advance()
    self.compileStatements()
    @vmWriter.writeLabel("IF_END#{@ifCount}")
  else
    @tokenizer.backward() #返回到}处
    @vmWriter.writeLabel("IF_FALSE#{@ifCount}")
  end
  @ifCount = @ifBackTrace.pop()
end

def compileWhile
  @whileBackTrace << @whileCount
  @whileTotle = @whileTotle + 1
  @whileCount = @whileTotle
  @vmWriter.writeLabel("WHILE_EXP#{@whileCount}")
  @tokenizer.advance()
  @tokenizer.advance()
  self.compileExpression()
  @vmWriter.writeArithmetic("not")
  @vmWriter.writeIf("WHILE_END#{@whileCount}")
  @tokenizer.advance()
  @tokenizer.advance()
  self.compileStatements()
  @vmWriter.writeGoto("WHILE_EXP#{@whileCount}")
  @vmWriter.writeLabel("WHILE_END#{@whileCount}")
  @whileCount = @whileBackTrace.pop
end

函数调用和返回

在调用VM函数之前，调用者必须将函数的参入压入栈，且如果被调用的VM函数是自己实例方法，那么首先入栈的参数是该方法操作对象的引用（进入函数后这个对象引用变为this指针）。return方法的实现则很简单，不过当return的类型为void时，我们也需要返回一个常量0作为返回值。

代码关键实现如下：

def compileSubroutineCall
  isVoid = false
  firstSymbol = self.getIndentifier()
  @tokenizer.advance()
  if @tokenizer.symbol() == "(" #调内部方法分支
    @tokenizer.advance()
    @vmWriter.writePush("pointer", 0) #调用实例方法，先push this
    paramCount = self.compileExpressionList()
    methodName = "#{@className}.#{firstSymbol}"
    @vmWriter.writeCall(methodName, paramCount + 1)
    @tokenizer.advance()
  elsif @tokenizer.symbol() == "." #调外部方法分支
    @tokenizer.advance()
    className = firstSymbol
    methodName = self.getIndentifier() 
    @tokenizer.advance()
    @tokenizer.advance()
    symbolKind = @symbolTable.kindOf(firstSymbol)
    symbolIndex = @symbolTable.indexOf(firstSymbol)
    isInstanceMethod = symbolKind != "NONE" && symbolIndex != "NONE"
    if  isInstanceMethod #调用实例的方法
      if symbolKind == "field"
        @vmWriter.writePush("this", symbolIndex) #push this
      else
        if @curFunctionType == "method" && symbolKind == "argument"
          symbolIndex = symbolIndex + 1
        end
        @vmWriter.writePush(symbolKind, symbolIndex)
      end
      className = @symbolTable.typeOf(firstSymbol)
    end
    paramCount = self.compileExpressionList()
    if isInstanceMethod
      paramCount = paramCount + 1
    end
    callName = "#{className}.#{methodName}"
    @vmWriter.writeCall(callName, paramCount)
    @tokenizer.advance()
  end
end

def compileReturn
  @tokenizer.advance()
  if @tokenizer.symbol() == ";" #数组
    @vmWriter.writePushNumber(0) #默认push0
    @vmWriter.writeReturn() #return
  else
    self.compileExpression()
    @vmWriter.writeReturn() #return
  end
end

对象访问

上述我们讲的操作都是发生在栈空间，而对象和数组存储的内存位置在堆空间。对象和数组的处理方式很类似，都是在内存中为其分配一块连续的内存，然后通过一个指向起始地址的指针来进行访问。

this指针在对象访问中起到了重要作用，在构造函数中，我们通过系统的Memory.alloc()函数来为对象分配内存，Memory.alloc()返回指向对象起始地址的指针，然后我们把这个指针赋值给THIS段，返回给调用者。

constructor Ball new(int Ax, int Ay,
                     int AleftWall, int ArightWall, int AtopWall, int AbottomWall) {      
  let x = Ax;   
  let y = Ay;
  let leftWall = AleftWall;
  let rightWall = ArightWall - 6;
  let topWall = AtopWall; 
  let bottomWall = AbottomWall - 6;
  let wall = 0;
  do show();

  return this;
}

# 编译构造函数，开辟实例内存
def compileConstructor
  filedCount = @symbolTable.varCount("field")
  @vmWriter.writePushNumber(filedCount)       #首先我们要知道对象需要多大的内存，即需要存储多少个变量
  @vmWriter.writeCall("Memory.alloc", 1)
  @vmWriter.writePop("pointer", 0)            #把实例内存地址pop到THIS
end

当我们调用对象的实例方法时，需要先push实例方法的入参，但我们首先需要push一个额外的隐含参数，就是调用对象本身，这个参数在函数内部我们同样通过this指针来访问。可以看到通过虚拟内存段this，我们简化了对象访问操作。

def compileDo
  @tokenizer.advance()
  self.compileSubroutineCall()
  @vmWriter.writePop("temp", 0) #do语句总是调用返回类型为void的函数，所以最后弹出(并忽略)调用函数的返回值
end

def compileSubroutineCall
  isVoid = false
  firstSymbol = self.getIndentifier()
  @tokenizer.advance()
  if @tokenizer.symbol() == "(" #调内部方法分支
    @tokenizer.advance()
    @vmWriter.writePush("pointer", 0) #调用实例方法，先push this
    paramCount = self.compileExpressionList()
    methodName = "#{@className}.#{firstSymbol}"
    @vmWriter.writeCall(methodName, paramCount + 1)
    @tokenizer.advance()
  elsif @tokenizer.symbol() == "." #调外部方法分支
    @tokenizer.advance()
    className = firstSymbol
    methodName = self.getIndentifier() 
    @tokenizer.advance()
    @tokenizer.advance()
    symbolKind = @symbolTable.kindOf(firstSymbol)
    symbolIndex = @symbolTable.indexOf(firstSymbol)
    isInstanceMethod = symbolKind != "NONE" && symbolIndex != "NONE"
    if  isInstanceMethod #调用实例的方法
      if symbolKind == "field"
        @vmWriter.writePush("this", symbolIndex) #push this
      else
        if @curFunctionType == "method" && symbolKind == "argument"
          symbolIndex = symbolIndex + 1
        end
        @vmWriter.writePush(symbolKind, symbolIndex)
      end
      className = @symbolTable.typeOf(firstSymbol)
    end
    paramCount = self.compileExpressionList()
    if isInstanceMethod
      paramCount = paramCount + 1
    end
    callName = "#{className}.#{methodName}"
    @vmWriter.writeCall(callName, paramCount)
    @tokenizer.advance()
  end
end

数组访问

对象的访问我们使用了this指针，那么数组的访问我们会用上最后一个虚拟内存段：that指针。例如在访问数组对象array[index]时，先计算array指向的首地址+index，得出的值就是要访问的元素，然后把这个值赋值给that指针，这里面用到了temp 0来保存临时变量，为了防止that指针在使用时冲突。that指针的存在也是为了简化代码的结构。

关键代码实现如下：

function void main() {
    var Array a, b, c;
    
    let a = Array.new(10);
    let b = Array.new(5);
    let c = Array.new(1);
    
    let a[3] = 2;
    let a[4] = 8;
    let a[5] = 4;
    let b[a[3]] = a[3] + 3;  // b[2] = 5
    let a[b[a[3]]] = a[a[5]] * b[((7 - a[3]) - Main.double(2)) + 1];  // a[5] = 8 * 5 = 40
    let c[0] = null;
    let c = c[0];
    
    ......
    return;
}

def compileLet
  @tokenizer.advance()
  varName = self.getIndentifier()
  @tokenizer.advance()
  isArray = false
  if @tokenizer.symbol() == "[" #数组
    isArray = true
    @tokenizer.advance()
    self.compileExpression()
    self.pushVarName(varName)
    @vmWriter.writeArithmetic("add")
    @tokenizer.advance()    
  end
  @tokenizer.advance()
  self.compileExpression()
  if isArray                                 
    @vmWriter.writePop("temp", 0)            #temp0 = expression above
    @vmWriter.writePop("pointer", 1)         #that指向数组
    @vmWriter.writePush("temp", 0)
    @vmWriter.writePop("that", 0)
  else
    symbolKind = @symbolTable.kindOf(varName)
    symbolIndex = @symbolTable.indexOf(varName)
    if symbolKind == "argument" || symbolKind == "local" || symbolKind == "static"
      @vmWriter.writePop(symbolKind, symbolIndex) # 把expression的值pop到var
    elsif symbolKind == "field"
      @vmWriter.writePop("this", symbolIndex) # 把expression的值pop到this段
    else
      raise "不能识别"
    end
  end
end

def compileTerm
  ......
  else #varName | varName[expression] | subroutineCall
    firstToken = @tokenizer.identifier()
    @tokenizer.advance()
    secondToken = @tokenizer.symbol()
    @tokenizer.backward()
    if secondToken != "[" && secondToken != "(" && secondToken != "." #varName
      varName = self.getIndentifier()
      self.pushVarName(varName)
      @tokenizer.advance()
    elsif secondToken == "[" #varName[expression]
      varName = self.getIndentifier()
      @tokenizer.advance()
      @tokenizer.advance()
      self.compileExpression()
      self.pushVarName(varName)
      @vmWriter.writeArithmetic("add")
      @vmWriter.writePop("pointer", 1) #修改That
      @vmWriter.writePush("that", 0)
      @tokenizer.advance()
    elsif 
      ...... 
    end
  end
end

总结

日常工作中，绝大多数程序员都不会去编写一个编译器，我们对于编译器的学习和了解可能更多的来自对一些教材和资料浅尝辄止地阅读，只是形成了一个模糊的概念，甚至自己都会怀疑自己对其理解的正确性。虽然比起动辄百万行代码的工业级编译器，Jack编译器实在是太过简单，但我们仍可以从亲自实现它的过程中真正地窥探到编译器工作的基本原理。

到此为止，我们从0到1构建计算机系列的文章就要接近尾声了，下一篇我们会实现一个最简单的操作系统，支持高级数学运算、内存分配、数组操作、字符串操作、输入输出等能力。

本篇完整实现放在了:github