实现计算器级别的语言

本章开始真正写编译器。第一个目标很小：让编译器能够处理四则运算以及一些基本算术运算符，并把下面这样的表达式编译成可执行代码。

30 + (4 - 2) * -5

这个目标看似简单，实际已经触及编译器的核心问题：输入只是一串字符，但表达式本身有结构。括号要优先，乘除要高于加减，一元运算符还会改变含义。编译器必须从扁平的字符流中恢复出这棵隐藏的结构树。

如果完全没有背景知识，语法分析确实会显得抽象。历史上它也曾是编译器研究中的重要问题。不过今天我们已经有了成熟的方法，只要按合适的顺序学习，它并不神秘。

本章采用递归下降语法分析（recursive descent parsing）。它直观、容易手写，而且足够强大。GCC、Clang 等现实中的 C/C++ 编译器，也在重要部分使用了类似的手写递归下降分析器。

这项技术并不只属于编译器。配置文件、查询语言、模板语言、日志格式，只要文本里有结构，就会遇到类似问题。因此，递归下降分析值得放进你的长期工具箱。

步骤 1：制作只能编译一个整数的语言

先考虑最简单的 C 语言子集。你会想到什么样的语言呢？是只包含 `main` 函数的语言吗？还是只由一个表达式构成的语言？仔细想想，由一个整数构成的语言，大概就是能想到的最小子集。

本步骤首先实现这个最简单的语言。

本步骤要制作的程序，会从输入中读取一个数字，并输出一段把该数字作为程序退出码返回的汇编代码。也就是说，当输入是 42 这样的字符串时，编译器会读取它并输出如下汇编。

.intel_syntax noprefix
.globl main

main:
  mov rax, 42
  ret

`.intel_syntax noprefix` 是给汇编器的指令，表示在多种汇编写法中，本书选择使用 Intel 记法。现在制作的编译器必须在开头输出这一行。其他行已经在前一章说明过。

读到这里，你可能会想：“这样的程序也能叫编译器吗？”坦率地说，作者也这么想。但是，这个程序接受由一个数值构成的语言作为输入，并输出与该数值对应的代码。从定义上讲，它已经是名副其实的编译器。即使是这样简单的程序，只要持续改造，也很快能变得复杂起来。所以先完成这一步。

实际上，从整体开发流程来看，本步骤非常重要。后续开发都会以这一步生成的程序作为骨架继续推进。除了编译器主体，本步骤还会创建构建文件（Makefile）、自动测试以及 git 仓库。下面逐项说明这些作业。

另外，本书中制作的 C 编译器名为 `9cc`。`cc` 是 C compiler 的缩写。数字 9 没有特别含义，只是因为作者以前写过一个名为 `8cc` 的 C 编译器，所以把下一部作品命名为 `9cc`。这个名字并不重要。请不要因为纠结命名而迟迟不开始。包括 GitHub 仓库在内，名字以后也可以改，先随便取一个也没有问题。

mov rbp, rsp                    // Intel
mov %rsp, %rbp                  // AT&T
mov rax, 8                      // Intel
mov $8, %rax                    // AT&T
mov [rbp + rcx * 4 - 8], rax    // Intel
mov %rax, -8(rbp, rcx, 4)       // AT&T

编译器主体的制作

编译器通常以文件作为输入，但现阶段打开并读取文件还比较麻烦，所以这里直接把命令行的第一个参数当作代码。下面这个简单的 C 程序会把第一个参数当作数值读入，并嵌入固定的汇编模板中。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "参数个数不正确\n");
        return 1;
    }

    printf(".intel_syntax noprefix\n");
    printf(".globl main\n");
    printf("main:\n");
    printf(" mov rax, %d\n", atoi(argv[1]));
    printf(" ret\n");
    return 0;
}

创建一个名为 `9cc` 的空目录，并在其中创建 `9cc.c`，内容写入上面的程序。之后按如下方式运行，确认 `9cc` 能正常工作。

$ cc -o 9cc 9cc.c
$ ./9cc 123 > tmp.s

第一行会编译 `9cc.c`，生成名为 `9cc` 的可执行文件。第二行把 `123` 作为输入传给 `9cc`，生成汇编代码，并写入 `tmp.s`。我们来查看 `tmp.s` 的内容。

$ cat tmp.s
.intel_syntax noprefix
.globl main
main:
  mov rax, 123
  ret

如你所见，汇编已经生成。接下来，把这个汇编文件交给汇编器，就可以生成可执行文件。

在 Unix 中，`cc`（或 `gcc`）不只是 C/C++ 编译器，也能作为多种语言的前端，根据文件扩展名选择合适的编译器或汇编器。因此，和编译 `9cc` 一样，把 `.s` 扩展名的汇编文件传给 `cc`，也可以完成汇编。下面是汇编并运行生成文件的例子。

$ cc -o tmp tmp.s
$ ./tmp
$ echo $?
123

在 shell 中，可以通过 `$?` 变量取得上一条命令的退出码。上面的例子显示了与传给 `9cc` 的参数相同的数字 `123`，这说明程序确实在工作。请在 0～255 的范围内尝试 `123` 以外的数字，确认 `9cc` 的运行结果。Unix 进程的退出码范围就是 0～255。

自动测试的制作

也许很多读者平时写小程序时并不写测试，但本书在扩展编译器时会同时编写测试代码。刚开始可能觉得写测试很麻烦，但很快就会明白测试的作用。不写测试的话，最终每次都得手动运行同样的检查，反而更麻烦。

“写测试很麻烦”这种印象，很大程度上来自测试框架过大，或者测试思想被讲得过于教条。例如 JUnit 这类测试框架功能很强，但引入它、记住用法本身就要花时间。因此，本章不会引入正式测试框架，而是用 shell 脚本手写一个极其简单的“测试框架”。

下面是测试用的 shell 脚本 `test.sh`。其中的 shell 函数 `assert` 接收两个参数：预期输出值和输入值。它会把 `9cc` 的输出汇编起来，运行结果程序，并把实际结果与预期值比较。脚本在定义 `assert` 后，用 `0` 和 `42` 检查编译器是否能正确编译。

