Blog • 一个最简单的编译器的实现

本文将会带领读者做出一个简单的类C（但比C简单无数倍）语言的编译器。

参考代码在这里，本文完成时的版本是这个。

这个语言支持：

两种基本数据类型：int 和 double
上述数据类型的数组
两种控制结构：if（当然可以有可选的 else）和 while
基本数学和关系运算：+、-、*、/、<、<=、>、>=、==、!=

本文假设读者是一个比较熟练的C语言¹程序猿，并具有基本的正则表达式知识。

同时本文读者应当熟悉 flex & bison 的基本使用，如果你对此不熟悉，可以参考我的另一篇文章。

编译过程

首先本文中所述的编译器编译一个程序的过程如下²：

routine

显然很多代码都不用我们自己写，生在这样一个有丰富工具的时代既是幸运，也是一种不幸。

词法分析

在此给出 flex 的关键部分代码：

"char"                      {yylval.type=Char; return TYPE;}
"int"                       {yylval.type=Int; return TYPE;}
"double"                    {yylval.type=Double; return TYPE;}
"string"                    {yylval.type=String; return TYPE;}
"if"                        {return IF;}
"else"                      {return ELSE;}
"while"                     {return WHILE;}
"print"                     {return PRINT;}
([-])?[0-9]+                {yylval.int_value=atoi(yytext); return INT_LITERAL;}
([-])?[0-9]+\.[0-9]*        {yylval.double_value=atof(yytext); return DOUBLE_LITERAL;}
[a-zA-Z][0-9a-zA-Z_]*       {yylval.string_value=strdup(yytext); return IDENTIFY;}
"=="                        {return EQUAL;}
"!="                        {return NONEQUAL;}
"<"                         {return *yytext;}
"<="                        {return LESSEQ;}
">"                         {return *yytext;}
">="                        {return GREATEREQ;}
"+"                         {return *yytext;}
"-"                         {return *yytext;}
"*"                         {return *yytext;}
"/"                         {return *yytext;}
"["                         {return *yytext;}
"]"                         {return *yytext;}
[ \t]                       {}
.                           {return *yytext;}

语法分析

在此给出 bison 的关键部分代码：

program:
    program statement           
    |                          
    ;

assign:
    '=' expression             
    ;

defineStatement:
    TYPE IDENTIFY ';'
    | TYPE IDENTIFY '[' INT_LITERAL ']' ';' 
    | TYPE IDENTIFY assign ';'
    ;

assignStatement:
    referenceExpression assign ';'
    ;

statementList:
    statementList statement                 
    |                                       
    ;

block:
    '{' statementList '}' 
    ;

ifStatement:
    IF expression block                   
    | IF expression block ELSE block        
    ;

whileStatement:
    WHILE expression block                  
;

printStatement:
    PRINT '(' expression ')' ';'
;

statement:
    defineStatement
    | assignStatement
    | block
    | ifStatement
    | whileStatement
    | printStatement
;

referenceExpression:
    IDENTIFY 
    | IDENTIFY '[' expression ']' 

atomExpression:
    INT_LITERAL                            
    | DOUBLE_LITERAL                      
    | referenceExpression                  
    | '(' expression ')'                  
    ;

unaryOperator:
    '+'
    | '-'
    | '!'
    ;

unaryExpression:
    atomExpression                        
    | unaryOperator atomExpression         
;

binaryOrAtomExpression:
    unaryExpression                                    
    | binaryOrAtomExpression '+' unaryExpression       
    | binaryOrAtomExpression '-' unaryExpression   
    | binaryOrAtomExpression '*' unaryExpression        
    | binaryOrAtomExpression '/' unaryExpression      
    | binaryOrAtomExpression '<' unaryExpression       
    | binaryOrAtomExpression '>' unaryExpression       
    | binaryOrAtomExpression LESSEQ     unaryExpression 
    | binaryOrAtomExpression GREATEREQ  unaryExpression
    | binaryOrAtomExpression EQUAL      unaryExpression 
    | binaryOrAtomExpression NONEQUAL   unaryExpression 
;

expression:
    binaryOrAtomExpression 
    ;

注意此处没有给出相应的行为代码，因为首先需要理解AST才能明白这些行为。

AST（抽象语法树）

抽象语法树将语法分析得到的语法单元组织成树状。

基本上每个statement和expression都可以对应AST上的一个node。

本编译器的AST设计

部分参考了llvm的AST设计。

ast

