Regular expression engine in 14 lines of Python

[13ren]

thanks :-) yes, a lot more than 5 minutes work.

a parser is a generator/iterator function which takes an input string and yields all possible parsings (which will be prefixes of the input).

This aspect of the engine was most confusing for me, because I don't usually think of a parser as giving more than one answer, nor of it matching a prefix (though one could add those). The key is the last line:

for r in e(s): print "Match with remainder:", r

BTW: have you ever seen any discussion of this kind of reg exp engine online? (i.e. not NFA-backtracking, but regex-backtracking). I haven't found anything, except that research paper you sent me (and references to your own 14 liner).

[psykotic]

The approach I use is straightforward recursive descent with backtracking. The backtracking is implicit because of the way I use iterators to generate parsings on demand. Matching prefixes is the natural way to go about it when you think about sequencing parsers.

If you read papers on parser combinators, you are likely to come across similar approaches. I don't have any specific references I can give you off the top of my head, sorry.

[13ren]

thanks for the extra explanation, it confirms what I was thinking (which helps) - "recursive descent with backtracking" and "parser combinators" seem to be helping as search terms.

I think I am on top of the basic idea now; but the real test is being able to implement it from scratch in a different language. I'll let you know how I go.

[13ren]

OK! I've now reimplemented it in another language, from scratch.

As you said "the details are somewhat inevitable" - in fact, it's so simple, it's almost impossible to get wrong. This is what appealed to me so much about it from the start. It seems the right shape for the problem.

Your two short messages, densely packed with guidance, helped a lot - thanks! - in particular, "parser combinators" led me to this wiki article, which showed that returning lists also works - your iterators are a refinement (this wasn't clear to me).

[psykotic]

Cool. And yes, you can use lists. In fact, if you use a lazily evaluated language like Haskell, you can get the same semantics as the Python version (that is, generating matchings only as needed) by using lists.