指针与字符串字面量

到目前为止，我们的语言已经能做不少计算，但还不能写出经典的 Hello world。本章会加入字符串相关能力，让程序终于可以输出可读消息。

在 C 中，字符串字面量并不是孤立特性。它和 char、数组、指针、全局数据区都有关系。先看一个最简单的例子。

int main(int argc, char **argv) {
    printf("Hello, world!\n");
}

从实现角度看，字符串字面量可以理解成一个隐藏的全局字符数组。上面的代码大致等价于下面这种写法。这里的 msg 只是说明用的名字，真实编译器会生成不会与用户代码冲突的内部名字。

char msg[15] = "Hello, world!\n";

int main(int argc, char **argv) {
    printf(msg);
}

要走到字符串字面量这一步，编译器还缺几块基础设施。我们会按依赖顺序补上这些能力。

1. 一元 & 和一元 *
2. 指针
3. 数组
4. 全局变量
5. char 类型
6. 字符串字面量

这些功能完成后，测试程序也会从简单表达式逐渐过渡到更接近普通 C 程序的形式。

步骤 16：一元 & 与一元 *

本步骤作为实现指针的第一步，先实现返回地址的一元 & 运算符，以及解引用地址的一元 * 运算符。

这两个运算符本来分别会返回或使用指针类型的值。但我们的编译器目前还没有整数以外的类型，所以先用整数类型代替指针类型。

也就是说，&x 会把变量 x 的地址作为一个整数返回；*x 则把 x 的值视为地址，并从该地址读取值。

实现这些运算符后，下面这样的代码就可以运行。

x = 3;
y = &x;
return *y; // 返回 3

另外，因为局部变量在内存上连续分配，所以也可以经由指针间接地访问栈上的变量。

下面的代码假定变量 x 位于栈上变量 y 的 8 字节上方。

x = 3;
y = 5;
z = &y + 8;
return *z; // 返回 3

在这种没有区分指针类型和整数类型的实现里，例如 *4 这样的表达式会被当作“从地址 4 读取值”的表达式。当前阶段这样处理即可。

实现本身比较简单。加入一元 & 和一元 * 后，语法如下所示。按这个语法修改语法分析器，将一元 & 和一元 * 分别读成 ND_ADDR 和 ND_DEREF 类型的节点。

unary="+"? primary
| "-"? primary
| "*" unary
| "&" unary

代码生成器也需要修改。修改点如下。

case ND_ADDR:
gen_lval(node->lhs);
return;
case ND_DEREF:
gen(node->lhs);
printf(" pop rax\n");
printf(" mov rax, [rax]\n");
printf(" push rax\n");
return;

步骤 17：取消隐式变量定义，并引入 int 关键字

到目前为止，变量和函数返回值都被隐式地视为 int。因此此前不能写 int x; 这样的、同时给出类型名的变量定义；所有新出现的标识符都会被当作新的变量名。今后不能再继续依赖这个假定，所以先改造这一点。本步骤实现以下功能。

• 如果新的标识符作为变量名出现，但该变量没有定义，则报错。
• 支持 int x; 这种形式的变量定义。不需要支持 int x = 3; 这样的初始化，也不需要支持 int x, y; 这样的多变量定义。先实现最简单的形式即可。
• 函数目前写成 foo(x, y) 这样的形式，本步骤将其改成 int foo(int x, int y)。由于当前顶层只有函数定义，语法分析器先读取 int，再读取函数名，随后读取 int <参数名> 这样的参数列表即可。不必为了“将来扩展”而支持更复杂的语法；能读入简单的 int <函数名>(...) 形式就足够。

步骤 18：引入指针类型

定义表示指针的类型

本步骤开始允许类型名由 int 后接 0 个或多个 * 组成。也就是说，可以解析 int *x 和 int ***x 这样的定义。

编译器内部也必须能表示“指向 int 的指针”这样的类型。例如变量 x 是指向 int 的指针时，编译器需要知道表达式 *x 的类型是 int。“指向指向指向 int 的指针的指针”这样的复杂类型也可能出现，不能用固定大小的枚举值简单表示。

因此这里使用指针来表示类型关系。到目前为止，变量关联的信息只有“相对于栈上基址指针 RBP 的偏移量”。现在要在其中加入变量类型。粗略地说，类型可以用下面这样的结构体表示。

struct Type {
    enum { INT, PTR } ty;
    struct Type *ptr_to;
};

