『Let’s Build a Compiler』再訪

 (eli.thegreenplace.net)
1 ポイント 投稿者 GN⁺ 2025-12-12 | 1件のコメント | WhatsAppで共有
  • 1988〜1995年に公開された Jack Crenshaw の 「Let’s Build a Compiler」チュートリアルを、Python と WebAssembly で再実装したプロジェクト
  • 原作では Pascal と Motorola 68000 アセンブリを使っていたが、今回は現代的な環境で実行可能なコードへ変換
  • チュートリアルの核心は、**再帰下降パーサー（recursive-descent parser）**を自ら実装し、初期段階から実際のアセンブリコードを生成するアプローチ
  • Crenshaw の方式は 構文指向翻訳（syntax-directed translation） を用いるが、型処理の段階で限界が見えてくる
  • 今回の再実装は、この古典的チュートリアルを現代の開発者が 自分で実行し実験できる形で復元した点に意義がある

古典的チュートリアルの背景

  • Jack Crenshaw の 「Let’s Build a Compiler」 は 1988〜1995 年に公開されたコンパイラ作成入門で、今なお頻繁に言及される資料
    • 原文は Pascal で書かれ、Motorola 68000 アセンブリコードを出力
    • 35 年が経った 2025 年になっても Hacker News などで継続的に話題になっている
  • 筆者は 2003 年にこのチュートリアルに初めて触れて強い印象を受け、2025 年にこれを Python と WebAssembly に移植した

Python および WebAssembly への再実装

  • 単に読むだけでなく、チュートリアルのコンパイラを Python に翻訳し、WebAssembly（WASM） を出力するよう実装
  • 成果物は GitHub リポジトリ（eliben/letsbuildacompiler）で公開
    • TUTORIAL.md ファイルで、原作の各パートが Python コードにどう対応するかを説明
    • ユーザーは原作チュートリアルを読みながら、実際に動かせるコードを試せる

KISS 言語の例と WASM 出力

  • Crenshaw が設計した KISS 言語のサンプルプログラムを、Python 版コンパイラでコンパイルした結果を提示
    • サンプルには procedure、while ループ、値渡しと参照渡しが含まれる
  • 出力された WASM テキストには 参照パラメータ（by-reference parameter） の処理ロジックが含まれ、最適化はほとんど行われていない
  • グローバル変数 X が main 関数から暗黙に返される部分は、テストを容易にするための仕組み
  • 生成された WASM コードは、実行によって 期待する結果を検証するテストに使われる

チュートリアルの強み

  • Crenshaw のチュートリアルは、再帰下降パーサーを段階的に構築し、複雑な理論よりも 実際に動作するコード生成に焦点を当てている
    • 当時は lex と yacc が標準と見なされていたが、手書きパーサーの単純さと明快さが大きな影響を与えた
    • その後 20 年間、筆者は 手動の再帰下降パーサーを好むようになった
  • また、多くの講義が構文解析に偏っていた時代に、Crenshaw は 初期段階からアセンブリコード生成を扱っていた

限界と改善の可能性

  • チュートリアルは 構文指向翻訳（syntax-directed translation） 方式を使い、パース中にそのままコードを生成する
    • このアプローチは学習には有用だが、型情報を事前に把握できないため最適化が難しいという限界がある
  • とくに型が導入される第 14 部以降では、中間表現（IR）や AST を活用した構造的アプローチが必要になることが見えてくる
  • Crenshaw が第 14 部以降でチュートリアルを中断した理由は明示されていないが、この限界と関係している可能性に言及している
  • 筆者は、第 14 部を転換点として AST を生成し、その後に型検査とコード生成を行うアプローチのほうが適していると評価している

結論

  • 原作チュートリアルは今なお コンパイラ作成入門として卓越した読みやすさと実用性を保っている
  • 今回の Python・WASM 版は、現代の開発者が古い技術に縛られず学べるよう補完した実装
  • GitHub リポジトリを通じて誰でも試すことができ、コンパイラの構造を自ら体験できる現代的な再解釈として評価される

関連記事

