{{ $root.errMsg }}

【深入淺出教你寫編譯器(Compiler)】六、編譯器(Compiler)﹣生成代碼(Code Generation)(下)

(已刪除)

(已關閉)

(已標記為濫發)

(已保護)


上回提要:我們開始著手編寫編譯部份,從那棵 Parse tree 生成代碼,做法跟之前的 Analyser 差不多,都是用 mutual recursion 來遍歷 Parse tree。上回我們已經寫好了大部份的編譯,只剩下兩款 expression 未寫好,即 if 和 while,本節就是要把這兩款 expression 都寫出來。

 

還記得我們 Wemachine 是如何做 label 的嗎?我們的 Wemachine 只能跳到程式上面已經定義好的 label,如果要跳轉到的 label 之前還未被定義的話就會當是 runtime error,但問題是,我們要做 if-else 時,如果條件式不成立的話就要跳到 else block,那可能是十丈遠,不可以跟之前做 相等比較 一樣先執行一次所有程式碼再判斷,因此,我們必須要有一個支援跳到在後面定義的 label 的 Wemachine,所以第一步我們就要改寫 Wemachine 了。

西杰將會新增一個指令,叫做 vlabel,定義方法跟 label 一樣,只是跳轉的時候,我們要在 label 前面加上 “_”,以標示要跳轉的是 vlabel 而不是 label。另外,跟 label 一樣,我們要定義一個 hash map 以記下 program counter,但這次不同的是,我們要在程式開始之前就建立好這個 hash map,或則我們就不能跳轉到未被定義的 label 了。因此,我們最好就是在一開始建立 instruction 列表時就順便建立這個 hash map。

function Wemachine(code){
    //simple parser
    this.vlabelMap = {};
 
    var instructions = code.split(";");
    var processedInstructions = [];
    for (var i = 0, l = instructions.length; i < l; i++){
        var instruction = trim(instructions[i]);
        if (instruction == ""){
            continue;
        }
        var insObj = {};
        var opcode = "";
        for (var j = 0, k = instruction.length; j < k; j++){
            if (instruction[j] == " "){
                instruction = instruction.substr(j);
                break;
            }else{
                opcode += instruction[j];
            }
        }
        insObj.opcode = opcode;
        insObj.operands = [];
 
        var operands = instruction.split(",");
        for (var j = 0, k = operands.length; j < k; j++){
            insObj.operands.push(trim(operands[j]));
        }
 
        if (insObj.opcode == "vlabel"){
            this.vlabelMap[insObj.operands[0]] = i;
        }
 
        processedInstructions.push(insObj);
    }
 
    this.instructions = processedInstructions;
    this.registers = [];
    this.pc = 0;
    this.labelMap = {};
}

看看新增了的那段代碼,如果我們讀到了 vlabel 的指令,我們就會記下 program counter,就是這樣簡單了。另外,現在跳轉的方法有所改變,即要加上 “_” 來跳轉到 vlabel,所以我們最好也把跳轉的代碼抽出來。

Wemachine.prototype.easyJump = function (lbl){
    var nextPC;// = this.labelMap[lbl];
    if (lbl.substr(0, 1) == "_"){
        //it is vlabel
        var realLbl = lbl.substr(1);
        nextPC = this.vlabelMap[realLbl];
    }else{
        nextPC = this.labelMap[lbl];
    }
 
    if (nextPC == null){
        Errors.push({
            type: Errors.RUNTIME_ERROR,
            msg: "Label not found",
            line: 0
        });
    }else{
        this.pc = nextPC;
    }
}

最後要改寫一下那些跳轉程式的寫法,把它們改成使用 easyJump 來跳轉,這裏就用 beq 來做例子。

Wemachine.prototype.beq = function (operand1, operand2, operand3){
    var val1 = this.getRegisterContent(operand1);
    var val2 = this.getRegisterContent(operand2);
    if (val1 == val2){
        this.easyJump(operand3);
    }
}

比之前簡潔了很多吧其他跳轉的做法也差不多,這裏不詳述了。

