電子通信情報系コアテキストシリーズ C-1 実践コンパイラ構成法

電子通信情報系コアテキストシリーズ C-1

実践コンパイラ構成法

滝本宗宏東京理科大教授博士（工学）著

コンパイラについて実践的に学ぶことができる教科書。コンパイラを記述するプログラミング言語にはOCamlを採用した。

ジャンル

発行年月日: 2017/07/25

判型: A5

ページ数: 220ページ

ISBN: 978-4-339-01933-9

在庫あり

2営業日以内に出荷致します。

定価

3,080円(本体2,800円+税)

カートに入れる

購入案内

内容紹介
まえがき
目次
レビュー
著者紹介

本書は，実践的にコンパイラを学ぶことができる教科書である。コンパイラを記述するプログラミング言語にはOCamlという関数型言語を採用した。また，目的コードには多くのPCで動作確認ができるようにx64コードを採用した。

言語処理系の研究の歴史は，計算機科学の分野の中でも，特に古い部類に入る。その長い歴史の中でも，最近のコンパイル技術の発展には目を見張るものがある。プログラミング言語に新しい概念が導入されるたびに新たなコンパイル手法が提案されてきたのはもちろんであるが，コード最適化に代表されるコンパイラ特有の技術も目覚ましい発展を遂げてきた。

一方，コンパイラの理論と実装の間のギャップはさらに広がったように見える。なぜなら，コンパイラの理論は，長年かつ多岐にわたるアルゴリズムの集積によってさらに複雑化しており，その実装は，新たな原始言語あるいは目的機械から生ずる多くの例外を，統合するよう求められるからである。大学や大学院における授業のなかで，このギャップを埋めて実践的なコンパイラのイメージを伝えることは，さらに難しくなった。
それでも，すでにコンパイラの知識を身に付けた研究者にとって，自分が組み立てた理論や手法のコンパイラ上への実装は，容易になったように見える。それは，コンパイラ共通基盤のような，実装の難しさをモジュール化しながら一部の改編によって研究成果を得ることができる多くのツールや方法が提供されるようになってきたからである。
同様な方法を，基礎を教える授業に適用するのは難しい。それは，アルゴリズムとその実装を直接結び付けて解説する必要性があることから，モジュール化をうまく利用できないからである。

そこで，従来から，自動生成系を導入することによって，その入力である宣言的な表現でコンパイラの一部を記述する試みがなされてきた。この試みは，授業の理解を深めるとともに，授業内でのコンパイラの実装を容易にするのに役立った。しかしながら，依然として，自動生成系の意味動作や，コンパイラのほかの部分は，C言語やJavaで記述されることが多く，自動生成される部分とそれ以外の部分との間には大きなギャップが残されていた。

本書は，自動生成系を利用するとともに，コンパイラを記述するプログラミング言語に，OCamlという関数型言語を採用している。OCamlは，型付きの強い言語でありながら，型推論機構によって，型を指定する必要がほとんどない。さらに，組やリストといったデータ構造を表現する構文を備えており，新しいデータ構造も容易に定義することができる。このOCamlの勘弁な記述によって，例えば，アルゴリズムの説明を行う際にも，仮想言語を用いることなく，OCamlの記述を直接に見せて進めることもできるであろう。
そうはいっても，OCamlは，C言語やJava言語のように，多くの大学で教えられているプログラミング言語というわけではない。多くの場合，コンパイラの授業のために，わざわざ新しいプログラミング言語を学ぶということになるかもしれない。そのような場合のために，本書の最初には，プロジェクトを実施するために必要最低限のOCamlへの入門を載せた。

本書のもう一つの特徴は，機械コードとしてx64コードを採用していることである。一般性を排し，特定の多くのPCで動作できるコードを採用することによって，具体性を高め，課題や自主開発を通じた独自の発展を促すことが狙いである。なるべく学生自身のPCで動作確認ができるように，Linux，Mac OS X，Cygwinで動作するように心がけた。

本書中で紹介したソースコード，また内容をよりよく理解するための練習問題はWebで提供するので，是非活用していただきたい。
本書の内容は，著者がここ数年，東京理科大学，慶應義塾大学，東京工業大学の学部学生を対象に担当してきたコンパイラの講義資料をベースにしている。OCamlについては，東京理科大学の情報科学科の学生が，演習をとおして使用した経験があるだけであった。また，慶應義塾大学と東京工業大学では，関数型言語を使用するのも初めてという学生が多かったが，実装課題においては優れたレポートが多く見られたことを付け加えておきたい。

