搜尋

隨機推薦

24 十二月 2010

【深入淺出教你寫編譯器(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,這需要利用一些技巧才可以)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 出去就可以了。

1
2
3
4
5
Compiler.prototype.evaluateIntNode = function (node){
    var register = this.getNextRegister();
    this.writeln("lwi " + register + ", " + node.data + ";");
    return register;
}
為什麼要返回 register 名稱呢?因為我們後面會用到它來運算,例如加減乘除等等的運算,我們需要兩個 register

處理完數字之後,我們要處理其中一個最複雜的東西,就是 compound node 了。其實說它複雜也不是真的很複雜,跟我們的 Analyser 做的東西差不多,只是今次要用數個 register 來做。來,看看代碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 裡的內容。

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

現在看看運行結果吧:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 也處理掉:

1
2
3
4
5
6
7
8
9
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,先看看代碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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 機制才可以完美編譯,所以留待下一節才討論如何編譯。大家現在先摸熟以上的教學吧!

 


 

 

廣告

无觅相关文章插件,快速提升流量

Please publish modules in offcanvas position.