函数与局部变量

本章把语言推进到更像 C 的阶段：实现局部变量、函数、返回语句，以及基本控制结构。完成后，编译器就能够处理下面这种带循环和函数调用的程序。

// 对 m 到 n 求和
sum(m, n) {
    acc = 0;
    for (i = m; i <= n; i = i + 1)
        acc = acc + i;
    return acc;
}

main() {
    return sum(1, 10); // 返回 55
}

它还不是完整的 C，但已经具备了“真正程序”的形态：有变量、有循环、有函数调用，也有返回值。

步骤 9：单字符局部变量

到上一章，我们已经做出了能够处理四则运算的语言。本节要继续给这门语言添加变量。具体目标是能编译如下包含变量和多条语句的程序。

a = 3; b = 5 * 6 - 8; a + b / 2;

我们把最后一个表达式的结果作为整个程序的计算结果。与只能计算四则运算的语言相比，这门语言已经开始有“真正语言”的味道了。

本章先说明变量应当如何实现，然后再以增量方式逐步实现变量。

栈上的变量区域

在 C 中，变量存在于内存中。也可以说，变量就是给某个内存地址起了名字。这样我们就不必说“访问内存的 0x6080 地址”，而可以说“访问变量 a”。

不过，函数的局部变量必须在每次函数调用时分别存在。单从实现方便看，似乎可以把“函数 f 的局部变量 a 放在 0x6080 地址”这样写死，但这样在递归调用 f 时就无法工作。为了让每次函数调用都有各自的局部变量，C 会把局部变量放在栈上。

用一个具体例子来看栈的内容。假设函数 f 有局部变量 a 和 b，并且某个其他函数调用了 f。函数调用的 call 指令会把返回地址压入栈，因此在 f 刚被调用时，栈顶保存的就是这个返回地址。除此之外，栈上还可能已有其他值；这里具体内容并不重要，用“⋯⋯”表示。图示如下。

采用这种布局时，用 RSP+8 可以访问 a，用 RSP 可以访问 b。这种为每次函数调用分配的内存区域称为“函数栈帧”或“活动记录”。

RSP 要移动多少字节、分配出的区域里变量按什么顺序摆放，这些都不会被其他函数看到，因此可以按编译器实现的需要自行决定。

基本上，局部变量就是以这种简单方式实现的。

不过，这种方法有一个问题，实际实现时还需要再使用一个寄存器。请回忆一下，在我们的编译器中（其他编译器也类似），函数执行过程中 RSP 可能会变化。9cc 会用 RSP 所指的栈来保存表达式的中间结果，因此 RSP 的值会频繁变化。这样一来，就不能用相对于 RSP 的固定偏移访问 a 和 b。

常见的解决方法是：除 RSP 之外，再准备一个始终指向当前函数栈帧起点的寄存器。这样的寄存器称为“基址寄存器”，其中保存的值称为“基址指针”。在 x86-64 中，惯例上使用 RBP 作为基址寄存器。

函数执行期间，基址指针不能改变；这正是引入基址指针的理由。函数内部可能再调用其他函数，返回后基址指针不能变成别的值。因此每次函数调用都需要保存原来的基址指针，并在返回前恢复。

下面的图展示了使用基址指针时函数调用中的栈状态。假设有一个带局部变量 x 和 y 的函数 g，它调用函数 f。在 g 执行期间，栈如下所示。

这样，a 总是可以通过 RBP-8 访问，b 总是可以通过 RBP-16 访问。为了构造这样的栈状态，编译器应当在函数开头输出如下汇编。

  push rbp
  mov rbp, rsp
  sub rsp, 16

这种由编译器在函数开头固定输出的指令序列称为“序言”（prologue）。这里的 16 只是示例；实际值应当根据每个函数需要的变量数量和大小决定。

从 RSP 指向返回地址的状态开始执行上面的代码，就会得到预期的函数栈帧。下面按每条指令展示栈状态。

函数返回时，要把 RBP 恢复为原来的值，并让 RSP 重新指向返回地址，然后执行 ret（ret 会从栈中弹出地址并跳转到那里）。代码可以简洁地写成如下形式。

  mov rsp, rbp
  pop rbp
  ret

