阅读 chibicc 笔记

从 chibicc 中学习编译原理和指令集。

1写在前面
2Week 1
3Week 2
4Week 3
5未完待续......

DAY15 - 支持 if 语句

对应提交 72b8415。

今天，我们打算支持下面这种代码：

{ if (0) return 2; return 3; }
{ if (0) { 1; 2; return 3; } else { return 4; } }

Token 流阶段

为了支持 if 语句，我们需要支持更多关键字。在这里，我们需要支持 if 和 else 这两个关键字。所以我们给出函数 is_keyword 如下：

static bool is_keyword(Token *tok) {
  static char *kw[] = {"return", "if", "else"};
  
  for (int i = 0; i < sizeof(kw) / sizeof(*kw); i++)
    if (equal(tok, kw[i]))
      return true;
  return false;
}

这里我们遍历 kw，如果 tok 存在于 kw 中，那么我们就断言传入的 token 是一个关键字。

在 DAY12，我们支持了第一个关键字，即 return，我们在那一天添加了 convert_keywords，用于将一个本应为关键字的 token 转换为 TK_KEYWORD token。现在我们使用 is_keyword 来判断一个 token 是否为关键字，那么我们现在可以让 convert_keywords 直接使用这个函数：

static void convert_keywords(Token *tok) {
  for (Token *t = tok; t->kind != TK_EOF; t = t->next)
    if (is_keyword(t))
      t->kind = TK_KEYWORD;
}

AST 阶段

首先，我们需要支持新的 AST 节点来表示 if 语句。

这里我们支持 ND_IF node，同时我们还扩展了 Node 的定义，为其加上了字段 Node *cond、Node *then 和 Node *els。可以知道，对于 ND_IF node 而言，它存在 cond、then 和 els 这三个 AST 子树。目前 Node 定义如下：

// AST node type
struct Node {
  NodeKind kind; // Node kind
  Node *next;    // Next node

  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side

  // "if" statement
  Node *cond;
  Node *then;
  Node *els;

  // Block
  Node *body;

  Obj *var;      // Used if kind == ND_VAR
  int val;       // Used if kind == ND_NUM
};

然后，我们给出新的 BNF，因为 if 语句也是语句，所以我们更新了 stmt 的定义：

stmt = "return" expr ";"
     | "if" "(" expr ")" stmt ("else" stmt)?
     | "{" compound-stmt
     | expr-stmt

对应的我们需要更新相关代码，来将这部分 token 流转换为对应 AST 节点：

if (equal(tok, "if")) {
  Node *node = new_node(ND_IF);
  tok = skip(tok->next, "(");
  node->cond = expr(&tok, tok);
  tok = skip(tok->next, ")");
  node->then = stmt(&tok, tok);
  if (equal(tok, "else"))
    node->els = stmt(&tok, tok->next);
  *rest = tok;
  return node;
}

整个逻辑非常简单，我们首先构建一个 ND_IF node，然后依次地解析并构建 cond、then 和 els（如果有 else 分支的话）字段。

汇编生成阶段

考虑到如下的代码：

{ if (0) { 1; 2; return 3; } else { return 4; } }

我们希望对应的汇编代码如下（为了可读性我添加了一些空行和注释）：

    .globl main
main:
    ; Alloc the stack frame.
    push %rbp
    mov %rsp, %rbp
    sub $0, %rsp
    
    ; Do the conditional check.
    mov $0, %rax
    cmp $0, %rax
    je .L.else.1
    
    ; If it is true.
    mov $1, %rax
    mov $2, %rax
    mov $3, %rax
    jmp .L.return
    jmp .L.end.1
    
    ; If it is false.
.L.else.1:
    mov $4, %rax
    jmp .L.return
.L.end.1:

.L.return:
    mov %rbp, %rsp
    pop %rbp
    ret

