コンパイラの仕組み

ある言語のコンパイラを実現する流れに沿い, 問題解決に必要な技術を具体的に解説した実践書。〔内容〕概要 / 字句解析 / 演算子順位 / 再帰的下向き構文解析 / 記号表と中間語 / 誤り処理 / 実行環境とレジスタ割付 / コード生成 / Tiny C / 他
1. プログラミング言語
1.1 プログラミング言語の設計
1.2 言語仕様の記述方式への要請
1.3 バッカス記法 (BNF)
1.4 意味仕様の記述
1.5 演習問題
2. コンパイラの概要
2.1 コンパイラの作り方の検討
2.2 コンパイラでの処理過程
3. 字句解析
3.1 事例検討
3.2 正規表現
3.3 オートマン
3.4 オートマンに基づく字句解析
3.5 演習問題
4. 演算子順位による構文解析
4.1 事例による方式検討
4.2 演算子順位法
4.3 演習問題
5. 下向き構文解析
5.1 適用範囲の広い方式の検討
5.2 再帰的下向き構文解析の概要
5.3 プログラムと構文規則の照合方法
5.4 LL (1) 文法
5.5 再帰的下向き構文解析の実現方法
5.6 非再帰的な表駆動下向き構文解析
5.7 その他の構文解析方法
5.8 演習問題
6. 記号表と中間語
6.1 意味解析
6.2 記号表
6.3 中間語
5.9 演習問題
7. 誤り処理
7.1 誤りの種類
7.2 誤りの検出
7.3 誤りへの対処
8. 実行時環境とレジス夕割り付け
8.1 命令の実行に必要な準備
8.2 スタックの管理と呼び出し・復帰の手順
8.3 記憶域割り付け
8.4 レジスタ割り付け
8.5 開始・終了処理とその他の処理
8.6 演習問題
9. コード生成
9.1 コード生成の概要
9.2 変数へのアクセス
9.3 機械語変換の基本パターン
8.7 演習問題
10. Tiny C コンパイラ
10.1 Tiny C コンパイラの概要
10.2 方式
10.3 コンパイラのプログラム構成
10.4 コーディング様式
10.5 テーブル仕様
10.6 言語解析部
10.7 コード生成部
10.8 オブジェクト・プログラム
10.9 演習問題
11. その他の話題
11.1 前処理
11.2 オブジェクト最適化
11.3 記憶管理
11.4 実行時ライブラリ
11.5 解釈実行系
12. コンパイラ小史
12.1 Fortran
12.2 Algol
12.3 Cobol
12.4 PL/I
12.5 Pascal
12.6 C
12.7 Basic
12.8 Ada
12.9 gcc
12.1O Java
13. 付 録 Tiny C コンパイラのソース・プログラム
14. 演習問題解答
15. 参考文献
16. 索 引

『コンパイラの仕組み』 (渡邊 坦 著、朝倉書店、1998 年 4 月刊) は、ある言語のコンパイラーを実現する流れに沿って、字句解析、構文解析、記号表と中間語、誤り処理、実行時環境、コード生成を順にたどる教科書です。朝倉書店の情報科学こんせぷつシリーズの第 8 巻で、版元の紹介文は、問題解決に必要な技術を具体的に解説した実践書と位置づけています。理論の網羅よりも、小さなコンパイラーを 1 つ組み上げる筋道を通してコンパイラーの内部を理解したい人に向いた 1 冊です。

言語仕様の記述に始まる 12 章と Tiny C コンパイラーの付録

目次は 1 から 16 までの番号で並び、12「コンパイラ小史」までが本文です。第 1 章「プログラミング言語」は言語の設計と、バッカス記法 (BNF) による言語仕様の記述を扱い、第 2 章「コンパイラの概要」で処理過程の全体を示したあと、第 3 章「字句解析」では正規表現とオートマトンに基づく字句解析を扱います。構文解析は 2 つの章に分かれ、第 4 章「演算子順位による構文解析」と第 5 章「下向き構文解析」で、後者には LL (1) 文法や非再帰的な表駆動の方式の節も含まれます。第 6 章「記号表と中間語」、第 7 章「誤り処理」、実行時環境とレジスターの割り付けを扱う第 8 章、第 9 章「コード生成」と続き、第 10 章「Tiny C コンパイラ」では、方式、プログラム構成、コーディング様式、テーブル仕様、言語解析部、コード生成部、オブジェクト・プログラムを順に示します。第 11 章「その他の話題」は前処理やオブジェクト最適化、解釈実行系など、第 12 章の小史は Fortran から Java までの言語と処理系を節に立てています。13 は付録の Tiny C コンパイラーのソース・プログラムで、演習問題解答、参考文献、索引が続き、多くの章の末尾には演習問題があります。

演算子順位法と再帰的下向き構文解析、手で書ける構文解析の位置づけ

構文解析の方式には、文法から表を自動生成する上向きの方式と、文法規則をそのまま関数の呼び出しに写す下向きの方式があります。本書が章を割く演算子順位法と再帰的下向き構文解析は、どちらも人の手でプログラムとして書き下ろせる方式で、式の優先順位や結合の向きを素直に扱えるのが利点です。生成系の道具に頼らずに書けるため、誤りの報告を細かく作り込みやすく、実用のコンパイラーの中にも手書きの再帰的下向き構文解析を採用しているものがあります。字句解析の側も同様で、ログの検索や入力の検査で日常的に使う 正規表現 は、字句の形を有限オートマトンで認識するという同じ理論の上に立っています。コンパイラーの各段を自分で組み立てた経験は、設定ファイルの読み込みや小さなドメイン特化言語の実装といった、コンパイラー以外の場面でもそのまま役立ちます。

1998 年刊の教科書として読む前提と、合う読者

刊行は 1998 年で、小史の最後の節が Java であることからも分かるとおり、その時点の技術環境を前提にしています。目次で最適化に当たる節は第 11 章の「オブジェクト最適化」で、データフロー解析や SSA 形式といった語は目次に現れないため、最適化の理論や LLVM のような基盤を中心に学びたい人には別の専門書の方が目的に合います。反対に、字句解析からコード生成までを 1 本の筋として通し、付録のソース・プログラムで実際の作りを確かめながら理解したい学生や技術者にとっては、各段の役割が具体的に見える構成です。低レイヤーの他の分野の本と学ぶ順序を組み立てるなら OS と低レイヤーの技術書の選び方 も参考になります。言語処理系を一度自分の手で組み上げてみたい人が、その道筋を日本語で順にたどれる 1 冊です。