这种由编译器在函数末尾固定输出的指令序列称为“尾声”（epilogue）。

下面展示执行尾声时的栈状态。RSP 以下的区域可以看作无效数据，图中省略。

这样，通过执行尾声，调用方函数 g 的栈状态就被恢复了。call 指令会把下一条指令的地址压入栈；尾声中的 ret 会把该地址弹出并跳转过去，于是从 call 的下一条指令重新开始执行。这正是我们熟悉的函数调用行为。

函数调用和函数局部变量就是这样实现的。

修改词法分析器

既然已经知道变量应当如何实现，接下来就实现它。不过立刻支持任意数量的变量会比较难。本步骤先把变量限制为一个小写字母：变量 a 放在 RBP-8，b 放在 RBP-16，c 放在 RBP-24，也就是说所有单字符变量都始终存在。字母表有 26 个小写字母，因此每次函数调用只要预留 26×8，也就是 208 字节，就能放下全部单字符变量。

先修改词法分析器。除了目前已有的语法元素之外，还要能把一个字符的变量识别出来。为此需要增加一种新的标记类型。变量名可以从 str 成员读取，因此 Token 类型不需要增加新成员。标记类型最终变成如下形式。

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

修改词法分析器时，如果遇到小写英文字母，就生成 TK_IDENT 类型的标记。把下面的 if 语句加入词法分析器即可。

if ('a' <= *p && *p <= 'z') {
    cur = new_token(TK_IDENT, cur, p++);
    cur->len = 1;
    continue;
}

修改语法分析器

递归下降语法分析可以把语法机械地映射为函数调用。因此，在修改语法分析器前，需要先思考“加入变量名（标识符）后的语法应当是什么样”。

标识符记为 ident，它和 num 一样是终结符。变量可以出现在数值能出现的地方，因此原来的 num 可以改为 num | ident。也就是说，变量和数值可以出现在相同位置。

除此之外，还需要加入赋值表达式。变量如果不能赋值就没法使用，所以语法要允许 a=1 这样的表达式。这里也先允许 C 语言中的 a=b=1 这种写法。

再加上用分号分隔的多条语句，新语法如下。

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

请先确认 42;、a=b=2;、a+b; 这样的程序都符合这个语法。然后把目前的语法分析器改成能分析上述语法。这个阶段即使 a+1=5 这样的表达式也能被解析，但无法正确执行；这种语义上不正确的表达式会在下一遍处理中排除。语法分析器的改造没有特别技巧性的新点，和之前一样按语法元素映射到函数即可。

由于可以有多条用分号分隔的表达式，解析结果也需要保存多个节点。这里准备一个全局数组，按顺序保存解析出的节点，最后用 NULL 作为结尾标记。新增代码的一部分如下。

Node *code[100];

Node *assign() {
    Node *node = equality();
    if (consume("="))
        node = new_node(ND_ASSIGN, node, assign());
    return node;
}

Node *expr() {
    return assign();
}

Node *stmt() {
    Node *node = expr();
    expect(";");
    return node;
}

void program() {
    int i = 0;
    while (!at_eof())
        code[i++] = stmt();
    code[i] = NULL;
}

还需要在抽象语法树中表示“局部变量节点”。为此新增局部变量节点类型，并给节点增加必要成员。例如可以这样定义。语法分析器在遇到标识符标记时，会创建并返回 ND_LVAR 类型的节点。

typedef enum {
    ND_ADD, // +
    ND_SUB, // -
    ND_MUL, // *
    ND_DIV, // /
    ND_ASSIGN, // =
    ND_LVAR, // 局部变量
    ND_NUM, // 整数
} NodeKind;

typedef struct Node Node;

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

offset 成员表示局部变量相对于基址指针的偏移量。当前阶段中，变量 a 固定为 RBP-8，b 固定为 RBP-16，因此在语法分析阶段就能根据变量名决定偏移量。下面是读入标识符并返回 ND_LVAR 节点的代码。