var a:int = 1;
		print a--;
		print a;
		
		lwi $0, 1;
		lwi $1, 1;
		beq $0, $1, _lbl1;
		print $0;
		vlabel lbl1;
		addi $2, $0, 1;
		print $2;
		
2

好了,改寫了 Wemachine,我們改寫了未來 ,現在要做的事就是要生成 if 和 while 的 Wemachine code。

if

Compiler.prototype.evaluateIfNode = function (node){
    var condReg = this.evaluateExpressionNode(node.conditionExpression);
 
    var elseLbl = this.getNextLabel();
    var endLbl = this.getNextLabel();
 
    this.writeln("beq " + condReg + "," + this.falseRegister + "," + "_" + elseLbl + ";");
    this.evaluateExpressionBlockNode(node.expressions);
    this.writeln("j _" + endLbl + ";");
 
    this.writeln("vlabel " + elseLbl + ";");
    this.evaluateExpressionBlockNode(node.elseExpressions);
    this.writeln("vlabel " + endLbl + ";");
}

if 要做什麼呢?首先就是要做一個判斷,看看條件式是否不成立,不成立的話就要跳到 else 的位置,成立的話只需直接執行落去就可以了。但要緊記,不能一直執行下去,當完成執行時就要跳到 else block 之後,不然條件式成立與否 else block 都會運行。if 就是這樣了,不太難吧,不暪你說,其實 while 更容易!

while

Compiler.prototype.evaluateWhileNode = function (node){
    var whileLbl = this.getNextLabel();
    var endLbl = this.getNextLabel();
 
    this.writeln("vlabel " + whileLbl + ";");
    var condReg = this.evaluateExpressionNode(node.conditionExpression);
    this.writeln("beq " + condReg + "," + this.falseRegister + "," + "_" + endLbl + ";");
 
    this.evaluateExpressionBlockNode(node.expressions);
    this.writeln("j _" + whileLbl + ";");
    this.writeln("vlabel " + endLbl + ";");
}

又是判斷條件式,如果不成立的話就直接跳到 end label 結束 while 迴圈,不然就繼續執行,並且每次執行完都跳到最頂再做一次條件式判斷。很容易吧!運行一下看看運作是否正常。

var a:int = 3;
		while (a != 0){
			print a;
			a--;
		}
		
		if (a == 0){
			print 0;
		}else{
			print 1;
		}
		
lwi $0,1;
lwi $1,0;
lwi $3,3;
move $2,$3;
move $4,$2;
vlabel lbl0;
move $5,$4;
lwi $7,0;
move $6,$7;
move $10,$5;
move $11,$6;
lwi $8,0;
label lbl2;
label lbl4;
add $10,$10,$8;
lwi $9,0;
beq $8,$0,lbl2;
label lbl3;
lwi $9,1;
beq $8,$0,lbl2;
label lbl2;
lwi $8,1;
beq $10,$11,lbl4;
move $5,$9;
beq $5,$1,_lbl1;
move $12,$4;
print $12;
move $13,$4;
subi $4,$4,1;
j _lbl0;
vlabel lbl1;
move $14,$4;
lwi $16,0;
move $15,$16;
move $19,$14;
move $20,$15;
lwi $17,0;
label lbl5;
label lbl7;
add $19,$19,$17;
lwi $18,1;
beq $17,$0,lbl5;
label lbl6;
lwi $18,0;
beq $17,$0,lbl5;
label lbl5;
lwi $17,1;
beq $19,$20,lbl7;
move $14,$18;
beq $14,$1,_lbl8;
lwi $22,0;
move $21,$22;
print $21;
j _lbl9;
vlabel lbl8;
lwi $24,1;
move $23,$24;
print $23;
vlabel lbl9;
3
2
1
0

運作正常,那就大功告成啦!

本章就此完結了,Wescript compiler 也可以算是完成了,從讀取 Wescript 到建立 parse tree,再到本章生成代碼,一路走來用的技巧都是 mutual recursion,可見其重要性,大家要好好掌握這個技巧,那麼大家編寫自己的 compiler 時也能得心應手~

compiler  


{{ ctrl.votes | shortNumber: 0 }}
寫於 {{ '2017-08-14T09:52:27.854Z' | calendarTime }}

{{ $root.errMsg }}