You may remember my recent node about extending regular expressions to allow recursion. I've completely rewritten the implementation, so that it backtracks properly. All the known bugs have been fixed, and both the regexes that Juerd posted last time now seem to work.

The web page has been updated to reflect the changes, and the new patch is available from there. The most significant functional change is that calls must be recursive. With the previous version you could write

/(a*)b(?1)/

and it would mean the same as /(a*)ba*/. Now you can only call out to a group that's still open. I made that change for technical reasons related to the implementation (so that I could use stack rather than heap storage, basically), but I don't think it's a big problem. Let me know if you disagree.

Proper detection of left recursion is implemented as well, meaning that a regex like /((?1))/ won't even compile now.

On a slight tangent, is anyone else interested in the idea of (as an experiment) hacking perl to use the PCRE library in place of its built-in engine? I don't think it would be all that hard.