这里的 ty 可以取 int 类型和“指向某类型的指针”类型这两种值。ptr_to 是在 ty 为“指针类型”时使用的成员，里面保存“指向的那个类型”的 Type 对象指针。例如“指向 int 的指针”在内部可以表示如下。

“指向指向 int 的指针的指针”则表示如下。

这样，编译器内部也能表示复杂类型。

向指针所指向的位置赋值

赋值表达式左边不一定是简单变量名，也可能是 *p=3 这样的表达式。这种表达式也可以用与简单变量赋值相同的基本概念处理：在这种情况下，先生成 p 表示的地址，再把 *p 作为左值编译。

编译表示 *p=3 的语法树时，代码生成器会递归地向下处理语法树。最先被调用的是为了把 *p 作为左值编译的代码生成逻辑。

这部分代码会根据语法树节点类型分支。简单变量时，如前所述输出取得该变量地址的代码；但遇到解引用运算符时需要不同处理。对解引用运算符来说，要把其内部的表达式作为“右值”编译，也就是编译出某个地址计算代码（这个结果不能再继续解引用），并把该地址留在栈上。

做到这里后，就可以编译下面这样的语句。

int x;
int *y;
y = &x;
*y = 3;
return x; // → 3

步骤 19：实现指针的加法和减法

本步骤允许对指针类型的值 p 写 p+1 和 p-5 这样的表达式。表面上这和整数加法相同，实际结构却不同。p+1 并不是给 p 保存的地址加 1，而是表示“指向 p 的下一个元素”。因此实际增加的字节数应当是指针所指向数据类型的宽度。例如 p 指向 int 时，在我们的 ABI 中 p+1 会让地址增加 4；如果 p 是指向指针的指针，则 p+1 会增加 8。

因此，指针加减法需要知道类型大小。当前只有 int 和指针，分别固定为 4 字节和 8 字节，所以可以先把这些值直接写入代码。

这个阶段还没有分配连续内存的方法（因为还没有数组），所以写测试比较困难。这里暂时借助外部编译器：一侧用 malloc 分配内存，另一侧用自己的编译器输出的代码调用该辅助函数。可以像下面这样测试。

int *p;
alloc4(&p, 1, 2, 4, 8);
int *q;
q = p + 2;
*q; // → 4
q = p + 3;
return *q; // → 8

步骤 20：sizeof 运算符

sizeof 看起来像函数，但语法上是一元运算符。在 C 里，大多数运算符都是符号，sizeof 这种由单词组成的运算符是一个例外。

先复习 sizeof 的行为。sizeof 返回其参数表达式的类型在内存中占用的字节数。例如在我们的 ABI 中，如果 x 是 int，sizeof(x) 返回 4；如果 x 是指针，则返回 8。sizeof 的参数可以是任意表达式，例如 sizeof(x+3) 会根据 x+3 这个表达式整体的类型返回 4 或 8。

我们的编译器还没有数组，但在 C 中，sizeof(x) 如果 x 是数组，就会返回整个数组的字节数。例如 int x[10] 时，sizeof(x) 返回 40；int x[5][10] 时，sizeof(x) 返回 200，sizeof(x[0]) 返回 40，sizeof(x[0][0]) 返回 4。

sizeof 的参数只是为了取得类型而写，并不会在运行时实际求值。例如写 sizeof(x[3]) 时，访问 x[3] 这件事不会真的发生。x[3] 这个表达式的类型在编译时已经确定，sizeof(x[3]) 会在编译时被替换为该类型的大小。因此，sizeof 中的具体表达式不会在运行时存在。

下面展示 sizeof 的行为。

int x;
int *y;

sizeof(x); // 4
sizeof(y); // 8

sizeof(x + 3); // 4
sizeof(y + 3); // 8
sizeof(*y); // 4

// sizeof 可以接收任意表达式
sizeof(1); // 4

// 目前 sizeof 的结果是 int 类型，因此等同于 sizeof(int)
sizeof(sizeof(1)); // 4

接下来实现这个 sizeof 运算符。实现它需要修改词法分析器和语法分析器。

首先修改词法分析器，把 sizeof 这个关键字识别为 TK_SIZEOF 类型的标记。

然后修改语法分析器，把 sizeof 替换成 int 类型的常量。加入 sizeof 后的语法如下。这里把 sizeof 定义成一元运算符，优先级与一元正号和一元负号相同；这与 C 的语法一致。

