この記事はEDOCODE Advent Calendar 2024、12月03日(火)の記事です。

1つ前の記事はktat
(Kato Atsushi)さんによる実際のアクセスに近づけたAPIの負荷テストを行うでした。
実運用環境に近い形でのテストについて解説されているので、ぜひご覧ください。

また、グループ親会社であるWanoのAdvent Calenderもあります。
こちらでも様々な技術的な知見が共有されているので、合わせてチェックしてみてください！

パーサーを書きたくなったことはありますか？

いきなりパーサーとは何かと言われても分からない方もいるかもしれませんが、最も一般的に使われるパーサーである正規表現を書いたことがある人は多いのではないでしょうか？

文字列等にフォーマットされたデータをプログラムで読み込んで使う際には、文字列などから情報を取り出す為にパーサーが使われています。正規表現もこの用途に用いられる事が多いです。

正規表現で十分なケースが多いですが、正規表現では対応できないケースもあります。

例えば、以下のような入れ子構造を持つ文字列を正確にパースすることは正規表現では困難です。

((1 + 2) * (3 + 4)) のような数式
{name: {first: "John", last: "Doe"}} のような任意のネストされたJSON
<div><p>Hello <em>World</em></p></div> のような入れ子のあるHTML/XML

こういった構造は前後の関係などを見ながら解析する必要があるので正規表現では対応できません。

この様なデータをパースしたい場合には正規表現ではないパーサーを用意する必要が出てきます。

正規表現ではないパーサーとは？

正規表現以外のパーサーには、大きく分けて以下のような種類があります。

再帰下降構文解析: プログラムで直接パーサーを実装する手法で、文法規則を関数として表現します。
パーサージェネレータ: yacc/bisonなどのツールで、文法規則を定義すると自動的にパーサーを生成してくれます。
パーサーコンビネーター: 小さなパーサーを組み合わせて複雑なパーサーを作る手法です。

この記事では簡単にパーサーを実装できるパーサーコンビネーターについて見ていきます。

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

パーサーコンビネーターは、小さなパーサーを組み合わせて複雑なパーサーを作る手法です。
単純なパーサーを組み合わせる(combine)ことでより複雑なパーサーを組み上げていきます。

例えば括弧があって演算が足し算・引き算だけの数式をパースする場合は、以下のような感じでパーサーを組み合わせていきます。

数字を1文字読み取るパーサー
数字を1文字以上読み取るパーサー (上記を1回以上繰り返す)
演算子(+/-)を読み取るパーサー
括弧を読み取るパーサー
括弧で括られた式を読み取るパーサー
項を読み取るパーサー
数式全体を読み取るパーサー

言葉だけではちょっと分かりにくいですね。
次の章から具体的にどの様にパーサーコンビネーターでパーサーを作っていくのか見ていきましょう。

パーサーコンビネーターで数式パーサーを実装しよう

ではこれからパーサーの実装をしていきましょう。
今回はRust言語で実装していきます。

パースして取り出したデータで作るデータ構造を定義

まずは最初にパースして取り出したデータで作るデータ構造を定義しましょう。
今回は数値と足し算と引き算と括弧からなる数式をパースするので、それに対応するデータ構造を定義します。

数式は演算子の両隣に項があるという形をしています。
また項は単独の数値または括弧で括られた数式という形をしています。
また数式には暗黙の括弧がある場合があります。
例えば 1 + 2 + 3 は (1 + 2) + 3 や 1 + (2 + 3) と見なせます。
今回は暗黙の括弧は左側に付くこととします。
これをそのままデータ構造に反映させてみましょう。

#[derive(Debug, PartialEq)]
enum Expr {
    Number(i32),
    BinOp(Box<Expr>, char, Box<Expr>),
}

こんな定義になりました。

1 + 2 + 3 であれば

Expr::BinOp(
    Box::new(Expr::BinOp(
            Box::new(Expr::Number(1)),
            '+',
            Box::new(Expr::Number(2))
            )),
    '+',
    Box::new(Expr::Number(3)),
)

パース後はこんな感じのデータ構造になります（こうなるように後でパーサーを実装します）。
ちゃんと演算子の左側に括弧が付いているかのような構造になっていますね。

パースする対象の構文を定義

次はパーサーを実装する前にパースする対象の構文をきちんと定義しましょう。
パース対象の事を正しく理解していないとパースできないですからね！

構文を定義するにはBNF(バッカス・ナウア)記法を使うと便利です。

BNF記法とは文法規則を定義するための表記法です。
プログラミング言語やデータ形式の構文を厳密に定義するのによく使われます。

BNF記法の基本的な要素を説明すると:

<何か> は「何か」という名前の規則を表します
::= は「次のように定義される」という意味です
| は「または」を表します
"文字" は実際の文字を表します

といった感じです。

例えば日本の郵便番号だったら次のようなBNF記法で表現できます。

