Pratt パース：アルゴリズム以上のマインドセット変換

Pratt パースは単なるコードのテクニックではなく、コンパイラ開発における思考の枠組み（マインドセット）を根本から変化させるものです。この記事では、Pratt パースの本質、実装の核心、そして従来の手法との決定的な違いについて整理します。

1. Pratt パースの真髄：9 行と抽象化

Pratt パースの実装は驚くほどシンプルです。Rhombus という言語ではわずか 9 行 で記述できます：

let mutable left = t.nud()

このコード自体を理解する必要はありません。「クイソートの実装を知らずとも使えるようにしたいが、ファイルシステムの内部構造まで把握しなくてもよい」という論理と同じです。抽象化する能力こそが重要であり、詳細な理解に縛られる必要はないのです。著者のコンパイラでは、この簡潔なスニペットの詳細を無視しながらも、Pratt を多用したパース機構の中核を実装しています。

• 歴史的背景: このアルゴリズムは 1973 年以来変更されていません。
• コードジェネレータとの比較: 「コンパイラのコンパイラ」と呼ばれる分野では、複雑な依存関係を生成するのではなく、この 9 行をコピー＆ペーストしてそのまま利用できます。

Douglas Crockford の定義

Douglas Crockford 氏は Pratt パースの本質を以下のように要約しました：

「Pratt はパースという非常に複雑なものを、一つの単純な質問へと還元します：「トークンの左側に何が期待されるのか」」 — Douglas Crockford, GOTO 2013

2. NUDs と LEDs：従来の手法との決定的な違い

Pratt パースでは、セマンティックアクション（意味的動作）を末端記号（トークン）に対して直接登録します。これが従来のパース技術との根本的な転換点です。

expr: expr '+' expr

nud_table

led_table

プログラミング言語における実装例 (C++ スタイル)

NUD テーブル、LED テーブル、結合度テーブルを定義する典型的な実装です。

static constinit const auto nud_table = make_dispatch_table(
    rule_c<token::lparen, token::nud::parse_lparen>,
    rule_c<token::lbrace, token::nud::parse_lbrace>,
    rule_c<token::code::exclamation_mark, token::nud::parse_negation>,
    // ... 他のトークン定義
);

static constinit const auto led_table = make_dispatch_table(
    rule_c<token::lparen, token::led::parse_function_call>,
    rule_c<token::lbrack, token::led::parse_array_indexing>,
    // ... 他のトークン定義
);

static constexpr auto binding_power = make_dispatch_table(
    rule_c<token::code::dvertical_bar, 10>,
    rule_c<token::code::lparen, 130>,
    // ... 結合度の設定
);

テーブルの定義

• NUD テーブル:

  prefix operator

  の処理（左側に何も期待しないトークン）。
• LED テーブル:

  infix/postfix operator

  の処理（左側にある何かを期待するトークン）。
• 結合度テーブル: 優先順位（Binding Power）の整数値。

セマンティックアクションの実装例

NUD 関数は単純で、直ちに再帰的なパース呼び出しを行います。

std::shared_ptr<ast::Expr> parse_unary_plus(
    ParsingContext& context, reader tok, reader& r)
{
    return ast::make_expr<ast::UnaryPlus>(
        tok.line(), tok.column(),
        // 左側にある式をパース（再帰降下）
        parse_expr(context, r, prefix_operator_binding_power));
}

3. Pratt パースの利点と特性

従来の手法と比較して、Pratt パースは以下の重要なメリットを提供します。

• 左再帰の心配がない:

  • LL(k) パースなどでのような「左再帰」問題は発生しません。
  • ストリームからトークンが消費された後にディスパッチが行われるためです。

• バックトラック不要（高速）:

  • 従来のパースエンジンに見られる「速度対メモリ」のジレンマがありません。
  • メモ化は必要なく、単純な数値比較と反復処理で済みます。

• 副作用を含めることができる:

  • セマンティックアクションは「一発勝負」です。マッチ失敗時の巻き戻し（backtrack）は不要です。
  • 名前予約表の更新など、文脈への直接的な操作が可能です。

• 先読み（Lookahead）と PEG の活用:

  • アクション内部で複雑な構文解析を行うことができます。
  • ユーザー定義関数内で PEG パースや Pratt 再帰を利用できます。

• 曖昧性の扱い:

  • グラムマチックな曖昧性はテーブル衝突として簡素化されます。
  • 複数のパーサーを組み合わせることで、より複雑な文法を構築できます。

4. アルゴリズム的・グラムマ的制約

Pratt パースを採用する際の重要な制限事項と前提条件です。

• 独立したレックス（Lexer）が必要:

  • スキャナレスモードや内包したレックス定義は使えません。明示的なトークン化フローが必要です。

• ステートメントパースの限界:

  • ステートメントを含む言語をパースするには、他の技術との組み合わせが必須です。