#!/bin/bash
assert() {
  expected="$1"
  input="$2"

  ./9cc "$input" > tmp.s
  cc -o tmp tmp.s
  ./tmp
  actual="$?"
  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 0
assert 42 42

echo OK

把上述内容保存为 `test.sh`，然后执行 `chmod a+x test.sh` 赋予执行权限。实际运行 `test.sh` 看看。如果没有出错，`test.sh` 最后会像下面这样显示 `OK` 并退出。

$ ./test.sh
0 => 0
42 => 42
OK

如果发生错误，`test.sh` 不会显示 `OK`，而是像下面这样显示失败测试的预期值和实际值。

$ ./test.sh
0 => 0
42 expected, but got 123

调试测试脚本时，可以给 bash 加上 `-x` 选项来运行脚本。加上 `-x` 后，bash 会如下显示执行跟踪。

$ bash -x test.sh
+ assert 0 0
+ expected=0
+ input=0
+ cc -o 9cc 9cc.c
+ ./9cc 0
+ cc -o tmp tmp.s
+ ./tmp
+ actual=0
+ [ 0 != 0 ]
+ assert 42 42
+ expected=42
+ input=42
+ cc -o 9cc 9cc.c
+ ./9cc 42
+ cc -o tmp tmp.s
+ ./tmp
+ actual=42
+ [ 42 != 42 ]
+ echo OK
OK

本书使用的“测试框架”不过就是上面这样的 shell 脚本。

与 JUnit 等正式测试框架相比，它也许显得过于简单，但这种简单程度正好与 9cc 本身的简单程度相匹配。

自动测试的重点只是：一键运行自己写的代码，并机械地比较结果。不要想得太复杂，先把测试跑起来才是最重要的。

用 make 构建

读完整本书的过程中，读者可能会构建 9cc 几百次，甚至几千次。

生成 9cc 可执行文件，再运行测试脚本，这些步骤每次都一样，交给工具处理会更方便。标准工具就是 `make` 命令。

`make` 运行时，会读取当前目录中名为 `Makefile` 的文件，并执行其中写好的命令。`Makefile` 由以冒号结尾的规则，以及规则对应的一组命令构成。下面这个 `Makefile` 用来自动化本步骤中要执行的命令。

CFLAGS=-std=c11 -g -static

9cc: 9cc.c

test: 9cc
	./test.sh

clean:
	rm -f 9cc *.o *~ tmp*

.PHONY: test clean

把上述内容保存为 `Makefile`，放在与 `9cc.c` 相同的目录中。

这样，只要执行 `make` 就能生成 9cc，执行 `make test` 就能运行测试。

`make` 能理解文件之间的依赖关系，所以修改 `9cc.c` 后，不需要在 `make test` 前手动执行 `make`。只要 `make` 发现 `9cc` 比 `9cc.c` 更旧，就会在运行测试前自动重新构建 9cc。

`make clean` 是删除临时文件的规则。临时文件也可以手动用 `rm` 删除，但误删不该删的文件会很麻烦，所以这种工具性操作也写进 `Makefile`。

另外，编写 `Makefile` 时必须注意：缩进必须使用制表符，不能用 4 个或 8 个空格，否则会报错。这只是一个不太好用的语法，但 make 是 1970 年代开发的老工具，传统上就是这样。

一定要给 `cc` 传入 `-static` 选项。这个选项会在“动态链接”一章中说明，现在不需要特别关心它的含义。

用 git 版本管理

本书使用 git 作为版本管理系统。我们会一步一步完成编译器，请在每一步都创建一个 git 提交，并写提交消息。提交消息可以用中文，只要用一行概括实际改了什么即可。如果想写多行详细说明，请在第一行之后空一行，再继续写说明。

git 只需要管理大家手写生成的文件。运行 9cc 后生成的文件，只要再次执行相同命令就能重新生成，不必纳入版本管理。相反，如果把这类文件也提交进去，每次提交的差异都会变得不必要地冗长，所以应当把它们排除在仓库之外。

git 可以在 `.gitignore` 文件中写入要排除在版本管理之外的文件模式。在与 `9cc.c` 相同的目录中创建 `.gitignore`，写入下面的内容，让 git 忽略临时文件和编辑器备份文件。

*~ *.o tmp* a.out 9cc

第一次使用 git 的读者，需要告诉 git 你的名字和邮箱。

这里设置的名字和邮箱会记录在提交日志中。下面是设置作者姓名和邮箱的例子，请改成你自己的信息。

$ git config --global user.name "Your Name"
$ git config --global user.email "you@example.com"

要创建提交，首先需要用 `git add` 添加修改过的文件。这次是第一次提交，所以先用 `git init` 创建 git 仓库，然后把目前为止创建的所有文件都用 `git add` 添加进去。

$ git init
Initialized empty Git repository in /home/user/9cc
$ git add 9cc.c test.sh Makefile .gitignore

之后执行 `git commit` 创建提交。

$ git commit -m "制作只能编译一个整数的编译器"

`-m` 选项用来指定提交消息。如果不加 `-m`，git 会启动编辑器。提交后，可以运行 `git log -p` 确认提交内容。

$ git log -p
commit 0942e68a98a048503eadfee46add3b8b9c7ae8b1 (HEAD -> master)
Author: Your Name <you@example.com>
Date: Sat Aug 4 23:12:31 2018 +0000 制作只能编译一个整数的编译器
diff --git a/9cc.c b/9cc.c
new file mode 100644
index 0000000..e6e4599
--- /dev/null
+++ b/9cc.c
@@ -0,0 +1,16
@@ +#include <stdio.h> +#include <stdlib.h> + +int main(int argc, char **argv) { + if (argc != 2) { ...

最后，把迄今为止创建的 git 仓库上传到 GitHub。严格来说没有必须上传到 GitHub 的理由，但也没有不上传的理由；GitHub 还能作为代码备份。要上传到 GitHub，先创建一个新仓库（下面的例子中，用户 `rui314` 创建了名为 `9cc` 的仓库），再用以下命令把它添加为远程仓库。

$ git remote add origin git@github.com:rui314/9cc.git

然后执行 `git push`，本地仓库的内容就会被推送到 GitHub。执行后，用浏览器打开 GitHub，确认自己的源代码已经成功上传。

到这里，第 1 步的编译器就完成了。本步骤中的编译器虽然简单得有些过分，但作为编译器所需的要素已经齐全。也许你现在还难以相信，不过接下来我们会不断扩展它的功能，最终把它培养成一个像样的 C 编译器。请先体会完成第一步的感觉。

步骤 2：制作能编译加减法的编译器

本步骤将在上一步做出的编译器基础上继续扩展，使它不仅能够处理 42 这样的单个数值，也能接受 2+11、5+20-4 这样的加减法表达式。

像 5+20-4 这样的表达式，也可以在编译时直接算出结果，并把结果数值（这里是 21）嵌入汇编中。但那样就更像解释器，而不是编译器了。因此，我们需要输出在运行时执行加减法的汇编。执行加法和减法的汇编指令分别是 add 和 sub。add 接收两个寄存器，把其中的内容相加，并把结果写入第一个参数寄存器；sub 与 add 类似，只是执行减法。使用这些指令，5+20-4 可以编译成下面这样。

.intel_syntax noprefix
.globl main

main:
  mov rax, 5
  add rax, 20
  sub rax, 4
  ret

这段汇编先用 mov 把 5 设置到 RAX 中，然后给 RAX 加上 20，再减去 4。执行到 ret 时，RAX 的值应当是 5+20-4，也就是 21。把上面的内容保存为 tmp.s，汇编并运行来确认一下。

$ cc -o tmp tmp.s
$ ./tmp
$ echo $?
21

如上所示，程序正确显示了 21。

那么，如何生成这样的汇编文件呢？如果把加减法表达式看成一门“语言”，可以把这门语言定义如下。

• 最开始是一个数字。
• 其后跟着 0 个或多个“项”。
• 所谓“项”，就是“+ 后接数字”或“- 后接数字”。

把这个定义直接落到 C 代码中，就会得到下面的程序。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "参数个数不正确\n");
        return 1;
    }

    char *p = argv[1];

    printf(".intel_syntax noprefix\n");
    printf(".globl main\n");
    printf("main:\n");
    printf(" mov rax, %ld\n", strtol(p, &p, 10));

    while (*p) {
        if (*p == '+') {
            p++;
            printf(" add rax, %ld\n", strtol(p, &p, 10));
            continue;
        }

        if (*p == '-') {
            p++;
            printf(" sub rax, %ld\n", strtol(p, &p, 10));
            continue;
        }

        fprintf(stderr, "意外的字符: '%c'\n", *p);
        return 1;
    }

    printf(" ret\n");
    return 0;
}

