变长回顾后断言中的平衡组

Question

TL;DR: 在.NET中使用捕获(特别是平衡组)时，位于回顾后面的内容发生了变化，尽管它不应该有任何影响。这是.NET回顾后面的什么问题，导致预期行为被破坏了吗？

我试图回答另一个问题此处链接未提供并借此机会玩一下.NET的平衡组。然而，我无法让它们在可变长度回顾后面正常工作。

首先，请注意，我并不打算以这种特定的解决方案来实现生产力。这更多是出于学术原因，因为我感觉在可变长度回顾后面发生了一些事情，我还没有意识到。当我实际上需要使用此类方法来解决问题时，了解这一点可能会派上用场。

考虑以下输入：

~(a b (c) d (e f (g) h) i) j (k (l (m) n) p) q

目标是匹配所有在括号内的字母，这些括号前面有一个波浪线~，无论多深（所以从a到i的所有内容）。我的尝试是在回顾中检查正确的位置，以便我可以在单个调用Matches中获取所有字母。这是我的模式：

(?<=~[(](?:[^()]*|(?<Depth>[(])|(?<-Depth>[)]))*)[a-z]

在lookbehind中，我试图找到一个~(，然后使用命名组堆栈Depth来计算多余的开括号。只要在~(中打开的括号从未关闭，lookbehind就应该匹配。如果到达了那个关闭括号，(?<-Depth>...)无法从堆栈中弹出任何内容，lookbehind就会失败（也就是说，对于所有字母从j开始）。不幸的是，这并不起作用。相反，我匹配了a、b、c、e、f、g和m。因此，只有这些：

~(a b (c) _ (e f (g) _) _) _ (_ (_ (m) _) _) _

这似乎意味着当我关闭一个单独的括号时，回溯无法匹配任何内容，除非我回到之前到达的最高嵌套级别。

好的，这可能只是我的正则表达式有些奇怪，或者我没有正确理解平衡组。但是我尝试了一下不使用回溯。我为每个字母创建了一个字符串，如下所示：

~(z b (c) d (e f (x) y) g) h (i (j (k) l) m) n
~(a z (c) d (e f (x) y) g) h (i (j (k) l) m) n
~(a b (z) d (e f (x) y) g) h (i (j (k) l) m) n
....
~(a b (c) d (e f (x) y) g) h (i (j (k) l) z) n
~(a b (c) d (e f (x) y) g) h (i (j (k) l) m) z

我使用这个模式对每个元素进行了操作：

~[(](?:[^()]*|(?<Depth>[(])|(?<-Depth>[)]))*z

根据要求，所有 a 和 i 之间的字母都可以用 z 替换，所有替换后的情况都匹配成功，但在此之后的所有情况都匹配失败。

那么，这个（可变长度）回顾机制做了什么破坏了这种平衡组的使用呢？我试图整晚研究这个问题（并找到了像this one这样的页面），但我找不到一个在回顾机制中使用这个的例子。

如果有人能够链接一些深入的信息，让我了解.NET正则表达式引擎如何处理.NET特定的内部功能，我也会很高兴。我发现this amazing article，但它似乎没有涉及（可变长度）回顾机制等内容。

- Martin Ender

---

请参阅使用.NET正则表达式平衡组的乐趣。 - ΩmegaMan

@OmegaMan，谢谢你，但我也发现了（实际上那就是我基于代码的页面）。不幸的是，这一个在后顾之中也没有使用任何平衡组。 - Martin Ender

@Les 我可以轻松地使用类似于无回溯断言模式的方法，在单个匹配中捕获从 a 到 i 的所有字母。重点不在于找到一个正确匹配的算法，而是要找到当我将平衡组和后置断言结合使用时出现奇怪行为的解释。 - Martin Ender

我看了一下，成功地减少了这种现象：类似 (?<=(?<A>.)(?<-A>.)) 的东西永远不会匹配。我期望它能够匹配第二个位置之后的任何位置。然而，(?<A>)(?<=(?<A>.)(?<-A>.))(?<-A>) 可以匹配这些位置（尽管在你的情况下类似的方法不起作用）。我要注意的是 Mono 表现完全相同：http://ideone.com/rvmQhr - 对于你的模式 http://ideone.com/Hjb3jn - 所以可能有一些规范解释了这一点。 - Kobi

@m.buettner - 是的，这就是它所做的。又一个空捕获。 - Kobi

Answer 1

我想我明白了。 首先，正如我在其中一条评论中提到的那样，(?<=(?<A>.)(?<-A>.))从来不匹配。 但是后来我想，那么(?<=(?<-A>.)(?<A>.))呢？它确实匹配！ 那么(?<=(?<A>.)(?<A>.))呢？对于"12"进行匹配时，A捕获到了"1"，如果我们查看Captures集合，它是{"2", "1"} - 先是两个，然后是一个 - 它被颠倒了。 所以，在lookbehind内部，.net是从右到左进行匹配和捕获的。 现在，我们如何使其从左到右进行捕获呢？这其实很简单 - 我们可以通过使用lookahead来欺骗引擎。

(?<=(?=(?<A>.)(?<A>.))..)

应用于您的原始模式，我想到的最简单的选择是：

(?<=
    ~[(]
    (?=
        (?:
            [^()]
            |
            (?<Depth>[(])
            |
            (?<-Depth>[)])
        )*
        (?<=(\k<Prefix>))   # Make sure we matched until the current position
    )
    (?<Prefix>.*)           # This is captured BEFORE getting to the lookahead
)
[a-z]

这里的挑战是现在平衡部分可能出现在任何位置，所以我们让它一直延伸到当前位置（类似于\G或\Z在这里会很有用，但我不认为.net有这个功能）。

很有可能这种行为在某处有记录，我会尝试查找一下。

这里还有另一种方法。思路很简单 - .net想从右到左匹配？没问题！就这样：
（提示：从底部开始阅读 - 这就是.net的做法）

(?<=
    (?(Depth)(?!))  # 4. Finally, make sure there are no extra closed parentheses.
    ~\(
    (?>                     # (non backtracking)
        [^()]               # 3. Allow any other character
        |
        \( (?<-Depth>)?     # 2. When seeing an open paren, decreace depth.
                            #    Also allow excess parentheses: '~((((((a' is OK.
        |
        (?<Depth>  \) )     # 1. When seeing a closed paren, add to depth.
    )*
)
\w                          # Match your letter

- Kobi

---

哇，这太棒了。你看，我注意到捕获的顺序是相反的，但我假设这在某种程度上是由于组的堆栈式特性（当然，这完全是无稽之谈；但从右到左的匹配根本没有想到）。明天我会试着玩一下，看看这个方法有多可靠，是否可以找到其他解决方法。非常感谢你抽出时间来调查这个问题！ - Martin Ender

刚刚发现了这个链接，其中提到了“驱动.NET后顾模式的从右到左模式…”等内容。还有这本书也证实了这一点。 - Martin Ender

自然地，这在Mono上失败了：http://ideone.com/GuCNVM。我的大多数模式在Mono上都失败了。 - Kobi

啊，你最后那个模式真的很棒。我也在尝试做类似的事情，但我没有想到 (?<-Depth)? 这个技巧。这真的很聪明！ - Martin Ender

@m.buettner - 谢谢！\( (?<-Depth>)? 真的与 (?<-Depth>\\()|\\() 相同，没有太特别的东西:)。我花了大约20分钟的时间找寻匹配顺序（以及 Regex 的一般性规则），但无法找到确切的文档。感谢您提出这个有趣的问题！ - Kobi

Answer 2

我认为问题在于数据，而不是模式。数据有“Post”项需要匹配，例如：

(a b ( c ) d e f )

其中d、e和f需要匹配。更加“平衡”的数据应该是

(a b (c)(d)(e)(f))

因此，在这个示例数据中，我采取了一种需要在大括号后进行后置匹配的方法：

~(a b (c) d (e f (g) h) i) j k

其中j和k应该被忽略......我的模式失败并捕获它们。

有趣的是，我对捕获组进行了命名，以找出它们在哪里出现，而j和k在捕获三中出现。我给你留下了一个尝试，看看你是否能改进它。

(~                         # Anchor to a Tilde
 (                         # Note that \x28 is ( and \x29 is )      
  (                          # --- PRE ---
     (?<Paren>\x28)+          # Push on a match into Paren
     ((?<Char1>[^\x28\x29])(?:\s?))*
   )+                         # Represents Sub Group 1
  (                           #---- Closing
   ((?<Char2>[^\x28\x29])(?:\s?))*
   (?<-Paren>\x29)+           # Pop off a match from Paren

  )+  
  (
     ((?<Char3>[^\x28\x29])(?:\s?))*   # Post match possibilities
  )+

 )+
(?(Paren)(?!))    # Stop after there are not parenthesis    
)

这里是使用我自己创建的工具拆分出来的匹配结果（也许有一天我会公开发布）。请注意，˽表示匹配到的空格。

Match #0
               [0]:  ~(a˽b˽(c)˽d˽(e˽f˽(g)˽h)˽i)˽j˽k
       ["1"] → [1]:  ~(a˽b˽(c)˽d˽(e˽f˽(g)˽h)˽i)˽j˽k
       →1 Captures:  ~(a˽b˽(c)˽d˽(e˽f˽(g)˽h)˽i)˽j˽k
       ["2"] → [2]:  (e˽f˽(g)˽h)˽i)˽j˽k
       →2 Captures:  (a˽b˽(c)˽d˽, (e˽f˽(g)˽h)˽i)˽j˽k
       ["3"] → [3]:  (g
       →3 Captures:  (a˽b˽, (c, (e˽f˽, (g
       ["4"] → [4]:  g
       →4 Captures:  a˽, b˽, c, e˽, f˽, g
       ["5"] → [5]:  ˽i)
       →5 Captures:  ), ), ˽h), ˽i)
       ["6"] → [6]:  i
       →6 Captures:  ˽, h, ˽, i
       ["7"] → [7]:  
       →7 Captures:  ˽d˽, , ˽j˽k, 
       ["8"] → [8]:  k
       →8 Captures:  ˽, d˽, ˽, j˽, k
   ["Paren"] → [9]:  
  ["Char1"] → [10]:  g
      →10 Captures:  a, b, c, e, f, g
  ["Char2"] → [11]:  i
      →11 Captures:  ˽, h, ˽, i
  ["Char3"] → [12]:  k
      →12 Captures:  ˽, d, ˽, j, k

- ΩmegaMan

---

这是一个非常有用的工具！然而，我认为你之所以会匹配到 j 和 k 是因为你在 Parens 栈上计数第一个开括号 (，所以删除最后一个开括号是完全有效的。而在我的模式中，我不计算 ~( 中的 (，所以我永远无法关闭它。(如果我不使用回顾后发断言，而只将其作为普通模式使用，像你一样，我的平衡似乎也能正常工作)。无论如何，感谢你提出使用命名捕获组来查找更多匹配的想法！我会研究一下的！ - Martin Ender

@m.buettner，这是我昨晚做的最后一件事情，所以帖子没有我可以做到的那么简洁，但你的问题足够引人入胜，值得我发帖回复。 - ΩmegaMan

我真的很感谢你的贡献；）。当我们分析更多的捕获时，如果有任何结果，我会让你知道。 - Martin Ender

@m.buettner，如果想要更多人关注这个问题，请考虑在MSDN Regex论坛上发布。 - ΩmegaMan