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.
import re
# Initialize the scanner.
scanner = re.Scanner([
(r"\d+", lambda scanner, token: ('COUNT', int(token))),
(r"\w+", lambda scanner, token: ('ANIMAL', token.removesuffix('s'))),
(r"[,. ]", None), # None -> skip token.
])
# Scan a sample string.
results, remainder = scanner.scan("45 pigeons, 23 cows, 11 spiders.")
# Ensure we parsed the whole thing.
assert not remainder
print(results)
# [('COUNT', 45),
# ('ANIMAL', 'pigeon'),
# ('COUNT', 23),
# ('ANIMAL', 'cow'),
# ('COUNT', 11),
# ('ANIMAL', 'spider')]
[1]: https://en.wikipedia.org/wiki/Lexical_analysis#Tokenization
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.)
Issues with readability and communication? How pythonic.
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
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?
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 }));
}
}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.
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-...
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!
The ignore example is just p1 <* p2 in Haskell (that operator is in the standard library).
Seems like we're needlessly reintroducing limitations from the paper medium that don't exist in digital media for weird aesthetic reasons?
The user experience occludes great content though.
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.
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.
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 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.
„A Parser for Things is a function from Strings to Lists of Pairs of Things and Strings!“
Also, I wish I had been exposed to stuff like that my first semester of CS.
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.
type Parser<T> = (input: string) => [T, string]
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.
(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..)
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)).
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.
If you always define T as some useful stuff or unit, your experience with parser combinators and their composition is going to be miserable.
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.
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.
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 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.
A parser for a thing
Is a function from a string
To a list of pairs
Of strings and things.If it's a List, wouldn't you be forced to write the Cartesian product of two parsers instead?
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.
64 bytes from 1.1.1.1: icmp_seq=3 ttl=52 time=47.1 ms
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".
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.
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!
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.
pToken :: Parser<Bytestring, Token>
pExpr :: Parser<List<Token>, Expr>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)
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.
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
(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.)
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!
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!
> 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.bytes → (NewOrder | Cancel) → handlers → (Ack | Reject) →
https://github.com/hale-lang/hale/issues/1530#issuecomment-6...
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:
PInt = many1 pDigit
I say "according to TFA's design" because I've been arguing elsewhere that parsers must return Either<Error,(T, Remainder)> not (T, Remainder)
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!