Hoes of Tech

Conceptualization of Technology

Build Compiler with LALR(1) Parser Generator(III)

在经过前两章的奋战之后, 我们对于Parser终于多少有了点理解——虽然还有一些遗留问题。至少现在已经可以把一门简单的语言编译成bytecode然后解析执行了。不过就像上一章里所说的,有些时候我们还希望能够把程序编译成可执行文件,在这一篇文章里我们就来做这件事情,不用担心,并不是所有的工作都是由compiler来做的。在这里,基于前一章编译出来的ByteCode,我们首先生成汇编代码,然后通过NASM编译成elf object,最后通过ld链接成可执行文件。

首先来熟悉下最简单的汇编程序,比如一个Hello,World可以写成下面的样子:

global _start
section .text

_print:
    push rdx
    push rax
    push rbx
    mov edx, 1
    mov eax, 4
    mov ebx, 1
    int 0x80
    pop rbx
    pop rax
    pop rdx
    ret

_start:
    mov ecx, str1
    mov eax, [size]
_loop1:
    call _print
    inc ecx
    dec eax
    test eax, eax
    jne _loop1
    mov eax, 1
    mov ebx, 0
    int 0x80

section .data
    str1 db 'hello,world',0x0A,0x00
    size dd 12

当然这个例子并不是最好的写法,毕竟sys_write提供了一次性输出,不过考虑到跟接下来Brainfuck的衔接,还是吧print单独写成一个函数更加简单。另外需要注意的是虽然上面的代码是64位的,如果需要编译成elf32,那么需要把_print里面的push rxx改成push exx。

仔细观察上面的小例子,结合上一张的brainfuck语言,会发现其实实现一个ByteCode to assembly并不是很困难,只要从前向后解析Bytecode,然后printf(writeln)对应的汇编代码而已, 剩下的工作全部是Assembler和linker的了。作为第一步,首先来定义几个必要的函数:

_read:
    push rdx
    push rax
    push rbx
    push rbp
    mov dword [ecx], 0x30
    xor rbp, rbp
_start_read:
    sub dword [ecx], 0x30
    imul ebp, 10
    add ebp, dword [ecx]
    mov edx, 1
    mov eax, 3
    mov ebx, 0
    int 0x80
    cmp byte [ecx], 0x30
    jl _end_read
    cmp byte [ecx], 0x39
    jg _end_read
    cmp byte [ecx],0x0A
    jne _start_read
_end_read:
    mov [ecx], ebp
    pop rbp
    pop rbx
    pop rax
    pop rdx
    ret

_error:
    mov rcx, memover
    xor rbp, rbp
    mov ebp, dword [memsize]
_loop_error:
    call _print
    dec rbp
    inc rcx
    test rbp, rbp
    jg _loop_error
    ret

首先,除了最初的print之外,唯一需要的函数就是read了,它负责将stdin的内容读进目前磁头所指向的磁带。跟原始的brainfuck语言的spec稍有不一样的是:原语言的规格里认为磁带里每一个section都是byte,而为了能够进行更大规模的输入,这里每个section都是一个dword。另外,虽然理想的图灵机考虑有无限长的纸片,显然实际上是不可能的,所以当磁头走出预先定义的范围时,需要报一个内存溢出的错误。 在这里memover可以是任何有意义的错误提示,而memsize则是对应字符串的长度(dd类型)。这些函数都是完全固定的,因此并不需要特别的处理,只需要在compiler执行的时候输出它们就足够了。 剩下的就是简单的用汇编实现每个brainfuck operator的功能:

const memSize = 5096;
const loopPrefix = "_loop";
const loopSuffix = "_loopend";

