Cコンパイラを自作する

ずっとやってみたかったCコンパイラを作成します。
参考にするのは植山類さんの記事です。

個人的な学びも結構含んでいてそれらは上記の記事とは関係なく自身で調べてまとめたものになりますので、間違いがある可能性があります。

また、学びのアウトプットを目的の一つにしているため文章は人間が打っています。もしtypoや間違いに気づかれた際、補足したい箇所があればdiscussionをたてて教えてくださると本当に嬉しいです。細かい言い回しのニュアンスのズレなどは頻繁にありそうなのでむず痒いと思いますがスルーしてください。

特に章に分けたりはしないつもりで、気づいたことや学びをその都度書いていきます。

Cとそれに対応するアセンブラ

.intel_syntax noprefix
.globl main
main:
  mov rax, 42
  ret

42という値をRAXというレジスタにセットし、mainからreturnするという意味。このように整数を入れられるレジスタはRAX込みで16個あるが、関数からreturnしたときにはRAXに入っている値が関数の返り値という約束になっている。つまり、このコードは42をreturnする。Cで書くと

int main(){
  return 42;
}

上記のアセンブリを出力するためには9cc.cの内部を次のようにする。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");
  printf("  mov rax, %d\n", atoi(argv[1]));
  printf("  ret\n");
  return 0;
}

コードの意味を見ていきましょう。
int main(int argc, char **argv)はコマンドラインから渡された引数をプログラム内で受け取るための書き方です。argcは引数の個数でargvは引数の文字列そのものが入ります。例として./9cc 42を実行したとします。このときargc=2、argv[0]=”./9cc”、argv[1]=“42”となります。argv[0]には実行ファイル名自身が必ず入るらしいです(ということはargvのサイズは渡した引数の数+1になるのか？)。

その次の

if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

ではargcの数が2ではなかった場合にエラーを出して異常終了するようにしていますね。printfではなくfprintfが使用されているのは標準エラー出力へ書くという目的があるからです。標準出力してしまうとエラーメッセージが紛れ込みアセンブリが壊れるからです。return 1は異常終了をシェルに伝えています。Cでは0のみが正常終了を表します。

その後に続く数行のprintfですが、printf(" mov rax, %d\n", atoi(argv[1]));だけ解説。
arg[1]というのは文字列です。%dではintを要求するのでatoiで数値に変換して渡しているということです。atoiはエラー報告できないのでこの段階では入力は正しい数値であることを前提としているのですかね。

では、上記のコードが出力する下記のアセンブリはどういう意味になるのか。

.intel_syntax noprefix
.globl plus, main

plus:
        add rsi, rdi
        mov rax, rsi
        ret

main:
        mov rdi, 3
        mov rsi, 4
        call plus
        ret

1行目はアセンブリの文法を指定する命令らしい。htmlで言うところの!DOCTYPE宣言のようなものかな？
本書で使っているIntel記法という記法を選ぶためのアセンブラコマンドだそうです。
.globl plus, mainでplusとmainという2つの関数をプログラム全体から見える関数だということをアセンブリに指示している。では非公開にするには.private plus, mainとでもなるのか？と思ったが、どうやらデフォルトでprivateらしい。つまり.globlとはデフォルトで非公開のものをわざわざ公開するための宣言ということだ。一応.localというディレクティブも存在するようだ。
また、このような.で始まる.globlや.localのようなものをディレクティブと呼ぶ。CPUへの命令ではなく、アセンブラへの指示のことを指す。
上記のコードを見ても分かる通り、アセンブリのソースファイルには性質の異なる2種類の行が混ざっている。

• 命令: mov,sub,callなどのアセンブラによって機械語のバイト列に変換され実行時にCPUが実行するもの。
• ディレクティブ: .globl,intel_syntax,dataなどの機械語には変換されずに、アセンブル作業をどう進めるかをアセンブルに指示するもの。

TSでconst x: number = 1と書いたとき、: numberはコンパイル後のJSに残らないけど、コンパイラの挙動(型チェック)は制御する、みたいな感じかな？

movはmoveの省略形だが、実際にはデータを移動するわけではなく単にコピーする命令だそうだ。
RSI, RDIという2つのレジスタがある。アセンブラにおいて第一引数はRDIレジスタ、第二引数はRSIレジスタに入れるという約束になっているらしい。

上記2点を踏まえるとRDIレジスタに3をコピーし、RSIレジスタに4をコピーしている事がわかる。
その後call plusでplus関数を呼んでいる。plus関数のadd rsi, rdiによりRSIレジスタとRDIレジスタの和がRSIレジスタに書き込まれれる。
関数からreturnするときの返り値はRAXに入れるという決まりを先ほどならった。mov rax, rsiにより、RAXレジスタにRSIレジスタの値を書き込み、その後のretによりRAXレジスタの値がmain関数に返っていく。その後main内のretによりRAXの値が返るということになる。

つまり、上記のアセンブリは3+4を関数に渡し、その結果をreturnするというものになる。

int plus(int x, int y){
  return x+y;
}
int main(){
  return plus(3,4);
}

こちらのサイトでリアルタイムにC言語とそのアセンブリが表示される様子を眺められる。

電卓レベルの言語の作成

目標は次のような式をコンパイルできるようになること
30+(4-2)*-5

参考記事でも「他愛もない目標のようで結構難しい」と書かれていますが、見るからに難しそうです。私たちが当たり前に従っているルールを適用する必要があります。掛け算割り算の優先度や「マイナス5」なのか「引く5」なのかの判別もしないといけないですね。

こういった構文解析系の問題は1950年代から1970年代にかけて活発に研究が行われていたそうです。そんな昔からあるんだ、、。ただ、その成果のおかげで今では簡単なんだとか。

