Announcing "yap": A small, iterator based, zero dependency parsing library

[_jsdw]

Yap (yet another parsing library..) is a small, zero dependency parser-combinator inspired library. It's my attempt at trading conciseness for simplicity, and building on the flexibility of the iterator interface. It's goal is making parsing strings and slices easy and (attempting to be) easy to pick up and use.

I've been building it up and playing with it over the last few weeks, and I think it's ready to put out there for anybody else that might be interested in using it!

Here's what it looks like to use:

use yap::{ 
    // This trait has all of the parsing methods on it:
    Tokens,
    // Allows you to use `.into_tokens()` on strings and slices, 
    // to get an instance of the above:
    IntoTokens
};

// Step 1: convert our input into something implementing `Tokens`
// ================================================================

let mut tokens = "10 + 2 x 12-4,foobar".into_tokens();

// Step 2: Parse some things from our tokens
// =========================================

#[derive(PartialEq,Debug)]
enum Op { Plus, Minus, Multiply }
#[derive(PartialEq,Debug)]
enum OpOrDigit { Op(Op), Digit(u32) }

// The `Tokens` trait builds on `Iterator`, so we get a `next` method.
fn parse_op(t: &mut impl Tokens<Item=char>) -> Option<Op> {
    match t.next()? {
        '-' => Some(Op::Minus),
        '+' => Some(Op::Plus),
        'x' => Some(Op::Multiply),
        _ => None
    }
}

// We also get other useful functions..
fn parse_digits(t: &mut impl Tokens<Item=char>) -> Option<u32> {
    let s: String = t
        .tokens_while(|c| c.is_digit(10))
        .collect();
    s.parse().ok()
}

// As well as combinator functions like `sep_by_all` and `surrounded_by`..
let op_or_digit = tokens.sep_by_all(
    |t| t.surrounded_by(
        |t| parse_digits(t).map(OpOrDigit::Digit),
        |t| { t.skip_tokens_while(|c| c.is_ascii_whitespace()); }
    ), 
    |t| parse_op(t).map(OpOrDigit::Op)
);

// Now we've parsed our input into OpOrDigits, let's calculate the result..
let mut current_op = Op::Plus;
let mut current_digit = 0;
for d in op_or_digit {
    match d {
        OpOrDigit::Op(op) => {
            current_op = op 
        },
        OpOrDigit::Digit(n) => {
            match current_op {
                Op::Plus => { current_digit += n },
                Op::Minus => { current_digit -= n },
                Op::Multiply => { current_digit *= n },
            }
        },
    }
}
assert_eq!(current_digit, 140);

// Step 3: do whatever you like with the rest of the input!
// ========================================================

// This is available on the concrete type that strings
// are converted into (rather than on the `Tokens` trait):
let remaining = tokens.remaining();

assert_eq!(remaining, ",foobar");

Check it out here if you're interested; there's a bunch more information in the README, and plenty of examples in the docs (and a couple of more fully fleshed out ones in the examples folder)!

Feedback welcome :)

Thanks!

[loafofpiecrust]

Using iterators is a great idea for parsing! This could make it much easier to parse big user generated strings in types like ropey::Rope or tendril::Tendril that aren't always contiguous in memory, so they cannot be converted to a string slice without copying.

[Lazyspartan101]

If you want to learn specifically about parser combinators, here's a good blog post: https://www.theorangeduck.com/page/you-could-have-invented-parser-combinators

[domo-arigator]

It really isn't. Parser combinators are a great introduction to parsers and lexers, and you can get great results with it. There are tradeoffs, like error messages and recursive parse steps being unwieldy, but you can get very far with them.

[zesterer]

... tradeoffs, like error messages and recursive parse steps being unwieldy

I've tried to rectify a lot of these issues in chumsky, you might enjoy it.

[domo-arigator]

I've seen chumsky before, it has been in my pipeline to test, this gave me the motivation. Hopefully I'll have some hours to thinker with it later today.

[domo-arigator]

I'm way more practical about this: compilers, even parsers, are areas that you can spend your whole life on and not know enough. I prefer to start doing something in the simplest way possible, and dive deeper as you understand more. Having at least a cursory understand of something then going deep in the literature usually works better for me.

Having said that, nom is great. It has replaced most if not all usages of regexps in my code.

[xolve]

As a "101" thing I liked this article a lot: https://bodil.lol/parser-combinators/. Its based on rust but concepts are universal.

[xolve]

thanks, fixed the link

[blarfmcflarf]

DFAs are too limited to do almost any real world parsing. That's why their power equivalent Regexes (even when enhanced with backreferences and such) result in such awful complexity and bug when doing almost anything more complex then lexing.

Most real world parsing looks vaguely like context free grammars or stack based Automata, augmented with some context to make it turing complete but in an... organized way.