六、編譯器（Compiler）﹣生成代碼（Code Generation）（上）

終於來到最重要一步了，我們要把之前建立好的 parse tree 變成可以被 Wemachine 運行的代碼，有了編譯器才是真正的 compiler！在這一步，我們還是要用那個老技巧，即 mutual recursion，來遍歷我們的 parse tree，並輸出相應的代碼。事不宜遲，現在就開始了。

首先， Copy and paste 一下，把 Analyser 的 method 複製一次，並且把所有屬於 Analyser 做的工作都移除，只留下 evaluate* 的語句，以保留 mutual recursion 來遍歷我們的 parse tree。然後我們需要建立一個安排 register 的機制，由於我們的 Wemachine 有無限個 register 可以用，所以我們只需要一直取新的 register 來用就可以，而不用重用已被使用的 register（實際的情況當然不會有無限的 register，這需要利用一些技巧才可以）。

function Compiler() {
    this.lineBreak = "\n";
    this.register = 0;
}
Compiler.prototype.getMachineCode = function (expressionBlockNode) {
    this.code = "";
    this.evaluateExpressionBlockNode(expressionBlockNode);
    return this.code;
}
Compiler.prototype.getNextRegister = function () {
    return "$" + this.register++;
}
Compiler.prototype.writeln = function (code) {
    this.code += code + this.lineBreak;
}

這就是我們 compiler 的基本功能了。現在先來處理最簡單的語句吧，第一樣要處理的是純數字，遇到一個數字的時候，我們只需簡單地把數字放到 register 中，並把 register 名稱 return 出去就可以了。

Compiler.prototype.evaluateIntNode = function (node) {
    var register = this.getNextRegister();
    this.writeln("lwi " + register + ", " + node.data + ";");
    return register;
}

為什麼要返回 register 名稱呢？因為我們後面會用到它來運算，例如加減乘除等等的運算，我們需要兩個 register 處理完數字之後，我們要處理其中一個最複雜的東西，就是 compound node 了。其實說它複雜也不是真的很複雜，跟我們的 Analyser 做的東西差不多，只是今次要用數個 register 來做。來，看看代碼：

Compiler.prototype.evaluateCompoundNode = function (node) {
    var operator = null;
    var resultRegister;
    for (var i = 0, l = node.nodes.length; i < l; i++) {
        var subNode = node.nodes[i];
        if (subNode instanceof OperatorNode) {
            operator = subNode;
        } else {
            if (resultRegister == null) {
                resultRegister = this.getNextRegister();
                this.writeln("move " + resultRegister + "," +this.evaluateExpressionNode(subNode) + ";");
            } else {
                var currRegister = this.evaluateExpressionNode(subNode);
                if (operator instanceof OperatorPlusNode) {
                    this.writeln("add " + resultRegister + "," +resultRegister + "," + currRegister + ";");
                }
            }
        }
    }
    return resultRegister;
}

這段程式在做什麼呢？這段程式有一個 for loop ， loop 裡面做的跟 Analyser 差不多，就是讀一個 node 進來，是運算元的話就 evaluate 一下，並把結果放到另一個 register 中，然後再讀一個運算符 node ，把兩邊的數值進行一下運算，再返回結果，這就完成了 compound node 的基本流程了。

最後再寫一下 print，以便我們之後 debug ， print 要做的事很簡單，就是直接輸出 print 指令，以列印出 register 裡的內容。

Compiler.prototype.evaluatePrintNode = function (node) {
    var register = this.evaluateExpressionNode(node.expressionNode);
    this.writeln("print " + register + ";");
}

現在看看運行結果吧：

第一步成功了，現在就把剩餘的運算符都編寫出來吧。加減乘除及取餘數的做法都差不多，但相等的比較就很不同了，要記住， instruction set 提供的指令通常都很有限，很多時我們都要模擬一些指令，例如 “==” ，我們的 instruction set 裡只指供 beq ，那麼我們只能靠它來模擬這個比較。又，我們的 Wemachine 不能跳到未曾運行到的 label ，所以我們在 compile 的時候也要考慮目標機器運行的特性。現在看看 “==” 是如何模擬的：

var doneLbl = this.getNextLabel();
var falseLbl = this.getNextLabel();
var trueLbl = this.getNextLabel();
var doneRegister = this.getNextRegister();
var tempResultRegister = this.getNextRegister();
var aRegister = this.getNextRegister();
var bRegister = this.getNextRegister();
this.writeln("move " + aRegister + "," + resultRegister + ";");
this.writeln("move " + bRegister + "," + currRegister + ";");
this.writeln("lwi " + doneRegister + ",0;");
this.writeln("label " + doneLbl + ";");
this.writeln("label " + trueLbl + ";");
this.writeln("add " + aRegister + "," + aRegister + "," + doneRegister +";");
this.writeln("lwi " + tempResultRegister + ",1;");
this.writeln("beq " + doneRegister + "," + this.trueRegister + "," +doneLbl + ";");
this.writeln("label " + falseLbl + ";");
this.writeln("lwi " + tempResultRegister + ",0;");
this.writeln("beq " + doneRegister + "," + this.trueRegister + "," +doneLbl + ";");
this.writeln("label " + doneLbl + ";");
this.writeln("lwi " + doneRegister + ",1;");
this.writeln("beq " + aRegister + "," + bRegister + "," + trueLbl + ";");
this.writeln("move " + resultRegister + "," + tempResultRegister + ";");

