CINXE.COM

<!DOCTYPE html> <html lang="en"><head><meta charset="utf-8"><link rel=canonical href='https://https://www.regular-expressions.info//recursebackref.html'><title>Backreferences That Specify a Regular Expression Recursion Level</title> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta name="author" content="Jan Goyvaerts"> <meta name="description" content=""> <meta name="keywords" content=""> <link rel=stylesheet href="regex.css" type="text/css"><script src="theme.js" type="text/javascript"></script><link rel="alternate" type="application/rss+xml" title="New at Regular-Expressions.info" href="updates.xml"> </head> <body bgcolor=white text=black> <div id=top></div> <div id=btntop><div id=btngrid><a href="quickstart.html" target="_top"><div>Quick Start</div></a><a href="tutorial.html" target="_top"><div>Tutorial</div></a><a href="tools.html" target="_top"><div>Tools & Languages</div></a><a href="examples.html" target="_top"><div>Examples</div></a><a href="refflavors.html" target="_top"><div>Reference</div></a><a href="books.html" target="_top"><div>Book Reviews</div></a></div></div> <div id=contents><div id=side> <TABLE CLASS=side CELLSPACING=0 CELLPADDING=4><TR><TD CLASS=sideheader>Regex Tutorial</TD></TR><TR><TD><A HREF="tutorial.html" TARGET=_top>Introduction</A></TD></TR><TR><TD><A HREF="tutorialcnt.html" TARGET=_top>Table of Contents</A></TD></TR><TR><TD><A HREF="characters.html" TARGET=_top>Special Characters</A></TD></TR><TR><TD><A HREF="nonprint.html" TARGET=_top>Non-Printable Characters</A></TD></TR><TR><TD><A HREF="engine.html" TARGET=_top>Regex Engine Internals</A></TD></TR><TR><TD><A HREF="charclass.html" TARGET=_top>Character Classes</A></TD></TR><TR><TD><A HREF="charclasssubtract.html" TARGET=_top>Character Class Subtraction</A></TD></TR><TR><TD><A HREF="charclassintersect.html" TARGET=_top>Character Class Intersection</A></TD></TR><TR><TD><A HREF="shorthand.html" TARGET=_top>Shorthand Character Classes</A></TD></TR><TR><TD><A HREF="dot.html" TARGET=_top>Dot</A></TD></TR><TR><TD><A HREF="anchors.html" TARGET=_top>Anchors</A></TD></TR><TR><TD><A HREF="wordboundaries.html" TARGET=_top>Word Boundaries</A></TD></TR><TR><TD><A HREF="alternation.html" TARGET=_top>Alternation</A></TD></TR><TR><TD><A HREF="optional.html" TARGET=_top>Optional Items</A></TD></TR><TR><TD><A HREF="repeat.html" TARGET=_top>Repetition</A></TD></TR><TR><TD><A HREF="brackets.html" TARGET=_top>Grouping & Capturing</A></TD></TR><TR><TD><A HREF="backref.html" TARGET=_top>Backreferences</A></TD></TR><TR><TD><A HREF="backref2.html" TARGET=_top>Backreferences, part 2</A></TD></TR><TR><TD><A HREF="named.html" TARGET=_top>Named Groups</A></TD></TR><TR><TD><A HREF="backrefrel.html" TARGET=_top>Relative Backreferences</A></TD></TR><TR><TD><A HREF="branchreset.html" TARGET=_top>Branch Reset Groups</A></TD></TR><TR><TD><A HREF="freespacing.html" TARGET=_top>Free-Spacing & Comments</A></TD></TR><TR><TD><A HREF="unicode.html" TARGET=_top>Unicode</A></TD></TR><TR><TD><A HREF="modifiers.html" TARGET=_top>Mode Modifiers</A></TD></TR><TR><TD><A HREF="atomic.html" TARGET=_top>Atomic Grouping</A></TD></TR><TR><TD><A HREF="possessive.html" TARGET=_top>Possessive Quantifiers</A></TD></TR><TR><TD><A HREF="lookaround.html" TARGET=_top>Lookahead & Lookbehind</A></TD></TR><TR><TD><A HREF="lookaround2.html" TARGET=_top>Lookaround, part 2</A></TD></TR><TR><TD><A HREF="keep.html" TARGET=_top>Keep Text out of The Match</A></TD></TR><TR><TD><A HREF="conditional.html" TARGET=_top>Conditionals</A></TD></TR><TR><TD><A HREF="balancing.html" TARGET=_top>Balancing Groups</A></TD></TR><TR><TD><A HREF="recurse.html" TARGET=_top>Recursion</A></TD></TR><TR><TD><A HREF="subroutine.html" TARGET=_top>Subroutines</A></TD></TR><TR><TD><A HREF="recurseinfinite.html" TARGET=_top>Infinite Recursion</A></TD></TR><TR><TD><A HREF="recurserepeat.html" TARGET=_top>Recursion & Quantifiers</A></TD></TR><TR><TD><A HREF="recursecapture.html" TARGET=_top>Recursion & Capturing</A></TD></TR><TR><TD><A HREF="recursebackref.html" TARGET=_top>Recursion & Backreferences</A></TD></TR><TR><TD><A HREF="recursebacktrack.html" TARGET=_top>Recursion & Backtracking</A></TD></TR><TR><TD><A HREF="posixbrackets.html" TARGET=_top>POSIX Bracket Expressions</A></TD></TR><TR><TD><A HREF="zerolength.html" TARGET=_top>Zero-Length Matches</A></TD></TR><TR><TD><A HREF="continue.html" TARGET=_top>Continuing Matches</A></TD></TR> </TABLE><TABLE CLASS=side CELLSPACING=0 CELLPADDING=4><TR><TD CLASS=sideheader>More on This Site</TD></TR><TR><TD><A HREF="index.html" TARGET=_top>Introduction</A></TD></TR><TR><TD><A HREF="quickstart.html" TARGET=_top>Regular Expressions Quick Start</A></TD></TR><TR><TD><A HREF="tutorial.html" TARGET=_top>Regular Expressions Tutorial</A></TD></TR><TR><TD><A HREF="replacetutorial.html" TARGET=_top>Replacement Strings Tutorial</A></TD></TR><TR><TD><A HREF="tools.html" TARGET=_top>Applications and Languages</A></TD></TR><TR><TD><A HREF="examples.html" TARGET=_top>Regular Expressions Examples</A></TD></TR><TR><TD><A HREF="refflavors.html" TARGET=_top>Regular Expressions Reference</A></TD></TR><TR><TD><A HREF="refreplace.html" TARGET=_top>Replacement Strings Reference</A></TD></TR><TR><TD><A HREF="books.html" TARGET=_top>Book Reviews</A></TD></TR><TR><TD><A HREF="print.html" TARGET=_top>Printable PDF</A></TD></TR><TR><TD><A HREF="about.html" TARGET=_top>About This Site</A></TD></TR><TR><TD><A HREF="updates.html" TARGET=_top>RSS Feed & Blog</A></TD></TR></TABLE></DIV><div class=bodytext><div class=topad style="height:130px"><A HREF="https://www.regexbuddy.com/create.html" TARGET="_top"><picture><source media="(max-width: 370px)" srcset="ads/320/rxbtutorial100.png 1x, ads/320/rxbtutorial150.png 1.5x, ads/320/rxbtutorial200.png 2x, ads/320/rxbtutorial250.png 2.5x, ads/320/rxbtutorial300.png 3x, ads/320/rxbtutorial350.png 3.5x, ads/320/rxbtutorial400.png 4x"><source media="(max-width: 500px)" srcset="ads/360/rxbtutorial100.png 1x, ads/360/rxbtutorial150.png 1.5x, ads/360/rxbtutorial200.png 2x, ads/360/rxbtutorial250.png 2.5x, ads/360/rxbtutorial300.png 3x, ads/360/rxbtutorial350.png 3.5x, ads/360/rxbtutorial400.png 4x"><source media="(max-width: 660px)" srcset="ads/480/rxbtutorial100.png 1x, ads/480/rxbtutorial150.png 1.5x, ads/480/rxbtutorial200.png 2x, ads/480/rxbtutorial250.png 2.5x, ads/480/rxbtutorial300.png 3x, ads/480/rxbtutorial350.png 3.5x, ads/480/rxbtutorial400.png 4x"><source media="(max-width: 747px)" srcset="ads/640/rxbtutorial100.png 1x, ads/640/rxbtutorial150.png 1.5x, ads/640/rxbtutorial200.png 2x, ads/640/rxbtutorial250.png 2.5x, ads/640/rxbtutorial300.png 3x, ads/640/rxbtutorial350.png 3.5x, ads/640/rxbtutorial400.png 4x"><img src="ads/728/rxbtutorial100.png" srcset="ads/728/rxbtutorial100.png 1x, ads/728/rxbtutorial125.png 1.25x, ads/728/rxbtutorial150.png 1.5x, ads/728/rxbtutorial175.png 1.75x, ads/728/rxbtutorial200.png 2x, ads/728/rxbtutorial250.png 2.5x, ads/728/rxbtutorial300.png 3x, ads/728/rxbtutorial350.png 3.5x, ads/728/rxbtutorial400.png 4x" alt="RegexBuddy—Better than a regular expression tutorial!"></picture></A></div> <div class=bulb><h1>Backreferences That Specify a Recursion Level</h1><script type="text/javascript">showbulb();</script></div> Earlier topics in this tutorial explain <A HREF="recurse.html" TARGET="_top">regular expression recursion</A> and <A HREF="subroutine.html" TARGET="_top">regular expression subroutines</A>. In this topic the word “recursion” refers to recursion of the whole regex, recursion of capturing groups, and subroutine calls to capturing groups. The previous topic also explained that these features <A HREF="recursecapture.html" TARGET="_top">handle capturing groups differently</A> in Ruby than they do in Perl and PCRE. Perl, PCRE, and Boost restore capturing groups when they exit from recursion. This means that backreferences in Perl, PCRE, and Boost match the same text that was matched by the capturing group at the same recursion level. This makes it possible to do things like <a href="recursecapture.html#palindrome">matching palindromes</a>. Ruby does not restore capturing groups when it exits from recursion. <A HREF="backref.html" TARGET="_top">Normal backreferences</A> match the text that is the same as the most recent match of the capturing group that was not backtracked, regardless of whether the capturing group found its match at the same or a different recursion level as the backreference. Basically, normal backreferences in Ruby don’t pay any attention to recursion. But while the normal capturing group storage in Ruby does not get any special treatment for recursion, Ruby actually stores a full stack of matches for each capturing groups at all recursion levels. This stack even includes recursion levels that the regex engine has already exited from. Backreferences in Ruby can match the same text as was matched by a capturing group at any recursion level relative to the recursion level that the backreference is evaluated at. You can do this with the same syntax for <A HREF="named.html" TARGET="_top">named backreferences</A> by adding a sign and a number after the name. In most situations you will use <TT CLASS=code>+0</TT> to specify that you want the backreference to reuse the text from the capturing group at the same recursion level. You can specify a positive number to reference the capturing group at a deeper level of recursion. This would be a recursion the regex engine has already exited from. You can specify a negative number to reference the capturing group a level that is less deep. This would be a recursion that is still in progress. <a href="jgsoft.html#v2">JGsoft V2</a> also supports backreferences that specify a recursion level using the same syntax as Ruby. To get the same behavior with JGsoft V2 as with Ruby, you have to use Ruby’s <tt>\g</tt> syntax for your subroutine calls. <a name="palindrome.html"></a><h2>Odd Length Palindromes in Ruby</h2> In Ruby you can use <TT CLASS=syntax>\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b</TT> to match palindrome words such as <tt class=match>a</tt>, <tt class=match>dad</tt>, <tt class=match>radar</tt>, <tt class=match>racecar</tt>, and <tt class=match>redivider</tt>. To keep this example simple, this regex only matches palindrome words that are an odd number of letters long. Let’s see how this regex matches <tt class=match>radar</tt>. The <A HREF="wordboundaries.html" TARGET="_top">word boundary</A> <TT CLASS=syntax>\b</TT> matches at the start of the string. The regex engine enters the capturing group “word”. <TT CLASS=syntax>[a-z]</TT> matches <tt class=match>r</tt> which is then stored in the stack for the capturing group “letter” at recursion level zero. Now the regex engine enters the first recursion of the group “word”. <TT CLASS=syntax>(?'letter'[a-z])</TT> matches and captures <tt class=match>a</tt> at recursion level one. The regex enters the second recursion of the group “word”. <TT CLASS=syntax>(?'letter'[a-z])</TT> captures <tt class=match>d</tt> at recursion level two. During the next two recursions, the group captures <tt class=match>a</tt> and <tt class=match>r</tt> at levels three and four. The fifth recursion fails because there are no characters left in the string for <TT CLASS=syntax>[a-z]</TT> to match. The regex engine must backtrack. The regex engine must now try the second alternative inside the group “word”. The second <TT CLASS=syntax>[a-z]</TT> in the regex matches the final <tt class=match>r</tt> in the string. The engine now exits from a successful recursion, going one level back up to the third recursion. After matching <TT CLASS=syntax>\g'word'</TT> the engine reaches <TT CLASS=syntax>\k'letter+0'</TT>. The backreference fails because the regex engine has already reached the end of the subject string. So it backtracks once more. The second alternative now matches the <tt class=match>a</tt>. The regex engine exits from the third recursion. The regex engine has again matched <TT CLASS=syntax>\g'word'</TT> and needs to attempt the backreference again. The backreference specifies <TT CLASS=syntax>+0</TT> or the present level of recursion, which is 2. At this level, the capturing group matched <tt class=match>d</tt>. The backreference fails because the next character in the string is <tt class=string>r</tt>. Backtracking again, the second alternative matches <tt class=match>d</tt>. Now, <TT CLASS=syntax>\k'letter+0'</TT> matches the second <tt class=match>a</tt> in the string. That’s because the regex engine has arrived back at the first recursion during which the capturing group matched the first <tt class=match>a</tt>. The regex engine exits the first recursion. The regex engine is now back outside all recursion. At this level, the capturing group stored <tt class=match>r</tt>. The backreference can now match the final <tt class=match>r</tt> in the string. Since the engine is not inside any recursion any more, it proceeds with the remainder of the regex after the group. <TT CLASS=syntax>\b</TT> matches at the end of the string. The end of the regex is reached and <tt class=match>radar</tt> is returned as the overall match. <h2>Backreferences to Other Recursion Levels</h2> Backreferences to other recursion levels can be easily understood if we modify our palindrome example. <tt class=match>abcdefedcba</tt> is also a palindrome matched by the previous regular expression. Consider the regular expression <TT CLASS=syntax>\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter-1'|z)|[a-z])\b</TT>. The backreference now wants a match the text one level less deep on the capturing group’s stack. It is alternated with the letter <TT CLASS=syntax>z</TT> so that something can be matched when the backreference fails to match. The new regex matches things like <tt class=match>abcdefdcbaz</tt>. After a whole bunch of matching and backtracking, the second <TT CLASS=syntax>[a-z]</TT> matches <tt class=match>f</tt>. The regex engine exits from a successful fifth recursion. The capturing group “letter” has stored the matches <tt class=match>a</tt>, <tt class=match>b</tt>, <tt class=match>c</tt>, <tt class=match>d</tt>, and <tt class=match>e</tt> at recursion levels zero to four. Other matches by that group were backtracked and thus not retained. Now the engine evaluates the backreference <TT CLASS=syntax>\k'letter-1'</TT>. The present level is 4 and the backreference specifies -1. Thus the engine attempts to match <tt class=match>d</tt>, which succeeds. The engine exits from the fourth recursion. The backreference continues to match <tt class=match>c</tt>, <tt class=match>b</tt>, and <tt class=match>a</tt> until the regex engine has exited the first recursion. Now, outside all recursion, the regex engine again reaches <TT CLASS=syntax>\k'letter-1'</TT>. The present level is 0 and the backreference specifies -1. Since recursion level -1 never happened, the backreference fails to match. This is not an error but simply a <A HREF="backref2.html" TARGET="_top">backreference to a non-participating capturing group</A>. But the backreference has an alternative. <TT CLASS=syntax>z</TT> matches <tt class=match>z</tt> and <TT CLASS=syntax>\b</TT> matches at the end of the string. <tt class=match>abcdefdcbaz</tt> was matched successfully. You can take this as far as you like. The regular expression <TT CLASS=syntax>\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter-2'|z)|[a-z])\b</TT> matches <tt class=match>abcdefcbazz</tt>. <TT CLASS=syntax>\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter-99'|z)|[a-z])\b</TT> matches <tt class=match>abcdefzzzzzz</tt>. Going in the opposite direction, <TT CLASS=syntax>\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter+1'|z)|[a-z])\b</TT> matches <tt class=match>abcdefzedcb</tt>. Again, after a whole bunch of matching and backtracking, the second <TT CLASS=syntax>[a-z]</TT> matches <tt class=match>f</tt>, the regex engine is back at recursion level 4, and the group “letter” has <tt class=match>a</tt>, <tt class=match>b</tt>, <tt class=match>c</tt>, <tt class=match>d</tt>, and <tt class=match>e</tt> at recursion levels zero to four on its stack. Now the engine evaluates the backreference <TT CLASS=syntax>\k'letter+1'</TT>. The present level is 4 and the backreference specifies +1. The capturing group was backtracked at recursion level 5. This means we have a backreference to a non-participating group, which fails to match. The alternative <TT CLASS=syntax>z</TT> does match. The engine exits from the fourth recursion. At recursion level 3, the backreference points to recursion level 4. Since the capturing group successfully matched at recursion level 4, it still has that match on its stack, even though the regex engine has already exited from that recursion. Thus <TT CLASS=syntax>\k'letter+1'</TT> matches <tt class=match>e</tt>. Recursion level 3 is exited successfully. The backreference continues to match <tt class=match>d</tt> and <tt class=match>c</tt> until the regex engine has exited the first recursion. Now, outside all recursion, the regex engine again reaches <TT CLASS=syntax>\k'letter+1'</TT>. The present level is 0 and the backreference specifies +1. The capturing group still retains all its previous successful recursion levels. So the backreference can still match the <tt class=match>b</tt> that the group captured during the first recursion. Now <TT CLASS=syntax>\b</TT> matches at the end of the string. <tt class=match>abcdefzdcb</tt> was matched successfully. You can take this as far as you like in this direction too. The regular expression <TT CLASS=syntax>\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter+2'|z)|[a-z])\b</TT> matches <tt class=match>abcdefzzedc</tt>. <TT CLASS=syntax>\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter+99'|z)|[a-z])\b</TT> matches <tt class=match>abcdefzzzzzz</tt>. <div id=cntmobi>|&ensp;<a href='quickstart.html'>Quick Start</a>&ensp;|&ensp;<a href='tutorial.html'>Tutorial</a>&ensp;|&ensp;<a href='tools.html'>Tools & Languages</a>&ensp;|&ensp;<a href='examples.html'>Examples</a>&ensp;|&ensp;<a href='refflavors.html'>Reference</a>&ensp;|&ensp;<a href='books.html'>Book Reviews</a>&ensp;||&ensp;<a href='tutorial.html'>Introduction</a>&ensp;|&ensp;<a href='tutorialcnt.html'>Table of Contents</a>&ensp;|&ensp;<a href='characters.html'>Special Characters</a>&ensp;|&ensp;<a href='nonprint.html'>Non-Printable Characters</a>&ensp;|&ensp;<a href='engine.html'>Regex Engine Internals</a>&ensp;|&ensp;<a href='charclass.html'>Character Classes</a>&ensp;|&ensp;<a href='charclasssubtract.html'>Character Class Subtraction</a>&ensp;|&ensp;<a href='charclassintersect.html'>Character Class Intersection</a>&ensp;|&ensp;<a href='shorthand.html'>Shorthand Character Classes</a>&ensp;|&ensp;<a href='dot.html'>Dot</a>&ensp;|&ensp;<a href='anchors.html'>Anchors</a>&ensp;|&ensp;<a href='wordboundaries.html'>Word Boundaries</a>&ensp;|&ensp;<a href='alternation.html'>Alternation</a>&ensp;|&ensp;<a href='optional.html'>Optional Items</a>&ensp;|&ensp;<a href='repeat.html'>Repetition</a>&ensp;|&ensp;<a href='brackets.html'>Grouping & Capturing</a>&ensp;|&ensp;<a href='backref.html'>Backreferences</a>&ensp;|&ensp;<a href='backref2.html'>Backreferences, part 2</a>&ensp;|&ensp;<a href='named.html'>Named Groups</a>&ensp;|&ensp;<a href='backrefrel.html'>Relative Backreferences</a>&ensp;|&ensp;<a href='branchreset.html'>Branch Reset Groups</a>&ensp;|&ensp;<a href='freespacing.html'>Free-Spacing & Comments</a>&ensp;|&ensp;<a href='unicode.html'>Unicode</a>&ensp;|&ensp;<a href='modifiers.html'>Mode Modifiers</a>&ensp;|&ensp;<a href='atomic.html'>Atomic Grouping</a>&ensp;|&ensp;<a href='possessive.html'>Possessive Quantifiers</a>&ensp;|&ensp;<a href='lookaround.html'>Lookahead & Lookbehind</a>&ensp;|&ensp;<a href='lookaround2.html'>Lookaround, part 2</a>&ensp;|&ensp;<a href='keep.html'>Keep Text out of The Match</a>&ensp;|&ensp;<a href='conditional.html'>Conditionals</a>&ensp;|&ensp;<a href='balancing.html'>Balancing Groups</a>&ensp;|&ensp;<a href='recurse.html'>Recursion</a>&ensp;|&ensp;<a href='subroutine.html'>Subroutines</a>&ensp;|&ensp;<a href='recurseinfinite.html'>Infinite Recursion</a>&ensp;|&ensp;<a href='recurserepeat.html'>Recursion & Quantifiers</a>&ensp;|&ensp;<a href='recursecapture.html'>Recursion & Capturing</a>&ensp;|&ensp;<a href='recursebackref.html'>Recursion & Backreferences</a>&ensp;|&ensp;<a href='recursebacktrack.html'>Recursion & Backtracking</a>&ensp;|&ensp;<a href='posixbrackets.html'>POSIX Bracket Expressions</a>&ensp;|&ensp;<a href='zerolength.html'>Zero-Length Matches</a>&ensp;|&ensp;<a href='continue.html'>Continuing Matches</a>&ensp;|</div> <div id=copyright> Page URL: <A HREF="https://www.regular-expressions.info/recursebackref.html" TARGET="_top">https://www.regular-expressions.info/recursebackref.html</A> Page last updated: 22 November 2019 Site last updated: 06 November 2024 Copyright © 2003-2024 Jan Goyvaerts. All rights reserved. </div> </div> </div> </body></html>