#nom #parser #packrat #extension

nom-packrat

Extension of nom to apply Packrat Parsing

16 releases

0.7.0 Mar 23, 2023
0.6.0 Aug 31, 2021
0.5.0 Nov 26, 2020
0.4.0 Apr 1, 2020
0.1.18 Jul 28, 2019

#142 in Parser tooling

Download history 395/week @ 2024-06-14 484/week @ 2024-06-21 326/week @ 2024-06-28 324/week @ 2024-07-05 465/week @ 2024-07-12 927/week @ 2024-07-19 618/week @ 2024-07-26 455/week @ 2024-08-02 537/week @ 2024-08-09 513/week @ 2024-08-16 557/week @ 2024-08-23 433/week @ 2024-08-30 522/week @ 2024-09-06 534/week @ 2024-09-13 548/week @ 2024-09-20 589/week @ 2024-09-27

2,274 downloads per month
Used in 12 crates (2 directly)

MIT/Apache

11KB
122 lines

nom-packrat

Extension of nom to apply "Packrat Parsing".

Actions Status Crates.io Docs.rs

Requirement

nom must be 5.0.0 or later. nom-packrat can be applied to function-style parser only.

Usage

[dependencies]
nom-packrat = "0.7.0"

Example

use nom::character::complete::char;
use nom::IResult;
use nom_packrat::{init, packrat_parser, storage};

// Declare storage used by packrat_parser
storage!(String);

// Apply packrat_parser by custom attribute
#[packrat_parser]
pub fn parser(s: &str) -> IResult<&str, String> {
    let (s, x) = char('a')(s)?;
    Ok((s, x.to_string()))
}

fn main() {
    let input = "a";

    // Initialize before parsing
    init!();
    let result = parser(input);

    println!("{:?}", result);
}

Performance

Syntax

<S> ::= <T> + <S> | <T> - <S> | <T>
<T> ::= ( <S> ) | a

Input

The following 8 patterns. The first pattern is named as "pair 0" and the last is "pair 7".

a
(a)
((a))
(((a)))
((((a))))
(((((a)))))
((((((a))))))
(((((((a)))))))

Result

  • original : the original nom parser
  • packrat : all parsers with #[packrat_parser]
  • packrat_opt: only <T> with #[packrat_parser]

This is an edge case. The execution time of the original parser increases exponentially. By packrat pasring, the time becomes linear. Instead packrat parsers consume more memory than the original parser.

speed

memory

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Dependencies

~2.5MB
~56K SLoC