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

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

今回作成するコンパイラ

トークナイザを導入(トークナイザが導入されたコンパイラ)

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

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c

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

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
};

// 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);
}

// Consumes the current token if it matches `op`.
bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

// Ensure that the current token is `op`.
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("expected '%c'", op);
  token = token->next;
}

// Ensure that the current token is TK_NUM.
int expect_number() {
  if (token->kind != TK_NUM)
    error("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) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

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

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

    // Punctuator
    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

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

    error("invalid token");
  }

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

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

  token = tokenize(argv[1]);

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // The first token must be a number
  printf("  mov rax, %d\n", expect_number());

  // ... followed by either `+ <number>` or `- <number>`.
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

  printf("  ret\n");
  return 0;
}

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

main関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR105
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L105

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

  token = tokenize(argv[1]);

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");

  // The first token must be a number
  printf("  mov rax, %d\n", expect_number());

  // ... followed by either `+ <number>` or `- <number>`.
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

  printf("  ret\n");
  return 0;
}
コマンドライン引数の個数をチェックする
  if (argc != 2) {
    error("%s: invalid number of arguments", argv[0]);
    return 1;
  }

argcの値が2であること→コマンドライン引数が2個であること→プログラムを実行するときに渡された引数が1つであることを確認します。
argcの値が2ではない場合は、error関数を実行して、メッセージを出力してからプログラムを終了させます。

トークナイズを行う
token = tokenize(argv[1]);

tokenize関数を呼び出して、argv[1]が指定する文字列をトークナイズします。
tokenには連結リストの先頭トークンを指定するアドレスが格納されます。

部分的にアセンブリコードを生成する①
  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");
部分的にアセンブリコードを生成する②
 printf("  mov rax, %d\n", expect_number());

トークン列の先頭は整数であることが期待されているので、expect_number関数を呼び出してトークンを1つ読み進めます。
また、expect_number関数の戻り値は、その整数の値となります。

部分的にアセンブリコードを生成する③
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

at_eof()関数の戻り値がtrueになるまで→着目しているトークンがトークン列の終端を表すトークンになるまで、while文のループを継続します。
consume('+')の戻り値がtrueになる場合は、アセンブリコード"add rax, expect_number関数の戻り値"を生成します。
consume('+')の戻り値がfalseになる場合は、着目しているトークンは - であることが期待されているので、expect('-')を呼び出してから、アセンブリコード"sub rax, expect_number関数の戻り値"を生成します。

部分的にアセンブリコードを生成する④
  printf("  ret\n");
  return 0;

error関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR26
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L26

// 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);
}

error関数は、引数fmtで指定された文字列と可変部の引数を用いてメッセージを出力し、プログラム(プロセス)を終了させます。

va_list ap について

va_startマクロ・vprintf関数などを使用するために必要となるva_list型の変数apを宣言します。

va_start(ap, fmt) について

va_list型の変数apを初期化して可変個の引数を扱えるようにするために、va_startマクロを呼び出します。
第一引数には先ほど宣言したva_list型の変数apを、第二引数には可変部分の引数の直前にある引数fmtを指定する必要があります。

vfprintf(stderr, fmt, ap) について

vfprintf関数は、可変個の引数を扱うことができるfprintf関数です。
標準エラー出力ファイルに、fmtが指定する文字列データを書き込みます(コンソール画面に文字列が表示されます)。

fprintf(stderr, "\n") について

fprintf関数を呼び出して、標準エラー出力ファイルに、\nを書き込みます(コンソール画面で改行が行われます)。

exit(1) について

exitシステムコールを呼び出して、このプログラム(プロセス)の処理を終了させます。
引数で指定した1の値が終了ステータスになります。

TokenKind

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR8
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L8

typedef enum {
  TK_RESERVED, // Keywords or punctuators
  TK_NUM,      // Integer literals
  TK_EOF,      // End-of-file markers
} TokenKind;

enum型を用いて、トークンの種類(トークンの型)を表現する名前付き整数定数を定めます。さらに、typedefキーワードを用いて、enum型をTokenKind型として定義します。

Token構造体

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR14
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L14

// 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
};

トークンを表現するデータ構造であるToken構造体を定義します。
さらに、typedefキーワードを用いて、Token構造体をToken型として定義します。

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR24
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L24

Token *token;

また、パースやアセンブリコード生成の際に着目しているトークンをグローバル変数tokenで表現します。

tokenize関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR72
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L72

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

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

    // Punctuator
    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

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

    error("invalid token");

  }

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

tokenize関数は、引数pで指定された文字列をトークン列に分割します。

トークンからなる連結リストのヘッダーを作成する
  Token head;
  head.next = NULL;
  Token *cur = &head;

トークン構造体headを定義し、これから作成する連結リスト(トークン構造体からなる連結リスト)のヘッダーとします。
nextメンバの初期値はNULL、連結リストの終端をcurで表現します。

空白文字の場合(while文内で一文字ずつ文字を読み込んだ時)
    if (isspace(*p)) {
      p++;
      continue;
    }

isspace(*p)の戻り値が0以外の場合は→文字*pが空白文字だった場合は、次の文字を取得するためにchar型へのポインタpをインクリメントしてからwhile文のループを継続します。
isspace関数は、引数で指定された文字が空白文字であるかを判定します。引数で指定された文字が空白文字である場合は0以外の値が戻り値となり、引数で指定された文字が空白文字ではない場合は、0が戻り値となります。

