概要

字句解析から最適化まで、インタプリタを2言語で実装する

想定読者

言語処理系の仕組みを実装レベルで理解したいエンジニア

こんな人には向いていない

• プログラミング言語の文法を学んでいる段階の初学者には、実装経験の前提が不足している
• バイトコードVMやコンパイラを実務で既に構築した経験者には、基礎的な説明の比重が大きい

この本で身につくこと

• 字句解析(スキャナ)と構文解析(パーサ)の役割と実装手順を理解できる
• 動的型付けとクロージャを持つ言語の処理系をJavaで1から構築できる
• Cを用いた低レイヤな実装手法と最適化の基礎的なアプローチを習得できる
• コンパイラコンパイラの仕組みと利用場面を把握できる

ハイライト(外部からの言及)

動的型付けやクロージャを備えたモダンな言語をどのように実装するのか？！「字句解析」から「コンパイラコンパイラ」の使い方、「最適化」まで、ＪａｖａとＣによる２つの実装で開発のエッセンスを解説。 — 出典

本書のカバー範囲と2言語実装というアプローチを端的に示している

章立て

第1章 はじめに

第1部 導入編。本書の目的と Lox 言語の概要

第2章 領域の地図

処理系の種類(インタプリタ・コンパイラ・トランスパイラ等)の分類地図。本書全体の設計判断を理解する土台になるため、第2部・第3部に進んだ後で振り返ると理解が深まる。

第3章 Lox言語

本書を通じて実装する Lox 言語の仕様。後続章の到達点を先に把握できる

第4章 字句解析（スキャニング）

第2部 木の巡回によるインタプリタ(jlox / Java)。手書きで字句解析器を作る最初の実装章

第5章 コードを表現する

AST のデータ構造設計。Visitor パターンの実装

第6章 式の構文を解析する

再帰下降構文解析。演算子優先順位の扱い

第7章 式を評価する

jlox が式の値を初めて計算・出力する章。ここで実際に動作するインタプリタが生まれるため、学習進捗の節目として手元でコードを動かしながら進むと効果的。

第8章 文と状態

変数宣言とスコープを管理する Environment クラスを導入する章。以降の制御フロー・関数章の前提となる依存度が高い。

第9章 制御フロー

if・while・for をインタプリタで評価する実装。比較的短い章だが、jlox の動的実行モデルを確認する節目となる。

第10章 関数

クロージャの基礎。Lox に第一級関数を導入する章

第11章 解決と束縛

変数の解決フェーズを別パスとして追加する章。実行前の静的解析の発想に初めて触れるため、動的評価との境界が詰まりポイントになりやすい。

第12章 クラス

jlox に OOP の基礎を実装する章。フィールドをハッシュマップで管理するシンプルな設計が、後の clox 実装(第27章)との比較基準になる。

第13章 継承

jlox のスーパークラスチェーン実装。第11章の変数解決パスを再活用する設計で、jlox パート全体の仕上げ章として位置づけられる。

第14章 バイトコード

第3部 バイトコード式仮想マシン(clox / C)。最適化を意識した実装に切り替わる転換章

第15章 仮想マシン

スタックベース VM の実装。性能特性を理解できる

第16章 オンデマンドの字句解析

clox は jlox と異なりトークンを先読みせずオンデマンドで生成する設計。jlox(第4章)との設計差分を意識して読むと理解が深まる。

第17章 式をコンパイルする

Pratt パーサによる式のコンパイルを実装する章。プレフィックス・インフィックス関数を登録する設計が詰まりポイントになりやすい。

第18章 値の型

数値・真偽値・nil を tagged union で表現する設計を実装する章。型タグの扱い方が第30章の NaN-boxing 最適化の前提知識になる。

第19章 文字列

ヒープ上の文字列オブジェクトを導入する章。Obj 系の型階層とメモリ管理の基本設計が確立され、第26章の GC 実装の準備になる。

第20章 ハッシュ表

オープンアドレッシング法でハッシュテーブルを自作。データ構造の実装力が試される章

第21章 グローバル変数

clox のグローバル変数をハッシュテーブルで管理する実装。第20章で自作したハッシュ表が初めて本格的に活用される章で、設計の一貫性が体感できる。

第22章 ローカル変数

ローカル変数をスタック上のオフセットで管理する章。ヒープ確保なしで変数を扱う設計と、jlox の Environment との対比で性能差の理由が掴める。

第23章 前後にジャンプする

条件分岐とループをバイトコードのジャンプ命令で実装する章。バックパッチによる未確定アドレス解決の手順が典型的な詰まりポイントになる。

第24章 コールと関数

コールスタックとコールフレームを実装する章。jlox の再帰的な実行モデルとの対比でスタックベース VM の性能設計を理解できる。

第25章 クロージャ

アップバリュー(Upvalue)の概念。クロージャの効率的な実装

第26章 ごみ集め

マーク&スイープ GC の実装。GC の動作原理を最小実装で理解できる本書の白眉

第27章 クラスとインスタンス

clox に OOP を追加する章。jlox の第12章と比較するとスタックベース VM でのフィールド管理の差分が明確になる読み方ができる。

第28章 メソッドと初期化子

メソッド呼び出しと init() の特殊処理を実装する章。バウンドメソッドのキャッシュ最適化の設計判断を追うことで、第30章の最適化との連続性が見えてくる。

第29章 スーパークラス

clox のスーパークラス実装。upvalue を再利用した super 変数の束縛設計が本書のアップバリュー理解の最終確認になる章。

第30章 最適化

本書の集大成。NaN-boxing 等の最適化テクニックを実装に組み込む

学習のヒント

• JavaとCの2実装は独立したパートとして読めるため、使い慣れた言語の実装から着手し最初の動くインタプリタを短期間で完成させると全体像が掴みやすい
• 字句解析・構文解析のパートは後続のVM実装・最適化の土台になるため、コードを実際に手元で書きながら各ステップの動作確認を取りつつ進めると理解が定着しやすい
• コンパイラコンパイラのセクションは手書き実装の自動化に相当するため、先に手書きパーサを一通り実装した後に読むと対比が明確になる

前提知識

• JavaまたはCのいずれか1言語で基本的なプログラムを読み書きできること
• 変数・関数・スコープなど、プログラミング言語の基本概念を理解していること

次に読む本

コンパイラ 原理・技法・ツール(ドラゴンブック)

本書がインタプリタの動作実装に集中するのに対し、ドラゴンブックは字句・構文解析の形式理論(正規表現・CFG・LR 構文解析)を体系化する。本書で実装経験を積んだ後に読むことで、各実装手法の理論的根拠を遡及的に理解できる。

低レイヤを知りたい人のためのCコンパイラ作成入門(Rui Ueyama著)

本書の clox(C 実装)でバイトコード VM までは構築できるが、ネイティブコード生成・x86 アセンブリ出力には踏み込まない。本書でスタック VM の仕組みを掴んだ後、このテキストで機械語生成の段階に進むと処理系の全レイヤを一気通貫して理解できる。