出版書誌データベース

最新技法の実装および研究に不可欠な課題を凝縮・網羅！！　理論と実装の卓越した平衡

過去10年の間に、コンパイラを構築する方法には、いくつかの進展が見られた。まず、新しい種類のプログラミング言語が使用されるようになった。たとえば、動的メソッドをもつオブジェクト指向言語や、入れ子になった有効範囲や一級関数閉包をにつ関数型言語である。そしてこれらの言語の多くは、ごみ集めを必要とする。新しいコンピュータは大規模なレジスタセットをもつが、一方でメモリアクセスは大きなペナルティとなるので、命令のスケジューリングや命令やデータをローカルキャッシュに置くためのコンパイラの助けがあるほうが高速に実行できる。本書は、1学期あるいは2学期用のコンパイラコースの教科書として意図されている。本書を通じて学生は、コンパイラの様々な構成要素の背後にある理論、理論を実践へと結びつけるためのプログラミング技法、そしてコンパイラをモジュール化するためのインタフェースを学ぶことができる。インタフェースとプログラミング例を明確にかつ具体的にするために、それらをMLプログラミング言語で記述した。

第 I 部　コンパイラ基礎編

第1章　はじめに
1.1　モジュールとインターフェース
1.2　ツールとソフトウェア
1.3　木言語のデータ構造

第2章　字句解析
2.1　字句トークン
2.2　正規表現
2.3　有限オートマトン
2.4　非決定性有限オートマトン
2.5　ML-Lex：字句解析器生成系

第3章　構文解析
3.1　文脈自由文法
3.2　予測型構文解析
3.3　LR構文解析
3.4　構文解析器生成系の使用
3.5　エラー回復

第4章　抽象構文
4.1　意味動作
4.2　抽象解析木

第5章　意味解析
5.1　記号表
5.2　Tigerコンパイラの束縛
5.3　式の型検査
5.4　宣言の型検査

第6章　駆動レコード
6.1　スタッフフレーム
6.2　Tigerコンパイラのフレーム

第7章　中間コードへの変換
7.1　中間表現木
7.2　木への変換
7.3　宣言

第8章　基本ブロックとトレース
8.1　正準木
8.2　条件分岐の単調化

第9章　命令選択
9.1　命令選択アルゴリズム
9.2　CISCマシン
9.3　Tigerコンパイラの命令選択

第10章　生存解析
10.1　データフロー方程式の解
10.2　Tigerコンパイラの生存変数

第11章　レジスタ割付け
11.1　単純化による彩色
11.2　合併
11.3　既彩色節
11.4　グラフ彩色の実装
11.5　木に対するレジスタ割付け

第12章　コンパイラ制作

第 II 部　コンパイラ発展編

第13章　ごみ集め
13.1　マークスイープ回収法
13.2　参照カウント
13.3　複写回収法
13.4　世代別回収法
13.5　斬進的回収法
13.6　Bakerのアルゴリズム
13.7　コンパイラへのインタフェース

第14章　オブジェクト指向言語
14.1　クラス
14.2　データフィールドの単一継承
14.3　多重継承
14.4　クラスメンバーシップの検査
14.5　非公開なフィールドとメソッド
14.6　クラスの無い言語
14.7　オブジェクト指向プログラムの最適化

第15章　関数型プログラミング言語
15.1　単純な関数型言語
15.2　閉包
15.3　変更不能変数
15.4　インライン展開
15.5　閉包変換
15.6　効率的な末尾再帰
15.7　遅延評価

第16章　多相型
16.1　パラメトリック多相性
16.2　型推論
16.3　多相変数の表現
16.4　静的多重定義の解決

第17章　データフロー解析
17.1　フロー解析向けの中間表現
17.2　様々なデータフロー解析
17.3　データフロー解析を用いた変換
17.4　データフロー解析の高速化
17.5　別名解析

第18章　ループ最適化
18.1　支配節
18.2　ループ不変計算
18.3　帰納変数
18.4　配列境界検査
18.5　ループ展開

第19章　静的単一代入形式
19.1　SSA形式への変換
19.2　支配木の効率的な計算
19.3　SSAを用いた最適化アルゴリズム
19.4　配列、ポインタ、およびメモリ
19.5　制御依存グラフ
19.6　SSA形式への逆変換
19.7　関数型中間形式

第20章　パイプライニングとスケジュール
20.1　資源束縛のないループスケジューリング
20.2　資源束縛のあるループパイプライニング
20.3　分岐予測

第21章　メモリ階層
21.1　キャッシュの構成
21.2　キャッシュブロック整合
21.3　事前取出し
21.4　ループ交換
21.5　ブロック化
21.6　ごみ集めとメモリ階層

付録A　Tiger言語リファレンスマニュアル
A.1　字句について
A.2　宣言
A.3　変数と式
A.4　標準ライブラリ
A.5　Tigerプログラムの例