Engineering a Compiler（コンパイラの工学）

引用

Cooper, K. D., & Torczon, L. (2022). Engineering a Compiler (3rd ed.). Morgan Kaufmann (Elsevier).

章の要約

本書は14の章と2つの付録からなり、章の本文は合計約755ページです。出版社は第3版を、コンパイラ技術の最新の進展を扱うものと説明しており、新しい章としては、意味的な精緻化（生成されたパーサにおける場当たり的な構文主導翻訳の仕組みからコードを生成するときに生じる問題）、名前付けとアドレス可能性に対する実行時の支援、そして式・代入・制御構造のコード形状が挙げられています。以下のページ数は、公表されているページ範囲から割り出した各章の長さです。

第1章：Overview of Compilation（コンパイルの概観）

26ページの最初の章は、コンパイルの概観であり、各フェーズを扱う章に先立ちます。

第2〜3章：Scanners（スキャナ）；Parsers（パーサ）

2つのフロントエンドの章は、約58ページと73ページで、プログラムの単語の認識と文法構造を扱います。合わせて本文の約6分の1を占め、後の章に比べると小さな割合です。

第4章：Intermediate Representations（中間表現）

この章（49ページ）は、コンパイラがプログラムを解析・変換する間、プログラムを保持する内部形式に目を向けます。

第5章：Syntax-Driven Translation（構文主導翻訳）

第5章（65ページ）は、ソースプログラムの構文によって駆動される翻訳を扱います。意味的な精緻化に関する新しい内容についての出版社の説明は、生成されたパーサにおける場当たり的な構文主導翻訳の仕組みからのコード生成を指しており、これはこの章の題が示す主題です。

第6章：Implementing Procedures（手続きの実装）

この章（51ページ）は、手続きがどのように実装されるかを扱います。出版社は、名前付けとアドレス可能性に対する実行時の支援を新たに扱われた話題の一つに挙げており、この章の内容と合致します。

第7章：Code Shape（コード形状）

コード形状の章（52ページ）は、式、代入、制御構造に対して生成されるコードの形を扱い、出版社はこれも新しい章の話題として挙げています。

第8〜10章：Introduction to Optimization（最適化入門）；Data-Flow Analysis（データフロー解析）；Scalar Optimization（スカラ最適化）

3つの最適化の章は、合わせて約194ページです。最適化の入門（69ページ）から、最適化が依拠する解析の仕組みであるデータフロー解析（68ページ）を経て、スカラ最適化（57ページ）へと進みます。

第11〜13章：Instruction Selection（命令選択）；Instruction Scheduling（命令スケジューリング）；Register Allocation（レジスタ割り当て）

コード生成の章（42、46、50ページ）は、ターゲット命令の選択、その並べ替え、値へのレジスタの割り当てを扱います。出版社は、本書が局所的な範囲でのボトムアップ方式のレジスタ割り当てを扱うと述べています。

第14章：Runtime Optimization（実行時最適化）

最後の章（43ページ）は、プログラムの実行中に行われる最適化を扱います。

付録A〜B

付録A（ILOC、12ページ）と付録B（データ構造、23ページ）のあとに、参考文献と索引が続きます。

主要概念

第1〜7章：ソースからコードへ

• コンパイラの構造：プログラムがコンパイラの中で通過する各フェーズ。
• 中間表現：解析と変換に使われる内部のプログラム形式。
• 意味的な精緻化と構文主導翻訳：構文解析の結果から意味とコードを生み出すこと。
• 手続き、名前付け、コード形状：名前、手続き呼出し、式が生成コードの中でどう実現されるか。

第8〜14章：最適化とバックエンド

• データフロー解析：最適化の背後にある解析。
• スカラ最適化：個々の手続きのコードの改善。
• 命令選択、スケジューリング、レジスタ割り当て：コード生成の3つの段階。
• 実行時最適化：実行時に行われる最適化。

批判的分析

長所

• 重点が構成に表れている。 最適化とコード生成（第8〜14章）が本文の約半分を占め、スキャナとパーサの章は約6分の1です。これは、本書がコードの最適化とコード生成に特に注意を払っているという出版社の説明に合致します。
• 抽象化への着目。 出版社は、本書がコンパイラ（とインタプリタ）が抽象化をどう実装するかに焦点を当て、学生がすでに知っている言語と内容を結びつけていると述べています。
• 実際にコンパイラを作ってきた著者による。 出版社の著者紹介によれば、Cooper はライス大学の Massively Scalar Compiler プロジェクトを率い、Torczon はその主任研究者の一人です。出版社は、本書が基本原理と最先端のコンパイラを作ってきた経験を組み合わせていると述べています。
• 授業向けの補助資料。 Elsevier は、2つの授業（COMP 412 と COMP 506）の教員向け授業ファイル、画像集、その他の資料を挙げており、著者紹介は Cooper が学部と大学院でコンパイラ構成を教えていると述べています。

短所

• 大きい。 付録と索引を含めて800ページを超えており、授業ではその中から取捨選択する必要があります。
• バックエンドに偏っている。 フロントエンドは2章だけなので、字句解析や構文解析を深く学びたい読者には別の本が必要で、言語設計や型システムを扱う章もありません。
• 想定読者のレベル。 出版社が示す想定読者は、主に大学院生で、一部の学部生、プロのコンパイラ開発者、システムソフトウェア開発者です。このことは、最初のコンパイラの授業には求められる内容が高いことを示唆します。
• 教員専用の資料。 授業ファイルなどの教材は登録された教員に限られるため、独習者は自分でプロジェクトを設計する必要があります。

コースにおける位置づけ

Cooper と Torczon の本は、このコースの図書の中でバックエンドに重点を置く教科書です。Aho、Lam、Sethi、Ullman の Compilers: Principles, Techniques, and Tools（「ドラゴンブック」）は、字句解析、構文解析、構文主導翻訳、中間コード、コード生成、最適化を1冊で扱う長年の標準的な参考書で、両者は代替にも補完にもなります。最初のプロジェクト型の体験には、小さな言語のための2つのインタプリタを作る Nystrom の Crafting Interpreters があり、オンラインで無料で読めます。Thain の Introduction to Compilers and Language Design は、小さな C 風の言語からアセンブリへのコンパイラを作る、1学期の授業向けの簡潔な無料の教科書です。どちらも本書の前に読めます。

Pierce の Types and Programming Languages は型システムの大学院レベルの論述で、本書の最適化への重点を言語の理論で補いますが、これは Cooper と Torczon が独立した章として扱っていない分野です。

本書の使い方

本書は、データ構造とアルゴリズム、そしてある程度のシステムの基礎をすでに持ち、コンパイラがコードを生成し最適化する仕組みを理解したい読者に向いています。上級のコンパイラの授業、大学院の最初の授業、そしてコンパイラやシステムソフトウェアの開発者に適しています。

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

• 中核： 第1章、続いて、構文解析されたプログラムを生成コードに結びつける第4〜7章。スキャンと構文解析にすでに慣れているなら、第2・3章は素早く読むか、軽い本に置き換えてもかまいません。
• 最適化： 第8〜10章を順に。データフロー解析（第9章）がスカラ最適化（第10章）の土台だからです。
• バックエンド： 第11〜13章。順に読んでも、関心に応じて選んでも構いません。
• 任意： 第14章と、参考としての付録（ILOC とデータ構造）。
• 実習： 読み進めながら小さなコンパイラを、1回に1つのフェーズずつ加えて作り、各章の演習で各アルゴリズムを確認してください。