こんにちは。 Rust初心者中の初心者です。今回はnomというライブラリを使ってRustで簡単な計算機を作ってみたので、そのことについて書いていきたいと思います。

nomはRust製のパーサコンビネータです。 nomを利用することで、関数の組み合わせで簡単に~~字句解析器~~構文解析器を作り上げることが可能になります。 nomの詳しいチュートリアルは次のページを参照することをおすすめします。

本記事ではnomを使って簡単な計算機を作っていきたいと思います。

計算式をEBNFで定義する

まずは四則演算の計算式をEBNF（拡張バッカス・ナウア記法）で定義することから始めましょう。

計算式は次のようなEBNFで定義されます*1。

<addsub> ::= <muldiv> (('+' | '-') <muldiv>)*
<muldiv> ::= <fact> (('*' | '/') <fact>)*
<fact> ::= <num> | '(' <addsub> ')'

それぞれ、addsubが足し算引き算、muldivが掛け算割り算、factが数値または括弧でくくられた計算式を表しています。

次に、それぞれを関数化していきます。

EBNFを関数化する

数字列をパースする

数字列をパースする関数です。 map_resでパース結果をf64に変換します。

fn num(s: &str) -> IResult<&str, f64> {
    map_res(
            digit1,
        |int: &str| -> Result<f64, ParseFloatError> {
            int.parse::<f64>()
        }
    )(s)
}

f64に変換しているのは、計算結果で小数に対応するためです。

返り値はIResult<&str, f64>となっており、これはパーサで解析できなかった余りの&strと解析結果のf64から成ります。

<fact>を関数化する

EBNFでの<fact>を関数化していきます。

fn fact(s: &str) -> IResult<&str, f64> {
    alt((
        num,
        delimited(
            char('('),
            delimited(multispace0, addsub, multispace0),
            char(')'),
        ),
    ))(s)
}

altはいずれかにマッチするものを指定でき、delimitedは囲われた部分を取り出すのに使えます。

この場合だと、数字列にマッチする場合或いは括弧で囲まれた計算式にマッチする場合、となります。

<muldiv>を関数化する

ここから少し複雑になります。

fn muldiv(s: &str) -> IResult<&str, f64> {
    map_res(
        permutation((
            fact,
            many0(
                map_res(
                    permutation((
                        multispace0,
                        alt((
                            char('*'),
                            char('/'),
                        )),
                        multispace0,
                        fact,
                    )),
                    |(_, opr, _, rval)| -> Result<f64, &str> {
                        if opr == '*' {
                            Ok(rval)
                        } else {
                            Ok(1.0 / rval)
                        }
                    }
                )
            ),
        )),
        |(lval, rvec)| -> Result<f64, &str> {
            Ok(lval * rvec.iter().fold(1.0, |acc, x| { acc * x }))
        }
    )(s)
}

permutationはパーサの逐次実行を意味します。上の例の場合、factに続いてmany0以下が実行されます。 many0は0回以上の繰り返しで、EBNFだと(('*' | '/') <fact>)*の部分にあたります。

内側のmap_resはオペランドによってVecに格納する値を変更しています。掛け算であればそのまま、割り算であれば1/値を追加することで、全ての結果を掛け算にすることができます。

外側のmap_resは左側の値（<fact>）に右側の値（(('*' | '/') <fact>)*）の積を掛けて答えを出しています。これがOk(lval * rvec.iter().fold(1.0, |acc, x| { acc * x }))のところです。

<addsub>を関数化する

<addsub>も<muldiv>と同様に関数化できます。

fn addsub(s: &str) -> IResult<&str, f64> {
    map_res(
        permutation((
            muldiv,
            many0(
                map_res(
                    permutation((
                        multispace0,
                        alt((
                            char('+'),
                            char('-'),
                        )),
                        multispace0,
                        muldiv,
                    )),
                    |(_, opr, _, rval)| -> Result<f64, &str> {
                        if opr == '+' {
                            Ok(rval)
                        } else {
                            Ok(-1.0 * rval)
                        }
                    }
                )
            ),
        )),
        |(lval, rvec)| -> Result<f64, &str> {
            Ok(lval + rvec.iter().fold(0.0, |acc, x| { acc + x }))
        }
    )(s)
}

やってることは<muldiv>の場合とほとんど変わりません。変わっているのはオペランドの場合分けと最終的な計算部分です。

外側のmap_resは(('+' | '-') <muldiv>)*を処理していって最終的に得られたVecを足して結果を返します。

実行結果

上記プログラムを実行してみます。

fn main() {
    let parser = all_consuming(addsub);
    assert_eq!(parser("1 + 2"), Ok(("", 3.)));
    assert_eq!(parser("1 * 2"), Ok(("", 2.)));
}

問題なく実行できるかと思います。

ソースコード

ソースコード全体は以下のようになりました。

calculator written in Rust with parser combinator…

このプログラムを実行すると、標準入力に入力された計算式を計算し続けるプログラムが走ります。計算機の完成です。

所感

今回はRustのパーサコンビネータnomを使って簡単な計算機を実装しました。

nomは関数の組み合わせで~~字句解析~~構文解析を行ってくれるため、非常にわかりやすく~~字句解析器~~構文解析器を組み立てることができました。機会があれば他の用途でもnomを使ってみたいと思います。

*1:参考: http://home.a00.itscom.net/hatada/lp2012/chap02/formal-language.html

正論なんて諭んないで

cordx56のブログです

Rustでnomを使って計算機を作ってみる