可以看到，生成的汇编代码和给定的输入一一对应。我们跳过了初始化栈和回收栈的相关逻辑，这些逻辑在 DAY11 已经讲过了。而 CMP 比较指令在 DAY7 讨论过了，而 JMP 无条件跳转指令也在 DAY12 讨论过了。这里为了根据比较结果的不同来跳转到不同分支，我们使用了 JE 相关有条件跳转指令。有：

Jcc

执行有条件跳转。常见的条件跳转指令如下：

  • JZ / JE。即 Jump if Zero / Equal。在 ZF = 1 的时候（此时比较结果为相等，或者运算结果为 0）进行跳转。
  • JNZ / JNE。即 Jump if Not Zero / Not Equal。在 ZF = 0 的时候（此时比较结果为不等于）进行跳转。
  • JG / JNLE。即 Jump if Greater。在 ZF = 0 同时 SF = OF 的时候（此时比较结果为大于）进行跳转。
  • JGE / JNL。即 Jump if Greater or Equal。在 SF = OF 的时候（此时比较结果为大于等于）进行跳转。
  • JL / JNGE。即 Jump if Less。在 SF ≠ OF 的时候（此时比较结果为小于）进行跳转。
  • JLE / JNG。即 Jump if Less or Equal。在 ZF = 1 同时 SF ≠ OF 的时候（此时比较结果为小于等于）进行跳转。

可以看到，这整个代码核心部分逻辑有：

  • 首先我们生成 cond 对应的汇编代码，它会将得到的值放入 %rax（这里表达式 0 直接对应 mov $0, %rax 了）；
  • 然后我们通过 CMP 和 JE 指令，使得在 %rax == 0 的时候，跳过一系列逻辑，到达 .L.else.1 标签然后继续运行。
  • 我们生成的时候需要生成 then 控制流相关的汇编代码。同时，在 then 相关代码运行完毕后我们不希望运行 els 对应的代码，所以我们需要使用 jmp .L.end.1 来跳过 els 分支的代码，直接退出 if 语句（虽然 return 生成的 jmp .L.return 会无条件跳转到 .L.end.1，所以这个语句实际上并不会运行，但是我们还是将其加上了）。
  • 最后开始生成 els 相关的汇编代码，它们被生成在 .L.else.1 标签下。最后我们还需要有一个 .L.end.1 标签，表示这个 if 语句的结束。

给出相关汇编代码生成逻辑对应 C 代码如下：

int c = count();
gen_expr(node->cond);
printf("  cmp $0, %%rax\n");
printf("  je  .L.else.%d\n", c);
gen_stmt(node->then);
printf("  jmp .L.end.%d\n", c);
printf(".L.else.%d:\n", c);
if (node->els)
  gen_stmt(node->els);
printf(".L.end.%d:\n", c);
return;

这里 count() 维护一个自增的值。我们使用它来保证生成的标签唯一。

DAY16 - 支持 for 语句

对应提交 f5d480f。

今天我们尝试支持 for 语句，例如：

{ i = 0; j = 0; for (i = 0; i <= 10; i = i + 1) j = i + j; return j }

为了实现我们的目标，我们需要：

  1. 在 token 流生成的过程中，支持标识 for 这个 token 为关键字。
  2. 在 AST 构建的过程中，我们需要使用 ND_FOR node 来表示这个语句。
    • 我们需要让 Node 结构体支持两个新的字段 init 和 inc，用来表示示例中 for 语句的 i = 0 和 i = i + 1，中间的 i <= 10 可以复用字段 cond，而 body 部分可以复用字段 then。
    • 我们不讨论如何生成这个 AST 子树，对于读者来说，我们知道其对应 BNF 为 "for" "(" expr-stmt expr? ";" expr? ")" stmt，应该很容易知道其代码如何编写。
  3. 为 ND_FOR node 生成对应的汇编代码。