1件のコメント

 
GN⁺ 2025-12-12
Hacker Newsの意見

  • フロントエンドの細部に埋没せず、最初からすぐに 動作するアセンブリコード を生成するチュートリアルである点が気に入った
    Ghuloumのアプローチのように、言語のごく小さな部分から全体を組み立て、段階的に拡張していくやり方がとりわけ魅力的だ
    最近見つけた良書はこのリンクのもので、Cとx86は初心者にとって最適なターゲットではないが、最初のコンパイラを作るには素晴らしい資料だった
    参考までに、Ghuloumの論文はこちらにある

    • これは珍しいケースだが、アカデミックなアプローチ が実際には実用性と合っていない例だと思う
      昔はパースが最重要だったのでカリキュラムもそう組まれていたが、今は言語機能をどう実装するかのほうが重要だ
      たとえ自分でコンパイラを作るとしても、今は「Claude、この文法で再帰下降パーサーを作って」と言えば、ほぼ一発で結果が出る時代だ
    • 学術研究者と実務開発者の違いを感じた
      学術側は レイヤー(layer) ベースで、実務側は パイプ(pipe) ベースでアプローチする傾向がある
      レイヤー方式はビルド可能なコードを与えるが実行しにくく、パイプ方式は実行は容易だが構造化が弱い
      結局のところ、実行可能な最小単位に分けて開発することが核心だ

  • この記事は本当に要点をよく突いていると思う
    大学に入る前からコンパイラに興味があったが、この資料が最も入りやすい入門書だった
    17歳のときに 再帰下降パーサー を自作し、一見複雑な問題も正しい 基礎単位(primitive) に分解すれば単純になるのだと気づいた

    • 「問題を正しい プリミティブ に分解すること」こそ、プログラミングの本当の核心だ
      アルゴリズムに関する資料は多いが、問題をどうプリミティブとして捉えるかを扱う資料は少ない
    • 再帰下降は単にパーサーを作る方法ではなく、プログラム設計の教訓 でもある
      以前はyaccのような テーブル駆動パーサー が主流だったが、今は再帰下降のほうが実用的で柔軟だ
      LLMによるコード生成のおかげで、このアプローチはさらに簡単になった
      学習用のトイコンパイラなら、ASTやIR、最適化を省いて直接コード生成に進んでも十分有益だ
      以前会社でCのサブセットをサポートするテストツールを作ったとき、パーサーはコードを生成する代わりに 実行可能なデータ構造 を返すようにした
      たとえばForLoopStatementクラスがtestExpressionを含み、Execute()メソッドでそれを直接呼び出す、といった具合だった
    • Niklaus Wirthの1971年の論文 Program Development by Stepwise Refinement は、この考え方を最も早く体系化した古典だ
      Fred Brooksの The Mythical Man-Month でも言及されている重要な論文だ
    • 最近はパースが必要になるたびに パーサーコンビネータ(parser combinator) を使うようになった
      概念的にあまりにも自然で、きれいだ

  • Jack Crenshawのチュートリアルが syntax-directed translation 方式を使っているという説明は興味深かった
    これが単に シングルパスコンパイラ を意味するのか、それとももっと具体的な概念なのかが気になる
    静的型付け言語では型ベースの最適化が難しい点は理解できるが、型検査のレベルにも制約があるのか知りたい

    • ターゲット言語が 定義後使用規則 に従い、複雑な型推論がなければ、型ベースの最適化や定数畳み込み程度は可能だ
      しかしIRがなければ、LICM、CSE、GVNのような高度な最適化は不可能だ
      個人的には 関数単位の2パスコンパイル を好む — 最初のパスでIRを作り、すぐコード生成して状態を捨てる方式で、高速かつ効率的な結果を得られる
    • syntax-directed translationはもう少し具体的な概念で、ソースコードを読みながら即座にコード生成 を行うことを意味する
      シングルパスコンパイラでも段階を分離して、最後にコード生成だけを行うことはできる

  • Crenshawのチュートリアルは実用的なレベルまでは届かないが、precedence climbing 手法で拡張すればずっと有用になる
    関連記事はこのリンクによく整理されている

  • 「Let’s Build a Compiler」関連スレッドをあらためて見返した
    2007年から2023年まで、複数回 HNに投稿された記録 がある
    特にJack Crenshawのインタビューはコメントこそないが、とても興味深い読み物だった

    • 4番目のリンクはCrenshawの記事ではなく、同じタイトルの別記事だ
    • Crenshawのインタビューは本当に良かった

  • 個人プロジェクトの紹介を兼ねた宣伝: cwerg.org
    Pythonと 再帰下降パース を使い、IRでフロントエンドとバックエンドを分離している
    x86とARM向けのELFバイナリを生成し、実用を目指している
    ただし複雑で、チュートリアル風ではない

  • 以前、USENETのcomp.compilersニュースグループでJack Crenshawのチュートリアルを学んだ懐かしい記憶がある
    ちなみにそのグループは今でも活動中だ

  • 現代的なコンパイラのアプローチとしては、このCornellブログ記事を勧めたい

    • LLVMのおかげで、コンパイラ作りは 驚くほど簡単になった
      使うたびに、まるでピラミッドの上に石をいくつか積むような感覚だ
    • しかしLLVMは 間接的なアプローチ なので限界がある
      LLVMをバックエンドに使う言語は共通して コンパイル速度が遅い
      Zigはこれを認識して独自バックエンドを開発中で、Rustはいまだに遅いコンパイルに縛られている
      LLVMは複雑さが品質を保証するという錯覚を与え、開発者の 自律性を弱める技術 だと思う
      これは他の人気技術（頭文字が似ている）にも似ている

  • 私も似た理由で tiny-optimizing-compiler というチュートリアルを書いた
    コンパイラの 中間段階とバックエンド だけを扱う簡潔な例だ
    GitHubリンク

    • これを Lean で実装してみると面白そうだ

  • 子どものころ、このチュートリアルを印刷して持ち歩きながら読んでいた
    短時間でコンパイラが完成していくのを見るのは本当にすごかった
    Beej’s Guideのようなこうした資料は、CS教育で最も価値ある文書 の一つなのに、正当に評価されていない