nomで四則演算の構文解析をする

nomについて

nomはRust製のパーサーコンビネーターを実装するためのフレームワークです。
基本的なparserおよび、組み合わせるための関数が多く定義されているため、気軽にパーサーコンビネーターを実装することができます。

基本的なparserから理解する

とりあえず初めてnomを触るので、四則演算を組み立てるために必要になるparserを順番に触って理解します。
基本的には公式からリンクされているドキュメントを順番にたどりますが、必要なところだけを抜粋します。

IResult

nomで実装されるparserは基本的にIResultを返すような関数になっていて、これは以下のような形になります。
今回は帰ってきたタプルに残りとマッチした部分が帰ってくることだけを把握しておけば問題ないです。

// fn parse_fn(input: &str) -> IResult;
// let (マッチした部分を除いた残りの部分, マッチした部分)
let (input, output) = parse_fn(input)?;

nom::bytes::complete::tag

一番シンプルなparserを返す関数です、指定された文字列に一致する部分を先頭から切り取ります。

use nom::{
    IResult,
    bytes::complete::tag
};

fn parse_abc(input: &str): IResult<&str, &str> -> {
    tag("abc")(input)
}

fn main() {
    let (input, output) = parse_abc("abcdef").unwrap();
    assert_eq!(output, "abc");
    assert_eq!(input, "def");
}

nom::character::complete::i32

数値をparseします nom::character::complete 以下に定義されています。
この後の四則演算のparseで、厳密にやるのであれば一旦数値文字列としてparseしてからどの型に当てはまるか(u8, i32, f64等)別途検査する方が望ましいですが、今回は簡略化してi32である前提とします。

use nom::{
    IResult,
    character::complete
};

fn parse_int(input: &str) -> IResult<&str, i32> {
    let (input, int) = complete::i32(input.trim_start())?;

    Ok((input, int))
}

fn main() {
    let (_, result) = parse_int("123").unwrap();
    assert_eq!(result, 123);
}

今回は四則演算が目的なので使用しませんが、 0文字以上の英字文字列にマッチする alpha0、1文字以上の空白文字にマッチする multispace1 などの基本的なparserが多く定義されています。

nom::branch::alt

引数として与えられたいずれかのparserにマッチする結果を返します。正規表現でいうところの foo|bar に対応します。

use nom::{
    IResult,
    bytes::complete::tag,
    branch::alt,
};

fn parse_foo_or_bar(input: &str) -> IResult<&str, &str> {
    alt((tag("foo"), tag("bar")))(input)
}

fn main() {    
    let (_, result) = parse_foo_or_bar("foo").unwrap();
    assert_eq!(result, "foo");
    
    let (_, result) = parse_foo_or_bar("bar").unwrap();
    assert_eq!(result, "bar");
}

ここまでのnomの使い方を把握すれば四則演算のparserを実装するための準備は万端です。

四則演算の構文を定義する

今回実装する四則演算は以下に示すbnfで定義される構文を持ちます。

※ マイナスの実装は省略しています
※ この構文には左再帰性の問題が存在しますが、今回の実装では問題なく動くため無視します

<expr>   ::= <term> | <term> "+" <expr> | <term> "-" <expr>
<term>   ::= <fact> | <fact> "*" <term> | <fact> "/" <term>
<fact>   ::= <number> | "(" <expr> ")"
<number> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

今回numberは簡略化のためにi32として扱います。
まず、構文に対応する構造体を定義します。

#[derive(Debug, PartialEq)]
enum Expr {
    Term(Term),
    Add(Term, Box<Expr>),
    Sub(Term, Box<Expr>),
}

#[derive(Debug, PartialEq)]
enum Term {
    Factor(Factor),
    Mul(Factor, Box<Term>),
    Div(Factor, Box<Term>),
}

#[derive(Debug, PartialEq)]
enum Factor {
    Val(i32),
    BracketedExpr(Box<Expr>),
}

この段階で、この構文を評価して計算するための関数も定義してしまいます。
実装自体はとても単純で、値に対応する計算に変換して、実際に計算を行うだけです。

fn eval_expr(expr: &Expr) -> i32 {
    match expr {
        Expr::Term(term) => eval_term(term),
        Expr::Add(term, expr) => eval_term(term) + eval_expr(expr),
        Expr::Sub(term, expr) => eval_term(term) - eval_expr(expr),
    }
}

fn eval_term(term: &Term) -> i32 {
    match term {
        Term::Factor(factor) => eval_factor(factor),
        Term::Mul(factor, term) => eval_factor(factor) * eval_term(term),
        Term::Div(factor, term) => eval_factor(factor) / eval_term(term),
    }
}

fn eval_factor(factor: &Factor) -> i32 {
    match factor {
        Factor::Val(val) => *val,
        Factor::BracketedExpr(expr) => eval_expr(expr),
    }
}

ここまでの実装が実際に動作するか確認します。

fn main() {
    let expr = Expr::Add(
        Term::Factor(Factor::Val(1)), 
        Box::new(Expr::Term(Term::Factor(Factor::Val(2))))
    );
    assert_eq!(eval_expr(&expr), 3);

    let expr = Expr::Term(Term::Mul(
        Factor::Val(2), 
        Box::new(Term::Factor(Factor::Val(3)))
    ));
    assert_eq!(eval_expr(&expr), 6);
}

parserを定義する

さて、四則演算に対応する構文木と評価する関数の定義はできたので、次は文字列を構文木に変換するための関数を定義します。

下準備

まず、一旦それぞれに対応するからの関数を宣言しておきます。(お互いの呼び出しがあるので、一旦宣言があった方が書きやすいので)

fn parse_expr(input: &str) -> IResult<&str, Expr> {
    unimplemented!()
}

