Regular expressions such as (?R)?z or a?(?R)?z or a|(?R)z that use recursion without having anything that must be matched in front of the recursion can result in infinite recursion. If the regex engine reaches the recursion without having advanced through the text then the next recursion will again reach the recursion without having advanced through the text. With the first regex this happens immediately at the start of the match attempt. With the other two this happens as soon as there are no further letters a to be matched.

JGsoft V2 and Boost 1.64 and later treat the first regex as a syntax error because it always leads to infinite recursion. The fact that the recursion is optional does not change this. They allow the other two regexes because they have the option to match a before the recursion. Ruby 1.9 and later, all versions of PCRE and Delphi, PCRE2 10.20 and prior, PHP 7.2.x and prior, and R 3.6.3 and prior treat all three forms of potential infinite recursion as a syntax error. All versions of Perl, PCRE2 10.21 and later, PHP 7.3.0 and later, R 4.0.0 and later, and Boost 1.63 and prior allow all three forms.

Circular Infinite Subroutine Calls

Subroutine calls can also lead to infinite recursion. All flavors handle the potentially infinite recursion in ((?1)?z) or (a?(?1)?z) or (a|(?1)z) in the same way as they handle potentially infinite recursion of the entire regex, as described above.

But subroutine calls that are not recursive by themselves may end up being recursive if the group they call has another subroutine call that calls a parent group of the first subroutine call. When subroutine calls are forced to go around in a circle that too leads to infinite recursion. Detecting such circular calls when compiling a regex is more complicated than checking for straight infinite recursion. Only JGsoft V2 and Ruby 1.9 and later are able to detect this and treat it as a syntax error. All other flavors allow these regexes.

Errors and Crashes

When infinite recursion does occur, whether it’s straight recursion or subroutine calls going in circles, JGsoft V2, Perl, and PCRE2 treat it as a matching error that aborts the entire match attempt. Boost 1.64 handles this by not attempting the recursion and acting as if the recursion failed. If the recursion is optional then Boost 1.64 may find matches where other flavors throw errors.

PCRE 8.12 and prior and Boost 1.63 and prior crash when infinite recursion occurs. This also affects Delphi up to version XE6 and PHP up to version 5.4.8 as they are based on older PCRE versions. PCRE 8.13 fixed this by treating infinite recursion as a maching error like Perl does. Boost 1.64 fixed it by failing the recursive call but otherwise allowing the matching process to proceed. So with Boost 1.64 and later (?:a|(?R)|z) matches the string z. With Perl, PCRE2, and PCRE 8.13 it triggers a matching error when (?R) is attempted at the start of the string.

Endless Recursion

A regex such as a(?R)z that has a recursion token that is not optional and does not have an alternative without the same recursion leads to endless recursion. Such a regular expression can never find a match. When a matches the regex engine attempts the recursion. If it can match another a then it has to attempt the recursion again. Eventually a will run out of letters to match. The recursion then fails. Because it’s not optional the regex fails to match.

JGsoft V2 and Ruby detect this situation when compiling your regular expression. They flag endless recursion as a syntax error. Perl, PCRE, PCRE2, and Boost do not detect endless recursion. They simply go through the matching process which finds no matches.