做这个项目的时候我第一反应是前面六个项目都在跟导线、逻辑门、芯片图较劲突然拐到写软件跨度有点大。真正动手把第一条push constant 7翻译成汇编、再在 CPU 模拟器里看到栈指针从 256 变成 257 的那一刻才明白这一层的意义——它是整个体系里第一次让“软件”和“硬件”真正对上话的接口。Nand2Tetris 的 Project 07 干的活就是写一个 VM 翻译器把栈式虚拟机的命令翻译成 Hack 汇编让编译器的后半段有了落脚点。这篇东西适合谁如果你正在做这个项目、卡在 eq/gt/lt 的标签冲突或者 pop 顺序上那直接抄作业就行如果你只是听说过后端翻译这回事想看看一层中间表示到底怎么落到机器指令上那这里的拆解能帮你建立完整的直觉。我把踩过的坑、每个命令的汇编模板、以及那些文档里不会写的小技巧都摊开讲代码可以直接改成你自己的实现。1. 项目定位与整体设计思路1.1 为什么要在高层语言和机器码之间插一层栈机先说个大白话的类比。编译器前端把高级语言变成某种中间表示后端把中间表示变成机器码这两步之间如果没有一个稳定的约定那么每换一种源语言、每换一种目标硬件所有组合都得重写一遍。栈式虚拟机就是那个约定它规定了“表达式怎么算、变量怎么存、函数怎么调用”这三件事的抽象形式前端只管产出 VM 命令后端只管消费 VM 命令。这种设计在真实工程里非常常见它的好处是目标平台的数量和源语言的数量从相乘变成相加。你的源语言有 M 种目标平台有 N 种没有中间层要写 M×N 个编译器有了中间层只要写 M 个前端和 N 个后端。Project 07 只做后端的一半栈运算和内存访问Project 08 补上控制流和函数调用那时整个 VM 才算完整。从学习角度看这一层还藏着一个很重要的思维转变从“寄存器视角”切换到“栈视角”。Hack 只有 A、D 两个寄存器和一块 RAM写汇编的时候你满脑子想的是“这个值现在在哪个寄存器里”。而 VM 层面你不需要关心这些你只需要知道“栈顶是什么、下一个是什么”剩下的事翻译器替你扛。这个抽象给你带来的轻松恰恰是翻译器作者也就是你要付出的代价。1.2 栈机模型把表达式求值变成压栈弹栈栈机的核心只有两个动作压入push和弹出pop。任何表达式不管多复杂都能拆成一串 push 和 pop 的组合。比如(x y) * (z - 1)在栈机眼里就是push x、push y、add、push z、push 1、sub、mul。栈的结构天然对应括号的嵌套这也就是为什么很多编译器的中间表示选栈机而不是三地址码——它省掉了临时变量命名的麻烦。但栈机有个“反直觉”的地方二元运算的结果默认放在哪。在寄存器机器上你必须显式指定目标寄存器栈机则是约定俗成地“弹出两个操作数、把结果压回去”。这个约定一旦固定所有翻译模板都能统一成同一套骨架代码量能压得很小。我建议你在动手写代码之前先在纸上画一画1 2这个表达式执行完之后的栈状态push 1 之后 SP 指向下一个空位栈里只有一个元素push 2 之后 SP 再进一格add 执行时先让 SP 退一格、读走 2再让 SP 再退一格、用 1 和 2 相加、把结果写回去、SP 退回到只剩一个元素的位置。这个手推过程能帮你检查后面所有的模板对不对。1.3 翻译器的整体架构解析、分段、生成我自己的实现是三段式的几乎没变过读入与清洗逐行读取 .vm 文件去掉行尾注释和空行把多空格、Tab 混合的分隔符统一成空格得到干净的 token 列表。解析与分类判断这条命令是 9 个算术命令之一还是 push/pop 命令。如果是 push/pop再拆出段名和偏移量。代码生成按命令类型查表输出对应的汇编片段同时维护两种状态——比较命令的递增标签计数器以及当前文件名用于 static 段。这个结构最大的好处是加新命令几乎不用改主循环。Project 08 加入label、goto、if-goto、call、function、return的时候你只要在分类那一步多加几个分支生成逻辑各写各的互不干扰。我见过有人把整段逻辑塞进一个大 if-else 里硬写到 Project 08 基本推倒重来。提示分段维护计数器这件事别嫌麻烦。比较命令的标签一旦重复汇编器不会报错只会在运行时跳到错误的位置症状是“程序跑完了但结果不对”排查起来非常磨人。2. 吃透 Hack 平台的内存地图2.1 指针区与栈区那几个不能碰的地址在写任何翻译代码之前把 RAM 布局记牢这是整个项目的地基。Hack 的 RAM 是 16 位地址空间常用区域这么划分地址范围用途说明RAM[0]SP栈指针指向下一个空位RAM[1]LCLlocal 段基址RAM[2]ARGargument 段基址RAM[3]THISthis 段基址RAM[4]THATthat 段基址RAM[5]–RAM[12]temp 段对应 R5–R12共 8 个格子RAM[13]–RAM[15]通用临时变量我习惯拿 R13 存地址、R14 存值RAM[16]–RAM[255]static 段每个 VM 文件从 16 开始分配RAM[256]–RAM[2047]栈区从 256 开始向下增长实际是向上增长这里要注意一点栈区的起点是 256测试脚本通常会先把 SP 初始化成 256。你生成的代码不该假设 SP 初始值而应该每步都从 RAM[0] 读这样才经得起测试脚本的各种预置状态。我在第一版里图省事直接把 256 硬编码进去SimpleAdd 过了BasicTest 一上来就挂原因就是测试脚本在开始前把 SP 改成了别的值。2.2 八个内存段分别落在哪里VM 命令的 push/pop 支持八个段argument、local、this、that、constant、static、temp、pointer。它们并不是平等的分成三类处理方式完全不同直接寻址类temp、pointer、constant。地址可以直接算出来不需要查指针。间接寻址类local、argument、this、that。要先读出段基址再加上偏移量。文件相关类static。地址跟文件名绑定本质上是直接寻址但符号名里带文件名。这种分类不是随便定的它来自真实编译器的需求函数参数和局部变量要跟着函数调用走所以需要一块在栈上动态分配的段基址存在指针里而 static 变量是文件作用域的全局量地址在编译期就固定所以用固定的符号地址。2.3 栈指针 SP 的自增自减约定SP 的语义只有一句永远指向栈顶的下一个空位。这句约定后面所有的模板都是由它推出来的push 之后 SP 要加 1因为新元素占了一个格子。pop 的时候先要把 SP 减 1减完之后的 SP 才指向“即将被弹出”的那个格子。二元运算需要先退一格读第二个操作数再退一格读第一个算完之后把结果写在第一个操作数的位置SP 停在“结果的下一个空位”。有个细节很多人第一次会搞混add执行完之后 SP 应该比执行前少 1因为两个操作数变成了一个结果。如果你算出来的 SP 只少 0 或者少 2就是模板写错了。我在调试时就养成了一个习惯每写完一个模板先在纸上推一遍 SP 的初值和终值这个动作能挡掉八成的错误。另外补一句Hack 的 RAM 每个格子是 16 位所有值按补码解释。所以-1在内存里是 0xFFFFpush constant -1是合法的汇编里写1然后D-A也能得到。比较命令返回的“真”也因此是 -1 而不是 1这个约定在后面讲 eq 的时候会再强调一次。3. 栈算术命令的翻译真的只有加减乘除吗3.1 二元运算的统一模板九个算术命令里add、sub、and、or属于二元运算它们共享同一个五条指令的骨架SP AMM-1 DM AA-1 M运算逐行拆解一下。SP把 SP 的地址装进 AAMM-1同时做两件事把 SP 的值减 1 写回 RAM[0]并把减完的新值装进 A。此时 A 指向栈顶那个即将被弹出的元素DM把它读进 D。接着AA-1让 A 退到第二个操作数的位置最后M运算把结果写在这个位置。这里运算的四个取值分别是DM、M-D、DM、M|D。注意sub的顺序——此时 D 里装的是栈顶也就是被减数在第二位的那个减数M 里装的是次顶。VM 语义是“次顶减栈顶”所以要写M-D而不是D-M。这一个字符的顺序我在 StackTest 上卡了大概二十分钟因为sub的错误只在两个数不相等的时候才暴露出来。and和or是位运算顺序无所谓但也要注意 Hack 汇编里按位与是、按位或是|不是或||——后者在别的语言里是逻辑运算在这份汇编里根本不存在。3.2 一元运算与 neg/not 的区别neg和not都是一元运算模板更短SP AM-1 M-M这里AM-1直接把 A 指向栈顶元素注意不是AM因为 SP 的值不变我们只是访问栈顶不需要移动指针。然后M-M原地取反。neg是算术取负not是逐位取反这两个在补码世界里恰好满足-x !x 1所以一个数两种取反的结果是差 1 的。测试文件里经常把这两个放在一起对比如果结果总是差 1那就是你把其中一个写成了另一个。注意一元运算不改变 SP这点跟二元运算不同。如果你的neg模板里出现了AMM-1之类的写法栈就会一点点被啃掉程序跑飞。3.3 比较命令与唯一标签eq/gt/lt 的正确实现eq、gt、lt是这九个命令里唯一需要控制流的也是这个项目最容易翻车的地方。它们的语义是弹出两个数比较大小把 -1真或 0假压回栈。必须用跳转实现因为 Hack 没有“比较并置标志位”的指令。模板长这样以eq为例SP AMM-1 DM AA-1 DM-D EQ_TRUE0 D;JEQ SP AM-1 M0 EQ_END0 0;JMP (EQ_TRUE0) SP AM-1 M-1 (EQ_END0)推演一遍前四行把栈顶减到 SPD 装栈顶值A 退到次顶D 变成“次顶减栈顶”。如果相等D 为 0D;JEQ跳到真分支把 -1 写到次顶位置否则顺序执行把 0 写过去再跳到结束标签。两路都保证 SP 已经减过 1结果覆盖在次顶的位置上。三个命令的区别只在跳转条件eq用D;JEQgt用D;JGTlt用D;JLT。gt判断的是“次顶减栈顶大于 0”也就是次顶大于栈顶方向和直觉一致不用担心。真正的问题是标签不能重复。同一个 .asm 文件里如果你写了两次(EQ_TRUE)汇编器会报标签重复有些宽松的实现不报错直接让后面的覆盖前面的运行时跳到一个错误位置症状极其诡异。解决办法是给每个生成的标签加一个全局递增序号EQ_TRUE_0、EQ_TRUE_1、EQ_END_0……我在翻译器里用一个成员变量self.label_count每次生成比较代码前自增一次简单可靠。还有一个坑-1 不等于 1。判断“真”的返回值必须是 -1全 1不是 1。测试脚本读栈里的值跟 -1 比对你返回 1 就判定失败。这个约定在整门课里是一致的记住就行。4. 内存访问命令的翻译push/pop 的八种目标4.1 直接寻址段temp、pointer、constant这三个段的共同点是不需要读指针地址能直接算出来。constant只支持 push不支持 pop往常量里写东西没意义。模板是n DA SP AM MD SP MM1注意这里必须用DA装的是立即数 n 的值不是DM那是把 RAM[n] 的内容读出来。这个区别我在第一次写的时候搞反了push constant 7变成了把 RAM[7] 的值压栈结果 SimpleAdd 算出来一个莫名其妙的大数。temp段的偏移 0–7 对应 RAM[5]–RAM[12]所以地址是5 n。push 的时候5n DM SP AM MD SP MM1pointer段只有两个合法偏移0 对应 THISRAM[3]1 对应 THATRAM[4]。有人图省事直接写THIS和THAT符号这也是正确的Hack 汇编器认识这两个预定义符号。我倾向于写成3/4加上偏移计算这样两种分支可以合并成一行代码。pop到 temp 和 pointer 的模板比较特别因为它不涉及间接寻址SP AMM-1 DM 5n MD先退 SP、取值进 D、再写进目标地址干净利落。这里比较容易错的地方是先减 SP 再写目标顺序反了会把还没弹出的值覆盖掉。4.2 间接寻址段local/argument/this/that这四个段的偏移是动态的必须先从指针位置读出基址再加上偏移。push 的模板n DA LCL AMD DM SP AM MD SP MM1这里有个执行顺序的小陷阱AMD这一句会覆盖 A 寄存器而它依赖的 M 是 RAM[LCL] 的值。Hack 的 C 指令求值顺序是先算 comp 再写 dest所以这条指令是安全的A 会被更新成 LCL 段的第 n 个格子地址。但如果你写成LCL然后DMD那就错了因为 D 里还装着重 n。另一种等价写法是把地址先存进临时变量LCL DM n ADA DM这种写法多一条指令但读起来清楚我早期用它后来熟练了改用前一种。两种都对选自己不容易写错的。pop到这个段要注意一个非常经典的顺序问题你需要先算出目标地址、存到一个临时位置再弹栈取值因为弹栈会改变 A 和 D。标准做法是借用 R13LCL DM n DDA R13 MD SP AMM-1 DM R13 AM MD这段代码我建议直接背下来因为它对应的错误最隐蔽如果你先弹栈再算地址栈顶值就在 D 里被地址计算覆盖了如果你把地址算完不存临时变量弹栈之后 A 已经变了指针就丢了。我见过有人用 R14 存值、R13 存地址也是对的只是要保证这两个临时变量在单个命令内部不被复用冲突。4.3 static 段与文件名前缀static段的特殊之处在于它是文件作用域的Foo.vm里的static 3和Bar.vm里的static 3是两个不同的变量必须落在不同地址。标准做法是把符号名写成文件名.偏移例如Foo.3让汇编器自己去分配地址。Hack 汇编器处理这种带点的标签时会把它当成变量符号从 RAM[16] 开始往上分配。所以你的翻译器需要在启动时记录当前处理的文件名生成代码时用Foo.3这种形式。这里有个我踩过的坑文件名要取 basename去掉路径和扩展名。如果你直接把命令行传进来的路径拼进去生成的符号会变成./src/Foo.3或者C:\work\Foo.3汇编器要么报错要么解析出奇怪的结果。正确做法是按路径分隔符切一段再去掉.vm后缀。Windows 和 Unix 的分隔符不一样稳妥的写法是两种都处理一遍。提示同一个文件里Foo.2出现两次是正常的多次访问同一个变量但Foo.2出现在两个不同文件里就说明文件名没取对。测试 StaticTest 会专门验证这一点。4.4 pop 的执行顺序陷阱先算地址再减 SP上面提到过一次这里单独展开因为它是整个 Project 07 里最容易反复犯的错误。所有 pop 命令都可以总结成三步算目标地址读指针、加偏移把结果存到 R13。弹栈SP 减 1把栈顶值读进 D。写回从 R13 取出地址把 D 写进去。顺序一旦颠倒比如先弹栈再算地址或者算地址的过程中覆盖了 D结果就是“写到了正确的地址但值是错的”或者“值是对的但写错了地方”。这两种症状在 CPU 模拟器里看起来很像都是 RAM 某个格子数值不对但排查方向完全不同。我的建议是先把 R13 里存的东西打印出来验证模拟器可以单步看 RAM[13]确认地址算对了再查值的问题。另外pop constant是非法的翻译器遇到这种情况应该直接报错退出而不是默默生成一段垃圾代码。这一点在课程文档里有明确说明但很多人为了省事不写校验最后在别的测试文件上炸掉。5. 手写翻译器从 .vm 到 .asm 的完整实现5.1 解析器的状态机设计我的解析循环非常朴素但每条命令的处理都做了严格分类ARITH {add: add, sub: sub, neg: neg, eq: eq, gt: gt, lt: lt, and: and, or: or, not: not} for line in lines: line line.split(//)[0].strip() if not line: continue parts line.split() cmd parts[0] if cmd in ARITH: emit_arith(cmd) elif cmd in (push, pop): segment, index parts[1], int(parts[2]) emit_memory(cmd, segment, index) else: raise ValueError(funknown command: {cmd})这个循环干了三件事去注释、跳过空行、按首词分派。这里有个细节值得注意注释可能跟在命令后面也可能单独占一行也可能在//后面还有别的字符。先按//切再 strip 是最稳的写法比用正则匹配关键字可靠得多。还有一点是为了 Project 08 预留的把push和pop的段名和偏移拆成独立变量后面加label/goto这类单参数命令时直接照猫画虎加分支就行。5.2 核心生成代码与关键片段先看算术部分的生成函数我把它拆成一个模板字典BINARY { add: DM, sub: M-D, and: DM, or: D|M, } def emit_arith(cmd): if cmd in BINARY: out [SP, AMM-1, DM, AA-1, fM{BINARY[cmd]}] elif cmd neg: out [SP, AM-1, M-M] elif cmd not: out [SP, AM-1, M!M] else: emit_compare(cmd)比较命令单独拉一个函数因为要生成标签def emit_compare(cmd): n self.next_label() jump {eq: JEQ, gt: JGT, lt: JLT}[cmd] out [ SP, AMM-1, DM, AA-1, DM-D, fCMP_TRUE_{n}, fD;{jump}, SP, AM-1, M0, fCMP_END_{n}, 0;JMP, f(CMP_TRUE_{n}), SP, AM-1, M-1, f(CMP_END_{n}), ]然后是内存访问部分我用字典把“段名”映射到“地址计算方式”DIRECT {constant: None, temp: 5, pointer: 3} def base_symbol(segment): return {local: LCL, argument: ARG, this: THIS, that: THAT}[segment]push分三种情况走constant 用DA直接寻址段用basen然后DM间接寻址段走指针加偏移。pop只处理后两种constant 直接抛异常。最后别忘了在文件结尾加一个无限循环(END) END 0;JMP这是课程要求的收尾防止程序“跑穿”到后面的内存区域。虽然测试脚本通常会主动停下但缺了这个循环某些测试会在结束时异常我第一次跑 StackTest 就因为这个卡了一会儿。5.3 逐个命令的落地测试与预期结果写完之后别急着跑全部测试一个一个来。我的顺序和预期结果是这样的SimpleAdd压 7、压 8、相加。执行完 SP 应该等于 258RAM[256] 应该等于 15RAM[257] 还是 8加法没覆盖它因为结果写在 256。StackTest一大串算术命令。这个测试能暴露几乎所有的模板错误尤其是sub的方向、and/or的操作符。跑完之后对照脚本里写好的期望值逐个核对 RAM 里从 256 开始的内容。BasicTest涉及 local、argument、this、that 四个间接段。这个测试会在执行前把栈指针初始化到 256然后在一段代码里把某个地址设成 300 之类的值专门检验你的间接寻址是否正确。如果结果里出现了本该是局部变量的值变成 0多半是指针读错了段。PointerTest只测 pointer 段。它会把 THIS 和 THAT 改成某个值再读回来。如果你的THIS写成了3但语义理解错比如以为 pointer 0 对应 LCL这里立刻暴露。StaticTest测 static 段。它会验证Xxx.i这种符号是否能正确分配和读写。注意这个测试往往涉及两个文件也就是检验你的文件名前缀处理。在 CPU 模拟器里跑的时候我建议把RAM[0]SP加到观察窗口每步单步执行时盯着它。SP 的异常是最早能发现的信号如果一个 push 之后 SP 只涨了 0说明MM1被吞了如果一个二元运算之后 SP 没降说明AMM-1写错了。6. 实测踩坑记录与排查手册6.1 常见错误症状速查表下面这张表是我自己攒的几乎覆盖了我遇到过的所有问题症状可能原因排查动作汇编器报标签重复eq/gt/lt 的标签没有唯一化检查是否用了全局递增计数模拟器一启动就报错汇编文件末尾缺少无限循环补(END) END 0;JMP算术结果整体偏移SP 初始值假设错误检查是否硬编码了 256sub 结果符号相反模板写成D-M改成M-D比较结果总是 0真分支写成了 1 而不是 -1检查M-1pop 后某个变量变 0先弹栈后算地址D 被覆盖改成先算地址存 R13static 变量串味文件名带路径或扩展名取 basename 并去后缀temp 段写入影响了别的变量偏移算成了n而不是5n检查基址用这张表的时候有个技巧先看症状落在哪一类再看具体命令。比如“pop 后变量变 0”问题一定在 pop 的模板里跟算术命令无关不用去看别的地方。6.2 调试方法论盯住 SP 和栈顶调试这个项目最有效的手段不是读代码而是看内存。CPU 模拟器可以单步执行每一行汇编执行完都会更新 RAM 视图。我的固定套路是第一步把 RAM[0] 和 RAM[256] 到 RAM[260] 这几个格子加到观察列表这样一眼能看到栈指针和栈顶五个元素。第二步在 .vm 文件里手动插几条“探针”命令。比如怀疑某个 push 有问题就在它前后各插一条push constant 111和push constant 222跑完之后看栈里有没有这两个标记值。有标记就知道执行到了哪里没有就说明前面的代码跳飞了。第三步对比较命令单独建一个最小测试只写push constant 3、push constant 3、eq跑完看栈里是不是 -1、SP 是不是 257。这个最小用例能把标签问题、操作数顺序问题、真假值问题一次性隔离出来。这套方法之所以有效是因为它把“整段程序跑不对”拆成了“某一条命令执行后状态不对”问题的粒度一下子从几百行缩到五行。6.3 一些我用了很多年的小技巧技巧一先手写一段汇编再写生成器。在写代码之前挑五条最有代表性的命令push constant、push local、pop local、add、eq手动写出对应的汇编并在模拟器里验证通过。有了这五个“标准答案”生成器写出来后直接对比输出一眼就能看出哪里不一致。这比盲目调试快得多。技巧二把生成结果按命令加注释。每生成一条 VM 命令对应的汇编片段前面加一行// push local 3这样的注释。汇编器会忽略它但你在模拟器里单步的时候能立刻知道当前这段汇编对应的是哪条 VM 命令。这个习惯在 Project 08 调试函数调用时是救命的。技巧三给翻译器加上命令行参数校验。输入不是.vm文件就报错退出文件不存在也报错退出。听起来是废话但我在调试时曾经因为路径写错翻译器默默生成了一个空的 .asm然后我在模拟器里跑了一个空程序盯着屏幕找了半小时“为什么什么都没有”。技巧四把标签计数器做成可复位的。批量翻译多个文件的时候每个文件单独翻译计数器在文件开头复位这样生成的文件不会因为序号累积变得巨大也方便对比两次翻译的差异。技巧五别急着优化生成的代码。有些人生成完了会想“这段能不能少两条指令”然后改着改着就把栈搞乱了。这个项目的目标是把语义翻译对不是把指令压到最少。等全部测试过了想优化再说那时候你有回归测试兜底改坏了能立刻发现。6.4 翻译器之外的两点体会做到这一步你会发现这个项目真正难的不是某条命令的模板而是保持状态一致性。SP 是唯一的事实来源所有命令都必须围绕它自洽。一旦你在某个模板里“省了一步”比如忘了在 pop 里减 SP或者在一元运算里多加了一次自减整个程序就会在几十条命令之后莫名其妙地崩掉而且崩的地方往往离错误发生的地方很远。另一个体会是关于抽象层的价值。写完之后回头看VM 命令只有 17 条9 个算术 8 个段的 push/pop却足以表达任意复杂度的表达式求值。等到 Project 08 补上函数调用这个小小的指令集就能支撑起完整的程序。你在这一层花的每一分钟都会在后面调试高级语言程序的时候还回来——因为当程序出错时你能一眼看出是哪条 VM 命令生成的汇编有问题而不是对着一坨编译产物发呆。最后分享一个我至今保留的习惯每次跑完一个新测试文件我都会把 RAM[256] 往后十几个格子的值抄在纸上和测试脚本里的期望值逐条对一遍。看起来笨但这个过程能让我记住“栈机执行完之后到底长什么样”下次再看到异常的内存布局直觉就能告诉我问题出在 push 还是 pop 上。