fn parse_term(input: &str) -> IResult<&str, Term> {
    unimplemented!()
}

fn parse_factor(input: &str) -> IResult<&str, Factor> {
    unimplemented!()
}

次に、演算に対応するparseを定義したいのですが、四則演算は全てに共通して

{式} {演算子: +, -, *, /} {式}

という形をしています。
この形を共通化しておくと後々の実装が楽になるので、抽象化したparserを生成する関数を定義します。
この関数は、左側の式のparser、演算子を表す文字列、右側の式のparserを受け取り、上に示した形の式のparserを返します。

type Parser<T> = fn(&str) -> IResult<&str, T>;
fn parse_op<'a, L: 'a, R: 'a>(
    left_parser: Parser<L>,
    op_name: &'a str,
    right_parser: Parser<R>,
) -> impl for<'b> Fn(&'b str) -> IResult<&'b str, (L, R)> + 'a {
    move |input| {
        let (input, left) = left_parser(input.trim_start())?;
        let (input, _) = tag(op_name)(input.trim_start())?;
        let (input, right) = right_parser(input.trim_start())?;

        Ok((input, (left, right)))
    }
}

enum Exprのためのparserを定義する

enum Expr には以下3種類の構文があるので、それぞれに対応するparserの関数を定義します。

enum Expr {
    Term(Term),
    Add(Term, Box<Expr>),
    Sub(Term, Box<Expr>),
}

Add, Plusには上で定義したparse_opを利用します。

fn parse_add(input: &str) -> IResult<&str, Expr> {
    let (input, (left, right)) = parse_op(parse_term, "+", parse_expr)(input)?;

    Ok((input, Expr::Add(left, Box::new(right))))
}

fn parse_sub(input: &str) -> IResult<&str, Expr> {
    let (input, (left, right)) = parse_op(parse_term, "-", parse_expr)(input)?;

    Ok((input, Expr::Sub(left, Box::new(right))))
}

fn parse_expr_term(input: &str) -> IResult<&str, Expr> {
    let (input, left) = parse_term(input.trim_start())?;

    Ok((input, Expr::Term(left)))
}

bnfの定義によると、3つのいずれかにマッチすれば良いので、altを使い、まとめた関数を定義します

fn parse_expr(input: &str) -> IResult<&str, Expr> {
    alt((parse_add, parse_sub, parse_expr_term))(input)
}

enum Termのためのparserを定義する

enum Term には以下3種類の構文があるので、それぞれに対応するparserの関数を定義します。

enum Term {
    Factor(Factor),
    Mul(Factor, Box<Term>),
    Div(Factor, Box<Term>),
}

実装はexpr側の定義とほぼ変わらないので説明は省略します。

fn parse_mul(input: &str) -> IResult<&str, Term> {
    let (input, (left, right)) = parse_op(parse_factor, "*", parse_term)(input)?;

    Ok((input, Term::Mul(left, Box::new(right))))
}

fn parse_div(input: &str) -> IResult<&str, Term> {
    let (input, (left, right)) = parse_op(parse_factor, "/", parse_term)(input)?;

    Ok((input, Term::Div(left, Box::new(right))))
}

fn parse_term_factor(input: &str) -> IResult<&str, Term> {
    let (input, left) = parse_factor(input.trim_start())?;

    Ok((input, Term::Factor(left)))
}

fn parse_term(input: &str) -> nom::IResult<&str, Term> {
    alt((parse_mul, parse_div, parse_term_factor))(input)
}

enum Factorのためのparserを定義する

enum Factor の構文は以下二つです

enum Factor {
    Val(i32),
    BracketedExpr(Box<Expr>),
}

Valは上で説明した nom::character::complete::i32 を使って数値に変換、BracketedExprは nom::bytes::complete::tag を使って、両端の () を取り除いてparseをします。

fn parse_bracketed_expr(input: &str) -> nom::IResult<&str, Factor> {
    let (input, _) = tag("(")(input.trim_start())?;
    let (input, expr) = parse_expr(input.trim_start())?;
    let (input, _) = tag(")")(input.trim_start())?;

    Ok((input, Factor::BracketedExpr(Box::new(expr))))
}

fn parse_val(input: &str) -> IResult<&str, Factor> {
    let (input, val) = complete::i32(input.trim_start())?;

    Ok((input, Factor::Val(val)))
}

fn parse_factor(input: &str) -> nom::IResult<&str, Factor> {
    alt((parse_bracketed_expr, parse_val))(input)
}

最後にここまでの実装の動作を確認します

fn main() {
    let (_, expr) = parse_expr("(3 + 2) * 4").unwrap();
    assert_eq!(expr, Expr::Term(
        Term::Mul(
            Factor::BracketedExpr(Box::new(Expr::Add(
                Term::Factor(Factor::Val(3)), 
                Box::new(Expr::Term(Term::Factor(Factor::Val(2))))))
            ),
            Box::new(Term::Factor(Factor::Val(4)))))
    );

    let (_, expr) = parse_expr("((1 + 1) * (7 - 2)) / 5").unwrap();
    let result = eval_expr(&expr);
    assert_eq!(result, 2);
}

無事、四則演算の実装ができました。

ここまでの実装は gist にまとめてあげます。

まとめ

今回は、nomを使って、四則演算のparserの実装をしました。
nom自体は非常にシンプルなparserながらも、組み合わせることにより、複雑なparserも簡単に実装できることがわかると思います。
四則演算のparserではnomで定義されている関数のほんの一部しか使いませんでしたが、この先、さらに複雑な構文の解析に挑戦することによって、さらにこのライブラリを使いこなせるきっかけにできるかもしれません。
私は、Rustも構文解析もそこまで知識があるわけではないですが、それでもサクッと実装することができたので、皆さんもぜひ挑戦してみてください。