chibicc 源码笔记

2024-10-19

(0522e2d) Compile an integer to an exectuable that exits with the given number

  • 输出一个简单的 echo 汇编到tmp.s.
  • Makefile 中的 main.o 默认自动编译，.PHONY声明test和clean为伪目标，防止意外依赖。

(bf7081f) Add + and - operators
(a1ab0ff) Add a tokenizer to allow space characters between tokens

  • 设计 Token 链表结构
typedef enum {
  TK_PUNCT, // Punctuators
  TK_NUM,   // Numeric literals
  TK_EOF,   // End-of-file markers
} TokenKind;

// Token type
typedef struct Token Token;
struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *loc;      // Token location
  int len;        // Token length
};
  • 在 Token 链尾添加一个新的 Token
cur = cur->next = new_token(TK_NUM, p, p);
  • 注意 skip 返回的是符号后的下一个节点，这和 equal 不一样
  • 使用 static 关键字可避免命名冲突并避免为高复用代码反复分配内存

C 语言中的 static 关键字有两个用处，第一种作用和其他现代语言一样， 旨在声明一个可重复使用的值，第二种作用相当于现代语言的 private 关键字， 旨在限定其作用域，由于一些历史原因，C 使用同一个关键字来实现这两种"相反"的用法。

(cc5a6d9) Improve error message
(84cfcaf) Add *, / and ()

  • 设计 AST 节点结构
typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_NUM, // Integer
} NodeKind;

// AST node type
typedef struct Node Node;
struct Node {
  NodeKind kind; // Node kind
  Node *lhs;     // Left-hand side
  Node *rhs;     // Right-hand side
  int val;       // Used if kind == ND_NUM
};
  • 遍历 AST 生成汇编代码
void gen_expr(Node *node) {
  gen_expr(node->rhs); // 递归地生成右子树的汇编代码。
  push();              // 将右子树的计算结果压入栈中。
  gen_expr(node->lhs); // 递归地生成左子树的汇编代码。
  pop("%rdi");         // 从栈顶弹出左子树的计算结果，并将其放入寄存器 %rdi 中。
}
  • 基本流程 Token -> AST -> 汇编代码
  Token *tok = tokenize();        // 生成 Tokens
  Node *node = expr(&tok, tok);   // 构造 AST
  gen_expr(node);                 // 遍历 AST 生成汇编代码
  • 初步定义了三种表达式结构，分别是多项式，单项式和基本单元
// expr = mul ("+" mul | "-" mul)*
// mul = primary ("*" primary | "/" primary)*
// primary = "(" expr ")" | num

(bf9ab52) Add unary plus and minus

  • 新增了 unary 可用于表示负数，new_unary 生成一个只有左子树的单叶节点
// expr = mul ("+" mul | "-" mul)*
// mul = unary ("*" unary | "/" unary)*
// unary = ("+" | "-") unary
//       | primary
// primary = "(" expr ")" | num

(25b4b85) Add ==, !=, <= and >= operators

  • 注意 parse 只有 < 和 <= 即 ND_LT 和 ND_LE 两种节点，> 和 >= 只要交换左子树和右子树即可实现
  • 现在的表达式结构
// expr = equality
// equality = relational ("==" relational | "!=" relational)*
// relational = add ("<" add | "<=" add | ">" add | ">=" add)*
// add = mul ("+" mul | "-" mul)*
// ...

(725badf) Split main.c into multiple small files

  • 拆分后的 main.c 仅记录基本流程
  • chibicc.h 包含所有结构和定义
  • tokenize.c parse.c codegen.c 分别对应三个步骤
  • Makefile 中的 CFLAGS 是 make 的内置规则识别的变量，其中 -std=c11 表示源代码是用最新的 C 标准 C11 编写的；-g 表示输出调试信息；-static 表示静态链接。
  • Makefile 里 SRCS 中使用的 wildcard 是 make 提供的一个函数，它可以替代与参数相匹配的文件名，如 $(wildcard *.c) 可表示 main.c parse.c 和 codegen.c.
  • Makefile 里 OBJS=$(SRCS:.c=.o) 表示将 SRC 中的 .c 替换为 .o, 即 main.o parse.o 和 codegen.o.

(76cae0a) Accept multiple statements separated by semicolons

  • 添加多语句支持
// stmt = expr-stmt
// expr-stmt = expr ";"
// expr = equality
// ...

(1f9f3ad) Support single-letter local variables

  • 新增了两个种类
  ND_ASSIGN,    // =
  ND_VAR,       // Variable
  • 只支持 a 到 z 的 Token
// Identifier
if ('a' <= *p && *p <= 'z') {
  cur = cur->next = new_token(TK_IDENT, p, p + 1);
  p++;
  continue;
}
  • 表达式重新定义为
// expr = assign
// assign = equality ("=" assign)?
  • 获取变量值
// 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) {
    int offset = (node->name - 'a' + 1) * 8;
    printf("  lea %d(%%rbp), %%rax\n", -offset);
    return;
  }

  error("not an lvalue");
}

(482c26b) Support multi-letter local variables

  • 实现变量名词法
// Returns true if c is valid as the first character of an identifier.
static bool is_ident1(char c) {
  return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || c == '_';
}

// Returns true if c is valid as a non-first character of an identifier.
static bool is_ident2(char c) {
  return is_ident1(c) || ('0' <= c && c <= '9');
}

// Identifier
if (is_ident1(*p)) {
  char *start = p;
  do {
    p++;
  } while (is_ident2(*p));
  cur = cur->next = new_token(TK_IDENT, start, p);
  continue;
}

(6cc1c1f) Add “return” statement

  • tokenize 完成后再遍历链表一次，将匹配到的节点类型置为新增的 TK_KEYWORD
static void convert_keywords(Token *tok) {
  for (Token *t = tok; t->kind != TK_EOF; t = t->next)
    if (equal(t, "return"))
      t->kind = TK_KEYWORD;
}
  • 语句结构重新定义为
// stmt = "return" expr ";"
//      | expr-stmt

(18ac283) Add { … }

  • 新增结构 compound-stmt
// stmt = "return" expr ";"
//      | "{" compound-stmt
//      | expr-stmt
  • 在匹配到右括号前将所有 stmt 节点都添加到 compound-stmt 中
compound-stmt = stmt* "}"

(ff8912c) Add null statement
(72b8415) Add “if” statement

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

(f5d480f) Add “for” statement

  • for 的 parse, 对应 for loop 的三段式
if (equal(tok, "for")) {
  Node *node = new_node(ND_FOR);
  tok = skip(tok->next, "(");

  node->init = expr_stmt(&tok, tok);

  if (!equal(tok, ";"))
    node->cond = expr(&tok, tok);
  tok = skip(tok, ";");

  if (!equal(tok, ")"))
    node->inc = expr(&tok, tok);
  tok = skip(tok, ")");

  node->then = stmt(rest, tok);
  return node;
}

(1f3eb34) Add “while” statement

  • while 是 for 的变体，是一个只有 cond 属性的 for 节点
if (equal(tok, "while")) {
  Node *node = new_node(ND_FOR);
  tok = skip(tok->next, "(");
  node->cond = expr(&tok, tok);
  tok = skip(tok, ")");
  node->then = stmt(rest, tok);
  return node;
}

(5b142b1) Add LICENSE and README.md
(3d86277) Add a representative node to each Node to improve error messages
(863e2b8) Add unary & and *

  • 添加 取址符 和 解引用 操作
// unary = ("+" | "-" | "*" | "&") unary
//       | primary
[ Code ] 
#C