ソフトウェア科学を学ぶために |
まえがき |
学習の手引き |
1 言語処理系とそのなかま |
1.1 プログラム言語とその処理 2 |
1.2 コンパイラのなかま 7 |
1.3 コンパイラとプログラミング環境 10 |
第1章のまとめ・演習問題1 12 |
2 コンパイラのあらまし |
2.1 コンパイラの構成 16 |
(a) 字句解析 19 |
(b) 記号表 22 |
(c) 構文解析 24 |
(d) 意味解析 34 |
(e) 中間コード生成 37 |
(f) 最適化 41 |
(g) コード生成 43 |
2.2 誤り処理とエラーメッセージ 45 |
2.3 コンパイラの物理の構造 47 |
(a) パス 47 |
(b) コンパイラのさまざまな構成 49 |
(c) フロントエンドとバックエンド 50 |
2.4 コンパイラ生成系 51 |
第2章のまとめ・演習問題2 53 |
3 字句解析 |
3.1 字句解析のあらまし 56 |
3.2 正規表現と有限オートマトン 58 |
(a) 正規表現 58 |
(b) 有限オートマトン 61 |
(c) 正規表現から非決定性有限オートマトンへ 64 |
(d) 非決定性有限オートマトンから決定性有限オートマトンへ 67 |
(e) 決定性オートマトンの状態数の最小化 70 |
3.3 字句解析器 73 |
(a) 字句解析器の構成 73 |
(b) 文字読取り器 74 |
(c) 文字読取り器の効率化 77 |
(d) 字句読取り器 80 |
(e) 字句読取り器の効率化 88 |
(f) 字句読取り器についての補足 88 |
3.4 字句解析における誤り処理 89 |
3.5 字句解析器生成系 90 |
第3章のまとめ・演習問題3 93 |
4 構文解析 |
4.1 構文解析のあらまし 98 |
4.2 文脈自由文法と構文の記述 99 |
(a) 文脈自由文法 99 |
(b) 導出と還元 106 |
(c) 解析木 108 |
(d) 文法のあいまいさ,演算子の優先順位と結合性 110 |
(e) 正規右辺文法 118 |
4.3 種々の構文解析法と構文誤り処理 120 |
(a) 文脈自由文法と構文解析法との関係 120 |
(b) 構文解析器と他のフェーズとの協同 122 |
(c) 構文誤りの処理 123 |
4.4 下向き構文解析 126 |
(a) 後戻りつき下向き構文解析 126 |
(b) 下向き構文解析の問題点 129 |
(c) 予測的構文解析 136 |
(d) 後戻りなしの再帰降下構文解析 137 |
(e) 非再帰予測的構文解析 144 |
(f) FIRST,FOLLOW,DIRECTOR集合と構文解析表の計算 148 |
(g) LL(1)文法 157 |
4.5 下向き構文解析における誤り処理 159 |
4.6 上向き構文解析 161 |
(a) シフト還元構文解析 162 |
(b) 演算子順位構文解析 165 |
(c) LR構文解析 170 |
4.7 LR構文解析における誤り処理 206 |
4.8 構文解析法の比較 209 |
4.9 構文解析器生成系 211 |
第4章のまとめ・演習問題4 217 |
5 意味解析 |
5.1 意味解析のあらまし 222 |
5.2 属性文法 223 |
(a) 属性文法のあらまし 223 |
(b) 属性評価 228 |
(c) 属性文法の定義 231 |
5.3 プログラム言語の意味解析 233 |
(a) スコープ規則の意味解析 233 |
(b) 宣言部の意味解析 241 |
(c) 型の解析 249 |
5.4 意味誤りの処理 255 |
5.5 記号表とその処理 257 |
(a) 記号表内の情報 257 |
(b) 記号表の操作とデータ構造 259 |
(c) 記号表における入れ子型スコープの扱い 268 |
5.6 属性文法のクラスと属性評価 273 |
(a) 非循環属性文法とその属性評価 274 |
(b) 絶対非循環性文法とその属性評価 279 |
(c) 1パス型の属性文法とその属性評価 284 |
(d) 属性評価の最適化 296 |
(e) 属性文法クラスの包含関係 299 |
5.7 意味解析器生成系 301 |
第5章のまとめ・演習問題5 306 |
6 実行時環境 |
6.1 記憶管理 312 |
(a) 実行時記憶 312 |
(b) 活性レコード 314 |
(c) 手続き呼出しと戻り時の処理 321 |
6.2 非局所名の参照 325 |
(a) 入れ子のあるブロックにおける名前の割当て 325 |
(b) 入れ子の手続きでの非局所名の参照 326 |
(c) 静的リンク法 327 |
(d) ディスプレイ法 330 |
6.3 パラメタの渡し方 333 |
(a) 値呼び 334 |
(b) 参照呼び 334 |
6.4 記憶領域の動的割当て 336 |
(a) 単一寸法の領域の動的記憶管理 337 |
(b) 多種寸法の領域の動的記憶管理 338 |
第6章のまとめ・演習問題6 342 |
7 中間コード生成 |
7.1 中間コード生成のあらまし 348 |
7.2 中間言語の種類 349 |
(a) 抽象構文木とdag 349 |
(b) 後置コード 355 |
(c) 3番地コード,四つ組,三つ組 360 |
(d) 本書で用いる拡張3番地コード 364 |
7.3 代入文と配列の中間コード 367 |
(a) 混合演算と型変換 368 |
(b) 配列要素 370 |
(c) レコード 372 |
7.4 制御文と論理式の中間コード 373 |
(a) 制御文の中間コード 373 |
(b) 論理式の中間コード 375 |
(c) 論理式の飛越し型中間コード 378 |
7.5 手続き呼出しの中間コード 384 |
7.6 中間コード生成の効率化 385 |
(a) 意味規則の書換えによる効率化 385 |
(b) バックパッチング 387 |
第7章のまとめ・演習問題7 391 |
8 コード生成 |
8.1 コード生成のあらまし 396 |
(a) 中間言語と目的言語 396 |
(b) 記憶割当ての時期 397 |
(c) 命令の選択と目的コードの効率 398 |
(d) レジスタ割当てと評価順序 399 |
8.2 目的機械のモデル 401 |
8.3 式のコード生成 402 |
(a) 変数の参照 403 |
(b) 配列やレコードの参照 404 |
(c) 式の最適なコード 405 |
8.4 文の列に対するコード生成 418 |
(a) 諸定義 419 |
(b) グラフ彩色によるレジスタ割当て 420 |
(c) 一時名に対する記憶割当て 424 |
(d) 基本ブロックのコード生成 425 |
(e) 条件飛越しのコード生成 427 |
(f) 手続き呼出しのコード生成 429 |
8.5 コード生成器生成系 431 |
(a) 木の書換え規則による代入文のコード生成の定式化 432 |
(b) 木の下向きパタンマッチングによるコード生成 435 |
(c) LR構文解析を利用するコード生成 438 |
第8章のまとめ・演習問題8 439 |
9 コード最適化 |
9.1 コード最適化のあらまし 442 |
9.2 最適化の例 444 |
(a) 代数的性質の利用 445 |
(b) コピー伝播 445 |
(c) 共通部分式の除去 446 |
(d) 不要コードの除去 447 |
(e) ループの最適化 447 |
(f) インライン展開 451 |
(g) パイプライン制御の考慮 452 |
(h) その他の最適化 452 |
9.3 基本ブロックの最適化 453 |
9.4 基本ブロックを越える最適化 459 |
(a) 制御フロー解析 460 |
(b) ループ 461 |
(c) データフロー解析 464 |
(d) 最適化変換とコード生成器への情報渡し 465 |
9.5 データフロー解析と各種最適化変換 465 |
(a) 到達する定義 465 |
(b) 構造的プログラム言語のデータフロー解析(到達する定義) 467 |
(c) 一般のプログラムのデータフロー解析(到達する定義) 471 |
(d) 利用可能式と大域的共通部分式の除去 476 |
(e) 生存変数と不要コードの除去 480 |
(f) データフロー方程式の分類 482 |
(g) ループの最適化 483 |
9.6 のぞき穴最適化 493 |
9.7 その他の最適化手法 496 |
第9章のまとめ・演習問題9 497 |
10 インタプリタ |
10.1 インタプリタの概念 502 |
10.2 スタック仮想機械と後置コード 505 |
(a) PL/0機械 505 |
(b) PL/0コード 507 |
(c) PL/0プログラムのPL/0コードへの翻訳 509 |
10.3 インタプリタのプログラム 513 |
(a) インタプリタの構成 513 |
(b) PL/0インタプリタ 515 |
(c) インタプリタの効率化 515 |
第10章のまとめ・演習問題10 516 |
付録A 言語処理系の移植 519 |
付録B 生成系を用いたPL/0言語の処理系 525 |
演習問題の解答 553 |
参考書 583 |
索引 595 |