Zenn
🦀

Rust でパーサコンビネータを作ってみる (前編)

2022/01/24に公開
Rust
#
parser
tech

パーサーコンビネータ とは、小さなパーサーを 合成(combine) して複雑なパーサーを作り上げていく手法です。この記事では、Rust で簡単なパーサーコンビネータのライブラリを作成し、それを使って JSON をパースすることを目指します。

パーサーコンビネータの使用例

今回作成するパーサーコンビネータを使うと以下のようなコードが書けます。

// カンマ区切りの整数列を受け付けるパーサー
let digits_seq = separated(digits, character(','));
// "empty" というキーワードを受け取り、空の Vec を返すパーサー
let empty_keyword = map(string("empty"), |_| vec![]);
// カンマ区切りの整数列 または "empty" というキーワードを受け付けるパーサー
let parser = choice(digits_seq, empty_keyword);

// パースしてみる。
// .unwrap().0 でパース結果を取り出せる (詳しくは後述)
assert_eq!(parser("10,20,30").unwrap().0, vec![10, 20, 30]);
assert_eq!(parser("empty").unwrap().0,    vec![]);

digits, character(','), string("empty") が上で言っていた「小さなパーサー」に相当します。これらを separated や choice といった関数で組み合わせることで複雑な動作をするパーサーを作り上げています。

パーサーコンビネータの利点・欠点

パーサーコンビネータの利点はなんと言っても再利用性が高いことです。直交性の高い部品を組み合わせていく手法なので、各部品を容易に再利用できます。また、Rust のような汎用のプログラミング言語で文法を記述できるというのも嬉しい性質です。yacc や ANTLR のような専用の DSL を使う手法と比べると、関数やマクロといった言語の機能をそのまま利用できますし、エディタや周辺ツールのサポートも利用できます。

逆に、パーサーコンビネータの欠点は高階関数、すなわち「関数を受け取る関数」や「関数を返す関数」を多用することです。こういう関数に慣れていない人は理解に時間がかかると思います。また、Rust のクロージャはライフタイムの仕様が若干特殊なので、ここでハマる場合もあります（ハマりました）。

「パーサーとは何か」を考える

それでは、パーサーコンビネータのライブラリを作っていきましょう。具体的なコードの記述に入る前に 「パーサーとは何か」 を考えてみましょう。

  • パーサーは文字列を入力として取る。
  • パースに成功した場合、パーサーは何かを出力する。
  • パースに失敗した場合、パーサーはエラーを出力する。

とりあえずこんなところでしょう。これを Rust で表すと以下のようなトレイトになります。

Fn(&str) -> Option<T>

T はパースの結果となる型を表します。例えば整数のパーサーでは i64 などになるでしょう。Option はパースエラーを表現するために入れています。本当はエラーの発生した行や詳細なメッセージなどを伝搬するために Result 型にすべきですが、この記事では実装を簡単にするために Option で妥協します。

しかし、残念ながらこれだけではパーサーを合成していくことができません。ちょっと天下り的ですが、パーサーの定義を少し変更して、次のようにしてみましょう。

Fn(&str) -> Option<(T, &str)>

さっきの定義との違いは、戻り値の型が Option<T> から Option<(T, &str)> になったことです。戻り値の &str は パースされずに残った部分 を表します。この記事ではパーサーの定義として、このトレイトを採用することにします。

最初のパーサー: digits

最初のパーサーとして digits という関数を定義しましょう。これは、引数として与えられた文字列の先頭にある整数をパースし、その結果と残りの文字列を返します。パースに失敗した場合は None を返します。こんな感じです。

assert_eq!(digits("123*456"), Some((123, "*456")));
assert_eq!(digits("ABCDEFG"), None);

digits の実装は String の find メソッドと parse メソッドを使って以下のように書けます。

// s の先頭にある整数をパースし、整数値と残りの文字列を返す。
// パースに失敗した場合は None を返す。
pub fn digits(s: &str) -> Option<(i64, &str)> {
    let end = s.find(|c: char| !c.is_ascii_digit()).unwrap_or(s.len());
    match s[..end].parse() {
        Ok(value) => Some((value, &s[end..])),
        Err(_) => None,
    }
}