这里我们希望上面的示例能生成如下的汇编代码：

    ; ...

    ; i = 0
    lea -16(%rbp), %rax
    push %rax
    mov $0, %rax
    pop %rdi
    mov %rax, (%rdi)

.L.begin.1:
    ; The statment of i <= 10.
    mov $10, %rax
    push %rax
    lea -16(%rbp), %rax
    mov (%rax), %rax
    pop %rdi
    cmp %rdi, %rax
    setle %al
    movzb %al, %rax

    ; Break if !(i <= 10).
    cmp $0, %rax
    je .L.end.1

    ; The statement of j = i + j.
    lea -8(%rbp), %rax
    push %rax
    lea -8(%rbp), %rax
    mov (%rax), %rax
    push %rax
    lea -16(%rbp), %rax
    mov (%rax), %rax
    pop %rdi
    add %rdi, %rax
    pop %rdi
    mov %rax, (%rdi)

    ; The loop.
    jmp .L.begin.1
.L.end.1:
    
    ; ...

这里可以看到 for 循环对应的汇编结构：

  1. 首先是 init 部分。
  2. 然后开始循环（通过 .L.begin.1 标签和程序末尾的 jmp .L.end.1 来标识）。
  3. 每个循环分为三个部分：
    1. 一个是对 cond 的求值。
    2. 二是检验 cond 求职的结果，如果 cond 为假的时候我们会立即退出（通过 je .L.end.1 指令）。
    3. 最后是 body 部分，即 then 字段。在 then 字段对应子树求值完后，我们会通过 jmp .L.begin.1 进入循环。

对应汇编生成逻辑这里也不再展开。

DAY17 - 支持 while 语句

对应提交 1f3eb34。

今天我们支持 while 语句，如下：

{ i = 0; while (i < 10) { i = i + 1; } return i; }

其实在前一天的基础上我们实现这个很容易的。这是因为在语义上 while (cond) { stmt; } 等价于 for (;cond;) { stmt; }。这里给出的汇编结构为：

.L.begin.1:
    ; ... Some code to calculate the cond, and move the value to %rax.

    ; Compare the cond with 0. If cond equals with 0, time to end the loop.
    cmp $0, %rax
    je .L.end.1

    ; ... The code of the loop body.

    jmp .L.begin.1
.L.end.1

整体改动很小，在今天我们就不再详细展开和讨论了。主要变更为：

  • 在 token 生成中，我们支持了 "while" 关键字。
  • 在 AST 生成中，我们直接使用 ND_FOR node 来表达 while 语句。显而易见的，while 语句只是相比而言少了 init 和 inc 部分。

感兴趣的读者可以尝试自己实现，或者参考 chibicc 对应提交。

DAY18 - 支持更好的错误消息

对应提交 3d86277。

今天我们尝试支持更好的错误消息。我们将为 Node 结构体带来新的字段 Token *tok。

现在 Node 结构体如下：

// AST node type
struct Node {
  NodeKind kind; // Node kind
  Node *next;    // Next node
  Token *tok;    // Representative token

  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side

  // "if" or "for" statement
  Node *cond;
  Node *then;
  Node *els;
  Node *init;
  Node *inc;

  // Block
  Node *body;

  Obj *var;      // Used if kind == ND_VAR
  int val;       // Used if kind == ND_NUM
};

现在新建一个 Node 对象需要传入 Token 值了，例如：

static Node *new_node(NodeKind kind, Token *tok) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  node->tok = tok;
  return node;
}

这样，当我们生成汇编的时候我们也能够知道当前处理的 Node 对象到底对应的是源文件的哪一个 token，这使得我们能够使用 error_tok 来展示带有更多上下文的错误消息。例如：

// Compute the absolute address of a given node.
// It's an error if a given node does not reside in memory.
static void gen_addr(Node *node) {
  if (node->kind == ND_VAR) {
    printf("  lea %d(%%rbp), %%rax\n", node->var->offset);
    return;
  }

  error_tok(node->tok, "not an lvalue");
}

