|
楼主 |
发表于 2017-12-7 16:18:52
|
显示全部楼层
Matching Nested Constructs with Balancing Groups 将嵌套结构与平衡组匹配* I- W% x: L1 ]* x
$ b' M& f. [& w- w+ o1 K2 Z4 }4 I
PowerGREP 有一个特殊的功能, 称为平衡组。平衡组的主要目的是匹配平衡的构造或嵌套的构造, 它们从哪里得到它们的名字。该功能的一个技术上更准确的名称是捕获组减法。这就是它的真正功能。此功能最初是由. NET regex 风格发明的, 它不支持regular expression recursion正则表达式递归。
1 @- [ X2 _% m: w$ w3 D3 u(?<capture-subtract>;regex)或(?'capture-subtract'regex)是平衡组的基本语法。它与命名的捕获组使用的语法相同, 但两个组名由减号分隔。该组的名称为 “capture 捕获"。当 "regex" 匹配时, 该匹配存储在 “capture 捕获" 的名称下。这与正常命名的捕获组没有什么不同。您可以省略组的名称。(?<-subtract>regex) 或 (?'-subtract'regex) 是捕获平衡组的语法。
4 f/ T0 a7 Q+ C1 a) ~ q! K( u名称 “subtract 减法" 必须是 regex 中另一个组的名称。当 regex 引擎进入平衡组时, 它从组 “subtract 减法" 中减去一个匹配项。如果组 “subtract 减法" 尚未匹配, 或者它的所有匹配项已被减去, 则平衡组将无法匹配。您可以将平衡组看作是一个条件, 它测试组 “subtract 减法", 将 "regex" 作为 "if" 部分, 而 "else" 部分总是无法匹配。不同之处在于, 平衡组具有从组 “subtract 减法" 中减去一个匹配项的附加特征, 而条件则使该组未触及。
% m1 ~+ f K0 } O. {- ELooking Inside The Regex Engine查看 Regex 引擎的内部
" X3 }1 L6 a& ]! k* n2 z) A; T- j2 n2 B5 i: R9 V, S2 Z3 u
让我们应用 regex (?'open'o)+(?'-open'c)+ 去匹配 ooccc。(?'open'o) 匹配第一个 o 和存储,作为第一次捕获的组 "open". quantifier + 重复该组。 (?'open'o) 匹配第二个 o 并将其存储为第二个捕获。再次重复,(?'open'o) 无法匹配第一个 c. 但 + 满足两个重复。
( i) A5 E9 Q3 H. D. e1 bregex 引擎前进到 (?'-open'c)。在引擎可以进入这个平衡组之前, 它必须检查减去组 "open" 是否捕获了什么。它有。引擎进入组, 从 "open" 中减去最近的捕获。这使得组 "open", 第一 o 作为其唯一的捕获。现在在平衡组中, c 匹配 c。引擎退出平衡组。因为在连字符之前没有指定名称, 所以没有捕获任何东西。平衡组也有 + 作为它的量词。引擎再次发现, 减去组 "open" 捕获的东西。正则表达式进入平衡组, 使组 "打开" 而不进行任何匹配。c 与字符串中的第二个 c 匹配。
+ S* X- L" j& [+ Z, M: S( f9 @平衡组再次重复。但这一次, regex 引擎发现组 "open" 没有匹配项。平衡组无法匹配。但 + 是满足两个迭代。引擎已到达 regex 的末尾。它返回 oocc 作为整体匹配。Match.Groups['open']。Success 将返回 false, 因为该组的所有捕获都被减去。
1 L9 M5 N' I: R( l* q, z B4 ]- sMatching Balanced Pairs 匹配平衡对
7 I' }0 T3 z, ~- j3 d; ~* s8 X) E3 D) m9 p
我们需要修改这个 regex, 如果我们想它匹配的 o's 和 c’s 平衡数。为了确保 regex 不匹配 ooccc, 它的 c's 大于 o's, 我们可以添加anchors定位点: ^(?'open'o)+(?'-open'c)+$。此 regex 经过与前一个相同的匹配过程。但之后 (?'-open'c)+ 无法匹配其第三次迭代, 引擎将达到 $, 而不是 regex 的末尾。此操作无法匹配。regex 引擎将回溯尝试不同的量词排列, 但它们都无法匹配。无法找到匹配项。
) t+ ~ s9 T4 Q/ b" @; ~: j: {4 [; @' k9 D6 h. l% s
但 ^(?'open'o)+(?'-open'c)+$ 仍然匹配 ooc。匹配的过程再次相同, 直到平衡组与第一个 c 匹配, 并将组 "open" 与第一个 o 作为其唯一捕获。限定符使引擎再次尝试平衡组。引擎再次发现, 减去组 "open" 捕获的东西。正则表达式进入平衡组, 使组 "open" 而不进行任何匹配。但是现在, c 无法匹配, 因为 regex 引擎已到达字符串的末尾。: C3 k( S; w% w
% e9 v Q; z0 B* Eregex 引擎现在必须从平衡组中返回。当回溯平衡组时, PowerGREP 也回溯减法。由于第一个 o 的捕获是在进入平衡组时从 "open" 中减去的, 因此现在在退出平衡组时将恢复此捕获。重复组 (?'-open'c)+ 现在已减少为单个迭代。但量词是好的, 因为 + 它总是意味着 "一次或更多"。在字符串的末尾, regex 引擎在正则表达式中达到 $ 匹配。整个字符串 ooc 作为整体匹配返回。Match.Groups['open']。捕获将字符串中的第一个 o 作为 CaptureCollection 中的唯一项。这是因为, 在回溯后, 第二个 o 从组中减去, 但第一个 o 不是。1 e& S& s/ ]. q
, v" C2 z# ?3 w! S6 o为了确保正则表达式与 oc 和 oocc 匹配, 而不是 ooc, 我们需要检查当匹配进程到达 regex 末尾时, 组 "open" 没有任何捕获。我们可以设置条件的做到。(?(open)(?!))是一个条件, 用于检查组 "open" 是否匹配某项。在 PowerGREP 中, 有匹配的东西意味着仍然在堆栈上没有回溯或减去的捕获。如果该组已捕获了某些内容, 则会计算条件的 "if" 部分。在这种情况下, 是空的负预测先行(?!),此前预测中的空字符串始终匹配。因为前瞻性是负的, 这会导致预测先行总是失败。因此, 如果组捕获了某些东西, 则条件总是失败。如果组没有捕获任何内容, 则对条件的 "else" 部分进行计算。在这种情况下, 没有 "else" 部分。这意味着如果组没有捕获到某些东西, 则条件总是成功。这使 (?(open)(?!))一个正确的测试, 以验证组 "open" 没有捕获剩余。/ K% {: t, e, W, m8 @7 e
; D) F3 M7 @: N g# P, ?^(?'open'o)+(?'-open'c)+(?(open)(?!))$无法匹配 ooc。当 c 无法匹配时, 由于 regex 引擎已到达字符串的末尾, 因此引擎回溯出平衡组, 并将 "open" 保留为单个捕获。正则表达式引擎现在到达条件, 无法匹配。regex 引擎将回溯尝试不同的量词排列, 但它们都无法匹配。无法找到匹配项。" L; h6 y* N3 H1 ]0 ~0 A5 H
; Q% u7 V2 x N+ l" x
^(?'open'o)+(?'-open'c)+(?(open)(?!))$匹配oocc。然后 (?'-open'c)+ 已匹配 cc, 正则表达式引擎不能第三次进入平衡组, 因为 "open" 没有捕获。引擎前进到条件。条件成功, 因为 "open" 没有剩余的捕获, 条件也没有 "else" 部分。现在 $ 匹配在字符串的末尾。
D" {9 V2 }$ I4 `4 Z) R; m0 _; F) g+ z; Z# s
Matching Balanced Constructs 匹配平衡结构
% N4 m1 \& W% [0 m5 t x, u K, r3 w( q0 \, W, g
^(?:(?'open'o)+(?'-open'c)+)+(?(open)(?!))$ 将捕获组和平衡组封装在一个捕获组中, 也会重复。此 regex 匹配任何类似 ooocooccocccoc 的字符串, 其中包含任意数量的完全平衡的 o 和 c, 任意数量的对按顺序排列, 嵌套到任意深度。平衡组确保 regex 永远不会匹配字符串中的任何点上的 c 的字符串, 它的左边有 o 的位置。结束时必须保持在重复组之外的条件, 确保 regex 永远不匹配具有大于 c 的字符串。
6 x5 I' m; R& v+ J" u( \2 k, A$ G^(?>(?'open'o)+(?'-open'c)+)+(?(open)(?!))$ 通过使用atomic group 原子组而不是捕获组来优化上一个 regex。当正则表达式找不到匹配时, 原子组也捕获, 消除了几乎所有的回溯, 这可以大大提高在使用大量 o 和 c 的长字符串时的性能, 但最终没有适当的平衡。原子组不会更改 regex 如何匹配具有平衡 o 和 c 的字符串。( i& E7 W% s2 }# {, { z* y% B
m*(?>(?>(?'open'o)m*)+(?>(?'-open'c)m*)+)+(?(open)(?!))$ 允许任意数量的字母 m 在字符串的任何地方, 而仍然需要所有 o 和 c 的平衡。在正则表达式的起始处允许任何数量的 m* 在第一个 o前。(?'open'o)+被改成 (?>(?'open'o)m*)+, 以允许任何数量的 m 在 o后。同样的, (?'-open'c)+ 被更改为 (?>(?'-open'c)m*)+ 允许任何数量的 m 在每个 c 之后。 $ d8 E5 q* [5 [' N9 l* v3 G3 i9 x
这是使用 PowerGREP 的平衡组或捕获组减法特征来匹配平衡结构的一般解决方案。可以用任何正则表达式替换 o, m 和 c,只要这些三中没有两个可以匹配相同的文本。
1 U- q; }- i/ I^[^()]*(?>(?>(?'open'\()[^()]*)+(?>(?'-open'\))[^()]*)+)+(?(open)(?!))$应用此技术匹配一个字符串, 其中所有括号都是完全平衡的。- P/ D+ K+ }: r' `7 P
Backreferences To Subtracted Groups 引用减去组
( m0 ~: m0 i( N- \
6 i8 E7 c9 G1 x( u8 I( k1 }您可以将引用用于由平衡组减去其匹配项的组。引用匹配该组的最新匹配, 而不是回溯或减去。regex (?'x'[ab]){2}(?'-x')\k'x'匹配 aab, abb, baa, 或 bba。它不符合匹配。字符串的第一和第三个字母必须相同。/ u& y/ U( T* [, N+ m
2 t3 l/ S/ m$ `, L0 @; @0 E+ z$ J$ `4 Y- i让我们看看(?'x'[ab]){2}(?'-x')\k'x'如何匹配 aba。第一次迭代 (?'x'[ab]) 捕获 a。第二个迭代捕获 b。现在 regex 引擎到达平衡组 (?'-x')。它检查组 "x" 是否匹配, 它有。引擎进入平衡组, 从组 "x" 的堆栈中减去匹配 b。平衡组中没有 regex 标记。它的匹配没有通过字符串前进。现在正则表达式引擎到达引用 \k'x'。组 "x" 的堆栈顶部的匹配是。字符串中的下一个字符也是引用匹配的 a。aba 被认为是一个整体的匹配。2 {1 o+ _. H! s) e2 k# ~
! d% O. H( s6 S" a' f8 C' k
当您将此 regex 应用于 abb 时, 匹配的进程是相同的, 只是引用无法匹配字符串中的第二个 b。由于 regex 没有其他的排列, 正则表达式引擎可以尝试, 因此匹配尝试失败。+ L A2 n& ?. Q: ]
' u8 F) ?( G: S
Matching Palindromes 匹配回文4 N, t! ~$ Q1 C
& |/ e; H7 o9 i0 n$ k! S/ l
^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$匹配任何长度的回文。这个正则表达式充分利用了引用和捕获组减法。它还在上一节中使用一个空平衡组作为 regex。/ R: T3 d- ~" W( U, s! b; r
% @! a( J: M5 w o
让我们看看这个 regex 是如何匹配回文radar。^ 匹配在字符串的开头。然后 (?'letter'[a-z])+ 循环五次。组 "letter" 结束时, 其堆栈上有五匹配项:r, a, d, a, 和 r。正则表达式引擎现在位于字符串的末尾并且位于 [a-z]? 上。在 regex 中。它不匹配, 但这很好, 因为量词使它可选。引擎现在到达\k'letter'。组 "letter" 有 r 在其栈的顶部。这无法匹配字符串末尾后的 void。' s2 q0 N. j8 h, U/ H+ \
9 s! S Q4 s; A! ~( Uregex 引擎回溯。(?'letter'[a-z])+ 减少到四次迭代, 在组 “letter" 的堆栈上留下 r, a, d, 和 a 。[a-z]?匹配 r。引用再次未能匹配的空白后, 字符串的末尾。引擎回溯, 迫使 [a-z]?放弃匹配现在 "letter" 有一个在其栈顶部。这将导致引用无法匹配 r。6 A0 F8 P! W7 r0 m
6 O$ D6 z+ l2 G* k) ~6 e8 w更多回溯如下。(?'letter'[a-z])+将减少为三次迭代, 在组 “letter" 的堆栈顶部保留 d。引擎再继续使用 [a-z]?。它再次失败, 因为没有 d 引用匹配。5 t; d, d4 ]: F% T* ~
4 \- h& r$ ]! g& K& D# H1 T
再次回溯, 将组 "letter" 的捕获栈还原为 r 和 a。现在形势变成[a-z]?匹配 d。引用匹配的是组 "letter" 中最近的匹配项, 而不是回溯。引擎现在到达空平衡组 (?'-letter')。此匹配, 因为组 "letter" 有一个要减去的匹配 a。
" ?, B2 v! Q7 F1 }/ U+ \ X2 j' @; F5 u+ G8 f
后向引用和均衡组内重复非捕获组,因此引擎试再一遍。后向引用匹配 r 和平衡组减去它从“letter”的叠加,使得捕获组没有任何匹配。重复一次,后向引用失败,因为该组“letter”对其堆栈没有匹配。这使得该组充当非捕获组。反向引用非捕获组始终在PowerGREP失败。+ j0 l, N# \4 H7 t
9 m/ Y, N4 d+ s. k" ](?:\k'letter'(?'-letter'))+ 成功匹配了两个迭代。现在,条件(?(letter)(?!)) 成功是因为组 "letter" 没有匹配左边. 锚 $ 也匹配. 回文radar已匹配。 |
|