Rust nom

GitHub - rust-bakery/nom: Rust parser combinator framework

nomはRustで書かれたパーサ・コンビネータ・ライブラリです。その目的は、速度やメモリ消費量を犠牲にすることなく、安全なパーサーを構築するためのツールを提供することです。そのために、Rustの強力な型付けとメモリ安全性を広範に使用して、高速で正しいパーサーを生成し、関数、マクロ、traitを提供して、エラーが発生しやすい配管の大部分を抽象化します。

shiratori

Introduction - The Nom Guide (Nominomicon)
Nomはパーサー・コンビネーター・ライブラリである。 つまり、定義するためのツールを提供する：
「パーサー」（入力を受け取り、出力を返す関数）と
"コンビネーター"（パーサーを受け取り、それらを組み合わせる関数！）。

shiratori

nom - Rust - #nom-eating-data-byte-by-byte

nomは、安全な構文解析、ストリーミング・パターン、可能な限りゼロコピーに焦点を当てたパーサー・コンビネーター・ライブラリである。

nom - Rust - #parser-combinators

パーサー・コンビネーターは、lexやyaccのようなソフトウェアとはまったく異なるパーサーへのアプローチだ。文法を別の構文で書いて対応するコードを生成する代わりに、「5バイトを取る」とか「単語'HTTP'を認識する」といった特定の目的を持った非常に小さな関数を使い、「'HTTP'を認識し、次にスペース、次にバージョン」といった意味のあるパターンに組み立てる。出来上がったコードは小さく、他のパーサー・アプローチで書かれた文法のように見える。

これにはいくつかの利点がある：

パーサーは小さくて書きやすい。
パーサー・コンポーネントは再利用しやすい（もし十分汎用的であれば、nomに追加してください！）。
パーサーコンポーネントは個別にテストしやすい（ユニットテストとプロパティベースのテスト）
パーサーの組み合わせのコードは、あなたが書いたであろう文法に近い。
その時点で必要なデータに特化した部分的なパーサーを構築し、残りを無視することができる。

以下はそのようなパーサーの一例で、括弧の間のテキストを認識する：

use nom::{
  IResult,
  sequence::delimited,
  // see the "streaming/complete" paragraph lower for an explanation of these submodules
  character::complete::char,
  bytes::complete::is_not
};

fn parens(input: &str) -> IResult<&str, &str> {
  delimited(char('('), is_not(")"), char(')'))(input)
}

parensという名前の関数が定義されており、この関数は、（）、（）を含まない最長のバイト配列、その次に（）という文字列を認識し、その中間のバイト配列を返す。

もうひとつのパーサーを紹介しよう。今回はnomのコンビネーターを使わずに書いた：

use nom::{IResult, Err, Needed};

fn take4(i: &[u8]) -> IResult<&[u8], &[u8]>{
  if i.len() < 4 {
    Err(Err::Incomplete(Needed::new(4)))
  } else {
    Ok((&i[4..], &i[0..4]))
  }
}

この関数はバイト配列を入力として受け取り、4バイトを消費しようとする。 Rustの安全機能にもかかわらず、このようにすべてのパーサーを手作業で書くのは危険だ。まだ多くの間違いを犯す可能性がある。そのため、nomはパーサー開発に役立つ関数のリストを提供している。

関数を使う場合は、次のように書く：

use nom::{IResult, bytes::streaming::take};
fn take4(input: &str) -> IResult<&str, &str> {
  take(4u8)(input)
}

nomにおけるパーサーとは、入力タイプI、出力タイプO、オプションのエラータイプEに対して、以下のシグネチャーを持つ関数のことである：

fn parser(input: I) -> IResult<I, O, E>;

あるいは、カスタム・エラー・タイプを指定したくない場合はこのようにする（デフォルトでは（I, ErrorKind）となる）：

fn parser(input: I) -> IResult<I, O>;

IResultはResult型のエイリアスである：

use nom::{Needed, error::Error};

type IResult<I, O, E = Error<I>> = Result<(I, O), Err<E>>;

enum Err<E> {
  Incomplete(Needed),
  Error(E),
  Failure(E),
}

以下の値を持つことができる：

正しい結果Ok((I,O))は、最初の要素が入力の残り（まだ解析されていない）、2番目の要素が出力値である；
エラーErr(Err::Error(c))。cは入力位置から構築できるエラーで、パーサー固有のエラー。
さらに入力が必要であることを示すエラー Err(Err::Incomplete(Needed)). Neededは、どれだけのデータが必要かを示す
エラー Err(Err::Failure(c))。これはErrorの場合と同じように動作しますが、回復不可能なエラーを示します：後戻りして別のパーサーをテストすることはできません。

shiratori

