Match Nested Brackets with Regex: A new approach

My first blog post was a bit of a snoozefest, so I feel I ought to make this one a little shorter and more to the point. I'm going to show you how to do something with regular expressions that's long been thought impossible. Get excited.

The problem

You want to match a full outer group of arbitrarily nested parentheses with regex but you're using a flavour such as Java's java.util.regex that supports neither recursion nor balancing groups.

The solution

(?=\()(?:(?=.*?\((?!.*?\1)(.*\)(?!.*\2).*))(?=.*?\)(?!.*?\2)(.*)).)+?.*?(?=\1)[^(]*(?=\2$)

Proof: Java Regex or PCRE on regex101 (look at the full matches on the right)

Et voila; there you go. That right there matches a full group of nested parentheses from start to end. Two substrings per match are necessarily captured and saved; these are useless to you. Just focus on the results of the main match.

No, there is no limit on depth. No, there are no recursive constructs hidden in there. Just plain ol' lookarounds, with a splash of forward referencing. If your flavour does not support forward references (I'm looking at you, JavaScript), then I'm sorry. I really am. I wish I could help you, but I'm not a freakin' miracle worker.

That's great and all, but I want to match inner groups too!

OK, here's the deal. The reason we were able to match those outer groups is because they are non-overlapping. As soon as the matches we desire begin to overlap, we must tweak our strategy somewhat. We can still inspect the subject for correctly-balanced groups of parentheses. However, instead of outright matching them, we need to save them with a capturing group like so:

