alt Hacker NewsLove me some combinators. In my earlier days it helped bridge the academic gap of CS grammars and languages to something I could not readily apply to internship dev work. I seem to recall an attempt to map or generate the from regex and in reverse, but I might be crazy this early in the morning.
Nice visuals btw. If I may be so bold: slightly smaller font and header would make scrolling through the bottom readable code snippets a little easier!
Replies
schindlabua • today at 12:04 PM
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)
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