前幾節(jié)，我們介紹了如何使用語法解析算法對代碼進(jìn)行解析。語法解析的目的是為了明白代碼語句的意圖，例如對于語句: c = a + b; 語法解析后，編譯器就明白代碼是想把變量a和b的值相加，再把結(jié)果賦值給變量c.然而要想實現(xiàn)這樣的結(jié)果，編譯器還得需要不少輔助信息，例如變量a和b對應(yīng)的數(shù)值是多少，這些輔助信息我們會存儲在一種稱之為符號表的數(shù)據(jù)結(jié)構(gòu)中。

在前幾節(jié)語法解析時，代碼實際上建造了一種樹形結(jié)構(gòu)，例如語句 a+b; 其中包含三個元素，a和b屬于Identifier, 三者構(gòu)成了一個算術(shù)表達(dá)式，也就是expression, 這就相當(dāng)于構(gòu)建了一顆三叉樹，樹的節(jié)點就是expression, 葉子節(jié)點就是兩個Identifier和加號。在進(jìn)行語句執(zhí)行時，編譯器會遍歷這樣的多叉樹，然后執(zhí)行相應(yīng)的動作，把動作執(zhí)行后的結(jié)果存儲在對應(yīng)的符號表里。例如編譯器遍歷了語句a+b對應(yīng)的多叉樹后，會從符號表中找到變量a,b對應(yīng)的數(shù)值，根據(jù)讀取到的符號"+",它會做一個加法，把結(jié)果存儲到變量c對應(yīng)的符號表中，接下來我們先看看符號表結(jié)構(gòu)，我們先看看整型和布爾型變量對應(yīng)的符號是怎么定義的。

在本地目錄新建一個文件叫MonkeyEvaluator.js, 添加如下代碼：

class BaseObject {
    constructor (props) {
        this.INTEGER_OBJ = "INTEGER"
        this.BOOLEAN_OBJ = "BOOLEAN"
        this.NULL_OBJ = "NULL"
    }

    type() {return null}

    inspect() {return null}
}

class Integer extends BaseObject {
    constructor(props) {
        super(props)
        this.value = props.value
    }

    inspect () {
        return "" + this.value
    }

    type () {
        return this.INTEGER_OBJ
    }
}

class Boolean extends BaseObject {
    constructor (props) {
        super(props)
        this.value = props.value
    }

    type () {
        return this.BOOLEAN_OBJ
    }

    inspect () {
        return "" + this.value
    }
}

class Null extends BaseObject {
    constructor (props) {
        super(props)
    }

    type () {
        return this.NULL_OBJ
    }

    inspect () {
        return "null"
    }
}

上面代碼定義了符號表中應(yīng)對不同數(shù)據(jù)類型的符號，BaseObject是所有符號對象的父類，它定義所有符號對象必須導(dǎo)出的接口，其中type接口返回符號對應(yīng)的數(shù)據(jù)類型，inspect接口打印符號對象的內(nèi)容。在BaseObject的構(gòu)造函數(shù)中，它定義了當(dāng)前符號對象的類型，分別是整形，布爾型和NULL。

接下來的Integer, Boolean, 和 Null 分別繼承自BaseObject, 他們分別用于記錄數(shù)據(jù)類型為整形，布爾型和Null型變量的輔助信息，其中前兩者都含有一個value域，它用來存儲變量對應(yīng)的數(shù)值。接著我們將實現(xiàn)一個能夠遍歷語法解析樹的類，它將遍歷每個節(jié)點，同時執(zhí)行相應(yīng)動作，我們先回到MonkeyCompilerParser.js,為每個節(jié)點增加一個類型信息，例如：

class ExpressionStatement extends Statement {
  constructor(props) {
    super(props)
    this.token = props.token
    this.expression = props.expression
    var s = "expression: " + this.expression.getLiteral()
    this.tokenLiteral = s
    this.type = "ExpressionStatement"
  }
}
...