(?=\()(?=((?:(?=.*?\((?!.*?\2)(.*\)(?!.*\3).*))(?=.*?\)(?!.*?\3)(.*)).)+?.*?(?=\2)[^(]*(?=\3$))) 

Exactly the same as the previous expression, except I've wrapped the bulk of it in a lookahead to avoid consuming characters, added a capturing group, and tweaked the backreference indices so they play nice with their new friend. Now the expression matches at the position just before the next parenthetical group, and the substring of interest is saved as \1.

So... how the hell does this actually work?

I'm glad you asked. The general method is quite simple: iterate through characters one at a time while simultaneously matching the next occurrences of '(' and ')', capturing the rest of the string in each case so as to establish positions from which to resume searching in the next iteration. Let me break it down piece by piece:

Note	Component	Description
	(?=\()	Make sure '(' follows before doing any hard work.
	(?:	Start of group used to iterate through the string, so the following lookaheads match repeatedly.
Handle '('	(?=	This lookahead deals with finding the next '('.
	.*?\((?!.*?\1)	Match up until the next '(' that is not followed by \1. Below, you'll see that \1 is filled with the entire part of the string following the last '(' matched. So "(?!.*?\1)" ensures we don't match the same '(' again.
	(.*\)(?!.*\2).*)	Fill \1 with the rest of the string. At the same time, check that there is at least another occurrence of ')'. This is a PCRE band-aid used to overcome this bug.
	)
Handle ')'	(?=	This lookahead deals with finding the next ')'.
	.*?\)(?!.*?\2)	Match up until the next ')' that is not followed by \2. Like the earlier '(' match, this forces matching of a ')' that hasn't been matched before.
	(.*)	Fill \2 with the rest of the string. The above-mentioned bug is not applicable here, so this simple expression is sufficient.
	)
	.	Consume a single character so that the group can continue matching. It is safe to consume a character here because neither occurrence of the next '(' or ')' could possibly exist before the new matching point.
	)+?	Match as few times as possible until a balanced group has been found. This is validated by the following check.
Final validation	.*?(?=\1)	Match up to and including the last '(' found.
	[^(]*(?=\2$)	Then match up until the position where the last ')' was found, making sure we don't encounter another '(' along the way (which would imply an unbalanced group).

Conclusion

So, there you have it. A way to match balanced nested structures using forward references coupled with standard (extended) regex features - no recursion or balancing groups. It's not efficient, and it certainly isn't pretty, but it is possible. And it's never been done before. That, to me, is quite exciting.

If you share my excitement for things of this nature then I encourage you to follow this blog, as I have a few more pearls of regex wisdom to offer in good time. Also in the cards is a regex quiz adventure that will test your skills in a variety of interesting and challenging ways. So please do stay tuned.

I'd like to thank Me-me on Freenode for inspiring this discovery with a clever attempt at one of my #regex challenges. Thank you for being man enough to attempt them!

Bonus: Optimization!

Just for fun, I managed to improve the performance of this technique from "disgustingly, horrendously awful" to just "awful". Using the example in the proofs above:

Original (16,257 steps):

(?=\()(?:(?=.*?\((?!.*?\1)(.*\)(?!.*\2).*))(?=.*?\)(?!.*?\2)(.*)).)+?.*?(?=\1)[^(]*(?=\2$)

Optimized (4,205 steps):

(?=\()(?:(?=(?(1).*?(?=\1)).*?\((.*))(?=(?(2).*?(?=\2)).*?\)(.*)).)+?(?>.*?(?=\1))[^(]*?(?=\2$)

And just so you can get an idea of how poor this method truly is, here's how the conventional recursive method measures up:

Recursive (445 steps):

\((?:[^()]+|(?R))*+\)

A whole order of magnitude more efficient.

Lookahead Quantification: An utterly loopy trick

Sufficiently adventurous readers may have come across the technique of forward or nested references to do some tricky things with regex, such as non-recursively match a palindrome, match aⁿbⁿ, and even match an isomorphic pair of words. The technique works well in cases where you can consume one character at a time while simultaneously performing tests that call for simple examination of only the remainder of the subject at the next matching point. But what of problems that require greater visibility of the subject at each pivotal position? We don't have variable-length lookbehinds in PCRE; how, then, are we to perform feats of absurdity? I'll cut to the chase in a second, but first allow me to put to you a challenge.

The Challenge

This is an example of a regex task that is simply stated, appears easy at first glance, but is impossible to solve in the general case given PCRE's current functionality:

"Match a character that appears only once in the subject."

That's it. Just find and match a single character, and it can be any character as long as it makes but one appearance.

Matched case-sensitively, this sentence contains 12 such characters.

And this one contains 8.

How hard could it be to match any one of them, right? I'll give you a few minutes to shake your head, scoff, minimize this article, and attempt this challenge in your favourite regex environment. 

Welcome back. Were you close? Did you try to test for uniqueness using a negative lookahead, only to realize that everything to the left of the current matching point is entirely inaccessible? Or did you instead run into shortcomings while trying to recursively match sets of repeated characters? I feel your pain. No matter what trick one pulls out of the bag, the features of PCRE seem to fall just short of providing the means to solve this deceptively difficult problem.

The (Partial) Answer

And so, I would like to introduce the method of lookahead quantification: a method that paves the way for partial solutions to problems of this type. This is not a method you can assume will chime with your every requirement; it is a method that, should the stars align in your favour, you would be able to merely get away with. It relies on quantifying (a limited number of times) a group consisting solely of a positive lookahead assertion, containing accumulating nested references, in order to iterate through the subject without altering the matching point. An example to partially solve the problem at hand:

^(?:(?=(\1.|)(.))){1,850}?(?!.*\2.*\2)\1\K\2

See it in action at: https://regex101.com/r/T0gJWO/1

I say "partially" because it's clearly limited by the magic number "850", the reason for which I'll explain in a second. But for now let's go through the full expression. A description of what's happening can be summarized as follows:

"Examine one character at a time, without ever advancing the matching point from the start of the subject, checking to see if the current character doesn't occur twice (or more)."

^(?:            # Anchor to start. All checks must take place here for full visibility.
 (?=(\1.|)(.))  # Look ahead and either add a single character to \1, or initialize it to "". Then \2 becomes the next character to be tested.
){1,850}?       # The lazy '?', in essence, forces the engine to start checking characters for uniqueness from the beginning of the string. It therefore iterates as few times as possible until a character satisfying the remainder of the expression is found.
(?!.*\2.*\2)    # Test the current value of \2 for uniqueness in the whole subject.
\1\K\2          # If found, match up to \2 by first consuming \1, resetting the match with \K, and then matching \2.

First of all: why is the group necessary, ie. why do we not just quantify the lookahead? Because, dear reader, we are not allowed. Or, rather, no matter how we attempt to quantify a lookahead, it can only match at most once. This is understandable. In general, it is not expected that a zero-width assertion needs to match more than once, because it consumes no characters. Even though the case above is a perfectly sensible scenario for a hypothetical quantified lookahead, we must accept that such tactics are off-limits to us and proceed with resourcefulness by enclosing it in a non-capturing group.

After the first iteration of the group, \1 = "" and \2 = <the first character in the subject>. Because the group has been quantified with '?' to invoke laziness, the engine will relax at this point and move on to matching the rest of the expression. This is important. If you remove the '?' and make the match greedy, the engine will go through as many of the 850 iterations as possible to the point where \2 ends up being either the 850th character or the last character in the subject, whichever comes first. Only then will it move on to the rest of the expression and test \2 for uniqueness. If unsuccessful, the engine will not backtrack and try again with \2 as the previous character; because the group matched an empty string, it simply aborts. This is why the lazy quantifier is crucial, not to mention a more natural analogy of the conventional 'for' loops that are typically used to iterate through strings.

So, where does "850" come from, you ask? Well, you may verify that if you increase it - say, to "851" - regex101 will throw a compile error at you: "regular expression is too large". This is because the PCRE compiler handles range quantification by making copies of the quantified element. With a sufficiently large range, the total length of the copies will exceed the hard limit imposed by the compiler on the overall length of an expression (which, by default, is 64 kilobytes). It is possible to predict this magic number by calculation once you deduce the memory consumption of each of the subexpression's individual components, but I won't get into that in this article. If this technique interests you and you do use it for some practical purpose (intelligently, while heeding all of my implicit warnings), I recommend you try to discover these limits yourself using a simple binary search, knowing the upper limit is somewhere on the order of 1000s.

Can I make it less limited?

Not really. Well, sort of. If you wish to use this method for whatever reason but find that it is too limited for your particular purpose, you may be able to overcome this by applying additional slightly amended expressions to continue match attempts where you left off. For example, if the first expression I gave you only checks the first 850 characters for uniqueness, you can use a second expression to iterate through each character in the next portion of the subject:

^(?:(?=(\1.|.{850})(.))){1,779}?(?!.*\2.*\2)\1\K\2

Unfortunately, the inner expression has grown a little, so the new magic number is "779". This means that the earlier expression coupled with this one, used in succession where necessary, will allow you to test the first 1,629 characters of a string for uniqueness. If this is still not enough, then you can keep amending the expression and reapplying in a similar fashion to check the next however many characters, changing the magic numbers as appropriate. Or, y'know, you could forget all this nonsense and use your programming language to implement this in a much more efficient and maintainable manner. But.. where's the fun in that?

Where else can I use this method?

Now that you've seen and, with any luck, understood the earlier example, you may be wondering what other problems this method may lend itself to solving.

To speak broadly, any regex problem that seems impossible at first thought because it requires iteration and comparison of a variable number of substrings either in front of or, perish the thought, behind the current matching point could probably benefit from application of this method.

Note that you need not limit yourself to iterating over individual characters; any describable series of contiguous substrings is perfectly acceptable. Here is an example that loops through whole words in the subject:

Match the longest word in a string

\b(?!(?:(?=\S+((?(1)\1 \S+|)))){1,760}?(?:(?=\S++\1 (\2?+\S))\S)++\b)(\S+)

This time, it is in our best interests to wrap most of the expression in a negative lookahead. Why? Think about the difference between these two statements: "find a word such that all words ahead of it are no larger" vs. "find a word such that there does not exist a word ahead of it that's larger". Each of these describes a valid way to tackle the problem, and each lends itself to its own solution involving this loopy trick. If we choose to interpret it the first way, the result will be an expression that resembles the following:

\b(?:(?=\S+(\1 \S+|))(?!(?:(?=\S++\1 (\2?+\S))\S)++\b)){1,387}?(\S++)(?=\1$)

This is very similar in operation to the expression above, but the magic number "387" (which, by the way, is now a limit on a number of words not characters) is almost half of the other. By thinking about the problem slightly differently, we can move some of the logic from inside the non-capturing group, thereby increasing its permissible range.

Note to self: this method of cascading negation is useful and might be worth a blog post at some point in the future.

Match the character that occurs with the greatest frequency

(.)(?!(?:(?=((?(2)\2.)\1*+)(.))){1,680}?((?=\1).(?4)*?\3|(?=\3).(?4)*?\1|(?(?!\1|\3).)+)*+\3)

Getting a little crazier now. Once again, it is to our benefit to place the meat of the logic in a negative lookahead. Then for each character \3 following the first character \1, we recursively match character pairs in order to see which occurs with greater frequency. If \3 is more common than \1, then after eating through all the non-\3s, non-\1s, and \1+\3 pairs, we will be left with one or more \3s.

There is a lot happening in this expression, and I leave it as an exercise to you to determine what. Mainly because I am too lazy to write anymore.

In Closing

I hope you've enjoyed not fallen asleep reading the above article, and can now leave this page a little smarter than when you came in. This is my first post, so I'd love to hear any suggestions on how I can make this kind of material more interesting or otherwise improve its presentation.

Thank you for reading.