• 再帰降下パースの一種:

  • カスタムコード（セマンティックアクション）がパース選択を支配するため、コンテキスト依存型の解析が可能です。

• 漸進的パース（Incremental Parsing）不可:

  • Tree-sitter のようなツールの挙動には不向きです。

5. 結合度テーブルの運用ルール

Pratt パースにおける**契約（Convention）**を守ることで、正しく動作するパーサーを構築できます。

• LED のみ結合度を定義する:

  • NUD は結合度値を持つ必要がありません。

• プレフィックス演算子の結合度は不要:

  • プレフィックス演算子のためのテーブルスロットは必要ありませんが、静的テーブルでの統一のために埋めておいても構いません。

• LED の結合度をゼロにしてはいけない:

  • 優先順位が不明確になると解析エラーの原因になります。

• 区切り記号（Delimiter）は除外する:

  • コマや EOF トークンには結合度値を割り当てません。

• 結合度の値付けについて:

  • 10 の倍数を使用すると、人間の可読性が高まります。
  • 末尾のゼロは無視して構いませんが、演算子の優先順位は明確に区別する必要があります。

6. 右結合演算子への実装

通常のインフィックス演算子は左結合（

1 + 2 + 3

(1+2)+3

a = b = c

左結合の場合

auto bp = binding_power[code::plus_sign]; // 例：10
auto right = parse_expr(context, r, bp);

右結合への変換（bp - 1）

優先順位を 1 下げて、現在のトークンの右側にいる式に対して「より低い優先度」の期待値を与えます。

std::shared_ptr<ast::Expr> parse_additionr(
    ParsingContext& context, reader tok, reader& r,
    std::shared_ptr<ast::Expr> left)
{
    // ここが違いです: bp - 1 を使用することで、
    // 同じ優先度の演算子を右側に追加せず、終了させるロジックを実現します。
    auto right = parse_expr(context, r, binding_power[code::plus_sign] - 1);
    return ast::make_expr<ast::Addition>(tok.line(), tok.column(), left, right);
}

7. マクロとレックスリングの自由な相互交差

Pratt パースは、マクロ機能をパーサーレベルに統合することを可能にし、**無制限な eDSLs（埋め込みドメイン特定言語）**の実装を容易にします。

マクロの振る舞い

• 通常の Pratt パースにおける

  NUD

  や

  LED

  は、マクロとしても機能できます。
• マクロは「パースしている言語に対するインタプリタ」として動作し、レックスリングとパーサーを直接制御できます。

モーダルレックスリング（Modal Lexing）

これは Pratt 開発において最も重要な技術の一つです。文脈に応じてレックスルール自体が動的に変化する仕組みです。

実装例：スコープごとの挙動変化

// スコープごとに異なるトークン定義を切り替え可能にする
void next_on_class_scope();      // クラス構文用
void next_on_type_scope();       // 型注釈用（: の後に現れる）
void next_on_expr_scope();       // 通常式用

Rust のような言語では、型注釈 (

:

Vec<u32>

設計上の注意点:

• レックスラーは**プル設計（Pull Design）**に従う必要があります。
• IO やバッファリングによる副作用を持つ重い処理は行わず、軽量なコピーオブジェクトとして動作させるのが望ましいです。
• ファイル全体をメモリに読み込み（mmap など）、レックスラーが共有ポインタを指すことで、効率的な先読みが可能になります。

8. レックスリングの重要なトリック：1 トークンの巻き戻し

Pratt パースでは、

<<

std::shared_ptr<ast::Expr> parse_enter_type_scope(
    ParsingContext& context, reader tok, reader& r)
{
    assert(tok.code() == code::less_than_sign);
    r = tok; //< ここで 1 トークンの rollback が発生

    // 巻き戻し直後の状態から、型スコープのルールで再レックスリング
    auto& type = parse_type(context, r, parse_until_end);
}

このテクニックは、

<>

Vec<u32>

9. 結論：ブラックボックス化は禁物

Pratt パースを使用する際、最大のリスクは**「内部機構を理解せずにブラックボックスとして扱うこと」**にあります。

• 優先順位クライミングのみと捉えがち:

  • Pratt は単なる「優先順位クライミング」ではなく、コード構造を再定義するアプローチです。
  • アブストラクションを外して内部を見て理解することが、真の活用への近道です。

• 適応性の限界:

  • Alex Kladov 氏が提案したようなアルゴリズム自体の変更や、推論を拒否するような変更は避けるべきです。
  • アルゴリズムを変更すると、ブラックボックスとしての恩恵（簡潔さ）を失います。

Pratt パースの真価は、「左側に何が期待されるか」というシンプルさを肝に銘じつつ、NUD/LED テーブルとモーダルレックスリングを組み合わせて複雑な言語を実現するマインドセットにあります。これを実践することで、コンパイラ開発における新しい地平を拓くことが可能です。