Yeah, the academic presentation of parsing complexity is not very useful for real-world parsing tasks. It is useful to know that regular expressions are limited (NFAs “can’t count”, so they’re not good for trying to match an unbounded number of balanced parentheses, for example). But beyond that, we largely choose capable algorithms either for ease of use or speed. Combinators, PEGs, parser generators (like lex/yacc, ANTLR) are mostly easy. For speed, almost everyone rolls a parser by hand.

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.

https://github.com/williams-cs/parsecco

  pToken :: Parser<Bytestring, Token>

  pExpr :: Parser<List<Token>, Expr>

Thanks! The site is going through a redesign so some things aren't perfect yet, I'll keep it in mind next iteration :p

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)