<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<first_3_digits> ::= <digit> <digit> <digit>
<last_4_digits> ::= <digit> <digit> <digit> <digit>
<zipcode> ::= <first_3_digits> "-" <last_4_digits>

でもちょっとBNF記法で書くのは面倒ですね。
特に3桁とか4桁とかの繰り返しの表現が面倒です。

そこで厳密な文書ではやめた方がいいですが、設計用の書き捨てドキュメントでは正規表現で拡張した表記を使うと便利です。

先程の例を正規表現で拡張した表記で表現すると次のようになります。

<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<first_3_digits> ::= <digit>{3}
<last_4_digits> ::= <digit>{4}
<zipcode> ::= <first_3_digits> "-" <last_4_digits>

繰り返しの所がスッキリしましたね.

ではこの正規表現で拡張したBNF記法を使って数式の構文を定義していきましょう。
今回は話を簡単にする為に演算子は足し算(+)と引き算(-)だけにします（掛け算と割り算が入ると優先度の問題を反映しないといけないので）。

<space> ::= " "
<spaces> ::= <space>*
<zero> ::= "0"
<nonzero> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<digit> ::= <zero> | <nonzero>
<number> ::= <digit> | <nonzero> <digit>+
<paren_left> ::= <spaces> "(" <spaces>
<paren_right> ::= <spaces> ")" <spaces>
<paren_expr> ::= <paren_left> <expression> <paren_right>
<term> ::= <spaces> (<number> | <paren_expr>) <spaces>
<operator> ::= <spaces> ("+" | "-") <spaces>
<expression> ::= <term> (<operator> <term>)*

<zero>と<nonzero>に分けているのは<number>の定義が表す対象に 001 みたいな0始まりの数値を含めないようにする為です。

これで数式の構文を定義できましたね。

パーサーを実装

今回はRustでnomというパーサーコンビネーターを使って数式パーサーを実装してみましょう。

パーサーコンビネーターは先ほど使った『正規表現で雑に拡張したBNF記法』に対応する便利関数を提供してくれている事が多い(結局そういう部分が実装する上で面倒なので…)ので、先程のBNF記法による定義を概ねそのままコードに落とし込む事ができます。

先に必要な関数をインポートします。

use nom::{
    branch::alt,
    character::complete::{char, one_of, space0},
    combinator::{map, recognize},
    multi::{many0, many1},
    sequence::{delimited, pair, tuple},
    IResult,
};

インポートしているもののうちIResultはパーサーの結果(成功・失敗)を表すResultのエイリアスです。
その他はこの後の実装の説明の中で順次解説していきます。

まずは <space> と <spaces> から取り掛かりましょう。
しかし何とこれはほぼそのまま対応する関数 nom::character::complete::space0 がnomから提供されていますので、これをそのまま使うだけでOKです。

次は <zero> と <nonzero> です。

『特定の文字』に対応するnom::character::complete::charと、『どれかの文字』に対応するnom::character::complete::one_ofを使うと実装できます。

fn zero(input: &str) -> IResult<&str, char> {
    char('0')(input)
}

fn nonzero(input: &str) -> IResult<&str, char> {
    one_of("123456789")(input)
}

これで0と1〜9という文字をパースするパーサーが実装できました！

次は <digit> です。
<digit> は <zero> または <nonzero> なので、『どちらか成功した方の結果を返す』に対応する nom::branch::alt を使って zero または nonzero を返すようにします。

fn digit(input: &str) -> IResult<&str, char> {
    alt((zero, nonzero))(input)
}

altというnomが提供するコンビネーター関数に自分で作った極小のパーサーであるzeroとnonzeroを組み合わせてdigitを実装できました！
パーサーコンビネーターを使ったパーサーの実装はこの様な感じで小さいパーサーを組み合わせて少しずつ大きなパーサーを作っていきます。

次は <number> です。
<number>の構文定義は<number> ::= <digit> | <nonzero> <digit>+となっており、<digit>または<nonzero>に続けて<digit>が1文字以上続くものとなっています。
ただ、ここまでに実装したdigit関数はcharを返しますが、2文字以上の数字からなる数値はどう考えても文字列です。
|に対応するnom::branch::altは引数に取るパーサーの型が一致することを要求してくるので、1文字だけのケースと2文字以上のケースの両方とも型が同じになるようにする必要があります。

ここでちょっと視点を変えてみます。
今対象としている数値は数字が1文字以上連続して並んでいるものです。
つまり連続した数字列をパーサーが読み取った区間を文字列として取れば簡単に両者の型を合わせられそうです。
（もちろんパーサーの戻り値を数値に変換して合わせる方法もあります）。

そこでnom::sequence::recognizeを使います。
これは引数に渡したパーサーが読み取った区間を文字列として返す関数で、今回の目的にぴったりです。

<digit>+という部分は、パーサーの1回以上の繰り返しに対応するnom::multi::many1というコンビネーターがあるのでこれを使います。

