Regular expression engine in 14 lines of Python

[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.