←back to thread

Parser Combinators Beat Regexes

(entropicthoughts.com)
120 points mooreds | 2 comments | 09 Apr 25 21:53 UTC | HN request time: 0.4s | source
Show context
yen223 ◴[10 Apr 25 00:49 UTC] No.43639551[source]▶
Parser combinators are one of those ideas that is really powerful in practice, but will never be mainstream because it had the bad fortune of coming from the functional programming world. It's a shame too, because parser combinators are what made parsers click for me.

Take the hard problem of parsing a language, break it down into the much simpler problem of reading tokens, then write simple "combinators" (and, or, one_or_many, etc etc) to combine these simple parsers into larger more complex parsers.

You could almost build an entire parser combinator library from scratch from memory, because none of the individual components are complicated.

replies(13): >>43639775 #>>43639805 #>>43639834 #>>43640597 #>>43641009 #>>43641205 #>>43641459 #>>43641675 #>>43642100 #>>43642148 #>>43643853 #>>43644151 #>>43650405 #
fooker ◴[10 Apr 25 06:24 UTC] No.43641205[source]▶
Parser combinators are already mainstream. All/most real languages are implemented with hand written recursive descent parsers that closely resemble parser combinators, or at the very least borrow a bunch of concepts.

It's the name that's unlikely to become mainstream. That's squarely upon FP folks giving sci-fi names to common sense concepts.

replies(1): >>43642845 #
1. antonvs ◴[10 Apr 25 11:37 UTC] No.43642845[source]▶
Presumably you're not objecting to the word "parser".

What name would you use for "combinator"? It's a pretty simple word, based on the root "combine".

The common sense concept here is functions whose results depends only on their arguments, which makes them well-suited for being used in "combination" with other combinators, as in `f . g` or `f(g(x))`. That's called function composition, which can be defined as the act of combining functions.

It's a term that has existed in logic for over a century, from before computers existed.

It seems to me that no amount of renaming of terms will fix people's lack of curiosity or lack of desire to learn or understand. That's on them.

replies(1): >>43646757 #
2. fooker ◴[10 Apr 25 18:26 UTC] No.43646757[source]▶
Every piece of software in existence calls functions and composes functions, there's no reason to attach 'combinator' to everything.

I do not doubt the correctness of the term, just the point of naming it. The fact that people write parsers all the time using these concepts without using the name proves that the name was not a great one.

> It's a term that has existed in logic for over a century, from before computers existed.

Yes, that's a great reason to not overload mathematical terms for random things. Monads and monoids are a great example of when this goes a bit wrong.

>It seems to me that no amount of renaming of terms will fix people's lack of curiosity or lack of desire to learn or understand.

Yes, I agree. Most people are just writing programs and solving problems, and moving on with their lives. It's weird to insist that they call something by a specific name if it's a simple idea that thousands of people have developed independently.