chibiccを読む～Cコンパイラコードリーディング～ ステップ7

トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ7に該当
github.com

今回作成するコンパイラ

比較演算子(<、<=、>、>=、==、!= を扱えるコンパイラを作成する)

コンパイラのソースコード

https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c

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

//
// Tokenizer
//

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer 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 *str;      // Token string
  int len;        // Token length
};

// Input program
char *user_input;

// Current token
Token *token;

// Reports an error and exit.
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Reports an error location and exit.
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, ""); // print pos spaces.
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// Consumes the current token if it matches `op`.
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;
}

// Ensure that the current token is `op`.
void expect(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    error_at(token->str, "expected \"%s\"", op);
  token = token->next;
}

// Ensure that the current token is TK_NUM.
int expect_number() {
  if (token->kind != TK_NUM)
    error_at(token->str, "expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

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

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str, int len) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  tok->len = len;
  cur->next = tok;
  return tok;
}

bool startswith(char *p, char *q) {
  return memcmp(p, q, strlen(q)) == 0;
}

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Multi-letter punctuator
    if (startswith(p, "==") || startswith(p, "!=") ||
        startswith(p, "<=") || startswith(p, ">=")) {
      cur = new_token(TK_RESERVED, cur, p, 2);
      p += 2;
      continue;
    }

    // Single-letter punctuator
    if (strchr("+-*/()<>", *p)) {
      cur = new_token(TK_RESERVED, cur, p++, 1);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p, 0);
      char *q = p;
      cur->val = strtol(p, &p, 10);
      cur->len = p - q;
      continue;
    }

    error_at(p, "invalid token");
  }

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

//
// Parser
//

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_EQ,  // ==
  ND_NE,  // !=
  ND_LT,  // <
  ND_LE,  // <=
  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
};

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

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

Node *new_num(int val) {
  Node *node = new_node(ND_NUM);
  node->val = val;
  return node;
}

Node *expr();
Node *equality();
Node *relational();
Node *add();
Node *mul();
Node *unary();
Node *primary();

// expr = equality
Node *expr() {
  return equality();
}

// equality = relational ("==" relational | "!=" relational)*
Node *equality() {
  Node *node = relational();

  for (;;) {
    if (consume("=="))
      node = new_binary(ND_EQ, node, relational());
    else if (consume("!="))
      node = new_binary(ND_NE, node, relational());
    else
      return node;
  }
}

// relational = add ("<" add | "<=" add | ">" add | ">=" add)*
Node *relational() {
  Node *node = add();

  for (;;) {
    if (consume("<"))
      node = new_binary(ND_LT, node, add());
    else if (consume("<="))
      node = new_binary(ND_LE, node, add());
    else if (consume(">"))
      node = new_binary(ND_LT, add(), node);
    else if (consume(">="))
      node = new_binary(ND_LE, add(), node);
    else
      return node;
  }
}

// add = mul ("+" mul | "-" mul)*
Node *add() {
  Node *node = mul();

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

// mul = unary ("*" unary | "/" unary)*
Node *mul() {
  Node *node = unary();

  for (;;) {
    if (consume("*"))
      node = new_binary(ND_MUL, node, unary());
    else if (consume("/"))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
  }
}

// unary = ("+" | "-")? unary
//       | primary
Node *unary() {
  if (consume("+"))
    return unary();
  if (consume("-"))
    return new_binary(ND_SUB, new_num(0), unary());
  return primary();
}

// primary = "(" expr ")" | num
Node *primary() {
  if (consume("(")) {
    Node *node = expr();
    expect(")");
    return node;
  }

  return new_num(expect_number());
}

//
// Code generator
//

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;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");
}

int main(int argc, char **argv) {
  if (argc != 2)
    error("%s: invalid number of arguments", argv[0]);

  // Tokenize and parse.
  user_input = argv[1];
  token = tokenize();
  Node *node = expr();

  // Print out the first half of assembly.
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // Traverse the AST to emit assembly.
  gen(node);

  // A result must be at the top of the stack, so pop it
  // to RAX to make it a program exit code.
  printf("  pop rax\n");
  printf("  ret\n");
  return 0;
}

追加・修正されたコンパイラのソースコード

Token構造体

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR25
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L25

struct Token {
  TokenKind kind; // Token kind
  Token *next;    // Next token
  int val;        // If kind is TK_NUM, its value
  char *str;      // Token string
  int len;        // Token length
};

