コンパイラ(コンパイラ)

本書は,プログラミングやコンピュータに興味を持つ者が,コンパイラの原理と構造,さらにその開発方法を基礎から理解するためのテキストである。
コンパイラの理解は,コンピュータの原理やプログラムの実行のしくみを理解する基礎である。そこで本書では,チューリングらによって確立された計算可能性の理論と万能計算機の構築方法を基礎として,コンパイラを含むプログラミング言語処理系の構築原理とその構造を解説する。これらの理解を基に,コンパイラ実現のための主要な基盤技術を,その原理とその背後にある考え方を含め習得することを目標とする。この考え方を理解することができれば,従来難解と受け止められている LR 構文解析や多相型の型推論などの技術も見通し良く習得できる。
これらのコンパイラの原理と構造の理解に加えて,先端的言語コンパイラの開発方法を習得するために,実際に実行可能なインタープリタと抽象機械へのコンパイラを開発する。高階の関数や多相型型推論などの先端機能を含む ML 言語の小さなサブセット CoreML を対象とし,ML 言語の一つである「 SML#」を用いてその処理系を開発する。
これらを学び直したいエンジニアや,コンピュータやプログラミングに興味を持つ学部学生に最適な一冊である。
第 1 章 計算とプログラミング言語
1.1 計算の原理と計算機の構造
1.2 プログラミング言語の構造と原理
1.3 プログラミング言語開発の枠組み
1.4 プログラミング言語処理系開発の課題
1.5 練習問題

第 2 章 SML#チュートリアル
2.1 高水準言語の役割と ML の紹介
2.2 チューリング言語インタープリタの設計と開発
2.3 分割コンパイルとコマンドの作成
2.4 練習問題

第 3 章 文字列の性質と文字列処理
3.1 文字列と文字列集合の性質と演算
3.2 文字列のみの構造を持つ CoreML 処理系
3.3 練習問題

第 4 章 字句解析
4.1 正規言語を用いた語彙の定義
4.2 正規言語を認識する機械
4.3 Lex による字句解析処理の自動生成
4.4 字句解析のみを行う CoreML 処理系
4.5 練習問題

第 5 章 構文解析
5.1 本章の内容と目的
5.2 文脈自由文法による構文構造の定義
5.3 構文解析問題
5.4 最右導出の再構築
5.5 LR 構文解析の原理
5.6 定理 5.1 の証明と DG の構築
5.7 効率的なアルゴリズム構築戦略
5.8 構文解析表の作成
5.9 先読み文字によるアルゴリズムの改良
5.10 yacc による構文解析処理の自動生成
5.11 構文解析のみを行う CoreML 処理系
5.12 練習問題

第 6 章 型の解析と型推論
6.1 型と型システムの考え方
6.2 型システムの定義
6.3 型の解析
6.4 式の主要な型判定を推論する CoreML 処理系
6.5 多相型の定義と解析
6.6 多相型を推論する CoreML 処理系
6.7 練習問題

第 7 章 インタープリタ
7.1 インタープリタの構造と役割
7.2 操作的意味論の定義
7.3 再帰関数の実現
7.4 インタープリタの実装
7.5 練習問題

第 8 章 抽象機械へのコンパイル
8.1 コンパイラの構造
8.2 SECD 機械の定義
8.3 SECD 機械へのコンパイル
8.4 CoreML コンパイラと実行時処理系の実装
8.5 練習問題

コンパイラの教科書には、道具の使い方を説明するものと、原理を証明つきで積み上げるものがあります。『コンパイラ 原理と構造』 (大堀淳 著、共立出版、 2021 年 9 月刊、 A5 判 196 ページ) は明確に後者で、しかも「作りながら」原理を学ばせる本格派のテキストです。チューリングらが確立した計算可能性の理論と万能計算機の構築方法を出発点に据え、プログラミング言語処理系がなぜその形をしているのかを、 ML 系言語のサブセット CoreML の処理系を実際に開発しながら解き明かしていきます。実装に使うのは 関数型言語 SML# です。

理論と実装が交互に進む全 6 章の構成

構成は理論と実装が交互に進みます。第 1 章で計算の原理とプログラミング言語の構造という土台を作り、第 2 章の SML# チュートリアルでチューリング言語のインタープリタを開発して道具に慣れます。第 3 章の文字列処理を経て、第 4 章では正規言語とそれを認識する機械の理論から Lex による字句解析の自動生成へ、第 5 章では文脈自由文法から LR 構文解析の原理、構文解析表の作成、 yacc による自動生成へと進みます。とりわけ第 5 章は、難解とされがちな LR 構文解析を定理の証明まで含めて正面から扱う、本書の白眉です。第 6 章の型の解析と型推論も、 ML 系言語を題材に選んだ利点が最も出る部分で、各章末には練習問題が付きます。

コンパイラを作らない人にも効く読みどころ

「コンパイラなんて作らないのに学ぶ意味があるのか」という定番の疑問には、本書の設計自体が答えになっています。字句解析は正規表現の、構文解析は文法とパーサの、型推論は 型システム の理解そのものであり、これらは言語処理系を作らない人でも、正規表現の限界を見積もる、設定言語や DSL を設計する、型エラーの出方を理解するといった場面で日常的に効いてきます。 196 ページと大部ではありませんが、密度は高く、定理と証明を追う数学的な読解力が要求されます。

対象読者と必要な前提知識

対象は、情報系の学部生と、コンパイラや計算理論を基礎から学び直したいエンジニアです。前提として、何らかの言語でのプログラミング経験と、集合や論理の記法への耐性は必要です。関数型言語の経験は第 2 章のチュートリアルで補えますが、「動くコンパイラを手早く作って達成感を得たい」という動機なら、 Go や C を使う 写経 型の自作コンパイラ本のほうが合います。本書はその逆で、薄い記述の裏に理論の裏付けを求める読者のための本です。

流行に左右されない基礎としての価値

コンパイラの原理は、言語やフレームワークの流行と無関係に何十年も安定している知識で、一度きちんと学べばプログラミング言語というもの全体の見え方が変わります。腰を据えて理論から登りたい人にとって、日本語で読める充実した選択肢です。