递归中的反向引用

指定递归级别的反向引用

本教程前面的章节介绍了正则表达式递归和正则表达式子例程。在本章节中，“递归”一词是指整个正则表达式的递归，捕获组的递归以及对捕获组的子例程调用。上一章节还解释了这些功能在Ruby中捕获组的方式与在Perl和PCRE中的不同。     

当Perl，PCRE和Boost退出递归时，它们会还原捕获组。这意味着Perl，PCRE和Boost中的反向引用与在相同递归级别上与捕获组匹配的相同文本匹配。这样就可以做类似回文的事情。 

Ruby从递归退出时不会恢复捕获组。普通的反向引用将与那些与未回溯的捕获组的最新匹配相同的文本进行匹配，无论捕获组是在与反向引用相同还是不同的递归级别上找到其匹配项。基本上，Ruby中的普通反向引用不会对递归给予任何关注。  

但是，尽管Ruby中的常规捕获组存储没有对递归进行任何特殊处理，但Ruby实际上在所有递归级别上为每个捕获组存储了完整的匹配栈。该堆栈甚至包括正则表达式引擎已经退出的递归级别。

相对于评估反向引用的递归级别，Ruby中的反向引用可以与捕获组在任何递归级别匹配的文本相同。我们可以通过在名称后添加符号和数字，对命名反向引用使用相同的语法。在大多数情况下，我们将使用+0来告诉正则引擎我们希望反向引用以相同的递归级别重用捕获组中的文本。我们可以指定一个正数，以在更深层次的递归上引用捕获组。  

JGsoft V2还支持使用与Ruby相同的语法指定递归级别的反向引用。要在JGsoft V2中获得与Ruby相同的行为，我们必须在子例程调用中使用Ruby的\g语法。   

Ruby中的奇数长度回文

在Ruby中，我们可以使用

\b(?'word'(?'letter'[a-z])\g'word'\k'letter+0'|[a-z])\b

匹配回文词，例如a ，dad ，radar，racecar和redivider。为使此示例简单，此正则表达式仅匹配长度为奇数个字母的回文词。       

让我们看看这个正则表达式如何匹配radar 。该单词边界\b匹配字符串的开始。正则表达式引擎进入捕获组“letter”。[a-z]匹配r ，然后将其以递归级别为零存储在捕获组“letter”的堆栈中。现在，正则表达式引擎进入“word”组的第一个递归。(?'letter'[a-z])在递归级别一匹配捕获a。正则表达式进入“word”组的第二次递归。(?'letter'[a-z])在第二递归级别捕获d 。在接下来的两次递归中，该组在第三和第四级捕获a和r 。第五次递归失败，因为字符串中没有[a-z]要匹配的字符。正则表达式引擎必须回溯。                      

正则表达式引擎现在必须在“word”组中尝试第二种选择项。正则表达式中的第二个[a-z]与字符串中的最后一个r相匹配。引擎现在从成功的递归退出，从第四级返回到第三级递归。    

匹配\g’word’后，引擎达到\k’letter+0’。反向引用失败，因为正则表达式引擎已到达目标字符串的末尾。因此，它再次回溯。现在第二个选择项与a相匹配。正则表达式引擎从第三级递归退出。    

正则表达式引擎再次匹配\g’word’，需要再次尝试反向引用。反向引用指定+0或当前递归级别，即2。在此级别，捕获组与d匹配。反向引用失败，因为字符串中的下一个字符是r 。再次回溯，第二个选择项匹配d 。

现在，\k’letter+0’匹配字符串中的第二个a 。这是因为正则表达式引擎返回到了第一级递归，在此期间捕获组与第一个a匹配。正则表达式引擎退出第一级递归。     

正则表达式引擎现在返回所有递归之外。在此级别上，捕获组存储r 。现在，反向引用可以匹配字符串中的最后一个r 。由于引擎不再位于任何递归内，因此在该组之后继续进行正则表达式的其余部分。\b在字符串末尾匹配。到达正则表达式的末尾，并返回radar作为整体匹配项。       

对其他递归级别的反向引用

如果我们修改回文示例，可以很容易地理解对其他递归级别的反向引用。abcdefedcba也是与以前的正则表达式匹配的回文。考虑正则表达式\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter-1'|z)|[a-z])\b。现在，反向引用希望在捕获组的堆栈上将文本的匹配程度降低一级。它与字母z交替使用，以便在反向引用不匹配时可以匹配某些内容。     

新的正则表达式与abcdefdcbaz类似的字符串匹配。经过一堆匹配和回溯之后，第二个[a-z]匹配f 。正则表达式引擎从成功的第五次递归退出。捕获组“letter”已经以零到四的递归级别存储了匹配项a ，b ，c ，d和e 。该组的其他匹配被回溯，因此没有保留。          

现在，引擎评估反向引用\k’letter-1’ 。当前级别为4，反向引用指定-1。因此，引擎尝试匹配d ，该匹配成功。引擎从第四级递归退出。  

反向引用将继续匹配c ，b和a，直到正则表达式引擎退出第一级递归。现在，在所有递归之外，正则表达式引擎再次到达\k’letter-1’ 。当前级别为0，反向引用指定-1。由于递归级别-1从未发生，因此后向引用无法匹配。这不是错误，而只是对非参与捕获组的反向引用。但是反向引用有另一种选择。z匹配z ，\b匹配字符串的末尾。abcdefdcbaz已成功匹配。              

正则表达式

\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter-2'|z)|[a-z])\b

与abcdefcbazz匹配。

\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter-99'|z)|[a-z])\b

与abcdefzzzzzz匹配。      

从反方向上来看，

\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter+1'|z)|[a-z])\b

匹配abcdefzedcb 。再次，在进行了一系列匹配和回溯之后，第二个[a-z]匹配f ，正则表达式引擎返回到递归级别4，并且组“letter”在递归级别零到四时在堆栈上具有a ，b ，c ，d和e。            

现在，引擎评估反向引用\k’letter+1’。当前级别为4，反向引用指定+1。捕获组在递归级别5上进行了回溯。这意味着我们对未参与组有一个反向引用，该组没有匹配。选择项z确实匹配。引擎从第四次递归退出。   

在递归级别3上，后向引用指向递归级别4。由于捕获组在递归级别4上成功匹配，即使正则表达式引擎已退出该层递归，捕获组仍在其堆栈上具有该匹配项。因此，\k’letter+1’匹配e 。递归级别3已成功退出。   

反向引用将继续匹配d和c，直到正则表达式引擎退出第一次递归为止。现在，在所有递归之外，正则表达式引擎再次达到\k’letter+1’。当前级别为0，反向引用指定+1。捕获组仍保留其先前所有成功的递归级别。因此，后向引用仍然可以匹配该组在第一次递归中捕获的b 。现在\b在字符串末尾匹配。abcdefzdcb成功匹配。           

我们也可以在这个方向上将其扩展到我们想要的程度。正则表达式

\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter+2'|z)|[a-z])\b

与abcdefzzedc匹配。

\b(?'word'(?'letter'[a-z])\g'word'(?:\k'letter+99'|z)|[a-z])\b

与abcdefzzzzzz匹配。