Hacker News Reader

Comment by ArneCode | Hacker News Reader

I really like the animations, makes it intuitive to understand what is happening!

One disadvantage that I think parser combinators have, for example compared to parser generator libraries (where the parser is generated from a seperate grammar file), is that you have to add a lot of mapping / unwrapping code. In my opinion this makes the parsers harder to read.

As an attempt to improve this, I have been working on a parser combinator library in rust. It adds two extra combinators (capture and bind) which can store the results of parsers in buckets (bind) and use the values stored in these buckets later to construct results (capture). This allows you to eliminate the unwrapping / mapping code and seperate the grammar from the result contstruction.

If you have the time, I would really appreciate feedback on this!

You can find it here: https://github.com/ArneCode/marser

View on HN

My first contact with parser combinators was in a parser generator library: https://github.com/engelberg/instaparse

This is (probably weirdly, since I've just learned that the approach in the OP is the original one that introduced parser combinators) the first time I've seen parser combinators where the parsers are just functions like this. If you want to be able to combine parsers and you don't want to write a bunch of mapping/unwrapping code, why not just use combinators over parsers assembled by a parser generator?

I think parser generators and parser combinators both have their advantages and disadvantages. For example with parser combinators you can use the already existing tools of the language. If you want the specific advantages of parser combinators, this could be a reason for not wanting to mix this.

I'm struggling to see the point in this. Your roll example using Winnow. Not really that much (un)wrapping logic:

    use winnow::{Result, ascii::digit1, combinator::separated_pair, prelude::*};

    #[derive(Debug, PartialEq)]
    struct Roll {
        count: u32,
        sides: u32,
    }

    fn number(input: &mut &str) -> Result<u32> {
        digit1.try_map(str::parse).parse_next(input)
    }

    fn roll(input: &mut &str) -> Result<Roll> {
        let (count, sides) = separated_pair(number, 'd', number).parse_next(input)?;
        Ok(Roll { count, sides })
    }

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

        #[test]
        fn test_roll() {
            let input = &mut "3d6";
            assert_eq!(roll(input), Ok(Roll { count: 3, sides: 6 }));
        }
    }

In this case yes, but I would argue this is because the roll grammar is a relatively simple grammar, you have no nesting of different combinators etc. (I have used it in the README because it is simple to understand). The winnow code also using seperated_pair to ignore the "d" value, which is also adding some logic to retain only the count and sides result.

One grammar I have been using to make a comparison is a function signature. I tried comparing with nom and chumsky: https://blog.arnedebo.com/posts/a-grammar-first-approach-to-...

These libraries have found ways to replace "unwrapping" code with combinators like separated_by or .ignore_then etc. but this still leaves a lot of code for result handling, in my opinon making the code harder to read and reason about, which is what I attempt to improve.

These are of course very subjective things, so another person might prefer the ways the other libraries do this.

I get what you are saying. If you write a "recognizer" with parser combinators (like a regex without capture groups) and then want to convert that recognizer to an actual AST parser, you have to change it more deeply than just choosing what pieces to capture. You have to carefully follow a trail of left/right capture/discards to figure out what actually ends up in a function input. It's tree-shaped not linear-list-of-captures.

Some parser combinator environments are better than others. Haskell's applicative style is pretty good:

    (\x y z -> ...) <$> parser1 <*> parser2 <*> parser3

F#'s FParsec has pairwise operators `.>>`, `>>.`, and `.>>.` for capture-left-ignore-right, capture-right-ignore-left, and capture-both-and-tuple. These rapidly get unwieldy:

    parser1 .>>. parser2 .>>. parser3 |>> (fun ((x, y), z) -> ...) // ugly nested tuples!

So they have functions like `pipe3` instead:

    pipe3 parser1 parser2 parser3 (fun x y z -> ...)

Still, what a pain when you mix in some "ignored" parts in between the "captured" parts. Ugly and awkward to follow.

    pipe3 (whitespace >>. parser1) (char '(' >>. parser2 .>> char ')') (whitespace >>. parser3 .>> whitespace) (fun x y z -> ...)

I wrote a library some years ago to alleviate my issues with that F# flavor of this problem. My solution is very similar to yours in that it also asks the user to think of it as like regex "capture groups"!

https://rspeele.github.io/FParsec-Pipes/Intro.html

My approach is more symbolic-operator flavored than yours though. In mine you always start a chain of parsers with `%%`, separate with `--` and end with `-|> function`.

    %% parser1 -- parser2 -- parser3 -|> fun () -> ...

If you want to capture any part of the chain you use the unary prefix operator `+.` to mark it captured and it will get passed through to the consuming function.

    %% +.parser1 -- parser2 -- +.parser3 -|> fun p1 p3 -> ...

I used it extensively in a SQL parser:

https://github.com/fsprojects/Rezoom.SQL/blob/master/src/Rez...

What kind of mapping/unwrapping are you being subjected to with PCs?

When combining two parsers, for example in a sequence like pSeq in this website, you need to think about what to do with their return values. One approach is to put all return values in a tuple. So lets say we are combining parsers p1,p2,..., p_n in a sequence, then the return value of the parser created by pSeq(p1,p2,...,p_n) is (R(p1), R(p2), ..., R(p_n)) if R(p) is the return value of parser p.

When writing parsers you will often use multiple nested combinators. This means you have nested tuples. Getting the values out of these means "unwrapping" these tuples. Additionally you might not need all of the values in the sequence, some of them might only be for parsing whitespace. So when using the results of the parsers to construct values you have to ignore them. This can for example be done by "mapping" the resulting tuples and only leaving relevant fields. There are other approaches as well, for example chaining parsers with p1.then_ignore(p2) which only returns R(p1).

Maybe I could have chosen the words here a bit better, I hope this makes it more clear what I mean.

I have also tried making a side-by-side comparison of parsers for grammars being written using my library and others, maybe this can act as an example: https://blog.arnedebo.com/posts/a-grammar-first-approach-to-...

I’ve always used parser combinaties in Haskell and I’ve never seen the things you describe. I guess in Haskell one always directly apply the parts to the function you want (ie an AST node constructor).

We are spoiled in so many ways by Haskell!

Parser combinators alone makes monads (or really applicative functors) worth it. But then there are the all the other spectacular things we can do with monads!

This. The <$ and $> operators are very elegant for parsers.

I think this is because Haskell allows hiding the tuples construction/unwrapping with do-notation. My primary interaction with parser combinators, in OCaml, uses a similar trick with binding operators. If you don't have some sort of syntactic sugar like that they do become a lot more unwieldy.

Does your language have native tuple destructuring syntax?

The ignore example is just p1 <* p2 in Haskell (that operator is in the standard library).

Reply on news.ycombinator.com