Node *primary() {
    ...

    Token *tok = consume_ident();
    if (tok) {
        Node *node = calloc(1, sizeof(Node));
        node->kind = ND_LVAR;
        node->offset = (tok->str[0] -'a'+1) *8;
        return node;
    }

    ...

左值与右值

与赋值以外的二元运算符不同，赋值表达式的左边需要特殊处理。这里先说明这一点。

赋值表达式的左边并不是任何表达式都可以。例如 1=2 不成立，(a+1)=2 也不是合法语句。a=2 这样的赋值可以；以后即使实现了指针和结构体，*p=2 这样的向指针所指位置赋值、a.b=2 这样的向结构体成员赋值，也会被认为是合法的。那么，怎样区分合法与非法的左边表达式呢？

答案很简单：C 中能出现在赋值表达式左边的，基本上是能指定某个内存地址的表达式。

变量存在于内存中，并有地址，因此可以写在赋值左边。类似地，*p 表示指针 p 的值所指向的地址，也可以写在左边。a.b 这样的结构体成员访问，也是在结构体 a 的起始地址上加上成员 b 的偏移量得到一个内存地址，因此也可以写在左边。

另一方面，a+1 这样的表达式结果不是变量，也不能用来指定内存地址。这种临时值实际可能只存在于寄存器中，不一定在内存里；即使曾经出现在内存里，也通常不能通过某个已知变量的固定偏移访问。因此，像 &(a+1) 这样的写法也不允许，编译器会报错。这样的表达式不能作为赋值语句的左边。

能写在左边的值称为“左值”（lvalue，left value），不能写在左边的值称为“右值”（rvalue，right value）。在当前语言中，变量是左值，除此之外的值都是右值。

变量的代码生成可以从左值出发考虑。当变量出现在赋值左边时，先把左边作为左值求值，也就是计算该变量的地址，然后把右边的求值结果存储到该地址。这样就能实现赋值表达式。当变量出现在其他语句中时，同样先计算变量地址，再从该地址加载值，把左值转换为右值。这样就能取得变量的值。

从任意地址加载值的方法

到目前为止，代码生成只访问过栈顶附近的内存；现在需要访问栈上的任意局部变量位置。这里说明一般的内存访问方法。

CPU 不仅能访问栈顶，也能从内存中的任意地址加载值或向任意地址存储值。

从内存加载值使用 mov dst, [src] 这种语法。这条指令表示“把 src 寄存器的值当作地址，从该地址加载值并保存到 dst”。例如 mov rdi, [rax] 会从 RAX 中保存的地址读取值，并设置到 RDI。

向内存存储值使用 mov [dst], src 这种语法。这条指令表示“把 dst 寄存器的值当作地址，把 src 寄存器的值写入那里”。例如 mov [rdi], rax 会把 RAX 的值写入 RDI 所指向的地址。

push 和 pop 是隐式使用 RSP 地址进行内存访问的指令，因此实际上也可以用普通内存访问指令组合来重写。比如 pop rax 等价于下面两条指令。

mov rax, [rsp]
add rsp, 8

而 push rax 等价于下面两条指令。

sub rsp, 8
mov [rsp], rax

它们本质上都是修改 RSP 并读写 RSP 所指向的内存。

修改代码生成器

利用迄今为止的知识，可以修改代码生成器，让它支持包含变量的表达式。本次修改会新增一个“把表达式作为左值求值”的函数。下面代码中的 gen_lval 就是该函数。gen_lval 在节点表示变量时计算变量地址并压入栈；其他情况则报错。这样就能排除 (a+1)=2 这样的表达式。

变量作为右值使用时，先作为左值求值，栈顶会得到地址；然后从该地址加载值。代码如下。

void gen_lval(Node *node) {
    if (node->kind != ND_LVAR)
        error("赋值的左边不是变量");

    printf(" mov rax, rbp\n");
    printf(" sub rax, %d\n", node->offset);
    printf(" push rax\n");
}

void gen(Node *node) {
    switch (node->kind) {
    case ND_NUM:
        printf(" push %d\n", node->val);
        return;
    case ND_LVAR:
        gen_lval(node);
        printf(" pop rax\n");
        printf(" mov rax, [rax]\n");
        printf(" push rax\n");
        return;
    case ND_ASSIGN:
        gen_lval(node->lhs);
        gen(node->rhs);

        printf(" pop rdi\n");
        printf(" pop rax\n");
        printf(" mov [rax], rdi\n");
        printf(" push rdi\n");
        return;
    }

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

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

    switch (node->kind) {
    case'+':
        printf(" add rax, rdi\n");
        break;
    case'-':
        printf(" sub rax, rdi\n");
        break;
    case'*':
        printf(" imul rax, rdi\n");
        break;
    case'/':
        printf(" cqo\n");
        printf(" idiv rdi\n");
    }

    printf(" push rax\n");
}

修改 main 函数

到这里所有部件已经齐备。接下来修改 main 函数，让编译器实际执行起来。

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

    // 进行词法分析和语法分析
    // 结果保存在 code 中
    user_input = argv[1];
    tokenize();
    program();

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

    // 函数序言
    // 为 26 个变量预留空间
    printf(" push rbp\n");
    printf(" mov rbp, rsp\n");
    printf(" sub rsp, 208\n");

    // 从头开始依次生成表达式代码
    for (int i = 0; code[i]; i++) {
        gen(code[i]);

        // 每个表达式的求值结果会留下一个值
        // 不再需要该值，先弹出丢弃
        printf(" pop rax\n");
    }

    // 函数尾声
    // 最后一个表达式的结果会留在 RAX 中，作为返回值
    printf(" mov rsp, rbp\n");
    printf(" pop rbp\n");
    printf(" ret\n");
    return 0;
}

