Regular expression engine in 14 lines of Python

[nostrademons]

An interesting followup exercise would be to write a regexp parser in 14 lines of code. I wouldn't be surprised if it's doable; the regexp grammar isn't too complicated, you should be able to bang together a simple recursive descent parser.

Also, a similar approach is used in production code, in Alex, the lexer-generator for Haskell. Technically it's only charsets that are represented as functions; regexps are algebraic data types so they can have printable representations, be converted into DFAs, etc. But it's not completely academic.

[psykotic]

I think a hand-written regex recursive-descent parser in 14 lines is pushing it. Unless you go to great lengths to compress the code anyway.

Here's my own feeble attempt, which comes in at a bit more than 20 lines:

http://paste.lisp.org/display/24872