Moiz's journal

プログラミングやFPGAなどの技術系の趣味に関するブログです

「低レイヤを知りたい人のための Cコンパイラ作成入門」を読んで、オレオレコンパイラを作り始めた

はじめに

表題通りですが、Rui Ueyama氏の「低レイヤを知りたい人のための Cコンパイラ作成入門」というPDF本を読んでCコンパイラ的なものを作り始めましたよ、というダラっとした内容です。

発端

ツイッター等で知ったのですが、セキュリティキャンプというイベントで、Cコンパイラを書く、というコースがあったそうです。

www.ipa.go.jp

内容については当時各所で話題になりましたし、参加者のブログなども多数書かれているようです。 たとえばこちらなど、コースの内容や雰囲気がよくわかります。

0x19f.hatenablog.com

hsjoihs.hatenablog.com

こういったものを見て、コンパイラ作成に興味を持ち始めたところ、そのセキュリティキャンプ講師のRui Ueyama氏が「低レイヤを知りたい人のための Cコンパイラ作成入門」を書かれた事を知りました。

booth.pm

PDF本は有料ですが、同内容のものがウェブページでも無料公開されています1

低レイヤを知りたい人のための Cコンパイラ作成入門

これはやるしかないだろう、という事で自分もオレオレコンパイラを書き始めました。

なお、目標はCに近い言語のコンパイラを作って見ることでコンパイラがどのようにできているか学ぶ、ということなので、Cの規格に正しく従っていない部分が多々あります。

とりあえず書いてみる

自分はコンパイラについての知識はまったくなかったのですが、PDF本の内容が懇切丁寧なので、その内容を実行するにあたってはあまり問題なくすすめる事ができました。

内容的にはまず、数字を一つ読み込んで出力するだけという、考えられる限りでもっとも単純なプログラムをアセンブラコンパイルできるだけの「コンパイラ」を作成します。次にそこに、四則演算を導入して、変数を導入し、と進んでいきます。

執筆途中とはいえ、現在公開されている記事の最後まですすむと、こんな内容のコードがコンパイルできるようになります。

a = 4;
b = 5 * 2;
a + b;

これをコンパイルして、アセンブラにかけると、示されたとおりの計算を行って、14という返り値を返す実行ファイルを生成することができます。

本の内容が丁寧なので、最初にまったく何もなかったところからここまで、意外なほと短時間でたどりつけました。

別のコンパイラ入門書をよんでみる

こうやってコンパイラを書きすすめてきたわけですが、残念ながらPDF本の内容はまだここまでしかできていません。

そこで、まず他の本を一冊読んでみることにしました。

日本語のコンパイラ作成入門の電子書籍を探していたところ、こちらの本に出くわしました。

明快入門 コンパイラ・インタプリタ開発 (林晴比古実用マスターシリーズ)

明快入門 コンパイラ・インタプリタ開発 (林晴比古実用マスターシリーズ)

この本の内容は、スタックマシンをエミュレートしたVM上で動作するCサブセットのコンパイラソースコードの解説と、その関連技術の説明です。

とりあえずこちらの内容を一通り読んで、コードを手入力して実行させてみました2

スタックマシンのエミュレータ、という点が独特ですが、最初に読んだ「低レイヤ〜」でもスタックマシン的なコードを出力していたので、わりとすんなりなじめました。

次にどうする?

ここまで来たところで元の自作コンパイラにもどったのですが、次に何をするのか途方にくれてしまいました。

そこで、セキュリティキャンプに参加した方から、Rui氏のブログでセキュリティキャンプではどのような順に実装を進めたのか書いてあると教えていただきました。

note.mu

とりあえず、こちらの方針に従って以下のように進めていくことにしました。

  1. 引数なしの関数呼び出し
  2. 引数ありの関数呼び出し
  3. 引数なしの関数定義
  4. 引数ありの関数定義
  5. グローバル変数
  6. 配列
  7. ポインタ
  8. char型
  9. 文字列リテラル
  10. 構造体
  11. #include