这使得对于 3 = 1 这种 C 程序而言，在生成汇编的时候，会出错，并告诉我们 3 不是一个左值。

DAY19 - 支持取地址和解引用

对应提交 863e2b8。

今天我们尝试支持取地址和解引用这两个操作，即：

{ x = 3; y = &x; *y = 5; return x; }

在生成 AST 中，我们只是更改了 unary 函数对应的 BNF（之前我们只支持一元 + 和 - 操作，现在支持更多操作了）：

unary = ("+" | "-" | "*" | "&") unary
      | primary

可以看到生成 AST 操作本身是简单的，这里我们不表。只不过我们需要新的 Node 类型。这里取地址 "&" 对应的节点是 ND_ADDR 节点，而解引用 "*" 对应的节点是 ND_DEREF 节点。

在生成 AST 之后，接下来就是汇编代码的生成了。注意到当我们使用 &a 这个表达式的时候，我们其实希望的是得到 a 对应的地址。假设 a 的 offset 为 -8，那么我们实际上希望生成这样的代码：

lea -8(%rbp), %rax

即将 a 的地址写入到 %rax 寄存器中。

实际上，这正是我们之前支持变量的赋值时调用 gen_addr 产生的汇编代码！比如当我们写表达式 a 的时候，我们原先生成的汇编代码其实本质上会：

  1. 通过 gen_addr 产生的汇编代码来将 a 的地址放进 %rax；
  2. 通过 mov (%rax), %rax，完成解应用，即我们根据 a 的地址，把 a 的值从内存中读取出来，并送入 %rax 中。

所以 a 表达式完全可以视为 *&a，即我们语义上是分为两步来获取 a 的值的。对应的 &a 表达式就是 a 表达式的前半部分，即 gen_addr 部分。而 *a 部分，我们则对应后半部分。

所以有：

// Generate code for a given node.
static void gen_expr(Node *node) {
  switch (node->kind) {
  // ...
  case ND_VAR:
    gen_addr(node);
    printf("  mov (%%rax), %%rax\n");
    return;
  case ND_DEREF:
    gen_expr(node->lhs);
    printf("  mov (%%rax), %%rax\n");
    return;
  case ND_ADDR:
    gen_addr(node->lhs);
    return;
  case ND_ASSIGN:
    gen_addr(node->lhs);
    push();
    gen_expr(node->rhs);
    pop("%rdi");
    printf("  mov %%rax, (%%rdi)\n");
    return;
  // ...
  }
  // ...
}

可以看到，对于解引用而言，我们认为 node->lhs 求值出来是一个地址，然后使用 mov (%rax), %rax 来解引用。而对于求地址而言，我们在直接使用 gen_addr 来获取地址即可。

还有一点是，在今天，我们需要支持 *y = 5 这种表达式。

如果是表达式 y = 5 的话，我们需要（可以参考上面代码中的 case ND_ASSIGN）：

  1. 通过 gen_addr 获取 y 的地址，放入 %rax 中。
  2. 将 5 放入到 %rax 对应的内存中。有 mov %rax, (%rdi)（这里 y 的地址经过 push 和 pop 最终在 %rdi 中，所以这个 mov 将值写入到 y 变量中）。

而对于 *y = 5 这种表达式，我们大体逻辑保存一致，不过 gen_addr 需要处理 ND_VAR 和 ND_DEREF 两种 nodes。而放进 %rax 的值不再是 y 对应的地址，而只是单纯的 y 的值。

我们更新 gen_addr 函数定义如下：

// Compute the absolute address of a given node.
// It's an error if a given node does not reside in memory.
static void gen_addr(Node *node) {
  switch (node->kind) {
  case ND_VAR:
    printf("  lea %d(%%rbp), %%rax\n", node->var->offset);
    return;
  case ND_DEREF:
    gen_expr(node->lhs);
    return;
  }

  error_tok(node->tok, "not an lvalue");
}