string assemble(ulong[] op){
    string ret;
    int[] labelList;
    int uniqCount = 0;
    ret =
`global _start
section .text

_print:
    push rdx
    push rax
    push rbx
    mov edx, 1
    mov eax, 4
    mov ebx, 1
    int 0x80
    pop rbx
    pop rax
    pop rdx
    ret

_read:
    push rdx
    push rax
    push rbx
    push rbp
    mov dword [ecx], 0x30
    xor rbp, rbp
_start_read:
    sub dword [ecx], 0x30
    imul ebp, 10
    add ebp, dword [ecx]
    mov edx, 1
    mov eax, 3
    mov ebx, 0
    int 0x80
    cmp byte [ecx], 0x30
    jl _end_read
    cmp byte [ecx], 0x39
    jg _end_read
    cmp byte [ecx],0x0A
    jne _start_read
_end_read:
    mov [ecx], ebp
    pop rbp
    pop rbx
    pop rax
    pop rdx
    ret

_error:
    mov rcx, memover
    xor rbp, rbp
    mov ebp, dword [memsize]
_loop_error:
    call _print
    dec rbp
    inc rcx
    test rbp, rbp
    jg _loop_error
    ret

_start:
    xor rax, rax
    xor rbx, rbx
    xor rcx, rcx
    xor rdx, rdx
    mov rax, arr
    mov rdx, arr
    add edx, [size]
`;

    size_t i= 0;
    while(i<op.length){
        switch(op[i]){
            case 0:
                ret ~= "\tadd rax,4\n\tcmp eax, edx\n\tjge _exit_error\n";
                break;
            case 1:
                ret ~= "\tsub eax,4\n";
                break;
            case 2:
                ret ~= "\tinc dword [eax]\n";
                break;
            case 3:
                ret ~= "\tdec dword [eax]\n";
                break;
            case 4:
                ret ~= "\tmov ecx, eax\n\tcall _print\n";
                break;
            case 5:
                ret ~= "\tmov ecx, eax\n\tcall _read\n";
                break;
            case 6:
                ret ~= "\tmov ebx, [eax]\n\ttest ebx,ebx\n\tje "~loopSuffix~(uniqCount).to!string~"\n";
                ret ~= loopPrefix~uniqCount.to!string~":\n";
                labelList ~= uniqCount;
                i++; uniqCount ++;
                break;
            case 7:
                ret ~= "\tmov ebx, [eax]\n\ttest ebx, ebx\n\tjne "~loopPrefix~labelList[$-1].to!string~"\n";
                ret ~= loopSuffix~labelList[$-1].to!string~":\n"; i++;
                labelList = labelList[0..$-1];
                break;
            default:
                throw new Exception("Unknown Operator");
        }
        i++;
    }
     ret ~= 
"_exit_main:
    mov eax, 1
    mov ebx, 0
    int 0x80

_exit_error:
    call _error
    mov eax, 1
    mov ebx, 1
    int 0x80

";
    ret ~= "section .data\n arr\ttimes "~memSize.to!string~" dd 0\n\tsize dd "~(memSize*4).to!string;
    ret ~= "\n\tmemover db 'mem overflow',0x0A,0x00\nmemsize dd 13";

    return ret;
}

这个工作或许很枯燥,不过没有一点难度。 唯一需要注意的就是在处理循环时,会遇到跟SourceCode to ByteCode Compiler同样的问题——当循环嵌套时,如何寻找对应的label? 这里我们用了一个类似堆栈的结构: 每当循环开始,这个循环的地址(label)都会被push进堆栈, 而遇到循环结束时, 只需要简单的从堆栈里pop出来就可以了。最后,在程序结束时,不要忘记使用sys_exit来退出程序,用ebx可以指定exit code。最后,用这个程序来编译下hello world,可以得到:

global _start
section .text

.... PRE DEFINED FUNC ....

_start:
    xor rax, rax
    xor rbx, rbx
    xor rcx, rcx
    xor rdx, rdx
    mov rax, arr
    mov rdx, arr
    add edx, [size]
    inc dword [eax]
    inc dword [eax]
    inc dword [eax]
    inc dword [eax]
    inc dword [eax]
    inc dword [eax]
    inc dword [eax]
    inc dword [eax]
    inc dword [eax]
    inc dword [eax]
    mov ebx, [eax]
    test ebx,ebx
    je _loopend0
_loop0:
    add rax,4

    .... LOOP BODY ...

    test ebx, ebx
    jne _loop0
_loopend0:
    add rax,4
    cmp eax, edx
    jge _exit_error

    .... PRINT ....

    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    mov ecx, eax
    call _print
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    dec dword [eax]
    mov ecx, eax
    call _print
    add rax,4
    cmp eax, edx
    jge _exit_error
    inc dword [eax]
    mov ecx, eax
    call _print
    add rax,4
    cmp eax, edx
    jge _exit_error
    mov ecx, eax
    call _print
