Skip to content

The Simplest Parser Library (that works) in Rust

Notifications You must be signed in to change notification settings

HigherOrderCO/TSPL

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

32 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.

About

The Simplest Parser Library (that works) in Rust

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •  

Languages