• PCRE regex
  • Recursive patterns

  • Recursive patterns
  • Recursive patterns

    Recursive patterns

    Consider the problem of matching a string in
    parentheses, allowing for unlimited nested parentheses. Without the
    use of recursion, the best that can be done is to use a pattern
    that matches up to some fixed depth of nesting. It is not possible
    to handle an arbitrary nesting depth. Perl 5.6 has provided an
    experimental facility that allows regular expressions to recurse
    (among other things). The special item (?R) is provided for the
    specific case of recursion. This PCRE pattern solves the
    parentheses problem (assume the PCRE_EXTENDED option is set so that white space is
    ignored): \( ( (?>[^()]+) | (?R) )* \)

    First it matches an opening parenthesis. Then it
    matches any number of substrings which can either be a sequence of
    non-parentheses, or a recursive match of the pattern itself (i.e. a
    correctly parenthesized substring). Finally there is a closing

    This particular example pattern contains nested
    unlimited repeats, and so the use of a once-only subpattern for
    matching strings of non-parentheses is important when applying the
    pattern to strings that do not match. For example, when it is
    applied to
    it yields “no match” quickly. However, if a once-only subpattern is
    not used, the match runs for a very long time indeed because there
    are so many different ways the + and * repeats can carve up the
    subject, and all have to be tested before failure can be

    The values set for any capturing subpatterns are
    those from the outermost level of the recursion at which the
    subpattern value is set. If the pattern above is matched against
    (ab(cd)ef) the value for the capturing parentheses is
    “ef”, which is the last value taken on at the top level. If
    additional parentheses are added, giving \( ( ( (?>[^()]+) |
    (?R) )* ) \)
    then the string they capture is “ab(cd)ef”, the
    contents of the top level parentheses. If there are more than 15
    capturing parentheses in a pattern, PCRE has to obtain extra memory
    to store data during a recursion, which it does by using
    pcre_malloc, freeing it via pcre_free afterwards. If no memory can
    be obtained, it saves data for the first 15 capturing parentheses
    only, as there is no way to give an out-of-memory error from within
    a recursion.

    (?1), (?2) and so on can be used
    for recursive subpatterns too. It is also possible to use named
    subpatterns: (?P>name) or (?&name).

    If the syntax for a recursive subpattern reference
    (either by number or by name) is used outside the parentheses to
    which it refers, it operates like a subroutine in a programming
    language. An earlier example pointed out that the pattern
    (sens|respons)e and \1ibility matches “sense and
    sensibility” and “response and responsibility”, but not “sense and
    responsibility”. If instead the pattern (sens|respons)e and
    is used, it does match “sense and responsibility”
    as well as the other two strings. Such references must, however,
    follow the subpattern to which they refer.

    The maximum length of a subject string is the
    largest positive number that an integer variable can hold. However,
    PCRE uses recursion to handle subpatterns and indefinite
    repetition. This means that the available stack space may limit the
    size of a subject string that can be processed by certain