练习

本节阅读量:

这一页适合读完第一章后回头做，不必一次全部完成。练习 1～6 主要帮助你对照各阶段输出；练习 7～8 需要修改代码；练习 9～10 继续理解栈槽和退出码；练习 11 是一项汇编生成进阶练习；最后一题用来思考下一章的问题。

练习 1：手画 AST

画出下面程序的 AST：

1

(+ (+ 1 2) 3)

参考形状：

1
2
3


Add
  ...
  ...

练习 2：追踪 parser

不用写代码，只写出 parser 的动作顺序。

程序：

1

(+ -1 3)

参考形式：

1
2
3
4


advance() 拿到 ...
expect(...) 检查 ...
parse_expr() 读到 ...
最后得到 Add(...)

这个练习的目的不是背函数名，而是确认你知道：

1

parser 先认出加法，再读两个子表达式。

练习 3：手写 IR

给下面程序写出计算步骤：

1

(+ (+ 1 2) (+ 3 4))

参考形式：

1
2
3
4


t.0 = ...
t.1 = ...
t.2 = ...
return t.2

练习 4：观察真实输出

运行：

1
2
3
4


cd code/01_numbers
./mini ast examples/nested_add.lang
./mini ir examples/nested_add.lang
./mini compile examples/nested_add.lang -o out.s

对照三个输出：

1
2
3


AST 是树。
IR 是步骤。
汇编是贴近机器的指令文本。

练习 5：手写简单汇编

尝试给下面程序手写汇编：

1

(+ 10 32)

目标结果是 42。

在 Linux 或 WSL 上，可以从这个最小函数骨架开始填写中间三行：

1
2
3
4
5


.globl main
main:
    # 用 movq 把 10 放进 %rax
    # 用 addq 加上 32
    # 用 retq 返回

保存为 add.s 后，用 cc add.s -o add 构建，再运行 ./add 和 echo $? 检查结果。macOS 需要把入口标签改成 _main；Apple Silicon Mac 还需要按照第 0 章的说明指定 x86-64 架构。

练习 6：改一个示例

新建或修改一个示例文件，让它表示：

1

(+ (+ 10 20) 12)

然后依次运行：

1
2
3


./mini run <file>
./mini ir <file>
./mini compile <file> -o out.s

检查解释器结果、IR 和汇编是否能对应起来。

练习 7（综合）：自己实现减法

把第一章的语言扩展一点点，让它支持二元减法：

1

(- 10 3)

这个程序的结果应该是 7。

再试一个嵌套例子：

1

(- (+ 10 5) (- 4 1))

这个程序的结果应该是 12。

你可以按这条线索改：

1
2
3
4
5
6


AST：增加减法表达式 kind
parser：在 "(" 后允许操作符是 "-"
解释器：先求左右两边，再计算 lhs - rhs
IR：增加减法操作 kind
汇编：生成 subq 指令
示例：新增一个减法示例文件

注意，-1 仍然是一个整数；(- 10 1) 才是减法表达式。

改完后至少运行：

1
2
3
4
5
6
7


./mini run <file>
./mini ast <file>
./mini ir <file>
./mini compile <file> -o out.s
cc out.s -o out
./out
echo $?

检查解释器结果、IR 和汇编运行结果是不是一致。

练习 8：给坏程序写错误信息

这一题不要求加入新语法。目标是让错误更清楚。

试着运行或构造下面这些坏程序：

1
2
3
4


