從零手寫 C 語言編譯器：最小可行編譯器實作全紀錄

編輯：關於C語言

從零手寫 C 語言編譯器：最小可行編譯器實作全紀錄

動手寫一個編譯器，是理解計算機如何工作的最佳途徑。遵循 Abdulaziz Ghuloum 論文《An Incremental Approach to Compiler Construction》「從最小可用子集開始，逐步擴展」的哲學，本文記錄從 int main() { return 2; } 這個最簡單程式開始，一步步構建 babyc 編譯器的完整過程：詞法分析、語法分析、代碼生成、組裝鏈接、執行驗證。

階段 0：目標程式

// return_two.c
int main() {
    return 2;
}

階段 1：詞法分析

使用 Flex 定義 Token：

/* lexer.l */
%{
#include "parser.h"
%}

"{"     return '{';
"}"     return '}';
"("     return '(';
")"     return ')';
";"     return ';';
[0-9]+  { yylval = atoi(yytext); return NUMBER; }
"return" return RETURN;
"int"   return TYPE;
"main"  return IDENTIFIER;
[ \t\n]  ;  // 忽略空白
.       { fprintf(stderr, "Unknown char: %s\n", yytext); }

階段 2：語法分析

使用 Bison 定義文法：

/* parser.y */
%{
#include <stdio.h>
#include <stdlib.h>
void yyerror(const char *s) { fprintf(stderr, "%s\n", s); exit(1); }
%}

%token NUMBER RETURN TYPE IDENTIFIER

%start program

%%
program: function ;
function: TYPE IDENTIFIER '(' ')' '{' expression '}' ;
expression: RETURN NUMBER ';' ;
%%

階段 3：代碼生成（x86 32 位組合語言）

/* 目標輸出 out.s */
.text
.global _start
_start:
    movl $2, %ebx    # 返回值放入 %ebx (sys_exit 參數)
    movl $1, %eax    # 系統呼叫號 sys_exit = 1
    int $0x80        # 觸發中斷進入核心

階段 4：整合編譯器主程式

/* compiler.c 簡化版 */
int main(int argc, char **argv) {
    FILE *src = fopen(argv[1], "r");
    yyin = src;
    yyparse();  // 語法分析並觸發代碼生成動作
    fclose(src);
    return 0;
}

階段 5：編譯、組裝、鏈接、執行驗證

# 1. 編譯編譯器本身
flex lexer.l
bison -d parser.y
gcc lex.yy.c parser.tab.c compiler.c -o babyc

# 2. 使用 babyc 編譯目標程式
./babyc return_two.c
# 輸出 out.s

# 3. 組裝為目標檔 (32 位)
as out.s -o out.o --32

# 4. 鏈接為可執行檔
ld -m elf_i386 -s -o out out.o

# 5. 執行並檢查返回碼
./out
echo $?  # 輸出 2 → 成功！

擴展路線圖：從 babyc 到完整子集

步驟	新增特性	學習重點	修改點
1	任意返回值 `return 42;`	立即數編碼、寄存器分配	代碼生成
2	一元運算 `return ~1;`	運算符優先級、AST 節點	語法分析、代碼生成
3	變數定義與賦值	符號表、棧幀佈局、記憶體存取	詞法/語法/代碼生成
4	二元運算 + - * /	表達式樹、暫存器分配	語法分析、代碼生成
5	if 條件判斷	控制流圖、標籤生成、跳轉指令	語法分析、代碼生成
6	while 迴圈	迴圈標籤、條件跳轉	語法分析、代碼生成
7	函數呼叫	呼叫慣例、參數傳遞、返回位址	代碼生成、運行時
8	陣列/結構體	記憶體佈局、位移計算	符號表、代碼生成