これで「小さなパーサー」が一つできました。この「文字列の先頭にある何か」をパースするという動きは今後定義するすべてのパーサーに共通する性質です。

特定の1文字をパースするパーサー: character

「小さなパーサー」をもう一つ作ってみましょう。特定の1文字をパースする character というパーサーです。以下に使用例を示します。

let parser = character('🍰');
assert_eq!(parser("🍰 yey!"), Some(((), " yey!")));
assert_eq!(parser("no cake"), None);

digits と使い方が違うことに気付いたでしょうか？ digits はそれ自体がパーサーでした。一方、character は引数として文字を渡すとパーサーが返ってきて、それに文字列を渡すとパース結果が返ってきます。

上で説明した通り、パーサーは関数です。よって、character は関数を返す関数、すなわち高階関数になっています。

実装はこうなります:

// 先頭の一文字が c であるときに成功して () を返すようなパーサーを返す。
pub fn character(c: char) -> impl Fn(&str) -> Option<((), &str)> {
    move |s| {
        let mut chars = s.chars();
        if chars.next() == Some(c) {
            Some(((), chars.as_str()))
        } else {
            None
        }
    }
}

実装を詳しく見ていきましょう。まず戻り値の型は impl Fn(&str) -> Option<((), &str)> です。上で述べたとおり、これは () を結果とするパーサーを表しています。

関数の内部ではクロージャを作って返しています。クロージャの前についている move は、このクロージャが外部の変数(つまりc)を参照ではなく move を使ってキャプチャすることを表しています。クロージャを関数から返したい場合、ローカル変数への参照をクロージャが持っていると困るため、ほぼ確実に move でキャプチャすることになります。

クロージャの内部では、s の先頭一文字をイテレータ経由で取得して c と比較しています。ここは普通のコードなので詳しい解説は省きます。

トレイトに別名をつける

ここまで Fn(&str) -> Option<(T, &str)> はパーサーですと言ってきたわけですが、このトレイトを何度もタイプするのは大変ですし、読むときもこれが何度も出てきたら目が滑ってしまいます。このトレイトにどうにかして短い別名をつけれないでしょうか？

結論から言うと、完全な別名にはなりませんが、ほぼ別名として使える名前を定義できます。

以下のように書いてください。

// Parser<T> を Fn(&str) -> Option<(T, &str)> の別名(のようなもの)として定義する。
pub trait Parser<T>: Fn(&str) -> Option<(T, &str)> {}
impl<T, F> Parser<T> for F where F: Fn(&str) -> Option<(T, &str)> {}

簡単に何をやっているか説明すると、一行目で Fn(&str) -> Option<(T, &str)> を継承して Parser<T> を定義しています。二行目で Fn(&str) -> Option<(T, &str)> を実装しているすべての型に対して Parser<T> を実装しています。

では、Parser<T> を使って character を書き直してみましょう。

pub fn character(c: char) -> impl Parser<()> {
    move |s| {
        ...
    }
}

するとどうでしょう。なんとエラーになります。実は Rust のクロージャの型の推論の都合でこのコードは型がマッチしません。残念ながらワークアラウンドが必要になります。

まず、以下の関数を定義します。

// クロージャの型推論を補助するための関数
// cf. https://github.com/rust-lang/rust/issues/70263#issuecomment-623169045
fn generalize_lifetime<T, F>(f: F) -> F
where
    F: Fn(&str) -> Option<(T, &str)>,
{
    f
}

そして、character の定義に出てきたクロージャをこの関数でラップします。

// 先頭の一文字が c であるときに成功して () を返すようなパーサーを返す。
pub fn character(c: char) -> impl Parser<()> {
    generalize_lifetime(move |s| {
        ...
    })
}

これで無事コンパイルが通りました。ちょっと不格好ですが、これ以上簡潔なやり方を知らないのでこれで行きます。

まとめると

  1. Parser<T> を Fn(&str) -> Option<(T, &str)> の別名として定義した。
  2. クロージャを impl Parser<T> として返すときは generalize_lifetime でラップする。さもなくば型エラーになる。

となります。

空白を読み飛ばす: lexeme

パーサーを書いていると、空白を読み飛ばさないといけない状況がよく発生します。例えば、JSON の場合、トークンの間に自由に空白を挿入できるので、パースの際はそれらを読み飛ばさなければなりません。

