|
楼主 |
发表于 2017-12-7 16:18:52
|
显示全部楼层
Matching Nested Constructs with Balancing Groups 将嵌套结构与平衡组匹配
* \( D& V2 m4 n9 B( r1 P: J+ I+ U2 C1 ]( z+ i; ^: E
PowerGREP 有一个特殊的功能, 称为平衡组。平衡组的主要目的是匹配平衡的构造或嵌套的构造, 它们从哪里得到它们的名字。该功能的一个技术上更准确的名称是捕获组减法。这就是它的真正功能。此功能最初是由. NET regex 风格发明的, 它不支持regular expression recursion正则表达式递归。
4 d, a* K0 K# C# Q$ q(?<capture-subtract>;regex)或(?'capture-subtract'regex)是平衡组的基本语法。它与命名的捕获组使用的语法相同, 但两个组名由减号分隔。该组的名称为 “capture 捕获"。当 "regex" 匹配时, 该匹配存储在 “capture 捕获" 的名称下。这与正常命名的捕获组没有什么不同。您可以省略组的名称。(?<-subtract>regex) 或 (?'-subtract'regex) 是捕获平衡组的语法。$ |. ], C1 m% V5 z+ m ]
名称 “subtract 减法" 必须是 regex 中另一个组的名称。当 regex 引擎进入平衡组时, 它从组 “subtract 减法" 中减去一个匹配项。如果组 “subtract 减法" 尚未匹配, 或者它的所有匹配项已被减去, 则平衡组将无法匹配。您可以将平衡组看作是一个条件, 它测试组 “subtract 减法", 将 "regex" 作为 "if" 部分, 而 "else" 部分总是无法匹配。不同之处在于, 平衡组具有从组 “subtract 减法" 中减去一个匹配项的附加特征, 而条件则使该组未触及。
) q+ w! V- \0 v V/ q! u4 zLooking Inside The Regex Engine查看 Regex 引擎的内部
" I$ E4 j5 X$ j% ]1 k
@* J2 D( ^2 M" b8 @7 K让我们应用 regex (?'open'o)+(?'-open'c)+ 去匹配 ooccc。(?'open'o) 匹配第一个 o 和存储,作为第一次捕获的组 "open". quantifier + 重复该组。 (?'open'o) 匹配第二个 o 并将其存储为第二个捕获。再次重复,(?'open'o) 无法匹配第一个 c. 但 + 满足两个重复。
( E5 H% C0 d! R' T7 _regex 引擎前进到 (?'-open'c)。在引擎可以进入这个平衡组之前, 它必须检查减去组 "open" 是否捕获了什么。它有。引擎进入组, 从 "open" 中减去最近的捕获。这使得组 "open", 第一 o 作为其唯一的捕获。现在在平衡组中, c 匹配 c。引擎退出平衡组。因为在连字符之前没有指定名称, 所以没有捕获任何东西。平衡组也有 + 作为它的量词。引擎再次发现, 减去组 "open" 捕获的东西。正则表达式进入平衡组, 使组 "打开" 而不进行任何匹配。c 与字符串中的第二个 c 匹配。
% o3 X$ k1 G& b" Z. F! E平衡组再次重复。但这一次, regex 引擎发现组 "open" 没有匹配项。平衡组无法匹配。但 + 是满足两个迭代。引擎已到达 regex 的末尾。它返回 oocc 作为整体匹配。Match.Groups['open']。Success 将返回 false, 因为该组的所有捕获都被减去。4 p# G" ?9 k f4 S& T; d% o
Matching Balanced Pairs 匹配平衡对
& [" E4 v9 e% P: k) `6 ^8 \) N+ R. `! I2 ^( g3 T
我们需要修改这个 regex, 如果我们想它匹配的 o's 和 c’s 平衡数。为了确保 regex 不匹配 ooccc, 它的 c's 大于 o's, 我们可以添加anchors定位点: ^(?'open'o)+(?'-open'c)+$。此 regex 经过与前一个相同的匹配过程。但之后 (?'-open'c)+ 无法匹配其第三次迭代, 引擎将达到 $, 而不是 regex 的末尾。此操作无法匹配。regex 引擎将回溯尝试不同的量词排列, 但它们都无法匹配。无法找到匹配项。- s0 _: E* r% e3 P+ W# h/ r) ]) o
6 n( m1 @7 f: d9 g" F' U但 ^(?'open'o)+(?'-open'c)+$ 仍然匹配 ooc。匹配的过程再次相同, 直到平衡组与第一个 c 匹配, 并将组 "open" 与第一个 o 作为其唯一捕获。限定符使引擎再次尝试平衡组。引擎再次发现, 减去组 "open" 捕获的东西。正则表达式进入平衡组, 使组 "open" 而不进行任何匹配。但是现在, c 无法匹配, 因为 regex 引擎已到达字符串的末尾。: c, f6 C. R1 p) H0 H/ |5 D2 s
7 a% y' A$ `% w. m% jregex 引擎现在必须从平衡组中返回。当回溯平衡组时, PowerGREP 也回溯减法。由于第一个 o 的捕获是在进入平衡组时从 "open" 中减去的, 因此现在在退出平衡组时将恢复此捕获。重复组 (?'-open'c)+ 现在已减少为单个迭代。但量词是好的, 因为 + 它总是意味着 "一次或更多"。在字符串的末尾, regex 引擎在正则表达式中达到 $ 匹配。整个字符串 ooc 作为整体匹配返回。Match.Groups['open']。捕获将字符串中的第一个 o 作为 CaptureCollection 中的唯一项。这是因为, 在回溯后, 第二个 o 从组中减去, 但第一个 o 不是。
8 P0 A( Q( x7 R# V* O R; ^( Y0 \$ M6 X: x% j. a5 t
为了确保正则表达式与 oc 和 oocc 匹配, 而不是 ooc, 我们需要检查当匹配进程到达 regex 末尾时, 组 "open" 没有任何捕获。我们可以设置条件的做到。(?(open)(?!))是一个条件, 用于检查组 "open" 是否匹配某项。在 PowerGREP 中, 有匹配的东西意味着仍然在堆栈上没有回溯或减去的捕获。如果该组已捕获了某些内容, 则会计算条件的 "if" 部分。在这种情况下, 是空的负预测先行(?!),此前预测中的空字符串始终匹配。因为前瞻性是负的, 这会导致预测先行总是失败。因此, 如果组捕获了某些东西, 则条件总是失败。如果组没有捕获任何内容, 则对条件的 "else" 部分进行计算。在这种情况下, 没有 "else" 部分。这意味着如果组没有捕获到某些东西, 则条件总是成功。这使 (?(open)(?!))一个正确的测试, 以验证组 "open" 没有捕获剩余。+ J, l3 G7 k/ Y |3 X' B
. V( o) L- R9 u5 g( T^(?'open'o)+(?'-open'c)+(?(open)(?!))$无法匹配 ooc。当 c 无法匹配时, 由于 regex 引擎已到达字符串的末尾, 因此引擎回溯出平衡组, 并将 "open" 保留为单个捕获。正则表达式引擎现在到达条件, 无法匹配。regex 引擎将回溯尝试不同的量词排列, 但它们都无法匹配。无法找到匹配项。
; t4 H- m6 `6 P2 u* a+ H# o9 @) k7 c6 z$ t8 b+ z
^(?'open'o)+(?'-open'c)+(?(open)(?!))$匹配oocc。然后 (?'-open'c)+ 已匹配 cc, 正则表达式引擎不能第三次进入平衡组, 因为 "open" 没有捕获。引擎前进到条件。条件成功, 因为 "open" 没有剩余的捕获, 条件也没有 "else" 部分。现在 $ 匹配在字符串的末尾。, ]5 H9 y9 H, l# `7 Y! O. o
7 b6 D/ h% {9 x4 hMatching Balanced Constructs 匹配平衡结构+ e5 G6 q! P3 |6 y# F
* Q6 [1 _0 H, y: p9 d
^(?:(?'open'o)+(?'-open'c)+)+(?(open)(?!))$ 将捕获组和平衡组封装在一个捕获组中, 也会重复。此 regex 匹配任何类似 ooocooccocccoc 的字符串, 其中包含任意数量的完全平衡的 o 和 c, 任意数量的对按顺序排列, 嵌套到任意深度。平衡组确保 regex 永远不会匹配字符串中的任何点上的 c 的字符串, 它的左边有 o 的位置。结束时必须保持在重复组之外的条件, 确保 regex 永远不匹配具有大于 c 的字符串。
- L7 k. L+ N$ {, o4 `, o {^(?>(?'open'o)+(?'-open'c)+)+(?(open)(?!))$ 通过使用atomic group 原子组而不是捕获组来优化上一个 regex。当正则表达式找不到匹配时, 原子组也捕获, 消除了几乎所有的回溯, 这可以大大提高在使用大量 o 和 c 的长字符串时的性能, 但最终没有适当的平衡。原子组不会更改 regex 如何匹配具有平衡 o 和 c 的字符串。7 J5 O: E, o( [9 t7 D) y
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 之后。 7 G8 G! J. u1 {4 q: m [) g* v& U
这是使用 PowerGREP 的平衡组或捕获组减法特征来匹配平衡结构的一般解决方案。可以用任何正则表达式替换 o, m 和 c,只要这些三中没有两个可以匹配相同的文本。
4 V7 d# U9 ]$ G8 Y, _0 F$ w^[^()]*(?>(?>(?'open'\()[^()]*)+(?>(?'-open'\))[^()]*)+)+(?(open)(?!))$应用此技术匹配一个字符串, 其中所有括号都是完全平衡的。! d. O% p1 ~& }7 c: P6 _
Backreferences To Subtracted Groups 引用减去组6 ~/ g) n) t/ B3 {& ~# n2 w
3 i3 E R( C! I, ?
您可以将引用用于由平衡组减去其匹配项的组。引用匹配该组的最新匹配, 而不是回溯或减去。regex (?'x'[ab]){2}(?'-x')\k'x'匹配 aab, abb, baa, 或 bba。它不符合匹配。字符串的第一和第三个字母必须相同。5 h7 x2 c5 _% | s9 r
; s2 ` w: Q- w# K
让我们看看(?'x'[ab]){2}(?'-x')\k'x'如何匹配 aba。第一次迭代 (?'x'[ab]) 捕获 a。第二个迭代捕获 b。现在 regex 引擎到达平衡组 (?'-x')。它检查组 "x" 是否匹配, 它有。引擎进入平衡组, 从组 "x" 的堆栈中减去匹配 b。平衡组中没有 regex 标记。它的匹配没有通过字符串前进。现在正则表达式引擎到达引用 \k'x'。组 "x" 的堆栈顶部的匹配是。字符串中的下一个字符也是引用匹配的 a。aba 被认为是一个整体的匹配。
$ t* Z* g5 d0 W* n6 F6 X8 |% R
0 u" A. q) p l' \' n当您将此 regex 应用于 abb 时, 匹配的进程是相同的, 只是引用无法匹配字符串中的第二个 b。由于 regex 没有其他的排列, 正则表达式引擎可以尝试, 因此匹配尝试失败。/ }, e* |. C7 d0 G% O4 U7 h; W& Y
a( r# w0 e$ ?. b; K, aMatching Palindromes 匹配回文
$ S) c" E, ?: V; r. u* N4 M
0 U. [9 U4 ~5 K8 e& H `^(?'letter'[a-z])+[a-z]?(?:\k'letter'(?'-letter'))+(?(letter)(?!))$匹配任何长度的回文。这个正则表达式充分利用了引用和捕获组减法。它还在上一节中使用一个空平衡组作为 regex。
. H; g+ X) N4 Z ], W' Z1 |* s- ~: m5 K, ^9 A4 n
让我们看看这个 regex 是如何匹配回文radar。^ 匹配在字符串的开头。然后 (?'letter'[a-z])+ 循环五次。组 "letter" 结束时, 其堆栈上有五匹配项:r, a, d, a, 和 r。正则表达式引擎现在位于字符串的末尾并且位于 [a-z]? 上。在 regex 中。它不匹配, 但这很好, 因为量词使它可选。引擎现在到达\k'letter'。组 "letter" 有 r 在其栈的顶部。这无法匹配字符串末尾后的 void。
) p, r* Y. N& C
( [! _- _- Z& S, Q9 n% }regex 引擎回溯。(?'letter'[a-z])+ 减少到四次迭代, 在组 “letter" 的堆栈上留下 r, a, d, 和 a 。[a-z]?匹配 r。引用再次未能匹配的空白后, 字符串的末尾。引擎回溯, 迫使 [a-z]?放弃匹配现在 "letter" 有一个在其栈顶部。这将导致引用无法匹配 r。
{: g P+ F, C2 ~& r, g6 _6 a7 C' ^7 ~; b7 }0 P" E" Y, A* |4 }
更多回溯如下。(?'letter'[a-z])+将减少为三次迭代, 在组 “letter" 的堆栈顶部保留 d。引擎再继续使用 [a-z]?。它再次失败, 因为没有 d 引用匹配。+ K( A0 E2 {/ x( v* ?9 B: l
& s1 Z& `* R. V" J8 o7 B再次回溯, 将组 "letter" 的捕获栈还原为 r 和 a。现在形势变成[a-z]?匹配 d。引用匹配的是组 "letter" 中最近的匹配项, 而不是回溯。引擎现在到达空平衡组 (?'-letter')。此匹配, 因为组 "letter" 有一个要减去的匹配 a。
: J0 O! |% v7 W8 a2 ?, x0 f. ~
. V# d# K q* q5 l后向引用和均衡组内重复非捕获组,因此引擎试再一遍。后向引用匹配 r 和平衡组减去它从“letter”的叠加,使得捕获组没有任何匹配。重复一次,后向引用失败,因为该组“letter”对其堆栈没有匹配。这使得该组充当非捕获组。反向引用非捕获组始终在PowerGREP失败。
* B# Z$ z5 t# L6 Z' B, K1 r! a6 L( }2 y; s& U
(?:\k'letter'(?'-letter'))+ 成功匹配了两个迭代。现在,条件(?(letter)(?!)) 成功是因为组 "letter" 没有匹配左边. 锚 $ 也匹配. 回文radar已匹配。 |
|