この資料の手順に従って作成するMiniMLコンパイラは,下図に示すとおり,構文解析部(字句解析含む)から始まり,全部で5つ(最適化に関連するフェーズを含めれば全部で7つ)のフェーズから構成される.
図中の丸いノードが各フェーズを表し,それらの前後に挟まっている四角いノードは,各フェーズの入出力データ(MiniMLプログラム,中間表現,またはARMアセンブリコード)を表す.
この図の流れに沿って各フェーズ(OCaml関数)を呼び出すメインモジュールは配布コード中ですでに実装されており,main.ml
に含まれている.また,各中間表現のデータ型も,関連するファイル中で定義済みである.そのため,この資料どおりにコンパイラを作成するのであれば,main.ml
を書き換えたり中間表現のデータ型を修正したりする必要はない.
基本的に,演習課題はこれらのフェーズを前から順に実装していくようになっている.先に述べたとおり,配布コード中の「式を計算するだけ」の偽の実装を本物の実装に置き換えることによって,コンパイラを完成に近づけていくこととなる.
以下,各フェーズについて,エントリ関数(main.ml
から呼び出される関数),そのフェーズが説明されている章,関連するOCamlファイル名,およびそのフェーズで行われる処理の概略を簡単にまとめておく.
-
Parser.toplevel
(フロントエンド.parser.mly
,lexer.mll
)構文解析(と少しばかりの後処理)を行う.
syntax.ml
中に定義された抽象構文木 (Abstract Syntax Tree, AST)を構築する. -
Normal.convert
(正規化.normal.ml
)ASTを正規形(normal form)に変換する.
-
Closure.convert
(クロージャ変換.closure.ml
)正規形を閉じた正規形 (closed normal form)に変換する.
-
Vm.trans
(仮想機械.flat.ml
,vm.ml
)閉じた正規形を仮想機械コードに変換する.また,変換の前処理としてコードの平滑化と名前の分類も行う(
Flat.flatten
). -
Arm_noreg.codegen
(コード生成.arm_spec.ml
,arm_noreg.ml
)仮想機械コードをARMのアセンブリコードに変換する.このフェーズでは,ARMの汎用レジスタを局所変数のために使用することのない素朴なコードを生成する.
-
Opt.optimize
(最適化.cfg.ml
,dfa.ml
,live.ml
,reg.ml
,opt.ml
)仮想機械コードに対する各種最適化およびレジスタ割付けを行い,レジスタ機械コードに変換する.仮想機械コードに対してデータフロー解析 (data-flow analysis, DFA)を行うことで,それらの処理に必要な情報を収集する.
-
Arm_reg.codegen
(レジスタ割付け.arm_spec.ml
,arm_reg.ml
)レジスタ機械コードをARMのアセンブリコードに変換する.レジスタ機械コードの仮想レジスタは,ARMの汎用レジスタにマッピングされる.
配布コードに含まれるその他のOCamlファイルについても簡単に触れておく.
misc.ml
- 諸々の補助関数を定義.
mySet.ml
- 集合を表わすデータ型と操作関数を定義.
myMap.ml
- 写像を表わすデータ型と操作関数を定義.キーの比較に
=
演算子ではなく==
演算子を用いていることに注意.敢えてこうしている(詳細はデータフロー解析). environment.ml
- 環境 (environment)を表わすデータ型と操作関数を定義.環境については講義「プログラミング言語処理系」のテキストを参照.インタプリタや型推論器以外だけでなく,コンパイラでもいくつかのフェーズで使用することになる(はず).
Note: どれかは内緒.
pretty.ml
- ソースプログラムや抽象構文木など,階層を持つデータ構造を人間に読みやすい形式で文字列化するための補助ライブラリ.
minimlc
コマンドの-v
オプションで中間表現を表示するのに用いられている.このファイルの中身について理解する必要はない.Tip: 興味のある人はPhilip Wadlerの論文を読んでみると楽しめるかも.
ARMアセンブリコードから機械語の実行ファイルへの変換,Raspberry Pi 3上での実行,および実行時間の測定方法については,アセンブリコードまでの変換を説明した後,実行環境で説明する.