How to find a match within another match in a regular expression

Suppose you have an HTML file in which various passages are marked as bold with <b> tags. You want to find all numbers marked as bold. If some bold text contains multiple numbers, you want to match all of them separately. For example, when processing the string 1 2 3 4 5 6 7, you want to find four matches: 2, 5, 6, and 7.

Here are sample solutions for the various flavors:

C#

StringCollection resultList = new StringCollection();
Regex outerRegex = new Regex("<b>(.*?)</b>", RegexOptions.Singleline);
Regex innerRegex = new Regex(@"\d+");
// Find the first section
Match outerMatch = outerRegex.Match(subjectString);
while (outerMatch.Success) {
    // Get the matches within the section
    Match innerMatch = innerRegex.Match(outerMatch.Groups[1].Value);
    while (innerMatch.Success) {
        resultList.Add(innerMatch.Value);
        innerMatch = innerMatch.NextMatch();
    }
    // Find the next section
    outerMatch = outerMatch.NextMatch();
}

VB.NET

Dim ResultList = New StringCollection
Dim OuterRegex As New Regex("<b>(.*?)</b>", RegexOptions.Singleline)
Dim InnerRegex As New Regex("\d+")
'Find the first section
Dim OuterMatch = OuterRegex.Match(SubjectString)
While OuterMatch.Success
    'Get the matches within the section
    Dim InnerMatch = InnerRegex.Match(OuterMatch.Groups(1).Value)
    While InnerMatch.Success
        ResultList.Add(InnerMatch.Value)
        InnerMatch = InnerMatch.NextMatch
    End While
    OuterMatch = OuterMatch.NextMatch
End While

Java

Iterating using two matchers is easy, and works with Java 4 and later:

List<String> resultList = new ArrayList<String>();
Pattern outerRegex = Pattern.compile("<b>(.*?)</b>", Pattern.DOTALL);
Pattern innerRegex = Pattern.compile("\\d+");
Matcher outerMatcher = outerRegex.matcher(subjectString);
while (outerMatcher.find()) {
    Matcher innerMatcher = innerRegex.matcher(outerMatcher.group());
    while (innerMatcher.find()) {
        resultList.add(innerMatcher.group());
    }
}

The following code is more efficient (because innerMatcher is created only once), but requires Java 5 or later:

List<String> resultList = new ArrayList<String>();
Pattern outerRegex = Pattern.compile("<b>(.*?)</b>", Pattern.DOTALL);
Pattern innerRegex = Pattern.compile("\\d+");
Matcher outerMatcher = outerRegex.matcher(subjectString);
Matcher innerMatcher = innerRegex.matcher(subjectString);
while (outerMatcher.find()) {
    innerMatcher.region(outerMatcher.start(), outerMatcher.end());
    while (innerMatcher.find()) {
        resultList.add(innerMatcher.group());
    }
}

Javascript

var result = [];
var outerRegex = /<b>([\s\S]*?)<\/b>/g;
var innerRegex = /\d+/g;
var outerMatch = null;
while (outerMatch = outerRegex.exec(subject)) {
    if (outerMatch.index == outerRegex.lastIndex)
        outerRegex.lastIndex++;
    var innerSubject = subject.substr(outerMatch.index,
                                      outerMatch[0].length);
    var innerMatch = null;
    while (innerMatch = innerRegex.exec(innerSubject)) {
        if (innerMatch.index == innerRegex.lastIndex)
            innerRegex.lastIndex++;
        result.push(innerMatch[0]);
    }
}

PHP

$list = array();
preg_match_all('%<b>(.*?)</b>%s', $subject, $outermatches,
               PREG_PATTERN_ORDER);
for ($i = 0; $i < count($outermatches[0]); $i++) {
    if (preg_match_all('/\d+/', $outermatches[0][$i], $innermatches,
                       PREG_PATTERN_ORDER)) {
        $list = array_merge($list, $innermatches[0]);
    }
}

Perl

while ($subject =~ m!<b>(.*?)</b>!gs) {
    push(@list, ({:content:}amp;amp; =~ m/\d+/g));
}

This only works if the inner regular exp​ression (\d+, in this example) doesn't have any capturing groups, so use noncapturing groups instead.

Python

list = []
innerre = re.compile(r"\d+")
for outermatch in re.finditer("(?s)<b>(.*?)</b>", subject):
    list.extend(innerre.findall(outermatch.group(1)))

Ruby

list = []
subject.scan(/<b>(.*?)<\/b>/m) {|outergroups|
    list += outergroups[0].scan(/\d+/)
}

Regular exp​ressions are well-suited for tokenizing input, but they are not well-suited for parsing input. Tokenizing means to identify different parts of a string, such as numbers, words, symbols, tags, comments, etc. It involves scanning the text from left to right, trying different alternatives and quantities of characters to be matched. Regular exp​ressions handle this very well.

Parsing means to process the relationship between those tokens. For example, in a programming language, combinations of such tokens form statements, functions, classes, namespaces, etc. Keeping track of the meaning of the tokens within the larger context of the input is best left to procedural code. In particular, regular exp​ressions cannot keep track of nonlinear context, such as nested constructs.

Trying to find one kind of token within another kind of token is a task that people commonly try to tackle with regular exp​ressions. A pair of HTML bold tags is easily matched with the regular exp​ression <b>(.*?)</b>. A number is even more easily matched with the regex \d+. But if you try to combine these into a single regex, you’ll end up with something rather different:

\d+(?=(?:(?!<b>).)*</b>)

Regex options: None
Regex flavors: .NET, Java, Javascript, PCRE, Perl, Python, Ruby

Though the regular exp​ression just shown is a solution to the problem posed by this recipe, it is hardly intuitive. Even a regular exp​ression expert will have to carefully scrutinize the regex to determine what it does, or perhaps resort to a tool to highlight the matches. And this is the combination of just two simple regexes.

A better solution is to keep the two regular exp​ressions as they are and use procedural code to combine them. The resulting code, while a bit longer, is much easier to understand and maintain, and creating simple code is the reason for using regular expressions in the first place. A regex such as <b>(.*?)</b> is easy to understand by anyone with a modicum of regex experience, and quickly does what would otherwise take many more lines of code that are harder to maintain.

Though the solutions presented here are most complex, they’re very straightforward. Two regular exp​ressions are used. The "outer" regular exp​ression matches the HTML bold tags and the text between them, and the text in between is captured by the first capturing group.

The second regular exp​ression matches a digit and is applied only to the part of the subject string matched by the first capturing group of the outer regular exp​ression.

There are two ways to restrict the inner regular exp​ressions to the text matched by (a capturing group of) the outer regular exp​ressions. Some languages provide a function that allows the regular exp​ression to be applied to part of a string. That can save an extra string copy if the match function doesn’t automatically fill a structure with the text matched by the capturing groups. We can always simply retrieve the substring matched by the capturing group and apply the inner regex to that.

Either way, using two regular exp​ressions together in a loop will be faster than using the one regular exp​ression with its nested lookahead groups. The latter requires the regex engine to do a whole lot of backtracking. On large files, using just one regex will be much slower, as it needs to determine the section boundaries (HTML bold tags) for each number in the subject string, including numbers that are not between <b> tags. The solution that uses two regular exp​ressions doesn't even begin to look for numbers until it has found the section boundaries, which it does in linear time.