コンパイラ：原理・技法・ツール

引用

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson.

章の要約

第2版は約1,000ページで、12章と2つの付録からなる。各章は要約で終わり、多くは参考文献の節も持つ。Pearsonは、この版を全面改訂したもので、命令レベル並列性、並列性と局所性のための最適化、手続き間解析を扱う3つの新しい章（第10～12章）が加わったと説明している。著者らは、コンパイラを実際に作る読者は少ないと述べ、ソフトウェアの設計と開発というより広い問題に焦点を当て続けている。

第1章：Introduction

言語処理系、コンパイラの構造、プログラミング言語の進化、コンパイラを作る科学、プログラミング言語の基礎。以降の章が順に取り上げる段階を示す。

第2章：A Simple Syntax-Directed Translator

小さいが完結したフロントエンド。構文定義、構文主導翻訳、構文解析、簡単な式の翻訳器、字句解析、記号表、中間コード生成を扱う。後続の章が各段階を深く扱う前に、動く全体像を与える。

第3章：Lexical Analysis

字句解析器の役割、入力のバッファリング、トークンの仕様と認識、Lexジェネレータ、有限オートマトン、正規表現からオートマトンへの変換、字句解析器ジェネレータの設計、DFAベースのパターンマッチャの最適化。

第4章：Syntax Analysis

文脈自由文法、文法の書き方、トップダウン構文解析、ボトムアップ構文解析、単純LR構文解析、より強力なLR構文解析器、曖昧な文法の利用、構文解析器ジェネレータ。

第5章：Syntax-Directed Translation

構文主導定義、評価順序、構文主導翻訳の応用、翻訳スキーム、L属性定義の実装。

第6章：Intermediate-Code Generation

構文木の変種、3番地コード、型と宣言、式の翻訳、型検査、制御フロー、バックパッチング、switch文、手続きの中間コード。

第7章：Run-Time Environments

記憶域の編成、スタックへの領域割り当て、非局所データへのアクセス、ヒープ管理、そしてガベージコレクションに関する4つの節（入門、トレースベース収集、短停止収集、発展的な話題）。

第8章：Code Generation

コード生成器の設計上の問題、ターゲット言語、ターゲットコードのアドレス、基本ブロックとフローグラフ、基本ブロックの最適化、単純なコード生成器、のぞき穴最適化、レジスタ割り当て、木の書き換えによる命令選択、動的計画法による式の最適コード生成。

第9章：Machine-Independent Optimizations

最適化の主な源、データフロー解析入門とその基礎、定数伝播、部分冗長性除去、フローグラフのループ、領域ベース解析、記号解析。

第10～12章：Instruction-Level Parallelism；Optimizing for Parallelism and Locality；Interprocedural Analysis

第2版の新しい章。第10章はプロセッサアーキテクチャ、コードスケジューリングの制約、基本ブロックとグローバルのスケジューリング、ソフトウェアパイプライニングを扱う。第11章は基本概念、詳しい例としての行列積、反復空間、アフィンな配列添字、データ再利用、配列データ依存解析、同期不要な並列性、局所性の最適化を展開する。第12章は手続き間解析で、データフローの論理的表現、ポインタ解析（文脈非依存・文脈依存）、BDDによるDatalog実装を含む。

付録

付録A A Complete Front Endは、原始言語、メインプログラム、字句解析器、記号表と型、式の中間コード、ジャンプコード、文の中間コード、構文解析器、フロントエンドの作成を挙げる。付録Bは線形独立な解の求め方を扱う。

主要概念

第1～5章：フロントエンド

• 正規表現と有限オートマトン：トークンを規定し認識する道具。
• 文脈自由文法とLR構文解析：形式体系と主要なボトムアップ構文解析アルゴリズム。
• 構文主導定義：文法の生成規則に計算を付随させる。

第6～8章：中間コードとバックエンド

• 3番地コード：第6章の中間表現。
• ガベージコレクション：ヒープ領域の回収。4つの節で扱われる。
• レジスタ割り当てと命令選択：第8章のコード生成上の判断。

第9～12章：最適化と解析

• データフロー解析：フローグラフに沿ってプログラムの性質を推論する枠組み。
• ソフトウェアパイプライニングと反復空間：並列性と局所性のためのスケジューリングとループ変換の考え方。
• 手続き間解析とポインタ解析：手続きの境界を越える解析で、Datalogで表現される。

批判的分析

長所

• 端から端までの網羅。 12章は、字句解析から構文解析、翻訳、コード生成を経て最適化まで、コンパイラを追い、付録にフロントエンドのコードがある。
• 解析と最適化が手厚い。 第9～12章の4章が、データフロー解析、並列性、局所性、手続き間解析に充てられている。
• ジェネレータと理論が並ぶ。 Lexやパーサジェネレータが、それらのもとになるオートマトンと文法の理論と並んで置かれている。この組み合わせは、lexやyaccのようなツールと、LL(1)・SLR(1)構文解析の演習を併せて行う講義に合う。
• 一貫した構成。 各章は要約と参考文献で終わり、第2版は現代のアーキテクチャのために3章を追加している。

