摘要：本文介绍 Mugo——一个面向 Go 编程语言极小子集的单遍编译器。它输出（非常朴素的）x86-64 汇编，仅支持刚好够实现一个 Mugo 编译器所需的语言特性：int 和 string 类型、切片、函数、局部变量、全局变量以及基本的表达式和语句。

自从开始写代码起，我就对编译器着迷。我的早期编程项目之一是“Third”，一个运行于 8086 DOS 上的自举 Forth 编译器。Forth 非常容易编译：它没有表达式和语句的概念，每个以空格分隔的词都会被直接编译成一条调用指令——通常会用到直接线程化等技术。

像 C 和 Go 这样的典型语言拥有更复杂的语法，包含表达式和语句，因此需要真正的解析器和代码生成器。这些语言的编译器通常复杂而强大，但正如我们将看到的，如果只坚持使用基本类型并且不做优化输出，仍然可以写出一个简单的编译器。

Mugo 在某种程度上延续了 Fabrice Bellard 的 Obfuscated Tiny C Compiler 的精神，不过我的这个当然要平庸得多，短期内也不可能赢得 IOCCC。Bellard 的编译器只实现了刚好够将自身编译为原生 i386 Linux 可执行文件的 C 语言子集。

我想用 Go 做一个类似的东西，只是去掉混淆。这个想法最初只是洗澡时的突发奇想：“Go 要精简到怎样的子集才能编译自身呢？”Fabrice 的 C 编译器是用 2048 字节的混淆 C 代码实现的，而我的则是由 1600 行格式整洁的 Go 代码构成。

虽然这是在一个长周末里完成的有趣练习，但它在很大程度上只是一个玩具——它舍弃了 Go 的所有优秀特性：自定义类型、接口、goroutine、channel、map、垃圾回收，甚至连边界检查都没有！我做 Mugo 的目的是为了学习：对我自己，也希望对你有所启发。做这类练习有助于揭开我们所用工具的神秘面纱。

支持 Go 的哪一部分？

Mugo 是 Go 的一个子集，因此它的源代码既可以用 Go 编译，也可以用 Mugo 自身编译。在我看来，这让它有趣得多。这也让测试变得更容易：当 Go 编译版本生成的汇编输出与 Mugo 编译版本完全一致时，我就知道它工作正常了——当 diff mugo2.asm mugo3.asm 没有任何输出时，那种感觉真是美妙！

在动手之前，我反复斟酌应该包含哪些特性。我知道需要某种容器类型来保存编译器状态：例如变量的名称和类型、函数签名和返回类型。但该用哪种容器呢？

Go 有指针，但比 C 的指针安全得多，却也远没有那么强大，因为不能进行指针算术。Bellard 的编译器大量使用了 C 指针，但在 Go 里这条路走不通。

那结构体或 map 呢？实现它们会更复杂，而且并不能很好地解决最常见的“存一列东西”的问题。所以我决定这些都可以不要，只需要切片就够了。

以下是 Mugo 支持的特性：

• int 类型、十进制整数字面量、字符常量，以及大多数作用于 int 的表达式：+、-、*、/、%、==、!=、<、<=、> 和 >=，运算符优先级按 Go 的规则处理。编译器能识别类型名 bool，但将其与 int 同等对待（&&、|| 和 ! 操作于这些伪布尔值上）。
• string 类型，包括带 \ 转义的字符串常量、使用 == 或 != 的字符串相等性判断、使用 + 的字符串拼接，以及 len()。
• 切片，但仅支持 []int 和 []string。不支持切片字面量和 make()，因此要构建切片必须先创建一个空切片再通过 append 添加元素。支持获取和赋值切片元素，也支持 slice[:n] 表达式和 len()。
• 存在类型检查，但并不完整。我只在有意义或有助于调试的地方做了检查，远非完备。
• 语句：if 和 else、for condition { ... }、return，以及 Go 的 := 短变量声明。
• 变量和常量。但 var 和 const 仅在顶层支持；局部变量必须使用 :=（这在 Go 中本来也更常见）。仅支持带类型的整型常量。
• 顶层函数，包括递归。但不支持函数值和匿名函数。函数只能有一个返回值，也不支持可变参数函数。
• I/O，使用三个预定义函数：getc 从标准输入读取单个字符，print 和 log 分别向标准输出和标准错误输出字符串。
• Go 语法，但精简到仅保留所需部分。大量结构都不支持，例如 ++ 和 --、for range 循环等等。支持以 // 开头的单行注释。

大致就是这些！如果上面列表里没有提到，那大概就是不支持的。正如我所说，是一个很小的子集。