_exit_main:
    mov eax, 1
    mov ebx, 0
    int 0x80

_exit_error:
    call _error
    mov eax, 1
    mov ebx, 1
    int 0x80

section .data
 arr    times 5096 dd 0
    size dd 20384
    memover db 'mem overflow',0x0A,0x00
memsize dd 13

因为全部的源代码很长并且没有什么意义, 大部分内容都被省略掉了。不过可惜的是这么直接生成的代码一点也不漂亮,更不高效,充满着让人忍不住去优化的部分,那些内容是Optimizer的工作,在这里我们不会触及。总之,这是一个可运行的代码,剩下的就是编译一下即可:

./compiler test.bf test
./assem test test.asm
nasm -f elf64 test.asm
ld test.o -o test

运行下最终生成的test,屏幕上将会显示出Hello,world。

好了, 到这里为止我们完成了Brainfuck的一个Lexer,Parser,ByteCodeCompiler,VM,以及最简单的到汇编的转换器。虽然省略了相当多的细节,毕竟是第一个可以正常运行的编译器。下面的工作就是回归最初的问题——如何给最初的计算器添加循环/判断和函数?

如果在刚刚完成最初版本的计算器时提出这个问题, 或许没有答案,但放到现在,一切就显得很自然了——跟Brainfuck里的括号运算符一样,只需要把源程序编译成ByteCode即可,甚至可以不编译,只要能够把它Parse成某种可以运行的形式,剩下的循环不过是简单的添加一个指令而已。既然有了明确的答案,那么先来回想下在Brainfuck里的做法: 我们给每一个operator都定义了一个数字,然后按照顺序把它们放进一个数组,当遇到循环时会插入硬编码过的地址…… 对于简单的程序语言似乎没什么问题,但当语言变得复杂,可以想象这个过程会多么容易出错,所有的东西都要直接写在Parser的执行部,并且所有的内容都或多或少有些不一样。因此我们需要一个容易描述程序的结构,它叫做Abstract Syntax Tree,简写为AST,中文称它为抽象语法树。看名字似乎很高端,但实际上所做的事情跟普通的树没什么大差别,下面这幅图来自与AST的维基百科.

AST

让我们来手动模拟一下它的执行过程: 首先是Statement节点,它本身没有什么意义,然后深度搜索这棵树,左侧是while节点,于是我们知道这是一个循环结构,而它的循环条件放在树的左侧,向下探索就会遇到compare,这个节点需要比较左右值的内容,继续向下探索,最终我们遇到了的左端的b。按照深度探索的规则,继续向右,会找到第二个值(右值),这两个节点执行之后会返回他们的内容,随后返回到compare节点,有了这左右值之后,我们自然就可以比较结果了,之后的循环体也如发炮制即可。

可以看到AST的想法很简单,将所有程序的elements都化为结点,用树来表示它们的结构,进一步想象一下,如果每一个节点都有一个Execute的function来执行自己对应的命令,那么我们需要做的就是Stat.Execute()而已。并且最大的优势在于,编写节点的Execute时,因为所有内容都是递归执行的,因此不必考虑当前指令的执行者来自与哪里,只需要执行玩自己的命令,然后返回相应的值即可。下面来实现一个简单的AST,因为当前的AST还不是特别复杂,我们可以按照自己的想法来编码。

首先来定义一个基本Class,所有的节点都要从继承这个class。

class ASTNode{
    public{
        string id;
        double value;
        int time;
        ASTNode[] node;
        void add(ASTNode n){ node ~= n; }
        abstract double evaluate();
    }
}

ASTNode[string] tab;

node用来储存字节点,evaluate用来取得当前节点的返回值,id和value用来储存值和ident,下面会用到。另外考虑到变量的问题,这里把之前定义在parser里的table也移了过来,鉴于目前的程序并没有scope一说,可以直接把所有变量都当成全局变量。下面先来实现常量和变量:

final class nul: ASTNode{
    override double evaluate(){
        return 0;
    }
}

final class num: ASTNode{
    override double evaluate(){
        return value;
    }
}

final class var: ASTNode{
    override double evaluate(){
        if((id in tab) !is null)
            return tab[id].evaluate;
        else return 0;
    }
}