可以看到，对于 y = 5 这种表达式，我们会生成类似 lea -8(%rbp), %rax 这种汇编指令来将 y 的地址放入到 %rax 中，而对于 *y = 5 这种表达式，我们则直接将 y 的值放入到 %rax 中。

DAY20 - 支持指针算术

对应提交 a6bc4ab。

今天我们打算支持指针算术：

{ x = 3; y = 5; return *(&x + 1); }

这个是因为我们假设我们的栈如下：

day020-stack

如上，我们假设越先出现的变量越靠近 %rsp（对应的，其越靠近低位），而越后出现的变量越靠近 %rbp（对应的，其越靠近高位）。这里 x 的地址我们能够通过 &x 来表示，而 y 的地址，根据假设应该比 &x 大 8 个字节（我们的栈中的变量都假设它占据 64 位，即 8 个字节）。根据 C 的标准，我们可以通过 &x + 1 来表示，这表示它偏移了 1 * sizeof(x) 个字节。故，上面的表达式应该返回的是 5（当然，永远不要在实际的代码中写这种依赖编译器行为的事情）。

类型系统

这表示即使对于同一个符号 + 而言，但是根据不同的类型我们却有着不同的含义。在普通的算术中，它对应的就是普通的 64 位加法。但是在指针运算中，它表示的则是对地址进行偏移，对于让一个地址加上一个整数（假设为 off），我们实际返回的是新地址，其值为原地址偏移 off * sizeof(typ)。

为此，我们需要在编译期引入类型信息：

typedef enum {
  TY_INT,
  TY_PTR,
} TypeKind;

struct Type {
  TypeKind kind;
  Type *base;
}

extern Type *ty_int;

这里我们引入了结构体 Type 来表示类型信息。目前可以看到我们支持 TY_INT 整数和 TY_PTR 指针类型。对应的，我们在 AST 的构成部分 Node 中加入了字段 Type *ty，这可以表明某个节点的类型信息（如果有的话）：

// AST node type
struct Node {
  NodeKind kind; // Node kind
  Node *next;    // Next node
  Type *ty;      // Type, e.g. int or pointer to int
  Token *tok;    // Representative token
  
  // ...
}

我们新增了一个 type.c 文件，它提供了：

  • ty_int。定义为 Type *ty_int = &(Type){TY_INT}。一个基本的类型，用于表示整数。
  • is_integer。接收 Type * 指针参数，然后判断参数的 kind 是否为 TY_INT，从而判断某个类型是否是整数对应的类型。
  • pointer_to。接收 Type * 指针参数，初始化一个对应的 TY_PTR 的 Type 结构体，并返回对应的 Type * 指针。
  • add_type。接收一个 Node * 指针参数，其表示一个 AST 语法树或者子树，并递归地完成整个语法树或者子树的类型标记。

我们现在仔细阅读 add_type 这个函数。那么有：

void add_type(Node *node) {
  if (!node || node->ty)
    return;
    
  // ...
}

这里我们对于 NULL 或者已经被标注过类型的 AST 而言，会直接返回。然后：

void add_type(Node *node) {
  // ...
  
  add_type(node->lhs);
  add_type(node->rhs);
  add_type(node->cond);
  add_type(node->then);
  add_type(node->els);
  add_type(node->init);
  add_type(node->inc);

  for (Node *n = node->body; n; n = n->next)
    add_type(n);
    
  // ...
}

可以看到，在对当前递归到的节点而言，我们会先递归地完成对子树的类型标记。然后再标记当前节点：

