Introduction to Compilers and Language Design（コンパイラと言語設計入門）

引用

Thain, D. (2020). Introduction to Compilers and Language Design (2nd ed.). Self-published. Free official edition: https://dthain.github.io/books/compiler/

章の要約

第1章：はじめに

冒頭の章は序文の役割を果たす。コンパイラをソース言語からターゲット言語への翻訳器として定義し、インタプリタとの違いを示し（Java バイトコードと実行時コンパイル（JIT）はその中間にあたる）、より良いコードを書くことから小さなドメイン固有言語を作ることまで、この分野を学ぶ理由を挙げる。著者は、コンパイラを学ぶ方法は実際に一つ作ることであり、それを C 言語で、広く使われているプロセッサ向けに書くべきだと主張する。また本書は多くのコンパイラ教科書に比べて最適化理論の比重を軽くし、実装上の工学と言語設計のトレードオフに多くを割くと説明している。

第2章：概観

この短い章では、まずコンパイラを Unix のツールチェーン（プリプロセッサ、コンパイラ本体、アセンブラ、静的・動的リンカ）の中に位置づけ、続いて内部の段階を挙げる。スキャナ、パーサ、意味解析ルーチン、中間表現、最適化器、コード生成器である。height = (width+56) * factor(foo); という一つの文を、トークンから抽象構文木、無限個のレジスタを持つ線形 IR、そして最終的な X86 アセンブリまで、すべての段階を通して追跡する。演習では、ツールチェーンの各段階を手で実行し、最適化レベルを比較することが求められる。

第3章：字句解析

言語に必要なトークンの種類から始め、ungetc で文字を押し戻す手書きの C スキャナを示したうえで、より厳密な方法が必要な理由を説明する。正規表現、決定性・非決定性有限オートマトン、そして三つの変換アルゴリズム（正規表現から NFA へ、部分集合構成法による NFA から DFA へ、Hopcroft 式の DFA 最小化）を定義する。有限オートマトンでは任意の深さの入れ子の括弧を照合できない理由を説明した後、完全な仕様ファイルとともに Flex スキャナ生成器を扱い、最後にキーワードの扱いやソース位置の追跡といった実際的な問題を論じる。

第4章：構文解析

本書で最も理論的な章である。文脈自由文法、導出、曖昧性を定義し、LL(1) 構文解析を展開する。左再帰と共通接頭辞の除去、FIRST 集合と FOLLOW 集合の計算、再帰下降パーサと表駆動パーサの作成である。後半はボトムアップ構文解析を扱う。シフト還元構文解析、LR(0) オートマトン、SLR、正準 LR(1)、LALR を、オートマトンと構文解析表の具体例とともに説明する。最後に文法クラスの関係（LL(1) ⊂ SLR ⊂ LALR ⊂ LR(1) ⊂ CFG）を整理し、チョムスキー階層を紹介する。

第5章：実践的な構文解析

ここでは Bison パーサ生成器を使って理論を実践に移す。算術式のための一つの LALR 文法をもとに、入力の正否だけを判定する検証器、構文解析中に結果を計算するインタプリタ、そして式の木を構築してから評価または表示する版という三つのプログラムを順に作る。これにより、プロジェクト言語の完全なパーサを書く準備が整う。

第6章：抽象構文木

この章では、授業用プロジェクトで使う C 風の言語 B-Minor の抽象構文木を、宣言、文、式、型、引数という五つの C 構造体として定義する。これらの用語を注意深く区別し、各種のプログラム断片が木のノードにどう対応するかを示し、最後に Bison のアクションから木全体を自動的に構築する。

第7章：意味解析

意味解析は、名前解決とそれに続く型検査として説明される。まず型システムを三つの軸（安全か非安全か、静的か動的か、明示的か暗黙的か）から概観し、C、C#、Go、Rust の短い例を示しながら、構造体、共用体、ヴァリアント型、異なる型どうしの変換といった設計上の選択を論じる。次に厳格な B-Minor の型システムを定め、スコープのスタックを用いた入れ子の記号表を作り、宣言と式における名前を解決し、expr_typecheck と stmt_typecheck を実装し、役に立つエラーメッセージの書き方について助言する。

第8章：中間表現

この章はいくつかの種類の IR とその得失を比較する。AST そのものから出発し、共通部分式を共有でき定数畳み込みも容易な有向非巡回グラフ（DAG）、さらに制御フローグラフ、静的単一代入形式、線形（三番地）IR、スタックマシン IR へと進む。GCC の GIMPLE、LLVM、Java 仮想マシンの実例によって、実用システムがこれらの考え方をどう用いているかを示す。

第9章：メモリ構成

コード生成に入る前に、実行中のプログラムがメモリをどう使うかを説明する。コード、データ、ヒープ、スタックという論理セグメントと、ハードウェアによるセグメンテーションがページングに取って代わられた経緯である。malloc と free の単純な連結リストによる実装を示し、スタック渡しとレジスタ渡しの呼び出し規約を比較し、コンパイラがグローバル変数、局所変数、引数、配列要素の位置をどう求めるかを説明し、プログラムのロードを紹介する。