トークンの文字列の長さを記録するためにlenメンバを追加します。

tokenize関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR115
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L115

// Tokenize `user_input` and returns new tokens.
Token *tokenize() {
  char *p = user_input;
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

    // Multi-letter punctuator
    if (startswith(p, "==") || startswith(p, "!=") ||
        startswith(p, "<=") || startswith(p, ">=")) {
      cur = new_token(TK_RESERVED, cur, p, 2);
      p += 2;
      continue;
    }

    // Single-letter punctuator
    if (strchr("+-*/()<>", *p)) {
      cur = new_token(TK_RESERVED, cur, p++, 1);
      continue;
    }

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p, 0);
      char *q = p;
      cur->val = strtol(p, &p, 10);
      cur->len = p - q;
      continue;
    }

    error_at(p, "invalid token");
  }

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

文字列の先頭アドレスを取得する(変更なし)

  char *p = user_input;

トークンからなる連結リストのヘッダーを作成する(変更なし)

  Token head;
  head.next = NULL;
  Token *cur = &head;

空白文字の場合(変更なし)

  while (*p) {
    // Skip whitespace characters.
    if (isspace(*p)) {
      p++;
      continue;
    }

複数文字の記号の場合

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR115
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L115

    // Multi-letter punctuator
    if (startswith(p, "==") || startswith(p, "!=") ||
        startswith(p, "<=") || startswith(p, ">=")) {
      cur = new_token(TK_RESERVED, cur, p, 2);
      p += 2;
      continue;
    }

条件式にある4つのstartwith関数のいずれかがtrueを戻り値とした場合→文字p*が、"=="、"!="、"<="、">=" のいずれかの文字列の一部だった場合は、new_token関数を呼び出して、記号を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
次の文字を取得するためにchar型へのポインタpを2バイト分(2文字分)インクリメントしてからwhile文のループを継続します。

1文字の記号の場合

    // Single-letter punctuator
    if (strchr("+-*/()<>", *p)) {
      cur = new_token(TK_RESERVED, cur, p++, 1);
      continue;
    }

str関数の第一引数の文字列に”<”と” >”を追加します。

数字の場合

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR132
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L132

    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p, 0);
      char *q = p;
      cur->val = strtol(p, &p, 10);
      cur->len = p - q;
      continue;
    }

strol関数を呼び出す前に文字のアドレス値をchar型へのポインタqに保存し、文字列の長さp - qを生成されたトークンに記録します。

その他の場合(変更なし)

    error_at(p, "invalid token");

トークン列の終端を表すトークンを生成する(変更なし)

  new_token(TK_EOF, cur, p, 0);

連結リストの先頭トークンを戻り値としてリターンする(変更なし)

return head.next;

new_token関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR92
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L92

// Create a new token and add it as the next token of `cur`.
Token *new_token(TokenKind kind, Token *cur, char *str, int len) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  tok->len = len;
  cur->next = tok;
  return tok;
}

トークンを生成する(変更なし)

  Token *tok = calloc(1, sizeof(Token));

生成されたトークンのメンバに値を設定する

  tok->kind = kind;
  tok->str = str;
  tok->len = len;

kindの値(トークンの種類、トークンの型)、strの値(トークンの文字列)、lenの値(トークンの文字列の長さ)を生成されるトークン構造体のメンバに設定します。

生成されたトークンを連結リストに追加する(変更なし)

  cur->next = tok

生成されたトークンを戻り値としてリターンする(変更なし)

  return tok;

startswith関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR97
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L97

bool startswith(char *p, char *q) {
  return memcmp(p, q, strlen(q)) == 0;
}

startswith関数は、引数pが指定する文字列と引数qが指定する文字列が同じであるかを判定します。
引数pが指定する文字列と引数qが指定する文字列が同じ場合は、trueが戻り値となります。
引数pが指定する文字列と引数qが指定する文字列が異なる場合は、falseが戻り値となります。

memcmp関数は、第一引数のアドレスから配置されているデータと第二引数のアドレスから配置されているデータを第三引数で指定されたバイトサイズ分だけ比較します。
第一引数のアドレスから配置されているデータ > 第二引数のアドレスから配置されているデータの場合は、戻り値は正の値、
第一引数のアドレスから配置されているデータ = 第二引数のアドレスから配置されているデータの場合は、戻り値は0の値、
第一引数のアドレスから配置されているデータ < 第二引数のアドレスから配置されているデータの場合は、戻り値は負の値、
になります。