void add_type(Node *node) {
  // ...

  switch (node->kind) {
  case ND_ADD:
  case ND_SUB:
  case ND_MUL:
  case ND_DIV:
  case ND_NEG:
  case ND_ASSIGN:
    node->ty = node->lhs->ty;
    return;
  case ND_EQ:
  case ND_NE:
  case ND_LT:
  case ND_LE:
  case ND_VAR:
  case ND_NUM:
    node->ty = ty_int;
    return;
  case ND_ADDR:
    node->ty = pointer_to(node->lhs->ty);
    return;
  case ND_DEREF:
    if (node->lhs->ty->kind == TY_PTR)
      node->ty = node->lhs->ty->base;
    else
      node->ty = ty_int;
    return;
  }
}

接下来我们就会检查当前 node 的类型（不是所有的 AST 都需要标记类型哦），然后对于需要标注的类型而言，我们根据语义来进行类型的标注。

比如可以看到对于 &a（ND_ADDR 节点），如果我们标注 a 对应的节点的类型为 TY_INT，那么我们就认为 &a 的类型为 TY_PTR，其中 Type 的 base 字段则指向了 a 对应的类型。这样，我们就表示了类型 int *。

对 type.c 有了初步的了解后，我们回过头来尝试解决问题。我们可以看到对于加法（或者减法）来说，我们需要根据不同的类型来决定不同的语义。我们原来使用的是下面的函数调用来构建这个 AST 子树：

new_binary(ND_ADD, node, mul(&tok, tok->next), start)

但是这个函数缺乏我们需要的逻辑（我们需要根据不同的类型，生成不同的 AST 子树），所以我们将其替换为：

new_add(node, mul(&tok, tok->next), start)

对应的，我们希望 new_add 的行为实现为：

  • 对于普通的整数算术而言，和原来的行为保持一致。即创建一个 ND_ADD AST 子树。
  • 对于指针和整数操作的时候（ptr + num 或者 num + ptr 这种），我们同样构建一个 ND_ADD AST 子树，不过它一个子树值为 num * 8，而另一个子树值为 ptr。

对于 new_sub 而言，它和 new_add 类似，不过我们还需要支持指针和指针的运算。同时，我们也不支持 num - ptr 这个操作，而只支持 ptr - num。这里不表。

以 new_add 为例，那么我们有：

// In C, `+` operator is overloaded to perform the pointer arithmetic.
// If p is a pointer, p+n adds not n but sizeof(*p)*n to the value of p,
// so that p+n points to the location n elements (not bytes) ahead of p.
// In other words, we need to scale an integer value before adding to a
// pointer value. This function takes care of the scaling.
static Node *new_add(Node *lhs, Node *rhs, Token *tok) {
  add_type(lhs);
  add_type(rhs);

  // num + num
  if (is_integer(lhs->ty) && is_integer(rhs->ty))
    return new_binary(ND_ADD, lhs, rhs, tok);

  if (lhs->ty->base && rhs->ty->base)
    error_tok(tok, "invalid operands");

  // Canonicalize `num + ptr` to `ptr + num`.
  if (!lhs->ty->base && rhs->ty->base) {
    Node *tmp = lhs;
    lhs = rhs;
    rhs = tmp;
  }

  // ptr + num
  rhs = new_binary(ND_MUL, rhs, new_num(8, tok), tok);
  return new_binary(ND_ADD, lhs, rhs, tok);
}

可以看到，我们会先求 lhs 子树和 rhs 子树的类型，然后根据类型来生成不同的 AST 子树。

DAY21 - 支持关键字 int

对应提交 b4e82cf。

这里我们引入了声明的概念。现在我们在使用变量之前需要先声明一下。比如：

{ int x = 3; int *y = &x; int **z = &y; return **x; }

这里也支持我们知晓变量的类型。在昨天，我们认为所有的变量的类型都是 TY_INT 的，这很明显是不成立的（之后我们可能需要支持其他类型呢）。而今天我们终于可以为变量指定类型了。

对应的，我们对于 Obj 这个结构体（原来这个结构体的作用是表示一个变量），新增了一个字段 ty：

struct Obj {
  Obj *next;
  char *name; // Variable name
  Type *ty;   // Type
  int offset; // Offset from RBP
}