步骤 10：多字符局部变量

上一节中，我们把变量名写死为 1 个字符，并假定从 a 到 z 的 26 个局部变量始终存在。本节支持长度超过 1 个字符的标识符，使下面这样的代码可以编译。

foo = 1;
bar = 2 + 3;
return foo + bar; // 返回 6

变量需要在第一次出现时自动定义。因此，语法分析器在看到每个标识符时，都要判断它是否已经出现过；如果是新的标识符，就要自动在栈上为它分配变量区域。

首先修改词法分析器，让由多个字符组成的标识符也能作为 TK_IDENT 类型的标记读入。

变量用链表表示。每个 LVar 结构体表示一个变量，链表头由 locals 指针保存。代码如下。

typedef struct LVar LVar;

// 局部变量的类型
struct LVar {
    LVar *next; // 下一个变量；末尾为 NULL
    char *name; // 变量名
    int len; // 名称长度
    int offset; // 相对于 RBP 的偏移量
};

// 局部变量
LVar *locals;

语法分析器看到 TK_IDENT 类型标记时，检查该标识符此前是否已经出现。沿着 locals 查找变量名；如果已存在，就使用已有变量的 offset。如果是新变量，就新建一个 LVar，设置新的偏移量，并使用该偏移量。

下面是按变量名查找变量的函数。

// 按变量名查找变量；未找到时返回 NULL。
LVar *find_lvar(Token *tok) {
    for (LVar *var = locals; var; var = var->next)
        if (var->len == tok->len && !memcmp(tok->str, var->name, var->len))
        return var;
    return NULL;
}

把下面的代码加入语法分析器即可。

Token *tok = consume_ident();
if (tok) {
    Node *node = calloc(1, sizeof(Node));
    node->kind = ND_LVAR;

    LVar *lvar = find_lvar(tok);
    if (lvar) {
        node->offset = lvar->offset;
    } else {
        lvar = calloc(1, sizeof(LVar));
        lvar->next = locals;
        lvar->name = tok->str;
        lvar->len = tok->len;
        lvar->offset = locals->offset + 8;
        node->offset = lvar->offset;
        locals = lvar;
    }
    return node;
}

专栏：机器指令的出现频度

观察 9cc 输出的汇编，会发现 mov 和 push 等数据移动指令很多，而 add、mul 这类“真正计算”的指令相对较少。这部分原因是 9cc 没有做优化，会输出一些无用的数据移动指令。不过，即使是优化编译器，最常输出的通常也仍然是数据移动指令。作者在自己的环境中反汇编 /bin 下的全部可执行文件并统计指令数，结果如下图所示。

可以看到，mov 指令实际上占了全部指令的约三成。计算机是处理数据的机器，而数据处理最频繁做的事情之一就是移动数据。把数据移动到合适的位置，是数据处理的本质之一；从这个角度看，mov 指令如此之多其实很自然。

步骤 11：return 语句