第10章：アセンブリ言語

著者は、コンパイラに必要なのは命令セットのごく一部（約 30 命令）にすぎないと述べ、二つのアーキテクチャを並行した独立の節で教える。X86-64 と ARM のそれぞれについて、レジスタとデータ型、アドレッシングモード、算術演算、比較とジャンプ（分岐）、スタック、呼び出し規約（X86 では System V ABI）、そして完全な葉関数と非葉関数を扱い、最後に 64 ビット ARM の違いを説明する。

第11章：コード生成

この章では、AST の各ノードを単独で扱う意図的に単純な方法で、動作する X86-64 コードを生成する。一時レジスタとラベルを管理する補助関数を用意し、expr_codegen を後行順の走査として書き、関数呼び出しを処理し、文、条件式、宣言のコードを生成して、より良いコードは次章に委ねる。演習では、コード生成器の完成、gcc の出力との比較、そして任意で ARM や LLVM 向けの第二のバックエンドの追加が求められる。

第12章：最適化

最終章は網羅的な解説ではなく概観である。局所的、大域的、手続き間の最適化を区別し、まずコンパイラに頼る前にアルゴリズムを見直しプロファイリングを行うよう勧める。続いて高水準の変換（定数畳み込み、演算強度の軽減、ループ展開、コードの巻き上げ、関数のインライン化、デッドコードの検出）、低水準の変換（のぞき穴最適化と木の被覆による命令選択）、そして生存区間、干渉グラフ、グラフ彩色を用いたレジスタ割り当てを説明する。短い節で、プログラムの意味を変えてしまう最適化や、最適化どうしの相互作用について注意を促す。

付録 A–C：授業用プロジェクトの例、B-Minor 言語、コーディング規約

付録 A は学期のプロジェクトを一連の課題（スキャナ、パーサ、整形出力器、型検査器、任意の IR、コード生成器、任意の言語拡張）として示す。付録 B は B-Minor を形式文法ではなくあえて例によって記述し、学生が自分で正確な仕様を引き出すよう求める。付録 C は、バージョン管理を使う、「動く状態から動く状態へ」進める、デッドコードを削除するといった、C のプロジェクトに対する著者のコーディング規則を挙げる。

主要概念

第1–2章：はじめに・概観

• コンパイラとインタプリタ：コンパイラは翻訳されたプログラムを出力し、インタプリタはソースを直接実行する。JIT コンパイルは両者を組み合わせる。
• コンパイラの段階：スキャナ、パーサ、意味解析ルーチン、IR、最適化器、コード生成器であり、それぞれが前の段階の出力を処理する。

第3章：字句解析

• 正規表現と有限オートマトン：トークンのパターンを記述する等価な二つの方法。正規表現は NFA に、さらに DFA に変換でき、最小化できる。
• スキャナ生成器：Flex のように、C のアクション付きの正規表現の一覧をスキャナのコードに変換するツール。

第4章：構文解析

• 文脈自由文法：左辺が一つの非終端記号である規則の集まりで、正規表現では表せない入れ子構造を記述できる。
• LL(1) 構文解析：現在の非終端記号と一つの先読みトークンから規則を選ぶトップダウン解析で、通常は再帰下降として書かれる。
• LR 構文解析：オートマトンに駆動されるボトムアップのシフト還元解析。LALR は生成器が採用する実用的な折衷案である。

第5–6章：実践的な構文解析・抽象構文木

• Bison のアクション：文法規則に付ける C のコードで、構文解析の途中で検証、解釈、木のノードの構築を行う。
• 抽象構文木：宣言、文、式、型、引数からなる木で、構文解析の細部を除いてプログラムの構造を記録する。

第7章：意味解析

• 型システムの軸：安全/非安全、静的/動的、明示的/暗黙的の三つで、言語が値をどう検査するかを特徴づける。
• 記号表：名前を宣言に対応づけるスコープのスタックで、型検査の前にすべての識別子を解決するために使う。

第8章：中間表現

• DAG：共通部分式を共有し、定数畳み込みを容易にする、単純化されたグラフ状の IR。
• 静的単一代入（SSA）：各変数がちょうど一度だけ代入される形式で、多くの解析を単純にする。

第9–10章：メモリ構成・アセンブリ言語

• 論理セグメント：プロセスのアドレス空間におけるコード、データ、ヒープ、スタックの慣習的な配置。
• 呼び出し規約：引数の受け渡し、戻り値、レジスタの退避に関する取り決めで、System V ABI がその例である。

第11–12章：コード生成・最適化

• 後行順のコード生成：子ノードを処理した後にノードの命令を出力し、中間値は一時レジスタに保持する。
• グラフ彩色によるレジスタ割り当て：生存区間から干渉グラフを作って彩色し、干渉する変数に異なるレジスタを割り当てる。
• 演算強度の軽減：高価な演算を等価な安価な演算に置き換えること。たとえば乗算をシフトに置き換える。

批判的分析

長所

