| ソフトウェア科学を学ぶために |
| まえがき |
| 学習の手引き |
| 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 |