本节添加 return 语句，使下面这样的代码可以编译。

a = 3;
b = 5*6-8;
return a + b /2;

return 语句也可以写在程序中途。和普通 C 一样，程序执行到第一个 return 时就会中断并从函数返回。例如下面的程序会返回第一个 return 的值，也就是 5。

return 5;
return 8;

为了实现这个功能，先考虑加入 return 后的语法应当是什么样。到目前为止，语句只是表达式；新语法要允许 return <表达式>; 这种形式。因此新语法如下。

program = stmt*
stmt    = expr ";"
        | "return" expr ";"
        | ...

为实现它，词法分析器、语法分析器和代码生成器都需要稍作修改。

首先，词法分析器要能识别 return 这个标记，并用 TK_RETURN 类型表示。return、while、int 等在语法上具有特殊意义的标记称为关键字。关键字数量有限，因此为每个关键字分配单独类型会比较简单。

只检查剩余输入是否以 return 开头是不够的，否则 returnx 会被错误地切成 return 和 x。因此还必须确认 return 后面的字符不是构成标识符的字符。

下面是判断某个字符是否能构成标识符的函数。

int is_alnum(char c) {
    return('a' <= c && c <= 'z') ||
    ('A' <= c && c <= 'Z') ||
    ('0' <= c && c <= '9') ||
    (c == '_');
}

使用这个函数，在 tokenize 中加入如下代码，就能把 return 词法分析为 TK_RETURN。

if (strncmp(p, "return", 6) == 0 && !is_alnum(p[6])) {
    tokens[i].ty = TK_RETURN;
    tokens[i].str = p;
    i++;
    p += 6;
    continue;
}

接下来修改语法分析器，使它能解析包含 TK_RETURN 的标记列。首先增加表示 return 语句的节点类型 ND_RETURN。然后修改读取语句的函数，使它可以解析 return 语句。和之前一样，语法可以机械地映射为函数调用。新的 stmt 函数如下。

Node *stmt() {
    Node *node;

    if (consume(TK_RETURN)) {
        node = calloc(1, sizeof(Node));
        node->kind = ND_RETURN;
        node->lhs = expr();
    } else {
        node = expr();
    }

    if (!consume(';'))
        error_at(tokens[pos].str, "';'不是标记是");
    return node;
}

这里没有专门写一个构造 ND_RETURN 节点的新函数，而是在现场 malloc 并设置成员。

最后修改代码生成器，让 ND_RETURN 类型节点输出合适的汇编。下面是新的 gen 函数的一部分。