「この章で学ぶ構文解析の手法は、大げさではなく一生物のテクニックと言ってよいでしょう。」だそうです！ワクワクだな。

まず最初に入力された数をそのまま返すようなアセンブリをを出力するコンパイラを作ります。ついに入力が出てきました！これも特定のレジスタが割り当てられているのだろうか。
記事では次のような例が載せられています。

.intel_syntax noprefix
.globl main

main:
        mov rax, 42
        ret

見ての通り42という文字列をreturnするアセンブリですね。これを出力するコンパイラの作成をすることになります。

次のようにファイルを構成し、ターミナルでcc -o 9cc 9cc.cを実行すると9ccというファイルが作成されます。

ちなみにccはC Compilerの略です。実態はシステムによって違い、Linuxでは大抵gcc、macOSではclangへのエイリアスになっています。
次のようにcc --versionで実態を確認できます。

$ cc --version

Apple clang version 17.0.0 (clang-1700.6.3.2)
Target: arm64-apple-darwin24.6.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

ここでDocker内で作業をしていないことに気づきました、、。記事で紹介されていたイメージを使用してコンテナを作成しました。

さて、./9cc 123 > tmp.sと入力するとtmp.sというファイルが作成されます。
中身を確認すると次のようになっていました。

.intel_syntax noprefix
.globl main
main:
  mov rax, 123
  ret

つまりtmp.sはアセンブリファイルです。

記事を見ると次に実行するコマンドは

$ cc -o tmp tmp.s
$ ./tmp
$ echo $?
123

のようです。

ちょっと分けがわからなくなってきました。
一旦まとめましょう。今のところ登場人物は以下の四人です。

1. 9cc.c
2. 9cc
3. tmp.s
4. tmp

1は第一引数を数値として読み込み、定型文のアセンブリの中に埋め込むCプログラムです。
ここで定型文とは以下のコードを指します。

.intel_syntax noprefix
.globl main

main:
        mov rax, 42
        ret

printfで書かれた内容そのままですね。これはOK。

2はcc -o 9cc 9cc.cにより生成されたバイナリファイルです。このコマンドの意味は9cc.cをコンパイルして9ccという実行ファイルを作成しろという意味。ccで指定されているのがx86-64です。コンパイラを作るにあたってそのコンパイラをコンパイルする必要があるのですね。。

以下重複する項目がありますが個人的に沸いた疑問とその理解です

つまり9ccは9cc.cの実行ファイルというわけですね。この実行ファイルから./9cc 123 > tmp.sでアセンブリを生成すると3のtmp.sが生成されます。
そして最後にcc -o tmp tmp.sを実行することでtmp.sの実行ファイルである4のtmpが生成されるというわけです。
tmpの中身は入力された値を数値にして返すアセンブリなわけで、先ほど./9cc 123 > tmp.sと打ったので返ってくる値は123ですね。
./tmpで実行してecho $?でreturnの値を見ると123と表示されるわけです。

ここまではおそらく理解できているぞ。次の章に進む。

加減算のできるコンパイラの作成

先程までは固定の値を出力するだけのコンパイラを作成してきましたが、ここからは加減算を含む式を受け取れるようにすることを目標とします。
例として5+20-4という式をアセンブリで書いてみましょう。

.intel_syntax noprefix
.globl main

main:
        mov rax, 5
        add rax, 20
        sub rax, 4
        ret

raxに5をコピーし、20を加算し、4を減算し、最後にretでraxの値つまり5+20-4の結果である21を出力します。

これをCで書くにはどうすればいいでしょうか。もととなるのは先程仕上げた特定の数をそのまま出力するプログラムです。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");
  printf("  mov rax, %d\n", atoi(argv[1]));
  printf("  ret\n");
  return 0;
}