#list-of-parsers-and-combinators
注：このリストは、docs.rsのドキュメントを読み通すよりも、ノムパーサーを見つけやすくするためのものです。 関数コンバイネーターはモジュールで整理されているので、少し見つけやすくなっています。
この文書にあるリンクは、ほとんどの場合、完全版のパーサーを指している。 ほとんどのパーサーにはストリーミング版もあります。

 Basic elements
これらは、「ここにドットがある」とか「ここにビッグエンディアンの整数がある」といったように、文法の最下層の要素を認識するために使われる。

 Choice combinators

 Sequence combinators

 Applying a parser multiple times

shiratori

Rust: nom によるパーサー実装 - MOXBOX

shiratori

 altパーザーのリストを試し、最初に成功したパーザーの結果を返す。
https://docs.rs/nom/latest/nom/branch/fn.alt.html
パーサーのリストを1つずつ、1つが成功するまでテストする。

引数にパーサーのタプルを取る。 最大21個のパーザーを指定できる。 それ以上必要な場合は、alt(parser_a, alt(parser_b, parser_c))のように他のalt呼び出しの中に入れ子にすることができます。
use nom::branch::alt;
use nom::character::complete::{alpha1, digit1};
use nom::error::ErrorKind;
use nom::IResult;
use nom::{error_position, Err};

fn parser(input: &str) -> IResult<&str, &str> {
    alt((alpha1, digit1))(input)
}
// the first parser, alpha1, recognizes the input
assert_eq!(parser("abc"), Ok(("", "abc")));

// the first parser returns an error, so alt tries the second one
assert_eq!(parser("123456"), Ok(("", "123456")));

assert_eq!(parser("abc123456"), Ok(("123456", "abc")));

assert_eq!(parser("123456abc"), Ok(("abc", "123456")));

assert_eq!(
    parser("?"),
    Err(Err::Error(error_position!("?", ErrorKind::Digit)))
);

assert_eq!(
    parser("?1"),
    Err(Err::Error(error_position!("?1", ErrorKind::Digit)))
);

assert_eq!(
    parser("?a"),
    Err(Err::Error(error_position!("?a", ErrorKind::Digit)))
);

// both parsers failed, and with the default error type, alt will return the last error
assert_eq!(
    parser(" "),
    Err(Err::Error(error_position!(" ", ErrorKind::Digit)))
);
カスタム・エラー・タイプを使えば、altが入力データで最も遠くに行ったパーサーのエラーを返すようにすることができる。

shiratori

 pairhttps://docs.rs/nom/latest/nom/sequence/fn.pair.html
最初のパーサーからオブジェクトを取得し、次に2番目のパーサーから別のオブジェクトを取得する。
Arguments
first 最初に適用するパーサー。
second 適用する2番目のパーサー。

use nom::{
    bytes::complete::tag,
    character::complete::{alphanumeric1, char, multispace0},
    error::ErrorKind,
    sequence::{delimited, pair},
    Err,
};

let mut parser_pair = pair(tag("abc"), tag("efg"));

assert_eq!(parser_pair("abcefg"), Ok(("", ("abc", "efg"))));
assert_eq!(parser_pair("abcefghij"), Ok(("hij", ("abc", "efg"))));
assert_eq!(parser_pair(""), Err(Err::Error(("", ErrorKind::Tag))));
assert_eq!(parser_pair("123"), Err(Err::Error(("123", ErrorKind::Tag))));

shiratori

 delimited括弧に囲まれたものを取得する
３つ引数をとり、第二引数が取得したい文字列、前後の引数が括弧の型を指定する
https://docs.rs/nom/latest/nom/sequence/fn.delimited.html
最初のパーサーからのオブジェクトにマッチしてそれを破棄し、次に2番目のパーサーからオブジェクトを取得し、最後に3番目のパーサーからのオブジェクトにマッチしてそれを破棄する。
Arguments
first 最初に適用され、破棄されるパーサー。
second 2番目に適用するパーサー。
third 3番目のパーサーが適用され、破棄される。

use nom::{
    bytes::complete::tag,
    character::complete::{char, multispace0},
    error::ErrorKind,
    sequence::delimited,
    Err,
};

let mut delimited_parser = delimited(tag("("), tag("abc"), tag(")"));

assert_eq!(delimited_parser("(abc)"), Ok(("", "abc")));

assert_eq!(delimited_parser("(abc)def"), Ok(("def", "abc")));

assert_eq!(delimited_parser(""), Err(Err::Error(("", ErrorKind::Tag))));
assert_eq!(
    delimited_parser("123"),
    Err(Err::Error(("123", ErrorKind::Tag)))
);

shiratori

many0

