Yet another Hacker News

45 points schindlabua 3 hours ago 21 comments

tikimcfee 1 hour ago | parent

Love me some combinators. In my earlier days it helped bridge the academic gap of CS grammars and languages to something I could not readily apply to internship dev work. I seem to recall an attempt to map or generate the from regex and in reverse, but I might be crazy this early in the morning.

Nice visuals btw. If I may be so bold: slightly smaller font and header would make scrolling through the bottom readable code snippets a little easier!

raddan 42 minutes ago | parent

Yeah, the academic presentation of parsing complexity is not very useful for real-world parsing tasks. It is useful to know that regular expressions are limited (NFAs “can’t count”, so they’re not good for trying to match an unbounded number of balanced parentheses, for example). But beyond that, we largely choose capable algorithms either for ease of use or speed. Combinators, PEGs, parser generators (like lex/yacc, ANTLR) are mostly easy. For speed, almost everyone rolls a parser by hand.

I like combinator style parsers because 1) it’s really easy to think of a discrete parsing task as a function 2) tokenizing is mostly irrelevant 3) for pedagogical reasons, they make it easier for students to grasp the point of curried functions and partial application.

I even maintain a (mostly mature) parser combinator library for TypeScript for students in my research group to use.

https://github.com/williams-cs/parsecco

monster_truck 1 hour ago | parent

I would suggest parsing my scroll wheel input and combinating it into page events

adrianhqs 1 hour ago | parent

Nice design

lacoolj 1 hour ago | parent

Did you use the new Claude Motion for this?

mrkeen 59 minutes ago | parent

Not a good starting type:

  type Parser<T> = (input: string) => [T, string]

This implies that it accepts a string and will return a T. Parsers might return a T.

The article also starts with the concept of a 'partial parser', from which other (non-partial?) parsers can be constructed?

  Or, and this is where the real power of partial parsers comes in: we wrap the chain up as a new parser of its own.

Nope, there's no distinction. If you combine partial parsers, you end up with a partial parser. If you combine full parsers (whatever that means) you end up with full parsers.

(Ironically there is a fitting definition of 'partial' here: the function isn't well defined on all inputs. For some inputs, T is returned, on other inputs, maybe an error is thrown, who knows..)

schindlabua 56 minutes ago | parent

Good input. Since we're working in typescript a partial parser can always throw an exception (It's what the parsimmon library does aswell I believe). I decided not to get into those technicalities too much!

raddan 55 minutes ago | parent

Combinators are functional—they always return something. But if you want to return nothing, fine; T is any type. Just return something like unit (ie, the singleton type that has nothing as a value).

rhdunn 34 minutes ago | parent

There are three return states that a parser (or partial parser) can return:

1. an item (`T`) for a successful parse;

2. an error (`ParseError`) for an unrecoverable parse error;

3. a partial item (`T with ParseError`) for a recoverable parse error or warning (known statically).

You may also want to differentiate between:

1. leaf nodes (numbers, identifiers, string literals, etc.);

2. composite/nested nodes (addition, multiplication, variable assignment, etc.).

pyrale 29 minutes ago | parent

T is not any type, T is a type defined at compile time, and usually checked against the parser’s implementation.

If you always define T as some useful stuff or unit, your experience with parser combinators and their composition is going to be miserable.

debugnik 9 minutes ago | parent

> If you combine partial parsers, you end up with a partial parser.

If by partial we mean the parser can fail, not necessarily. optional(elem) and repeat(elem) are total if elem doesn't consume input on error, at least for a reasonable semantics of parser combinators (although we usually consider it a programmer error if elem matches the empty string in repeat(elem)).

justinnk 57 minutes ago | parent

Very cool visual guide! I feel it is appropriate here to recite this little poem about parsers by Fritz Ruehr that stuck with me since my first semester of CS. With this, you will never forget the type signature of a parser.

„A Parser for Things is a function from Strings to Lists of Pairs of Things and Strings!“

https://people.willamette.edu/~fruehr/haskell/seuss.html

stevefan1999 49 minutes ago | parent

I love parser combinators so much. Those are possible because parsing itself exhibits monadic structure, it forms transition monoid, of its more well known name as the semiautomaton in the world of CS.

mbaranturkmen 43 minutes ago | parent

How does the parser decide _where_ to split the statement?

marginalia_nu 41 minutes ago | parent

I don't understand why this can't be on a single page. Makes it really hard to refer back to earlier "chapters" as you get new information when it's a slideshow. Can't search either.

Seems like we're needlessly reintroducing limitations from the paper medium that don't exist in digital media for weird aesthetic reasons?

BackacheDescent 40 minutes ago | parent

Just me or is clicking on share from the browser sharing the link with “example.com” instead of “t3.at”?

smusamashah 18 minutes ago | parent

Thanks for sharing. This was very easy to follow on many levels. I could see it's only 17 slides and the code was simple enough to read and understand. I have read the term parser combinators many time and now I actually understand it. Kudos to the writer for making it easy to understand.

9dev 17 minutes ago | parent

It's a cool guide, but you kind of missed the opportunity to parse the packet metadata as arbitrary key-value pairs, i.e. for:

  64 bytes from 1.1.1.1: icmp_seq=3 ttl=52 time=47.1 ms

everything after the colon is key-value data, and throwing in a generic parser for `pKeyVal()` would make an even better point of how elegant the approach is.

boomlinde 6 minutes ago | parent

The first address should probably not be parsed as an IP address as it can also be a hostname. Might seem like a nitpick, but it creates an opportunity to demonstrate what to do when you expect either of more than one kind of construct.