短所

• 最初のプロジェクトにはフロントエンドと理論が重い。 コード生成に至るまでにオートマトンと構文解析の理論をたくさん築くため、動くコンパイラを早く作りたい学生にはプロジェクト型の本のほうが向くかもしれない。
• バックエンドの話題は高度。 第10～12章は命令レベル並列性、アフィンなループ解析、Datalogによるポインタ解析を扱い、前の章よりはるかに難しい。
• 版による古さ。 第2版は初版の20年後の2006年に出ており、その後の言語やプロセッサの進展は扱われていない。
• 講義のツールとは分けて学ぶ。 COOLやLLVMを基盤とする講義では、本書の概念の学習と、講義が使うツールの資料とを並行して進めるとよい。

コースにおける位置づけ

Dragon Bookは、この読書リストの中で古典的で理論の豊かなコンパイラ教科書である。NystromのCrafting Interpretersは、読者が二つのインタプリタを作る実践的な入門で、本書の前に字句解析、構文解析、仮想マシンに触れるやさしい方法になる。ThainのIntroduction to Compilers and Language Designは、一つのプロジェクトを軸にした1学期用の、無料で入手できるコンパクトな本である。CooperとTorczonのEngineering a Compilerは、字句解析と構文解析を簡潔にして、中間表現、最適化、命令選択、スケジューリング、レジスタ割り当てにより多くを割くので、学部の講義でもっとも近い代替である。後述のUT Austinの講義は、この2冊を優劣をつけずに任意の代替教科書として並べている。PierceのTypes and Programming Languagesは型システムの大学院向け教科書で、第6章の型検査の節よりはるかに詳しく型システムを扱う。

本書の使い方

データ構造をしっかり学び、オートマトンと文法の基本、アセンブリレベルのプログラミングに少し触れたことのある、学部上級生や大学院初年度に向く。具体的な目安として、後述のUT Austinの講義は、計算機構成とプログラミングの既修科目（例：CS429とCS312、またはそれに相当するECE科目）を履修条件とし、さらに機械の構成、アセンブリの概念、C++、オブジェクト指向プログラミングの基礎を前提としている。

実践的な進め方は次のとおり。

• 最初の講義の中核： 第1～8章。第2章を、小さな完全なコンパイラとして最初に読む。
• 最適化： データフロー解析の入門として第9章。第10～12章の基礎にもなる。
• 選択・発展： 第10～12章と、動くフロントエンドのコードのための付録A。
• ガベージコレクション： 7.5～7.8節は、後回しにするか、独立した単元として読める。

読書は小さなコンパイラのプロジェクトと組み合わせるとよい。付録Aのフロントエンドは、完成形がどのようなものかを示している。

講義での使われ方

以下の講義資料のいずれにも特定の章やページの指定は見当たらないため、本書は通読用の課題ではなく、必要な箇所を引く参考書として扱うとよい。

• パイプラインと演習を軸にした講義の参考書。 IIT KharagpurのCSEサイトにある、コンパイラの理論と演習の講義ページ（掲載されている告知や課題は2025年付）は、本書を「Books and References」に挙げているが、必須とはしていない。同じ一覧には、HolubのCompiler Design in C、AppelのModern Compiler Implementation in C、MuchnickのAdvanced Compiler Design and Implementation、およびlex/yaccの参考書も並ぶ。演習課題には、Lex、LL(1)とSLR(1)構文解析、lexとyaccの統合、L属性文法、代入文の中間コード、バックパッチングが含まれる。本書ではこれらの話題が第3～6章で扱われるが、講義側は課題と教科書の節を対応づけていない。
• 最適化重視の講義での任意教科書。 UT AustinのECE479K Compilers（2025年秋学期）には必須教科書がない。本書（第2版）とCooper・TorczonのEngineering a Compiler（第3版、2022年）を任意の代替として挙げ、両方が必要になることはまずないとしている。講義はフロントエンドを扱った後、中間表現、実行時環境、制御フロー解析とデータフロー解析、最適化、レジスタ割り当て、命令選択、命令スケジューリングに重点を置く。COOLとLLVMを用いる演習は、構文解析から中間コード生成、データフロー最適化を経て、バックエンドのコード生成とレジスタ割り当てへ進む。このような講義で本書がもっとも対応するのは第6～9章と、第10章のスケジューリングの内容である。

版についての注記

どちらの講義も、このページで扱う第2版を挙げている。ECE479KはAddison-Wesley、2006年9月としている。IIT Kharagpurの講義ページはAddison-Wesley、2006年とし、さらにPearsonによる2014年のインド版も挙げている。2014年はインド版の年であり、新しい版番号を示すものではない。