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

平衡组

将嵌套构造与平衡组匹配


.NET正则表达式引擎支持一个叫平衡组的特殊功能。平衡组的主要目的是匹配平衡结构或嵌套结构,这是它们从中获得名称的地方。从技术上讲,该功能更准确的名称是捕获组减法。这就是功能的真正作用。这是.NET解决其他正则表达式类型(如Perl,PCRE和Ruby)使用正则表达式递归处理的问题的解决方案。JGsoft V2支持平衡组和递归。   上面说的这些可能比较泛泛,不够具体,因为概念的东西有时候真的不是很好理解,只有结合具体的使用我们才能真正理解它的作用。到那时至于具体给它起个什么名字就无所谓了。

(?<capture-subtract>regex)(?'capture-subtract'regex)是平衡组的基本语法。它与.NET中命名捕获组所使用的语法相同,但是两个组名之间用减号分隔。该组的名称是“捕获”。我们可以忽略组的名称。(?<-subtract>regex)(?'-subtract'regex)是非捕获平衡组的语法。

名称“subtract”必须是正则表达式中另一个组的名称。当正则表达式引擎进入平衡组时,它会从组“subtract”中减去一个匹配项。如果组“subtract”尚未匹配,或者所有的匹配都已被减去,则平衡组将不匹配。我们可以将平衡组视为测试组“subtract”的条件,其中“regex”为“if”部分,而"else"部分始终不匹配。区别在于,平衡组具有从组“subtract”中减去一个匹配项的附加功能,而条件组则使该组保持不变。  

如果平衡组匹配成功并且具有名称(在此示例中为“capture”),则该组将捕获从组“subtract”减去的匹配结束到平衡组匹配的开始之间的文本本身(在此示例中为“regex”)。

在.NET中起作用的原因是,.NET中的捕获组保留了在匹配过程中未回溯或减去的所有捕获内容。大多数其他正则表达式引擎仅存储每个捕获组的最新匹配项。当(\w)+匹配abc然后Match.Groups[1].Value返回c与其它正则表达式引擎相同,但Match.Groups[1].Captures存储该组的所有三次迭代:a,b 和c 。

看看正则表达式引擎内部


让我们看看用正则表达式(?"open"o)+(?"between-open"c)+来匹配字符串ooccc 。(?'open'o)与第一个o匹配,并将其存储为组“open”的第一个捕获值。量词+使该组继续重复。(?'open'o)与第二个o匹配并将其存储为组“open”的第二个捕获。再次重复,(?'open'o)与第一个c不匹配。

正则表达式引擎前进到(?'between-open'c)。在引擎进入此平衡组之前,它必须检查减去的组“ open”是否捕获了某些东西。它已经捕获了第二个o 。引擎进入该组,从“open”中减去最新捕获的数据。这使组“open”以第一个o作为唯一捕获。现在在平衡组内部,正则标记c匹配字符c 。引擎退出平衡组。“between”组捕获从“open”(第二个o )减去的匹配项与由平衡组刚匹配的c之间的文本。虽然是一个空字符串,但仍然会被捕获。          

平衡组也有+作为其量词。引擎再次发现减去的组“open”捕获了某些东西,即第一个o 。正则表达式进入平衡组,使该组“open”没有任何匹配项。正则标记c匹配字符串中的第二个字符c 。“between”组捕获oc ,它是从“open”(第一个o )减去的匹配项与刚刚由平衡组匹配的第二个c之间的文本。

平衡组再次重复。但是这一次,正则表达式引擎发现组“open”没有匹配项。平衡组不匹配。“between”的组不受影响,保留了最近的捕获,oc。

该+满足两个迭代。引擎已到达正则表达式的末尾。它返回oocc作为整体匹配。Match.Groups[‘open’].Success将返回false ,因为减去了该组的所有捕获量。Match.Groups[‘between’].Value返回 “oc”。

匹配平衡对


如果我们希望它匹配平衡数量的o和c,则需要修改此正则表达式。为了确保正则表达式不匹配ooccc ,里面c的数量多于o的数量,我们可以添加锚点:^(?“open”o)+(?“open”c)+$ 。此正则表达式与前面的正则表达式的匹配过程使相同的。但是,在(?’-open’c)+未能匹配其第三次迭代之后,引擎到达$而不是正则表达式的结尾。$无法匹配。正则表达式引擎将回溯去尝试量词的不同排列,但是它们都不匹配,找不到匹配项。       

