ふつうのコンパイラをつくろう
ふつうのコンパイラをつくろう 言語処理系をつくりながら学ぶコンパイルと実行環境の仕組み
ソフトバンククリエイティブ
著者：青木峰郎
ふつうのまえがき
前提となる知識
前提としない知識
本書の構成
謝辞
第1章 コンパイラ作りを始めよう
1.1 本書の概要
本書のテーマ
本書で作成するコンパイラ
コンパイルの例
実行可能ファイルとは
コンパイルとは
プログラムの実行環境
1.2 コンパイルの過程
コンパイルの4つの段階
構文解析
意味解析
中間表現の生成
コード生成
最適化
まとめ
1.3 Ｃ♭コンパイラによるコンパイル
Ｃ♭コンパイラの必要環境
Ｃ♭コンパイラのインストール
Ｃ♭によるHello,World!
第2章 Ｃ♭とcbc
2.1 Ｃ♭言語の概要
Ｃ♭でのHello.World!
Ｃ♭で削除された機能
import宣言の仕様
インポートファイルの仕様
2.2 Ｃ♭コンパイラcbcの構成
cbcのソースツリー
cbcのパッケージ
compilerパッケージのクラス群
mainメソッドの実装
commandMainメソッドの実装
Java 5のgenerics
buildメソッドの実装
Java 5のforeach文
compilerメソッドの実装
第1部 ソースコードの解析
第3章 構文解析の概要
3.1 構文解析の手法
ソースコード解析の問題点
ソースコード解析の定石
字句解析、構文解析、意味解析
スキャナの動き
単語の種類と意味値
トークン
抽象構文木とノード
3.2 パーサジェネレータ
パーサジェネレータとは
パーサジェネレータの種類
パーサジェネレータの選択
3.3 JavaCCの概要
JavaCCとは
文法記述ファイル
文法記述ファイルの例
JavaCCの実行
JavaCCで生成したパーサの起動
日本語の処理
第4章 字句解析
4.1 JavaCCによるスキャナの記述
この章の目的
JavaCCの正規表現
固定文字列
連接
文字クラス
否定文字クラス
1回以降の繰り返し
0回以上の繰り返し
n回からm回の繰り返し
ちょうどn回の繰り返し
省略可能
選択
4.2 構造のない単語のスキャン
TOKEN命令
識別子と予約後のスキャン
マッチする規則の選択
数値のスキャン
4.3 トークンを生成しない単語のスキャン
SKIP命令とSPECIAL_TOKEN命令
空白の読み捨て
行コメントの読み捨て
4.4 構造を持つ単語のスキャン
最長一致の原則とその問題
状態遷移を使ったスキャン
MORE命令
ブロックコメントの読み捨て
文字列リテラルのスキャン
文字リテラルのスキャン
第5章 JavaCCによるパーサの記述
5.1 EBNFによる文法の記述
この章の目的
JavaCCでの文法の記述
終端記号と非終端記号
JavaCCのEBNF記法
連接
0回以上の繰り返し
1回以上の繰り返し
選択
省略可能
5.2 曖昧な文法とトークンの先読み
曖昧な文法
JavaCCの制限
左端共通部分のくくり出し
トークンの先読み
省略可能な規則と衝突
繰り返しと衝突
より柔軟なトークンの先読み
先読みに関する注意
第6章 構文解析
6.1 定義の解析
プログラム全体を表す記号
構文の単位
import宣言の構文
さまざまな定義の構文
変数定義の構文
関数定義の構文
構造体定義と共用体定義の構文
構造体メンバと共用体メンバの構文
typedef文の構文
型の構文
C言語とＣ♭の変数定義の違い
基本型の構文
6.2 文の解析
文の構文
if文の構文
if文と中括弧の省略
while文の構文
for文の構文
さまざまなジャンプ文の構文
6.3 式の解析
式の全体構造
exprの規則
条件式
二項演算子
6.4 項の解析
項の規則
前置演算子の規則
後置演算子の規則
リテラルの規則
第2部 抽象構文木と中間表現
第7章 JavaCCのアクションと抽象構文木
7.1 JavaCCのアクション
この章の目的
簡単なアクション
アクションの実行されるタイミング
意味値を返すアクション
終端記号の意味値の取り出し
Tokenクラスのフィールド
非終端記号の意味値の取り出し
構文木の構築
選択とアクション
繰り返しとアクション
この節のまとめ
7.2 抽象構文木とノード
Nodeクラス群
Nodeクラスの定義
抽象構文木の表示
ノードによる式の表現の例
第8章 抽象構文木の作成
8.1 式の抽象構文木
リテラルの抽象構文木
型の表現
TypeRefクラスが必要な理由
単項演算の抽象構文木
二項演算の抽象構文木
条件式の抽象構文木
代入式の抽象構文木
8.2 文の抽象構文木
if文の抽象構文木
while文の抽象構文木
複文の抽象構文木
8.3 宣言の抽象構文木
変数宣言リストの抽象構文木
関数定義の抽象構文木
宣言リストを表す抽象構文木
プログラム全体を表す抽象構文木
外部シンボルのインポート
まとめ
8.4 cbcパーサの起動
Parserオブジェクトの生成
ファイルのパース
パーサの起動
第9章 意味解析（1）参照の解決
9.1 意味解析の概要
この章の目的
抽象構文木のトラバース
Visitorパターンを使わない抽象構文木の処理
Visitorパターンによる抽象構文木の処理
Visitorパターンの一般化
cbcにおけるVisitorパターンの実装
意味解析に関わるcbcのクラス
9.2 変数参照の解決
問題の概要
実装の概要
Scopeツリーの構造
LocalResolverクラスのフィールド
LocalResolverクラスの起動
変数定義の登録
関数定義の処理
pushScopeメソッド
currentScopeメソッド
popScopeメソッド
ローカルスコープの追加
VariableNodeと変数定義の対応付け
スコープツリーからの変数定義の取得
9.3 型名の解決
問題の概要
実装の概要
TypeResolverクラスのフィールド
TypeResolverクラスの起動
型の宣言
型と抽象構文木のトラバース
変数定義の型の解決
関数定義の型の解決
第10章 意味解析（2）静的型チェック
10.1 型定義のチェック
問題の概要
実装の概要
有向グラフのループを検出するアルゴリズム
構造体・共用体の循環定義チェック
10.2 式の妥当性のチェック
問題の概要
実装の概要
DereferenceCheckerクラスの起動
例外SemanticErrorの捕捉
左辺値ではない式のアドレス取得のチェック
ポインタでない値のデリファレンスのチェック
暗黙のポインタ生成
10.3 静的型チェック
問題の概要
実装の概要
Ｃ♭における演算の型
暗黙の型変換
TypeCheckerクラスの起動
二項演算式の型チェック
暗黙の型変換の実装
第11章 中間表現への変換
11.1 cbcの中間表現
中間表現の表示
中間表現を構成するクラス
中間表現ノードのフィールド
中間表現の演算子と型
さまざまな中間表現
中間表現の目的
11.2 IRGeneratorクラスの概要
抽象構文木のトラバースと返り値
IRGeneratorクラスの起動
関数本体の変換
文である式の判別
11.3 制御構造の変換
if文の変換(1)概要
if文の変換(2)else節がない場合
if文の変換(3)else節がある場合
while文の変換
break文の変換(1)問題の定義
break文の変換(2)実装の方針
break文の変換(3)実装
11.4 副作用のない式の変換
UnaryOpNodeオブジェクトの変換
BinaryOpNodeオブジェクトの変換
ポインタに対する加減算の変換
11.5 左辺値の変換
左辺と右辺
左辺値と右辺値
cbcでの左辺値の表現
構造体メンバのオフセット
メンバ参照(expr.memb)の変換
左辺値変換の例外:配列と関数
メンバ参照式(ptr->memb)の変換
11.6 副作用を持つ式の変換
式の副作用とは
副作用を持つ式の変換方針
単純な代入式の変換(1)文である場合
テンポラリ変数の導入
単純な代入式の変換(2)式である場合
後置インクリメントの変換
第3部 アセンブリコードの生成
第12章 x86アーキテクチャの概要
12.1 コンピュータの仕組み
CPUとメモリ
レジスタ
アドレス
物理アドレスと仮想アドレス
さまざまなデバイス
キャッシュメモリ
12.2 x86系CPUの歴史
x86系CPUとは
32ビットCPUとは
インストラクションセットとは
IA-32の変換
IA-32の64ビット拡張～AMD64～
12.3 IA-32の概要
IA-32のレジスタ
汎用レジスタ
マシンスタックとは
マシンスタックの操作
マシンスタックの用途
スタックフレームとは
インストラクションポインタ
フラグレジスタ
12.4 データの表現と配置
符号なし整数の表現
符号付き整数の表現
負の整数の表現と2の補数
エンディアン
アラインメント
構造体の表現
第13章 x86アセンブラプログラミング
13.1 GNUアセンブラによるプログラミング
GNUアセンブラ
アセンブラ言語によるHello,World!
GNUアセンブラによるアセンブル
13.2 GNUアセンブラの文法
アセンブリ版Hello,World!
インストラクション
ディレクティブ
ラベル
コメント
ニモニックサフィックス
さまざまなオペランド
間接メモリ参照
x68インストラクションセットの概要
13.3 転送命令
mov命令
push命令とpop命令
lea命令
movsx命令とmovzx命令
符号拡張とゼロ拡張
13.4 算術演算命令
add命令
キャリーフラグ
sub命令
imul命令
idiv命令とdiv命令
inc命令
dec命令
neg命令
13.5 ビット演算命令
and命令
or命令
xor命令
not命令
sal命令
sar命令
shr命令
13.6 演算の制御
jmp命令
条件付きジャンプ命令(jz、jnz、je、jne、・・・)
cmp命令
test命令
フラグを取り出す命令(SETcc)
call命令
ret命令
第14章 関数呼び出しと変数
14.1 手続き呼び出し規約
手続き呼び出し規約とは
Linux/x86の手続き呼び出し規約
14.2 Linux/x86での関数呼び出し
呼び出し完了まで
関数本体の実行開始まで
呼び出し基への復帰まで
後始末完了まで
関数呼び出しのまとめ
14.3 Linux/x86での関数呼び出しの詳細
レジスタの保存と復帰
caller-saveレジスタとcallee-saveレジスタ
caller-saveレジスタとcallee-saveレジスタの活用
大きな値と浮動小数点数の返しかた
他のプラットフォームでの手続き呼び出し規約
第15章 式と文のコンパイル
15.1 コンパイル結果の調査
cbcでの調査方法
gccでの調査方法
15.2 x86アセンブリのオブジェクト表現とDSL
アセンブリを表現するクラス
アセンブリオブジェクトの表示
15.3 cbcのx86アセンブリDSL
DSLによるアセンブリオブジェクトの生成
レジスタの表現
既値とメモリ参照の表現
インストラクションの表現
ディレクティブ、ラベル、コメントの表現
15.4 CodeGeneratorクラスの概要
CodeGeneratorクラスのフィールド
CodeGeneratorクラスの処理の概要
compileStmtsメソッドの実装
cbcのコンパイル戦略
15.5 単純な式のコンパイル
Intノードのコンパイル
Strノードのコンパイル
Uniノードのコンパイル(1)ビット否定
Uniノードのコンパイル(2)論理否定
15.6 二項演算のコンパイル
Binノードのコンパイル
compileBinaryOpメソッドの実装
除算と剰余の実装
比較演算の実装
15.7 変数の参照と代入
Varノードのコンパイル
Addrノードのコンパイル
Memノードのコンパイル
Assigノードのコンパイル
15.8 ジャンプ文のコンパイル
LabelStmtノードのコンパイル
Jumpノードのコンパイル
CJumpノードのコンパイル
Callノードのコンパイル
Returnノードのコンパイル
第16章 スタックフレームの割り当て
16.1 マシンスタックの操作
cbcのスタックフレーム
スタックポインタ操作の方針
関数本体のコンパイル手順
16.2 引数とローカル変数へのメモリ参照割り当て
この節の概要
引数へのメモリ参照割り当て
ローカル変数へのメモリ参照割り当て：方針
ローカル変数へのメモリ参照割り当て
スコープ内のローカル変数の処理
アラインメントの計算
子スコープの変数への割り当て
16.3 仮想スタックによるテンポラリ変数の割り当て
仮想スタックの目的
仮想スタックのインターフェース
仮想スタックの構造
virtulPushメソッドの実装
VirtulStack#extendメソッドの実装
VirtulStack#topメソッドの実装
virtulPopメソッドの実装
VirtulStack#rewindメソッドの実装
仮想スタックの動作
16.4 マシンスタックアクセスのオフセット調整
この節の概要
StackFrameInfoクラス
使われているcallee-saveレジスタの算出
テンポラリ変数領域のサイズの算出
ローカル変数のオフセット調整
テンポラリ変数のオフセット調整
16.5 プロローグ・エピローグの生成
この節の概要
プロローグの生成
エピローグの生成
16.6 allocaの実装
alloca関数とは
実装の方針
alloca関数の影響
alloca関数の実装
第17章 最適化の手法
17.1 最適化とは
いろいろな最適化
最適化の例
定数の畳み込み
式の単純化
演算強度の低減
共通部分式の削除
不要命令の削除
関数インライン展開
17.2 最適化の分類
手法による最適化の分類
対象範囲による最適化の分類
適用段階による最適化の分類
17.3 cbcでの最適化
cbcにおける最適化の方針
cbcで実装した最適化
cbcでの最適化の実装
17.4 より強力な最適化
パターンマッチによる命令選択
レジスタ割り当て
コントロールフロー解析
大規模なデータフロー解析とSSA形式
まとめ
第4部 リンクとロード
第18章 オブジェクトファイルの生成
18.1 ELFファイルの構造
ELFの目的
ELFのセクションとセグメント
オブジェクトファイルの主要なELFセクション
readelfコマンドによるセクションヘッダの表示
readelfコマンドによるプログラムヘッダの表示
readelfコマンドによるシンボルテーブルの表示
readelfコマンドのオプション
DWARFフォーマットとは
18.2 グローバル変数のELFファイルでの表現
任意のELFセクションへの割り当て
一般的なELFセクションへの割り当て
.bssセクションの確保
コモンシンボル
グローバル変数に対応するシンボルの登録
シンボルの付帯情報の登録
コモンシンボルの付帯情報の登録
まとめ
18.3 グローバル変数のコンパイル
generateメソッドの実装
generateAssemblyCodeメソッドの実装
グローバル変数のコンパイル
既値のコンパイル
コモンシンボルのコンパイル
文字列リテラルのコンパイル
関数ヘッダの生成
関数のコードサイズの計算
まとめ
18.4 オブジェクトファイルの生成
asコマンド呼び出しの概要
GNUAssemblerクラスの呼び出し
asコマンド呼び出し
第19章 リンクとライブラリ
19.1 リンクの概要
リンクの実行例
gccとGNU ld
リンカが扱うファイル
よく使われるライブラリ
リンカの入力と出力
19.2 リンクとは
リンクで行われる処理
セクションのマージとは
再配置とは
シンボルの解決とは
19.3 ダイナミックリンクとスタティックリンク
2つのリンク手法
ダイナミックリンクの利点
ダイナミックリンクの欠点
ダイナミックリンクの実行例
スタティックリンクの実行例
ライブラリの検索規則
19.4 ライブラリの作成
静的ライブラリの作成
Linuxでの共有ライブラリの管理
共有ライブラリの作成
作成した共有ライブラリとのリンク
第20章 プログラムのロード
20.1 ELFセグメントのロード
mmapシステムコールによるファイルのマップ
プロセスのメモリイメージ
メモリ領域の属性
ELFセグメントとメモリ領域の対応
ELFファイルと対応しないメモリ領域
ELFファイルのロードの実装
20.2 ダイナミックリンクの過程
ダイナミックリンカローダとは
プログラムの起動から終了までの概要
ld.soの起動
カーネルから渡される情報
AUXベクタ
共有ライブラリの読み込み
シンボルの解決と再配置
初期化コードの実行
メインプログラムの開始
終了処理の実行
ld.soが解釈する環境変数
20.3 動的ロード
動的ロードとは
Linuxでの動的ロード
動的ロードの仕組み
20.4 GNU ldによるリンク
cbc用ldオプションの構築
Cランタイム
実行可能ファイルの作成
共有ライブラリの生成
第21章 位置独立コードの生成
21.1 位置独立コードとは
位置独立コードとは
グローバルオフセットテーブル(GOT)
GOTのアドレス取得
GOTを使ったグローバル変数アクセス
GOTを使ったファイル内グローバル変数へのアクセス
手続きリンクテーブル(PLT)
PLTエントリの呼び出し
位置独立な実行可能ファイル：PIE
21.2 グローバル変数参照の実装
GOTアドレスの取得
PICThunkメソッドの実装
重複した関数の削除と非可視属性
GOTアドレスのロード
locateSymbolsメソッドの実装
グローバル変数の参照
グローバル変数へのアクセス：位置独立コードの場合
関数のシンボル
文字列定数の参照
21.3 リンカ呼び出しの実装
実行可能ファイルの生成
generateSharedLibraryメソッド
21.4 プログラムの解析から実行まで
ビルドとロードの過程
字句解析
構文解析
中間表現の生成
コード生成
アセンブル
共有ライブラリの生成
実行可能ファイルの生成
ロード
第22章 本書を読み終えたあとに
22.1 書籍紹介
コンパイラ全体について
構文解析について
アセンブリ言語について
22.2 リンク・ロードについて
22.3 さまざまな言語機能
例外の実装に関する書籍
ガーベージコレクションとは
ガーベージコレクションに関する書籍
オブジェクト指向言語の実装
関数型言語
付録
A.1 参考文献
A.2 オンラインドキュメント
A.3 ソースコード
索引