2006/10/5 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎

Presentation on theme: "2006/10/5 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎"— Presentation transcript:

1 2006/10/5 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎
コンパイラ演習 第 1 回 2006/10/5 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎

2 実験II全体の目標 オリジナルの CPU を作る その CPU を対象とするコンパイラを作る その CPU とコンパイラでレイトレを動かす
メタな目標： 計算機システムが（ハードもソフトも） “black box” ではないことを身をもって感じる

3 コンパイラ演習の目標 オリジナルの CPU でレイトレが動くような （クロス） コンパイラを実装する
現代的なコンパイラが装備している機能 のいくつかを調査・実装する メタな目標： 言語処理系が “black box” では ないことを理解する

4 講義計画 講義方式 解説は15～45分程度、あとは各自で演習 佐藤 （TA） と山下 (TA) のどちらかが講義
講義での対象言語は O’Caml もどき、 記述言語は O’Caml

5 カリキュラム予定 イントロ、字句解析と構文解析 型推論、k正規形とα変換、最適化 クロージャ変換 仮想マシンコード生成 基礎編
レジスタ割り当て アセンブリ生成、末尾呼び出し最適化 Garbage Collection オブジェクト指向 Polymorphism 例外処理 パターンマッチ エスケープ解析 & リージョン推論 基礎編 応用編

6 課題 課題 共通課題 毎回出題される 全12課題を予定 コンパイラ係用大課題 応用編の内容を中心とした自由課題
5題程度から１題を選択して解答

7 単位条件（非コンパイラ係） 共通課題を 6 個以上提出 and 菅原助手側の課題をクリア

8 単位条件（コンパイラ係） シミュレータ or 自作 CPU 上でレイトレ完動 and 共通課題を 6 個以上提出 and
「美しい日本の ML コンパイラ」 を改造する形でもかまわない and 共通課題を 6 個以上提出 and 大課題を 1 個以上提出 菅原助手側の課題をクリア

9 美しい日本の ML コンパイラ 作者： 住井英二郎（東北大学助教授） 対象言語は ML サブセット、記述言語は O’Caml
SPARC アセンブリを生成 通称 “MinCaml”

10 美しい日本の ML コンパイラ 解説が付属 サンプルプログラムとしてレイトレも付属 実験IIレイトレ競技会のソースとは若干異なる
オープンソース 改良続行中 CVS で最新版をダウンロードすることを薦める

11 本演習のやり方 基本的には、MinCaml ソースを 読解・改造しながらコンパイラの内部構造を学ぶ
一から自分のコンパイラを作りたい という意欲ある人は、作ってもよい そのほうが、たぶん知識が身につく 他の言語が ML よりも好きでたまらない人は、 別の対象言語/記述言語を使用してもよい

12 イントロダクション

13 コンパイラとは何か？ ある言語のプログラムを、より低レベルな 言語に翻訳するシステム GCC （Cなど → アセンブリ）
ある言語のプログラムを、より低レベルな 言語に翻訳するシステム GCC （Cなど → アセンブリ） javac （Java → JVM） ocamlc （O’Caml → O’Caml VM） ocamlopt （O’Caml → アセンブリ） etc.

14 コンパイルの例 アセンブリ(機械語) ソースコード let rec gcd m n = if m = 0 then n else
.section ".text" gcd.7: cmp %i2, 0 bne be_else.17 nop mov %i3, %i2 retl be_else.17: cmp %i2, %i3 bg ble_else.18 sub %i3, %i2, %i3 b gcd.7 ble_else.18: sub %i2, %i3, %o5 mov %o5, %i3 …… … ソースコード let rec gcd m n = if m = 0 then n else if m <= n then gcd m (n - m) else gcd n (m - n) in print_int (gcd )

15 この大きなギャップを どうやって埋めるのか？
適切な中間言語を設定すれば、 ほとんど自明な記号変換の連続 MinCaml の行数 46 alpha.ml 22 anchor.ml 18 assoc.ml 38 beta.ml 45 main.ml ... 42 simm13.ml 105 sparcAsm.ml 27 syntax.ml 11 type.ml 163 typing.ml 164 virtual.ml 1634 total let lexbuf outchan l = Id.counter := 0; Typing.extenv := M.empty; Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f (iter !limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l)))))))))

16 なぜCやJavaではなく、 MLなのか？ 一言でいうと 「MLが一番楽だったから」