void gen(Node *node) {
    if (node->kind == ND_RETURN) {
        gen(node->lhs);
        printf(" pop rax\n");
        printf(" mov rsp, rbp\n");
        printf(" pop rbp\n");
        printf(" ret\n");
        return;
    }
    ...

上面代码中的 gen(node->lhs) 会输出 return 返回值表达式的代码。该代码会在栈顶留下一个值。后续汇编把这个值弹出到 RAX，然后从函数返回。

到上一章，我们总是在函数末尾输出一条 ret 指令。用本节的方法实现 return 后，每个 return 语句都会输出额外的 return 序列。多输出几条可能执行不到的指令并不会造成问题。此处为了实现简单，允许输出多条 ret。在当前阶段，不必拘泥于这些细节；优先保持实现简单更重要。写复杂代码是一项技能，但“在该简单的时候不把代码写复杂”同样是一项有用技能。

1973 年的 C 编译器

到目前为止，我们一直以增量方式制作编译器。从某种意义上说，这个开发过程也可以说是对 C 历史的复现。

从现代 C 的角度看，有些地方会显得不清楚或不必要地复杂。脱离历史背景，就很难理解这些设计。阅读早期 C 的代码，并了解 C 及其编译器之后的发展，可以帮助理解现代 C 中一些看似费解的地方。

C 最初是在 1972 年作为 Unix 的系统编程语言开始开发的。1972～1973 年，也就是 C 历史极早期的源代码磁带被保留下来，并从中读出了文件后公开在互联网上。下面稍微看一下当时 C 编译器的代码。以下是一个接收 printf 格式字符串并把它显示为编译错误消息的函数。

error(s, p1, p2) {
    extern printf, line, fout, flush, putchar, nerror;
    int f;

    nerror++;
    flush();
    f = fout;
    fout = 1;
    printf("%d: ", line);
    printf(s, p1, p2);
    putchar('\n');
    fout = f;
}

这段代码看起来有些奇怪，像 C 又不像现代 C。阅读这段当时的 C 代码，首先会注意到：和我们编译器的早期阶段一样，函数没有返回值和参数类型。这里的 s 是指向字符串的指针，p1 和 p2 是整数；在当时的机器上它们大小相同，因此可以这样处理。

第 2 行是 error 所引用的全局变量和函数的声明。当时的 C 编译器还没有头文件，也没有 C 预处理器，程序员需要这样手动告诉编译器变量和函数的存在。

和当前的 9cc 一样，当时不会检查函数名是否存在，也不会检查参数类型和个数是否一致。只要按预期个数把参数压到栈上，再跳到函数本体，函数调用就能成立。

fout 是一个全局变量，保存输出目标文件描述符编号。当时还没有 fprintf，为了把字符串输出到标准错误而非标准输出，需要通过全局变量切换输出目标。

error 内部调用了两次 printf。第二次 printf 传入了格式字符串之外的两个值。那么如果错误消息只使用一个值，会怎样呢？

实际上，即使这个 error 函数以少于预期的参数调用，它也能执行。请回想当时还没有参数检查。s、p1、p2 等参数只是栈指针后第 1、第 2、第 3 个字的位置；是否真的传入了对应值，编译器并不知道。printf 只会按照格式字符串中的 %d 和 %s 个数访问额外参数。如果格式字符串只含一个格式指定符，p2 不会被访问，因此参数数量不一致也不会出问题。

可以看到，早期 C 编译器与当前阶段的 9cc 有一些相似之处。

再看另一个代码例子。下面的代码把传入字符串复制到静态分配区域，并返回该区域开头的指针。也就是说，这是一个使用静态区域的 strdup。

copy(s)
char s[]; {
    extern tsp;
    char tsp[], otsp[];

    otsp = tsp;
    while (*tsp++ = *s++);
    return(otsp);
}

当时还没有 int *p 这种声明语法。指针类型被写成 int p[]。函数参数列表和函数体之间插入了变量定义，用来把 s 声明为指针类型。

这个早期 C 编译器还有其他值得注意的地方。

• 此时还没有结构体。
• 还没有 && 和 || 等运算符。当时 & 和 | 在 if 等条件表达式中会根据上下文作为逻辑运算符使用。
• += 等运算符写作 =+。这种语法会造成问题：例如想赋值 -1 时，如果写成 i =- 1，可能会被解释为把 i 递减。
• 整数类型只有 char 和 int，还没有 short 和 long。也没有能描述“函数指针数组”等复杂类型的声明语法。

如上所述，20 世纪 70 年代初的 C 缺少很多功能。尽管如此，这个 C 编译器从源代码可知是用 C 写的。也就是说，在连结构体都没有的时代，C 已经完成了自举。

观察旧源代码，也能推测 C 的某些语法为什么会成为现在这样。extern、auto、int、char 后面总是变量名，这样的变量定义语法便于解析。指针用 [] 表示，也只是紧跟在变量名之后，解析起来很简单。但也能看出，这种早期编译器所采用的方向一路发展下来，形成了现代 C 中一些不必要复杂的形式。

也就是说，Dennis Ritchie 在 1973 年前后与 Unix 和 C 的共同开发中采用了增量式开发。他一边发展 C，一边用 C 编写它的编译器。现代 C 并不是从一开始就有一个特别明确的最终形态；它只是 Dennis Ritchie 在某个时间点觉得“语言功能已经足够”之后逐步定型的结果。

我们的编译器也不需要一开始就追求最终形态。所谓 C 的完成形并没有特别神圣的意义，没有必要一开始就奔着那里去。每个阶段都让语言拥有合理的功能集合，然后继续开发，最终到达 C。这正是原始 C 编译器曾经采用过的正统开发方式。可以有信心地继续推进。

步骤 12：添加控制语句

从这里开始的章节仍处于写作中。前面的章节写得相对细致，但从这里往后还没有达到完全公开成品的水平。尽管如此，能读到这里的读者应当已经可以自行补全很多细节；也有人希望获得后续推进的路线图，因此这里仍然公开。

本节把 if、if ... else、while、for 等控制结构加入语言。这些控制结构乍看复杂，但如果直接编译为汇编，实现并不难。

汇编本身没有专门支持 C 控制结构的机制。C 的控制结构在汇编中会被表示为分支指令和标签。这含义着控制结构可以改写为使用 goto 的代码。既然人类可以手工把控制结构改写成 goto，编译器也就可以机械地做同样的转换。

除此之外还有 do ... while、goto、continue、break 等控制语句，但当前阶段不需要实现。

加入 if、while、for 后的新语法如下。

program = stmt*
stmt    = expr ";"
        | "if" "(" expr ")" stmt ("else" stmt)?
        | "while" "(" expr ")" stmt
        | "for" "(" expr? ";" expr? ";" expr? ")" stmt
        | ...

读取 expr? ";" 时，只要向前看一个标记：如果下一个标记是 ;，就说明表达式不存在；否则读取表达式即可。

if (A) B 可以编译成下面这样的汇编。

编译 A 得到的代码  // 结果应在栈顶
pop rax
cmp rax, 0
je .LendXXX
编译 B 得到的代码
.LendXXX:

也就是说，if (A) B 等价于下面的形式。

if (A == 0)
    goto end;
B;
end:

其中 XXX 可以是连续编号等，用来保证所有标签唯一。

if (A) B else C 可以编译成下面这样的汇编。

编译 A 得到的代码  // 结果应在栈顶
pop rax
cmp rax, 0
je .LelseXXX
编译 B 得到的代码
jmp .LendXXX
.LelseXXX:
编译 C 得到的代码
.LendXXX:

也就是说，if (A) B else C 等价于下面的形式。

if (A == 0)
    goto els;
B;
goto end;
els:
C;
end:

读取 if 语句时，向前看一个标记，检查是否有 else。如果有，就按 if ... else 编译；否则按不带 else 的 if 编译。

while (A) B 可以编译成下面这样。

.LbeginXXX:
编译 A 得到的代码
pop rax
cmp rax, 0
je .LendXXX
编译 B 得到的代码
jmp .LbeginXXX
.LendXXX:

也就是说，while (A) B 等价于下面的代码。

begin:
if (A == 0)
    goto end;
B;
goto begin;
end:

for (A; B; C) D 可以编译成下面这样。

编译 A 得到的代码
.LbeginXXX:
编译 B 得到的代码
pop rax
cmp rax, 0
je .LendXXX
编译 D 得到的代码
编译 C 得到的代码
jmp .LbeginXXX
.LendXXX:

支持 for (A; B; C) D 的 C 代码如下。

A;
begin:
if (B == 0)
    goto end;
D;
C;
goto begin;
end:

另外，以 .L 开头的标签会被汇编器特殊识别为自动的文件作用域标签。文件作用域标签只能从同一个文件中引用，不能从其他文件引用。因此，编译器为 if 和 for 生成以 .L 开头的标签时，不必担心与其他文件中的标签冲突。

可以用 cc 编译小循环，参考它输出的汇编来实现。

步骤 13：代码块

本步骤支持在 { ... } 之间写多条语句的“块”（block）。块的正式名称是“复合语句”（compound statement），但名称较长，通常直接称为块。

块可以把多条语句当作一条语句使用。在上一步实现的 if 和 while 中，条件成立时只能执行一条语句；实现块之后，就能像 C 一样在后面写 {} 并放入多条语句。

函数体其实也是块。从语法上讲，函数体必须是块。函数定义中的 { ... }，与写在 if 和 while 后面的 { ... } 语法相同。

加入块后的语法如下。

program = stmt*
stmt    = expr ";"
        | "{" stmt* "}"
        | ...

这个语法表示：当 stmt 以 { 开始时，在出现 } 之前可以读取 0 个或多个 stmt。为了分析 stmt* "}"，可以在看到 } 前反复调用 stmt，并把结果作为向量返回。

