13 releases

0.0.13 Aug 6, 2024
0.0.12 May 15, 2024
0.0.11 Apr 23, 2024
0.0.9 Mar 15, 2024
0.0.4 Feb 24, 2024

#236 in Rust patterns

Download history 172/week @ 2024-07-18 179/week @ 2024-07-25 336/week @ 2024-08-01 353/week @ 2024-08-08 265/week @ 2024-08-15 191/week @ 2024-08-22 224/week @ 2024-08-29 171/week @ 2024-09-05 214/week @ 2024-09-12 169/week @ 2024-09-19 175/week @ 2024-09-26 193/week @ 2024-10-03 151/week @ 2024-10-10 147/week @ 2024-10-17 122/week @ 2024-10-24 107/week @ 2024-10-31

4,937 downloads per month
Used in 5 crates (3 directly)

MIT license

12KB
216 lines

The Simplest Parser Library (TSPL)

TSPL is the The Simplest Parser Library that works in Rust.

Concept

In pure functional languages like Haskell, a Parser can be represented as a function:

Parser<A> ::= String -> Reply<A, Error>

This allows us to implement a Monad instance for Parser<A>, letting us use the do-notation to create simple and elegant parsers for our own types. Sadly, Rust doesn't have an equivalent. Yet, we can easily emulate it by:

  1. Using structs and impl to manage the cursor state internally.

  2. Returning a Result, which allows us to use Rust's ? to emulate monadic blocks.

This library merely exposes some functions to implement parsers that way, and nothing else.

Example

As an example, let's create a λ-Term parser using TSPL.

  1. Implement the type you want to create a parser for.
enum Term {
  Lam { name: String, body: Box<Term> },
  App { func: Box<Term>, argm: Box<Term> },
  Var { name: String },
}
  1. Define your grammar. We'll use the following:
<term> ::= <lam> | <app> | <var>
<lam>  ::= "λ" <name> " " <term>
<app>  ::= "(" <term> " " <term> ")"
<var>  ::= alphanumeric_string
  1. Create a new Parser with the new_parser()! macro.
TSPL::new_parser!(TermParser);
  1. Create an impl TermParser, with your grammar:
impl<'i> TermParser<'i> {
  fn parse(&mut self) -> Result<Term, String> {
    self.skip_trivia();
    match self.peek_one() {
      Some('λ') => {
        self.consume("λ")?;
        let name = self.parse_name()?;
        let body = Box::new(self.parse()?);
        Ok(Term::Lam { name, body })
      }
      Some('(') => {
        self.consume("(")?;
        let func = Box::new(self.parse()?);
        let argm = Box::new(self.parse()?);
        self.consume(")")?;
        Ok(Term::App { func, argm })
      }
      _ => {
        let name = self.parse_name()?;
        Ok(Term::Var { name })
      }
    }
  }
}
  1. Use your parser!
fn main() {
  let mut parser = TermParser::new("λx(λy(x y) λz z)");
  match parser.parse() {
    Ok(term) => println!("{:?}", term),
    Err(err) => eprintln!("{}", err),
  }
}

The complete example is available in ./examples/lambda_term.rs. Run it with:

cargo run --example lambda_term

Credit

This design is based on T6's new parser for HVM-Core, and is much cleaner than the old HOPA approach.

Dependencies

~16KB