程序稍微变长了一些，但前半部分和 ret 之前的部分基本与上一步相同。中间新增的是读取项的代码。这次不再只是读取一个数字，而是要连续读取数字和运算符。由于 atoi 不会告诉我们读到了第几个字符，因此无法判断下一个项从哪里开始。这里改用 C 标准库的 strtol 函数。

strtol 读入数值后，会通过第二个参数更新指针，让它指向被读入数值之后的下一个字符。因此，读完一个数值后，如果后面还有 + 或 -，指针 p 就会指向那个字符。上面的程序利用这一点，在 while 循环中逐个读取项，并为每一项输出一行汇编。

现在运行这个改造后的编译器。更新 9cc.c 后，执行 make 就可以生成新的 9cc。运行示例如下。

$ make
$ ./9cc '5+20-4'
.intel_syntax noprefix
.globl main
main:
  mov rax, 5
  add rax, 20
  sub rax, 4
  ret

可以看到，汇编已经按预期输出。为了测试这个新功能，请在 test.sh 中加入下面这一行。

assert 21 "5+20-4"

完成到这里后，把本步骤的修改提交到 git。执行下面的命令。

$ git add test.sh 9cc.c
$ git commit

执行 git commit 会启动编辑器。写入“添加加法和减法”之类的提交消息并保存退出。然后用 git log -p 确认提交内容符合预期，最后执行 git push 把提交推送到 GitHub，本步骤就完成了。

步骤 3：引入词法分析器

上一步制作的编译器有一个缺点：如果输入中包含空白字符，就会报错。例如输入下面这种带空格的 5 - 3 时，程序本来应该读取 + 或 - 的位置会看到空白字符，因此编译失败。

$ ./9cc '5 - 3' > tmp.s
意外的字符: ' '

解决这个问题的一个直接办法，是在读取 + 和 - 时也像读取数字前那样跳过空白字符。这个办法本身没有特别大的问题，但本步骤采用另一种方式：在读取表达式之前，先把输入拆分成一个个单词。

和日语、英语一样，算术表达式和编程语言也可以看成由一串“词”组成。例如 5+20-4 可以看成 5、+、20、-、4 这 5 个词。这里的“词”称为“标记”（token）。标记之间的空白只是分隔符，不是标记本身的一部分。因此，把字符串拆成标记列时自然也会去掉空白字符。把字符串拆分为标记列的过程称为“词法分析”。

把字符串拆成标记列还有其他好处。把表达式拆成标记时，可以同时对每个标记分类并附加类型。例如 + 和 - 就是看起来那样的符号，而 123 这个字符串表示数值 123。词法分析并不只是把输入分割为字符串，而是同时解释每一个标记，这样后续消费标记列时需要考虑的事情就会减少。

对于目前支持加减法的表达式语法，标记类型有三种：+、- 和数值。为了实现方便，我们还会额外定义一种表示标记列结尾的特殊类型，这能让程序更简洁（类似字符串以 \0 结尾）。标记之间用指针连接成链表，这样就可以处理任意长度的输入。

代码会稍微变长。下面列出引入词法分析器后的改良版编译器。

#include <ctype.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 标记的种类
typedef enum {
    TK_RESERVED, // 符号
    TK_NUM, // 整数标记
    TK_EOF, // 表示输入结束的标记
} TokenKind;

typedef struct Token Token;

// 标记类型
struct Token {
    TokenKind kind; // 标记的类型
    Token *next; // 下一个输入标记
    int val; // kind 为 TK_NUM 时的数值
    char *str; // 标记字符串
};

// 当前关注的标记
Token *token;

// 用于报告错误的函数
// 接收与 printf 相同的参数
void error(char *fmt, ...) {
    va_list ap;
    va_start(ap, fmt);
    vfprintf(stderr, fmt, ap);
    fprintf(stderr, "\n");
    exit(1);
}

// 如果下一个标记是预期的符号，则读取该标记
// 返回真。否则返回假。
bool consume(char op) {
    if (token->kind != TK_RESERVED || token->str[0] != op)
        return false;
    token = token->next;
    return true;
}

// 如果下一个标记是预期的符号，就前进 1 个标记。
// 否则报告错误。
void expect(char op) {
    if (token->kind != TK_RESERVED || token->str[0] != op)
        error("'%c'不是", op);
    token = token->next;
}

// 如果下一个标记是数值，就前进 1 个标记并返回该数值。
// 否则报告错误。
int expect_number() {
    if (token->kind != TK_NUM)
        error("不是数字");
    int val = token->val;
    token = token->next;
    return val;
}

bool at_eof() {
    return token->kind == TK_EOF;
}

// 创建新标记并连接到 cur
Token *new_token(TokenKind kind, Token *cur, char *str) {
    Token *tok = calloc(1, sizeof(Token));
    tok->kind = kind;
    tok->str = str;
    cur->next = tok;
    return tok;
}

// 对输入字符串 p 词法分析并返回结果
Token *tokenize(char *p) {
    Token head;
    head.next = NULL;
    Token *cur = &head;

    while (*p) {
        // 跳过空白字符
        if (isspace(*p)) {
            p++;
            continue;
        }

        if (*p == '+' || *p == '-') {
            cur = new_token(TK_RESERVED, cur, p++);
            continue;
        }

        if (isdigit(*p)) {
            cur = new_token(TK_NUM, cur, p);
            cur->val = strtol(p, &p, 10);
            continue;
        }

        error("无法词法分析");
    }

    new_token(TK_EOF, cur, p);
    return head.next;
}

int main(int argc, char **argv) {
    if (argc != 2) {
        error("参数个数不正确");
        return 1;
    }

    // 词法分析
    token = tokenize(argv[1]);

    // 输出汇编代码的前半部分
    printf(".intel_syntax noprefix\n");
    printf(".globl main\n");
    printf("main:\n");

    // 表达式开头必须是数字，因此先检查它
    // 输出第一条 mov 指令
    printf(" mov rax, %d\n", expect_number());

    // `+ <数>`或者`- <数>`这样的标记的序列并消费它们
    // 输出汇编
    while (!at_eof()) {
        if (consume('+')) {
            printf(" add rax, %d\n", expect_number());
            continue;
        }

        expect('-');
        printf(" sub rax, %d\n", expect_number());
    }

    printf(" ret\n");
    return 0;
}

这段代码大约 150 行，不能算很短，但并没有做特别取巧的事情，从上往下读应该能理解。