比你想像中的要複雜得多吧？在有限的資源下，我們只能這樣做。這段代碼在做什麼呢？首先我們要把準備比較的項目抄到兩個新的 register 中，以防止改變了原本的數值。然後，我們設定一個 doneRegister 來表示我們的比較到底做完了沒有，然後是設定兩個 label ，一個叫 doneLbl ，這並不是真的用來跳轉的 label，而只是防止 runtime error 而事先定義的 label，稍後我們仍然會再重新定義它的位置。

在 trueLbl 下要做三件事，第一是把 aRegister 的數值加上 doneRegister 的數值，第一次執行 doneRegister 的數值是 0 ，所以不會改變 aRegister ，下一次執行 doneRegister 的數值就是 1 ，這就會改變 aRegister ，這有助我們離開這段比較程式。然後就是真正的設定結果為 1（亦即 true），再接下來的是看看 doneRegister 是不是 1 ，是的話就直接跳出設定 true/false 的程式，否則繼續初始化比較程式。 falseLbl 下做的事都差不多，不詳述。

到 doneLbl 了，它要做的事是設定 doneRegister 的數值為 1 ，並比較 aRegister 和 bRegister 的數值，相等就跳到 trueLbl 以設定結果為 1 ，而這次執行 trueLbl 就和初始化時有所不同了，因為這時 doneRegister 的數值是 1 ，所以會令 aRegister 的數值有所改變，那麼下次再比較 aRegister 和 bRegister 時結果就會不同，這就可以避免 infinite loop。最後就是把 tempResultRegister 中的東西抄到 resultRegister 中，那麼整個比較過程就完了。

編寫不等比較和 and/or 都跟之前使用的技巧很相似，這裡就不詳述了，現在就欠 assign node 未做，但做這個之前我們先要處理變數。變數的處理不難，只要有個 hash map 記下變數的數值儲在哪個 register 中就可以了，以後使用這個變數就用同一個 register 。

Compiler.prototype.evaluateVariableNode = function (node) {
    var init = null;
    if (node.initExpressionNode) {
        init = this.evaluateExpressionNode(node.initExpressionNode);
    }
    var reg = this.getNextRegister();
    this.varMap[node.varName] = reg;
    this.writeln("move " + reg + "," + init + ";");
}
Compiler.prototype.evaluateIdentifierNode = function (node) {
    var reg = this.varMap[node.identifier];
    return reg;
}

當然，如果變數有 initialise block 的話我們也要把數值抄到變數的 register 中。

好了，一切正常。把 assign node 也處理掉：

if (operator instanceof OperatorAssignNode) {
    this.writeln("move " + this.evaluateIdentifierNode(operand) + "," +currRegister + ";");
} else if (operator instanceof OperatorPlusAssignNode) {
    var reg = this.evaluateIdentifierNode(operand);
    this.writeln("add " + reg + "," + reg + "," + currRegister + ";");
} else if (operator instanceof OperatorMinusAssignNode) {
    var reg = this.evaluateIdentifierNode(operand);
    this.writeln("sub " + reg + "," + reg + "," + currRegister + ";");
}

這部份應該沒有什麼懸念，只是新加了一個叫做 operand 的變數，是用來儲存要 assign 到的變數，以便要真正 assign 時可以用來 resolve 正確的 register。再看一下結果：

接下來要編寫的是一堆 unary operator ，先看看代碼：

Compiler.prototype.evaluateNegateNode = function (node) {
    var reg = this.evaluateExpressionNode(node.node);
    this.writeln("multi " + reg + "," + reg + ",-1;");
    return reg;
}
Compiler.prototype.evaluateNotNode = function (node) {
    var reg = this.evaluateExpressionNode(node.node);
    this.writeln("addi " + reg + "," + reg + ",1;");
    this.writeln("modi " + reg + "," + reg + ",2;");
    return reg;
}
Compiler.prototype.evaluateParenNode = function (node) {
    return this.evaluateExpressionNode(node.node);
}
Compiler.prototype.evaluatePostIncrementNode = function (node) {
    var reg = this.evaluateExpressionNode(node.node);
    this.writelnToBuffer("addi " + reg + "," + reg + ",1;");
    return reg;
}
Compiler.prototype.evaluatePreIncrementNode = function (node) {
    var reg = this.evaluateExpressionNode(node.node);
    this.writeln("addi " + reg + "," + reg + ",1;");
    return reg;
}
Compiler.prototype.evaluatePostDecrementNode = function (node) {
    var reg = this.evaluateExpressionNode(node.node);
    this.writelnToBuffer("subi " + reg + "," + reg + ",1;");
    return reg;
}
Compiler.prototype.evaluatePreDecrementNode = function (node) {
    var reg = this.evaluateExpressionNode(node.node);
    this.writeln("subi " + reg + "," + reg + ",1;");
    return reg;
}

大抵上都很直觀，這裡只抽兩個比較特別的來說。第一個是 not ， not 的意思就是 true 變 false ， false 變 true ，由於 Wemachine 沒有提供指令，我們只能模擬，就是一條很簡單的數學： a = (a + 1) % 2 ，那就可以 1 變 0 ， 0 變 1 了。第二個是 post increment ，post increment 的意思是先執行整句 expression ，執行完就把變數 + 1 ，這個跟我們之前的做法都不一樣，我們需要把指令寫到 buffer 中，等到 expression 執行完才把 buffer 的東西抄到 output stream 去。

最後看一看結果：

現在只剩下 if 和 while 未編譯，這兩個是比較特別的，因為這需要改動 Wemachine 的 label 機制才可以完美編譯，所以留待下一節才討論如何編譯。大家現在先摸熟以上的教學吧！