|
楼主 |
发表于 2017-12-7 16:18:52
|
显示全部楼层
Matching Nested Constructs with Balancing Groups 将嵌套结构与平衡组匹配
9 j2 O* M" L" F& _. f1 G0 G9 x
/ y5 L0 D+ [& v* D6 S" m2 VPowerGREP 有一个特殊的功能, 称为平衡组。平衡组的主要目的是匹配平衡的构造或嵌套的构造, 它们从哪里得到它们的名字。该功能的一个技术上更准确的名称是捕获组减法。这就是它的真正功能。此功能最初是由. NET regex 风格发明的, 它不支持regular expression recursion正则表达式递归。
* O2 q1 X$ r/ y% |1 \(?<capture-subtract>;regex)或(?'capture-subtract'regex)是平衡组的基本语法。它与命名的捕获组使用的语法相同, 但两个组名由减号分隔。该组的名称为 “capture 捕获"。当 "regex" 匹配时, 该匹配存储在 “capture 捕获" 的名称下。这与正常命名的捕获组没有什么不同。您可以省略组的名称。(?<-subtract>regex) 或 (?'-subtract'regex) 是捕获平衡组的语法。
5 j) y/ s1 x* W名称 “subtract 减法" 必须是 regex 中另一个组的名称。当 regex 引擎进入平衡组时, 它从组 “subtract 减法" 中减去一个匹配项。如果组 “subtract 减法" 尚未匹配, 或者它的所有匹配项已被减去, 则平衡组将无法匹配。您可以将平衡组看作是一个条件, 它测试组 “subtract 减法", 将 "regex" 作为 "if" 部分, 而 "else" 部分总是无法匹配。不同之处在于, 平衡组具有从组 “subtract 减法" 中减去一个匹配项的附加特征, 而条件则使该组未触及。
/ I0 {' [+ ~& E* w# PLooking Inside The Regex Engine查看 Regex 引擎的内部
- `; g* [+ f; W- N1 Y8 ? r) u; }# m0 J
让我们应用 regex (?'open'o)+(?'-open'c)+ 去匹配 ooccc。(?'open'o) 匹配第一个 o 和存储,作为第一次捕获的组 "open". quantifier + 重复该组。 (?'open'o) 匹配第二个 o 并将其存储为第二个捕获。再次重复,(?'open'o) 无法匹配第一个 c. 但 + 满足两个重复。
, J1 x3 b$ t- xregex 引擎前进到 (?'-open'c)。在引擎可以进入这个平衡组之前, 它必须检查减去组 "open" 是否捕获了什么。它有。引擎进入组, 从 "open" 中减去最近的捕获。这使得组 "open", 第一 o 作为其唯一的捕获。现在在平衡组中, c 匹配 c。引擎退出平衡组。因为在连字符之前没有指定名称, 所以没有捕获任何东西。平衡组也有 + 作为它的量词。引擎再次发现, 减去组 "open" 捕获的东西。正则表达式进入平衡组, 使组 "打开" 而不进行任何匹配。c 与字符串中的第二个 c 匹配。5 }, X" j) V/ ^+ e" y
平衡组再次重复。但这一次, regex 引擎发现组 "open" 没有匹配项。平衡组无法匹配。但 + 是满足两个迭代。引擎已到达 regex 的末尾。它返回 oocc 作为整体匹配。Match.Groups['open']。Success 将返回 false, 因为该组的所有捕获都被减去。
3 e# o( A. Z9 y, D. p7 s* }Matching Balanced Pairs 匹配平衡对
% j& q1 w; e9 P3 x$ H9 q" i
! @- x- W R5 n1 m9 U& U; j* c我们需要修改这个 regex, 如果我们想它匹配的 o's 和 c’s 平衡数。为了确保 regex 不匹配 ooccc, 它的 c's 大于 o's, 我们可以添加anchors定位点: ^(?'open'o)+(?'-open'c)+$。此 regex 经过与前一个相同的匹配过程。但之后 (?'-open'c)+ 无法匹配其第三次迭代, 引擎将达到 $, 而不是 regex 的末尾。此操作无法匹配。regex 引擎将回溯尝试不同的量词排列, 但它们都无法匹配。无法找到匹配项。7 D) W6 Z. f7 k5 K7 P# g8 k/ w; \
# l$ U- |7 M7 F, ~
但 ^(?'open'o)+(?'-open'c)+$ 仍然匹配 ooc。匹配的过程再次相同, 直到平衡组与第一个 c 匹配, 并将组 "open" 与第一个 o 作为其唯一捕获。限定符使引擎再次尝试平衡组。引擎再次发现, 减去组 "open" 捕获的东西。正则表达式进入平衡组, 使组 "open" 而不进行任何匹配。但是现在, c 无法匹配, 因为 regex 引擎已到达字符串的末尾。
9 S! Q$ A! b, h/ y
- I: ?# |. d. o kregex 引擎现在必须从平衡组中返回。当回溯平衡组时, PowerGREP 也回溯减法。由于第一个 o 的捕获是在进入平衡组时从 "open" 中减去的, 因此现在在退出平衡组时将恢复此捕获。重复组 (?'-open'c)+ 现在已减少为单个迭代。但量词是好的, 因为 + 它总是意味着 "一次或更多"。在字符串的末尾, regex 引擎在正则表达式中达到 $ 匹配。整个字符串 ooc 作为整体匹配返回。Match.Groups['open']。捕获将字符串中的第一个 o 作为 CaptureCollection 中的唯一项。这是因为, 在回溯后, 第二个 o 从组中减去, 但第一个 o 不是。4 s0 \6 x2 o. I9 J- U; F
) z. E1 U {5 _# o! ]+ n9 z/ e+ g为了确保正则表达式与 oc 和 oocc 匹配, 而不是 ooc, 我们需要检查当匹配进程到达 regex 末尾时, 组 "open" 没有任何捕获。我们可以设置条件的做到。(?(open)(?!))是一个条件, 用于检查组 "open" 是否匹配某项。在 PowerGREP 中, 有匹配的东西意味着仍然在堆栈上没有回溯或减去的捕获。如果该组已捕获了某些内容, 则会计算条件的 "if" 部分。在这种情况下, 是空的负预测先行(?!),此前预测中的空字符串始终匹配。因为前瞻性是负的, 这会导致预测先行总是失败。因此, 如果组捕获了某些东西, 则条件总是失败。如果组没有捕获任何内容, 则对条件的 "else" 部分进行计算。在这种情况下, 没有 "else" 部分。这意味着如果组没有捕获到某些东西, 则条件总是成功。这使 (?(open)(?!))一个正确的测试, 以验证组 "open" 没有捕获剩余。
! \' z- A5 s+ ^; C" v
7 |/ U* n: N' Z% t. D^(?'open'o)+(?'-open'c)+(?(open)(?!))$无法匹配 ooc。当 c 无法匹配时, 由于 regex 引擎已到达字符串的末尾, 因此引擎回溯出平衡组, 并将 "open" 保留为单个捕获。正则表达式引擎现在到达条件, 无法匹配。regex 引擎将回溯尝试不同的量词排列, 但它们都无法匹配。无法找到匹配项。
9 _# o) h9 B$ D4 B: E# p8 [5 ^7 O: N& r$ K7 j
^(?'open'o)+(?'-open'c)+(?(open)(?!))$匹配oocc。然后 (?'-open'c)+ 已匹配 cc, 正则表达式引擎不能第三次进入平衡组, 因为 "open" 没有捕获。引擎前进到条件。条件成功, 因为 "open" 没有剩余的捕获, 条件也没有 "else" 部分。现在 $ 匹配在字符串的末尾。
) H2 r$ L0 r, K6 @! w6 _* ^* n4 [" y$ b% h9 P5 s0 ]. i( e' ~
Matching Balanced Constructs 匹配平衡结构
* C8 z G0 M3 b2 d) E# r
8 x) D" b3 X. a) ^) @2 T* X^(?:(?'open'o)+(?'-open'c)+)+(?(open)(?!))$ 将捕获组和平衡组封装在一个捕获组中, 也会重复。此 regex 匹配任何类似 ooocooccocccoc 的字符串, 其中包含任意数量的完全平衡的 o 和 c, 任意数量的对按顺序排列, 嵌套到任意深度。平衡组确保 regex 永远不会匹配字符串中的任何点上的 c 的字符串, 它的左边有 o 的位置。结束时必须保持在重复组之外的条件, 确保 regex 永远不匹配具有大于 c 的字符串。
" K( w$ V2 x- C" C4 D+ B; K2 S^(?>(?'open'o)+(?'-open'c)+)+(?(open)(?!))$ 通过使用atomic group 原子组而不是捕获组来优化上一个 regex。当正则表达式找不到匹配时, 原子组也捕获, 消除了几乎所有的回溯, 这可以大大提高在使用大量 o 和 c 的长字符串时的性能, 但最终没有适当的平衡。原子组不会更改 regex 如何匹配具有平衡 o 和 c 的字符串。% x% V( s6 Z! R6 o
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 之后。 ; T0 K' G& ?) P- P3 q ^$ n
这是使用 PowerGREP 的平衡组或捕获组减法特征来匹配平衡结构的一般解决方案。可以用任何正则表达式替换 o, m 和 c,只要这些三中没有两个可以匹配相同的文本。" [0 [+ q7 a0 V. x- O* i
^[^()]*(?>(?>(?'open'\()[^()]*)+(?>(?'-open'\))[^()]*)+)+(?(open)(?!))$应用此技术匹配一个字符串, 其中所有括号都是完全平衡的。: W; O8 z. V& c6 ] @# F* w' o0 U
Backreferences To Subtracted Groups 引用减去组; [- d, S# {, m6 ~7 f. o6 n
0 e' H( E5 Q! S9 z8 A! w您可以将引用用于由平衡组减去其匹配项的组。引用匹配该组的最新匹配, 而不是回溯或减去。regex (?'x'[ab]){2}(?'-x')\k'x'匹配 aab, abb, baa, 或 bba。它不符合匹配。字符串的第一和第三个字母必须相同。2 u6 H: ]( P4 G+ z
- Q! m7 y# v0 z+ P. C3 t8 h
让我们看看(?'x'[ab]){2}(?'-x')\k'x'如何匹配 aba。第一次迭代 (?'x'[ab]) 捕获 a。第二个迭代捕获 b。现在 regex 引擎到达平衡组 (?'-x')。它检查组 "x" 是否匹配, 它有。引擎进入平衡组, 从组 "x" 的堆栈中减去匹配 b。平衡组中没有 regex 标记。它的匹配没有通过字符串前进。现在正则表达式引擎到达引用 \k'x'。组 "x" 的堆栈顶部的匹配是。字符串中的下一个字符也是引用匹配的 a。aba 被认为是一个整体的匹配。
8 V- z7 ]9 O: K6 B, E) ?4 ^. \9 @3 K ?
当您将此 regex 应用于 abb 时, 匹配的进程是相同的, 只是引用无法匹配字符串中的第二个 b。由于 regex 没有其他的排列, 正则表达式引擎可以尝试, 因此匹配尝试失败。
" ], n. s0 s9 k- Y2 N8 a3 l4 ~
4 V) X8 n7 U' g# f$ i UMatching Palindromes 匹配回文& U/ ~+ _- O, u! ~# r
4 \& Q; N! x K5 `% T
^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$匹配任何长度的回文。这个正则表达式充分利用了引用和捕获组减法。它还在上一节中使用一个空平衡组作为 regex。
0 y7 o6 S: k m |; L: s
. |; ` }4 q( ~: L* K让我们看看这个 regex 是如何匹配回文radar。^ 匹配在字符串的开头。然后 (?'letter'[a-z])+ 循环五次。组 "letter" 结束时, 其堆栈上有五匹配项:r, a, d, a, 和 r。正则表达式引擎现在位于字符串的末尾并且位于 [a-z]? 上。在 regex 中。它不匹配, 但这很好, 因为量词使它可选。引擎现在到达\k'letter'。组 "letter" 有 r 在其栈的顶部。这无法匹配字符串末尾后的 void。) e5 ]* V$ X* N
! j1 G/ _( s$ y7 X: V5 [! F. ~
regex 引擎回溯。(?'letter'[a-z])+ 减少到四次迭代, 在组 “letter" 的堆栈上留下 r, a, d, 和 a 。[a-z]?匹配 r。引用再次未能匹配的空白后, 字符串的末尾。引擎回溯, 迫使 [a-z]?放弃匹配现在 "letter" 有一个在其栈顶部。这将导致引用无法匹配 r。" [2 m9 w: ~' g T% L' v
# Q! L C7 k6 ]+ h1 G, A8 k9 _
更多回溯如下。(?'letter'[a-z])+将减少为三次迭代, 在组 “letter" 的堆栈顶部保留 d。引擎再继续使用 [a-z]?。它再次失败, 因为没有 d 引用匹配。
. R% Q* r& }7 W% w) e2 v. i, N, x7 R- Y% A3 T; h) Q3 {& ?
再次回溯, 将组 "letter" 的捕获栈还原为 r 和 a。现在形势变成[a-z]?匹配 d。引用匹配的是组 "letter" 中最近的匹配项, 而不是回溯。引擎现在到达空平衡组 (?'-letter')。此匹配, 因为组 "letter" 有一个要减去的匹配 a。
( |! j2 y: G' v$ }; n! j
9 G2 b2 H/ q6 V- x: Z7 a后向引用和均衡组内重复非捕获组,因此引擎试再一遍。后向引用匹配 r 和平衡组减去它从“letter”的叠加,使得捕获组没有任何匹配。重复一次,后向引用失败,因为该组“letter”对其堆栈没有匹配。这使得该组充当非捕获组。反向引用非捕获组始终在PowerGREP失败。4 A3 i$ }7 G0 p1 B$ L
+ ~/ X- A+ Z9 G
(?:\k'letter'(?'-letter'))+ 成功匹配了两个迭代。现在,条件(?(letter)(?!)) 成功是因为组 "letter" 没有匹配左边. 锚 $ 也匹配. 回文radar已匹配。 |
|