过度设计的计算器：Zig + QBE

# 过度设计的计算器：Zig + QBE 来源：https://tomekw.com/overengineered-calculator-zig-qbe/ 2026\-07\-29\| 返回首页 (https://tomekw.com/) 对于许多想了解编译器工作原理的人来说，Robert Nystrom 的《Crafting Interpreters》(https://craftinginterpreters.com/) 和 Thorsten Ball 的《Writing An Interpreter In Go》(https://interpreterbook.com/)（以及《Writing A Compiler In Go》(https://compilerbook.com/)）是必读资源。我通读了这两本书，学到了词法分析的工作原理、语言文法以及 EBNF (https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form) 记法是什么。我构建了自己的第一个递归下降解析器 (https://en.wikipedia.org/wiki/Recursive_descent_parser)，然后通过直接解释执行（慢）和实现字节码编译器与虚拟机（快）让代码活了起来。 这两本书没教我的，是如何将源代码翻译成本地机器码。这时，QBE (https://c9x.me/compile/) 登场了。 > QBE 是一个编译器后端，旨在用 10% 的代码实现工业级优化编译器 70% 的性能。QBE 通过提供一个紧凑、易用且高性能的后端来促进语言创新。代码规模限制迫使 QBE 只关注核心功能，避免陷入收益递减的永无止境之路。 我想出了一个小项目，展示如何完成从源代码到本地可执行文件的全部必要步骤。再发明一种编程语言会适得其反，我会把时间花在纠结设计决策上，而不是专注于我关心的重点：代码生成。 算术表达式是一个明显且简单的问题。但如何让 `2 + 2 * 2` 得到 `6` 而不是 `8`？我从定义文法开始。文法告诉我应该期望哪些标记，以及如何处理优先级规则。例如：乘法和除法应在加法和减法之前执行。 最终得到这样的文法： ``` Expression = Sum; Sum = Product , { ( "+" | "-" ) , Product }; Product = Unary , { ( "*" | "/" ) , Unary }; Unary = ( ( "-" | "+" ) , Unary ) | Primary; Primary = Number | "(" , Expression , ")"; ``` 这意味着什么？ - 标记包括：数字、运算符（`+`、`-`、`*`、`/`）以及用于分组的括号。 - 优先级规则源自从上到下依次遵循文法规则，从最宽松到最严格： - `Expression` 是一个 `Sum`（加法和减法） - `Sum` 是一系列 `Product`（乘法和除法） - `Product` 是一系列 `Unary`（取负） - `Unary` 要么是 `Primary`，要么在有运算符时是另一个 `Unary` - `Unary` 操作可以堆叠：`----1` = `1` - `Primary` 要么是一个 `Number`，要么是一个分组的 `Expression` ## 词法分析器 基于文法，我使用 Zig (https://ziglang.org/) 实现了一个词法分析器。我参考了真正的 Zig 词法分析器 (https://codeberg.org/ziglang/zig/src/branch/master/lib/std/zig/tokenizer.zig)。 标记标签列表如下： ```zig pub const Tag = enum { invalid, eof, left_paren, right_paren, plus, minus, star, slash, number, }; ``` 注意：`invalid` 和 `eof` 是元标签，用于知道何时停止——遇到无效标记或输入结束。 词法分析器变成了一个简单的状态机： ```zig const TokenizerState = enum { start, number, }; pub fn nextToken(self: *Tokenizer) Token { var result: Token = .{ .tag = .eof, .start = self.current_position, .end = undefined }; state: switch (TokenizerState.start) { .start => switch (self.input[self.current_position]) { 0 => {}, ' ', '\t', '\n', '\r' => { self.current_position += 1; result.start = self.current_position; continue :state .start; }, '0'...'9' => { result.tag = .number; self.current_position += 1; continue :state .number; }, '+' => { result.tag = .plus; self.current_position += 1; }, '-' => { result.tag = .minus; self.current_position += 1; }, '*' => { result.tag = .star; self.current_position += 1; }, '/' => { result.tag = .slash; self.current_position += 1; }, '(' => { result.tag = .left_paren; self.current_position += 1; }, ')' => { result.tag = .right_paren; self.current_position += 1; }, else => { result.tag = .invalid; self.current_position += 1; }, }, .number => switch (self.input[self.current_position]) { '0'...'9' => { self.current_position += 1; continue :state .number; }, else => {}, }, } result.end = self.current_position; return result; } ``` （查看：完整源代码 (https://github.com/tomekw/oc/blob/main/src/tokenizer.zig)） ## 解析器 接着，我创建了一个解析器，从标记列表构建抽象语法树。文中的 `Sum`、`Product` 和 `Unary` 变成了 `binary` 和 `unary` 操作： ```zig const BinaryOp = enum { add, sub, mul, div, }; const UnaryOp = enum { neg, }; pub const AstNode = union(enum) { binary: struct { lhs: *AstNode, op: BinaryOp, rhs: *AstNode, }, unary: struct { op: UnaryOp, rhs: *AstNode, }, number: i64, }; ``` （查看：完整源代码 (https://github.com/tomekw/oc/blob/main/src/parser.zig)） ## 解释器 读完那两本书后，直接解释 AST 很简单： ```zig pub const Interpreter = struct { pub fn interpret(ast: Ast) !i64 { return eval(ast.root); } fn eval(node: *const AstNode) !i64 { return switch (node.*) { .binary => |b| switch (b.op) { .add => try eval(b.lhs) + try eval(b.rhs), .sub => try eval(b.lhs) - try eval(b.rhs), .mul => try eval(b.lhs) * try eval(b.rhs), .div => try std.math.divTrunc(i64, try eval(b.lhs), try eval(b.rhs)), }, .unary => |b| switch (b.op) { .neg => -try eval(b.rhs), }, .number => |value| value, }; } }; ``` （查看：完整源代码 (https://github.com/tomekw/oc/blob/main/src/interpreter.zig)） ## 发射器 接下来是好玩的部分。首先，我构建了一个 QBE 中间语言代码发射器。官方文档 (https://c9x.me/compile/doc/il.html) 是无价之宝。我的 `add`、`sub`、`mul`、`div` 和 `neg` 操作直接映射到 QBE 指令： ```qbe # add 64-bit 2 to 2 and store the result in a temporary %result %result =l add 2, 2 ``` 其他所有指令也一样。 在 QBE 中，中间语言采用静态单赋值形式 (https://en.wikipedia.org/wiki/Static_single-assignment_form)。这意味着我需要为我所有的 `binary` 和 `unary` 操作各发射一条 QBE 指令，然后将它们堆叠起来。对于像 `+4` 这样的表达式，发射指令是没有意义的，因为它和 `4` 是一样的。 对于 `2 + 2 * 2` 表达式： ```qbe # ld means: as long integer data $fmt = { b "%ld\n", b 0 } export function w $main() { @start %.0 =l mul 2, 2 %.1 =l add 2, %.0 # call C printf function, needs linking with libc, to print the result call $printf(l $fmt, ..., l %.1) ret 0 } ``` 对于 `-2 + 2 * (4 / 2)`： ```qbe data $fmt = { b "%ld\n", b 0 } export function w $main() { @start %.0 =l neg 2 %.1 =l div 4, 2 %.2 =l mul 2, %.1 %.3 =l add %.0, %.2 call $printf(l $fmt, ..., l %.3) ret 0 } ``` （查看：完整源代码 (https://github.com/tomekw/oc/blob/main/src/emitter.zig)） ## 编译器 最后需要的是将所有部分整合起来，生成一个本地可执行文件。我决定将编译器分为三个阶段： - `Qbe`： - 词法分析 - 语法分析 - 发射 QBE SSA - 使用 `qbe` 可执行文件生成原始汇编文件 - `Cc`：将汇编编译成可执行文件。由于我是用 Zig 实现的，直接调用 `zig cc` 很自然。 - `Run`：运行可执行文件并输出结果。 从头到尾就是这样： ```sh $ oc "2 + 2 * 2" 6 ``` 我决定保留所有构建产物，方便手动检查。 `target/result.ssa` 包含 QBE IL： ```qbe data $fmt = { b "%ld\n", b 0 } export function w $main() { @start %.0 =l mul 2, 2 %.1 =l add 2, %.0 call $printf(l $fmt, ..., l %.1) ret 0 } ``` `target/result.s` 包含由 `qbe -o result.s result.ssa` 生成的汇编： ```asm .data .balign 8 fmt: .ascii "%ld\n" .byte 0 /* end data */ .text .balign 16 .globl main main: endbr64 pushq %rbp movq %rsp, %rbp movl $6, %esi leaq fmt(%rip), %rdi movl $0, %eax callq printf movl $0, %eax leave ret .type main, @function .size main, .-main /* end function main */ .section .note.GNU-stack,"",@progbits ``` 我观察到一个有趣的现象。由于 QBE 是一个优化编译器后端，它把所有常量折叠了，直接返回结果：`movl $6, %esi`。 但在有除法的情况下（`-2 + 2 * (4 / 2)`），却没有发生这样的优化： ```asm .data .balign 8 fmt: .ascii "%ld\n" .byte 0 /* end data */ .text .balign 16 .globl main main: endbr64 pushq %rbp movq %rsp, %rbp movl $2, %ecx movl $4, %eax cqto idivq %rcx imulq $2, %rax, %rax movq %rax, %rsi addq $-2, %rsi leaq fmt(%rip), %rdi movl $0, %eax callq printf movl $0, %eax leave ret .type main, @function .size main, .-main /* end function main */ .section .note.GNU-stack,"",@progbits ``` ## 总结 完整源代码可在 此处 (https://github.com/tomekw/oc) 获取。需要安装 `qbe` 和 `zig` 包才能构建和运行。在 Alpine Linux 上非常简单： ```sh $ apk add qbe zig ``` 项目目前处于相当完整的状态。可能还有些粗糙：需要更多测试，错误处理也有改进空间，特别是针对溢出和除以零的情况。 我用手写文字和代码。