在构建过程中，我多次查阅了简洁明了的 Go 语言规范，尽管几乎可以肯定有些地方还是弄错了。不过，已实现的部分表现得确实和 Go 一致，正如我的“diff 测试”所证明的那样。

代码生成

Mugo 是一个单遍编译器，在解析的同时直接输出 x86-64 汇编。（它是为 Linux 编写的，但在 macOS 或 Windows 上运行也不难。）它没有在内存中构建抽象语法树——反正只靠切片也很难构建。

它也非常朴素。没有任何优化——我基本上把强大的基于寄存器的 CPU 当成了笨拙的栈式机器，把中间值在栈上推入和弹出。真正的编译器大约一半的复杂度在代码生成，另一半在类型检查——而这两者在 Mugo 中都被极大地简化了。

我不得不耍的一个小技巧是处理局部变量声明（Go 的 := 语法）。由于只有一遍扫描，直到解析完整个函数才知道会有多少局部变量以及它们的类型。因此，除了常规的 rbp 帧指针操作外，我的函数序言会从栈指针中减去 64 字节，为最多 8 个单元的局部变量预留空间（Mugo 中用得最多的函数使用了 7 个单元）。

更新：Hacker News 上的 “a1369209993” 指出，我本可以在函数末尾定义一个汇编常量，待确定大小后再引用。我已经在处理 if 和 else 的前向跳转时让汇编器做了类似的事。感谢指正！

下面是一个整型 add 函数的完整输出：

; func add(x int, y int) int {
;     return x + y
; }

; function prologue
add:
push rbp             ; rbp is the frame pointer
mov rbp, rsp
sub rsp, 64          ; make space for any more locals
                     ; (not used by this function)

; fetch and push local variable x, then y
push qword [rbp+24]
push qword [rbp+16]

; the + operation
pop rbx
pop rax
add rax, rbx
push rax

; pop result back into rax for "return"
pop rax

; function epilogue (restore stack and frame pointer)
mov rsp, rbp
pop rbp
ret 16              ; return, and free space due to
                    ; caller pushing x and y

与 gcc 未优化的输出相比，我们的表现还不算太差：

push    rbp
mov     rbp, rsp
mov     qword [rbp-8], rdi
mov     qword [rbp-16], rsi
mov     rdx, qword [rbp-8]
mov     rax, qword [rbp-16]
add     rax, rdx
pop     rbp
ret

不过，gcc 优化后的输出只产生了一条基于寄存器的指令：

lea     rax, [rdi+rsi]
ret

在调用方，为了生成对 add 的调用，Mugo 会产生如下代码：

; add(1, 2)

push qword 1  ; push first arg
push qword 2  ; push second arg
call add      ; call the function
push rax      ; push return value back to stack

如你所见，Mugo 使用了自己的一套非常低效的 ABI，与 x86-64 ABI 完全不同——标准 ABI 会把前六个“单元”（64 位值）放在寄存器中。

为了简单起见，Mugo 的 ABI 将参数压入栈中。参数按顺序压栈，因此在内存中它们在栈上呈逆序排列。不过，Mugo 确实会使用寄存器来返回结果：rax，如果有更多单元则依次使用 rbx 和 rcx。和 Go 一样，int 占一个单元，string 占两个单元（地址和长度），切片占三个单元（地址、长度和容量）。

对于字符串拼接和切片追加的内存分配，Mugo 使用了一个极其简单的“bump 分配器”。换句话说，它在一块固定的 1MB 内存中不断向前移动指针，如果用完就以内存不足的信息退出。它从不释放内存，也没有垃圾回收器。非常适合短期运行的程序！

为了生成汇编，Mugo 只是简单地调用 print 向标准输出写入：

func genFuncStart(name string) {
    print("\n")
    print(name + ":\n")
    print("push rbp\n")
    print("mov rbp, rsp\n")
    print("sub rsp, " + itoa(localSpace) + "\n") // space for locals
}

Mugo 运行结束后，我使用 NASM 汇编其输出，并用 ld 链接器构建可执行文件。下面是来自 Makefile 的示例，展示了我如何构建三个版本的编译器：

# Build the compiler with Go
mugo:
    go build -o build/mugo

# Build the compiler with the Go-built Mugo
mugo2:
    build/mugo <mugo.go >build/mugo2.asm
    nasm -felf64 -o build/mugo2.o build/mugo2.asm
    ld -o build/mugo2 build/mugo2.o

# Build the compiler with the Mugo-built Mugo
mugo3:
    build/mugo2 <mugo.go >build/mugo3.asm
    nasm -felf64 -o build/mugo3.o build/mugo3.asm
    ld -o build/mugo3 build/mugo3.o
    diff build/mugo2.asm build/mugo3.asm  # ensure output matches!