unary="sizeof" unary
| ("+" | "-")? primary

这个语法不仅允许 sizeof(x)，也允许 sizeof x 这样的写法；实际的 C 也一样。

语法分析器遇到 sizeof 运算符时，照常解析它的参数表达式，然后根据解析结果语法树所带的类型，把表达式替换成 int 为 4、指针为 8 这样的数值。由于在语法分析阶段就替换成常量，代码生成器不需要修改。

步骤 21：实现数组

定义数组类型

本步骤实现数组。到这个阶段，还没有出现过无法放入寄存器的大类型数据；数组是第一次出现这种数据。

先整理一下 C 语法中数组的限制。数组不能作为函数参数按值传递，也不能作为函数返回值返回。如果写出这种代码，实际上传递或返回的不是数组本身，而是自动生成的、指向数组首元素的指针。数组之间也不支持直接赋值拷贝（需要用 memcpy 等函数）。

因此，我们不需要在函数和变量之间传递无法放入寄存器的数据。只要能在栈上分配大于 1 字节的内存区域就足够了。

读入如下变量定义。

int a[10];

上面的 a 的类型是数组。该数组长度为 10，元素类型为 int。和指针类型一样，数组类型也可以复杂嵌套，所以和步骤 18 一样，让 ptr_to 指向数组元素类型。类型表示结构体如下。

struct Type {
    enum { INT, PTR, ARRAY } ty;
    struct Type *ptr_to;
    size_t array_size;
};

这里的 array_size 是只在数组类型中使用的字段，保存数组元素个数。

分配数组变量的栈区域并不困难。数组的字节大小等于元素字节大小乘以元素个数。到目前为止，我们为所有变量都分配 1 个字的栈空间；现在只要改成按数组需要的大小分配即可。

实现数组到指针的隐式类型转换

C 在语法上把数组和指针组合得很紧密，看起来几乎像是不区分指针和数组。这很容易让程序员困惑。因此这里先说明数组和指针之间的关系。

首先，C 中数组和指针是完全不同的类型。

指针在 x86-64 上是 8 字节的值类型。像 int 一样，指针也定义了 + 和 - 等运算符（虽然规则不同）。另外，还可以对指针使用一元 * 来访问它所指向的位置。除了一元 * 之外，指针可以看作一种普通类型。

另一方面，数组是不定大小的类型。与指针不同，数组本身几乎没有定义运算符。能直接作用于数组的只有返回数组大小的 sizeof，以及返回数组首元素指针的一元 &。除此之外，没有其他运算符能直接作用于数组。

那么为什么 a[3] 这样的表达式能编译呢？C 把 a[3] 定义为等价于 *(a+3)。可是数组本身并没有定义 + 运算符，不是吗？

这里生效的是“数组到指针的隐式转换”这一语法规则。除非数组作为 sizeof 或一元 & 的操作数，否则数组会被隐式转换为指向其首元素的指针。因此 *(a+3) 表示：先把数组 a 转换为指向首元素的指针，再加 3，然后解引用；其结果就等同于访问数组的第 3 个元素。

C 里并不存在专门的数组访问运算符 []。C 的 [] 只是通过指针访问数组元素的简便记法。

同样，数组作为函数参数传递时会变成指向首元素的指针，也不能直接对数组赋值，原因也在这里。

因此，编译器在实现各个运算符时，需要在适当位置执行数组到指针的类型转换。实现并不难：除了实现 sizeof 和一元 & 时，解析完运算符操作数后，如果其类型是 T 的数组，就把它改为指向 T 的指针。代码生成器对数组类型的值只需要生成“把该值的地址压入栈”的代码即可。

做到这里后，下面这样的代码就可以运行。

int a[2];
*a = 1;
*(a + 1) = 2;
int *p;
p = a;
return *p + *(p + 1) // → 3

步骤 22：实现数组下标

C 把 x[y] 定义为等价于 *(x+y)。因此数组下标实现起来比较简单：在语法分析器中把 x[y] 读成 *(x+y) 即可。例如 a[3] 会变成 *(a+3)。

这个语法还会把 3[a] 展开为 *(3+a)。因此 a[3] 能工作，3[a] 也能工作；而且在 C 中 3[a] 确实是合法表达式。可以亲自试一下。

步骤 23：实现全局变量

要在程序里写字符串字面量，就需要让它存在于栈之外的固定位置。C 中字符串字面量是 char 数组。数组已经实现了，但字符串字面量与普通数组不同：它不是栈上的值，而是位于内存中的固定位置。因此，为了实现字符串字面量，先要加入全局变量。

