If you're on Python and your problem is too big for a single regex, but too small for a full-blown parser like in the article, I can recommend the built-in re.Scanner[0]. It's a regex-based tokenizer[1] (so no recursive parsing) in the `re` module, that for reasons is completely missing from any official documentation.
You give it a pattern for each token type, and a function to process each match, and you get back a list of processed tokens.
Importantly, it processes the list in one pass and ensures the matches are contiguous, where a naive `re.findall` with capture groups will ignore unmatched characters. You also get a reference to the running scanner, so you can record the location of the match for reporting errors.
It is a nice addition to a weird region of “more than re” but “less than parsimonious”.
Usually these topics are
mentioned with no overlap (at least in the narrow rabbit hole I went down last time I was interested in making regexes simple to read for humans.)
Are the first use of 'scanner' and the second use of 'scanner' the same variable, or are they in different scopes. If they are in different scopes , would it be better to use a different variable, for the code to be more readable?
Different variable in a different scope referring to the same thing. Normally I'd agree with giving it a different name, but both scanner variables refer to the same object in memory, so it doesn't actually matter that they are different variables in the code as shown.
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?
I get your argument, but I liked it! Something about isolating each segment makes it feel more readable. Perhaps in an ideal world every article like this would allow the reader to switch between "slideshow" and "single page" view, since the same content would work for both.
Yes, it would be good. However I guess even simple show/hide chapters/sections also would do good work. It could be something similar to foldable directories or code fragments in code editors (for example VS Code has this feature).
Yes, I was at first discouraged to try to continue reading .. I’m glad I persisted .. but it’s as an annoyance to not know how to advance and then have to switch between scrolling and advancing instead of just scrolling ..
The user experience occludes great content though.
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!
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.
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.
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:
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"!
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`.
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.
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’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).
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!
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.
I think this is really cool website and love this topic
But I think you might want to test this page on smaller screens, just very limited screen real estate for the content of interest, the top right half lots of padding, the scrollable content basically has 1/3 of the available screen space, the left hand side kind of has another 1/3
Look your website your vision, I get it and I respect your trying something different with the UI but if your goal here is to communicate your ideas, as a reader I'd appreciate having more screen space for the content, when I clicked on the link to see this specific post I'm just not interested in your other posts (or at least until I've read the one I went out of my way to read).
Thanks for the feedback. The idea was to create something between a youtube video and a blog post and something you can consume in bite-sized pieces. I'd like the visuals to do most of the talking but I guess parser combinators came out with a lot of text anway. I'll try to tighten up the UI some and get a smaller phone for testing.
Another bad thing is that switching between pages doesn’t enter the browser history, which means you can’t use the browser’s Back/Forward controls to browse back and forth.
Really, inventing a new navigation UI for what is supposed to be a document, on top of a browser and bypassing its navigation conventions, simply isn’t a good idea.
I really enjoyed it and I look forward to trying out the ideas.
I think you are close to every effective presentation format, but the cramped space for the text was the biggest friction. The moving visuals, as helpful as they are, also became a little distracting as I was trying to absorb the meaning of the text. You could solve both issues with a toggle to hide or expand the visual.
I guess also, what’s happening in the top right is cool but I think as a user you’re preoccupied on figuring out how to view the other content it’s difficult to appreciate and I imagine that’s where you put a lot of effort
> I'd like the visuals to do most of the talking
If you’re aiming for a more curated experience, it might be worth limiting content that is likely to confuse the user for what the intended experience is meant to be. Many users have preconceived ideas of how some parts of the UI behave & which might get in the way to delivering the experience you’re trying to deliver.
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!“
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.
The article was somewhat difficult to read due to the limited area devoted to the body of the text. I had to scroll on several pages despite the short chapters.
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..)
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!
> 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)).
No, that was my ironically landed upon definition of partial.
The article used it as in a sub-parser, which is the other thing I objected to. If you add two Integers, you get back an Integer, not a Sum. Same principle here, two parsers make a parser. You don't need to write new code to combine a partial parser with a parser, or vice versa.
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).
You don’t need 2 and 3. You can express them just with with T. For example, you could use an Either type for “good, here’s your value/bad, here’s your error.” If you want to get more sophisticated, you can add a type with extra error cases. In my own combinator libraries, I also include extra failure information to make diagnosing failed parses easy (and to generate pretty output). This does not change the fact that T is sufficient.
No. The parser code (in a library that everyone depends on) will branch on success/fail internally. It has nothing to branch on if it only sees T, because T may not have a success/fail nature.
You could take a step back and make sure T has a fail case, e.g. T-extends-Either<A, B>, but what is to be gained?
* Firstly, what the hell is A?
* The user would need to type Parsers of T=Cat and T=Dog instead as Parsers of T=Either<Error,Dog> and T=Either<Error,Cat>. If everyone has to do it, pull the common abstraction back into the library itself! Also the caller would receive a successful parse of T=Either and would then need to check to see if it was success(success) or success(fail).
* You also mix abstractions in the same way as newlines in string literals. You could no longer represent a successful parse of a failed Either, since the failed Either would look like a parse error.
> T is not any type, T is a type defined at compile time,
This is a distinction without a difference. In a static, type-safe language, T always has to be instantiated with a type. But that does not change the fact that, from the perspective of the function definition, T is any type. T must be a specific type for the function call.
From the function's point of view it may be asked to return any type T. That is not the same thing as it being able to return any type that is convenient for its implementation.
What makes no sense? To be useful, a Parser<T> needs to return a type that is useful for the consumer. If your Parser<T> returns, say, an Id or a unit, and then you combine that with a parser whose type is:
Parser<T> -> Parser<List<T>>
You'll leave your user with the task of filtering their list. If the implementer for the list parser had done the same bad job, you'd use a:
Parser<T> -> Parser<List<T>|()>
And your final type would be:
Parser<List<Id|()>|()>
That would be beyond horrible to use, and anyone using such a parser combinator library would, rightfully, be extremely annoyed.
If you use an Either instead of a List, then you can write an or combinator, which accepts two parsers and tries the second if the first fails. It branches on the Left/Right of the Either.
If it's a List, wouldn't you be forced to write the Cartesian product of two parsers instead?
You’re going to write a monad and alternative instance for whatever structure you use. A list is a Cartesian product, but that’s just the join of parser B over each remaining input of parser A, it’s still a one-liner.
The question is capabilities. Either gives you an error result that might be useful. List gives you backtracking and, depending on your grammar, multiple parses. Maybe is like a weaker Either. Other monads might do other interesting things, but from the perspective of accepting strings satisfying a grammar, List is the choice that supports non-determinism.
(Laziness strongly recommended.)
The poem is not mine, I believe it is Conor McBride’s.
It's cute so I had to look it up. According to this guy [1], it's a poem from Graham Hutton's Haskell book [2]. I don't have the book so I can't check, but it sounds plausible.
The list represents the possible parses and the remaining input for each. In most cases you might prefer an unambiguous grammar, so a successful parse is a singleton list of a pair of the full parsed result with an empty input sequence.
But parser combinators build your final parser out of little bits, and sometimes those little bits might be something potentially ambiguous, like "any number of leading zeros followed by a number" which needs to parse "0" as no leading zeros and the number 0, but "00" as one leading zero and the number 0.
Non-deterministic parsers can easily blow out with backtracking much like careless recursive descent parsers, though.
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.
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.
This explains the concept of parser combinators pretty well.
Personally, I find the concepts of monads and data processing very interesting. A couple years ago, I’ve read a paper somewhere about “monadic parser combinators”. It intrigued me and I’ve experimented with the idea a lot. My initial idea was identical in regards of the return value.
It makes sense in terms of “logic” to return the extracted value and the rest, but in terms of performance it does not. It appears that string slicing is way slower than just working with an index. Well at least in nodejs that is.
Though the index approach requires a slightly different function signature to remain pure, which unfortunately makes it less as elegant to use in return.
I’ve clobbered this typescript library together, later with the help from Claude (shameless self-plug: https://github.com/sovrin/unitas).
It is typed to a degree (recursions are hit or miss) and should have every function one might need.
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!
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.
Thanks! The site is going through a redesign so some things aren't perfect yet, I'll keep it in mind next iteration :p
Parser combinators are stronger than pure regular expressions but I'm not sure how they compare to the non-regular regexes we use in programming (PCRE etc)
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.
Observation: In LISP and LISP-like languages, aka Functional programming languages, parsers can be written elegantly, as combinations of simpler parsing functions...
In theory this could also be done in Imperative or Object-Oriented programming languages (other programming language paradigms) as well, but the key to the elegance seems to come from two particular language aspects:
1) The ability for functions to return lists (not specific to Functional programming languages, many languages have this ability)
2) The ability of those lists to contain unstructured asymmetric data types of individual list elements at runtime, including the ability for arbitrary individual list elements to be first class, unnamed, dynamically created functions aka "Lambda Functions" at runtime.
Any Language which supports #1 and #2 has the ability to create some very elegant parsing functions based on simpler parsing functions.
Of course, parsers with the equivalent functionality can be written in any Turing-complete programming language (which is basically every programming language!), although with slightly less (and yes, aesthetics are always in the proverbial "eye of the beholder" -- so any given individuals's personal ones may be different from any other given individual's, and probably different than mine!) elegant-looking (IMHO) code...
An underrated quality of parser combinators is that they're often written in continuation passing style (monadic style is a simple generalisation of this). So, you get "incremental" parsing for free (as "what to do next" is trivially available). So, many of these parsers work well on streams (e.g. TCP sockets) without manually maintaining a state machine - as you may do in C. Further to this, such a state machine is derivable by defunctionalising the parser combinator code. Of course, you get the same benefit if you have decent coroutine support, but it's nice to see techniques that work around not having runtime/language support for such niceties.
There's another, more obscure, technique in the functional programming world called [iteratees](https://okmij.org/ftp/Haskell/Iteratee/index.html) which are quite neat and (as done in related article) linked to "online parser combinators".
Just as Claude is working in the background to fix any bug it can find in my ancient parser-combinator library in OCaml [0].
It's written in literate programing style, so it's not for everyone (I guess f you love the posted animated slide show, you won't like literate programming :)) but it has some cool features (and, according to Claude, some frightening bugs too): it can parse in stream mode, and it can be given an "error budget" to automatically fix syntax errors (be careful with this, as the complexity goes to the roof so quick I've never benn able to use this feature in any real scenario).
The main advantage of such a parser (and the reason why I'm reviving this one right now) is because they accept syntaxes that most other type of parsers would find ambiguous.
Others mentioned, but to make it more clear, the problem with regex is not that it gets messy/complex, but that it's formally proven that it's not possible to use regex for recursive parsing.
In fact regex has a regular grammar, and based on language theories, it's not possible to parse context-free grammar with a regular language.
@schindlabua: Your explanations made some things click for me for the very first time, thank you! (Also, the YouTube channel you linked to is indeed a fascinating rabbit hole: https://m.youtube.com/@ooqui )
In case you take suggestions for additional parts in that series: I would love to learn more about common color spaces such as DCI-P3 and Adobe RGB and how they relate to sRGB, and what the pipeline
(An application on, say, Linux/Wayland defines a pixel to have color C in color space S.)
->
(My color-corrected screen which supports/doesn't fully support color space S shows that color C.)
Haha wow, thank you that's very kind. I didn't really expect to make it to the front page today, feels like people are entering my flat when I haven't cleaned up in a while haha.
Ooqui inspired me to start a series on Colour actually. As a dev you'll naturally know a thing or two about colour or perception but this guy goes deep and it's super fascinating content I agree. Super unique too, I had never heard about most of the stuff he researches before watching his videos.
I'm working on a series about milk at the moment but I'll get back to colours eventually, there's a lot more to tell there :) Will make sure to give color spaces and gamut special treatment!
In my case the frustration came from having to figure out the github actions yml. And I am thankful to have not bothered going doing the ansible rabbit hole!
I hope you get time to work on making it mobile friendly, since it can be a time consuming endeavor and would encourage you to have an RSS feed for your blog!
> Now.. we’re really reaching the boundaries of my knowledge here, but as I understand, not all theorems in mathematics are provable by constructive proofs, which is what the Curry-Howard isomorphism gives us access to. So there will always be mathematical truths that are outside the reach of any type system, that are provable under for example the set of axioms known as Zermelo-Fraenkel set theory with the axiom of choice (ZFC). ZFC is provably more expressive than λC or any other type system we can come up with, because the axiom of choice gives us access to non-constructive proofs.
I am no expert on type theory nor logic but I think there are a few errors here:
- Curry-Howard is not restricted to intuitionistic logic / constructive type theories.
- Type systems can be made arbitrarily expressive.
- Non-constructive proofs exist in pure ZFC, too. They don't depend on assuming the Axiom of Choice. The core ingredient is the Law of Excluded Middle / proofs by contradiction.
I'm working on landing a similar feature in a language project, but in a general way, geared torward high level application flows. The general idea is that you can declare a "seam" between a function that returns a type set, and some other actor that exposes a method set that covers said typeset. The compiler can deal with the inbetween code, so the mainline of the app is just a set of typespace expansions/compressions. A callstack within a single thread domain can be expressed like:
They should at least point out the limitations of the approach. For example that they cannot handle left-recursive grammars, and that they tend to backtrack a lot on ambiguous grammars leading to exponentially bad performance.
All this seems for me to be overcomplicated. Naturally parsing is just a function, which may call subfunctions, sometimes recursively. Sometimes it can do it in a loop - in order to parse sequences.
I have written many parsers in such a way and I didn't even require such terms as "parser combinators".
If you're on Python and your problem is too big for a single regex, but too small for a full-blown parser like in the article, I can recommend the built-in re.Scanner[0]. It's a regex-based tokenizer[1] (so no recursive parsing) in the `re` module, that for reasons is completely missing from any official documentation.
You give it a pattern for each token type, and a function to process each match, and you get back a list of processed tokens.
Importantly, it processes the list in one pass and ensures the matches are contiguous, where a naive `re.findall` with capture groups will ignore unmatched characters. You also get a reference to the running scanner, so you can record the location of the match for reporting errors.
[0]: https://stackoverflow.com/a/693818/252218[1]: https://en.wikipedia.org/wiki/Lexical_analysis#Tokenization
Wow! This is a nice tidbit of information.
It is a nice addition to a weird region of “more than re” but “less than parsimonious”.
Usually these topics are mentioned with no overlap (at least in the narrow rabbit hole I went down last time I was interested in making regexes simple to read for humans.)
https://github.com/mikaelho/python-human-regex
https://github.com/vinta/awesome-python#text-processing
> is completely missing from any official documentation
Issues with readability and communication? How pythonic.
Are the first use of 'scanner' and the second use of 'scanner' the same variable, or are they in different scopes. If they are in different scopes , would it be better to use a different variable, for the code to be more readable?
Different variable in a different scope referring to the same thing. Normally I'd agree with giving it a different name, but both scanner variables refer to the same object in memory, so it doesn't actually matter that they are different variables in the code as shown.
Have you seen https://docs.python.org/3/library/re.html#writing-a-tokenize... ?
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?
I get your argument, but I liked it! Something about isolating each segment makes it feel more readable. Perhaps in an ideal world every article like this would allow the reader to switch between "slideshow" and "single page" view, since the same content would work for both.
Yes, it would be good. However I guess even simple show/hide chapters/sections also would do good work. It could be something similar to foldable directories or code fragments in code editors (for example VS Code has this feature).
[dead]
Yes, I was at first discouraged to try to continue reading .. I’m glad I persisted .. but it’s as an annoyance to not know how to advance and then have to switch between scrolling and advancing instead of just scrolling ..
The user experience occludes great content though.
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
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:
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:
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: So they have functions like `pipe3` instead: Still, what a pain when you mix in some "ignored" parts in between the "captured" parts. Ugly and awkward to follow. 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`.
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. 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.
This. The <$ and $> operators are very elegant for parsers.
This. The <$ and $> operators are very elegant for parsers.
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).
[dead]
I think this is really cool website and love this topic
But I think you might want to test this page on smaller screens, just very limited screen real estate for the content of interest, the top right half lots of padding, the scrollable content basically has 1/3 of the available screen space, the left hand side kind of has another 1/3
Look your website your vision, I get it and I respect your trying something different with the UI but if your goal here is to communicate your ideas, as a reader I'd appreciate having more screen space for the content, when I clicked on the link to see this specific post I'm just not interested in your other posts (or at least until I've read the one I went out of my way to read).
FWIW, I'm using a macbook air right now.
Thanks for the feedback. The idea was to create something between a youtube video and a blog post and something you can consume in bite-sized pieces. I'd like the visuals to do most of the talking but I guess parser combinators came out with a lot of text anway. I'll try to tighten up the UI some and get a smaller phone for testing.
Another bad thing is that switching between pages doesn’t enter the browser history, which means you can’t use the browser’s Back/Forward controls to browse back and forth.
Really, inventing a new navigation UI for what is supposed to be a document, on top of a browser and bypassing its navigation conventions, simply isn’t a good idea.
I really enjoyed it and I look forward to trying out the ideas.
I think you are close to every effective presentation format, but the cramped space for the text was the biggest friction. The moving visuals, as helpful as they are, also became a little distracting as I was trying to absorb the meaning of the text. You could solve both issues with a toggle to hide or expand the visual.
Definitely keep experimenting
I guess also, what’s happening in the top right is cool but I think as a user you’re preoccupied on figuring out how to view the other content it’s difficult to appreciate and I imagine that’s where you put a lot of effort
> I'd like the visuals to do most of the talking
If you’re aiming for a more curated experience, it might be worth limiting content that is likely to confuse the user for what the intended experience is meant to be. Many users have preconceived ideas of how some parts of the UI behave & which might get in the way to delivering the experience you’re trying to deliver.
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
I was just looking for that to post it! Instead google started trying to come up with its own Dr.Seuss themed parser combinator examples.
Also, I wish I had been exposed to stuff like that my first semester of CS.
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.
The article was somewhat difficult to read due to the limited area devoted to the body of the text. I had to scroll on several pages despite the short chapters.
Not a good starting type:
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?
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..)
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!
> 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)).
No, that was my ironically landed upon definition of partial.
The article used it as in a sub-parser, which is the other thing I objected to. If you add two Integers, you get back an Integer, not a Sum. Same principle here, two parsers make a parser. You don't need to write new code to combine a partial parser with a parser, or vice versa.
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).
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.).
You don’t need 2 and 3. You can express them just with with T. For example, you could use an Either type for “good, here’s your value/bad, here’s your error.” If you want to get more sophisticated, you can add a type with extra error cases. In my own combinator libraries, I also include extra failure information to make diagnosing failed parses easy (and to generate pretty output). This does not change the fact that T is sufficient.
No. The parser code (in a library that everyone depends on) will branch on success/fail internally. It has nothing to branch on if it only sees T, because T may not have a success/fail nature.
You could take a step back and make sure T has a fail case, e.g. T-extends-Either<A, B>, but what is to be gained?
* Firstly, what the hell is A?
* The user would need to type Parsers of T=Cat and T=Dog instead as Parsers of T=Either<Error,Dog> and T=Either<Error,Cat>. If everyone has to do it, pull the common abstraction back into the library itself! Also the caller would receive a successful parse of T=Either and would then need to check to see if it was success(success) or success(fail).
* You also mix abstractions in the same way as newlines in string literals. You could no longer represent a successful parse of a failed Either, since the failed Either would look like a parse error.
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.
> T is not any type, T is a type defined at compile time,
This is a distinction without a difference. In a static, type-safe language, T always has to be instantiated with a type. But that does not change the fact that, from the perspective of the function definition, T is any type. T must be a specific type for the function call.
From the function's point of view it may be asked to return any type T. That is not the same thing as it being able to return any type that is convenient for its implementation.
This literally makes no sense.
What makes no sense? To be useful, a Parser<T> needs to return a type that is useful for the consumer. If your Parser<T> returns, say, an Id or a unit, and then you combine that with a parser whose type is:
Parser<T> -> Parser<List<T>>
You'll leave your user with the task of filtering their list. If the implementer for the list parser had done the same bad job, you'd use a:
Parser<T> -> Parser<List<T>|()>
And your final type would be:
Parser<List<Id|()>|()>
That would be beyond horrible to use, and anyone using such a parser combinator library would, rightfully, be extremely annoyed.
If you use an Either instead of a List, then you can write an or combinator, which accepts two parsers and tries the second if the first fails. It branches on the Left/Right of the Either.
If it's a List, wouldn't you be forced to write the Cartesian product of two parsers instead?
You’re going to write a monad and alternative instance for whatever structure you use. A list is a Cartesian product, but that’s just the join of parser B over each remaining input of parser A, it’s still a one-liner.
The question is capabilities. Either gives you an error result that might be useful. List gives you backtracking and, depending on your grammar, multiple parses. Maybe is like a weaker Either. Other monads might do other interesting things, but from the perspective of accepting strings satisfying a grammar, List is the choice that supports non-determinism.
(Laziness strongly recommended.)
The poem is not mine, I believe it is Conor McBride’s.
It's cute so I had to look it up. According to this guy [1], it's a poem from Graham Hutton's Haskell book [2]. I don't have the book so I can't check, but it sounds plausible.
[1] https://myotherpants.com/tag/test-first/
[2] https://www.amazon.com/Programming-Haskell-Graham-Hutton/dp/...
Here the list is the "flattened” ast of (Node, slice of input corresponding to the node)
The list represents the possible parses and the remaining input for each. In most cases you might prefer an unambiguous grammar, so a successful parse is a singleton list of a pair of the full parsed result with an empty input sequence.
But parser combinators build your final parser out of little bits, and sometimes those little bits might be something potentially ambiguous, like "any number of leading zeros followed by a number" which needs to parse "0" as no leading zeros and the number 0, but "00" as one leading zero and the number 0.
Non-deterministic parsers can easily blow out with backtracking much like careless recursive descent parsers, though.
[dead]
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:
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.I would suggest parsing my scroll wheel input and combinating it into page events
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.
This explains the concept of parser combinators pretty well.
Personally, I find the concepts of monads and data processing very interesting. A couple years ago, I’ve read a paper somewhere about “monadic parser combinators”. It intrigued me and I’ve experimented with the idea a lot. My initial idea was identical in regards of the return value.
It makes sense in terms of “logic” to return the extracted value and the rest, but in terms of performance it does not. It appears that string slicing is way slower than just working with an index. Well at least in nodejs that is.
Though the index approach requires a slightly different function signature to remain pure, which unfortunately makes it less as elegant to use in return.
I’ve clobbered this typescript library together, later with the help from Claude (shameless self-plug: https://github.com/sovrin/unitas). It is typed to a degree (recursions are hit or miss) and should have every function one might need.
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!
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
Tokenising is actually a strength of PC, it fits the parser structure exactly!
Thanks! The site is going through a redesign so some things aren't perfect yet, I'll keep it in mind next iteration :p
Parser combinators are stronger than pure regular expressions but I'm not sure how they compare to the non-regular regexes we use in programming (PCRE etc)
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.
Me too! I've written quite a few (by hand) in my time. They're awesome for writing parsers that resemble the language you're trying to parse!
Great article!
Observation: In LISP and LISP-like languages, aka Functional programming languages, parsers can be written elegantly, as combinations of simpler parsing functions...
In theory this could also be done in Imperative or Object-Oriented programming languages (other programming language paradigms) as well, but the key to the elegance seems to come from two particular language aspects:
1) The ability for functions to return lists (not specific to Functional programming languages, many languages have this ability)
2) The ability of those lists to contain unstructured asymmetric data types of individual list elements at runtime, including the ability for arbitrary individual list elements to be first class, unnamed, dynamically created functions aka "Lambda Functions" at runtime.
Any Language which supports #1 and #2 has the ability to create some very elegant parsing functions based on simpler parsing functions.
Of course, parsers with the equivalent functionality can be written in any Turing-complete programming language (which is basically every programming language!), although with slightly less (and yes, aesthetics are always in the proverbial "eye of the beholder" -- so any given individuals's personal ones may be different from any other given individual's, and probably different than mine!) elegant-looking (IMHO) code...
Anyway, great article!
An underrated quality of parser combinators is that they're often written in continuation passing style (monadic style is a simple generalisation of this). So, you get "incremental" parsing for free (as "what to do next" is trivially available). So, many of these parsers work well on streams (e.g. TCP sockets) without manually maintaining a state machine - as you may do in C. Further to this, such a state machine is derivable by defunctionalising the parser combinator code. Of course, you get the same benefit if you have decent coroutine support, but it's nice to see techniques that work around not having runtime/language support for such niceties.
There's another, more obscure, technique in the functional programming world called [iteratees](https://okmij.org/ftp/Haskell/Iteratee/index.html) which are quite neat and (as done in related article) linked to "online parser combinators".
Just as Claude is working in the background to fix any bug it can find in my ancient parser-combinator library in OCaml [0]. It's written in literate programing style, so it's not for everyone (I guess f you love the posted animated slide show, you won't like literate programming :)) but it has some cool features (and, according to Claude, some frightening bugs too): it can parse in stream mode, and it can be given an "error budget" to automatically fix syntax errors (be careful with this, as the complexity goes to the roof so quick I've never benn able to use this feature in any real scenario).
The main advantage of such a parser (and the reason why I'm reviving this one right now) is because they accept syntaxes that most other type of parsers would find ambiguous.
[0]: https://github.com/rixed/ocaml-parsercombinator
Others mentioned, but to make it more clear, the problem with regex is not that it gets messy/complex, but that it's formally proven that it's not possible to use regex for recursive parsing.
In fact regex has a regular grammar, and based on language theories, it's not possible to parse context-free grammar with a regular language.
See langsec for more.
Great little series!
OP has written other fantastic posts, like this one on colors:
https://t3.at/blog/2026-08-21-color-1-rgb-cube/
@schindlabua: Your explanations made some things click for me for the very first time, thank you! (Also, the YouTube channel you linked to is indeed a fascinating rabbit hole: https://m.youtube.com/@ooqui )
In case you take suggestions for additional parts in that series: I would love to learn more about common color spaces such as DCI-P3 and Adobe RGB and how they relate to sRGB, and what the pipeline
looks like exactly.Haha wow, thank you that's very kind. I didn't really expect to make it to the front page today, feels like people are entering my flat when I haven't cleaned up in a while haha.
Ooqui inspired me to start a series on Colour actually. As a dev you'll naturally know a thing or two about colour or perception but this guy goes deep and it's super fascinating content I agree. Super unique too, I had never heard about most of the stuff he researches before watching his videos.
I'm working on a series about milk at the moment but I'll get back to colours eventually, there's a lot more to tell there :) Will make sure to give color spaces and gamut special treatment!
Loved your blog and unique presentation style!
I specifically resonated with your post [Please just give me a programming language man](https://t3.at/blog/2025-08-07-configuramming/).
In my case the frustration came from having to figure out the github actions yml. And I am thankful to have not bothered going doing the ansible rabbit hole!
I hope you get time to work on making it mobile friendly, since it can be a time consuming endeavor and would encourage you to have an RSS feed for your blog!
@schindlabua: On a different note, regarding your series on type systems, specifically the very last part https://t3.at/blog/2025-12-24-type-systems-iceberg/ :
> Now.. we’re really reaching the boundaries of my knowledge here, but as I understand, not all theorems in mathematics are provable by constructive proofs, which is what the Curry-Howard isomorphism gives us access to. So there will always be mathematical truths that are outside the reach of any type system, that are provable under for example the set of axioms known as Zermelo-Fraenkel set theory with the axiom of choice (ZFC). ZFC is provably more expressive than λC or any other type system we can come up with, because the axiom of choice gives us access to non-constructive proofs.
I am no expert on type theory nor logic but I think there are a few errors here:
Thanks! I might just reword that section or leave it out to not spread half-truths then. I'm really not very solid on either CoC or ZFC.
I'm working on landing a similar feature in a language project, but in a general way, geared torward high level application flows. The general idea is that you can declare a "seam" between a function that returns a type set, and some other actor that exposes a method set that covers said typeset. The compiler can deal with the inbetween code, so the mainline of the app is just a set of typespace expansions/compressions. A callstack within a single thread domain can be expressed like:
bytes → (NewOrder | Cancel) → handlers → (Ack | Reject) →
https://github.com/hale-lang/hale/issues/1530#issuecomment-6...
They should at least point out the limitations of the approach. For example that they cannot handle left-recursive grammars, and that they tend to backtrack a lot on ambiguous grammars leading to exponentially bad performance.
[dead]
All this seems for me to be overcomplicated. Naturally parsing is just a function, which may call subfunctions, sometimes recursively. Sometimes it can do it in a loop - in order to parse sequences. I have written many parsers in such a way and I didn't even require such terms as "parser combinators".
I think everyone should take some time out of their lives to learn parser combinators; they give you a good grasp of how languages work.
After building a few parsers with `nom`, my appreciation for English grew, and I took an interest in learning all the nuances of the language I speak.
Why is AI processed content so bad?
Just me or is clicking on share from the browser sharing the link with “example.com” instead of “t3.at”?
Can I parse (X)HTML that way, or should I go back to regex?
Regex is overkill for this. Just split the input string on '<' and '>'.
- 404 on your page?
- https://t3.at/blog
That was beautifully done!
How does the parser decide _where_ to split the statement?
Each parser blindly follows its own rules.
If pDigit saw "123 ", according to TFA's design, it would return (1, "23 ").
If PInt saw the "123 ", it would return (123, " ").
You could approximate pInt in terms of pDigit via:
(Ignoring negatives, int maxvalue, and many1 implies 1-or-more, not 0-or-more.)I say "according to TFA's design" because I've been arguing elsewhere that parsers must return Either<Error,(T, Remainder)> not (T, Remainder)
looks like standard functional programming to me
Nice design
Did you use the new Claude Motion for this?
I used plain Opus. Will check out Claude Motion though, thanks for mentioning it!
Not the OP, but thanks for mentioning this! Looks really useful.
[flagged]
[flagged]
[dead]