先说明上面代码中用到的几个编程技巧。

• 语法分析器读取标记列的位置，用全局变量 token 表示。语法分析器会把链表 token 当作输入流向前读取。使用这种全局变量的风格未必漂亮；但在这里，把输入标记列看成类似标准输入的流，能让语法分析器代码更容易读。因此本书采用这种写法。
• 直接操作 token 的代码只放在 consume、expect 等函数里，其他函数不直接接触 token。
• tokenize 函数会构建链表。构建链表时，先创建一个哑元头节点 head，再把新元素连接到它后面，最后返回 head.next，这样代码会比较简单。这个方法会为哑元头节点多分配一点内存，但局部变量分配成本可以忽略，不需要特别在意。
• calloc 和 malloc 一样是内存分配函数。不同之处在于，calloc 会把分配到的内存清零。这里使用 calloc，是为了省掉手动初始化各成员的麻烦。

这个改良版可以正确跳过空白字符。请在 test.sh 中加入下面这一行测试。

assert 41 " 12 + 34 - 5 "

Unix 进程的退出码只能是 0～255 之间的数。编写测试时，请让整个表达式的结果落在 0～255 这个范围内。

把测试文件加入 git 仓库并提交，本步骤就完成了。

步骤 4：改进错误消息

迄今为止制作的编译器，在输入语法错误时，并不会指出错误发生在哪里。本步骤要改进这一点，使它能显示下面这种更直观的错误消息。

$ ./9cc "1+3++" > tmp.s
1+3++
    ^ 不是数字
$ ./9cc "1 + foo + 5" > tmp.s
1 + foo + 5
    ^ 无法词法分析

为了显示这种错误消息，需要知道错误发生在输入的第几个字节。为此，我们把整个输入字符串保存在 user_input 变量中，并定义一个新的错误报告函数：它接收指向输入字符串中某个位置的指针，然后打印出对应位置。代码如下。

// 输入程序
char *user_input;

// 报告出错位置
void error_at(char *loc, char *fmt, ...) {
    va_list ap;
    va_start(ap, fmt);

    int pos = loc - user_input;
    fprintf(stderr, "%s\n", user_input);
    fprintf(stderr, "%*s", pos, " "); // 输出 pos 个空格
    fprintf(stderr, "^ ");
    vfprintf(stderr, fmt, ap);
    fprintf(stderr, "\n");
    exit(1);
}

error_at 接收的指针指向完整输入字符串中的某个位置。把这个指针与指向输入开头的指针相减，就能知道错误位置是输入的第几个字节，并在该位置下方用 ^ 标出错误。

把 argv[1] 保存到 user_input，然后把 error("数不是") 这类调用改成 error_at(token->str, "数不是") 这类形式，本步骤就完成了。

对于实用级别的编译器，输入错误时的行为也应该编写测试。不过目前错误消息主要是为了辅助调试，所以这个阶段不专门为它写测试也可以。

if ((err = ReadyHash(&SSLHashSHA1, &hashCtx)) != 0)
    goto fail;
if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
    goto fail;
    goto fail;

语法的描述方法与递归下降语法分析

接下来要把乘除法和表示优先级的括号，也就是 *、/、() 加入语言。为此，需要跨过一个较大的技术关口：必须表达“乘法和除法在表达式中要先计算”这个规则。例如 1+2*3 应该解释为 1+(2*3)，而不是 (1+2)*3。这种决定哪个运算符先被结合的规则，称为“运算符优先级”（operator precedence）。

那么，运算符优先级应该怎样处理呢？如果只是沿用目前编译器的做法，从标记列开头顺次读取并输出汇编，然后直接加入 * 和 /，那么 1+2*3 很可能会被当作 (1+2)*3 来编译。

现有编译器当然可以正确处理运算符优先级。编译器的语法分析器非常强大，即使遇到这样的复杂输入，只要语法正确，也能机械地解释它。它的行为有时看起来像超越人类的读解能力，但实际并不是计算机具备了人类式的理解能力，而是通过一套机械的语法分析机制完成的。下面就来看这种机制具体是怎样工作的。

因此，在继续写代码之前，我们先暂停一下，系统学习语法分析的技巧。本章会按下面的顺序说明。

1. 首先把握语法分析器最终要输出什么样的数据结构。
2. 学习定义语法规则的方法。
3. 在此基础上，学习编写语法分析器的技巧。

用树结构表示语法结构

编程语言的语法分析器通常接收扁平的标记列作为输入，并输出表示嵌套结构的树。本书要制作的编译器也采用这种结构。

C 语言中的 if、while 等语法元素可以彼此嵌套。树结构正是表示这类嵌套结构的自然方法。

表达式有结构：括号中的部分要先计算，乘除法先于加减法。乍看之下它不像树，但用树表示它的结构非常简单。例如 1*(2+3) 可以用下面这样的树表示。

如果采用“从树的叶子开始依次计算”的规则，上面的树就表示 1*(2+3) 这个表达式。也就是说，树的形状本身就表达了具体的计算顺序。

再看另一个例子。下图这棵树表示 7-3-3。

上面的树通过树的形状明确表示了“减法从左到右结合”这一规则。也就是说，它表示的是 (7-3)-3 = 1，而不是 7-(3-3) = 7。如果要表示后者，树会不是向左加深，而是向右加深。

必须从左向右计算的运算符称为“左结合”运算符；必须从右向左计算的运算符称为“右结合”运算符。在 C 中，除了赋值运算符 = 以外，几乎所有运算符都定义为左结合。

树结构也可以表示更长、更深的表达式。下面这棵树表示 1*2+3*4*5。

像上面这样的树称为“语法树”（syntax tree）。其中，尽量去掉用于分组的括号等冗余元素、以更紧凑形式表示的语法树，称为“抽象语法树”（abstract syntax tree，AST）。上面的这些语法树都可以看作抽象语法树。

抽象语法树是编译器的内部表示，所以可以按实现需要定义。尽管如此，像加法、乘法这样的算术运算符，本来就是对左边和右边两个操作数的运算，因此任何编译器都自然会把它们表示成二叉树。另一方面，函数体中的语句这类只是按顺序执行、数量不固定的结构，则更适合表示为拥有多个子节点的扁平树。

语法分析的目标，就是构造抽象语法树。编译器首先进行语法分析，把输入的标记列转换为抽象语法树；随后再把这棵语法树转换为汇编代码。

用产生规则定义语法

接下来学习如何描述编程语言的语法。大多数编程语言的语法都可以用“产生规则”（production rule）来定义。产生规则是一种递归地定义语法结构的规则。

先从自然语言想一想。自然语言的语法也有嵌套结构。例如，一个名词可以扩展成“形容词 + 名词”的名词短语，而这个名词短语又可以出现在更大的句子里。也就是说，较小的语法成分可以被替换或嵌入到较大的语法成分中。

可以把这种语法看成一组规则：例如“句子由主语和谓语组成”，“名词短语可以是名词，也可以是形容词加名词”。从“句子”这个起点出发，不断应用这些规则展开，就能生成无数符合语法的句子。