为实现块，需要增加表示块的节点类型 ND_BLOCK。表示节点的结构体 Node 也要增加用于保存块内表达式/语句向量的成员。代码生成器遇到 ND_BLOCK 时，按顺序生成其中所有语句的代码。另外，每条语句会留下一个值，别忘了每次都把它弹出。

步骤 14：支持函数调用

本步骤的目标是识别 foo() 这样的无参数函数调用，并把它编译为 call foo。

加入函数调用后的语法如下。

...
primary = num
| ident ("(" ")")?
| "(" expr ")"

读到 ident 后，需要向前看一个标记，判断该标识符是变量名还是函数名。

测试时可以准备一个包含 int foo() { printf("OK\n"); } 之类内容的 C 文件，用 cc -c 编译为目标文件，再与自己编译器的输出链接。这样可以确认自己的代码能调用外部函数。

能执行后，再支持 foo(3, 4) 这样的函数调用。此时不检查参数个数和类型，只要按顺序求值参数，把参数通过栈临时保存，再按 x86-64 ABI 规定的顺序复制到寄存器中并执行 call。暂时不支持超过 6 个参数。

测试方式与上面类似，可以准备 int foo(int x, int y) { printf("%d\n", x + y); } 这样的函数，链接后执行确认。

x86-64 函数调用 ABI 还有一个注意点：调用函数前，RSP 必须是 16 的倍数。push 和 pop 以 8 字节为单位修改 RSP，因此执行 call 前 RSP 不一定是 16 的倍数。如果不满足这个约束，某些假定 RSP 为 16 倍数的函数可能以约一半概率崩溃。调用函数前需要调整 RSP，使其成为 16 的倍数。

