Capturing inner items using .net Regex Balanced Matching

Question

I have found the following resources on Balanced Matching for .net Regexes:

• http://weblogs.asp.net/whaggard/archive/2005/02/20/377025.aspx
• http://blogs.msdn.com/bclteam/archive/2005/03/15/396452.aspx
• http://msdn.microsoft.com/en-us/library/bs2twtah%28VS.85%29.aspx#BalancingGroupDefinitionExample

From what I have read in these, the following example should work:

This regex should find an "a" anywhere within an angle-bracket group, no matter how deep. It should match "<a>", "<<a>>", "<a<>>", "<<>a>", "<<><a>>", etc.

(?<=
    ^
    (
     (
      <(?<Depth>)
      |
      >(?<-Depth>)
     )
     [^<>]*?
    )+?
)
(?(Depth)a|(?!))

matching on the "a" in the string "<<>a>"

While it will work for strings "<a<>>" and "<<a>>", I can't get it to match an "a" that is following a ">".

According to the explanations I have read, the first two "<"s should increment Depth twice, then the first ">" should decrement it once. At this point, (?(Depth)a|(?!)) should perform the "yes" option, but the regex never even makes it here.

Consider the following regex, which makes no such check and still fails to match the string in question:

(?<=
    ^
    (
     (
      <(?<Depth>)
      |
      >(?<-Depth>)
     )
     [^<>]*?
    )+?
)
a

Am I missing something, or is the regex engine working incorrectly?

Answer 1

It's generally a safe assumption that classes in a library litterally used by millions do not have any major bugs :D

the below regex will match all the above version of <>a

var pattern =  "(" +
                       "((?'Open'<)[a]?)+" +
                       "((?'Close-Open'>)[a]?)+" +
                     ")*" +
                     "(?(Open)(?!))$";

Answer 2

You need to remember that a lookbehind only scans as far back as it has to in order to satisfy its embedded regex. The expression in your lookbehind is only required to match an angle bracket, so it only looks as far back as the latest one. If it's a left angle bracket, (?<Depth>) pushes an empty string onto the stack represented by that capture group. But if it's a right angle bracket...

It is worth mentioning that if no named group N exists when trying to pop (<-N>) then it will fail... *

In other words it's not the conditional expression -- (?(Depth)a|(?!)) -- that's making your regex fail (as you observed), it's the attempt to "decrement" the "counter". As far as I can tell, your regex is exactly equivalent to

(?<=<[^<>]*)a

So, to answer your question, .NET's balanced-construct matching is not broken. Byzantine yes, but broken, no. :D

Answer 3

Completely revised answer (first two comments were for a previous, incomplete answer):

I have figured out how to accomplish this in a way that I can "replace all" on the results.

string input = @"a<a<<a>>a<a>a>a<a>a";
Regex reg = new Regex(@"
    (?<=
     <
     [^<>]*
     (?(ReverseDepth)(?!))
     (?:
      (?:
       <(?<-ReverseDepth>)
       |
       >(?<ReverseDepth>)
      )
      [^<>]*
     )*
    )
    a
    ", RegexOptions.IgnorePatternWhitespace);
Console.WriteLine(reg.Replace(input, "b"));

This produces the following output:

a<b<<b>>b<b>b>a<b>a

I now realize that my question did not specify this, but I never actually cared to check whether or not the group ever closes fully, since the text I am going to apply this to is pre-validated xml. In order to match my answer to the question, though, and prevent the 'a' in "<a" from matching, the following regex can be used in place of the one I have provided here:

Regex reg = new Regex(@"
    (?<=
     <
     [^<>]*
     (?(ReverseDepth)(?!))
     (?:
      (?:
       <(?<-ReverseDepth>)
       |
       >(?<ReverseDepth>)
      )
      [^<>]*
     )*
    )
    a
    (?=
     (?:
      (?:
       <(?<Depth>)
       |
       >(?<-Depth>)
      )
      [^<>]*
     )*
     (?(Depth)(?!))
     [^<>]*
     >
    )
    ", RegexOptions.IgnorePatternWhitespace);

Answer 4

If you want to find every 'a' that's inside a balanced pair of angle brackets, I would suggest this approach:

Regex r = new Regex(@"
    <
      (?>
         [^<>a]+
       |
         (a)
       |
         <(?<N>)
       |
         >(?<-N>)
      )+
    (?(N)(?!))
    >
", RegexOptions.IgnorePatternWhitespace);
string target = @"012a<56a8<0a2<4a6a>>012a<56789a>23456a";
foreach (Match m in r.Matches(target))
{
  Console.WriteLine("{0}, {1}", m.Index, m.Value);
  foreach (Capture c in m.Groups[1].Captures)
  {
    Console.WriteLine("{0}, {1}", c.Index, c.Value);
  }
}

result:

9, <0a2<4a6a>>
11, a
15, a
17, a
24, <56789a>
30, a

Instead of mucking about with the conditional, it goes ahead and matches the whole bracket-delimited (sub)string, in the process capturing any a's it might contain. Unlike your approach, it can pluck any number of bracketed substrings out of a larger string, and any number of a's out of each substring.