反过来说，也可以从已有的句子出发，思考它是怎样通过一系列展开步骤生成出来的，从而理解这个字符串具有怎样的结构。

这种思想原本是为描述自然语言而提出的，但它和计算机容易处理的数据结构也很契合。因此，产生规则不仅用于编程语言，也被广泛用于计算机科学中的许多场景。

用 BNF 描述产生规则

为了紧凑地书写产生规则，常用的记法包括 BNF（Backus–Naur form）以及它的扩展形式 EBNF（Extended BNF）。本书使用 EBNF 描述 C 的语法。本节先说明 BNF，再说明 EBNF 的扩展记法。

在 BNF 中，一条产生规则通常写成 A = α₁α₂⋯ 的形式。这表示记号 A 可以展开为记号列 α₁α₂⋯。右侧可以包含 0 个或多个记号，其中既可以有不能再展开的记号，也可以有还会继续展开的记号。

不能继续展开的记号称为“终结符”（terminal symbol）；能够继续展开、也就是会出现在产生规则左侧的记号称为“非终结符”（nonterminal symbol）。用这类产生规则定义的语法通常称为“上下文无关文法”（context-free grammar）。

同一个非终结符可以对应多条产生规则。例如同时存在 A = α₁ 和 A = α₂ 时，表示 A 既可以展开为 α₁，也可以展开为 α₂。

产生规则的右边也可以为空。这样的规则会把左边的记号展开为长度为 0 的记号列，也就是“空”。不过，为了避免右边省略造成歧义，BNF 中通常会在右边写上表示“空”的记号 ε（epsilon）。本书也采用这种写法。

字符串用双引号括起来，例如 "foo"。字符串总是终结符。

以上就是 BNF 的基本规则。EBNF 在 BNF 之上增加了一些简写记法，可以更简洁地表达复杂规则。

例如 A = ("fizz" | "buzz")* 表示：A 可以展开为 "fizz" 或 "buzz" 重复 0 次以上得到的字符串，也就是下面这些字符串之一。

• ""
• "fizz"
• "buzz"
• "fizzfizz"
• "fizzbuzz"
• "buzzfizz"
• "buzzbuzz"
• "fizzfizzfizz"
• "fizzfizzbuzz"
• ⋯⋯

也就是说，可以生成由 fizz 和 buzz 任意连接而成的字符串。

简单的产生规则

作为用 EBNF 描述语法的例子，考虑下面这条产生规则。

expr = num ("+" num | "-" num)*

这里假定 num 是另行定义的、表示数值的记号。这个规则表示：expr 首先是一个 num，后面跟着 0 个或多个“+ num”或“- num”。这正是加减法表达式的语法。

从 expr 出发并不断展开，就可以生成任意加减法表达式，例如 1、10+5、42-30+2。下面确认几个展开结果。

expr → num →"1"

expr → num "+" num
→"10""+""5"

expr → num "-" num "+" num
→"42""-""30""+""2"

展开过程不仅可以按顺序用箭头表示，也可以画成树。上面表达式的语法树如下。

用树表示后，就能直观看出每个非终结符展开成了哪些记号。

如上图所示，包含输入中所有标记、并与语法一一对应的树，称为“具象语法树”（concrete syntax tree）。这个术语通常与抽象语法树相对。

另外，上面的具象语法树本身并没有把“加减法从左向右计算”这个规则完全表示出来。像这样的规则，在语言规格中通常不会只靠 EBNF 表示，而会在文字说明中补充一句“加减法从左向右结合”。语法分析器需要同时考虑 EBNF 和这些补充说明，读取表示表达式的标记列，并构造出能正确表示求值顺序的抽象语法树。

因此，上述语法中，EBNF 所表示的具象语法树与语法分析器输出的抽象语法树并不完全一致。也可以把语法定义得更冗长，使二者结构一致；但那样会让语法本身和语法分析器都更难写。实际的语言规格通常会在形式化语法的严密性和自然语言补充说明的易读性之间取得平衡。

用产生规则表示运算符优先级

产生规则是描述语法的强力工具。只要设计得当，运算符优先级也可以自然地表示在产生规则中。新的语法如下。

expr = mul ("+" mul | "-" mul)*
mul = num ("*" num | "/" num)*

在之前的规则中，expr 可以直接展开为 num；这次 expr 需要先经过 mul 再展开。mul 是处理乘除法的产生规则，而加减法的 expr 会把 mul 当作组成部分使用。这样，“乘除法优先”这个规则就会自然体现在语法树中。来看几个具体例子。

在上面的树结构中，乘法总是出现在比加法更靠近叶子的方向。实际上，由于不存在从 mul 回到 expr 的产生规则，所以乘法下面不会再生成加法节点。仅靠这样简单的规则就能把优先级表示进树结构中，稍显不可思议。请你也实际对照产生规则和语法树，确认树的形状是否正确。

包含递归的产生规则

产生规则也可以自然地表达递归语法。下面是加入了优先级括号和四则运算之后的产生规则。

expr = mul ("+" mul | "-" mul)*
mul = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

与前面的语法相比，这个新语法中，原来到处出现 num 的位置现在改成了 primary，也就是可以是 num，也可以是 "(" expr ")"。换言之，新语法把括号包住的表达式当作一个整体来处理，就像一个单独的数字一样。来看一个例子。

下面这棵树是 1*2 的语法树。

下面这棵树是 1*(2+3) 的语法树。

比较这两棵树，可以看到 mul 右侧分支中 primary 的展开结果不同。出现在树末端的 primary，既可以展开为一个数字，也可以展开为用括号括起来的任意表达式。这个规则就这样反映在树结构中。只靠如此简单的产生规则就能表达括号的优先级，确实有点令人感动。

递归下降语法分析

如果有 C 语言的产生规则，并从这些规则不断展开，就可以从形式上机械地生成任意合法的 C 程序。但我们在 9cc 中要做的是反方向的事情：外部给我们一个字符串形式的 C 程序，我们要找出怎样的展开步骤能生成这个字符串，也就是要知道与输入字符串对应的语法树结构。

对于实用的产生规则，可以机械地写出代码，用来求得与该规则生成的句子相匹配的语法树。这里说明其中一种技巧：“递归下降语法分析”。

以四则运算语法为例来考虑。下面再次列出四则运算的语法。

expr = mul ("+" mul | "-" mul)*
mul = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

递归下降语法分析的基本策略，是把每个非终结符一一映射为一个函数。因此语法分析器会拥有 expr、mul、primary 这三个函数；每个函数负责解析与其名称对应的语法成分。

接下来考虑具体代码。语法分析器接收输入标记列，生成并返回抽象语法树。先定义抽象语法树节点的类型，如下所示。

// 抽象语法树节点的种类
typedef enum {
    ND_ADD, // +
    ND_SUB, // -
    ND_MUL, // *
    ND_DIV, // /
    ND_NUM, // 整数
} NodeKind;

typedef struct Node Node;

// 抽象语法树节点类型
struct Node {
    NodeKind kind; // 节点类型
    Node *lhs; // 左边
    Node *rhs; // 右边
    int val; // 仅在 kind 为 ND_NUM 时使用
};