常量直接储存在了节点的value里面,但这并不是普通的做法,以后我们会渐渐改掉,而变量则储存在了table里面。还有一个nul用来表示空值,比如什么都没有的statement。其他的节点也都类似:

final class plus: ASTNode{
    override double evaluate(){
        return node[0].evaluate+node[1].evaluate;
    }
}

final class pr: ASTNode{
    override double evaluate(){
        double res;
        for(size_t i=0; i<node.length; i++){
            res = node[i].evaluate;
            writefln("%.20f", res);
        }
        return res;
    }
}

final class eq: ASTNode{
    override double evaluate(){
        auto n = new num;
        n.value = node[1].evaluate;
        tab[node[0].id] = n;
        return n.value;
    }
}

上面三个分别是加法,输出(print)和变量赋值(定义),这里的实现稍微有些绕弯子。其他的已有的元素都可以仿照上面来逐个定义。对于循环结构,一切也没有什么变化:

final class loop: ASTNode{
    override double evaluate(){
        double res;
        while(node[0].evaluate > 0){
            for(size_t j=1; j<node.length; j++){
                res = node[j].evaluate;
            }
        }
        return res;
    }
}

这个循环结构无非就是不停的执行循环体,然后返回最后一次的值而已(因为之前定义了所有的block都有自己的返回值),而真正的循环是又D语言的循环结构实现的,再向下想象,D语言的结构是又汇编的test,jnz来实现的,汇编的循环最终是由硬件来实现的——也就是说我们并没有“创造”循环,而只是把最初的循环换成了更容易使用的形式而已。

好了,说了一堆,甚至把AST都写好了,还没有给出循环的parser,首先来看一个想象的例子:

c = 50
loop (c=c-1)(
    b = 1
    a = c
    loop (a=a-1)(
        b = b*a
    )
    print b
)

这是一个计算\(n!\)的例子,等于好代表变量赋值,loop代表这循环结构,后边紧跟一个block表示循环条件,随后是循环体。再次提醒,因为计算器只有float类型,所以循环只能用当前值是否大于0来判断,而之前规定了所有block都有返回值,因此在循环条件的部分不需要特殊处理,只需要一个code block即可。如果把实数全部改成自然数的话,相信每个人都能简单的把这个程序跟\(\lambda\)演算等价起来。下面是这个程序的Lexer和Parser的定义:

:text
%token          LOOP    "loop"
%token          SO      ":="

.................

program: block !{ result = $1.n; !}.

block: equation !{ $$.n = new order; $$.n.add($1.n); !}
    | block equation !{ $$.n = new order; $$.n.add($1.n); $$.n.add($2.n); !}
    .

prblock: LPR block RPR !{ $$.n = $2.n; !}
    .


lo: LOOP expr "(" block ")" !{ $$.n = new loop; $$.n.add($2.n); $$.n.add($4.n); !}
    | LOOP expr TERM "(" block ")" !{ $$.n = new loop; $$.n.add($2.n); $$.n.add($5.n); !}
    .

equation:TERM !{ $$.n = new nul; !}
    | expr TERM !{ $$.n = $1.n; !}
    | equation TERM !{ $$.n = $1.n;  !}
    .

expr: lo !{ $$.n = $1.n; !}
    | ID SO prblock !{ $$.n = new eqf; auto n = new var; n.id = $1.ident; $$.n.add(n); $$.n.add($3.n); !}
    | ID SO expr !{ $$.n = new eqf; auto n = new var; n.id = $1.ident; $$.n.add(n); $$.n.add($3.n); !}
    | ID !{  $$.n = new var; $$.n.id = $1.ident; !}
    | ID "=" expr !{ $$.n = new eq; auto n = new var; n.id = $1.ident; $$.n.add(n); $$.n.add($3.n); !}
    | ID "=" prblock !{ $$.n = new eq; auto n = new var; n.id = $1.ident; $$.n.add(n); $$.n.add($3.n); !}
    | expr "+" expr !{ $$.n = new plus; $$.n.add($1.n); $$.n.add($3.n); !}
    | expr "-" expr !{$$.n = new min; $$.n.add($1.n); $$.n.add($3.n); !}
    | expr "*" expr !{$$.n = new time; $$.n.add($1.n); $$.n.add($3.n); !}
    | expr "/" expr !{$$.n = new div; $$.n.add($1.n); $$.n.add($3.n); !}
    | "(" expr ")" !{$$.n = $2.n;!}
    | "-" expr %prec UMINUS !{$$.n = new um; $$.n.add($2.n); !}
    | "+" expr %prec UPLUS !{$$.n = $2.n; !}
    | NUMBER !{$$.n = new num; $$.n.value = $1.value; !}
    | PR expr !{ $$.n = new pr; $$.n.add($2.n); !}
    .

