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

Posted at 2025-04-14

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

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

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

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

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

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

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

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

Chumskyの特徴

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

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

Chumskyの基本概念

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

1. `Parser` トレイト

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

// '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() - 何も消費せずに成功する

例えば：

// "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) - 開始と終了のパーサーで囲まれたパーサー

例えば：

// "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 関数を使います：

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

Chumskyによるパース例

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

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

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

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パーサーの例では：

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

上記以外にも様々な例が紹介されています

エラー処理とリカバリー

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

公式ドキュメントには、エラー処理のためのさまざまな方法が記載されており、Error and recoveryセクションで詳しく説明されています。

パフォーマンス

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

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

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

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

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

これらの方法は、Chumskyガイドの「Getting Started」セクションのアドバイス部分に記載されています。

パーサーのデバッグ

Chumskyガイドのデバッグセクションには、パーサーをテストし、問題を特定するための様々なテクニックが紹介されています。

Chumskyの使い所

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

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

まとめ

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

参考リンク

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up