还有一个 make 目标用于通过一个让编译器编译自身的简单测试来生成覆盖率报告。该测试只是调用 Mugo 的 main()，因此我们会在启用覆盖率分析的情况下运行测试二进制文件，并将 mugo.go 通过标准输入传给它。这个“测试”就是编译编译器本身的完整源代码，并记录得到的覆盖率：

coverage:
    go test -c -o build/mugo_test -cover
    build/mugo_test -test.coverprofile build/coverage.out \
        <mugo.go >/dev/null
    go tool cover -html build/coverage.out -o build/coverage.html

起初我加入了几个编译器本身并未使用的特性，因此它们没有被测试到，在覆盖率报告中显示为红色。除了像少数几处出于一致性考虑而保留的特性外，比如 ! 非运算符和字符串切片赋值，我移除了未使用的特性。现在除了错误处理之外，所有特性都达到了完全覆盖。

我有一两次不得不祭出 gdb 来调试。我的 x86 汇编技能确实已经生疏，而且从未写过正经的 64 位汇编。我确信即便在单遍扫描的限制下，也有许多改进输出的方法——但这些改进就留给读者作为练习吧。:-)

词法分析与语法分析

Go 的语法简洁优美，易于分词和解析。Mugo 的词法分析器只使用单字符前瞻，并采用典型的递归下降解析器。

词法分析器本质上就是对下一个字符的一大堆 if 判断，该字符存储在全局整型变量 c 中。下面是它的一段代码片段：

func next() {
    // Skip whitespace and comments, and look for / operator
    for c == '/' || c == ' ' || c == '\t' || c == '\r' || c == '\n' {
        if c == '/' {
            nextChar()
            if c != '/' {
                token = tDivide
                return
            }
            nextChar()
            // Comment, skip till end of line
            for c >= 0 && c != '\n' {
                nextChar()
            }
        } else if c == '\n' {
            nextChar()
            // Semicolon insertion: golang.org/ref/spec#Semicolons
            if token == tIdent || token == tIntLit || token == tStrLit ||
                token == tReturn || token == tRParen ||
                token == tRBracket || token == tRBrace {
                token = tSemicolon
                return
            }
        } else {
            nextChar()
        }
    }
    if c < 0 {
        // End of file
        token = tEOF
        return
    }

    // Integer literal
    if isDigit(c) {
        tokenInt = c - '0'
        nextChar()
        for isDigit(c) {
            tokenInt = tokenInt*10 + c - '0'
            nextChar()
        }
        token = tIntLit
        return
    }

    // ... handle other tokens (snipped) ...
}

在解析器中，我尽量使用了 Go 规范文法中的产生式名称，例如 Expression、VarSpec 和 Operand。当然，由于我们处理的只是语言的一个子集，其中许多产生式都经过了精简。下面是几个解析函数的示例——请注意代码生成函数的调用是如何穿插其中的：

func Literal() int {
    if token == tIntLit {
        genIntLit(tokenInt)
        next()
        return typeInt
    } else if token == tStrLit {
        genStrLit(tokenStr)
        next()
        return typeString
    } else {
        error("expected integer or string literal")
        return 0
    }
}

func SimpleStmt() {
    // Funky parsing here to handle assignments
    identName := tokenStr
    expect(tIdent, "assignment or call statement")
    if token == tAssign {
        next()
        lhsType := varType(identName)
        rhsType := Expression()
        if lhsType != rhsType {
            error("can't assign " + typeName(rhsType) + " to " +
                typeName(lhsType))
        }
        genAssign(identName)
    } else if token == tDeclAssign {
        next()
        typ := Expression()
        defineLocal(typ, identName)
        genAssign(identName)
    } else if token == tLParen {
        genIdentifier(identName)
        typ := Arguments()
        genDiscard(typ) // discard return value
    } else if token == tLBracket {
        next()
        indexExpr()
        expect(tRBracket, "]")
        expect(tAssign, "=")
        Expression()
        genSliceAssign(identName)
    } else {
        error("expected assignment or call not " + tokenName(token))
    }
}

func Statement() {
    if token == tIf {
        IfStmt()
    } else if token == tFor {
        ForStmt()
    } else if token == tReturn {
        ReturnStmt()
    } else {
        SimpleStmt()
    }
}

上面“简单语句”有一点混乱——如果解析器会生成语法树，你可能会先调用 Expression 来解析左侧，然后查看是否有 = 或 := 来判断赋值，再解析右侧。但我们不能调用 Expression，否则它会生成获取该表达式值的代码，而不是赋值代码。因此我们必须先解析一个标识符，再判断接下来是赋值、函数调用还是切片表达式。我确信上面的代码并未正确处理所有边界情况，但已经足够好了。