+ または - の場合(while文内で一文字ずつ文字を読み込んだ時)
    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

文字*pが+または-だった場合は、new_token関数を呼び出して、記号を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
次の文字を取得するためにchar型へのポインタpをインクリメントしてからwhile文のループを継続します(char型へのポインタpを後置インクリメントしているので、評価前のpの値(+または-の文字を指定するアドレス)が引数として渡されます)。

数字の場合(while内で一文字ずつ文字を読み込んだ時)
    // Integer literal
    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

isdigit関数は、引数で指定された文字が数字であるかを判定します。引数で指定された文字が数字である場合は0以外の値が戻り値となり、引数で指定された文字が数字ではない場合は0が戻り値となります。
isdigit(*p)の戻り値が0以外の場合は→文字*pが数字だった場合は、new_token関数を呼び出して、数値を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
strtol関数を呼び出して新規に生成されたトークンにその数値を記録してから、while文のループを継続します(strtol関数の引数pには、数字の次にある文字を指定するアドレスが格納されます)。

その他の場合(while内で一文字ずつ文字を読み込んだ時)
    error("invalid token");

上記のいずれにも該当しなかった場合は、error関数を呼び出して、メッセージを出力してからプログラムを終了させます。

トークン列の終端を表すトークンを生成する
  new_token(TK_EOF, cur, p);
  return head.next;

最後に、トークン列の終端を表すトークンを生成します。

連結リストの先頭トークンを戻り値としてリターンする
return head.next;

連結リストの先頭トークン(連結リストのヘッダーの次にあるトークン)のアドレスを戻り値としてリターンします。

new_token関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR63
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L63

Token *new_token(TokenKind kind, Token *cur, char *str) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

new_token関数は、新規にトークンを生成し、引数curで指定されたトークンと生成されたトークンを連結させます。

トークンを生成する
Token *tok = calloc(1, sizeof(Token));

calloc関数を呼び出して、トークン構造体の生成に必要なメモリ領域を割り当てます。
calloc関数は、第二引数で指定されたバイトサイズ分のメモリ領域を、第一引数で指定された数だけ、割り当てます。
今回は、sizeof(Token)バイトのメモリ領域を1つ割り当てています。

生成されたトークンのメンバに値を設定する
  tok->kind = kind;
  tok->str = str;

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

生成されたトークンを連結リストに追加する
cur->next = tok;

引数curで指定されたトークン構造体のnextメンバに、生成されたトークンのアドレスを格納します。

生成されたトークンを戻り値としてリターンする
return tok;

生成されたトークン構造体のアドレスを戻り値としてリターンします。

at_eof関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR59
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L59

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

at_eof関数は、現在着目しているトークンがトークン列の終端であるかを判定します。
現在着目しているトークンがトークン列の終端である場合はtrueを、現在着目しているトークンがトークン列の終端ではない場合はfalseを、戻り値としてリターンします。

consume関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR35
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L35

bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

consume関数は、現在着目しているトークンの文字列が引数opで指定された文字列と同じであるかを判定します。

現在着目しているトークンの文字列を調べる
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合は、戻り値をflaseとしてリターンします。

着目しているトークンを次のトークンに変更する
  token = token->next;
  return true;

上記以外の場合は、着目しているトークンを次のトークンに変更し、戻り値をtrueとしてリターンします。

expect関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR43
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L43

void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("expected '%c'", op);
  token = token->next;
}

expect関数は、現在着目しているトークンの文字列が引数opで指定された文字列と同じである場合に、トークンを1つ読み進めます。

現在着目しているトークンの文字列を調べる
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("expected '%c'", op);

現在着目しているトークンの型がTK_RESERVEDではない場合(トークンの種類が記号ではない場合)、または、トークンの文字列と引数opで指定された文字列が異なる場合は、error関数を呼び出して、メッセージを出力し処理を終了します。

着目しているトークンを次のトークンに変更する
 token = token->next;

上記以外の場合は、着目しているトークンを次のトークンに変更します。

expect_number関数

https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR50
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/main.c#L50

int expect_number() {
  if (token->kind != TK_NUM)
    error("expected a number");
  int val = token->val;
  token = token->next;
  return val;
}

expect_number関数は、現在着目しているトークンの種類が整数である場合に、トークンを1つ読み進めます。

現在着目しているトークンの種類が整数であることを確認する
  if (token->kind != TK_NUM)
    error("expected a number");

現在着目しているトークンの型がTK_NUMではない場合(トークンの種類が整数ではない場合)、error関数を呼び出して、メッセージを出力し処理を終了します。

着目しているトークンを次のトークンに変更する
  int val = token->val;
  token = token->next;
  return val;

上記以外の場合は、着目しているトークンを次のトークンに変更し、トークンが持つ整数値を戻り値としてリターンします。

テストコード

test.sh
https://github.com/rui314/chibicc/commit/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R22
https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/test.sh#L22

#!/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 '

echo OK

Makefile

https://github.com/rui314/chibicc/blob/ef6d1791eb2a5ef3af913945ca577ea76d4ff97e/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