consume関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR58
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L58

// Consumes the current token if it matches `op`.
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;
}

文字ではなく文字列を扱えるように改良します。

現在着目しているトークンの文字列を調べる

  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    return false;

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列長と引数opで指定された文字列長が異なる場合(strlen(op)の戻り値とstrlen(op)の戻り値が異なる場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合(memcmp(token->str, op, token->len)の戻り値が0以外の値になる場合)は、戻り値をflaseとしてリターンします。

strlen関数は、引数が指定する文字列の長さ(バイトサイズ)を戻り値として取得します。

memcmp関数は、第一引数のアドレスから配置されているデータと第二引数のアドレスから配置されているデータを第三引数で指定されたバイトサイズ分だけ比較します。
第一引数のアドレスから配置されているデータ > 第二引数のアドレスから配置されているデータの場合は、戻り値は正の値、
第一引数のアドレスから配置されているデータ = 第二引数のアドレスから配置されているデータの場合は、戻り値は0の値、
第一引数のアドレスから配置されているデータ < 第二引数のアドレスから配置されているデータの場合は、戻り値は負の値、
になります。

着目しているトークンを次のトークンに変更する(変更なし)

  token = token->next;
  return true;

expect関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR67
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L67

// Ensure that the current token is `op`.
void expect(char *op) {
  if (token->kind != TK_RESERVED || strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    error_at(token->str, "expected \"%s\"", op);
  token = token->next;
}

文字ではなく文字列を扱えるように改良します。

現在着目しているトークンの文字列を調べる

  if (token->kind != TK_RESERVED || strlen(op) != strlen(op) ||
      memcmp(token->str, op, token->len))
    error_at(token->str, "expected \"%s\"", op);

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列長と引数opで指定された文字列長が異なる場合(strlen(op)の戻り値とstrlen(op)の戻り値が異なる場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合(memcmp(token->str, op, token->len)の戻り値が0以外の値になる場合)は、error関数を呼び出して、メッセージを出力してから処理を終了します。

strlen関数は、引数が指定する文字列の長さ(バイトサイズ)を戻り値として取得します。

memcmp関数は、第一引数のアドレスから配置されているデータと第二引数のアドレスから配置されているデータを第三引数で指定されたバイトサイズ分だけ比較します。
第一引数のアドレスから配置されているデータ > 第二引数のアドレスから配置されているデータの場合は、戻り値は正の値、
第一引数のアドレスから配置されているデータ = 第二引数のアドレスから配置されているデータの場合は、戻り値は0の値、
第一引数のアドレスから配置されているデータ < 第二引数のアドレスから配置されているデータの場合は、戻り値は負の値、
になります。

着目しているトークンを次のトークンに変更する(変更なし)

token = token->next;

NodeKind

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR154
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L154

typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_EQ,  // ==
  ND_NE,  // !=
  ND_LT,  // <
  ND_LE,  // <=
  ND_NUM, // Integer
} NodeKind;

==、!=、<、<=にそれぞれ対応するノードの型(ノードの種類)を追加します。
>、>=、に対応するノードの型は定義せず、 < や <= に対応するノードを生成するときに子ノードを入れ替えることで、< や <= の処理を再現します(詳細はrelational関数、gen関数)。

expr関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR197
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L197

// expr = equality
Node *expr() {
  return equality();
}

expr関数は、生成規則 expr = equality に基づいて、抽象構文木のノードを生成します。

equality

  return equality();

equality関数を呼び出して、抽象構文木のノードを生成します。
生成したノードのアドレスが戻り値となります。

equality関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR202
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L202

// equality = relational ("==" relational | "!=" relational)*
Node *equality() {
  Node *node = relational();

  for (;;) {
    if (consume("=="))
      node = new_binary(ND_EQ, node, relational());
    else if (consume("!="))
      node = new_binary(ND_NE, node, relational());
    else
      return node;
  }
}

equality関数は、生成規則 equality = relational ("==" relational | "!=" relational)* に基づいて、抽象構文木のノードを生成します。

relational

  Node *node = relational();

「"=="とrelational、または、"!="とrelational」を0回以上

  for (;;) {
    if (consume("=="))
      node = new_binary(ND_EQ, node, relational());
    else if (consume("!="))
      node = new_binary(ND_NE, node, relational());
    else
      return node;
  }

relational関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR216
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L216

// relational = add ("<" add | "<=" add | ">" add | ">=" add)*
Node *relational() {
  Node *node = add();

  for (;;) {
    if (consume("<"))
      node = new_binary(ND_LT, node, add());
    else if (consume("<="))
      node = new_binary(ND_LE, node, add());
    else if (consume(">"))
      node = new_binary(ND_LT, add(), node);
    else if (consume(">="))
      node = new_binary(ND_LE, add(), node);
    else
      return node;
  }
}

relational関数は、生成規則 relational = add ("<" add | "<=" add | ">" add | ">=" add)* に基づいて、抽象構文木のノードを生成します。

add

  Node *node = add();

add関数を呼び出して、抽象構文木のノードを生成します。

「"<"とadd または "<="とadd または ">"とadd または ">="とadd」を0回以上

  for (;;) {
    if (consume("<"))
      node = new_binary(ND_LT, node, add());
    else if (consume("<="))
      node = new_binary(ND_LE, node, add());
    else if (consume(">"))
      node = new_binary(ND_LT, add(), node);
    else if (consume(">="))
      node = new_binary(ND_LE, add(), node);
    else
      return node;
  }

consume("<")の戻り値がtrueとなる場合→着目しているトークンが < の場合は、new_binary関数を呼び出して、< 記号を表現するノードを生成します。< 記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのadd関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のadd関数で生成されたノードを子ノードとして持ちます。

consume("<=")の戻り値がtrueとなる場合→着目しているトークンが <= の場合は、new_binary関数を呼び出して、<= 記号を表現するノードを生成します。<= 記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのadd関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のadd関数で生成されたノードを子ノードとして持ちます。

consume(">")の戻り値がtrueとなる場合→着目しているトークンが > の場合は、new_binary関数を呼び出して、< 記号を表現するノードを生成します。
ここでは、> 記号を表現するノードを生成せずに、第二引数と第三引数を入れ替えることで、> の処理を再現します。

consume(">=")の戻り値がtrueとなる場合→着目しているトークンが >= の場合は、new_binary関数を呼び出して、<= 記号を表現するノードを生成します。
ここでは、>= 記号を表現するノードを生成せずに、第二引数と第三引数を入れ替えることで、>= の処理を再現します。

上記以外の場合は、最後に生成されたノードのアドレスを戻り値としてリターンします。

add関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR239
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L239

// add = mul ("+" mul | "-" mul)*
Node *add() {
  Node *node = mul();

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

add関数は、生成規則 add = mul ("+" mul | "-" mul)* に基づいて、抽象構文木のノードを生成します。

mul

  Node *node = mul();

mul関数を呼び出して、抽象構文木のノードを生成します。

「"+"とmul または "-"とmul」を0回以上

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

consume("+")の戻り値がtrueとなる場合→着目しているトークンが + の場合は、new_binary関数を呼び出して、加算記号を表現するノードを生成します。この加算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのmul関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。

consume("-")の戻り値がtrueとなる場合→着目しているトークンが - の場合は、new_binary関数を呼び出して、減算記号を表現するノードを生成します。この減算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのprimary関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。

上記以外の場合は、最後に生成されたノードのアドレスを戻り値としてリターンします。

mul関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR253
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L253

// mul = unary ("*" unary | "/" unary)*
Node *mul() {
  Node *node = unary();

  for (;;) {
    if (consume("*"))
      node = new_binary(ND_MUL, node, unary());
    else if (consume("/"))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
  }
}

unary(変更なし)

  Node *node = unary();

「"*"とprimary または "/"とprimary」を0回以上

  for (;;) {
    if (consume("*"))
      node = new_binary(ND_MUL, node, unary());
    else if (consume("/"))
      node = new_binary(ND_DIV, node, unary());
    else
      return node;
   }

consume関数の引数を文字から文字列に変更します。

unary関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR265
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L265

Node *unary() {
  if (consume("+"))
    return unary();
  if (consume("-"))
    return new_binary(ND_SUB, new_num(0), unary());
  return primary();
}

unary関数は、生成規則 unary =("+" | "-")? unary | primaryに基づいて、抽象構文木のノードを生成します。

「"+"または"-" を0回か1回」とunaray

  if (consume("+"))
    return unary();
  if (consume("-"))
    return new_binary(ND_SUB, new_num(0), unary());

consume関数の引数を文字から文字列に変更します。

primary(変更なし)

 return primary();

primary関数

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR274
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L274

// primary = "(" expr ")" | num
Node *primary() {
  if (consume("(")) {
    Node *node = expr();
    expect(")");
    return node;
  }

  return new_num(expect_number());
}

primary関数は、生成規則 primary = "(" expr ")" | num に基づいて、抽象構文木のノードを生成します。

"("とexprと")"

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

consume関数・expect関数の引数を文字から文字列に変更します。

num(変更なし)

return new_num(expect_number());

gen関数！

https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR313
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/main.c#L313

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;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");
}

数値を得るためのアセンブリコードを生成する(変更なし)

  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;
  case ND_EQ:
    printf("  cmp rax, rdi\n");
    printf("  sete al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_NE:
    printf("  cmp rax, rdi\n");
    printf("  setne al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LT:
    printf("  cmp rax, rdi\n");
    printf("  setl al\n");
    printf("  movzb rax, al\n");
    break;
  case ND_LE:
    printf("  cmp rax, rdi\n");
    printf("  setle al\n");
    printf("  movzb rax, al\n");
    break;
  }

  printf("  push rax\n");

ノードの型がND_EQの場合(ノードの種類が==の場合)、ノードの型がND_NEの場合(ノードの種類が!=の場合)、ノードの型がND_LTの場合(ノードの種類が<の場合)、ノードの型がND_LEの場合(ノードの種類が<=の場合)、それぞれの場合に応じてアセンブリコードを生成する処理を追加します。
> や >= に対応するアセンブリコードは生成せず、抽象構文木の作成中において < や <= に対応するノードの子ノードを入れ替えることで、> や >= の処理を再現します(詳しくはrelational関数)

cqo
cqo命令は、RAXにセットされている値を128ビット値に符号拡張して、その符号拡張された128ビット値のうち、上位64ビットをRDXに、下位64ビットをRAXにセットします。

idiv rdi
idiv命令は、上位64ビットがRDXにセットされた値、下位64ビットがRAXにセットされた値からなる符号拡張された128ビット値をRDIにセットされている値で除算します。

cmp
cmp命令は、第一オペランドの値と第二オペランドの値を比較し、その比較した結果を、EFLAGSレジスタのフラグに以下のように反映させます。
第一オペランドの値 > 第二オペランドの値 の場合 → CF(キャリーフラグ)=1、ZF(ゼロフラグ)=0
第一オペランドの値 = 第二オペランドの値 の場合 → CF(キャリーフラグ)=0、ZF(ゼロフラグ)=1
第一オペランドの値 < 第二オペランドの値 の場合 → CF(キャリーフラグ)=0、ZF(ゼロフラグ)=0

sete
、、、

setne
、、、

setl
、、、

setle
、、、

movzb
movzb命令は、1byte(8bit)のレジスタにセットされている値を64bitに符号拡張してから、mov命令と同じ処理を行います。

テストコード

test.sh
https://github.com/rui314/chibicc/commit/6ddba4be5f63388607fc77fd786267b9ddcb14c9#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R30
https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/test.sh#L30

#!/bin/bash
assert() {
  expected="$1"
  input="$2"
  ./chibicc "$input" > tmp.s
  gcc -static -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
assert 21 '5+20-4'
assert 41 ' 12 + 34 - 5 '
assert 47 '5+6*7'
assert 15 '5*(9-6)'
assert 4 '(3+5)/2'
assert 10 '-10+20'
assert 10 '- -10'
assert 10 '- - +10'

assert 0 '0==1'
assert 1 '42==42'
assert 1 '0!=1'
assert 0 '42!=42'

assert 1 '0<1'
assert 0 '1<1'
assert 0 '2<1'
assert 1 '0<=1'
assert 1 '1<=1'
assert 0 '2<=1'

assert 1 '1>0'
assert 0 '1>1'
assert 0 '1>2'
assert 1 '1>=0'
assert 1 '1>=1'
assert 0 '1>=2'

echo OK

Makefile

https://github.com/rui314/chibicc/blob/6ddba4be5f63388607fc77fd786267b9ddcb14c9/Makefile

CFLAGS=-std=c11 -g -static

chibicc: main.o
	$(CC) -o $@ $? $(LDFLAGS)

test: chibicc
	./test.sh

clean:
	rm -f chibicc *.o *~ tmp*

.PHONY: test clean