【正则表达式教程】递归中的捕获

• Z时代
• 2024-01-10
• 分类：综合

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

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

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的解决方案是使用指定递归级别的反向引用，而不是此页面的正则表达式中使用的常规反向引用。

本文转载自：迹忆客（https://www.jiyik.com）

以上是 【正则表达式教程】递归中的捕获 的全部内容， 来源链接： utcz.com/z/290341.html