这里就要求了我们在使用变量之前就能够明确知晓这个变量的类型。比如说我们在写 &x 这种表达式之前，x 就必须被声明过了，比如 int x = 3; 这样。

在昨天中，我们在 type.c 中定义了 add_type 函数，它原本是用来给 AST 添加类型信息的，它原先对于 ND_VAR node 而言，会无脑将其标记为 TY_INT 类型的。这是不对的。而现在，这里我们可以使用 ty 字段来标识了：

case ND_VAR:
  node->ty = node->var->ty;
  return;

另外，我们也可以同样地改动 ND_DEREF node 的类型标注过程：

case ND_DEREF:
  if (node->lhs->ty->kind != TY_PTR)
    error_tok(node->tok, "invalid pointer dereference");
  node->ty = node->lhs->ty->base;
  return;

此外，我们还更改了 struct Type 地定义，新加了字段 name：

struct Type {
  TypeKind kind;

  // Pointer
  Type *base;
  
  // Declaration
  Token *name;
};

这个 Type 的 name 指向了对应的变量的 token。比如对于声明 int *a, **b; 而言，b 对应的 Obj 对象的字段 ty 的 name 就指向 b 这个 token。在后文的 AST 阶段中，我们使用这个字段来找到类型对应的变量名字。

Token 流阶段

这里我们主要涉及到两个改动，一个是我们让 int 成为了关键字，这里不表。另外一个是我们提供了函数 consume，如下：

bool consume(Token **rest, Token *tok, char *str) {
  if (equal(tok, str)) {
    *rest = tok->next;
    return;
  }
  *rest = tok;
  return false;
}

可以看到，它接收一个游标 rest（语义是一个指向待消费的 token 的指针）、待消费的 token 以及一个字符串。如果 token 对应的字符串和提供的字符串相等，我们就会消费掉这个 token。比如说我们在消费 int **z 对应的 token 流时，我们可以通过下面的表达式来消费掉 * 这个 token。

consume(&tok, tok, "*")

在 AST 阶段我们使用它来消费 token 流。

AST 阶段

在原来的 BNF 定义中，我们有：

compound-stmt = stmt* "}"
stmt          = "return" expr ";"
              | "if" "(" expr ")" stmt ("else" stmt)?
              | "for" "(" expr-stmt expr? ";" expr? ")" stmt
              | "while" "(" expr ")" stmt
              | "{" compound-stmt
              | expr-stmt

这里我们新加了一个语义 declaration，它被用于声明一个变量：

compound-stmt = (declaration | stmt)* "}"
declaration   = declspec (declarator ("=" expr)? ("," declarator ("=" expr)?)*)? ";"
declspec      = "int"
declarator    = "*"* ident
stmt          = "return" expr ";"
              | "if" "(" expr ")" stmt ("else" stmt)?
              | "for" "(" expr-stmt expr? ";" expr? ")" stmt
              | "while" "(" expr ")" stmt
              | "{" compound-stmt
              | expr-stmt

可以看到：

  • 一个变量的声明 declaration，必先使用 declspec 作为开头，并使用 ";" 分号作为结尾，然后使用逗号分割开一个或者多个变量的声明。声明的变量可以被初始化（这里的 "=" expr），但是这个是可选的。
  • declarator 本身由零个或多个星号和一个变量名来指定。这使得我们可以使用类似 int a, *b; 这种形式，在同一个 declaration 中即声明一个 int 类型的变量，又声明一个 int * 类型的变量。

这里可以看到，在定义 compound-stmt 对应的函数时，我们需要判断下一个语法单位到底是 declaration 还是 stmt，这里可以看到 declaration 的开头必是 "int" 对应的 keyword，而 stmt 则不然，那么有：