class IntegerLiteral extends Expression {
    constructor(props) {
        super(props)
        this.token = props.token
        this.value = props.value
        var s = "Integer value is: " + this.token.getLiteral()
        this.tokenLiteral = s
        // change here
        this.type = "Integer"
    }
}

//change here 
class Boolean extends Expression {
  constructor(props) {
    super(props)
    this.token = props.token
    this.value = props.value
    var s = "Boolean token with value of " + this.value
    this.tokenLiteral = s
    //change here
    this.type = "Boolean"
  }
}
...

我們增加的type值域就是用來標(biāo)明當(dāng)前節(jié)點的類型。回憶前幾節(jié)我們詳細(xì)研究的語法解析流程，對于如下代碼：

5;

語法解析器會先調(diào)用parseExpressionStatement()來執(zhí)行解析，在該函數(shù)里，它會根據(jù)調(diào)用表，調(diào)用parseExpression()接口來執(zhí)行解析，后者會調(diào)用parseIntegerLiteral()接口，在該函數(shù)中，它把字符"5"轉(zhuǎn)換成數(shù)字5，然后創(chuàng)建一個IntegerLiteral對象，把數(shù)字5存儲在里面，這個對象會返回到parseExpressionStatement(),這個函數(shù)會構(gòu)造一個ExpressionStatement對象，然后再把IntegerLiteral對象存儲其中。根據(jù)上面代碼的定義，IntegeLiteral對象會存儲在ExpressionStatment對象的expression值域中。

于是解析過程就構(gòu)造了一個語法樹節(jié)點，它的結(jié)構(gòu)是這樣：ExpressionStatement -> IntegerLiteral。于是變量這個節(jié)點時，我們需要先訪問ExpressionStatement,然后從它的expression值域中取出IntegerLiteral對象，再從后者的value域中讀取對應(yīng)的數(shù)值。根據(jù)這個邏輯，我們編寫語法執(zhí)行器的代碼如下：

class MonkeyEvaluator {
    eval (node) {
        var props = {}
        switch (node.type) {
            case "Integer":
              console.log("Integer with value:", node.value)
              props.value = node.value
              return new Integer(props)
            case "Boolean":
              props.value = node.value
              console.log("Boolean with value:", node.value)
              return new Boolean(props)
            case "ExpressionStatement":
              return this.eval(node.expression)
        }

        return null
    }
}

eval 函數(shù)負(fù)責(zé)變量語法樹節(jié)點，并根據(jù)節(jié)點信息執(zhí)行相應(yīng)動作。當(dāng)它遍歷的節(jié)點類型是ExpressionStatment時，它知道需要繼續(xù)解析它的expression域，于是它遞歸調(diào)用eval函數(shù)，傳入該對象的expression域，eval再次被調(diào)用是，傳進(jìn)來的就是IntegerLiteral對象，它的type域?qū)?yīng)的就是"Integer",于是代碼讀取它存儲的數(shù)值5，然后創(chuàng)建一個Integer符號對象，把數(shù)值5存在里面。我們對boolean類型的解析邏輯跟整形的解析邏輯是一樣的。

接著，我們看看更復(fù)雜的表達(dá)式對應(yīng)的節(jié)點如何解釋執(zhí)行。對于表達(dá)式:!true, -5, 他們就是我們前面幾節(jié)所描述的前綴表達(dá)式，我們先看看前綴表達(dá)式對應(yīng)的節(jié)點對象：

class PrefixExpression extends Expression {
  constructor(props) {
    super(props)
    this.token = props.token
    this.operator = props.operator
    this.right = props.expression
    var s = "(" + this.operator + this.right.getLiteral() + " )"
    this.tokenLiteral = s
    this.type = "PrefixExpression"
  }
}

其中的operator 代表著表達(dá)式前面的操作符，而right代表操作符后面的表達(dá)式，因此我們在解析前綴表達(dá)式節(jié)點時，需要先解析它的right對象，然后再根據(jù)不同的操作符采取不同的動作，因此相應(yīng)代碼如下：

