Strange Loop

Parser Combinators: How to Parse (nearly) Anything

Parser combinators are a programming concept that can be used to parse and process a huge class of grammars. They are lightweight and nimble like a rhinoceros thrown from a plane at altitude is not.

This is mostly a technique talk. Parser combinators are not specific to a language, nor are they found in only a single, specific library. They fill a wide gap where DSLs come up short and full parser-generators like ANTLR or yacc are too heavy-weight.

Under the hood, parser combinators are left-recursive (one of the 2 best kinds of recursive), have infinite lookahead (which, disappointingly, can not be used for nefarious time continuum-related mischief) and, for fans of category theory, can be defined both in terms of an associative binary operator and an identity value (I understand if this doesn't turn everyone's crank).

I'll explain all of the above and more, using sample code from diverse languages with that hope that I can impart a very practical knowledge to my listeners about what makes parser combinators tick and how they can be used to greatly expand the number of languages an application speaks.

Click to view published talk video

Nate Young

Nate Young


Nate Young is programmer living in the midwest. His first job was a strictly-maintenance programming position in a lightly padded cube. With his copious free time he learned Common Lisp and made a _lot_ of origami cranes. He thinks there is a tao to the fact that even though he has since moved on to more stimulating software projects, he continues to try to bring his coding levels down to those of his first, lazy days as a programmer. Away from the computer, Nate plays the ancient Irish sport of hurling, enjoys hiking with his wife and 2 labradors, and has a decent ping-pong record, though he never really mastered his spin shots. If you like his talk, buy him a gin and tonic afterward. He is not that impressed with baby seals and generally roots for the orca.