出版書誌データベース

コンパイラの原理を学ぶ

原著は米国ポートランド大学を中心に幅広く教科書として採用され、3rd Editionを重ねるまでになっています。

本書は全3分冊でコンピュータ数学の基礎分野を網羅する新しい独習シリーズの第3冊目となり、プログラミング分野でも汎用性の高い「コンパイラ」の動作原理でもある「計算論（計算可能性）」に関して、解説しています。「正規言語とオートマトン」「文脈自由語」「チューリングマシン」そして「計算の概念（計算可能性）」、P/NP問題など、数学を学ぶ方はもちろんコンピュータの動作原理の研究やソフトウェア開発に携わる方にも関係の深いトピックの解説と演習がコンパクトにまとまった好著です。

『Binary Hacks』 『Write Great Code』 『The Artof Computer Programming』 など名著と呼ばれるコンピュータ書やチューリング、チョムスキー、ゲーデル、ラッセル＆ホワイトヘッド等の読者層に特にお薦めの一冊です。

第11章　正規言語と有限オートマトン

11.1　正規言語
　　　11.1.1　正規表現
　　　11.1.2　正規表現の代数
11.2　有限オートマトン
　　　11.2.1　決定性有限オートマトン
　　　11.2.2　非決定性有限オートマトン
　　　11.2.3　正規表現を有限オートマトンへ変換する
　　　11.2.4　有限オートマトンを正規表現へ変換する
　　　11.2.5　出力装置としての有限オートマトン
　　　11.2.6　有限オートマトンを表現して実行する
11.3　効率的な有限オートマトンを構成する
　　　11.3.1　正規表現からNFAへのもう１つのアルゴリズム
　　　11.3.2　NFAをDFAへ変換する
　　　11.3.3　最少状態のDFA
11.4　正規言語のトピックス
　　　11.4.1　正規文法
　　　11.4.2　正規言語の性質
11.5　章のまとめ

第12章　文脈自由言語とプッシュダウンオートマトン

12.1　文脈自由言語
12.2　プッシュダウンオートマトン
　　　12.2.1　受理の同値形
　　　12.2.2　文脈自由文法とプッシュダウンオートマトン
　　　12.2.3　プッシュダウンオートマトンを表現し実行する
12.3　文脈自由構文解析
　　　12.3.1　LL(k)文法による下向き構文解析
　　　12.3.2　上向き構文解析とLR(k)文法
12.4　文脈自由言語のトピックス
　　　12.4.1　文法を変換する
　　　12.4.2　文脈自由言語の性質
12.5　章のまとめ

第13章　チューリングマシンおよびそれと同値な計算モデル

13.1　チューリングマシン
　　　13.1.1　チューリングマシンの定義
　　　13.1.2　出力のあるチューリングマシン
　　　13.1.3　異なる定義
　　　13.1.4　万能チューリングマシン
13.2　チャーチ ＝ チューリングの提唱
　　　13.2.1　計算モデルの同値性
　　　13.2.2　単純なプログラミング言語
　　　13.2.3　帰納的関数
　　　13.2.4　文字列を変換するマシン
13.3　章のまとめ

第14章　計算の概念

14.1　計算可能性
　　　14.1.1　有効列挙
　　　14.1.2　停止問題
　　　14.1.3　全体問題
　　　14.1.4　その他の問題
14.2　言語の階層
　　　14.2.1　言語
　　　14.2.2　まとめ
14.3　計算量のクラス
　　　14.3.1　クラスP
　　　14.3.2　クラスNP
　　　14.3.3　クラスPSPACE
　　　14.3.4　扱いにくい問題
　　　14.3.5　完全性
　　　14.3.6　形式的計算量理論
14.4　章のまとめ

付録

ギリシャ文字
記号
参考文献

索引

訳：神林　靖