教程 > 正则表达式 > 递归 阅读:50

递归中的捕获

子例程调用可能会捕获,也可能不会捕获


本教程使用了下面的例子介绍了子例程调用:

Name: John Doe
Born: 17-Jan-1964
Admitted: 30-Jul-2013
Released: 3-Aug-2013

在Ruby或PCRE中,我们可以使用以下正则表达式:

^Name:\ (.*)\n
Born:\ (?'date'(?:3[01]|[12][0-9]|[1-9])
               -(?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)
               -(?:19|20)[0-9][0-9])\n
Admitted:\ \g'date'\n
Released:\ \g'date'$

Perl需要稍微不同的语法,这在PCRE中也可以使用: 

^Name:\ (.*)\n
Born:\ (?'date'(?:3[01]|[12][0-9]|[1-9])
               -(?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)
               -(?:19|20)[0-9][0-9])\n
Admitted:\ (?&date)\n
Released:\ (?&date)$

不幸的是,这三种正则表达式在处理其语法之外的子例程调用方面存在差异。首先,在Ruby中,子例程调用使捕获组存储它在子例程调用期间匹配的文本。在Perl,PCRE和Boost中,子例程调用不会影响被调用的组。

当Ruby解决方案与上述示例匹配时,检索捕获组“ date”的内容将获得3-Aug-2013,该信息与对该组的最后一个子例程调用相匹配。当Perl解决方案与之匹配时,检索$+{date}会捕获17-Jan-1964。在Perl中,子例程调用根本没有捕获任何东西。但是,“Born”日期与一个正常的命名捕获组匹配,该捕获组存储了它正常匹配的文本。对该组的任何子例程调用都不会改变它。在这种情况下,即使我们将Ruby语法与PCRE一起使用,PCRE的行为也与Perl相同。

使用第一个正则表达式时,JGsoft V2的行为类似于Ruby。我们可以通过语法\g,此语法是Ruby发明,后来由PCRE复制,来记住这一点。当我们使用第二个正则表达式时,JGsoft V2的行为类似于Perl。我们还可以通过Perl在过程代码中使用&符进行子例程调用来记住这一点。   

如果要从匹配中提取日期,最好的解决方案是为每个日期添加另一个捕获组。然后,我们可以忽略“date”组存储的文本以及这些正则引擎之间的特殊区别。在Ruby或PCRE中:

^Name:\ (.*)\n
Born:\ (?'born'(?'date'(?:3[01]|[12][0-9]|[1-9])
                       -(?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)
                       -(?:19|20)[0-9][0-9]))\n
Admitted:\ (?'admitted'\g'date')\n
Released:\ (?'released'\g'date')$

Perl需要稍微不同的语法,这在PCRE中也可以使用: 

^Name:\ (.*)\n
Born:\ (?'born'(?'date'(?:3[01]|[12][0-9]|[1-9])
                       -(?:Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)
                       -(?:19|20)[0-9][0-9]))\n
Admitted:\ (?'admitted'(?&date))\n
Released:\ (?'released'(?&date))$

在递归或子例程调用中捕获组


当我们的正则表达式对包含其他捕获组的捕获组 进行子例程调用或递归调用时,Perl,PCRE和Ruby之间还有其他区别。如果整个正则表达式包含任何捕获组,那么同样的问题也会影响整个正则表达式的递归。对于本次主题的其余部分,术语“递归”同样适用于整个正则表达式的递归,递归到捕获组或对捕获组的子例程调用。  

在进入和退出递归时,PCRE和Boost会备份并还原捕获组。当正则表达式引擎进入递归时,它会在内部复制所有捕获组。这不会影响捕获组。递归内部的反向引用与递归之前捕获的文本匹配,除非它们引用的组在递归期间捕获了某些东西。递归后,所有捕获组都将替换为递归开始时创建的内部副本。递归过程中捕获的文本将被丢弃。这意味着我们不能使用捕获组来检索递归过程中匹配的部分文本。

Perl 5.10是第一个具有递归的版本,通过版本5.18,可以隔离每个递归级别之间的捕获组。当Perl 5.10的正则表达式引擎进入递归时,所有捕获组都会出现,因为它们尚未参加匹配。最初,所有反向引用都将失败。在递归过程中,捕获组将正常捕获。反向引用与在正常的相同递归过程中捕获的文本匹配。当正则表达式引擎从递归退出时,所有捕获组都将还原为递归之前的状态。Perl 5.20更改了Perl的行为,以PCRE的方式备份和还原捕获组。

但是,鉴于大多数实际情况,我们只能在其相应的捕获组之后使用反向引用。然后,Perl 5.10到5.18处理递归期间捕获组的方式与PCRE和更高版本的Perl所做的方式之间的区别仅仅是理论上的。

Ruby的行为是完全不同的。当Ruby的正则表达式引擎进入或退出递归时,它根本不会通过捕获组来对存储的文本进行任何更改。反向引用与捕获组在该组的最新匹配期间存储的文本匹配,而不用去考虑可能发生的任何递归。找到整体匹配项后,即使在递归过程中,每个捕获组仍会存储其最新匹配项的文本。这意味着我们可以使用捕获组来检索上次递归期间匹配的部分文本。

当我们使用从Ruby借用的\g语法时,JGsoft V2的行为类似于Ruby。使用任何其他语法时,其行为类似于Perl 5.20和PCRE。  

Perl和PCRE中的奇数长度的回文


在Perl和PCRE中,我们可以使用

\b(?'word'(?'letter'[a-z])(?&word)\k'letter'|[a-z])\b