运算符优先级通过递归下降来处理，例如下面对 && 和 || 运算符的处理（orExpr 和 andExpr 这些名称并未出现在 Go 规范中）：

func andExpr() int {
    typ := comparisonExpr()
    for token == tAnd {
        op := token
        next()
        typRight := comparisonExpr()
        typ = genBinary(op, typ, typRight)
    }
    return typ
}

func orExpr() int {
    typ := andExpr()
    for token == tOr {
        op := token
        next()
        typRight := andExpr()
        typ = genBinary(op, typ, typRight)
    }
    return typ
}

func Expression() int {
    return orExpr()
}

在递归下降解析器中有两个递归前向引用：Expression（解析表达式的各个函数内部需要调用 Expression）和 Block（块元素最终会嵌套到 Block 中）。Go 不需要也不允许前向引用，因此 Mugo 在启动时会以正确的签名预先定义这两个函数。

编译器通过一组全局切片来跟踪变量名和类型信息：

var (
    globals        []string // global names and types
    globalTypes    []int
    locals         []string // local names and types
    localTypes     []int
    funcs          []string // function names
    funcSigIndexes []int    // indexes into funcSigs
    funcSigs       []int    // each func: retType N arg1Type ... argNType
)

前四个很好理解，但 funcSigs 切片有点……古怪。它实际上是一个结构体切片。在真正的 Go 代码中，你可能会定义一个 funcSig 结构体，并将这三个“func”相关的切片合并为一个从函数名到结构体的 map：

var funcSigs map[string]funcSig

type funcSig struct {
    retType  int
    argTypes []int
}

但 Mugo 不支持结构体和 map，所以我不得不把这些字段塞进一个扁平的 int 切片中，用 funcSigIndexes[i] 指向 funcSigs 切片中对应伪结构体（索引为 i 的函数）的起始位置。

性能

由于完全没有优化，Mugo 显然会比 Go 慢得多，所以我不打算做全面的性能测试。但出于好玩，我写了一个小程序来测试包含一些整数运算的基本循环性能——它将 1 到 10 亿的数累加起来：

var (
    result int
)

func main() {
    sum := 0
    i := 1
    for i <= 1000000000 {
        sum = sum + i
        i = i + 1
    }
    result = sum // so Go doesn't optimize it out
}

在我的机器上，Go 版本运行时间为 0.34 秒。Mugo 版本则需要 5.7 秒——大约是前者的 17 倍。对于有史以来最糟糕的汇编代码之一来说，这成绩还不算太差。作为对比，同样循环的 Python 版本需要 1 分 38 秒……动态类型的字节码解释器显然不适合大量整数运算。

有趣的是，如果我把 sum 本身改成全局变量而非局部变量，Mugo 版本的耗时不变，但 Go 版本却从 0.34 秒变成了 1.7 秒。我怀疑 Mugo 慢得多的一大原因是它所有操作都在栈上的内存中进行——即便栈位于 CPU 缓存中，寄存器也总是更快。

性能的另一个方面是代码体积：Mugo 构建的可执行文件比 Go 构建的小得多。用 Go 构建的 Mugo 二进制文件为 1.6MB，而用 Mugo 自身构建的 Mugo 只有 56KB——大约是前者的 1/29！这并不是一场公平的较量——Mugo 没有内置 goroutine 调度器、垃圾回收器或运行时类型信息（参见这个 Go FAQ 问题）。不过，这确实引发了一个有趣的问题：对于用 Go 编写的简单命令行工具，我们是否可以通过一个极简的调度器和垃圾回收器来减小二进制体积？

相关项目

如前所述，我对解释器和编译器感兴趣已久。如果你喜欢这篇文章，这里还有一些我的相关项目：

• Third：我多年前编写的面向 8086 DOS 的 Forth 编译器。另可参阅 Richard Jones 的 jonesforth.S，其中有关于如何构建 Forth 编译器的教程。
• pyast64：使用 ast 模块将 Python 语法转换为 x86-64 汇编。
• LoxLox：用 Lox 自身编写的 《Crafting Interpreters》 中 Lox 编程语言的解释器（是不是开始发现规律了？）。
• GoAWK：用 Go 编写的兼容 POSIX 的 AWK 解释器。
• ZZT in Go：介绍了我为将 Adrian Siekierka 的 Reconstruction of ZZT 移植到 Go 而编写的 Pascal 到 Go 转换器。

希望你喜欢这篇文章——我自己在创作 Mugo 的过程中确实乐在其中。欢迎随时给我反馈！你也可以阅读在 Hacker News 上的讨论。