步骤 15：支持函数定义

到这里终于可以实现函数定义了。C 的完整函数定义语法比较麻烦，因此这里不全部实现。当前语言还没有 int 类型，所以不实现 int foo(int x, int y) { ... }，而是实现省略类型名的 foo(x, y) { ... }。

在被调用方内部，需要能通过 x、y 等名称访问参数；但按现状，值只是通过寄存器传入，无法用名称访问。解决办法是把 x 和 y 当作局部变量存在，在函数序言中把寄存器中的值写入这些局部变量对应的栈上区域。之后就不需要特别区分参数和局部变量。

到目前为止，我们相当于隐式地把整个输入包在 main() { ... } 中执行。现在废除这一点，要求所有代码都写在某个函数中。解析顶层时，先读取函数名，接着读取参数列表，然后读取函数体；按这个顺序简单读取即可。

本步骤完成后，就可以用递归计算并显示斐波那契数列，这会很有趣。

二进制层面的接口

C 语言规范规定的是源代码层面的规格。例如哪些写法可以定义函数、哪个文件包含哪些函数声明等。一份符合标准的源代码怎样转换为机器码，并不由 C 语言标准规定。C 标准并不以特定指令集为前提，这是自然的。

因此乍看似乎还需要另一个机器码层面的规范。实际上，各个平台会在一定程度上规定这样的规范，这种规范称为 ABI（Application Binary Interface，应用二进制接口）。

本书迄今为止已经说明过：函数调用方要按特定顺序把参数放入寄存器，返回值放入 RAX。这类函数调用方规则称为“函数调用规约”（function calling convention）。函数调用规约是 ABI 的一部分。

C 语言 ABI 除了参数和返回值的传递方式，还包括下面这些内容。

• 函数调用时哪些寄存器会被修改、哪些寄存器不会被修改（例如 RBP 必须在返回前恢复原值）。
• int 和 long 等类型的大小。
• 结构体布局规则，也就是结构体成员在内存中如何实际排列。
• 位字段布局规则，例如位字段从最低位开始排列还是从最高位开始排列。

ABI 不是软件层面的任意约定，而是为了让不同编译器生成的代码能互相调用而必须遵守的规则。通常 CPU 厂商和 OS 厂商会为平台定义标准 ABI。x86-64 上广泛使用的 ABI 主要有两种：Unix/macOS 使用的 System V ABI，以及 Windows 使用的 Microsoft ABI。这两种调用规约没有技术上的必然性差异，只是由不同的人分别制定。

到目前为止，我们已经让自制编译器调用了由其他编译器编译的函数。这之所以可行，是因为我们的 C 编译器遵守了与其他编译器相同的 ABI。