(+ 1)
(+ 1 2 3)
(+ 1 2
(1 2)

然后改 parser，让它们失败时尽量说清楚原因。

你可以先做到这种程度：

1
2
3
4


缺少右边表达式
加法后面有多余内容
缺少右括号
列表开头不是 +

这道题的重点不是写出很漂亮的错误系统，而是练习 parser 在哪里知道“现在不对了”。

练习 9：手算栈槽

不要先运行编译器。先手算下面程序可能需要哪些临时变量：

1

(+ (+ 1 2) (+ (+ 3 4) 5))

写出类似这样的表：

1
2
3
4
5
6
7
8
9


t.0 = ...
t.1 = ...
t.2 = ...
...

t.0 -> -8(%rbp)
t.1 -> -16(%rbp)
t.2 -> -24(%rbp)
...

然后运行：

1
2


./mini ir <file>
./mini compile <file> -o out.s

对照真实 IR 和汇编，看看你的临时变量顺序、栈槽位置和编译器是否一致。再回答三个问题：

1
2
3


这些临时变量一共需要多少字节？
向上对齐到 16 的倍数后，subq 应该分配多少字节？
执行 subq 后，%rsp 位于 %rbp 的哪个偏移位置？

最后尝试画出这次编译对应的栈帧，把 %rbp、%rsp 和每个临时变量标在图上。

其他编译器可以采用不同的临时变量安排；但这道练习的目标是读懂当前 lowerer 和汇编生成器。如果你的结果与实际输出不同，请沿着递归 lowering 的顺序找出从哪一步开始出现差异。

练习 10：观察退出码截断

第一章的汇编程序用返回值看结果。这个办法很方便，但它不是完整的数字输出。

试试这些程序：

1
2
3
4


42
300
(+ 200 100)
-1

每个程序都编译、链接、运行：

1
2
3
4


./mini compile <file> -o out.s
cc out.s -o out
./out
echo $?

记录你看到的结果。

想一想：

1
2
3


语言里的结果是多少？
echo $? 显示的是多少？
为什么它们不总是一样？

这道题是为了确认一件事：退出码只是操作系统保存的一小段结果，不等于语言以后真正的打印功能。

练习 11（进阶）：处理 `addq` 放不下的大整数

本章解释器用 long 保存整数。在常见的 64 位 Linux 和 macOS 环境中，long 可以保存 2147483648，所以先分别解释下面两个程序：

1

(+ 2147483648 1)

1

(+ 1 2147483648)

两次 mini run 都应该得到：

1

2147483649

再分别生成汇编并尝试链接：

1
2


./mini compile <file> -o out.s
cc out.s -o out

如果你在 Apple Silicon Mac 上，仍然要按照第 0 章的说明使用：

1

cc -arch x86_64 out.s -o out

观察生成的汇编，你可能会发现一个不对称现象：大整数在左边时通常可以先放进 %rax，大整数在右边时，当前生成器却会尝试生成：

1

addq $2147483648, %rax

x86-64 的 addq 虽然计算的是 64 位结果，但它直接携带的整数只有 32 位，并按有符号数扩展到 64 位。因此这种立即数的范围是：

1

-2147483648 到 2147483647

2147483648 超出了这个范围，汇编器会拒绝这条指令。这里不是加法结果超出了 64 位，而是指令本身放不下这个直接写入的整数。

修改汇编生成器：当 add 的右操作数是超出上述范围的整数时，先把它放进一个 scratch register，再执行寄存器加法。例如：

1
2
3


movq    $1, %rax
movabsq $2147483648, %rcx
addq    %rcx, %rax

修改后，至少检查下面四个边界值：

1
2
3
4


2147483647
2147483648
-2147483648
-2147483649

还要交换它们在加法左右两边的位置，确认解释器和编译器不再因为操作数顺序而表现不同。

这道练习要帮助你分清三件事：

1
2
3


语言里的整数范围
C++ long 能保存的范围
某一条机器指令能直接编码的立即数范围

练习 12：想一想下一章

如果下一章加入变量和局部绑定：

1

(let x 40 (+ x 2))

和现在的：

1

(+ 40 2)

会有什么不同？

先不用实现，只要想：

1
2


解释器怎样从 `let` 找到 `x` 的值？
编译器怎样为 `x` 安排一个保存位置？

这就是第二章要解决的问题。

1.9 本章总结

2.0 无名，天地之始；有名，万物之母

本节目录

练习