計算機科学実験及演習4（コンパイラ）
京都大学の計算機科学実験及演習4（コンパイラ）
MiniMLというML言語のサブセットのコンパイラをOCamlを用いて作成
コンパイラのターゲット言語はARMアセンブリ言語、動作確認にはRaspberry Pi 3を用いる
こちらも気になる
参考
京都大学工学部専門科目「プログラミング言語処理系」講義資料
計算機科学実験及演習4 (コンパイラ) 実験資料
Gitリポジトリ
課題リスト
1 はじめに
MiniMLのサンプル
code:ocaml
let multiplicand = 8 in
let rec multiply8 = fun n ->
if n < 1 then
0
else
multiplicand + multiply8 (n+-1)
in
let apply = fun f -> fun x -> f x in
apply multiply8 9;;
ビルド
make して minimlc を実行してみる。1+2;; などを入力するとダミーのアセンブリコードが出力される。
code:sh
$ make clean; make
$ ./minimlc
# 1+2;;
.text
.align 2
.global _toplevel
_toplevel:
_toplevel_ret:
bx lr
#
1.2 MiniMLコンパイラの全体構成
1. Parser.toplevel（フロントエンド）
parser.mly, lexer.mll
構文解析を行い、抽象構文木（AST）を返す
2. Normal.convert（正規化）
normal.ml
ASTを正規形（normal form）に変換する
3. Closure.convert（クロージャ変換）
closure.ml
正規形を「閉じた正規形（closed normal form）」に変換する
4. Vm.trans（仮想機械）
flat.ml，vm.ml
閉じた正規形を仮想機械コードに変換する．また，変換の前処理としてコードの平滑化と名前の分類も行う（Flat.flatten）
5. Arm_noreg.codegen（コード生成）
arm_spec.ml，arm_noreg.ml
仮想機械コードをARMのアセンブリコードに変換する．このフェーズでは，ARMの汎用レジスタを局所変数のために使用することのない素朴なコードを生成する
6. Opt.optimize（最適化）
cfg.ml, dfa.ml, live.ml, reg.ml, opt.ml
仮想機械コードに対する各種最適化およびレジスタ割付けを行い，レジスタ機械コードに変換する．仮想機械コードに対してデータフロー解析 (data-flow analysis, DFA)を行うことで，それらの処理に必要な情報を収集する
7. Arm_reg.codegen（レジスタ割付け）
arm_spec.ml, arm_reg.ml
レジスタ機械コードをARMのアセンブリコードに変換する．レジスタ機械コードの仮想レジスタは，ARMの汎用レジスタにマッピングされる．
https://gyazo.com/ce3c723146b15cf0f8afc50404e3ecf6
2 フロントエンド
課題2 フロントエンド
MiniMLの文法規則に従うMiniMLプログラムを入力とし，以下のsyntax.mlにより定義される抽象構文木を返す字句解析器・構文解析器を作成しなさい．配布コードのlexer.mll，parser.mlyには，講義テキスト3.5節のML4言語に相当する文法定義がすでに含まれている．
code:syntax.ml
exception Error of string
let err s = raise (Error s)
type id = string
type binOp = Plus | Mult | Lt
type exp =
Var of id
| ILit of int
| BLit of bool
| BinOp of binOp * exp * exp
| IfExp of exp * exp * exp
| LetExp of id * exp * exp
| FunExp of id * exp
| AppExp of exp * exp
| LetRecExp of id * id * exp * exp
| LoopExp of id * exp * exp (* loop <id> = <exp> in <exp> *)
| RecurExp of exp (* recur <exp> *)
| TupleExp of exp * exp (* (<exp>, <exp>) *)
| ProjExp of exp * int (* <exp> . <int> *)