Parser combinators beat regex for the messy middle ground of parsing
A Vienna-based developer walks through parser combinators, a technique that sits between regex and heavyweight tools like tree-sitter. A parser is just a function from a string to a value plus the leftover input; chain several together with pSeq and you can turn a ping log into a structured object. Regex gets tangled on complex tasks and tree-sitter is often overkill, but this approach stays clean.
Regex gets messy on complex tasks, and tree-sitter often is overkill — for this middle ground, parser combinators are perfect.
- ArneCode
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
- marginalia_nu
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?
- akst
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.
- BoppreH
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.
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')]
[0]: https://stackoverflow.com/a/693818/252218
[1]: https://en.wikipedia.org/wiki/Lexical_analysis#Tokenization
- boomlinde
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.