但是,正则表达式^(?‘open’o)+(?’-open’c)+$仍然可以匹配ooc 。匹配过程是相同的,直到平衡组与第一个c匹配并且将组“ open”与第一个o作为唯一捕获为止。量词使引擎再次尝试平衡组。引擎再次发现减去的组“ open”有捕获的值。正则表达式进入平衡组,从而使组“open”没有任何匹配项。但是现在,正则标记c无法匹配,因为正则表达式引擎已到达字符串的末尾。

正则表达式引擎现在必须回退到平衡组之外。当回溯平衡组时,.NET也会回溯减法。由于进入平衡组时从“open”中减去了第一个o的捕获值,因此现在恢复了该捕获,同时回溯到了平衡组之外。现在将重复的组(?’-open’c)+简化为单个迭代。但是,有量词+就可以了,因为+总是表示“一次或多次”。此时正则表达式引擎仍在字符串的末尾,正则表达式引擎在正则表达式中达到$ ,这两者相匹配。整个字符串ooc作为整体匹配项返回。

Match.Groups['open'].Captures将字符串中的第一个o保留为CaptureCollection中的唯一项。这是因为,在回溯之后,从组”open”中减去了第二个o ,但没有减去第一个o 。

为了确保正则表达式匹配oc和oocc但不匹配ooc ,当匹配过程到达正则表达式的末尾的时候,我们需要检查组“open”有没有剩余的捕获值。我们可以使用条件组做到这一点。((?open)(?!))是一个条件表达式,用于检查组“ open”是否有匹配某些内容。在.NET中,匹配某项意味着在堆栈上仍具有未回溯或减去的捕获。如果组已捕获到某些内容,则将评估条件的“if”部分。在这种情况下,这是空的否定前瞻断言(?!)。前瞻中的空字符串始终匹配。由于前瞻为否定,因此导致前瞻断言始终失败。因此,如果组已捕获某些内容,则条件始终为false。如果该组没有捕获任何东西,那么将评估条件的“else”部分。在这个表达式里,没有“else”部分。这意味着,如果组未捕获到某些条件,则if始终会成功。这使得((?open)(?!))成为一个非常合适的检测,可以验证“ open”组是否没有捕获。

正则表达式 ^(?’open’o)+(?’-open’c)+(?(open)(?!)))$不能匹配ooc 。当由于正则表达式引擎已到达字符串的末尾而导致c匹配失败时,引擎将回溯到平衡组之外,使得“open”只有一个捕获值。正则表达式引擎现在达到条件,该条件不匹配。正则表达式引擎将回退尝试量词的不同排列,但是它们都不能匹配。因此找不到匹配项。

正则表达式^(?’open’o)+(?’-open’c)+(?(open)(?!))$可以匹配oocc 。在(?'-open'c)+匹配cc之后,正则表达式引擎无法再次进入平衡组,因为“ open”没有剩余的捕获值。引擎前进到有条件的位置。条件为true,是因为“open”没有剩余捕获值,条件表达式中没有“else”部分。现在$匹配字符串的末尾。

匹配平衡结构


^(?:(?’open’o)+(?’-open’c)+)+(?(open)(?!)))$

将捕获组和平衡组封装在一个非捕获组中并使用量词+进行重复。此正则表达式匹配包含ooocooccocccoc之类的任何字符串,该字符串包含任意数量的完全平衡的o和c,并具有按顺序排列的任意数量的对,嵌套在任意深度。平衡组确保正则表达式永远不会匹配在字符串中任何一点上的c都比该点左边的o多的字符串。最后的条件必须保留在重复的组之外,以确保正则表达式永远不会匹配o的数量大于c的数量字符串。     

^(?>(?‘open’o)+(?’-open’c)+)+(?(open)(?!))$

通过使用原子组代替非捕获组来对之前的正则表达式进行优化。当正则表达式找不到匹配项时,原子组也不会捕获,消除了几乎所有的回溯,当在带有很多o和c的长字符串上使用但最终没有适当平衡时,可以大大提高性能。原子组不会更改正则表达式与具有平衡的o和c的字符串匹配的方式。   

^m*(?>(?>(?’open’o)m*)+(?>(?’-open’c)m*)+)+(?(open)(?!))$