2017年5月滝本宗宏

1.　はじめに
1.1　言語処理系
1.2　コンパイラ
　1.2.1　コンパイラの構成
　1.2.2　開発ツールと記述言語

2.　記述言語
2.1　コンパイラの記述とOCaml
2.2　OCamlの基本
　2.2.1　実行と基本型
　2.2.2　変数束縛
　2.2.3　関数定義
2.3　複雑な型の利用
　2.3.1　構造を持つ型
　2.3.2　パターンマッチング
　2.3.3　便利な高階関数
2.4　型の定義
　2.4.1　レコード
　2.4.2　バリアント
2.5　そのほかの重要構文
　2.5.1　let-rec-andとtype-and
　2.5.2　参照型
　2.5.3　例外
2.6　インタプリタの作成
　2.6.1　プログラムの木表現
　2.6.2　環境
　2.6.3　意味関数
　2.6.4　インタプリタの完成

3.　字句解析
3.1　字句解析の概観
3.2　トークンの指定
　3.2.1　正規表現
　3.2.2　Lexのトークン指定
3.3　有限オートマトンによる実現
　3.3.1　有限オートマトン
　3.3.2　DFAとその利用
　3.3.3　正規表現からNFAへの変換
　3.3.4　NFAからDFAへの変換
　3.3.5　状態の最小化
3.4　Lexを用いた字句解析器の実現
3.5　Simpleコンパイラの字句解析器

4.　構文解析
4.1　構文の指定
4.2　文脈自由文法
　4.2.1　導出
　4.2.2　解析木と曖昧な文法
　4.2.3　曖昧でない文法への変換
4.3　予測型構文解析
4.4　FIRST集合とFOLLOW集合
　4.4.1　FIRST集合を求めるアルゴリズム
　4.4.2　FOLLOW集合
4.5　予測型構文解析器の実現
　4.5.1　予測型構文解析表
　4.5.2　左再帰の除去
　4.5.3　左くくり出し
　4.5.4　エラー回復
4.6　LR構文解析
　4.6.1　LR(0) 構文解析器の実現
　4.6.2　SLR 構文解析
　4.6.3　LR(1) 構文解析
　4.6.4　LALR(1) 構文解析
　4.6.5　文法クラスの関係
4.7　YaccとSimple言語の構文解析器の実現
　4.7.1　OCamlyaccの概観
　4.7.2　曖昧な文法の利用
　4.7.3　OCamlyaccのエラー回復
　4.7.4　OCamllexとの連携
4.8　抽象構文木
4.9　Simpleコンパイラの構文解析
　4.9.1　文
　4.9.2　宣言
　4.9.3　左辺値
　4.9.4　式
　4.9.5　構文解析の実現

5.　意味解析
5.1　記号表
　5.1.1　有効範囲と記号表
　5.1.2　記号表の実現
　5.1.3　記号表の登録情報
5.2　型検査
　5.2.1　型
　5.2.2　式の型検査
　5.2.3　宣言の処理

6.　実行時環境
6.1　x64アセンブリ言語
　6.1.1　x64アセンブリコードの概観
　6.1.2　メモリの構成
　6.1.3　x64の命令
6.2　関数呼出しと駆動レコード
　6.2.1　高階関数
　6.2.2　スタックフレーム
　6.2.3　呼出し規約
　6.2.4　非局所データの参照

7.　コード生成
7.1　コード生成の準備
7.2　式のコード生成
　7.2.1　定数と変数
　7.2.2　算術演算
　7.2.3　関数呼出し
7.3　文のコード生成
　7.3.1　代入文
　7.3.2　Cライブラリを呼び出す仮想関数
　7.3.3　return文
　7.3.4　手続き呼出し
　7.3.5　関係演算と分岐
　7.3.6　ブロックのコード生成
7.4　宣言の処理
　7.4.1　型宣言の処理
　7.4.2　関数のコード生成
7.5　プログラムのコード生成
7.6　Simpleコンパイラの完成
7.7　コード最適化
　7.7.1　冗長な命令の削除
　7.7.2　制御フローの最適化

付録　Simple言語
A.1　言語マニュアル
　A.1.1　プログラム
　A.1.2　字句
　A.1.3　宣言
　A.1.4　文
　A.1.5　式
A.2　Simple言語のプログラム例
　A.2.1　ユークリッドの互除法
　A.2.2　再帰を用いた単純ソート
A.3　Simpleコンパイラプログラム

引用・参考文献
索引