書くぞ、書くぞ、書くぞ

その後はひたすら実装テスト実装テスト実装テストの繰り返しです。

毎回機能を追加する度にテストを追加し、ちょっとずつちょっとずつできることが増えて、とうとう文字列リテラルのところまですすみました。

また、セキュリティキャンプの参加者の方から(ときには講師の方から)いろいろと実践的なアドバイスをいただけたのは非常に助かりました。 特に、X86-64のABIではスタックポインタは16バイトアラインされている必用がある、というのと、rbxなどはcallee save、というのは自分ではきっと絶対に気が付かないではまっていたと思います。

そんなみなさんの協力もあって、今ではこんなコードをコンパイルすることができるようになりました。

void print(int a) {
  int b, c;
  b = 1;
  while(a >= 10 * b) {
    b = b * 10;
  }
  while(b > 0) {
    putchar((c = a/ b) + 48);
    a = a - c * b;
    b = b / 10;
  }
}

void print_string(char *a) {
  while(*a) {
    putchar(*a);
    a = a + 1;
  }
}

int fib(int a) {
  if (a <= 1) {
    return a;
  }
  return fib(a-1) + fib(a-2);
}

int main() {
  int i;
  print_string("Fibonacci seriese: ");
  for(i = 0; i < 20; i = i + 1) {
    print(fib(i));
    putchar(32);
  }
  putchar(10);
  return 0;
}

このコードをコンパイルすると以下のような結果が得られます。(m99ccというのが今回作ったコンパイラ、fibonacciが上記のプログラム。)

$ ./m99cc program/fibonacci.c > tmp.s && gcc -o tmp tmp.s && ./tmp
Fibonacci seriese: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

まだまだ不完全ではありますが、ゼロから初めて2ヶ月にしてはそれなりに形になっているのではないでしょうか。改めてご協力いただいた方々に感謝します。

(まだ終わってませんが。)

リポジトリ

これまでの結果はこちらのGithubリポジトリーにアップロードしてあります。

github.com

便利な資料

コンパイラ作成中に、ここまでで紹介した以外にもいろいろ便利なリソースについて教えていただいたので、ここにまとめておきます。

セキュリティキャンプの参加者のリポジトリ

github.com

github.com

こちらのShinya Kato氏(id:mizu0x19f)とはすじょい氏(id:hsjoihs)のお二人からは別途何度も有益なアドバイスをいただきました。

オンラインコンパイラGodbolt

godbolt.org

ブラウザ上でCやその他コードをコンパイルしてアセンブラの結果が見られる便利なサイトです。

変わった名前だなと思ったら本名のようです。まさに神ツール。

セキュリティキャンプ講師のスライド

docs.google.com

セキュリティキャンプの講師をされたhikalium( id:hikalium )氏のスライドです。

hikalium氏からは他にもいろいろ教えていただきました。上記のGodboltもhikalium氏経由の情報です。

C言語規格のドラフト

http://www.iso-9899.info/n1570.html

書籍 Compilers: Principles, Techniques, and Tools 2nd By Alfred V. Aho

入門書より範囲の広い本を、と思って買ってみましたがまだ読んでいません。

Intel® 64 and IA-32 Architectures Software Developer Manuals

Intel® 64 and IA-32 Architectures Software Developer Manuals | Intel® Software

インテルCPUのマニュアルです。 読まなきゃいけないのはわかるのですが、私は個人的な事情でこの書類を見ると鬱に...。


  1. 自分は応援も兼ねてPDFの方を購入しましたが、実際に参照したのはウェブページの方です。なおまだ執筆途中ということで、掲載されている内容はまだ途中までだそうです。

  2. 実はソースコードがダウンロードできるので、こんな事をする必要はなかったのですが、ダウンロード用URLが奥付に書いてあるのに気が付かず手で入力してしまいました。