ということで、パーサーを受け取って、先頭の空白を読み飛ばすようにしたパーサーを返すような関数 lexeme を定義しておくと便利でしょう。これも高階関数です。

まず使用例を示します。

let parser = lexeme(digits);
assert_eq!(parser("    123    hello"), Some((123, "    hello")));

実装は String::trim_start を使って以下のように書けます。

// パーサーを受け取って、先頭の空白を読み飛ばすようにしたパーサーを返す
pub fn lexeme<T>(parser: impl Parser<T>) -> impl Parser<T> {
    generalize_lifetime(move |s| {
        parser(s.trim_start())
    })
}

Parser<T> の実体は関数やクロージャであることに注意してください。

特定の文字列をパースするパーサー: string

どんどん行きましょう。string は character の文字列版です。strip_prefix のおかげで character より簡単に実装できます。

pub fn string(target: &'static str) -> impl Parser<()> {
    generalize_lifetime(move |s| {
        s.strip_prefix(target).map(|rest| ((), rest))
    })
}

#[test]
fn test_string() {
    let parser = string("hello");
    assert_eq!(parser("hello world"), Some(((), " world")));
    assert_eq!(parser("hell world"), None);
}

パースの結果に関数を適用する: map

次の関数はとても重要です。

map はパース結果に対して関数を適用する関数です。例えば、以下の例ではパース結果に 1 を足しています。

let parser = map(digits, |x| x + 1);
assert_eq!(parser("1"), Some((2, "")));
assert_eq!(parser("X"), None);

map はパースの結果を使って AST を組み立てたりするときに必須となる関数です。これからの例でもよく出てきます。

map の実装は、Option::map を使って以下のように書けます。

pub fn map<A, B>(
    parser: impl Parser<A>,
    f: impl Fn(A) -> B,
) -> impl Parser<B> {
    generalize_lifetime(move |s| {
        parser(s).map(|(value, rest)| (f(value), rest))
    })
}

複数の選択肢を試す: choice

choice は "または" を表現する関数です。以下の例のように複数の選択肢の中から一つにマッチするようなパーサーを生成します。

// 数値または "null" から成る文字列を受け取るパーサー。
// "null" をパースすると結果は 0 になる。
let parser = choice(
    digits,
    map(string("null"), |_| 0),
);
assert_eq!(parser("1234"), Some((1234, "")));
assert_eq!(parser("null"), Some((0, "")));
assert_eq!(parser("hoge"), None);

ここまで来るとパーサーを合成してる感が出てきましたね。

実装は Option::or_else を使って以下のようになります。

pub fn choice<T>(
    parser1: impl Parser<T>,
    parser2: impl Parser<T>,
) -> impl Parser<T> {
    generalize_lifetime(move |s| {
        parser1(s).or_else(|| parser2(s))
    })
}

注意点として、文字列が両方のパーサーにマッチするときは最初のパーサーの結果が採用されます。

選択肢が3つ以上ある場合も choice を繰り返し使うことで対応できます。ちょっとコードが煩雑になるのでマクロ化しておきましょう。

#[macro_export]
macro_rules! choice {
    ($parser0:expr, $($parser:expr),*) => {{
        let p = $parser0;
        $(
            let p = $crate::parsers::choice(p, $parser);
        )*
        p
    }};
}

#[test]
fn test_choice_macro() {
    let parser = choice![
        map(string("zero"), |_| 0),
        map(string("one"),  |_| 1),
        digits
    ];
    assert_eq!(parser("zero"), Some((0,  "")));
    assert_eq!(parser("one"),  Some((1,  "")));
    assert_eq!(parser("42"),   Some((42, "")));
    assert_eq!(parser("hoge"), None);
}

注意点として、このマクロは末尾にカンマを書くとエラーになります。気になる人は The Little Book of Rust Macros の Trailing separators に修正方法が載っています。

パーサーを連結する: join

join はふたつのパーサーを連結してそれらの結果をタプルで返す関数です。以下のコードは '+' または '-' をパースするパーサーの後ろに数値のパーサーを連結する例です。