lhs 和 rhs 分别是 left-hand side 和 right-hand side 的缩写，也就是左边和右边。

还要定义用于创建新节点的函数。本语法中的节点大致分为两类：接收左、右两个操作数的二元运算符节点，以及表示数值的节点。因此准备两个构造函数。

Node *new_node(NodeKind kind, Node *lhs, Node *rhs) {
    Node *node = calloc(1, sizeof(Node));
    node->kind = kind;
    node->lhs = lhs;
    node->rhs = rhs;
    return node;
}

Node *new_node_num(int val) {
    Node *node = calloc(1, sizeof(Node));
    node->kind = ND_NUM;
    node->val = val;
    return node;
}

现在用这些函数和数据类型来写语法分析器。+ 和 - 是左结合运算符。解析左结合运算符的函数，可以按下面这种模式来写。

Node *expr() {
    Node *node = mul();

    for (;;) {
        if (consume('+'))
            node = new_node(ND_ADD, node, mul());
        else if (consume('-'))
        node = new_node(ND_SUB, node, mul());
        else
        return node;
    }
}

consume 是前面步骤中定义过的函数：如果输入流中的下一个标记与参数匹配，它就读取一个标记并返回真。

请看 expr 函数。expr = mul ("+" mul | "-" mul)* 这条产生规则，与函数调用和循环的对应关系应当很清楚。这个函数返回的抽象语法树会体现运算符的左结合性，也就是返回节点左侧的分支会更深。

再定义 expr 所使用的 mul 函数。* 和 / 也是左结合运算符，因此可以用相同的模式来描述。函数如下。

Node *mul() {
    Node *node = primary();

    for (;;) {
        if (consume('*'))
            node = new_node(ND_MUL, node, primary());
        else if (consume('/'))
        node = new_node(ND_DIV, node, primary());
        else
        return node;
    }
}

上面代码中的函数调用关系，正好对应 mul = primary ("*" primary | "/" primary)* 这条产生规则。

最后定义 primary 函数。primary 要读取的不是左结合运算符，所以不用上面的模式；它只需要支持 primary = "(" expr ")" | num 这条产生规则对应的函数调用。代码如下。

Node *primary() {
    // 如果下一个标记是 "("，则应解析为 "(" expr ")"
    if (consume('(')) {
        Node *node = expr();
        expect(')');
        return node;
    }

    // 否则应为数值
    return new_node_num(expect_number());
}

到这里所有函数都齐了。这样真的能解析标记列吗？乍看也许不明显，但这组函数确实可以解析标记列。以 1+2*3 为例来考虑。

最先被调用的是 expr。我们把整个输入当作一个 expr 来读取。于是调用关系会变成 expr → mul → primary，读入 1 这个标记，并把表示 1 的语法树作为 expr 的返回值。

接着，expr 中的 consume('+') 为真，+ 标记被消费，mul 被再次调用。此时输入剩下的是 2*3。

和上次一样，mul 会调用 primary 并读入 2，但这次 mul 不会立刻返回。因为 mul 中的 consume('*') 为真，所以 mul 再次调用 primary，读入 3。结果，mul 会返回表示 2*3 的语法树。

回到 expr 后，表示 1 的语法树与表示 2*3 的语法树组合起来，构成表示 1+2*3 的语法树，并成为 expr 的返回值。也就是说，1+2*3 被正确解析了。

把函数调用关系以及各个函数读取的标记画成图，会得到下面的形式。图中最上层是负责读取整个 1+2*3 的 expr 调用；其下有两个 mul 调用，分别读取 1 和 2*3。

再看一个稍微复杂的例子。下图表示解析 1*2+(3+4) 时各个函数之间的调用关系。

不习惯递归的程序员，可能会觉得上面这种递归函数很难理解。坦率地说，即使作者已经非常熟悉递归，也仍然觉得这种代码能正确运行有点像魔法。递归代码即便明白原理，也总有某种不可思议感。请在脑中反复跟踪代码，并实际运行确认它确实能工作。

这种把一条产生规则映射到一个函数的语法分析方法，称为“递归下降语法分析”。上面的语法分析器只需要向前看一个标记，就能决定调用哪个函数或是否返回；这种只向前看一个标记的递归下降语法分析器称为 LL(1) 语法分析器。能被 LL(1) 语法分析器解析的语法称为 LL(1) 语法。

栈机器

前面的部分已经说明了如何把标记列转换成抽象语法树。通过选择能表达运算符优先级的语法，可以让 * 和 / 总是出现在比 + 和 - 更靠近叶子的分支上。那么，这棵树应该如何转换成汇编呢？下面说明这个方法。

先想一想，为什么不能沿用加减法阶段的简单做法来生成汇编。此前能够处理加减法的编译器把 RAX 当作结果寄存器，并在其中执行加法和减法。也就是说，编译后的程序在计算过程中只需要保存一个中间结果。

但是，如果表达式中包含乘除法，中间结果不一定只有一个。以 2*3+4*5 为例，在执行最后的加法之前，必须先算出左右两边的 2*3 和 4*5。也就是说，这种情况下需要同时保存两个中间结果，才能完成整体计算。

有一种称为“栈机器”的计算模型，特别适合处理这种计算。这里先暂时离开语法分析器生成的抽象语法树，学习一下栈机器。

栈机器的概念

栈机器是一种把栈作为数据保存区域的计算机。因此，在栈机器中，“压栈”和“出栈”是两个基本操作。压栈是在栈顶放入新元素；出栈则是从栈顶取出元素。

栈机器中的运算命令作用于栈顶元素。例如，栈机器的 ADD 命令会从栈顶弹出两个元素，把它们相加，并把结果压回栈中（为了避免和 x86-64 指令混淆，这里把虚拟栈机器的指令全部用大写表示）。换句话说，ADD 是把栈顶两个元素替换成它们之和的命令。

SUB、MUL、DIV 与 ADD 类似，分别把栈顶两个元素替换为它们的差、积、商。

PUSH 命令会把作为参数给出的元素压到栈顶。这里暂时不用，但也可以设想一个 POP 命令，用来从栈顶取出一个元素并丢弃。

接下来用这套指令来计算 2*3+4*5。按上面定义的栈机器，可以用下面的代码完成计算。

// 计算 2*3
PUSH 2
PUSH 3
MUL

// 计算 4*5
PUSH 4
PUSH 5
MUL

// 计算 2*3 + 4*5
ADD

稍微详细看一下这段代码。假设栈中一开始已经有一些值；这里这些值不重要，所以用“⋯”表示。图中栈从上向下增长。

最初的两个 PUSH 会把 2 和 3 压入栈；紧接着 MUL 执行前，栈状态如下。

MUL 会取出栈顶两个值，也就是 3 和 2，相乘得到 6，再把 6 压回栈。因此执行 MUL 后，栈状态如下。

接着把 4 和 5 压入栈中；在第二个 MUL 执行之前，栈会变成下面这样。

这里执行 MUL 时，会取出 5 和 4，相乘得到 20，再把 20 压回栈。