匹配回文词,例如a ,dad ,radar ,racecar 和redivider。此正则表达式仅匹配长度为奇数个字母的回文词。这涵盖了英语中的大多数回文词。为了扩展正则表达式以处理字符数偶数的回文词,我们必须关心递归尝试失败后Perl和PCRE回溯方式的差异,本教程稍后将对此进行讨论。我们在这里先忽略这些差异,因为它们仅在目标字符串不是回文且找不到匹配项时才会发生。

让我们看看这个正则表达式如何匹配radar 的。该单词边界\b匹配字符串的开始。正则表达式引擎进入两个捕获组。[a-z]匹配r ,然后将其存储在捕获组“letter”中。现在,正则表达式引擎进入“单词”组的第一个递归。此时,Perl忘记了“letter”组与r相匹配。而PCRE没有。但这无关紧要。(?'letter'[a-z])匹配并捕获a。正则表达式进入“word”组的第二次递归。(?'letter'[a-z]) 捕获d 。在接下来的两次递归中,组捕获a和r 。第五次递归失败,因为字符串中没有[a-z]要匹配的字符。正则表达式引擎必须回溯。

因为(?&word)无法匹配,所以(?'letter'[a-z])必须放弃其匹配。该组恢复为a ,这是该组在递归开始时保留的文本。(它在Perl 5.18及更高版本中变为空。)这没关系,因为正则表达式引擎现在必须尝试在“word”组中的第二个替代方案,该组不包含反向引用。第二个[a-z]与字符串中的最后一个r匹配。引擎现在从成功的递归退出。该组“letter”存储的文本已经恢复到它在进入第四层递归之前的内容 a。

匹配(?&word)后,引擎到达\k'letter'。反向引用失败,因为正则表达式引擎已到达目标字符串的末尾。因此它再次回溯,使捕获组放弃了a 。现在,第二个选择项与a相匹配。正则表达式引擎从第三次递归退出。在第二次递归期间,组“letter”被还原为匹配的d 。

正则表达式引擎再次匹配(?&word)。反向引用再次失败,因为该组存储d,而字符串中的下一个字符是r 。再次回溯,第二个替代项匹配d,并且在第一次递归期间将组还原为a匹配项。

现在,\k'letter'匹配字符串中的第二个a 。这是因为正则表达式引擎返回了第一个递归,在此期间捕获组与第一个a匹配。正则表达式引擎退出第一个递归。捕获组将还原到它在第一次递归之前匹配的r 。

最后,反向引用匹配第二个r 。由于引擎不再位于任何递归内,因此在该组之后继续进行正则表达式的其余部分。\b在字符串末尾匹配。到达正则表达式的末尾,并返回radar作为整体匹配项。如果我们在匹配后查询“word”和“letter”这两个组,则会得到rad和r 。这是所有递归之外的这些组匹配的文本。

为什么此正则表达式在Ruby中不起作用


要在Ruby中以这种方式匹配回文,我们需要使用一个特殊的反向引用来指定递归级别。如果我们使用

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

中的普通反向引用,Ruby不会报错。但是,它也不会与比三个字母更长的回文匹配。相反,此正则表达式匹配a ,dad ,radaa ,raceccc和rediviiii之类的东西。

让我们看看为什么此正则表达式在Ruby中不能与radar匹配。Ruby像Perl和PCRE一样开始,进入递归直到字符串中没有[a-z]要匹配的字符为止。

因为\g’word’不匹配,所以(?'letter'[a-z])必须放弃其匹配。Ruby把它恢复到a,这是该组最近匹配的文本。第二个[a-z]与字符串中的最后一个r匹配。引擎现在从成功的递归退出。组“letter”继续保持其最近的匹配a 。

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

正则表达式引擎再次匹配\g’word’ 。反向引用再次失败,因为该组存储d,而字符串中的下一个字符是r 。再次回溯,该组还原为a并且第二个选择项匹配d 。

现在,\k’letter’匹配字符串中的第二个a 。正则表达式引擎退出成功匹配ada的第一个递归。捕获组继续持有“ a” ,这是其最近未回溯的匹配。

正则表达式引擎现在位于字符串中的最后一个字符。这个字符是r 。反向引用失败,因为该组仍包含a。引擎可以再次回溯,强制(?'letter'[a-z])\g'word'\k'letter'放弃到目前为止匹配的rada 。现在,正则表达式引擎返回到字符串的开头。它仍然可以尝试该组中的第二个选择方案。这与字符串中的第一个r匹配。由于引擎不再位于任何递归内,因此在该组之后继续进行正则表达式的其余部分。\b在第一个r之后不匹配。正则表达式引擎没有其他可尝试的排列。匹配尝试失败。

如果目标字符串为radaa ,则Ruby的引擎将执行与上述几乎相同的匹配过程。仅最后一段中描述的过程会更改。当正则表达式引擎到达字符串中的最后一个字符时,该字符现在为a。这次,反向引用匹配。由于引擎不再位于任何递归内,因此在该组之后继续进行正则表达式的其余部分。\b在字符串末尾匹配。到达正则表达式的末尾,并返回radaa作为整体匹配项。如果在匹配后查询“word”和“letter”组,将得到radaa和a 。这些是这些组中未回溯的最新匹配。

基本上,在Ruby中,此正则表达式会匹配长度为奇数个字母的任何单词,并且中间字母右侧的所有字符都与中间字母左侧的所有字符相同。这是因为Ruby仅在回溯捕获组时才将其还原,而从递归退出时则不会还原。

特定于Ruby的解决方案是使用指定递归级别的反向引用,而不是此页面的正则表达式中使用的常规反向引用。

查看笔记

扫码一下
查看教程更方便