搜尋

隨機推薦

23 十一月 2010
12 八月 2013
23 十一月 2010
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.