• 一つのプロジェクトが最初から最後まで続く。 どの章も一つの B-Minor コンパイラに貢献し、演習の多くはそれを拡張するコードである。付録 A はこれをそのまま使える課題の流れにまとめており、一学期の授業に採用しやすい。
• 実在のツールと実在のターゲット。 読者は C でコードを書き、Flex と Bison を使い、GIMPLE、LLVM、JVM の例を読み、実際の X86-64 コードを生成する（ARM についても並行した説明がある）。約 30 命令で足りるという主張により、アセンブリの学習が手に負える範囲に収まる。
• 言語設計が内容の一部になっている。 意味解析の章は C、C#、Go、Rust の型システム上の選択を比較し、B-Minor 自体も議論を引き出すために意図的な癖（Pascal 風の型の書き方、型推論を要する print 文、実行時サポートを要する演算子）を持たせて設計されている。
• 短く読みやすい。 約 230 ページの中で、各アルゴリズムを密な形式的記法ではなく小さな具体例（部分集合構成、LR オートマトン、x=(a+10)*(a+10) の DAG、レジスタの干渉グラフ）で説明している。

短所

• 最適化と解析の扱いが軽い。 著者自身が認めているとおり、第12章は概観にとどまり、SSA 形式は第8章で短く現れるだけで、生存解析や到達可能性解析は概略が示されるのみである。コンパイラ研究に進む学生には、その後により高度な教科書が必要になる。
• C と一定のアーキテクチャの知識を前提とする。 コードはすべて C で書かれ、第9–10章はメモリ配置と呼び出し規約を速いペースで扱う。システムや計算機構成の授業を受けていない学生には負担が大きい。
• 演習に偏りがある。 第3章と第4章には紙と鉛筆の問題があるが、第9章と第10章には演習が一つもない。プロジェクト言語も意図的に例だけで規定されているため、曖昧な点を解消するには教員の助けか注意深い読解が必要になる。
• 扱う言語の範囲が狭い。 想定されているのは静的型付けの C 風の手続き型言語である。ガベージコレクション、クロージャ、オブジェクト指向の機能は扱われず、動的型付けは第7章の一般的な議論に出てくるだけである。

コースにおける位置づけ

このコースの書籍リストの中で、Thain の本は Robert Nystrom の Crafting Interpreters と並ぶ、簡潔でプロジェクト主導の選択肢である。両者は互いを補う。Nystrom は手書きのパーサを用いて動的型付け言語のインタプリタを作るのに対し、Thain は静的型付け言語のコンパイラを作り、文法理論（LL と LR の構文解析）とスキャナ・パーサ生成器を扱い、最終的に実際のアセンブリコードに至る。構文解析の背後にある理論とネイティブコードへの道筋の両方を理解したい学生は、Thain から始めるとよい。

Cooper と Torczon の Engineering a Compiler や、Aho、Lam、Sethi、Ullman の Compilers: Principles, Techniques, and Tools は自然な次の段階である。Thain 自身も後者を大学院レベルの包括的な参考書として推薦しており、両書は一般に第12章よりもはるかに深く最適化と解析を扱うとされている。第7章の参考文献に挙げられている Pierce の Types and Programming Languages は、Thain が非形式的にしか扱わない型システムの形式的な側面を学ぶための本である。

本書の使い方

本書は、C で問題なくプログラムを書け、データ構造と計算機構成またはアーキテクチャの入門科目を履修した学部生を対象としている。コンパイラや形式言語の予備知識は前提とせず、オートマトンと文法は第3章と第4章でゼロから展開される。

授業でも独学でも、本書の順序に従い、付録 A の課題と組み合わせて進めるとよい。第1–2章は一度に読める。第3章は Flex を、第4–5章は Bison を使いながら進め、FIRST/FOLLOW 集合や LR オートマトンに関する紙の演習を解いておく。多くの授業で試験に出るのはこの部分である。第6章と第7章がプロジェクトの中心（AST と型検査器）である。著者が自分の授業で行っているように AST から直接コードを生成するのであれば、第8章は流し読みでよい。第11章のコード生成器を書く前に第9章と第10章を読み、第10章はまず X86 か ARM のどちらか一方だけを読むとよい。第12章は最後の数週間で取り組む拡張課題の一覧として使える。

各段階を小さなプログラムで確かめてから次に進み、演習が勧めるとおり自分の出力を gcc -S の結果と比べること。著者のウェブサイトからは、サンプルのスキャナとパーサ、プロジェクトの雛形コード、各段階のテストケースを収めた GitHub リポジトリにリンクされている。

版と出典

本ガイドは第2版（2020年）に基づき、著者の公式ページ https://dthain.github.io/books/compiler/（compilerbook.org からもアクセス可能）で公開されている完全な無料 PDF（compilerbook.pdf、改訂日 2026年7月28日）を読んで作成した。謝辞のページ、完全な目次と図目次、全12章（第1–2章は全文、第3–12章は冒頭部分、すべての節見出し、中心となる例題、章末の演習と参考文献）、および付録 A–C を参照している。