【深入淺出教你寫編譯器（Compiler）】六、編譯器（Compiler）﹣生成代碼（Code Generation）（上） by Dukeland

quasiceo 2014-02-02

展开全文

【深入淺出教你寫編譯器（Compiler）】六、編譯器（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 機制才可以完美編譯，所以留待下一節才討論如何編譯。大家現在先摸熟以上的教學吧！