class MonkeyEvaluator {
    eval (node) {
        var props = {}
        switch (node.type) {
        ....
        case "PrefixExpression":
              var right = this.eval(node.right)
              if (this.isError(right)) {
                return right
              }

              var obj =  this.evalPrefixExpression(node.operator, right)
              console.log("eval prefix expression: ", obj.inspect())
              return obj
        }

        return null
    }

evalPrefixExpression(operator, right) {
        switch (operator) {
            case "!":
              return this.evalBangOperatorExpression(right)
            case "-":
              return this.evalMinusPrefixOperatorExpression(right)
            default:
              return this.newError("unknown operator:", operator, right.type())
        }
    }

    isError (obj) {
        if (obj !== null) {
            return obj.type() === obj.ERROR_OBJ
        }

        return false
    }

    evalBangOperatorExpression(right) {
        var props = {}
        if (right.type() === right.BOOLEAN_OBJ) {
            if (right.value === true) {
                props.value = false
            }

            if (right.value === false) {
                props.value = true
            }
        }

        if (right.type() === right.NULL_OBJ) {
            props.value = true
        }

        return new Boolean(props)
    }

    evalMinusPrefixOperatorExpression(right) {
        if (right.type() !== right.INTEGER_OBJ) {
            return this.newError("unknown operaotr:- ", right.type())
        }

        var props = {}
        props.value = -right.value
        return new Integer(props)
    }

    newError(msg, type) {
        var props = {}
        props.errMsg = msg + type
        return new Error(props)
    }

從上面代碼看出，在解析前綴表達(dá)式節(jié)點時，解析函數(shù)eval會先對節(jié)點的right值域進(jìn)行解釋執(zhí)行，創(chuàng)建相應(yīng)的符號對象，然后調(diào)用evalPrefixExpression()，在該函數(shù)中，它會根據(jù)節(jié)點的operator內(nèi)容進(jìn)行相應(yīng)的處理。如果操作符是"!",那么它調(diào)用evalBangOperatorExpression(),在這個函數(shù)里，它會對right解析后返回來的符號對象里面的value取反，如果操作符是"-", 函數(shù)調(diào)用evalMinusPrefixOperatorExpression(),它會將right解析后返回的符號對象里的value做取負(fù)操作，如果操作符不屬于這兩種情況，那么代碼返回錯誤信息。

完成了節(jié)點的解釋執(zhí)行流程，我們需要觸發(fā)這個流程，于是打開MonkeyCompilerIDE.js,添加如下代碼：

onLexingClick () {
      this.lexer = new MonkeyLexer(this.inputInstance.getContent())
      this.parser = new MonkeyCompilerParser(this.lexer)
      this.parser.parseProgram()
      this.program = this.parser.program
      for (var i = 0; i < this.program.statements.length; i++) {
          console.log(this.program.statements[i].getLiteral())

          //change here
          this.evaluator.eval(this.program.statements[i])
      }
    }

上面代碼執(zhí)行后情況如下，在編輯框里輸入如下語句：

這里寫圖片描述

點擊底下的parser按鈕，代碼會被語法進(jìn)行，然后進(jìn)入語法樹節(jié)點的解析執(zhí)行流程，代碼運行后結(jié)果如下：

這里寫圖片描述

表達(dá)式"!true"，它的值被解析成false, "-5"它的值被解析成整形-5，因此我們代碼就能成功的執(zhí)行了語句"!true"和"-5"。

在后續(xù)的章節(jié)中，我們將詳細(xì)研究后續(xù)表達(dá)式，例如a+b, a*(b+c);這類代碼的解析執(zhí)行，他們的處理過程要比本節(jié)前序表達(dá)式的處理過程復(fù)雜的多，我們也將使用一一拆解，分而治之的方式將難點分解，將難度降低，以便大家的掌握和理解。

更多技術(shù)信息，包括操作系統(tǒng)，編譯器，面試算法，機(jī)器學(xué)習(xí)，人工智能，請關(guān)照我的公眾號：

這里寫圖片描述