投稿 » 2025-12-01

コンパイラを一週間で作ろう

この記事は、理情 Advent Calendar 2025 の1日目の記事です。

どうも、自称「CPU実験2025 全班自作コンパイラ化応援団団長」です。

CPU実験¹では、OCamlで実装されたオリジナルのMinCaml(や移植版のmincaml-rs)を自班用に改造する班が多いかと思います。
しかし、慣れない言語で書かれた、他人が書いたプログラムを、コアのポテンシャルを引き出せるほど自由自在に書き換えるのは、つらいです。
大規模な書き換えにはコード全体を理解する必要があるなど、そのコストを考えるとフルスクラッチで自作するほうが最終的には速いかなと思ったので、私は最初から自作する道を選びました。
実際、最低限動作する(fibがコンパイルできるなど)ものを作るだけなら、それほど難しいものではありません。

1. コンパイラをコンパイラたらしめるもの

コンパイラは、高水準言語で書かれたコンピュータプログラムを、コンピュータが実行や解釈できる形式に、一括して変換するソフトウェア。

コンパイラ - Wikipedia

コンパイラに求める挙動は、【入力プログラム→(なんらかの処理)→機械語】というものでしょう。これさえ満たせば、まあコンパイラと呼んでいいのではないでしょうか。

この「なんらかの処理」が重要なわけですが、機械的に行うにはいくつかの工程を経る必要があります。
入力と出力の”ギャップ”はたとえば次のようなものです。

木構造 vs 一列
- 構造化された制御 vs ジャンプ
変数(型あり、配列なども持てる) vs レジスタ(型なし、サイズ固定)
- 同時に生存できる値の数の制限
入出力の抽象 vs 具体
(可読性 vs 速度)

これらの差を埋めるため、コンパイラは(たとえば)次のような段階を踏めばよいです。

字句・構文解析
命令列に変換、平坦化
バイナリ(機械語)に変換

2. 実装

ポイントは、下層から順に行うことです。そうすることで、動作確認が行いやすくなります。
出力されるプログラムが「正しい」かどうか判断するには、実際に実行するのが最も確実ですから、実行できる形を出力できるようにするのが最優先というわけです。
fibくらいならアセンブリでも人力で書けるので、これでテストしながら進めます。

2.0. 仕様策定

関数呼出規約

関数呼出まわりのルール(引数、戻り値、return address、スタックの扱い)は、それを基準に後のプログラムを作ることになるため、最初に決めるとよいです。
(授業など)チームで開発する場合はメンバーで相談してください。すでに決まっている場合でも再確認しましょう。

中間言語

コンパイルの処理の中で、フロントエンドとバックエンドの境界として、一度中間表現を経由することが定石となっています。
なお、この段階に文字列表現を用意しておくと移植性やデバッグのしやすさに貢献するのでおすすめです。

中間表現は、無制限に使える(数の制限がない)仮想レジスタ²を用い、再割り当てしない形式で「値の流れ」を表すものです。
LLVM IRを真似してもよいですが、自由なジャンプ命令を許すと解析がとても複雑になるため、通常命令+構造化された制御(分岐、関数呼び出し)³に制限するのがよいでしょう。

例として、私の策定した中間言語(の初期版)は以下のようになっています

fib(%n) {
  ; if n <= 1 then return n
  addi %one, zero, 1
  if (le %n, %one) {
    ret %n
  } else {
    ; f1 = fib(n - 1)
    subi %n1, %n, 1
    call %f1, fib, %n1
    ; f2 = fib(n - 2)
    subi %n2, %n, 2
    call %f2, fib, %n2
    ; return f1 + f2
    add %ans, %f1, %f2
    ret %ans
  }
}

2.1. アセンブラ

最速で作るならifを大量に並べればよさそう。私は、逆アセンブルとか統計とかを統一したい意図があったので、共通ライブラリのクレートを生やしてenumを使って構造化しながらじっくり作りました。