<nonzero> <digit>+という部分は2つのパーサーを続けて適用すれば良いのでnom::sequence::pairを使います。

またnom::combinator::mapを使うとパーサーの結果を加工して返す事ができます。

これらを使ってnumberを実装してみましょう。

fn number(input: &str) -> IResult<&str, Expr> {
    let (input, _) = space0(input)?;
    let (input, n) = map(
        alt((
            // Single digit
            recognize(digit),
            // Multiple digits starting with nonzero
            recognize(pair(nonzero, many1(digit))),
        )),
        |s: &str| Expr::Number(s.parse().unwrap()),
    )(input)?;
    let (input, _) = space0(input)?;
    Ok((input, n))
}

mapとrecognizeとpairというコンビネーターが実装の都合で使われていて少しゴテゴテしていますが、概ねBNF記法の定義をそのままコードに落とし込めましたね。

残りの部分は相互に再帰しあう関係になるので先に実装を見てしまいましょう。

fn paren_left(input: &str) -> IResult<&str, char> {
    let (input, _) = space0(input)?;
    let (input, p) = char('(')(input)?;
    let (input, _) = space0(input)?;
    Ok((input, p))
}

fn paren_right(input: &str) -> IResult<&str, char> {
    let (input, _) = space0(input)?;
    let (input, p) = char(')')(input)?;
    let (input, _) = space0(input)?;
    Ok((input, p))
}

fn paren_expr(input: &str) -> IResult<&str, Expr> {
    delimited(paren_left, expression, paren_right)(input)
}

fn term(input: &str) -> IResult<&str, Expr> {
    alt((number, paren_expr))(input)
}

fn operator(input: &str) -> IResult<&str, char> {
    let (input, _) = space0(input)?;
    let (input, op) = one_of("+-")(input)?;
    let (input, _) = space0(input)?;
    Ok((input, op))
}

fn expression(input: &str) -> IResult<&str, Expr> {
    let (input, first) = term(input)?;
    let (input, rest) = many0(tuple((operator, term)))(input)?;

    Ok((
        input,
        rest.into_iter().fold(first, |acc, (op, term)| {
            Expr::BinOp(Box::new(acc), op, Box::new(term))
        }),
    ))
}

paren_left、paren_right、term、operatorはここまでに説明したのと同じ方法で実装されています。

paren_exprはnom::sequence::delimitedというnomが提供するコンビネーター関数を使っています。
delimitedは3つのパーサーを引数に取り、第2引数のパーサーの結果だけを返すというパーサーです。
括弧で囲まれた文字列のような何かで括られた間の部分だけ欲しい時に便利です。

そして最後のexpressionもパース処理の部分はBNF記法の定義をそのままコードに落とし込んでいます。
nom::multi::many0とnom::sequence::tupleを使っているのがポイントです。
many0は引数で与えられたパーサーの0回以上の繰り返しを表すパーサーで、tupleは複数のパーサーを引数に取ってそれらのパーサーの結果をまとめてタプルで返すパーサーです。
更にexpressionは最終的なデータ構造を作る処理も行います。
今回は1 + 2 + 3の様な式を(1 + 2) + 3と見なすので、前から順番にExpr::BinOpで結合させていく処理を行っています。

最後にこの作ったパーサーを実行する処理を書きましょう。
main関数を次の様に書きます。

fn main() {
    let input = "1 + 2 + 3";
    let result = expression(input);
    println!("{:#?}", result);
}

これを cargo run して実行すると次の結果が出力されます。

Ok(
    (
        "",
        BinOp(
            BinOp(
                Number(
                    1,
                ),
                '+',
                Number(
                    2,
                ),
            ),
            '-',
            Number(
                3,
            ),
        ),
    ),
)

なんかそれっぽい出力が出てますね！

コード全体は https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=63a406e57f3a583c0be4147d10b6fddb にあります。
手軽に動かしてみたい方はこちらを参照してみて下さい。

おわりに

今回はパーサーコンビネーターによるパーサーの作り方を見ていきました。
小さいパーサーをコンビネーターと呼ばれる関数で組み合わせて大きなパーサーを作っていく体験はとても楽しいと思います。

今回はかなりシンプルな数式を対象としましたが、パーサーコンビネーターはもっと複雑な文法にも対応できます。
もし正規表現では無理な文法を扱う際はパーサーコンビネーターを使ってみるのも良いかもしれません。

また、この記事は正規表現エンジンを作って学ぶ正規表現のパーサー部分についての補足記事です。
こちらも合わせてご覧になるとより実戦的な理解ができるかもしれません。

また、明日12月04日(水)は、エンジニアのZasuさんによるCloudFormationで構築されたインフラを引き継いで得た学びです。

私たちWanoグループでは人材募集をしています。興味のある方は、下記のリンクからぜひ募集中の求人をご確認ください！
JOBS | Wano Group