到目前为止，顶层只允许函数定义。现在修改语法，使顶层也能写全局变量。

变量定义和函数定义长得很像，因此语法分析有一个关键点。例如比较下面 4 个定义。

int *foo;
int foo[10];
int *foo() { }
int foo() { }

上面两个是 foo 变量定义，下面两个是函数定义。这两类定义在读到作为函数名或变量名的标识符之前无法区分，只有再向前看一个标记才能判断。如果下一个标记是 (，就读取函数定义；否则读取变量定义。

解析出的全局变量要登记到名称映射中，使其能被名字查找。解析标识符时，只有在无法解析为局部变量时，才尝试解析为全局变量。这样就能自然实现“局部变量隐藏同名全局变量”的行为。

语法分析器会把局部变量引用和全局变量引用转换为抽象语法树中的不同节点。名称解析在解析阶段完成，因此该阶段也能确定类型。

到目前为止，所有变量都在栈上，因此变量读写通过相对于 RBP 的地址完成。全局变量不是栈上的值，而是位于内存固定位置的值，所以编译时要直接访问该地址。可以参考实际 GCC 的输出。

实现上，局部变量和全局变量是不同实体。只是从外观上看，C 语言把两者抽象成了同样可写的“变量”。

步骤 24：实现字符类型

数组是大于 1 个字的数据类型；字符则是小于 1 个字的数据类型。到本步骤之前，需要写一个接收类型对象并返回该类型字节大小的函数。先加入字符类型，然后修改该函数，使它对字符类型返回 1。

本步骤不需要实现字符字面量（单引号里的字符）。注意这一点，可以把改动控制得很小。

因此，本步骤中的字符本质上只是一个很小的整数类型。读取时可以用 movsx ecx, BYTE PTR [rax] 从 RAX 所指地址读取 1 字节并放入 ECX。如果不需要符号扩展，可以使用 movzx ecx, BYTE PTR [rax]。写入时使用 mov [rax], cl，也就是把源寄存器作为 8 位寄存器使用。

参考实际编译器的输出。

实现本步骤后，下面这样的代码就可以运行。

char x[3];
x[0] = -1;
x[1] = 2;
int y;
y = 4;
return x[0] + y; // → 3

步骤 25：实现字符串字面量

本步骤解析并编译双引号包围的字符串。数组、全局变量和字符类型这些必要部件已经齐备，实现应当比较简单。

首先修改词法分析器：词法分析器看到双引号时，读到下一个双引号为止，生成字符串标记。本步骤不需要实现反斜杠转义等功能。按小步骤前进很重要，所以即使实现看起来简单，也先不要做。

表示字符串字面量数据的汇编不能插在生成 CPU 执行代码的途中。输出汇编时，需要把全局数据和代码分开放置。也就是说，需要先收集代码中出现的所有字符串字面量，再输出它们。为此准备一个保存所有字符串字面量的向量，语法分析器每遇到一个字符串就把它加入向量即可。

参考实际编译器的输出。

到这里已经可以用 printf 输出字符串。使用自己做的编程语言时，正好可以不只写显而易见的测试代码，也试着写一些更有意思的程序。例如可以写一个八皇后问题求解器。人类从发明数字计算机到能开发出这个层级的编程语言，花了几十年；而你现在能在数周内实现到这里，这也是很大的进步。

（调用可变参数函数时，浮点参数的个数应放入 AL。我们的编译器没有浮点数，因此在函数调用前总是把 AL 设为 0。）

步骤 26：从文件读取输入

到目前为止，我们把作为 C 代码的字符串直接作为命令行参数传给编译器。但随着输入变长，接下来应改成普通 C 编译器那样，把命令行参数当作文件名来读取。打开文件、读入其内容，并返回以 \0 结尾的字符串的函数，可以简洁地写成如下形式。

#include <errno.h>
#include <stdio.h>
#include <string.h>

// 返回指定文件的内容
char *read_file(char *path) {
    // 打开文件
    FILE *fp = fopen(path, "r");
    if (!fp)
        error("cannot open %s: %s", path, strerror(errno));

    // 获取文件长度
    if (fseek(fp, 0, SEEK_END) == -1)
        error("%s: fseek: %s", path, strerror(errno));
    size_t size = ftell(fp);
    if (fseek(fp, 0, SEEK_SET) == -1)
        error("%s: fseek: %s", path, strerror(errno));

    // 读入文件内容
    char *buf = calloc(1, size + 2);
    fread(buf, size, 1, fp);

    // 确保文件一定以 "\n\0" 结尾
    if (size == 0 || buf[size -1] != '\n')
        buf[size++] = '\n';
    buf[size] = '\0';
    fclose(fp);
    return buf;
}

为了方便编译器实现，所有行最好都以换行符结束；比起直接以 EOF 结束的数据，以换行符结束的数据更易处理。因此，如果文件最后一个字节不是换行符，这里会自动追加一个换行符。

严格地说，这个函数在不能随机访问的特殊文件上不能工作。例如，把表示标准输入的设备文件 /dev/stdin 指定为文件名时，会看到 /dev/stdin: fseek: Illegal seek 这样的错误。不过在本书的实际用途中，这个函数基本足够。接下来把编译器改成用这个函数读取文件内容，并把读取到的字符串作为输入。

输入文件通常包含多行，所以错误消息函数也要加强。发生错误时，显示输入文件名、错误所在行号和该行内容，使错误消息变成如下形式。

foo.c:10: x = y + + 5; ^ 表达式不合法

显示这种错误消息的函数如下。

// 输入文件名
char *filename;

// 用于报告错误发生位置的函数
// 以下面的格式显示错误消息
//
// foo.c:10: x = y + + 5;
// ^ 表达式不合法
void error_at(char *loc, char *msg) {
    // 取得包含 loc 的行的起点和终点
    char *line = loc;
    while (user_input < line && line[-1] != '\n')
        line--;

    char *end = loc;
    while (*end != '\n')
        end++;

    // 调查找到的行是整体中的第几行
    int line_num = 1;
    for (char *p = user_input; p < line; p++)
        if (*p == '\n')
        line_num++;

    // 将找到的行连同文件名和行号一起显示
    int indent = fprintf(stderr, "%s:%d: ", filename, line_num);
    fprintf(stderr, "%.*s\n", (int)(end - line), line);

    // 用 "^" 标出错误位置，并显示错误消息
    int pos = loc - line + indent;
    fprintf(stderr, "%*s", pos, ""); // 输出 pos 个空格
    fprintf(stderr, "^ %s\n", msg);
    exit(1);
}

这个错误消息输出例程虽然做法简单，但结构上已经可以称得上是比较正式的错误输出格式。

步骤 27：行注释和块注释

我们的编译器逐步演进，已经能写比较正式的代码。接下来会想要注释。本节实现注释。

C 有两种注释。一种是行注释，从 // 到行末都视为注释；另一种是块注释，以 /* 开始、以 */ 结束。块注释中的字符，除表示结束的 */ 这两个字符外，都会被跳过。

在语法上，注释可以当成一个空白字符来处理。因此，在词法分析器中像跳过空白一样跳过注释是自然的实现方式。跳过注释的代码如下。

void tokenize() {
    char *p = user_input;

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

        // 跳过行注释
        if (strncmp(p, "//", 2) == 0) {
            p += 2;
            while (*p != '\n')
                p++;
            continue;
        }

        // 跳过块注释
        if (strncmp(p, "/*", 2) == 0) {
            char *q = strstr(p + 2, "*/");
            if (!q)
                error_at(p, "注释閉");
            p = q + 2;
            continue;
        }
        ...

这里用 C 标准库中的 strstr 函数寻找块注释的结尾。strstr 会在字符串中查找子字符串；找到时返回指向该位置开头的指针，找不到时返回 NULL。

a //*
// */ b

/* /* ... */ */

#if 0 ... #endif

步骤 28：用 C 重写测试

到本步骤之前，你应该已经写了 100 多个 shell 脚本测试。shell 脚本中的每个测试都会启动如果干进程。也就是说，每个测试都会启动自制编译器、汇编器、链接器和测试程序本身。

即使是小程序，启动进程也并不特别快。重复几百次后，总耗时就不可忽视了。现在的测试脚本大概会运行数秒。

另外，过去必须用 shell 脚本写测试，是因为语言本身还不能验证结果是否正确。在计算器级语言阶段，还没有 if 和 == 等功能，无法在语言内部检查计算结果。但现在已经可以做到：比较结果是否正确，错误时显示字符串错误消息并 exit。

因此，本步骤把原来写在 shell 脚本中的测试改写成 C 文件。