ラベルを扱うため、2-passのものが簡単で実装しやすいでしょう。
パーサーも出力もやることは最小限ですから、高々数時間あれば書けるはずです。

2.2. バックエンド

中間言語を入力としてアセンブリを出力するモジュールです。

主な仕事は、

関数呼出規約に基づいた関数呼び出しを出力
制御構造を平坦化
物理レジスタを割り当てる(加えてスピルの処理)

最適化のことはとりあえず考えずに、中間言語に現れるレジスタを「適当に」物理レジスタに割り当て、スピルしたらスタックフレームから復元する、という簡単なしくみで最低限動作するものは作れます。

2.3. フロントエンド

コード生成

制御以外の木構造を平坦化するのが主な仕事です。

入力されたプログラムソースの構文木を読んで、構造化された命令列(中間言語)を吐き出すモジュールです。
はじめは構文木を適当なデータ記述言語(JSONとか?)(またはプログラムに埋め込む)で与え、emitを実装します。

値の依存は基本的に木の根から葉の向きなので、評価は葉から順に行えば良いですね。
個人的にコンパイラの核心だと思っているので、動作を疑似コードで示します:

// 構文木のノードの値に対応する(仮想)レジスタと、その値を計算する命令列を出力する
Node::emit() {
  // 子をレジスタに変換し、そのコードを先に出力する
  regs = this.children.map(Node::emit);
  out = new_vreg();
  switch this.type {
    case ADD: write("add {out}, {regs.0}, {regs.1}");
    // ...
  }
  return out; // 値に対応するレジスタを返す
}

パーサ

これができたら、次にパーサーを書きます。
yacc系のツールを使ってもよいのですが、最近はPEGも選択肢に入ってきます。左再帰に弱いなどの欠点がある一方、十分高速に動作し(メモ化によって実質線形時間とかなんとか?わかってない)、動作が直感的で、Rustに使いやすいライブラリがあったので採用しました。

なお、MinCamlを実装する場合の注意点ですが、構文の定義など「実装が仕様」になっていて移植に苦労します。適当なテストコードを使いながら、挙動が一致するよう調整する必要があります。

クロージャ変換

クロージャ変換は関数型言語を対象とするなら必須となりますが、 ただのパズル なので、既存実装を参考にしながら頑張ってください。
とはいえ、多くのプログラムはクロージャを持たないか人力での変換が簡単なので、まずはクロージャを禁止したサブセット言語を対象として開発をすすめるとよいです。一度完成を達成してから実装するのでも間にあいます。

2.4. 完成

ここまでで、プログラムソースを入力として、機械語を出力する、というプログラムが出来上がりました。
複雑で大規模なプログラムだと思っていたコンパイラも、各レイヤに分けて開発してみればそれほど難しいところはないでしょう。

残るのは、出力されるプログラムを高速化する、最適化パートです。個人的には「頑張る💪」パートと呼んでいます。
ここから先は、何をどこに実装するかも含め、オリジナリティを発揮できる部分だと思うのと、記事の本題である「最低限動作する」ものを作成する、から離れてしまうので、ここでは扱わないこととします。

より実用的なコンパイラを目指すには、次のような機能を実装してもよいでしょう。

リンカ
デバッグ情報の付加
ランタイム・組み込み関数の整備
構文の拡張

3. おわりに

この記事で紹介したのは、コンパイラ開発の「はじめの一歩」に過ぎません。完成後は終わりのない改良の旅が待っています。しかしそれがコンパイラ開発の楽しいところだと思います。

読者のみなさんのフルスクラッチコンパイラ開発のきっかけになれば幸いです。(そして、コンパイラ係の皆の役に立ちますように…!)

東大理情3Aの授業(演習)「プロセッサ実験」「コンパイラ実験」。4人班で自作プロセッサを作ります ↩
(これをレジスタと呼ぶのおこがましいと思いませんか？値の束縛とか呼んでもいいと思う) ↩
ループは再帰を用いて書けるので、とりあえずは専用のしくみを用意しなくても大丈夫 ↩