You could have invented Parser Combinators

I was going to suggest it was based on Dan Piponi's slightly more relevant "You Could Have Invented Monads (And Maybe You Already Have)" [1] but after a quick dig found a comment seemingly by Dan Piponi [2] saying his article was indeed inspired by "You Could Have Invented Spectral Sequences". So I guess either way that's the original spark.

1: http://blog.sigfpe.com/2006/08/you-could-have-invented-monad... 2: http://blog.ezyang.com/2012/02/anatomy-of-you-could-have-inv...

Similarly titled article on Monads https://www.google.fr/search?q=you+could+have+invented+monad...

Attoparsec is pretty fast. http://www.serpentine.com/blog/2014/05/31/attoparsec/

I do the same in C++. I use Ragel for blasting through regular strings, where little extraction or semantic analysis is required, and use a full-blown recursive descent library for everything else.

Parser combinators are elegant but, at the end of the day, I find DSLs like PEGs, Ragels, and good old regex easier to read.

Well, in practice, it is a variant of recursive descent. It has pretty bad performance for certain grammars, but it is a perfectly good (and fast) alternative if you feel like spending time rewriting the grammar by hand to fit.

For example, nowadays gcc use recursive descent to parse C.

Also, not handling arbitrary CFG grammars well is extremely common, it is a feature that LL, LR, LALR, PEG and other all share. Is it obviously worse to have exponential time parsing something if compared to not parsing it at all? No, but if you need to handle ambiguity you probably should use a different algorithm.

I don't have experience with yacc, but bison can generate errors with almost that exact form. It's even possible to do Clang style underlining, although it takes some hand holding.

That said, usually recursive descent gives better errors but in my experience it's mostly from better recovery.

That was bad design in "yacc". To get decent diagnostics out of a parser generator of that type, error outputs need to indicate the last point at which the parser was on a unique, successful path, and where the parser input stream is at the error. The problem in the input is between those two points.

Between those points, the parser was working on several alternate possible parsings, none of which could be completed. Give the names of those grammar constructs to the user. So an error message should look like:

    struct point { float x, float y };
                          ^^^^^^^^^ Expected one of:
                          <structure-variable-name>
                          ;
                          }

I work in industry and I recently had to implement a special purpose templating language for our product. For various reasons none of the off the shelf ones quite did what we needed.

As a result I had to write a parser and interpreter. The thing about a lot of these computer science things is that you don't need them until you do. And then when you do it's nice to know about how they work.

One example from Rdio's image server code base: https://github.com/rdio/thor/blob/master/src/main/scala/com/...

It's used to parse arbitrarily complex transformations to apply to an image in the URL.

Any time you have to read a file format that doesn't have a library available already (or if you want to write that library). Plenty of industries have a de-facto standard file format that's basically text, but with some special command sequences or bracketing (e.g. recently I had someone ask me how to read "PGN" files, which turns out to be the standard way of recording chess games). Chess is a trivial example, but the "STL" format used by a CNC milling machine I've worked with is a pretty similar format.

So imagine I wanted to write a "middleware" piece for that milling machine - maybe it has a slight defect where its width measure isn't exactly the same as its depth measure (I expect modern machines automatically recalibrate themselves, but you can imagine weirder problems that this might not solve). Then I could write a program that would rescale models exported from a CAD application to match the weirdness of my particular machine, by reading the file, making the adjustments, and writing a new file.

For a less industrial example that I've actually done, I worked on a fan translation of a videogame. The scripts were, of course, in a weird format that the original makers came up with, with no publicly available libraries. So I wrote a parser that could separate the actual text lines from the timing information and so forth, allowing the translators to translate.

It might be applied (but this isn't the only possible approach, and I rarely use parser combinators) every time you need to write a parser. And when you need to write a parser? Oh, I have to write parsers all the time, seriously. It's not like all data is passed using json or something like this nowadays, there're plenty domains where obscure, custom data formats (often intended primarily to be read by humans, not processed by machines) are used. So when you need to use such a system with a custom data format you ought to write your own parser.