let plus_minus = choice(
    map(character('+'), |_| '+'),
    map(character('-'), |_| '-'),
);
// 符号付き整数パーサー
let parser = join(plus_minus, digits);   
assert_eq!(parser("+123"), Some((('+', 123), "")));
assert_eq!(parser("-123"), Some((('-', 123), "")));
assert_eq!(parser("-abc"), None);
assert_eq!(parser("*123"), None);

実装は以下のようになります。今度は Option::and_then が出てきました。

pub fn join<A, B>(
    parser1: impl Parser<A>,
    parser2: impl Parser<B>,
) -> impl Parser<(A, B)> {
    generalize_lifetime(move |s| {
        parser1(s).and_then(|(value1, rest1)| {
            parser2(rest1).map(|(value2, rest2)| {
                ((value1, value2), rest2)
            })
        })
    })
}

これも任意個の引数を受け取れるようにマクロ化しておきましょう。

#[macro_export]
macro_rules! join {
    ($parser0:expr, $($parser:expr),*) => {{
        let p = $parser0;
        $(
            let p = $crate::parsers::join(p, $parser);
        )*
        p
    }};
}

#[test]
fn test_join_macro() {
    // スペース区切りで数値をちょうど3つ受け付けるパーサー
    let parser = join![
        lexeme(digits),
        lexeme(digits),
        lexeme(digits)
    ];
    assert_eq!(parser("10 20 30"), Some((((10, 20), 30), "")));
    assert_eq!(parser("10 20 AA"), None);
}

この join! マクロはちょっと微妙な点があります。上のテストの例の場合、本来であれば (10, 20, 30) という値が返ってきてほしいのですが、実際には ((10, 20), 30) と、タプルがネストした形で返ってきます。残念ですが、簡単に修正する方法を思いつかなかったので、この記事ではこのままの仕様で行こうと思います。

0回以上の繰り返し: many

「繰り返し」はパーシングにおいて頻出です。0回以上の繰り返しを表現する関数 many を作りましょう。

pub fn many<T>(parser: impl Parser<T>) -> impl Parser<Vec<T>> {
    generalize_lifetime(move |mut s| {
        let mut ret = vec![];
        while let Some((value, rest)) = parser(s) {
            ret.push(value);
            s = rest;
        }
        Some((ret, s))
    })
}

#[test]
fn test_many() {
    let parser = many(lexeme(digits));
    assert_eq!(parser("10 20 30"), Some((vec![10, 20, 30], "")));
    assert_eq!(parser(""),         Some((vec![], "")));
    assert_eq!(parser("10 hello"), Some((vec![10], " hello")));
}

何かで区切られた列: separated

「カンマ区切りの列」のように何かで区切られた列をパースすることはよくあります。ということで、こういう何かで区切られた列をパースする関数 separated を用意しましょう。

pub fn separated<T>(
    parser: impl Parser<T>,
    separator: impl Parser<()>,
) -> impl Parser<Vec<T>> {
    generalize_lifetime(move |mut s| {
        let mut ret = vec![];

        match parser(s) {
            Some((value, rest)) => {
                ret.push(value);
                s = rest;
            }
            None => {
                return Some((ret, s));
            }
        }

        while let Some((_, rest)) = separator(s) {
            s = rest;
            match parser(s) {
                Some((value, rest)) => {
                    ret.push(value);
                    s = rest;
                }
                None => {
                    return None;
                }
            }
        }

        Some((ret, s))
    })
}

#[test]
fn test_separated() {
    // カンマ区切りの数値の列のパーサー
    let parser = separated(digits, character(','));
    assert_eq!(parser("1,2,3"), Some((vec![1, 2, 3], "")));
    assert_eq!(parser(""),      Some((vec![],        "")));
}

この separated はいわゆる「ケツカンマ」を許容しません。末尾に無駄な separator があると即エラーになるので注意してください。

正規表現パーサー: regex

最後に便利なパーサーを導入しましょう。正規表現パーサー regex です。

regex は正規表現 re と関数 f を取り、以下のような動きをするパーサーを返します。

  1. 入力文字列に対して正規表現 re をマッチさせる。
  2. マッチしなかった場合はパース失敗であり、None を返す。
  3. マッチした場合はその部分文字列を f に渡す。
  4. f が None を返した場合はパース失敗であり、None を返す。
  5. f が Some(x) を返した場合はパース成功であり、x をパース結果として返す。

