Rustのパーサコンビネータnomを使ってみよう

はじめに

使い方を学ぶのに、プロジェクトトップページの説明 と "Introduction to nom: a parsing framework written in Rust" という英語記事が参考になりました。

ここでは上記英語記事に倣って Hello, world! から始めつつ、簡単な計算機の例を解説します。

執筆時点では Rust は 1.13 で、nom は 1.2.4 です。

nom では楽に記述できるようにするためにマクロが多用されており、ソースコードを読むことでマクロの勉強になります。Rust のマクロの記述方法については「Rustのマクロを覚える」という記事を書きましたので参考にしてください。

特徴

lex & yacc (flex & bison) などと違い、書式ファイルを別に用意することなく、Rust のソースコードの中にルールを記述してパーサ関数を生成します。ルールを記述するためのマクロが多数用意されています。

データをバイト配列として扱い、パース結果はできるだけコピーを使わずにバイト配列のスライスで返します。そのため高速に動作します。データをバイト配列として扱うので、バイナリデータのパースも行うことができます。

Hello, World!

とりあえず動かしてみる

プロジェクトを作ります。名前はお好きに。

$ cargo new nom_hello --bin

とりあえず nom のプロジェクトページ に書いてある通りに Cargo.toml に依存関係を書きます。執筆時点では以下でした。

Cargo.toml

# （略）

[dependencies]
nom = "^1.2.4"

ソースコードを以下のように書きます。

src/main.rs

#[macro_use]
extern crate nom;

use nom::{IResult, space, alpha};

named!(name_parser<&str>,
    chain!(
        tag!("Hello,") ~
        space? ~
        name: map_res!(
            alpha,
            std::str::from_utf8
        ) ~
        tag!("!") ,

        || name
    )
);

fn main() {
    match name_parser("Hello, world!".as_bytes()) {
        IResult::Done(_, name) => println!("name = {}", name),
        IResult::Error(error) => println!("Error: {:?}", error),
        IResult::Incomplete(needed) => println!("Incomplete: {:?}", needed)
    }
}

実行してみましょう。"name = world" と表示されるはずです。

