1人でがんばる自作Cコンパイラ

Rustで作る自作Cコンパイラ

はじめに

セキュリティキャンを皮切りに自作Cコンパイラがとてもはやっていました。
たのしそー僕もやりたい!!!!でもどうやるんだ???
しかし僕の周りには知る限りではコンパイラに強い人はいませんでした。
友達がいないわけではありません
誰にも頼ることなくCコンパイラを作るのは難しいのでは!?
でもコンパイラは魔法みたいでいやだから知りたい。 本とかいろいろ眺めてみてもさっぱりわからなかったので誰でもできる方法はないかなーと考えたのが9ccをお手本にすることでした。 ということで9ccのファーストコミットからすべてRustにしてみました。 9ccrui314さんがやられているCコンパイラです。 9ccのコードは可読性がとても高くとてもやりやすかったです。9cc です。
おそらくこの方法で作るCコンパイラは事前知識はほとんど必要なくできると思います。
正直、やるだけだと思います(本当に シュッ です(ホンマ))。
もし同じようなことをやりたい人の参考になればawesomeです。

できたもの

できあがっているブツ: r9cc

9ccの前作である8ccでも同じことをチャレンジしていたのですが
行き詰っていた & 9ccがでた
ということで9ccの方に切り替えました。 ということで実は2度目のチャレンジです。

r9ccではコミットメッセージが大文字で始まるものが9ccから単純に移植しているものです。 小文字で始まるものは独自のリファクタリングだったり独自機能だったりします。 そろそろ日本語で書くのが疲れたので趣味で作ったr9ccでもこのくらいのコードならコンパイルできるぜっていうのを読者に見せつけます。

int fibdp[100];

int fib(int n) {
  if (n == 0 || n == 1) {
    return n;
  } else if (fibdp[n] != 0) {
    return fibdp[n];
  } else {
    fibdp[n] = fib(n-2) + fib(n-1);
    return fibdp[n];
  }
}

int main() {
  for (int i = 0; i < 100; i++)
    fibdp[i] = 0;
  int ans = fib(46);
  printf("%d\n", ans);
  return 0;
}

他にもこれくらいなら動きます。

  • 四則演算
  • 論理演算
  • ローカル変数
  • グローバル変数
  • 引数[あり|なし]の関数呼び出し
  • 引数[あり|なし]の関数定義
  • 配列
  • ポインタ
  • ++/--
  • char/int型
  • 文字列リテラル
  • 構造体
  • extern
  • #include
  • コメント文

r9ccの独自機能として配列の初期化時の代入も作ってみたのでこんなのも動きます。

int main() {
  int x[3] = {10, 11, 12};
  return x[1];
}

これだけでも結構いろいろなCのコードがコンパイルできてびっくりしました。

気を付けたこと

なにをしてるか把握する

おそらく各コミットを何も考えないででRustに書き換えることも可能です。 このように何もわからないままでもやり続けれてしまうことが1番怖いところだと思います。 Rustの力は上がるかもしれませんが本質であるコンパイラを知ることはできません。 Cじゃないの方が頭を使うかなと思ってRustにしました。 正直Cでもよいと思います。 できるだけ自分が作業しているコミットがなにをしているのかを意識して実装しました。 以下の手順で読んでみてコミット全体を把握してから実装することを徹底していました。

  1. コミットメッセージを読む
  2. 追加されたテストコードを読んでみる
  3. コード全体を読む

これに加えて今やってるコミットの+5コミット位を眺めて大まかな流れを把握していました。
独自機能を実装してみるのも自分がきちんとコードを把握できているのかチェックするのにはよいと思います。

ちょっとずつ

r9cc最初のコミットはこんなもんです。 9cc最初のコミットももちろんそうです。 数字を返すだけです。
こうみると誰でも出来そうじゃないですか!?
最初は型なんかありませんでした。
構文解析だけを先に作るという方針ではなく、アセンブリを出力するところまでの全体を均等的に作っていきます。 でかいものを作りたい気持ちはありましたが、ちょっとずつやっていきました。

変数名や順序(追記 2018-10-13)

変数名や関数の順番をr9ccとできるだけ一緒になるようにしました。 r9ccには関数が書かれている場所(?)順番(?)にも意味を持っているところがあります。 変数名や関数名もできるだけ一緒にしたほうがわかりやすくなると思います。

モチベーション

僕の周りにはコンパイラに興味のある人は少なかったためコンパイラについて話す相手はいませんでした。
そうなると自分のとても強い意志でがんばるかどうにかしてモチベーションを保つ必要がありました。
僕には強い意志を持つ自信がなかったのでモチベーションを保つ方法を考えました。
一人でやるときの大きな壁がここだと思います。
目標を持つことでモチベーションを保つことができると思います。
まず、大きな目標としてrui314さんの記事でも述べられていますがセキュリティキャンプではセルフホストを設定していたみたいです。 r9ccはRustで書いているのでセルフホストはできないので今回はペアレントホストにしました。
ペアレントホストは勝手に僕が考えたのですが、参考にしている9ccをコンパイルできるということです。
ただ、この目標だけだとモチベーションを保てそうになかったのでもう少し小さな目標を考えました。
小さな目標は9ccの適当なコミットを目標にしました。
コミットの選び方は自分がわくわくするものを選んで勝手に目標にしていました。
僕が選んだの

コミットメッセージのタイトルだけでもわくわくしませんか。うん、しますね。
ここまで行くと#includeが動くとか楽しみすぎでしょというモチベーションで少しずつやっていきました。

exampleも積極的に足していくとテンション爆上がりです。
9ccだとnqueen.cだけですが、 r9ccではfib.cprime.cも足してみました。 自分が書いたコードがコンパイルできた時はたのしー。

終わりに

とりあえず#includeまでできたので記事にしてみました。 r9ccを作ることでコーディングはもちろんですが全然わからなかったコンパイラの世界が垣間見れたかなと思います。 今後はペアレントホスト目指してちょっとずつ進んでいきます。 自作Cコンパイラ人口が少しでも増えれば面白いかなと思います。
自作Cコンパイラはやっていてめちゃめちゃ楽しいのでおすすめです!
Rustまだまだ初心者なのでこんな書き方の方がいいよ的なプルリク待ってます。
Rust固有のコンパイラを作るときに難したかった点はまた違う記事で書こうと思います。
ワタシ スコシ ホンノスコシ シーゲンゴデキル
くらいは言っても許されるかもしれない。
このような機会を与えてくれた9ccに感謝感謝です。 plz awesome.

追記(2018-10-13)

C言語ぽくまで動くまでには1.5週間くらいでした。 #includeができるまでは2ヵ月くらいでした。 もし自作コンパイラやってみようと思ってくれた方で質問や困ったことあったらTwitterで DMなりメンションをもらえればできるだけ考えます!

学べたこと

  • アセンブリ
  • C言語の挙動
  • いろいろなレジスタの役割
  • スタックについて強くなった

tcfm

rui314さんがやられているTuring Complete FMの紹介をします。
Cコンパイラの話など主に低レイヤの話が聞けます。
世の中にはすごい人しかいないのではと思えます。