埋め込みパーサーを繰り返し、結果をVecに集める。 Err::Errorで停止し、蓄積された結果を返す。代わりにエラーを連鎖させるには、cutを参照してください。

戻り値は、残りの文字列と、パーサーにマッチしたものがVectorに格納されたもの

引数

• f The parser to apply.

注: 渡されたパーサーが空の入力 (alpha0 や digit0 など) を受け入れる場合、many0 は無限ループに入るのを防ぐためにエラーを返します。

use nom::multi::many0;
use nom::bytes::complete::tag;

fn parser(s: &str) -> IResult<&str, Vec<&str>> {
  many0(tag("abc"))(s)
}

assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
assert_eq!(parser("abc123"), Ok(("123", vec!["abc"])));
assert_eq!(parser("123123"), Ok(("123123", vec![])));
assert_eq!(parser(""), Ok(("", vec![])));

pub mod parsers {

    use nom::{bytes::complete::tag, multi::many0, sequence::delimited, IResult};

    pub fn tag_parser() {
        fn many0_parser(s: &str) -> IResult<&str, Vec<&str>> {
            many0(tag("abc"))(s)
        }

        assert_eq!(many0_parser("abcabc"), Ok(("", vec!["abc", "abc"])));
        assert_eq!(many0_parser("abc123"), Ok(("123", vec!["abc"])));
        assert_eq!(many0_parser("123123"), Ok(("123123", vec![])));
        assert_eq!(many0_parser(""), Ok(("", vec![])));
        assert_eq!(many0_parser(""), Ok(("", vec![])));
    }

    pub fn expr_parser() {
        fn expr(i: &str) -> IResult<&str, &str> {
            print!("{}", i);
            tag("abc")(i)
        }

        fn many0_parser(s: &str) -> IResult<&str, Vec<&str>> {
            many0(delimited(tag("("), expr, tag(")")))(s)
        }

        assert_eq!(many0_parser("(abc)"), Ok(("", vec!["abc"])));
        assert_eq!(many0_parser(""), Ok(("", vec![])));
    }
}

https://github.com/t-shiratori/rust-nom-learning/blob/main/src/many0.rs

shiratori

 fold_many0https://docs.rs/nom/latest/nom/multi/fn.fold_many0.html
第一引数で繰り返し適用するパーサーを指定、第二引数でリターン用の格納データの初期値を指定、第三引数で現在の処理結果をアキュムレーターに結合して返す処理を書く
埋め込まれたパーサーを繰り返し、結果を収集するためにgを呼び出す。 これはErr::Errorで停止する。 代わりにエラーを連鎖させるには、cutを参照してください。

 引数
f : 適用するパーサ。

init : 初期値を返す関数。

g : f の結果と現在のアキュムレータを結合する関数。
注意：渡されたパーサが空の入力（alpha0 や digit0）を受け付ける場合、無限ループに入るのを防ぐため、many0 はエラーを返します。
use nom::multi::fold_many0;
use nom::bytes::complete::tag;

fn parser(s: &str) -> IResult<&str, Vec<&str>> {
  fold_many0(
    tag("abc"),
    Vec::new,
    |mut acc: Vec<_>, item| {
      acc.push(item);
      acc
    }
  )(s)
}

assert_eq!(parser("abcabc"), Ok(("", vec!["abc", "abc"])));
assert_eq!(parser("abc123"), Ok(("123", vec!["abc"])));
assert_eq!(parser("123123"), Ok(("123123", vec![])));
assert_eq!(parser(""), Ok(("", vec![])));

shiratori

recognize

子パーサが成功した場合、生成された値として消費された入力を返す。

つまりパーサーの処理がうまくいった場合に、引数で渡したインプットをそのまま返す関数。

use nom::combinator::recognize;
use nom::character::complete::{char, alpha1};
use nom::sequence::separated_pair;

let mut parser = recognize(separated_pair(alpha1, char(','), alpha1));

assert_eq!(parser("abcd,efgh"), Ok(("", "abcd,efgh")));
assert_eq!(parser("abcd;"),Err(Err::Error((";", ErrorKind::Char))));

shiratori

alpha1

1つ以上の小文字と大文字のASCIIアルファベットを認識する： a-z, A-Z 完全版：入力データが十分でない場合はエラーを返し、終了トークン（アルファベット以外の文字）が見つからない場合は入力全体を返します。

fn parser(input: &str) -> IResult<&str, &str> {
    alpha1(input)
}

assert_eq!(parser("aB1c"), Ok(("1c", "aB")));
// aBがマッチ結果として、1cが残りの入力値として返却される

assert_eq!(parser("1c"), Err(Err::Error(Error::new("1c", ErrorKind::Alpha))));
assert_eq!(parser(""), Err(Err::Error(Error::new("", ErrorKind::Alpha))));