$ cargo run
    Finished debug [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/nom_hello`
name = world

ビルドに失敗したり期待した通りに表示されない場合は、何か書き間違えているか、Rust か nom の仕様が変わったのかもしれません。

ちなみに as_bytes() で文字列をバイト配列のスライスに変換していますが、以下のように書くこともできます。ただし ASCII 文字しか含めることができません。

    match name_parser(&b"Hello, world!"[..]) {

パーサの書き方

パーサを定義している部分に説明コメントを入れてみました。

// name_parser という名前のパース関数を作る。結果は &str 型で受け取る。
named!(name_parser<&str>,
    // ルールを ~ で繋げる。
    chain!(
        // tag! は固定文字列を表す。
        tag!("Hello,") ~
        // space は空白だけでできている文字列を表す。
        // ?はオプションであることを表す。つまり空白はなくてもいい。
        space? ~
        // map_rest! は可変文字列を表す。結果を name で受け取る。
        name: map_res!(
            alpha,  // 文字列はアルファベットでできている。
            std::str::from_utf8  // 結果をこの関数に渡す。つまりバイト列を文字列化。
        ) ~
        tag!("!") ,  // , はルールチェインの終端を表す（というかchanel!への引数の区切りだよね）。

        // chain! が返す結果を決めるクロージャ。name を返す。
        || name
    )
);

要するに

• "Hello," で始まって
• その後に空白文字列があるかも
• その後にアルファベットでできた文字列があって（それを name という変数に入れる）
• 最後は "!" で終わる

という文字列をパースして name を返します。

結果の受け取り方

さて name_parser は結果を &str 型としたわけですが、パースに失敗する可能性もあるわけなので、実際に返る型は IResult 型です。この enum には下記のように Done, Error, Incomplete の３つのパターンがあります。

match name_parser("Hello, world!".as_bytes()) {
    IResult::Done(_, name) => println!("name = {}", name),
    IResult::Error(error) => println!("Error: {:?}", error),
    IResult::Incomplete(needed) => println!("Incomplete: {:?}", needed)
}

IResult::Done

うまくパースできると Done が返ります。これは２つのパラメータを持ち、１つ目はパース後に残ったもの、２つ目がパース結果です。パースした結果、後ろに余分なものがあると１つ目のパラメータに渡されます。

以下のテストを追加してみましょう。nom は文字ではなくバイトを扱うことに注意してください。

#[test]
fn test_name_parer() {
    let empty = &b""[..];    // ""をバイト配列として扱い、全体を配列のスライスに
    assert_eq!(name_parser("Hello, Rust!".as_bytes()), IResult::Done(empty, "Rust"));
    let remain = &b" How are you."[..];
    assert_eq!(name_parser("Hello, nom! How are you.".as_bytes()), IResult::Done(remain, "nom"));
}

テストを実行します。　

$ cargo test
（略）
running 1 test
test test_name_parer ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured

通過しましたか？ 試しに以下のように remain を empty に変更して失敗させてみましょう。

    assert_eq!(name_parser("Hello, nom! How are you.".as_bytes()), IResult::Done(empty, "nom"));

以下のようにテストを実行するとアサーションに失敗しますが、実際の値が [32, 72 ... ] というように数値の配列として表示されます。

$ cargo test
（略）
        thread 'test_name_parer' panicked at 'assertion failed: `(left == right)` (left: `Done([32, 72, 111, 119, 32, 97, 114, 101, 32, 121, 111, 117, 46], "nom")`, right: `Done([], "nom")`)', src/main.rs:26

これは文字列でも文字の配列 [char] でもなく、[u8] として扱っているからですね。高速化のためにバイト列として扱っているわけですが、エラーメッセージは分かりにくくなります。プログラム側で文字列に変換するなどの工夫が必要です。

IResult::Error

Hello を Hey に変更して、わざと失敗させてみましょう。

    match name_parser("Hey, world!".as_bytes()) {

cargo run すると、以下のように表示されました。

Error: Position(Tag, [72, 101, 121, 44, 32, 119, 111, 114, 108, 100, 33])

IResult::Error はパラメータにエラーを渡してきますが、これも enum になっていて、以下のように定義されています。

pub enum Err<P,E=u32>{
  // エラーコード
  Code(ErrorKind<E>),
  // エラーコードと、解析チェインの次のエラー
  Node(ErrorKind<E>, Box<Err<P,E>>),
  // エラーコードと関係する位置
  Position(ErrorKind<E>, P),
  // エラーコードと関係する位置と、解析チェインの次のエラー
  NodePosition(ErrorKind<E>, P, Box<Err<P,E>>)
}

さっきのエラーは Position で、エラー種別とエラーの発生した位置を表しています。

エラー種別 (ErrorKind) も enum です。詳細は nom の util.rs のコード を確認してください。description() メソッドを使うと、文字列に変換することができます。

もうちょっと分かりやすくなるようにエラー表示を改良してみます。

    IResult::Error(error) => match error {
        nom::Err::Position(kind, position) =>
            println!("Error: kind={}, position={}",
                     kind.description(),
                     std::str::from_utf8(position).unwrap()),
        _ => println!("Error: {:?}", error),
    },

これで以下のように表示されました。

Error: kind=Tag, position=Hey, world!

Hello がどこにもないのでエラー位置は文全体ってことみたいですね。今度は末尾の ! を . に変更してみます。

    match name_parser("Hello, world.".as_bytes()) {

以下のように表示されました。

Error: kind=Tag, position=.

今度は alpha を指定している部分にアルファベット以外を使ってみます。

    match name_parser("Hello, 1234!".as_bytes()) {

以下のように表示されました。

Error: kind=Alphabetic, position=1234!

IResult::Incomplete

マッチさせるのに入力が足らない場合に発生します。最後の ! を取り除いてみます。

    match name_parser("Hello, world".as_bytes()) {

以下のように表示されました。

Incomplete: Size(13)

Incomplete に渡されるパラメータは Needed 型で、以下のように定義されています。

pub enum Needed {
  /// needs more data, but we do not know how much
  Unknown,
  /// contains the required data size
  Size(usize)
}

１２文字渡したけど、最後に ! がないので１３文字必要だと言われてるみたいですね。

マルチバイト文字も扱えるようにしてみる

日本人なんだから名前は漢字やひらがなです。パーサの alpha を指定していた部分を is_not!("!") に置き換えてみます。is_not! は指定した文字列の中にある文字を含まない文字列にマッチします。

named!(name_parser<&str>,
    chain!(
        tag!("Hello,") ~
        space? ~
        name: map_res!(is_not!("!"), std::str::from_utf8) ~
        tag!("!") ,
        
        || name
    )
);

#[test]
fn name_parser_test() {
    let empty = &b""[..];
    assert_eq!(name_parser("Hello, ラスト!".as_bytes()), IResult::Done(empty, "ラスト"));
}

これで漢字や平仮名でもパースできるようになりました。

日本語で

日本語の挨拶をパースしてみましょう。take_until! は指定したバイト列に遭遇するまでを取得します。

named!(japanese_name_parser<&str>,
    chain!(
        name: map_res!(
            take_until!("さん、"),
            std::str::from_utf8
        ) ~
        tag!("さん、こんにちは。"),

        || name
    )
);

デフォルトで用意されている基礎的なパーサ

以下は nom のトップページに基礎的なパーサとして一覧になっているものです。

名前	説明
length_value	（バイナリデータでよくある）最初のバイトが後続のバッファのバイト数を表すデータをパースする
not_line_ending	行の終わり(\r または \n) までのデータを返す
line_ending	行の終わりにマッチする
alpha	入力の先頭から最も長いアルファベットでできた配列を返す
digit	入力の先頭から最も長い数字だけでできた配列を返す
alphanumeric	入力の先頭から最も長いアルファベットと数字でできた配列を返す
space	空白文字だけでできた最も長い配列を返す
multispace	空白文字, \r, \n を含む最も長い配列を返す
be_u8, be_u16, be_u32, be_u64	（バイナリデータの）ビッグエンディアンの符号なし整数をパースする
be_i8, be_i16, be_i32, be_i64	（バイナリデータの）ビッグエンディアンの符号あり整数をパースする
be_f32, be_f64	（バイナリデータの）ビッグエンディアンの浮動小数点数をパースする
eof	入力がなくなった場合のみ成功するパーサ。それ以外ではエラーを返す。

一般的なコンビネータ

以下は nom のトップページに一般的なコンビネータとして一覧になっているものです。

名前	説明
tag!	引数で渡されたバイト配列にマッチする
is_not!	渡されたバイト配列のどのバイトも含まない最大の配列にマッチする
is_a!	渡されたバイト配列のバイトのみを含む最大の配列にマッチする
take_while!	渡されたクロージャを適用して失敗するまでパースする
take!	指定されたバイト数だけ取得する
take_until!	指定されたバイト配列に出会うまでを取得する。指定されたバイト配列は入力に残す。
take_until_and_consume!	指定されたバイト配列に出会うまでを取得する。指定されたバイト配列はスキップする。
take_until_either_and_consume!	指定されたバイト配列のうちの１つに出会うまでを取得する。出会ったバイトはスキップする。
take_until_either!	指定されたバイト配列のうちの１つに出会うまでを取得する。出会ったバイトは残す。
map!	IResult の出力に関数を適用し、その結果で IResult の出力を置き換える
flat_map!	パーサを IResult の出力に適用し、同じ残り入力の新しい IResult を返す
map_opt!	Option を返す関数を IResult の出力に適用し、結果が Some(o) なら Done(input, o) を返し、そうでなければ Error(0) を返す。
map_res!	Result を返す関数を IResult の出力に適用し、結果が OK(o) なら Done(input, o) を返し、そうでなければ Error(0) を返す。

この後の計算機を作るときに使うその他のコンビネータです。これらも一般的によく使われそうなんですが、一般的なものは何を基準に選んだんでしょう？？

名前	説明
delimited!	何かに挟まれたものを返す
alt!	複数のうちのどれかにマッチさせる
preceded!	何かの後に続くものを返す
many0	パーサを０回以上繰り返し適用する

計算機を作ってみる

cargo doc を実行して nom のドキュメントを生成すると、最初のページに数式パーサの例が表示されます。これが何をやっているのか順に調べてみます。

適当な名前でプロジェクトを作成して、main.rs ファイルの先頭に以下を記述しておきます。

#[macro_use]
extern crate nom;

use nom::{IResult,digit};
use nom::IResult::*;
use std::str;
use std::str::FromStr;

括弧で囲まれたものをパース

delimited! マクロを使うと、何かに囲まれた中身を取り出せます。

#[test]
fn delimited_test() {
    named!(parens_any, delimited!(char!('('), is_not!(")"), char!(')')));
    
    assert_eq!(parens_any("(1+2)".as_bytes()), Done(&b""[..], &b"1+2"[..]));
}

これを使って数式を括弧で囲まれたものをパースするパーサを定義します。

named!(parens<i64>, delimited!(char!('('), expr, char!(')')));

expr はまだ定義していませんので、まだコンパイルは通りません。

整数をパース

digit で数字のみの文字列を取り出して、それを from_utf8 で文字列化し、さらにそれを from_str で数値化します。

named!(i64_digit<i64>,
    map_res!(
        map_res!(
            digit,
            str::from_utf8
        ),
        FromStr::from_str
    )
)

#[test]
fn i64_digit_test() {
    assert_eq!(i64_digit("123".as_bytes()), Done(&b""[..], 123i64));
}

from_utf8 は文字列が UTF-8 じゃなかったら失敗しますので、戻り値は Result 型です。同様に from_str も文字列が数値を表していない場合に失敗しますので、戻り値は Result 型です。map_res! マクロは Result 型を返す関数を適用するときに使います。Ok だったら結果を IResult::Done に格納して返し、Err だったらパースに失敗したとみなして IResult::Error を返します（元の Err のエラー内容は失われます）。

似たようなマクロに map_opt! と map! があります。map_opt! は Option を返す関数を適用し、map は失敗がなく値そのものを返す関数を適用するのに利用します。

関数呼び出しが１段増えることを気にしないなら、以下のように２つにバラしてもいいですね。細かくバラした方が関数の汎用性は増します。

named!(numeric_string<&str>, map_res!(digit, str::from_utf8));
named!(i64_digit<i64>, map_res!(numeric_string, FromStr::from_str));

複数のうちのどれか

alt! を使うと、複数条件のうちの１つにマッチすればOKというパーサが作れます。以下の factor 関数は、数値または括弧で囲まれた数式をパースします。

named!(factor<i64>, alt!(i64_digit | parens));

パーサを繰り返し適用する

many0 で指定したパーサを０回以上適用して結果を Vec で返します。０回もあり得るので、マッチするものがなかった場合は空のベクタを返します。後で数式を計算するときに使います。

#[test]
fn multi_test() {
    // 注！！ "> >" の部分を ">>" にするとコンパイルエラー
    named!(multi<&[u8], Vec<&[u8]> >,
        many0!(
            tag!("abcd")
        )
    );

    let res = vec![&b"abcd"[..], &b"abcd"[..]];
    assert_eq!(multi("abcdabcdefgh".as_bytes()), Done(&b"efgh"[..], res));
    assert_eq!(multi("azerty".as_bytes()), Done(&b"azerty"[..], Vec::new()));
}

なお１回以上適用する many1! や m 〜 n 回（n を含む）適用する many_m_n! マクロもあります。

パース結果を利用して処理を行う

tap! を使うとパース結果を使って処理を行うことができます。パース結果はそのまま返します。あとで数式を計算するときに利用します。

#[test]
fn tap_test() {
    named!(ptag, tap!(res: tag!( "abcd" ) => { println!("recognized {}", str::from_utf8(res).unwrap()) } ) );
    
    // パースを行い、普通に結果を返すが、同時に標準出力への表示も行われる。
    let r = ptag(&b"abcdefgh"[..]);
    assert_eq!(r, Done(&b"efgh"[..], &b"abcd"[..]));
}

何かの後に続くものを取得する

delimited! は何かに囲まれたものを取得しましたが、preceded! を使うと何かが頭に付いているものを取得することができます。頭についているものは無視して、その後に続くものを返します。あとで数式を計算するときに使います。

#[test]
fn preceded_test() {
    // abcd の後に efgh が続くものをパースし、後ろの efgh を返す
    named!(preceded_abcd_efgh<&[u8], &[u8]>, preceded!(tag!("abcd"), tag("efgh")) );
    
    assert_eq!(preceded_abcd_efgh(&b"abcdefghijkl"[..]),
               Done(&b"ijkl"[..], &b"efgh"[..]));
}

掛け算・割り算を計算する

演算子の優先順位的にまずは掛け算・割り算を計算します。先ほど紹介した many0!, tap!, preceded! を利用します。

named!(term <i64>,
    chain!(
        // factor は数値または括弧で囲まれた数式
        // 結果の acc は後の * や / の計算結果を適用できるように mut にしておく
        mut acc: factor  ~
        // その後に「* または / と factor」が０回以上続く
        many0!(
            alt!(
                // 掛け算にマッチしたら計算して acc を書き換える
                tap!(mul: preceded!(tag!("*"), factor) => acc = acc * mul) |
                // 割り算にマッチしたら計算して acc を書き換える
                tap!(div: preceded!(tag!("/"), factor) => acc = acc / div)
            )
        ),
        // 結果としてacc を返す
        ||  acc
    )
);

足し算・引き算を計算する

同様に足し算・割り算を計算します。先ほど factor だったところが、term に置き換わります。これにより、先に掛け算・割り算が計算されることになります。

named!(expr <i64>,
    chain!(
        mut acc: term  ~
        many0!(
            alt!(
                tap!(add: preceded!(tag!("+"), term) => acc = acc + add) |
                tap!(sub: preceded!(tag!("-"), term) => acc = acc - sub)
            )
        ),
        || acc
    )
);

動作させてみる

以下を追加して cargo run でも cargo test でも実行してみてください。

#[test]
fn main() {
    assert_eq!(expr(b"1+2"),         IResult::Done(&b""[..], 3));
    assert_eq!(expr(b"12+6-4+3"),    IResult::Done(&b""[..], 17));
    assert_eq!(expr(b"1+2*3+4"),     IResult::Done(&b""[..], 11));

    assert_eq!(expr(b"(2)"),         IResult::Done(&b""[..], 2));
    assert_eq!(expr(b"2*(3+4)"),     IResult::Done(&b""[..], 14));
    assert_eq!(expr(b"2*2/(5-1)+3"), IResult::Done(&b""[..], 4));
}

まとめ

Rust 用のパーサコンビネータ nom を利用してみました。ごくごく簡単なものしか扱っていませんが、取っ掛かりにはなったんじゃないでしょうか。

cargo doc して生成されるドキュメントを見れば、どんなパーサやコンビネータが用意されているか分かります。またソースコードのコメントの利用例や各関数のテストコードを見ると、使い方や動作がよくわかります。

nom プロジェクトの tests に、浮動小数点のパーサなどの簡単なものから JSON や INI のパーサなどのもうちょっと複雑なものまで、実際のパーサのコード例があります。

プロジェクトトップページの "Parsers written with nom" の章 には、nom を使って実装された様々なパーサへのリンクがあります。より複雑で実用的なものを作る際には参考になりそうです。