正規表現にマッチした部分文字列をそのままパース結果としないのはライフタイムの扱いを楽にするためです。部分文字列をスライスとして持ち運ぼうとするとライフタイムの扱いが面倒ですし、かといって部分文字列を to_owned() してしまうとコピーが発生して効率が悪くなります。そこで、f を挟むことで部分文字列をどのように扱うのかの判断を呼び出し元に委ねることにしました。呼び出し元が文字列として結果を受け取ることを希望するなら f で to_owned() すればいいですし、別の表現(例えば i64)に変換したいならば f で変換してしまえばよいです。

さて、今回は使用例より前に実装を示します。regex の実装は以下の通りです。

// [dependencies]
// regex = "1"

use regex::Regex;

pub fn regex<'a, T>(
    re: &'a Regex,
    f: impl Fn(&str) -> Option<T> + 'a,
) -> impl Parser<T> + 'a {
    generalize_lifetime(move |s| {
        re.find(s).and_then(|matched| {
            f(matched.as_str()).map(|value| {
                let rest = &s[matched.end()..];
                (value, rest)
            })
        })
    })
}

ライフタイムがちょっと難しいことになっています。引数や戻り値の型に書いてある impl Something + 'a という指定は、トレイト Something を実装していることに加えて ライフタイム制約 'a も満たしていなければならない、という意味になります。今回の場合、戻り値であるクロージャより先に re や f が死んでしまうと困るので、そうならないようにライフタイムを縛っているわけです。

実は上の方に出てきた string という関数も同じやり方でライフタイムを 'static から 'a に緩和できます。興味がある人はやってみてください。

さて、では regex を使っていきましょう。

// 識別子っぽい文字列をパース
let re = Regex::new(r"^[a-zA-Z_][a-zA-Z0-9_]*").unwrap();
let parser = regex(&re, |s| Some(s.to_owned()));
assert_eq!(parser("x_1=0"), Some(("x_1".to_owned(), "=0")));
assert_eq!(parser("0_1=0"), None);

ここで問題なのが、Regex::new が遅いことです。この例は一回しか実行されないので問題ないですが、実際の使用例ではループの中で何度もパーサーを作成する場合があり、そのたびに Regex::new されては困ります。よって、Regex::new の結果を覚えておいて使いまわしたいです。こういうときに便利なのが static 変数と once_cell クレート の組み合わせです。これらを使うことで、プロセスの寿命を通じて一度だけ初期化される変数を作ることができます (ちょうど C++ の static 変数のような動きになります)。

// [dependencies]
// once_cell = "1"

use once_cell::sync::Lazy;

// 識別子っぽい文字列をパース
const PATTERN: &str = r"^[a-zA-Z_][a-zA-Z0-9_]*";
static RE: Lazy<Regex> = Lazy::new(|| Regex::new(PATTERN).unwrap());
let parser = regex(&RE, |s| Some(s.to_owned()));
assert_eq!(parser("x_1=0"), Some(("x_1".to_owned(), "=0")));
assert_eq!(parser("0_1=0"), None);

regex 関数を使うたびに Lazy::new とかするのは地味に面倒なのでマクロ化しておきましょう。

#[macro_export]
macro_rules! regex {
    ($pattern:expr, $f:expr) => {{
        use regex::Regex;
        use once_cell::sync::Lazy;
        static RE: Lazy<Regex> = Lazy::new(|| Regex::new($pattern).unwrap());
        $crate::parsers::regex(&RE, $f)
    }};
}

以下のように使います。

let parser = regex!(r"^[a-zA-Z_][a-zA-Z0-9_]*", |s| Some(s.to_owned()));
assert_eq!(parser("x_1=0"), Some(("x_1".to_owned(), "=0")));
assert_eq!(parser("0_1=0"), None);

おわりに

長かったですが、これでパーサーコンビネータを一通り作り終えました！これで前半は終わりです。

この記事で作成したパーサーコンビネータのソースコードは GitHub に置いていますので、手元で試したい人はご参照ください。

後編ではこのパーサーコンビネータを使って JSON のパーサーを作っていきたいです。

Discussion