一切看起来都很简单,我们所做的就似乎把之前的硬编码换成树操作,剩下最大的挑战就是添加循环之后避免Shift/Reduce Conflict而已。在整个定义没有歧义之后,这个“语言”就算完成了。需要注意的是这里我们返回的是ASTNode型的树根,而不再是之前的float型的执行结果了。这样在Evaluator里,我们可以执行parse(text).evaluate来获得结果。

import std.stdio, std.file, std.string;
import parser2, ast;

int main(string[] args)
{
    if(args.length == 2){
        writefln("Program Exited: %f", evaluate(readText(args[1])).evaluate);
        return 0; 
    }
    return 1;
}

试着执行之前我们想象的那个程序,可以得到:

INSERT$ ./evaluator2 fact
12413915592536068246584490201464214099653701243174007003414528.00000000000000000000
258623241511168266876471800775489592695198290419683860414464.00000000000000000000
5502622159812089153567237889924947737578015493424280502272.00000000000000000000
119622220865480210353064206097531035159161141491744636928.00000000000000000000
2658271574788449549981313790911632279366972557834059776.00000000000000000000
60415263063373844708264795564905929160694072661245952.00000000000000000000
1405006117752880121086634743819753058130737680613376.00000000000000000000
33452526613163797571690755229534229392170908909568.00000000000000000000
815915283247898008314102179727920573516005507072.00000000000000000000
20397882081197446658430873854155690147131162624.00000000000000000000
523022617466601037913697377988137380787257344.00000000000000000000
13763753091226345578872114833606270345281536.00000000000000000000
371993326789901332234925207831002568720384.00000000000000000000
10333147966386144222209170348167175077888.00000000000000000000
295232799039604081776217808048838672384.00000000000000000000
8683317618811889480490536047552233472.00000000000000000000
263130836933693554659840465146216448.00000000000000000000
8222838654177923583120014535819264.00000000000000000000
265252859812191104246398737973248.00000000000000000000
8841761993739700772720181510144.00000000000000000000
304888344611713801550158626816.00000000000000000000
10888869450418351940239884288.00000000000000000000
403291461126605719042260992.00000000000000000000
15511210043330983907819520.00000000000000000000
620448401733239409999872.00000000000000000000
25852016738884978212864.00000000000000000000
1124000727777607680000.00000000000000000000
51090942171709440000.00000000000000000000
2432902008176640000.00000000000000000000
121645100408832000.00000000000000000000
6402373705728000.00000000000000000000
355687428096000.00000000000000000000
20922789888000.00000000000000000000
1307674368000.00000000000000000000
87178291200.00000000000000000000
6227020800.00000000000000000000
479001600.00000000000000000000
39916800.00000000000000000000
3628800.00000000000000000000
362880.00000000000000000000
40320.00000000000000000000
5040.00000000000000000000
720.00000000000000000000
120.00000000000000000000
24.00000000000000000000
6.00000000000000000000
2.00000000000000000000
1.00000000000000000000
1.00000000000000000000
Program Exited: 1.000000

可以看到这个程序已经可以正确执行了。虽然这个程序的功能依然很弱,对于简单的运算来说已经足够了,比如计算\(\pi\):

len = 20000000
pi = 1
a = 1
c = 1
s = -1
loop len-(a=a+2) (
    pi = pi + s*1/a 
    s = -1 * s
)
print pi*4

执行之后可以获得如下结果:

INSERT$ ./evaluator2 pi                            
3.14159255358979150330
Program Exited: 3.141593

好了,到此为止,最初开始是作为练习提出来的问题终于大部分得到了解决,但并不完美,实际执行之后发现,完全实时的evaluate非常慢,上面计算\(\pi\)的例子就足足花了15秒。 因此在下一章,我们会先把进一步扩充语言放到一边,转而引入LLVM(Low Level Virtual Machine),让目前的计算器获得巨大的性能提升。