因此我们就能写出 %union 和 %type：

%union {
    int int_value;
    double double_value;
    char* string_value;
    ASTNode* node;
    SymbolType type;
};

%token <type> TYPE
%token <string_value> IDENTIFY
%token <int_value> INT_LITERAL
%token <double_value> DOUBLE_LITERAL
%token <type> STRING INT DOUBLE
%token <void> IF ELSE WHILE FOR
%token <void> LESSEQ GREATEREQ EQUAL NONEQUAL
%token <void> PRINT

%left '>' '<' LESSEQ GREATEREQ EQUAL NONEQUAL
%left '+' '-'
%left '*' '/'

%type <node> statement assignStatement statementList block ifStatement whileStatement defineStatement printStatement
%type <node> expression referenceExpression assign atomExpression unaryExpression binaryOrAtomExpression
%type <node> program

整个程序是一个 CompoundStatement，我们要把结果存在一个全局变量中：

CompoundStatement *result;

然后向 bison 代码中加入行为部分，以 program 和 binaryOrAtomExpression 为例：

program:
    program statement           {add_statement((CompoundStatement *)$1, (Statement*)$2);}
    |                           {result=create_compound_statement(); $$=(ASTNode*)result;}
    ;

binaryOrAtomExpression:
    unaryExpression                                     {$$=$1;}
    | binaryOrAtomExpression '+' unaryExpression        {$$=(ASTNode*)create_binary_operation_result('+',(RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression '-' unaryExpression        {$$=(ASTNode*)create_binary_operation_result('-',(RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression '*' unaryExpression        {$$=(ASTNode*)create_binary_operation_result('*',(RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression '/' unaryExpression        {$$=(ASTNode*)create_binary_operation_result('/',(RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression '<' unaryExpression        {$$=(ASTNode*)create_binary_operation_result('<',(RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression '>' unaryExpression        {$$=(ASTNode*)create_binary_operation_result('>',(RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression LESSEQ     unaryExpression {$$=(ASTNode*)create_binary_operation_result(LESSEQ, (RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression GREATEREQ  unaryExpression {$$=(ASTNode*)create_binary_operation_result(GREATEREQ,(RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression EQUAL      unaryExpression {$$=(ASTNode*)create_binary_operation_result(EQUAL, (RValue*)$1,(RValue*)$3);}
    | binaryOrAtomExpression NONEQUAL   unaryExpression {$$=(ASTNode*)create_binary_operation_result(NONEQUAL, (RValue*)$1,(RValue*)$3);}

符号表与作用域

这个编译器由于不涉及多文件，也没有复杂类型，符号表的设计较为简单，维护一个全局符号表栈即可：

typedef enum {
    Bool,
    Int,
    String,
    Double,
    Array
} SymbolType;

typedef struct {
    SymbolType type;
    bool mutable;
    char *name;
    size_t namespace_id;
} Symbol;

typedef struct {
    Symbol base;
    SymbolType elementType;
    size_t length;
} ArraySymbol;

typedef struct {
    size_t length;
    Symbol **symbols;
    size_t namespace_id;
} SymbolTableFrame;

typedef struct {
    size_t length;
    SymbolTableFrame **frames;
} SymbolTableStack;

SymbolTableStack symbol_table_stack = {0, NULL};

void push_frame();

void pop_frame();

void add_symbol(Symbol *symbol);

Symbol *get_symbol(char *name);

其中 get_symbol 从栈顶向栈底寻找名字为 name 的符号。

在 add_symbol 时，会设置 symbol 的 namespace_id 为 frame 的 namespace_id，这在代码生成时会作为变量名称的一部分出现。

在语法分析时：

block:
    '{' {push_frame();} statementList '}'   {$$=$3;pop_frame();}
    ;

每遇到一个 block，就 push 一个 frame，离开 block 时 pop 即可，这样这个 block 内声明的 symbol 就会获得一个和这个 block 对应的 namespace_id。

在使用 symbol 时，由于刚刚进入的 block 对应的 frame 在栈顶附近，故会优先在这个 frame 中寻找名字为 name的符号，在这个 frame 中找不到时才会逐级向上寻找，这样就实现了作用域。

目标代码生成

为了方便代码跨平台和借用 llvm 的优秀的代码优化能力³，我们的目标代码是 LLVM IR。

LLVM IR兼有高级语言和汇编的特点，比如：

LLVM IR 是强类型的
LLVM IR 中的许多控制结构类似汇编，如 if、while 等控制结构都通过 br 跳转来表示
LLVM IR 中的”局部变量”相当程度上是一个”寄存器”，但 LLVM IR 逻辑上有无限多的这种”寄存器”，需要注意的是 LLVM IR是一种 SSA 形式的 IR，所以一个”寄存器”只能赋值一次。
LLVM 的很多操作都类似汇编的格式，如：%a = add i32 1, %b 类似 add %a, 1, %b

在此讲一些我们用到的 LLVM IR：

变量定义

用 alloca 在栈上开辟一块空间：

%i_0 = alloca i32

注意 alloca 返回的是一个指针。

变量的赋值

使用 store：

store i32 0, i32* %i_0

即将 0 放入 %i_0 所指的变量中。

读取变量的值

用 load：

%temp = load i32, i32* %i_0

即将 %i_0 所指的变量中的值放入 %temp 寄存器中。

运算

以加法为例：

%temp_22 = add i32 %temp_21, 1

即将 %temp_21 + 1 的值放入 %temp_22 中。

对于浮点数，用 fadd 代替 add。

比较

使用 icmp 与比较类型：

%temp_2 = icmp slt i32 %temp_1, 10

其中 slt 是“Signed Less Than”，即<。

浮点相应的有 fcmp 、olt等。

跳转

使用 br 进行跳转：

无条件

br label %label1

有条件

br i1 %condition, label %condition_true, label %condition_false

有这些个东西就够了。

然后我们就可以进行代码生成了。

例如变量声明：

static void generate_code(DeclareStatement *node) {
    printf("%%%s_%zu = alloca %s\n", node->variable->name, node->variable->namespace_id, type_name(node->variable));
    // 带初始化，则再生成一个赋值语句
    if (node->initial != NULL) {
        ((Statement *) (node->initial))->generate_code((Statement *) (node->initial));
    }
}

赋值：

static void generate_code(AssignStatement *node) {
    ((LValue *) (node->lhs))->generate_lvalue_code((LValue *) (node->lhs));
    node->rhs->generate_rvalue_code(node->rhs);
    char *rvalue_ir = node->rhs->rvalue_ir(node->rhs);
    char *lvalue_ir = node->lhs->lvalue_ir(node->lhs);
    printf("store %s %s, %s* %s\n",
           type_string(((RValue *) (node->lhs))->type),
           rvalue_ir,
           type_string(((RValue *) (node->lhs))->type),
           lvalue_ir);
    free(rvalue_ir);
    free(lvalue_ir);
}

对expression来说，左值右值要分开，以普通变量为例：

// 右值需从变量读取到寄存器才能使用
static void generate_rvalue_code(VariableReference *rValue) {
char *rvalue_ir_string = ((RValue *) rValue)->rvalue_ir((RValue*) rValue);
    char *lvalue_ir_string = ((LValue*) rValue)->lvalue_ir((LValue *) rValue);
    printf("%s = load %s, %s* %s\n",
           rvalue_ir_string,
           type_name(rValue->variable),
           type_name(rValue->variable),
           lvalue_ir_string);
    free(rvalue_ir_string);
    free(lvalue_ir_string);
}

// 左值无需读取出来
static void generate_lvalue_code(VariableReference *lValue) {
}

// 做左值时ir中的变量名
static char *lvalue_ir(VariableReference *lValue) {
    char *result = malloc(128);
    sprintf(result, "%%%s_%zu", lValue->variable->name, lValue->variable->namespace_id);
    return result;
}

// 做右值时ir中的变量名
static char *rvalue_ir(VariableReference *rValue) {
    char *result = malloc(128);
    sprintf(result, "%%temp_%zu", rValue->temp_register_id);
    return result;
}

其他代码如何生成可以由读者自己想出来，对我的实现感兴趣的话请自行阅读代码。

参考资料

编译原理

龙虎鲸三连：

《编译原理》——“龙书”
《现代编译原理：Ｃ语言描述》——“虎书”
《高级编译器设计与实现》——“鲸书”

参考词法 & 文法

LLVM IR

llvm 官方网站，尤其是其语言参考
mapping high level constructs to llvm ir

代码中将会使用C语言的面向对象编程，见用纯C实现面向对象编程。这东西用多了就有一种C语言远比C++好用的感觉（Linus一点都没说错）。

其实在构造AST里我偷偷摸摸做了一丁点语义分析。

其实是因为我懒。