コンパイラの教科書を読み、サンプル実装をF#で再実装した
モチベーション
- 処理系実装は何度かやったことがあるが、処理系の授業を受けたことはなく、教科書的なものを読んだこともあまりない (気がする)
- タイガー本 (最新コンパイラ構成技法) は内容を読んだが、サンプルの実装をちゃんと追うところまではできていない
- 1冊、詳しく読み込んで全体の内容を理解しておくと今後の学習の基礎になりそうな気がした
どういう本か
電子通信情報系コアテキストシリーズ C-1 実践コンパイラ構成法 | コロナ社 (2017/07/25 発行)
- サンプルコードはOCaml
- C風のミニ言語のコンパイラを作る
- コンパイル対象としてx64アーキテクチャのみ扱う
やったこと
リポジトリ: playground/pcc
- 3章で字句解析器ジェネレータ(OCamllex)が解説されている
- 正規表現をNFA(非決定的オートマトン)にしてインタプリトするのは前にやったことがある (2019-08-31-parse-study)
- 改めて、字句解析の定義ファイルから字句解析器を作ってサンプル言語の字句解析に使うところまでやった
- 4章でパーサジェネレータ(OCamlyacc)、LLおよびLR構文解析が解説されている
- これも定義ファイルからLR(1)パーサの生成を試した
- LRパースは理解できた気がする
- ただしサンプル言語のパースはできなかったので、続きは再帰下降パーサを書いて進めた
- 5章は意味解析の解説
- 記号表 (シンボルテーブル) や型検査など
- 再帰関数の処理など、自前実装でつまづきがちなところが説明されていてよさそうだった
- 意味解析とコード生成のステージを分けない (コード生成の最中に意味解析を行う) ことでレイヤが減っていて、それも興味深かった
- 7章は実行時環境の話
- アセンブリの命令セット、メモリ (ヒープとスタック)、ABI・呼び出し規約など
- 各種演算に対応する命令セットやレジスタの解説が今回、一番ためになったかもしれない。インタプリタやC言語に帰着させるタイプのコンパイラでは学んでいなかったし、学びづらいため
- 8章はコード生成の解説
- 7章で解説したとおりに中間表現からアセンブリに変換する部分
- 分岐とループをラベルとジャンプにするところはバイトコードインタプリタの実装と似ていた
- サンプルコードを参考にしながら書いたので、アドレスの計算やどのレジスタを使うかといった選択にハマることがなくて楽だった。イチから考えるとそのへんが大変そう