入力された文字列を前から順に見ていって、記号(+-)を発見したら場合分けをすれば良さそうです。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  char *p = argv[1];

  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");
  printf("  mov rax, %ld\n", strtol(p, &p, 10));

  while (*p) {
    if (*p == '+') {
      p++;
      printf("  add rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    if (*p == '-') {
      p++;
      printf("  sub rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    fprintf(stderr, "予期しない文字です: '%c'\n", *p);
    return 1;
  }

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

コードの解説をします。
例として./9cc "5+20-4"と実行したとします。先程習ったようにargc=2、argv[0]=”./9cc”、argv[1]=“5+20-4”となります。
そういえばchar **argvについて書いていませんでした。char *は文字列の先頭を指すポインタです。char **はそのポインタを指すポインタ、つまり文字列の配列です。
strtolの挙動は次の通り

• 第1引数: 数値に変換したい文字列
• 第2引数: 最初に現れた不正な文字を指すポインタのアドレス
• 第3引数: 基数(第1引数として渡した文字列を何進数の数値として扱うか)

よって、printf(" mov rax, %ld\n", strtol(p, &p, 10));によって引数の最初から見ていって初めてあたった不正な文字列のアドレスが&pで入ります。その後のwhileループによりもしあたった不正文字が+か、-かという場合分けをしてその中でも再度strtolを使用して次の不正な文字までジャンプする、という処理をし続けているわけです。
5が返った後にpに+を指すアドレスが入って20が出力されてpに-を指すアドレスが入って4が出力されるというわけですね。

これで加減算のできるコンパイラが完成しました！！コミットします！

• コミットリンク

トークナイザを導入

トークナイザ(字句解析器、lexerとも呼ばれます)は、コンパイラの一番最初の段階でソースコードというただの文字列を、意味のある最小単位(トークン)の列に分割する部品です。
例えばx=12+foo;という文字列をコンパイラがそのまま扱うのは大変です。「1と2は続いているから12という一つの数値だ」、「fooは3文字で一つの識別子だ」といった判断を後段の処理が毎回やるのは無駄なので、最初にまとめて片付けてしまいます。トークナイザを通すと次のようになります。

[識別子 “x”] [記号 ”=”] [数値 12] [記号 ”+”] [識別子 “foo”] [記号 ”;”]

各トークンは「種類(識別子・数値・記号・キーワードなど)」と「実際の文字列や値」を持つ構造体になるのが普通です。この時点で空白やコメントは捨てられます。そう、空白やコメントが捨てられるのです！先程のコンパイラには5+20-4という引数を渡しましたが、これがもし5 + 20 - 4だった場合空白文字を見つけた瞬間にstrtolがエラーになりコンパイル失敗します。よって、5、+、20、-、4という5つの要素にバラして処理をしやすくするということです。このバラされた5つの要素はそれぞれトークンといい、バラす処理をトークナイズするというらしいです。

先程の加減算のできるコンパイラに対してトークナイザを導入し改善すると次のようになるそうだ。

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

// トークンの種類
typedef enum {
  TK_RESERVED, // 記号
  TK_NUM,      // 整数トークン
  TK_EOF,      // 入力の終わりを表すトークン
} TokenKind;

typedef struct Token Token;

// トークン型
struct Token {
  TokenKind kind; // トークンの型
  Token *next;    // 次の入力トークン
  int val;        // kindがTK_NUMの場合、その数値
  char *str;      // トークン文字列
};

// 現在着目しているトークン
Token *token;

// エラーを報告するための関数
// printfと同じ引数を取る
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// 次のトークンが期待している記号のときには、トークンを1つ読み進めて
// 真を返す。それ以外の場合には偽を返す。
bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

// 次のトークンが期待している記号のときには、トークンを1つ読み進める。
// それ以外の場合にはエラーを報告する。
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("'%c'ではありません", op);
  token = token->next;
}

// 次のトークンが数値の場合、トークンを1つ読み進めてその数値を返す。
// それ以外の場合にはエラーを報告する。
int expect_number() {
  if (token->kind != TK_NUM)
    error("数ではありません");
  int val = token->val;
  token = token->next;
  return val;
}

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

// 新しいトークンを作成して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;
}

// 入力文字列pをトークナイズしてそれを返す
Token *tokenize(char *p) {
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // 空白文字をスキップ
    if (isspace(*p)) {
      p++;
      continue;
    }

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

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

    error("トークナイズできません");
  }

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

int main(int argc, char **argv) {
  if (argc != 2) {
    error("引数の個数が正しくありません");
    return 1;
  }

  // トークナイズする
  token = tokenize(argv[1]);

  // アセンブリの前半部分を出力
  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");

  // 式の最初は数でなければならないので、それをチェックして
  // 最初のmov命令を出力
  printf("  mov rax, %d\n", expect_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;
}

トークナイザ版のコードを読む

上のコードは大きく2段階に分かれています。

• tokenize(): 文字列をトークンの列(連結リスト)に変換する
• main()のループ: トークン列を先頭から消費しながらアセンブリを出力する

./9cc "5 + 20 - 4"を渡したときのイメージはこうです。

"5 + 20 - 4"
     ↓ tokenize()
[NUM:5] → [RESERVED:+] → [NUM:20] → [RESERVED:-] → [NUM:4] → [EOF]
     ↓ mainのループ
  mov rax, 5
  add rax, 20
  sub rax, 4
  ret

前のバージョンはstrtolで文字列を直接舐めながら出力していたので空白で死んでいましたが、間にトークナイズを挟んだことで空白はtokenize()の中で捨てられ、後段は空白の存在を一切気にしなくてよくなりました。

トークンの表現

struct Token {
  TokenKind kind; // トークンの型
  Token *next;    // 次の入力トークン
  int val;        // kindがTK_NUMの場合、その数値
  char *str;      // トークン文字列
};

配列ではなくnextを持った連結リストになっているのは、トークンが何個になるか実行前には分からないからです。数値のときだけvalを使い、それ以外では使わないという種類によって意味を持つメンバが変わる構造になっています。

strは文字列のコピーではなく、argv[1]の中を指すポインタである点が地味に重要そうです。今はconsumeやexpectがstr[0]を見るためだけに使っていますが、入力のどこで失敗したかを保持していることになるので、後々エラーメッセージで該当箇所を指し示すのに使える(はず)です。他の使い道は想像できませんでした。

そしてTK_EOFという終端トークンをわざわざ用意しているのがポイントです。これがあるおかげでまだトークンが残っているかの判定がat_eof()一発で済み、NULLチェックが要らなくなります。番兵というやつですね。

Token *token;がグローバル変数になっているのは、今どのトークンを見ているかという読み込み位置を関数間で引き回さなくて済ませるためです。行儀は悪いですが、この先パーサの関数が増えていったときに毎回ポインタを渡し合わなくてよくなるのは確かに楽そう。DFS書くときにseenをグローバル宣言していたのを思い出しました。

tokenize()の中身

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

これが一番はえぇ〜となった箇所です。headはダミーの先頭要素で、実際のトークンとしては使いません。これを置かないと、リストが空のときだけ先頭に代入し、それ以外はcur->nextに代入するという場合分けが必要になります。最後にhead.nextを返せばダミーを飛ばした本当の先頭が得られる、という寸法です。しかもheadはローカル変数なのでアロケートも要りません。

ループ本体は素直で、空白ならスキップ、+か-ならTK_RESERVED、数字ならTK_NUM、それ以外はエラーという分岐だけです。

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

p++が後置なので、new_tokenには進める前の位置が渡り、その後でpが1つ進みます。cやc++に限りますが1行に詰めこまれたコード好きです。

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

数値側では明示的なp++がありません。strtolの第2引数に&pを渡すと読み終わった位置までpを進めてくれるからですね。isdigitで先頭1文字だけ確認しておけば、複数桁はstrtolがまとめて面倒を見てくれるという分担になっています。上の方で一度習ったやつです。

consume / expect / expect_number

トークン列を読むためのAPIがこの3つで、たぶんこの先ずっと使い回すことになる部分です。

• consume(op): 期待する記号なら1つ読み進めてtrue、違えば何もせずfalse。もし+だったら〜という分岐に使う
• expect(op): 期待する記号なら読み進め、違えばエラー終了。ここは絶対)のはずだというアサーションに使う
• expect_number(): 数値ならその値を返して読み進め、違えばエラー

試して失敗してもよいconsumeと、失敗は許されないexpectが分かれているのが肝で、これがあるとmainのループがこう書けます。

while (!at_eof()) {
  if (consume('+')) {
    printf("  add rax, %d\n", expect_number());
    continue;
  }

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

elseを書かずにcontinueで抜けるスタイルになっていて、+でも-でもなければエラーという判定をexpect('-')が兼ねています。うまいですね。

コード生成自体は前と変わらず、raxをアキュムレータにして左から順に足し引きしているだけです。式の先頭は必ず数でなければならないので、そこだけexpect_number()でチェックして最初のmovを出しています。

エラー報告用のerror()

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

...は可変長引数で、printfと同じように書式文字列と任意個の引数を受け取れます。va_listとva_startで引数リストを取り出し、それをvfprintfに丸投げしています(printfのv付きバージョンはva_listを直接受け取れる)。出力先がstderrなのは、アセンブリを吐いている標準出力を汚さないためですね。最後にexit(1)しているので、この関数は呼んだら戻ってきません。

なのでmainの

if (argc != 2) {
  error("引数の個数が正しくありません");
  return 1;
}

のreturn 1;は実は到達しないデッドコードかも？今後使うから置いてあるとか、今まで使用していたから残してあるとか気遣いの可能性もあります。

気になった点(この先の伏線っぽいもの)

• 記号をstr[0]の1文字でしか比較していないので、このままでは==や<=のような複数文字の演算子に対応できません。
• エラーメッセージに位置情報がありません。
• mainのループが構文解析とコード生成を兼ねています。乗除算や括弧が入ると優先順位の概念が必要になるので、ここで抽象構文木とパーサに分離されるのですかね(後ろの方に木っぽい図が入ってるのがちらっと見えたので)。

test.shに空白込みのテストを追加してmakeで実行してみます！
類さんと同様にassert 41 " 12 + 34 - 5"と追記してみます。

./test.sh
0 => 0
42 => 42
5+20-4 => 21
 12 + 34 -5 => 41
OK

おおおおお！！空白込みでOKになりました！
もちろん空白の個数や場所を自由にやっても通ります。すごい進化した感じです！

 12   + 34 - 5 => 41
OK

これで空白込で加減算のできるコンパイラが完成しました！！コミットします！

• コミットリンク

エラーメッセージを改良を読む

やはりきました！エラー系を整えていくっぽいですね。
記事にもありますが、次のようなよく見るエラー文をどうやって出力しているのかがわかるっぽいです！

$ ./9cc "1+3++" > tmp.s
1+3++
    ^ 数ではありません

$ ./9cc "1 + foo + 5" > tmp.s
1 + foo + 5
    ^ トークナイズできません

いつもどうやってエラーの場所に矢印を引いているんだろう？とか、たまにぜんぜん違うところに矢印が引かれるのはなぜなんだろう？とか思っていたのでワクワクします。

結論からいうとプログラムの文字全体を変数に保存して、いまどこを見ているのかを指すポインタを受け取るエラー表示関数を定義することで達成されるそうです！なんとワイルドな。

// 入力プログラム
char *user_input;

// エラー箇所を報告する
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, " "); // pos個の空白を出力
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

user_inputをグローバルに置く理由

// 入力プログラム
char *user_input;

これは入力文字列全体の先頭を指すポインタです。mainでuser_input = argv[1];としておいて、以降どこからでも入力の先頭はここだと参照できるようにしています。

なぜグローバルなのかというと、エラーはtokenizeの中からもexpectの中からも起こりうるので、そのたびに入力の先頭を引数で引き回すのが面倒だからですね。Token *token;をグローバルにしたときと同じ発想です。コンパイラ全体で1つしかない情報だから置いてしまえ、という割り切りだと思われます。

注意点として、user_inputへの代入はtokenizeを呼ぶ前にやらないといけません。トークナイズ中にエラーが出た場合、error_atがuser_inputを読むので、まだNULLだったらセグフォします。

loc - user_inputで位置がわかる仕組み

ここが一番の肝ですね。

int pos = loc - user_input;

locはエラーが起きた場所を指すポインタで、user_inputは先頭を指すポインタです。同じ文字列の中を指すポインタ同士なので、引き算すると先頭から何文字目かが出てきます。

"1 + foo + 5"でfooのfのところでエラーになったとすると、locは先頭から4バイト進んだ位置を指しているのでposは4になります。つまり4文字分の空白を出力してから^を置けばよいということが分かるわけです。

思い返すと、前のバージョンでTokenのstrが文字列のコピーではなく入力文字列内を指すポインタだったのが、まさにこのために効いてきます。トークンが自分の出身地を覚えているので、後からいくらでも位置を復元できるという設計だったんですね。伏線回収された気分です。

%*sという書式

fprintf(stderr, "%*s", pos, " "); // pos個の空白を出力

初見だとかなり謎な行でした。%sの間に*が入っていますが、これは最小フィールド幅を実行時に引数で指定するという書式です。%5sならフィールド幅5、%*sなら幅は次の引数から取るという意味になります。

なので上の行は幅posで" "(空白1文字)を出力するという意味になり、%sはデフォルトで右寄せなので、足りない分が左に空白で埋められて結果的にpos個の空白が出力されます。ループを回して空白を出すより短くて済むというテクニックですね。printf("%5s", "ab")が" ab"になるのと同じ原理です。

その後の

fprintf(stderr, "^ ");
vfprintf(stderr, fmt, ap);

で^とメッセージ本体を出しています。可変長引数まわりのva_list/va_start/vfprintfは前のerror()と全く同じで、書式文字列と引数をそのままvfprintfに丸投げしているだけです。出力先がstderrなのも同じ理由(標準出力に混ぜるとアセンブリが壊れる)。最後にexit(1)しているので、これも呼んだら戻ってきません。

つまり出力の組み立てはこうなっています。

1 + foo + 5      ← fprintf(stderr, "%s\n", user_input) で入力をそのまま出す
    ^ トークナイズできません
^^^^             ← "%*s" で pos 個の空白
    ^^           ← "^ "
      ^^^^^^^^^^ ← vfprintf でメッセージ

言われてみればめちゃくちゃ単純で、入力をそのまま1行出して、空白を数えて^を置くだけでした。あの見慣れたエラー表示がこんな素朴な仕組みだったとは。

呼び出し側はどう変わるか

errorをerror_atに置き換えるにあたって、どこでエラーになったかを渡す必要が出てきます。

• tokenizeの中: まだトークンになっていないので、走査中のポインタpをそのまま渡す
• expect / expect_numberの中: すでにトークンになっているので、token->strを渡す

前者はerror_at(p, "トークナイズできません")、後者はerror_at(token->str, "数ではありません")という形ですね。エラーの発生源によって渡すものが変わるだけで、error_at側は入力内のどこかを指すポインタしか要求していないので、どちらでも同じように扱えます。

気になった点

• posが0のとき、つまり入力の1文字目でエラーになったときは"%*s"の幅が0になりますが、" "は1文字あるので空白が1つ出てしまう気がします。フィールド幅はあくまで最小幅なので、0を指定しても切り詰められないんですよね。^が1つ右にズレそうですが、実害がないから気にしていないのか、それとも私の勘違いか。" "ではなく""を渡せばぴったりになりそうです
• ここで数えているのはバイト数なので、日本語などマルチバイト文字が入力に含まれると^の位置が大きくズレるはずです。たまにぜんぜん違うところに矢印が引かれるのはなぜなんだろうという長年の疑問はこれが原因なんじゃないかという気がしてきました。タブ文字も同様で、1バイトなのに表示上は数文字分の幅を取るのでズレます。逆に言えば、まともなコンパイラのエラー表示はこのあたりを頑張って補正しているということですね
• 今のところ入力はargv[1]の1行だけなので何行目かの情報が要りませんが、複数行のソースファイルを読むようになったら行番号とその行だけを切り出す処理が必要になりそうです

さてtest.shの内容をわざとおかしくしてテストしてみましょう。
assert 41 " 12 + 34 - あ"

今回の修正を入れる前だと、次のように出力されるだけでした。

トークナイズできません

さて修正を入れて実行するとちゃんとエラーの場所を教えてくれるようになりました！

 12 + 34 - あ
           ^ トークナイズできません

• コミットリンク

文法の記述方法と再帰下降構文解析

この章を進めることで乗算除算カッコなどを含む式をコンパイルできるようになるそうですが難しそうですね。どんな膨大なコードもコンパイルして実行できる状態になるのが当たり前の生活をしていましたが、機械は人間じゃないので思考して判断してとかできませんし決まったルールに則ってそのとおりに変換して問題なく実行ファイルができているということが不思議です。AIに衝撃を受けることの多い昨今ですがコンパイラも同じくらいすっごいぞ。
私はグラフ系のアルゴリズムやデータ構造が得意なので活かしていきたいな。

類さんの記事では、まず最初にいくつかの式とその木の例が載っています。これをみながらまずは自分で考えてみます。

入力された式から抽象構文木を形成することを目標に考えてみます。

まず、カッコですがこれは深さを調整することで対処できそうです。基本的には入力された式を左から見ていって木に左から配置していき、各ノードは最大2つの子ノードを持つことができるとしてみるとなにか問題が起きるかな？

手を動かして反例を探すのが早そうです。

1 + 2 _ 3
1 _ 2 + 3
1 - 2 - 3

上記の3つを先程のルールに習っておいてみましたが別に問題はなさそうでした。ただ、一つ気づきとして葉から根に向かって計算するというルールが良さそうだと思いました。幅優先探索の逆的なね。そうなってくると優先順位の高い演算子は木の葉に近い位置に配置されるということになりそうです。
ここで次の式を考えてみます。

(1 + 2) * 3

これも何も問題なく配置できますが、乗算のノードが根になるものしか思いつきませんでした。となると根に優先順位の高いものを配置して根から葉に向かって見ることになりますか。
もう一つ思ったのは子を持つノードは演算子になるのか？ということです。葉ノードに演算子があるのは意味がわからないし、葉ノード以外に数が出てくるのもわからなさそうです。そうなると木を完全二分木にするのでしょうか。逆に子ノードを1つしか持たないノードは存在するのでしょうか。反例が思いつきません。

また、今後もし単項マイナスに対応するとなった場合にどうやって実装するかも気になります。そうなると葉ノードにマイナスという数でないものが入ってしまいます。まぁその場合は単項マイナスだと割り切るようにすれば問題ないのか？とも思いました。

答えが気になるので読み進めます。

まず自分の予想の答え合わせ

読み進める前に自分の考えを整理しておくと、葉から根に向かって計算するという直感は当たりでした。木の深いところにあるノードほど先に計算されるという性質が、そのまま優先順位を表しています。

(1 + 2) * 3で乗算が根に来たので根に優先順位の高いものが来るのかと迷いましたが、これは逆側から見ると筋が通ります。カッコは加算の優先順位を持ち上げるための記法なので、加算のほうが深い位置に来ます。つまり優先順位の高い演算子が深い位置に来るという最初のルールは崩れておらず、カッコによって加減算が乗除算より深くなることもある、というだけの話でした。

(1 + 2) * 3          1 + 2 * 3

      *                  +
     / \                / \
    +   3              1   *
   / \                    / \
  1   2                  2   3

深い演算子から順に潰していくと、左は1+2が先で右は2*3が先になります。ちゃんと期待通りですね。得意なグラフの話に寄せると、これは帰りがけ順のDFS、つまり後行順走査そのものです。子を全部片付けてから自分を処理するという順番が、そのまま計算順序になります。

生成規則をBNFで書く

さて記事の本題です。優先順位のルールを日本語でだらだら書くのではなく、そのままコードに落とせる形で厳密に書くための記法としてBNFが登場します。

用語の整理から。

• 生成規則: 左辺 = 右辺という形の1本のルール。左辺は右辺のように展開できるという意味
• 非終端記号: 生成規則の左辺に現れる記号。まだ展開できる、つまり中身を持つもの
• 終端記号: それ以上展開できない記号。+や(といった具体的な文字や、トークンそのもの

記事で使われているのはEBNFという拡張版で、正規表現に似た省略記法が使えます。

• A* … Aが0回以上の繰り返し
• A? … Aが0回か1回(あってもなくてもよい)
• A | B … AまたはB
• (...) … グループ化

記事にあるA = ("fizz" | "buzz")*という例なら、空文字列、fizz、buzzfizz、fizzfizzbuzzなどがすべて当てはまります。正規表現を知っていればそのまま読めるので、ここは助かりました。

いま作ってあるコンパイラを文法で書いてみる

加減算だけの現状は、この記法で書くとこうなります。

expr = num ("+" num | "-" num)*

まずnumが1つあり、そのあとに+とnumの組か-とnumの組が0回以上続く、と読みます。5+20-4はnum=5、+と20、-と4なので確かに当てはまります。

この規則は今書いてあるmainのループと形が一致しています。

printf("  mov rax, %d\n", expect_number());   // 先頭の num
while (!at_eof()) {                            // ( ... )* の繰り返し
  if (consume('+')) { ... }                    // "+" num
  expect('-'); ...                             // "-" num
}

優先順位を規則の階層で表す

乗除算を足すために、規則を2段に分けます。

expr = mul ("+" mul | "-" mul)*
mul  = num ("*" num | "/" num)*

exprの中身がnumからmulに変わっただけなのに、なぜこれで優先順位が表現できるのでしょうか。

exprは+の左右にmulを要求しています。つまり+が結びつく相手は必ずmulというかたまりです。そしてmulは*や/を先に食べてしまう規則なので、1+2*3を読ませると2*3が先に1つのmulとしてまとまり、+はその塊と結びつくしかなくなります。

mul = num ("*" num | "/" num)*
      ↑↑↑ これは繰り返しの外にある

繰り返し0回 → num 例: 1
繰り返し1回 → num "*" num 例: 1*2
繰り返し2回 → num "*" num "/" num 例: 1*2/3

まとめると、下の階層にある規則の演算子ほど強く結合します。優先順位の高い演算子を下に置く、というのがこの設計の型ですね。というか木にしようとすると勝手にそうなるのかな？

カッコを入れると規則が循環する

カッコを扱うために、numの位置をもう一段抽象化します。

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

primaryは、数そのものか、カッコで囲まれたexprのどちらか、という規則です。

注目したいのはprimaryの中にexprが出てくることです。expr → mul → primary → exprと一周して戻ってきています。この循環のおかげで、((1+2)*3)のように何重にネストしても3本の規則だけで表現できます。

生成規則を関数に写す

再帰下降構文解析でやることは、生成規則1本につき関数1つを書くことです。

Node *expr() {
  Node *node = mul();          // 先頭の mul

  for (;;) {                   // ( ... )* の繰り返し
    if (consume('+'))
      node = new_node(ND_ADD, node, mul());
    else if (consume('-'))
      node = new_node(ND_SUB, node, mul());
    else
      return node;             // + も - も来なければ繰り返し終了
  }
}

Node *mul() {
  Node *node = primary();

  for (;;) {
    if (consume('*'))
      node = new_node(ND_MUL, node, primary());
    else if (consume('/'))
      node = new_node(ND_DIV, node, primary());
    else
      return node;
  }
}

Node *primary() {
  if (consume('(')) {          // "(" expr ")" のほう
    Node *node = expr();
    expect(')');
    return node;
  }
  return new_node_num(expect_number());   // num のほう
}

規則と見比べると対応が機械的です。

• 右辺に出てくる非終端記号 → その名前の関数を呼ぶ
• 終端記号 → consumeかexpectでトークンを消費する
• * → for(;;)ループ
• | → if / else ifの分岐

ノードの構造体

typedef enum {
  ND_ADD, ND_SUB, ND_MUL, ND_DIV, ND_NUM,
} NodeKind;

struct Node {
  NodeKind kind;   // ノードの種類
  Node *lhs;       // 左辺
  Node *rhs;       // 右辺
  int val;         // kind が ND_NUM のときのみ使う
};

Tokenとよく似た形ですが、nextが1本だったところがlhsとrhsの2本に枝分かれしています。lhsはleft-hand side、rhsはright-hand sideの略だそうです。

1+2*3 を追ってみる

expr()
  mul()                 → primary() が 1 を読む
                        → 次のトークンは + なので * / のループに入らず NUM(1) を返す
  consume('+') が成功
  mul()                 → primary() が 2 を読む
                        → consume('*') が成功 → primary() が 3 を読む
                        → MUL(2, 3) を返す
  node = ADD(NUM(1), MUL(2,3))
  次は EOF なので return

自分で手を動かして描いた木と同じものが出てきました。カッコ付きの(1 + 2) * 3も追ってみます。

mul()
  primary()  → consume('(') が成功
             → expr() を呼ぶ → ADD(1, 2) を作る
             → expect(')')
             → ADD(1,2) をそのまま返す
  consume('*') が成功 → primary() が 3 を読む
  MUL(ADD(1,2), 3)

ここで大事なのは、カッコがノードとして木に残っていないことです。カッコは優先順位を変えるための指示にすぎず、木の形が決まった時点で役目を終えます。冗長な要素を残さないという意味で、この木は元の文字列から一段抽象化されている。だから抽象構文木と呼ばれてるのですか。

左結合になっている理由

node = new_node(ND_SUB, node, mul());

新しいノードを作るとき、それまで組み立ててきたnodeを左辺に置いて、新しく読んだものを右辺に置いています。1-2-3だとこうなります。

1周目: node = SUB(1, 2)
2周目: node = SUB(SUB(1,2), 3)

      -
     / \
    -   3
   / \
  1   2

左から順に積み上がるので(1-2)-3になり、正しく-4になります。もし新しいノードの右辺側に既存のnodeを置いてしまうと1-(2-3)の意味になって答えが変わります。左結合の演算子は既存のノードを左辺に、というのがルールなんだな。

自分の疑問の答え合わせ

読む前に書いた疑問がだいたい解けたのでまとめます。

• 子を持つノードは演算子になるのか: なります。ND_ADDからND_DIVまでは必ず子を2つ持ち、ND_NUMは必ず葉になります。演算子が葉に来たり数が内部ノードに来たりすることはありません
• 子を1つしか持たないノードは存在するのか: 今回の文法の範囲では出てきません。そして単項マイナスをどう実装するのかという疑問も、ここに繋がります。-xを子1つのノードとして表す手もありますが、記事の方式では-xを0-xに読み替えて、ND_SUBの左辺に0のノードを置くという形にします。つまり新しい種類のノードを増やさず、既存の二項演算に押し込んでしまう。葉に数でないものが入ってしまうという私の懸念は、そもそもマイナスをノードにしないことで消える、という解き方でした。思いつきませんでした(感動)。

スタックマシン

抽象構文木ができたので、次はそれをアセンブリに変換する段です。ここで出てくるのがスタックマシンという計算モデルでした。

なぜスタックが必要になるのか

これまで書いてきたコード生成はraxひとつを使い回すだけで済んでいました。加減算を左から順に潰していくだけなので、途中の値は常に1つしかなかったからです。

ところが木を扱うようになると、途中の値が複数同時に存在します。1+2*3なら、2*3を計算している間、左辺の1をどこかに取っておかなければなりません。式が深くなればなるほど取っておく値の個数は増えていきます。

汎用レジスタは16本しかないので、素朴にレジスタへ割り当てていくといつか足りなくなります。式の深さに制限を作りたくないので、いくらでも積める場所が欲しい。そこでメモリ上のスタックを使います。

スタックマシンという考え方

スタックマシンは、値を積むpushと、取り出すpopの2つの操作だけで計算を進める仮想的な機械です。演算命令は、スタックの上から必要な個数の値を取り出して、結果を積み直します。

1+2*3をこのモデルで書くとこうなります。

push 1
push 2
push 3
mul        ← 上の2つ(2と3)を取り出して掛けて、6を積む
add        ← 上の2つ(1と6)を取り出して足して、7を積む

これは逆ポーランド記法そのものですね。前の節で木を後行順で辿ると逆ポーランド記法になると書きましたが、まさにその出力先がスタックマシンだったわけです。木の形が計算順序を持っているので、辿った順に命令を並べるだけで正しい順番になります。基本情報をやった日を思い出すな。

x86-64をスタックマシンとして使う

x86-64は本来レジスタマシンですが、pushとpopという命令を持っているのでスタックマシンとしても使えます。

スタックの先頭を指しているのがRSPレジスタで、これをスタックポインタと呼びます。RSPが指す位置がスタックのてっぺんで、pushとpopはこのRSPを自動で動かしてくれます。

sub rsp, 8          RSPを8バイト分下げる
mov [rsp], rax      その位置にraxの値を書き込む

mov rax, [rsp]      RSPの位置から値を読む
add rsp, 8          RSPを8バイト分戻す

gen関数

木を受け取ってアセンブリを出力する関数です。

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

  printf("  push rax\n");
}

やっていることは木の後行順走査です。

• 数ノードなら、その値をpushして終わり
• 演算子ノードなら、左の子を処理し、右の子を処理し、それからpopして演算してpushする

グラフの言葉でいえば完全に帰りがけ順のDFSで、子を全部片付けてから自分の処理をするという形になっています。

再帰が成り立つ仕組み

この関数の正しさを支えているのは、次の一文に集約されると思いました。

gen(node)を1回呼ぶと、スタックの上にちょうど1つ値が増える。

これが守られているなら、gen(node->lhs)とgen(node->rhs)を続けて呼んだ時点で、スタックの上には必ず2つの値が乗っています。だからpopを2回して演算し、結果を1つpushすれば、gen全体としてもやはり1つ増えたことになって約束が保たれます。

この不変条件が成り立っているおかげで、どれだけ深くネストした式でも同じ4行のコードで処理できます。左の子がどんなに複雑な部分木でも、genを呼び終わればその評価結果が1つ積まれているという前提だけ信じればよいです。

popの順番が逆なのが大事

printf("  pop rdi\n");   // 先にこっち
printf("  pop rax\n");   // 後にこっち

gen(node->lhs)を先に呼んでいるので、スタックには左辺の値が下、右辺の値が上に積まれています。スタックはLIFOなので、最初にpopされるのは後から積んだ右辺です。

つまり、最初のpopで右辺がrdiに入り、次のpopで左辺がraxに入ります。そのうえでsub rax, rdiと書くことで左辺から右辺を引く形になります。

もしここを逆にすると1-2が1という答えになってしまいます。可換な加算と乗算では気づけず、減算と除算で初めて壊れるタイプの間違いなので、テストは引き算を必ず入れておきたいところです。

mainの変更

  // 抽象構文木を作る
  Node *node = expr();

  // アセンブリの前半部分を出力
  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");

  // 抽象構文木を下りながらコード生成
  gen(node);

  // スタックトップに式全体の値が残っているのでそれをraxにロードして返す
  printf("  pop rax\n");
  printf("  ret\n");

genを呼び終わった時点で、さきほどの不変条件からスタックの上には式全体の値がちょうど1つだけ残っています。

1+2*3 の生成結果を追う

ADD(NUM(1), MUL(NUM(2), NUM(3)))にgenをかけると、こういうアセンブリが出ます。右側にそのときのスタックの状態を書いてみました。

  push 1          [1]
  push 2          [1, 2]
  push 3          [1, 2, 3]
  pop rdi         [1, 2]        rdi = 3
  pop rax         [1]           rax = 2
  imul rax, rdi   [1]           rax = 6
  push rax        [1, 6]
  pop rdi         [1]           rdi = 6
  pop rax         []            rax = 1
  add rax, rdi    []            rax = 7
  push rax        [7]
  pop rax         []            rax = 7   ← mainの最後のpop
  ret

内側の2*3が先に計算されて6になり、それが1と足されて7になっています。木の深いところが先に潰れるという性質が、命令の並びとしてそのまま現れました。

いかにも冗長なpush raxのあと即pop rdiという並びが見えますが、ここは正しさを優先した素直な生成をしている段階で、記事でも後に最適化の話が出てくるようです。

乗算と除算のアセンブリ

加算と減算はaddとsubでそのままですが、乗除算は少し事情があります。

乗算はimul rax, rdiです。imulのiはintegerではなく符号付き整数(signed)を意味していて、符号を考慮した掛け算になります。

除算はdivではなくidivを使い、しかもその前にcqoという命令が必要でした。ここは独特です。

  cqo
  idiv rdi

idivは引数を1つしか取りません。被除数は暗黙にRDXとRAXの2本を連結した128bitの値として扱われ、除算の結果は商がRAX、余りがRDXに入ります。

つまりidivを呼ぶ前に、RDXとRAXを正しい被除数の形に整えておく必要があります。それをやるのがcqoで、RAXの値を128bitに符号拡張してRDXとRAXにセットしてくれます。RAXが正の数ならRDXは0、負の数ならRDXは全ビット1になります。

なぜスタックマシンにするのか

レジスタマシンとして真面目にコードを出そうとすると、どの値をどのレジスタに置くかを決めるレジスタ割り当てという難しい問題を解く必要があります。スタックに全部積む方式なら、その判断が一切要りません。

単項プラスと単項マイナス

いよいよ最初に目標として掲げられていた30+(4-2)*-5の-5の部分です。前の節で自分が気にしていた単項マイナスがここで回収されます(ワクワク)。

文法にunaryを足す

expr    = mul ("+" mul | "-" mul)*
mul     = unary ("*" unary | "/" unary)*
unary   = ("+" | "-")? primary
primary = num | "(" expr ")"

mulの中身がprimaryからunaryに変わり、その間に新しい階層が1本挟まりました。

unary = ("+" | "-")? primaryは、primaryの前に符号が0個か1個つくという意味です。?はあってもなくてもよいという記号なので、符号がなければただのprimaryとして通ります。前に整理した繰り返し0回の話と同じ構造ですね。どの階層も自分の担当が出てこなければ下をそのまま通すという性質です。

なぜmulとprimaryの間に入るのかというと、単項の符号は乗除算より強く結合するからです。-3*5は(-3)*5であって-(3*5)ではありません。今回の演算子では両者の答えが同じになってしまいますが、優先順位の高いものを下の階層に置くという原則からするとunaryはmulの下が正しい位置になります。

実装

Node *unary() {
  if (consume('+'))
    return primary();
  if (consume('-'))
    return new_node(ND_SUB, new_node_num(0), primary());
  return primary();
}

3行それぞれが文法の3つのケースに対応しています。

• +xはxと同じなので、符号を読み捨ててprimaryをそのまま返す
• -xは0-xに読み替えて、ND_SUBの左辺に0のノードを置く
• 符号がなければprimaryをそのまま返す

-3から作られる木はこうなります。

    -
   / \
  0   3

前の節で私は、単項マイナスに対応すると葉に数でないものが入ってしまうのではと心配していましたが、その心配はまるごと消えました。マイナスをノードとして表現せず、既存の二項減算に押し込んでしまう。新しいNodeKindも増えず、genに手を入れる必要もありません。

出力を追ってみる

-3は0-3と同じ木なので、出るアセンブリもそのままです。

  push 0
  push 3
  pop rdi
  pop rax
  sub rax, rdi
  push rax

さて一段落しました！ひとまずこれで基本的な機能が備わったはずです！
テストも多くなってきて気持ちよくなってきました。

$ make
0 => 0
42 => 42
5+20-4 => 21
 12 + 34 - 5  => 41
5+6*7 => 47
5*(9-6) => 15
(3+5)/2 => 4
-10+20 => 10
- -10 => 10
- - +10 => 10
0==1 => 0
42==42 => 1
0!=1 => 1
42!=42 => 0
0<1 => 1
1<1 => 0
2<1 => 0
0<=1 => 1
1<=1 => 1
2<=1 => 0
1>0 => 1
1>1 => 0
1>2 => 0
1>=0 => 1
1>=1 => 1
1>=2 => 0
OK

• コミットリンク