注意，此时 2*3 和 4*5 的计算结果都已经在栈上。在这个状态下执行 ADD，就会计算 20+6，并把结果压回栈中；最终栈会变成下面的状态。

栈机器的计算结果就是最后留在栈顶的值。因此，26 正是 2*3+4*5 的结果，这个表达式也就完成了计算。

栈机器不只适用于这个表达式，也能够处理需要保存多个中间结果的表达式。只要每个部分表达式都遵守“执行后把一个结果值留在栈顶”这一约定，就可以用上述方法编译。

编译到栈机器

本节说明如何把抽象语法树转换成栈机器代码。掌握这个方法后，就能解析四则运算表达式，构建抽象语法树，再用 x86-64 指令模拟栈机器来运行。也就是说，我们终于可以写出能编译四则运算的编译器。

在栈机器中，计算一个部分表达式时，只要最后把代表该结果的一个值留在栈顶即可。考虑下面这棵树。

这里的 A 和 B 是对任意子树的抽象表示，实际节点可以有不同类型。具体节点类型和子树形状并不影响整体思路；编译一棵树时，只需要按下面的方式处理即可。

1. 左的部分木编译
2. 右的部分木编译
3. 栈的 两个值，那加法了结果在置换代码输出

生成代码时，可以先为左子树输出代码，使左子树的计算结果留在栈顶；再为右子树输出代码，使右子树的计算结果也留在栈顶。这样，当前节点的两个操作数就都在栈上了。接下来只要输出相应运算指令，把这两个值替换为计算结果，就能得到整棵子树的值。

这样把抽象语法树编译成栈机器代码时，本质上就是递归地沿着树向下输出汇编。不习惯递归思维的读者可能会觉得困难，但处理树这种自相似的数据结构时，递归是最标准的技巧。

以下的例在具体的思考一下。

代码生成函数木的根的节点受取。

按上面的步骤，函数首先会编译左侧子树，也就是数值 2。由于 2 的求值结果就是 2，这个子树的编译结果就是 PUSH 2。

次代码生成函数右的部分木编译。和递归的部分木的左側编译，结果作为PUSH 3输出。次部分木的右側编译，PUSH 4输出。

之后，代码生成函数会从递归调用中返回，并根据当前子树的运算符类型输出代码。它先输出把栈顶两个元素替换为其乘积的代码，再输出把栈顶两个元素替换为其和的代码。结果会生成如下汇编。

PUSH 2 PUSH 3 PUSH 4 MUL ADD

这种手法使用，抽象语法树机械的汇编落作为的。

在 x86-64 中实现栈机器的方法

迄今为止讨论的是虚拟栈机器。实际的 x86-64 并不是栈机器，而是寄存器机器。x86-64 的运算通常定义在两个寄存器之间，并不是直接作用于栈顶两个值。因此，要在 x86-64 上使用栈机器技巧，需要用寄存器机器来模拟栈机器。

用寄存器机器模拟栈机器相对简单。栈机器中的一条指令，可以用多条实际机器指令来实现。

面向具体的手法说明。

首先准备一个寄存器，用来指向栈顶元素，这个寄存器称为栈指针。要从栈顶弹出两个值时，就读取栈指针指向的两个元素，并把栈指针移动相应的距离。反过来，要压入一个值时，就先移动栈指针，再把值写入栈指针指向的内存区域。

x86-64 的 RSP 寄存器就是以栈指针用途设计的。push 和 pop 等 x86-64 指令会隐式使用 RSP 作为栈指针，修改它的值，并访问 RSP 指向的内存。因此，在 x86-64 中按栈机器方式生成代码时，直接使用 RSP 作为栈指针是很自然的。先把 1+2 编译成用 x86-64 模拟栈机器的汇编。示例如下。

// 将左边和右边压入栈
push 1
push 2

// 弹出到 RAX 和 RDI 后相加
pop rdi
pop rax
add rax, rdi

// 将相加结果压回栈
push rax

x86-64 没有“把 RSP 指向的两个元素相加”这样的指令，所以需要把值加载到寄存器中相加，再把结果压回栈。上面的 add 指令完成的就是这个操作。

同样，如果在 x86-64 上实现 2*3+4*5，可以写成下面这样。

// 计算 2 * 3，并把结果压入栈
push 2
push 3
pop rdi
pop rax
mul rax, rdi
push rax

// 计算 4 * 5，并把结果压入栈
push 4
push 5
pop rdi
pop rax
mul rax, rdi
push rax

// 将栈顶两个值相加，也就是计算 2 * 3 + 4 * 5
pop rdi
pop rax
add rax, rdi
push rax

这样，利用 x86-64 的栈操作指令，即使目标机器是 x86-64，也可以运行非常接近栈机器的代码。

下面的 gen 函数用 C 实现了这种方法。

void gen(Node *node) {
    if (node->kind == ND_NUM) {
        printf(" push %d\n", node->val);
        return;
    }

    gen(node->lhs);
    gen(node->rhs);

    printf(" pop rdi\n");
    printf(" pop rax\n");

    switch (node->kind) {
    case ND_ADD:
        printf(" add rax, rdi\n");
        break;
    case ND_SUB:
        printf(" sub rax, rdi\n");
        break;
    case ND_MUL:
        printf(" imul rax, rdi\n");
        break;
    case ND_DIV:
        printf(" cqo\n");
        printf(" idiv rdi\n");
        break;
    }

    printf(" push rax\n");
}

这里没有新的语法分析和代码生成上的关键点，不过上面的代码中使用了规格有些特殊的 idiv 指令，需要说明一下。

idiv 是有符号除法指令。x86-64 的 idiv 规格并不直观。上面的代码本来想写成 idiv rax, rdi 这样的形式，但 x86-64 并不存在接收两个寄存器的除法指令。取而代之的是，idiv 会隐式读取 RDX 和 RAX，把它们合在一起看作一个 128 位整数，再除以作为参数给出的 64 位寄存器；结果的商写入 RAX，余数写入 RDX。

栈机器的说明到这里结束。读到这里，读者已经知道如何做复杂一些的语法分析，以及如何把语法分析得到的抽象语法树落到机器码上。现在把这些知识用回编译器制作中。

步骤 5：制作能四则运算的语言

本步骤要修改目前为止制作的编译器，把它扩展为能够处理带优先级括号的四则运算表达式。必要部件已经齐了，下面开始写新代码。编译器的 main 函数要改为使用新做的语法分析器和代码生成器，大致如下。

int main(int argc, char **argv) {
    if (argc != 2) {
        error("参数个数不正确");
        return 1;
    }

    // 词法分析语法分析
    user_input = argv[1];
    token = tokenize(user_input);
    Node *node = expr();

    // 输出汇编代码的前半部分
    printf(".intel_syntax noprefix\n");
    printf(".globl main\n");
    printf("main:\n");

    // 一边遍历抽象语法树，一边生成代码
    gen(node);

    // 栈顶应该保留表达式整体的值
    // 将其加载到 RAX，作为函数返回值
    printf(" pop rax\n");
    printf(" ret\n");
    return 0;
}

