3 ms·

Parser combinators are just recursive descent. That's it. They're just recursive descent - an idea that's been around since the 1960's. A parser combinator lib

by pubby 6y ago

Parser combinators are just recursive descent. That's it. They're just recursive descent - an idea that's been around since the 1960's. A parser combinator library is just fancy marketing speak for "recursive descent utility functions". All it is is a a bag of commonly used patterns wrapped up in generic functions. The hoopla is overblown.

GuuD 6y ago
Yes they are, but it's not about being novel. Parser combinators are abstraction, and damn good one: they are easily composable, reusable, and what's most important approachable even for somebody who is familiar with the functional approach but have never written parser before. While I could appreciate neat and tidy imperative recursive descent implementation, I would very much prefer to enjoy it from afar, not inside my own codebase.
fanf2 6y ago
And Pratt parsers are just precedence climbing, but I’ve rewritten unifdef’s precedence climbing expression evaluator in Pratt style and it has turned out much better, because of the way Pratt structures the technique so neatly. So the key feature of parser combinators is a neat and tidy way to structure a recursive descent parser, and the key feature of monadic parser combinators is to get extra neatness from Haskell’s categorical types.
- pubby 6y ago
  I wish more tutorials started with "Parser combinators is a neat and tidy way to structure a recursive descent parser" because I 100% agree. Mostly, my disagreements are how parser combinators presented and taught, obscuring the core ideas with a focus on language features and trivialities. To me, the monad/applicate stuff is a red herring. It's mostly used to simulate imperative sequencing. e.g. the Haskell code `Person <$> parseName <*> parseAddress` would be `return Person { parseName(), parseAddress() };` in C. There's a few tricks but it's not crucial to the parser combinator idea and doesn't help readability.

by pubby 6y ago

GuuD 6y ago

Yes they are, but it's not about being novel. Parser combinators are abstraction, and damn good one: they are easily composable, reusable, and what's most important approachable even for somebody who is familiar with the functional approach but have never written parser before. While I could appreciate neat and tidy imperative recursive descent implementation, I would very much prefer to enjoy it from afar, not inside my own codebase.

fanf2 6y ago

And Pratt parsers are just precedence climbing, but I’ve rewritten unifdef’s precedence climbing expression evaluator in Pratt style and it has turned out much better, because of the way Pratt structures the technique so neatly. So the key feature of parser combinators is a neat and tidy way to structure a recursive descent parser, and the key feature of monadic parser combinators is to get extra neatness from Haskell’s categorical types.

pubby 6y ago
I wish more tutorials started with "Parser combinators is a neat and tidy way to structure a recursive descent parser" because I 100% agree. Mostly, my disagreements are how parser combinators presented and taught, obscuring the core ideas with a focus on language features and trivialities. To me, the monad/applicate stuff is a red herring. It's mostly used to simulate imperative sequencing. e.g. the Haskell code `Person <$> parseName <*> parseAddress` would be `return Person { parseName(), parseAddress() };` in C. There's a few tricks but it's not crucial to the parser combinator idea and doesn't help readability.