Rustのパーサコンビネータライブラリnom 5.0を使ってみた

# はじめに
[nom](https://github.com/Geal/nom)はRust製のパーサコンビネータライブラリの一つで、マクロを使ったDSL記法で有名？です。しかし最近リリースされたバージョン5.0でマクロベースから関数ベースへと大きく方針変更しました。ちょうど書きたいパーサがあったので、早速試してみました。

# 題材
今回作ってみたのはSystemVerilogの数値リテラルパーサです。SystemVerilogでは`32'hffff_0000`といった感じでビット幅（ここでは32）と基数（`h`は16進数）を指定します。また`_`で自由に区切ることができ、ビット幅と基数、数値本体の間は空白を許します。他にも細かいことはいろいろありますがここでは省略します。

# 解説

細かいパーサ部品を個別に解説して、最後にソースコード全体を示します。途中のコードは切り貼り・修正しているのでコンパイルが通らないものがあるかもしれません。最終的に動くものとしては最後の全体ソースコードを参照してください。

まずパーサを表す関数は

```rust
pub fn parser(s: &str) -> IResult<&str, OUTPUT> {
}
```

のようになります。ここでは入力型は`&str`に決め打ちですが、バイナリのパーサなら`&[u8]`となります。
出力型は`IResult`で型引数の1つ目が入力型（これはパース後の残りを返すのに使います）、2つ目がパース結果の型です。

例えば16進数の基数部にマッチするパーサは

```rust
pub fn hex_base(s: &str) -> IResult<&str, &str> {
    alt((
        tag("'h"),
        tag("'H"),
    ))(s)
}
```

となります。`tag`が引数に与えたリテラルそのものにマッチし、`alt`が引数に与えたパーサのいずれかにマッチです。なのでこのパーサは`'h`か`'H`にマッチします。

また繰り返しを使った例はこんな感じです。

```rust
pub fn unsigned_number(s: &str) -> IResult<&str, Vec<&str>> {
    many1(alt((tag("_"), digit1)))(s)
}
```

`many1`が1回以上の繰り返しで、結果は`Vec`で返ってきます。この例だと`_`か数字の繰り返しです。
ただこのパーサだと`____`のようなものも受理してしまいます。
これを修正した実際のパーサは以下です。

```rust
pub fn unsigned_number(s: &str) -> IResult<&str, Vec<&str>> {
    let (s, x) = digit1(s)?;
    fold_many0(alt((tag("_"), digit1)), vec![x], |mut acc: Vec<_>, item| {
        acc.push(item);
        acc
    })(s)
}
```

先頭は必ず数字でその後は`_`か数字の繰り返しです。`fold_many0`は`many0`と同様に0回以上の繰り返しですが、クロージャでfoldできます。
ここでのポイントは`let (s, x) = digit1(s)?;`と一時変数に入れているところです。この`s`には`digit1`でパースした残りの`&str`が入ります。`x`はパース結果です。さらに?を使っているので`digit1`のマッチに失敗した場合は即座に`Err`でリターンします。つまり

```rust
    let (s, x) = digit1(s)?;
    let (s, x) = digit1(s)?;
    let (s, x) = digit1(s)?;
```

のようにつなげて書くと、パーサをandでつなげたような効果が得られます。一般的なパーサコンビネータ同様にnomにもつなげる用のコンビネータは用意されていて

```rust
tuple((digit1, digit1, digit1))
```

と書くこともできます。これくらい簡単な例だとこちらの方が簡潔ですが、実際に複雑なものを書いていくとインデントや括弧が深くなってつらいことになりがちです。
そのような場合にこの一時変数を使った書き方は有効ではないかと思います。

独自型を返す例です。

```rust
#[derive(Debug)]
pub struct DecimalNumber<'a> {
    pub size: Option<Vec<&'a str>>,
    pub decimal_base: &'a str,
    pub decimal_number: Vec<&'a str>,
}

pub fn decimal_number(s: &str) -> IResult<&str, DecimalNumber> {
    let (s, (size, _, decimal_base, _, decimal_number)) = tuple((
        opt(size),
        space0,
        decimal_base,
        space0,
        alt((unsigned_number, x_number, z_number)),
    ))(s)?;
    Ok((
        s,
        DecimalNumber {
            size,
            decimal_base,
            decimal_number,
        },
    ))
}
```

今度は`tuple`を使ってビット幅と基数と数値本体が連続したものをパースして、その結果をからstructを作っています。
ビット幅はオプションなので`opt`を使うと`Option`で返ってきます。

# combineと比べて
マクロベースのnomは使ったことがないので、同じく関数ベースのパーサコンビネータ[combine](https://github.com/Marwes/combine)と比べた感想です。

まず出てくる型が圧倒的に少ないです。nomの独自型といえば`IResult`くらいしかありません。他はほぼ普通のRustプログラミングで使う型の組み合わせになっています。
そのためドキュメントやコンパイルエラーがとても見やすくなっていると感じました。combineはライブラリ独自の型が非常に多く、genericに書いて型変数が増えることも相まって、コンパイルエラー時の型合わせが大変でした。

また解説でも書きましたが中間変数を使った記法はかなりいい感じです。combineではネストが深くなりすぎていたものをすっきり書くことができました。またrustfmtで変なフォーマットがされにくいというのもメリットです。変数のシャドウィングはあまり流行りませんが、この例ではとても有効に働いていると思いました。

一方で5.0になったばかりということか公式のドキュメントでもマクロ時代のものが結構残っています。ただコンビネータ自体はマクロ版と関数版で同名になっているのでそれほど混乱はしないと思います。

# ソースコード

SystemVerilogの数値リテラルパーサ（整数のみ）です。浮動小数点数リテラルは型だけ用意して未実装です。

```rust
use nom::branch::*;
use nom::bytes::complete::*;
use nom::character::complete::*;
use nom::combinator::*;
use nom::multi::*;
use nom::sequence::*;
use nom::IResult;

#[derive(Debug)]
pub enum Number<'a> {
    IntegralNumber(IntegralNumber<'a>),
    RealNumber(RealNumber),
}

#[derive(Debug)]
pub enum IntegralNumber<'a> {
    DecimalNumber(DecimalNumber<'a>),
    OctalNumber(OctalNumber<'a>),
    BinaryNumber(BinaryNumber<'a>),
    HexNumber(HexNumber<'a>),
    UnsignedNumber(Vec<&'a str>),
}

#[derive(Debug)]
pub enum RealNumber {
    FixedPointNumber,
    FloatingPointNumber,
}

pub fn number(s: &str) -> IResult<&str, Number> {
    alt((integral_number, real_number))(s)
}

pub fn integral_number(s: &str) -> IResult<&str, Number> {
    let (s, x) = alt((
        octal_number,
        binary_number,
        hex_number,
        decimal_number,
        integral_unsigned_number,
    ))(s)?;
    Ok((s, Number::IntegralNumber(x)))
}

#[derive(Debug)]
pub struct DecimalNumber<'a> {
    pub size: Option<Vec<&'a str>>,
    pub decimal_base: &'a str,
    pub decimal_number: Vec<&'a str>,
}

pub fn decimal_number(s: &str) -> IResult<&str, IntegralNumber> {
    let (s, (size, _, decimal_base, _, decimal_number)) = tuple((
        opt(size),
        space0,
        decimal_base,
        space0,
        alt((unsigned_number, x_number, z_number)),
    ))(s)?;
    Ok((
        s,
        IntegralNumber::DecimalNumber(DecimalNumber {
            size,
            decimal_base,
            decimal_number,
        }),
    ))
}

pub fn integral_unsigned_number(s: &str) -> IResult<&str, IntegralNumber> {
    let (s, x) = unsigned_number(s)?;
    Ok((s, IntegralNumber::UnsignedNumber(x)))
}

#[derive(Debug)]
pub struct BinaryNumber<'a> {
    pub size: Option<Vec<&'a str>>,
    pub binary_base: &'a str,
    pub binary_value: Vec<&'a str>,
}

pub fn binary_number(s: &str) -> IResult<&str, IntegralNumber> {
    let (s, (size, _, binary_base, _, binary_value)) =
        tuple((opt(size), space0, binary_base, space0, binary_value))(s)?;
    Ok((
        s,
        IntegralNumber::BinaryNumber(BinaryNumber {
            size,
            binary_base,
            binary_value,
        }),
    ))
}

#[derive(Debug)]
pub struct OctalNumber<'a> {
    pub size: Option<Vec<&'a str>>,
    pub octal_base: &'a str,
    pub octal_value: Vec<&'a str>,
}

pub fn octal_number(s: &str) -> IResult<&str, IntegralNumber> {
    let (s, (size, _, octal_base, _, octal_value)) =
        tuple((opt(size), space0, octal_base, space0, octal_value))(s)?;
    Ok((
        s,
        IntegralNumber::OctalNumber(OctalNumber {
            size,
            octal_base,
            octal_value,
        }),
    ))
}

#[derive(Debug)]
pub struct HexNumber<'a> {
    pub size: Option<Vec<&'a str>>,
    pub hex_base: &'a str,
    pub hex_value: Vec<&'a str>,
}

pub fn hex_number(s: &str) -> IResult<&str, IntegralNumber> {
    let (s, (size, _, hex_base, _, hex_value)) =
        tuple((opt(size), space0, hex_base, space0, hex_value))(s)?;
    Ok((
        s,
        IntegralNumber::HexNumber(HexNumber {
            size,
            hex_base,
            hex_value,
        }),
    ))
}

pub fn size(s: &str) -> IResult<&str, Vec<&str>> {
    let (s, x) = is_a("123456789")(s)?;
    let (s, x) = fold_many0(alt((tag("_"), digit1)), vec![x], |mut acc: Vec<_>, item| {
        acc.push(item);
        acc
    })(s)?;
    Ok((s, x))
}

pub fn real_number(s: &str) -> IResult<&str, Number> {
    let (s, x) = alt((fixed_point_number, floating_point_number))(s)?;
    Ok((s, Number::RealNumber(x)))
}

pub fn fixed_point_number(s: &str) -> IResult<&str, RealNumber> {
    Ok((s, RealNumber::FixedPointNumber))
}

pub fn floating_point_number(s: &str) -> IResult<&str, RealNumber> {
    Ok((s, RealNumber::FloatingPointNumber))
}

pub fn unsigned_number(s: &str) -> IResult<&str, Vec<&str>> {
    let (s, x) = digit1(s)?;
    fold_many0(alt((tag("_"), digit1)), vec![x], |mut acc: Vec<_>, item| {
        acc.push(item);
        acc
    })(s)
}

pub fn binary_value(s: &str) -> IResult<&str, Vec<&str>> {
    let (s, x) = is_a("01xXzZ?")(s)?;
    fold_many0(
        alt((tag("_"), is_a("01xXzZ?"))),
        vec![x],
        |mut acc: Vec<_>, item| {
            acc.push(item);
            acc
        },
    )(s)
}

pub fn octal_value(s: &str) -> IResult<&str, Vec<&str>> {
    let (s, x) = is_a("01234567xXzZ?")(s)?;
    fold_many0(
        alt((tag("_"), is_a("01234567xXzZ?"))),
        vec![x],
        |mut acc: Vec<_>, item| {
            acc.push(item);
            acc
        },
    )(s)
}

pub fn hex_value(s: &str) -> IResult<&str, Vec<&str>> {
    let (s, x) = is_a("0123456789abcdefABCDEFxXzZ?")(s)?;
    fold_many0(
        alt((tag("_"), is_a("0123456789abcdefABCDEFxXzZ?"))),
        vec![x],
        |mut acc: Vec<_>, item| {
            acc.push(item);
            acc
        },
    )(s)
}

pub fn decimal_base(s: &str) -> IResult<&str, &str> {
    alt((
        tag("'d"),
        tag("'sd"),
        tag("'Sd"),
        tag("'D"),
        tag("'sD"),
        tag("'SD"),
    ))(s)
}

pub fn binary_base(s: &str) -> IResult<&str, &str> {
    alt((
        tag("'b"),
        tag("'sb"),
        tag("'Sb"),
        tag("'B"),
        tag("'sB"),
        tag("'SB"),
    ))(s)
}

pub fn octal_base(s: &str) -> IResult<&str, &str> {
    alt((
        tag("'o"),
        tag("'so"),
        tag("'So"),
        tag("'O"),
        tag("'sO"),
        tag("'SO"),
    ))(s)
}

pub fn hex_base(s: &str) -> IResult<&str, &str> {
    alt((
        tag("'h"),
        tag("'sh"),
        tag("'Sh"),
        tag("'H"),
        tag("'sH"),
        tag("'SH"),
    ))(s)
}

pub fn x_number(s: &str) -> IResult<&str, Vec<&str>> {
    let (s, x) = alt((tag("x"), tag("X")))(s)?;
    fold_many0(
        alt((tag("_"), is_a("_"))),
        vec![x],
        |mut acc: Vec<_>, item| {
            acc.push(item);
            acc
        },
    )(s)
}

pub fn z_number(s: &str) -> IResult<&str, Vec<&str>> {
    let (s, x) = alt((tag("z"), tag("Z"), tag("?")))(s)?;
    fold_many0(
        alt((tag("_"), is_a("_"))),
        vec![x],
        |mut acc: Vec<_>, item| {
            acc.push(item);
            acc
        },
    )(s)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(
            format!("{:?}", all_consuming(number)("659")),
            "Ok((\"\", IntegralNumber(UnsignedNumber([\"659\"]))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("'h 837FF")),
            "Ok((\"\", IntegralNumber(HexNumber(HexNumber { size: None, hex_base: \"\\\'h\", hex_value: [\"837FF\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("'o7460")),
            "Ok((\"\", IntegralNumber(OctalNumber(OctalNumber { size: None, octal_base: \"\\\'o\", octal_value: [\"7460\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("4af")),
            "Err(Error((\"af\", Eof)))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("4'b1001")),
            "Ok((\"\", IntegralNumber(BinaryNumber(BinaryNumber { size: Some([\"4\"]), binary_base: \"\\\'b\", binary_value: [\"1001\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("5 'D 3")),
            "Ok((\"\", IntegralNumber(DecimalNumber(DecimalNumber { size: Some([\"5\"]), decimal_base: \"\\\'D\", decimal_number: [\"3\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("3'b01x")),
            "Ok((\"\", IntegralNumber(BinaryNumber(BinaryNumber { size: Some([\"3\"]), binary_base: \"\\\'b\", binary_value: [\"01x\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("12'hx")),
            "Ok((\"\", IntegralNumber(HexNumber(HexNumber { size: Some([\"12\"]), hex_base: \"\\\'h\", hex_value: [\"x\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("16'hz")),
            "Ok((\"\", IntegralNumber(HexNumber(HexNumber { size: Some([\"16\"]), hex_base: \"\\\'h\", hex_value: [\"z\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("8 'd -6")),
            "Err(Error((\" \\\'d -6\", Eof)))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("4 'shf")),
            "Ok((\"\", IntegralNumber(HexNumber(HexNumber { size: Some([\"4\"]), hex_base: \"\\\'sh\", hex_value: [\"f\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("16'sd?")),
            "Ok((\"\", IntegralNumber(DecimalNumber(DecimalNumber { size: Some([\"16\"]), decimal_base: \"\\\'sd\", decimal_number: [\"?\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("27_195_000")),
            "Ok((\"\", IntegralNumber(UnsignedNumber([\"27\", \"_\", \"195\", \"_\", \"000\"]))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("16'b0011_0101_0001_1111")),
            "Ok((\"\", IntegralNumber(BinaryNumber(BinaryNumber { size: Some([\"16\"]), binary_base: \"\\\'b\", binary_value: [\"0011\", \"_\", \"0101\", \"_\", \"0001\", \"_\", \"1111\"] }))))"
        );
        assert_eq!(
            format!("{:?}", all_consuming(number)("32 'h 12ab_f001")),
            "Ok((\"\", IntegralNumber(HexNumber(HexNumber { size: Some([\"32\"]), hex_base: \"\\\'h\", hex_value: [\"12ab\", \"_\", \"f001\"] }))))"
        );
    }
}
```