static Node *compound_stmt(Token **rest, Token *tok) {
  // ...
  Node *cur = &head;
  while (!equal(tok, "}")) {
    if (equal(tok, "int"))
      cur = cur->next = declaration(rest, tok);
    else
      cur = cur->next = stmt(rest, tok);
  }
}

接下来看 declaration 的对应定义，我们使用这个来表示变量的声明：

// declaration = declspec (declarator ("=" expr)? ("," declarator ("=" expr)?)*)? ";"
static Node *declaration(Token **rest, Token *tok) {
  Type *basety = declspec(&tok, tok);

  Node head = {};
  Node *cur = &head;
  int i = 0;

  while (!equal(tok, ";")) {
    if (i++ > 0)
      tok = skip(tok, ",");

    Type *ty = declarator(&tok, tok, basety);
    Obj *var = new_lvar(get_ident(ty->name), ty);

    if (!equal(tok, "="))
      continue;

    Node *lhs = new_var_node(var, ty->name);
    Node *rhs = assign(&tok, tok->next);
    Node *node = new_binary(ND_ASSIGN, lhs, rhs, tok);
    cur = cur->next = new_unary(ND_EXPR_STMT, node, tok);
  }

  Node *node = new_node(ND_BLOCK, tok);
  node->body = head.next;
  *rest = tok->next;
  return node;
}

这里值得注意的是，这里我们并没有让 declspec 和 declarator 这两个函数返回 Node *（即 AST 子树），相反，我们返回的是 Type *，即类型信息。它的流程为：

  • 首先从 declspec 获取这一行声明的所有变量的基本类型信息。
  • 然后我们开始循环，直到循环到 ";" 这个 token。我们使用 "," token 来分开不同变量的声明。
    • 对于每一个变量，我们从 declarator 来获取这个变量的真正类型信息（见后文）。
    • 我们使用 new_lvar 来定义这个变量。注意到 ty->name 指向了定义这个变量的语句中变量的那个 token，我们会通过 get_ident 来将这个 token 对应的字符串拷贝一份（见后文）。这里值得注意的是，new_lvar 原先只要求接受一个 char *name 参数，但是 Obj 结构体添加了 ty 字段，所以这里我们更改了它，使得它现在还额外接受一个 Type * 指针。
    • 如果有 "=" token 的话，我们会构建一个 AST 子树。即我们将 int a = 5; 视为 int a; a = 5;。注意，前面的声明不会产生对应的 AST，而只是更新符号表，但是后面的初始化我们会构建一个 assign 语法元素对应的 ND_ASSIGN AST 子树，并包裹在 ND_EXPR_STMT 中。
  • 最后我们将构建 ND_BLOCK AST 子树，将这里所有生成的 AST 子树包裹起来。

这里我们使用了很多函数，它们有：

static char *get_ident(Token *tok) {
  if (tok->kind != TK_IDENT)
    error_tok(tok, "expected an identifier");
  return strndup(tok->loc, tok->len);
}

// declspec = "int"
static Type *declspec(Token **rest, Token *tok) {
  *rest = skip(tok, "int");
  return ty_int;
}

// declarator = "*"* ident
static Type *declarator(Token **rest, Token *tok, Type *ty) {
  while (consume(&tok, tok, "*"))
    ty = pointer_to(ty);

  if (tok->kind != TK_IDENT)
    error_tok(tok, "expected a variable name");

  ty->name = tok;
  *rest = tok->next;
  return ty;
}

可以看到我们的 declarator 和 declspec 和之前说的一样，用于返回一个 Type * 指针。比如对于 int *a; 语句而言，我们最终只会得到一个 Type * 指针，而没有对应的 AST，但是这个 Type * 的 name 指向了 a，这使得这边变量对应的 Obj 结构体中知道它是在哪里声明的。

这里的 strndup 是 C 语言标准库中提供的用于复制字符串的函数。

今天，虽然我们提供的语言能力和昨天一致，但是我们让类型系统的基础更扎实了。

上一篇Week 2