到了这个阶段，加减乘除以及表示优先级的括号应该都能被正确编译了。添加一些测试。

assert 47 '5+6*7'
assert 15 '5*(9-6)'
assert 4 '(3+5)/2'

另外，前面的讲解为了方便，把 *、/、() 的实现说成像是一次完成的，但实际开发中最好避免一次做完。原本已经支持加减法，所以应先在不破坏现有功能的前提下引入抽象语法树和使用它的代码生成器；之后再添加新功能和测试。

步骤 6：一元加号与一元减号

减号 - 不仅可以写在 5-3 这样两个项之间，也可以写在 -3 这样单独的项之前。同样，加号 + 也可以省略左侧操作数，写成 +3。这种只取一个项作为操作数的运算符称为“一元运算符”（unary operator）。相对地，取两个项的运算符称为“二元运算符”（binary operator）。

C 中除了 + 和 - 以外，还有取地址 & 和指针解引用 * 等一元运算符。本步骤只实现 + 和 -。

一元 +、一元 - 与二元 +、二元 - 使用相同记号，但定义不同。二元 - 被定义为“从左边减去右边”，而一元 - 没有左边，因此不能沿用二元 - 的定义。C 中一元 - 被定义为反转右侧值的正负号；一元 + 则定义为直接返回右侧值。它基本上是不做任何事的运算符，所以也可以说是为了和一元 - 对称而存在。

+ 和 - 可以理解为存在多个同名但定义相似又不同的运算符：一元版本和二元版本。到底是一元还是二元，要根据上下文判断。包含一元 +/- 的新语法如下。

expr = mul ("+" mul | "-" mul)*
mul = unary ("*" unary | "/" unary)*
unary = ("+" | "-")? primary
primary = num | "(" expr ")"

在这个新语法中，新增了 unary 这个非终结符，并让 mul 使用 unary，而不是直接使用 primary。X? 表示可选项，即 X 出现 0 次或 1 次。unary = ("+" | "-")? primary 这条规则表示：unary 可以是前面带一个可选正负号的 primary。

请确认 -3、-(3+5)、-3*+5 这些表达式都匹配这个新语法。下面给出 -3*+5 的语法树。

接下来按这套新语法修改语法分析器。由于递归下降语法分析会把每条产生规则映射为一个函数，修改重点就是增加 unary 这一层，并让 mul 调用 unary。unary 函数大致如下。

Node *unary() {
    if (consume('+'))
        return primary();
    if (consume('-'))
        return new_node(ND_SUB, new_node_num(0), primary());
    return primary();
}

这里在解析的阶段在+xx，-x0-x置换了。因此本步骤代码生成器的修改不需要。

写几个测试，并和一元 +/- 的代码一起检查，本步骤就完成了。写测试时仍要注意测试结果落在 0～255 范围内。像 -10+20 这样虽然使用了一元 - 但整体结果为正的表达式，适合用作测试。

步骤 7：比较运算符

本节实现 <、<=、>、>=、==、!=。这些比较运算符看起来有特殊含义，但实际上和 +、- 一样，都是接收两个整数并返回一个整数的普通二元运算符。+ 返回两边相加的结果；例如 == 在两边相同时返回 1，不同时返回 0。

修改词法分析器

迄今为止处理过的符号标记长度都是 1 个字符，代码也以此为前提。要处理 == 这样的比较运算符，就需要把代码一般化。我们在 Token 结构体中加入 len 成员，用来保存标记字符串的长度。新的结构体类型如下。

struct Token {
    TokenKind kind; // 标记的类型
    Token *next; // 下一个输入标记
    int val; // kind 为 TK_NUM 时的数值
    char *str; // 标记字符串
    int len; // 标记长度
};

随着这个修改，consume 和 expect 等函数也要相应调整，让它们接收字符串而不是字符。修改示例如下。

bool consume(char *op) {
    if (token->kind != TK_RESERVED ||
    strlen(op) != token->len ||
    memcmp(token->str, op, token->len))
    return false;
    token = token->next;
    return true;
}

对由多个字符组成的符号做词法分析时，必须优先匹配更长的标记。例如剩余输入以 > 开头时，如果不先用 strncmp(p, ">=", 2) 检查它是否是 >=，而是先检查是否以 > 开头，那么 >= 就会被错误地拆成 > 和 = 两个标记。

新的语法

为了给语法分析器加入比较运算符支持，先考虑加入比较运算符后的语法应该是什么样。把目前出现过的运算符按优先级从低到高排列，如下所示。

1. ==!=
2. <<=>>=
3. +-
4. */
5. 一元+一元-
6. ()

运算符优先级可以用产生规则表示。不同优先级的运算符会映射到不同的非终结符。仿照 expr 和 mul 的方式，加入比较运算符后的新语法如下。

expr = equality
equality = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add = mul ("+" mul | "-" mul)*
mul = unary ("*" unary | "/" unary)*
unary = ("+" | "-")? primary
primary = num | "(" expr ")"

equality 表示 == 和 !=，relational 表示 <、<=、>、>=。这些非终结符都可以使用解析左结合运算符的相同模式映射到函数。

另外，上面的语法把整个表达式定义为 equality，因此把 expr 与 equality 分开了。也可以直接把 equality 的右边写到 expr 中，但上面这种写法更清楚。

生成汇编代码

在 x86-64 中，比较使用 cmp 指令。从栈中弹出两个整数并比较，如果相等就在 RAX 中设置 1，否则设置 0。代码如下。

  pop rdi
  pop rax
  cmp rax, rdi
  sete al
  movzb rax, al

这个代码，短的汇编和盛因此，步骤字节步骤在代码看。

最初两行从栈中弹出值。第 3 行比较这些值。比较结果会去哪里？在 x86-64 中，比较指令的结果会被设置到一种特殊的“标志寄存器”中。标志寄存器会在执行整数运算或比较运算指令时更新，里面包含结果是否为 0、是否发生进位/溢出、结果是否小于 0 等标志位。

标志寄存器不是普通整数寄存器。如果想把比较结果设置到 RAX，就需要把标志寄存器中的特定位复制到 RAX。这就是 sete 指令的作用。sete 会在紧邻前面的 cmp 指令比较的两个寄存器值相等时，把指定寄存器（这里是 AL）设为 1；否则设为 0。

AL 是本书目前还没有正式介绍过的寄存器名。实际上，AL 是 RAX 低 8 位的别名寄存器。通过 sete 设置 AL 时，RAX 的低 8 位也会随之更新。不过，经由 AL 更新 RAX 时，高 56 位的值不会自动清零；如果想让整个 RAX 成为 0 或 1，就需要清零高 56 位。这就是 movzb 指令的作用。之所以不能让 sete 直接写入 RAX，是因为 sete 的规格只接受 8 位寄存器作为参数。因此要用这两条指令把比较结果设置到 RAX。

把 sete 换成其他指令，就可以实现其他比较运算符。< 使用 setl，<= 使用 setle，!= 使用 setne。

> 和 >= 不需要在代码生成器中单独支持。语法分析器可以交换左右两边，把它们改写为 < 和 <=。