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

本节阅读量:

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

1

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

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

表达式可以先理解成：

1

能算出一个值的东西。

第一章只认两种表达式：

1
2


整数
加法

整数

整数是最小的表达式：

它的结果就是它自己。

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
2
3
4
5
6


(- 10 1)
(* 2 3)
(+ 1)
(+ 1 2 3)
x
(+40 2)

原因也很简单：

1
2
3
4
5


第一章没有减法。
第一章没有乘法。
+ 后面必须正好有两个表达式。
第一章没有变量。
普通小块要用空白或括号边界分开。

所以 -1 合法，因为它是整数；(- 10 1) 不合法，因为第一章没有减法表达式。

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

1.0 合抱之木，生于毫末

1.2 AST：从字符串到 C++ 可操作的结构

本节目录