从两个表达式开始：整数和加法

写解释器和编译器之前，先说清楚一件事：

1

第一章里，什么样的程序算合法？

这一步是在定义语言，而不是在讨论某个 C++ 函数怎样写。规则一旦确定，parser 要按它建立 AST，解释器和编译器也必须让同一个程序得到相同的结果。否则，我们实现的就是几套彼此不一致的语言。

第一章的程序很小，就是一个表达式。

表达式可以先理解成：

1

能算出一个值的东西。

第一章只认两种表达式：

1
2

整数
加法

整数

整数是最小的表达式：

1
2
3
4

0
42
-7
100

它的结果就是它自己。

1
2

42 -> 42
-7 -> -7

这里的 -7 是一个整数，不是减法。第一章还没有减法表达式。

加法

加法写成 Lisp 风格：

1

(+ 40 2)

它表示：

1

40 + 2

这段程序由五个小块组成：

1
2
3
4
5

(     左括号
+     加号
40    左边表达式
2     右边表达式
)     右括号

注意，左右两边不是“必须是整数”，而是“必须是表达式”。所以加法里面还可以继续放加法：

1

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

可以先这样看：

1
2
3

左边 (+ 1 2) -> 3
右边 (+ 3 4) -> 7
最后 3 + 7 -> 10

这就是本章语言里唯一的递归结构：表达式里面还能继续出现表达式。

写成规则

把上面的说法压缩成规则，就是：

1
2
3
4

expr ::= integer
       | "(" "+" expr expr ")"

integer ::= "-"? digit+

第一次看到这种写法，不用把它当成新数学。它只是更短的人话：

1
2

expr 可以是 integer。
expr 也可以是：左括号、加号、两个 expr、右括号。

这里有几个符号先这样读：

1
2
3
4
5

::=      可以写成
|        或者
"..."    源码里真的会出现这些字符
"-"?     负号可以有，也可以没有
digit+   一个或多个数字

digit+ 里的 + 不是加法符号，而是“一个或多个”的意思。

合法和非法

下面这些程序合法：

1
2
3
4
5

42
-7
(+ 40 2)
(+ (+ 1 2) 3)
(+ (+ 1 2) (+ 3 4))

非法程序和原因可以一一对照：

所以 -1 合法，因为它是一个整数；(- 10 1) 不合法，因为第一章还没有定义减法表达式。负号是不是紧贴数字，会改变它在语言里的角色。

本章正文示例只使用不会溢出、也能直接写进当前汇编指令的小整数。解释器用 C++ 的 long 保存整数，编译器生成 64 位整数指令；但“整数值是 64 位”不等于每条指令都能直接带一个任意大的整数。练习 11 会专门观察 addq 的立即数范围，并补上大整数操作数的生成规则。至于超出 long 范围的整数和算术溢出应该采用什么语义，不在第一版课程中定义。

现在我们知道什么文本算合法。下一节先不急着写 parser，而是看 parser 最终要生成的结构：AST。