從簡單的四則運算機來看編譯和組譯

這篇希望能用比較淺顯易懂的方式介紹編譯器和組譯器, 首先假設我們有一台計算器可以執行使用者輸入的運算, 這台計算器有下列的暫存器可以使用

ax //通用暫存器, 可用於儲放資料
sp //堆疊
pc //program counter 程式執行的位置

而該計算機可解析和執行下列幾種運算

MV: 資料搬移
PUSH: 把ax推入stack
ADD: 資料相加
MUL: 資料相乘
SUB: 資料相減
DIV: 資料相除
EXIT: 結束執行並返回堆疊內的資料

根據運算子和資料, 可以兜出這個計算器的組合語言, 比如說1+2這則運算, 可以兜出如下的組合語言

MV 
1
PUSH
ADD 
2
PUSH
EXIT

針對該計算器的運算子與資料處理方式, 可以寫出如下的虛擬該計算器的C程式碼, 該程式從PC指到的位置中取得op code, 並藉由OP code的判斷決定下一步是運算還是資料搬移並做出對應的處理

int execute()
{
	int op;
	
	while (1) 
	{
    	op = *pc++; // get next operation code	
    	if (op == MV) {ax = *pc++; printf("move :%ld\n",ax);}  
    	else if (op == PUSH) {*--sp = ax;printf("PUSH :%ld\n",ax);}
    	else if (op == ADD) {printf("ADD :%ld\n",ax);ax = *sp++ + ax;}
    	else if (op == MUL) {printf("MUL :%ld\n",ax);ax = *sp++ * ax;}
    	else if (op == SUB) {printf("SUB :%ld\n",ax);ax = *sp++ - ax;}
    	else if (op == DIV) {printf("DIV :%ld\n",ax);ax = *sp++ / ax;}
    	else if (op == EXIT) { printf("exit(%ld)\n", *sp); return *sp;}
    	else  return 0;
    }
}

至此可以說是完成了一個擁有3個暫存器的組合語言執行器, 接下來是如何產生這樣的組合語言

這邊我借用了清大陳煥宗老師寫的Lexical analyzer, 該Lexical analyzer大致的邏輯思路為截取使用者輸入的statement, 並對裡面的資料與運算式做語法分析, 而語法分析都有一套固定的套路如下樹狀圖

以根結點statement為例, 它必需處理expr與END, 所以它的函式可寫成如下

void statement(){
     if (match(END)){
       //handle END toke here
     }else{
       //handle expression here
     }
}

而expr必需處理term與expr_tail, 所以它的函式如下

void expr(){
     term();
     expr_tail();
}

所以照著Lexical analysis的規則, 在ADDSUB和MULDIV的節點加入虛擬機的組合語言如下原始碼片段

void expr_tail(void)
{
    if (match(ADDOP)){
        printf("ADDs: %s\n", getLexeme());
    	text[pos++] = PUSH;
        advance();
        term();
        text[pos++] = ADD;
        expr_tail();
 
    }
    else if (match(SUBOP)){
        printf("SUB: %s\n", getLexeme());
        text[pos++] = PUSH;
        advance();
        term();
        text[pos++] = ADD;
        expr_tail();
    } 
    else {
        // NIL
        text[pos++] = PUSH;
        text[pos++] = EXIT;
    }
}

void term_tail(void)
{
    if (match(MULOP)) {
        printf("MUL: %s\n", getLexeme());
		text[pos++] = PUSH;
        advance();
        factor();
        text[pos++] = MUL;
        term_tail();
    }
    else if (match(DIVOP)) {
        printf("DIV: %s\n", getLexeme());
        text[pos++] = PUSH;
        advance();
        factor();
        text[pos++] = DIV;
        term_tail();
    }  
    else {
        // NIL
         //text[pos++] = EXIT;
    }
}

完整程式的範例可參考這裡

藉由這個簡單打造4則運算機的範例, 可以知道compiler和assembler在程式編譯的過程中做語法分析與機器碼轉譯的步驟, 原理其實不難, 但可藉由此例一窺編譯器實做中所需具備的知識

[參考資料]

1. 手把手教你構建C語言編譯器