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.

In reply to Recursive Regex: Update by robin

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.