コンパイラを作りたい？ この2本の論文を読めばよい (2008)
(prog21.dadgum.com)- ほとんどのコンパイラ教科書は理論中心で膨大なため、初心者が実際に動くコンパイラを実装しにくいという問題提起
- これを克服する実践的な資料として、Jack Crenshawの「Let’s Build a Compiler!」シリーズが紹介されており、単一パス構造の簡潔なPascalコンパイラを扱う
- このチュートリアルは、構文解析とコード生成の結合、最小限の最適化、そしてC・Forth版を通じて実験的な学習を支援する
- 2つ目の資料である**「A Nanopass Framework for Compiler Education」論文は、多数の単純な変換(pass)から成るモジュール型コンパイラ構造**を提示する
- 2つの資料を通じて実際の実装経験を積んだあとで、必要であれば**伝統的な教科書(Dragon Book)**を参照して学習を深められる
コンパイラ学習の現実と2本の重要論文
- 既存のコンパイラ書籍はあまりに膨大で難解なため、初心者が実際に動作するコンパイラを書くのは難しいという指摘
- ほとんどの本が正規表現変換、文法理論など広範な主題を扱い、実用的な出発点を提供していない
- そのため「コンパイラは難しい」という誤解と神話が形成される
- こうした認識を打ち破る代表的な資料として、**Jack Crenshawの「Let’s Build a Compiler!」**シリーズが紹介される
- 1988年に始まったこのチュートリアルは、Turbo Pascalレベルの単一パスコンパイラを扱う
- 構文解析とコード生成を結合した構造で、最小限の最適化だけを行う
- もともとはPascalで書かれ、その後C版とForth翻訳版も存在する
- Forth版は対話的言語という特性のおかげで、実験と理解がしやすい
- Crenshawシリーズの限界は、**プログラムの内部表現(抽象構文木、AST)**がない点
- Pascalでは木構造の操作が複雑なため省略されたが、Python, Ruby, Erlang, Haskell, Lispのような高水準言語では容易に実装できる
- これらの言語はもともと木構造データの操作のために設計されている
- 2つ目に薦められる資料は、Sarkar, Waddell, Dybvigによる論文
「A Nanopass Framework for Compiler Education」
- 中核となる考え方は、「コンパイラとはプログラムの内部表現を段階的に変換していく一連の過程」であるという点
- **数十〜数百個の単純な変換(pass)**から成る構造を提案する
- 各変換は可能な限り単純に保ち、変換同士の結合を避ける
- フレームワークは各パスの入力と出力を明示的に定義する
- 実装言語はSchemeで、動的型付けに基づいて実行時検証を行う
- この2つの資料を通じて実際にコンパイラを書いたあと、必要であればDragon Bookのような伝統的教科書でさらに学習を続けられる
- ただし、この2つの資料だけでも十分に実用的なコンパイラ制作経験を得られる
1件のコメント
Hacker Newsのコメント
Donald Knuth の『The Art of Computer Programming』は今も執筆中で、もはや コンパイラ を扱わない可能性が高い
私は筆者の主張には同意しない。『Dragon Book』（Aho ら著）の第2章は、それだけを読んでも十分に完結した コンパイラ入門書 になっている
もう一つの優れた入門書は Niklaus Wirth の『Compilers』で、100ページにも満たない分量の中に、完全なコンパイラのソースコードと明快な説明が収められている
この2冊のおかげで、高校生のときに自分でコンパイラを作れるくらいには学べた
実習中心で、実際のコンパイラ作成プロセスを追っていく本の方がずっと良いと思う
参考資料は このリンク にまとまっている
第2版ではデータフロー解析が追加されたが、現代のコンパイラ（GCC、LLVM など）の中核である SSA(Static Single Assignment) 形式はたった1ページしか扱っていない
最新のバックエンドを作るには、SSA 理論を別途学ぶ必要がある
TAOCP公式ページ 参照
Abdulaziz Ghuloum の論文 An Incremental Approach to Compiler Construction は、
「コンパイラは魔法のようなものだ」という認識を打ち砕き、インタプリタのように簡単にコンパイラを作れる ことを示している
Scheme 言語の大部分をサポートし、Intel x86 向けのアセンブリを生成するコンパイラを段階的に構築する過程を詳しく説明している
最近は メタコンパイラ、適応的コンパイル（Adaptive Compilation）、JIT コンパイラ などによって、コンパイラ技術は大きく進歩している
Alan Kay の研究グループ VPRI は複雑性の問題を扱っている
関連資料: Ometa 論文、Adaptive Compilation 動画、Alan Kay 講演
本を読むうえで良い助言を聞いたことがある — 本は RAM のようにランダムアクセス できる、というものだ
必要な部分だけ選んで読めば、分厚い本でも負担が軽くなる
ただし、自分が何を知らないのか分からない段階では、このやり方は通用しない。だからこそ、軽い入門書の重要性が大きい
今では『Crafting Interpreters』がよく勧められている
Nanopass 論文のリンクは切れていた
そこで『Crafting Interpreters』の要点をまとめた チートシート を作った
この本は単なるマニュアルではなく、経験ベースの学習書 であり、visitor パターンなど著者の楽しさがにじみ出ている
最近、遊びで トイコンパイラ を作っている
複雑なパース理論や DSL の代わりに Megaparsec パーサーコンビネータ を使っている
パースロジックが明快で再利用しやすく、従来の lexer/parser 分離の煩雑さがない
バグが少なく、エラー診断が優れており、多くの言語（C#、Rust など）でもこの方式が使われている
tree-sitter も優れているが依存関係が多い。一方、再帰下降なら 依存関係のない簡潔な実装 が可能だ
パーサーコンビネータ方式の利点は、lexer と parser の両方を同じ パーサー型 として扱える点にある
空白処理やトークン化の問題をきれいに解決できる
死んでいた Nanopass 論文のリンクは こちら で読める
私にコンパイラを教えてくれたのは、1978年の BYTE マガジンに載った Tiny Pascal コンパイラ の記事だった
最適化は Stanford の Ullman と Hennessy が行った夏期講座で学んだ
コードジェネレータは自作の独創的な方式だった
『Dragon Book』は持っているが、実際に読んだことはない
Nanopass アプローチの核心は パスの数 ではなく、各パスごとに 明示的な入力・出力言語 を定義することにある
この構造的な考え方のおかげで、実行前に多くのバグを捕まえられる
Crenshaw のチュートリアルも優れているが、この 言語の不変条件の管理 こそが、本当にスケールするコンパイラを作るための違いだ
UC Irvine 時代、Niklaus Wirth の弟子である Michael Franz 教授 の CS241 の授業で、最適化コンパイラ を実装したのを覚えている
DLX という仮想マシン向けのバイトコードを生成する課題だった
関連資料は DLX アーキテクチャの説明 と
レジスタ割り当てアルゴリズム参考画像 で見られる