【Rust】表現力豊かなパーサーChumsky

「パーサー」とは、構造化されていないデータ（テキストファイルやバイト列など）を、プログラムが処理しやすい構造化されたデータ（抽象構文木など）に変換するプログラムのことです。例えば、JSONファイルの解析、プログラミング言語のコンパイル、設定ファイルの読み込みなど、多くの場面でパーサーが活躍します。

この記事では、Rustで書かれたパーサーコンビネータライブラリ「[Chumsky](https://github.com/zesterer/chumsky)」を紹介します。パーサーコンビネータとは、小さなパーサーを組み合わせて複雑なパーサーを構築するアプローチです。

## パーサーコンビネータとは

従来は手動で状態遷移を管理する命令型スタイルが一般的です。しかし、この方法では複雑なパーサーを書くのは時間がかかり、エラーも発生しやすくなります。

パーサーコンビネータは宣言型アプローチを採用しており、パーサーの「動作方法」ではなく「パースする対象」に焦点を当てます。これにより、短く読みやすいコードでパーサーを構築できます。

例えば、以下のようなJSONのような構造をパースしたい場合：

```json
{
  "name": "John",
  "age": 30,
  "is_active": true
}
```

パーサーコンビネータを使うと、各要素（文字列、数値、ブール値、オブジェクト）のパーサーを個別に定義し、それらを組み合わせて全体のパーサーを構築できる、とのことです。

## Chumskyの特徴

Chumskyは、Rustのパーサーコンビネータライブラリとして以下の特徴を持っています：

- 🪄 **表現力豊かなコンビネータ** - パーサー作成が直感的で楽しく
- 🎛️ **完全なジェネリック性** - 入力、トークン、出力、スパン、エラー型など全てにわたって
- 📑 **ゼロコピーパース** - メモリ割り当てを最小限に抑え、入力から直接参照を保持
- 🚦 **柔軟なエラー回復** - エラーが発生しても処理を続行できる仕組み
- ☑️ **チェックのみモード** - 高速な入力検証をサポート
- 🚀 **内部最適化** - 高性能なパーサーを自動生成
- 📖 **テキスト指向** - テキスト入力（`&[u8]`や`&str`）に特化した機能
- 👁️‍🗨️ **文脈自由文法** - 高度な構文解析をサポート
- 🏷️ **パターンラベリング** - ユーザーフレンドリーなエラーメッセージ
- 🗃️ **キャッシング** - パーサーを一度作成して何度も再利用可能

## Chumskyの基本概念

Chumskyを理解するには、いくつかの基本概念を押さえる必要があります：

### 1. `Parser` トレイト

Chumskyの中心となるのは `Parser` トレイトです。このトレイトは入力から出力を生成する能力を持つ型を表します。実際にパースを行うには、`parse` や `check` などのメソッドを使用します。

```rust
// 'Parser' トレイトを実装した型の例
fn my_parser<'a>() -> impl Parser<'a, &'a str, MyOutputType> {
    // パーサーの定義...
}

// パーサーを使用
let result = my_parser().parse(input_string);
```

### 2. プリミティブパーサー

Chumskyには、基本的なパースを行うプリミティブパーサーが多数用意されています：

- `just(x)` - 特定の値だけを受け付ける
- `any()` - どんな値でも受け付ける
- `end()` - 入力の終端にマッチする
- `empty()` - 何も消費せずに成功する

例えば：

```rust
// "hello"という文字列にだけマッチするパーサー
let hello = just("hello");

// 任意の数字にマッチするパーサー
let digit = any().filter(|c: &char| c.is_digit(10));
```

### 3. コンビネータ

小さなパーサーを組み合わせて複雑なパーサーを作るには、コンビネータを使います：

- `.or(other)` - どちらかのパーサーにマッチ
- `.then(other)` - 一方のパーサーの後に他方のパーサーが続く
- `.repeated()` - パーサーを0回以上繰り返す
- `.delimited_by(start, end)` - 開始と終了のパーサーで囲まれたパーサー

例えば：

```rust
// "hello" または "world" にマッチするパーサー
let hello_or_world = just("hello").or(just("world"));

// 数字の後に "px" が続くパターンにマッチするパーサー（例："42px"）
let pixels = text::int(10).then(just("px"));
```

### 3. 変換と抽出

パースした値を変換したり、必要な部分だけを抽出したりするメソッドもあります：

- `.map(f)` - パース結果を関数 `f` で変換
- `.to(val)` - パース結果を常に `val` に置き換える
- `.ignore()` - パース結果を捨てる


### 5. 再帰的なパーサー

再帰的な構造（例：式やネストされたブロック）をパースするには、`recursive` 関数を使います：

```rust
// 再帰的な括弧の式をパースする例
let expr = recursive(|expr| {
    let atom = number.or(expr.delimited_by(just('('), just(')')));
    // さらに演算子などを処理...
    atom
});
```

## Chumskyによるパース例

Chumskyでパーサーを作る一般的な手順は次のとおりです：

1. パース結果を表現するデータ構造（抽象構文木など）を定義する
2. 小さなパーサーを組み合わせて全体のパーサーを構築する
3. 入力にパーサーを適用する
4. 結果を処理する

以下は、Brainfuck言語をパースする例です：

```rust
use chumsky::prelude::*;

/// Brainfuck命令のための抽象構文木（AST）
#[derive(Debug, Clone)]
enum Instr {
    Left, Right,
    Incr, Decr,
    Read, Write,
    Loop(Vec<Self>), // Brainfuckでは、`[...]`ループ命令は任意の数の命令を含む
}

/// Brainfuckパーサーを生成する関数
fn brainfuck<'a>() -> impl Parser<'a, &'a str, Vec<Instr>> {
    // Brainfuck構文は再帰的: 各命令は多くのサブ命令を含むことができる（`[...]`ループを介して）
    recursive(|bf| choice((
        // すべての基本命令は単一の文字
        just('<').to(Instr::Left),
        just('>').to(Instr::Right),
        just('+').to(Instr::Incr),
        just('-').to(Instr::Decr),
        just(',').to(Instr::Read),
        just('.').to(Instr::Write),
        // ループは角括弧で区切られたBrainfuck命令の文字列
        bf.delimited_by(just('['), just(']')).map(Instr::Loop),
    ))
        // Brainfuck命令は連続して現れるので、必要な数だけ解析
        .repeated()
        .collect())
}

fn main() {
    let code = "--[>--->->->++>-<<<<<-------]>--.>---------.>--..+++.>----.>+++++++++.<<.+++.------.<-.>>+.";
    
    // Brainfuckコードをパース
    let result = brainfuck().parse(code);
    
    match result {
        Ok(instructions) => println!("パース成功: {:?}", instructions),
        Err(errors) => println!("エラー: {:?}", errors),
    }
}
```

このBrainfuckパーサーの例では：

1. まず `Instr` 列挙型で抽象構文木（AST）を定義しています
2. `recursive` 関数を使って再帰的なパーサーを作成しています
3. 基本命令（`<`, `>`, `+`, `-`, `,`, `.`）は `just` と `to` を使って簡単に定義
4. ループ構造（`[...]`）は `delimited_by` を使って定義し、内部に再帰的にBrainfuck命令を含む
5. `repeated` と `collect` を使って複数の命令をベクトルにまとめています

上記以外にも様々な[例](https://github.com/zesterer/chumsky/tree/main/examples)が紹介されています

## エラー処理とリカバリー

Chumskyは優れたエラー処理機能を備えています。パースエラーが発生した場合でも、一定の回復を試みることで、複数のエラーを一度に報告したり、部分的な結果を生成したりできます。

公式ドキュメントには、エラー処理のためのさまざまな方法が記載されており、[Error and recovery](https://docs.rs/chumsky/latest/chumsky/guide/_03_error_and_recovery/index.html)セクションで詳しく説明されています。

## パフォーマンス

Chumskyは高性能なパーサーを生成することを重視しています。内部的に最適化が行われるため、「手書き」のパーサーと同等あるいはそれ以上のパフォーマンスを発揮することもあります。

以下はJSONパース処理のベンチマーク結果の一例です：

| ランキング | ライブラリ | 時間 (小さいほど良い) | スループット |
|------------|------------|------------------------|--------------|
| 1 | `chumsky` (check-only) | 140.77 µs | 797 MB/s |
| 2 | `winnow` | 178.91 µs | 627 MB/s |
| 3 | `chumsky` | 210.43 µs | 533 MB/s |
| 4 | `sn` (hand-written) | 237.94 µs | 472 MB/s |
| 5 | `serde_json` | 477.41 µs | 235 MB/s |

## 実用的なヒントとプラクティス

### コンパイルエラーへの対処

複雑なパーサーでコンパイルエラーが発生することがあります。ドキュメントでは以下の対処法が提案されています：

1. 常に最初のエラーから解決していく
2. `.boxed()` メソッドを使ってパーサーの型を簡略化する
3. 長い `.or()` チェーンの代わりに `choice()` を使用する

これらの方法は、Chumskyガイドの「Getting Started」セクションの[アドバイス](https://docs.rs/chumsky/latest/chumsky/guide/_00_getting_started/index.html#advice)部分に記載されています。

### パーサーのデバッグ

Chumskyガイドの[デバッグセクション](https://docs.rs/chumsky/latest/chumsky/guide/_05_debugging/index.html)には、パーサーをテストし、問題を特定するための様々なテクニックが紹介されています。

## Chumskyの使い所

Chumskyは以下のような場面で特に役立ちます：

1. **コンパイラやインタプリタの作成** - プログラミング言語のパーサーを簡単に実装
2. **設定ファイルの解析** - JSON、YAML、TOML、独自形式などの構造化データを解析
3. **ドメイン固有言語（DSL）の実装** - 特定の用途に特化した言語を作成
4. **データ検証** - 複雑な入力検証ルールを実装
5. **プロトコルパーサー** - ネットワークプロトコルや通信フォーマットを解析

## まとめ

Chumskyは、Rustで高性能かつ表現力豊かなパーサーを簡単に作成できるライブラリです。宣言型のアプローチを採用することで、コードの可読性と保守性を高めながら、高速なパーサーを実現しています。

## 参考リンク

- [Chumsky GitHub](https://github.com/zesterer/chumsky)
- [Chumsky ドキュメント](https://docs.rs/chumsky/latest/chumsky/)
- [Chumsky ガイド](https://docs.rs/chumsky/latest/chumsky/guide/index.html)