17 コンパイラの入力言語 各班で議論して仕様を決定 プリミティブはターゲットのアーキテクチャ に応じて決める
プリミティブはターゲットのアーキテクチャ に応じて決める プリミティブでない機能は ライブラリや syntax sugar （単純なソース to ソースの変換） として実装 本演習の説明では MinCaml を使用

18 対象アーキテクチャ 本演習では RISC CPU を想定 3-operand register machine レジスタの数は、多い

19 字句解析と 構文解析

20 理論 細谷先生の夏学期講義でやったし、 理解すべき分野が他に多くあるので省略

21 道具 （ocamllex & ocamlyacc） の使用法
抽象構文 (構文木を表すデータ型) を 決める (syntax.ml) 構文解析のルールを書く (parser.mly) 字句解析のルールを書く (lexer.mll) コンパイルしてリンクする

22 構造 syntax.ml parser.mly lexer.mll ocamlyacc ocamllex parser.ml
parser.mli lexer.ml コンパイラの フロントエンド

23 構文の定義 (syntax.ml) 式 即値： Unit、真偽値、整数、浮動小数 演算： 否定、単項マイナス、加減乗除、比較 条件分岐
let、letrec 関数適用 タプル生成、タプル分解 配列の生成、参照、更新

24 構文解析ルールの書き方(parser.mly)
Header and trailer (optional) そのまま出力にコピーされる トークンの定義 lexer.mll を参照のこと 優先順位と結合の定義 「if は右結合」「関数適用は if より強く結合」など 開始記号とその型の定義 ルール

25 parser.mly の抜粋 … | LET IDENT EQUAL exp IN exp %prec prec_let { Let(addtyp $2, $4, $6) } … … | IF exp THEN exp ELSE exp %prec prec_if { If($2, $4, $6) } …

26 字句解析ルールの書き方(lexer.mll)
Header and trailer (optional) そのまま出力にコピーされる よく使う正規表現への名前付け ルール Entry point: 入力を処理する関数 lexer.mll ではコメント開始・終了トークンを読むと entry point が変わる Entry point ごとに、正規表現とアクションの組のリストを記述

27 lexer.mllの抜粋 残りの入力の解析結果を 本入力の解析結果とする rule token = parse | space { token lexbuf } … | “let” { LET } … | ‘-’? digit { INT(int_of_string (Lexing.lexeme lexbuf)) } 文字列“let”の解析結果はトークンLETとする マッチした文字列を整数に変換してトークンにする

28 情報源 http://caml.inria.fr/ 今日の内容の詳細は “The Objective Caml manual”
Chapter 12 Lexer and parser generators (ocamllex, ocamlyacc) を参照

29 Conflict を解消するためのヒント OCamlMakefile を include しているMakefile 中に YFLAGS = -v と書いておくと、parser が使うステートマシンが *.output に出力されます

30 共通課題 今回の字句・構文解析器で、パターンマッチングの順序や優先順位を変更すると、何がどう変わるか。いくつかの例を挙げよ
例は構文木でもアセンブリコードでも何でもOK 自分で簡単な言語 (プログラミング言語でなくてもよい) を設定し、ocamlyacc とocamllex で 字句・構文解析器を作成せよ

31 (提出の必要がない)課題 班のメンバーで話し合って、何を言語のプリミティブとするか決めよ（もちろん後で変えてもよい）
(コンパイラ係) MinCamlの字句・構文解析器を改造するなどして、理解を深めよ 文字列定数の追加 クラス定義、例外、 パターンマッチなどの構文の追加

32 課題の提出先と締め切り 提出先: compiler-enshu@yl.is.s.u-tokyo.ac.jp
締め切り: 2 週間後 (10/19) の午後 1 時 Subject: Report 1 <学籍番号> <アカウント> 本文にも氏名と学籍番号を明記のこと

33 課題の提出についての注意 プログラムだけでなく、 説明・考察・感想なども書くこと 基本的にはメールの本文に解答を記述
プログラムだけでなく、 説明・考察・感想なども書くこと 基本的にはメールの本文に解答を記述 多くのソースを送る必要がある課題では、ソースをtarファイルなどに固めて メールに添付のこと

34 講義資料は http://www. yl. is. s. u-tokyo. ac
講義資料は に置きます 質問は まで

35 謝辞 本科目では、前々担当の住井英二郎先生、前担当の大山恵弘先生、佐藤秀明氏によって書かれた資料の多くを再利用させていただいております。 ここに感謝いたします。

36 MinCamlの論文 Eijiro Sumii “MinCaml: A Simple and Efficient Compiler for a Minimal Functional Language” In Functional and Declarative Programming in Education (FDPE05), Tallinn, Estonia, Sep