允许任何字符串中任意位置的字母m的数量,同时仍然需要所有的o和c都是平衡的。正则表达式开头的m*允许在第一个o之前包含任意数量的m。(?’open’o)+更改为(?>(?’open’o)m*)+在每个o之后允许任意数量的m。类似地,将(?’-open’c)+更改为(?>(?’-open’c)m*)+在每个c之后允许任意数量的m。

这是使用.NET的平衡组或捕获组减法功能匹配平衡构造的通用解决方案。我们可以使用任何正则表达式替换o ,m和c ,只要这三个中没有两个可以匹配相同的文本即可。    

^[^()]*(?>(?>(?’open’\()[^()]*)+(?>(?’-open’\))[^()]*)+)+(?(open)(?!))$

应用此技术来匹配所有括号完全平衡的字符串。 

对减法组的反向引用


我们可以对平衡组中的被减去的组进行反向引用。反向引用与未回溯或减去的组的最新匹配项匹配。正则表达式(?’x’[ab]){2}(?’-x’)\k’x’匹配aaa ,aba ,bab或bbb 。它不匹配aab ,abb ,baa,或bba 。字符串的第一个和第三个字符必须相同。

让我们看看(?’x’[ab]){2}(?’-x’)\k’x’如何匹配aba 。(?’x’[ab])的第一次迭代捕获a。第二次迭代捕获b 。现在,正则表达式引擎到达平衡组(?’-x’)。它检查组“ x”是否匹配。引擎进入平衡组,从组“ x”的堆栈中减去匹配项b 。平衡组内没有正则表达式标记。它无需在字符串中前进。现在,正则表达式引擎到达反向引用\k’x’。组“x”的堆栈顶部的匹配是a 。字符串中的下一个字符也是a,反向引用可以匹配它。aba被认为是整体匹配项。

当我们将此正则表达式应用于abb时,匹配过程是相同的,只是反向引用无法匹配字符串中的第二个b 。由于正则表达式没有正则表达式引擎可以尝试的其他排列,因此匹配尝试失败。   

匹配回文


^(?’letter’[a-z])+[a-z]?(?:\k’letter’(?’-letter’))+(?(letter)(?!)))$

匹配任意长度的回文词。此正则表达式利用了以下事实:反向引用和捕获组减法可以很好地协同工作。在上一节中,还将空的平衡组用作正则表达式。 

让我们看看这个正则表达式如何与回文radar匹配。^匹配字符串的开头。然后(?’letter’[a-z])+重复五次。组“letter”以其堆栈上的五个匹配项结束:r ,a ,d ,a和r 。正则表达式引擎现在位于字符串的末尾且位于正则表达式的[a-z]?处。它不匹配,但这没什么问题,因为量词?使它成为可选的。引擎现在到达反向引用\k’letter’。组“letter”在其堆栈的顶部具有r 。这不能匹配字符串结尾之后的void。

正则表达式引擎回溯。(?’letter’[a-z])+减少为四个迭代,将r ,a ,d和a保留在“ letter”组的堆栈中。[a-z]?符合r 。在字符串结尾后,反向引用仍然无法匹配void。引擎回退,强制[a-z]?放弃匹配。现在,“letter”有a在它的堆栈的顶部。这将导致反向引用无法匹配r 。

接下来是更多的回溯。(?’letter’[a-z])+减少至三个迭代,将d保留在“letter”组的堆栈顶部。引擎再次以[a-z]?继续前进。。再次失败,因为没有d可以匹配反向引用。

再次回溯,组“letter”的捕获堆栈减少为r和a 。现在开始不再失败了。[a-z]?匹配d 。反向引用匹配a ,这是未回溯的组“letter”的最新匹配。引擎现在到达空的平衡组(?’-letter’)。之所以匹配,是因为组“letter”有一个匹配项a可以减去。

反向引用和平衡组位于重复的非捕获组内,因此引擎会再次尝试它们。反向引用匹配r ,并且平衡组从“letter”的堆栈中减去它,从而使捕获组没有任何匹配。再次迭代,反向引用失败,因为组“letter”的堆栈上没有剩余的匹配项。这使该组成为不参与匹配的组。像大多数正则表达式一样,对非参与组的反向引用在.NET中始终会失败。

(?:\k'letter'(?'-letter'))+已成功匹配两次迭代。现在,条件(?(letter)(?!))成功了,因为组“ letter”还没有匹配项。锚点$也匹配。回文radar已经匹配。

查看笔记

扫码一下
查看教程更方便