How to handle nested brackets and parentheses

Date Created
Date Modified

When Not Nested

Suppose you’re writing a blog post in Markdown and need to process the text using regexp in a Ruby script.

How do you match only the link portions from the following post?

## Links

 - [Link 1](https://example.com/link1)

 - [Link 2](https://example.com/link2)

 - [Link 3](https://example.com/link3)

One of the simplest way is below:

/\[[^\]]+\]\([^\)\s]+\)/

If we parse it from the beginning, it can be broken down into the following elements:

  1. opening bracket

  2. a string excluding the closing bracket

  3. closing bracket

  4. opening parenthesis

  5. a string excluding the closing parenthesis and whitespace characters

  6. closing parenthesis

regexp

Furthermore, you can create a capture group by adding parentheses to the title and link portions.

/\[([^\]]+)\]\(([^\)\s]+)\)/

From this pattern, you can extract the title and URL using the special variable $1 and $2.

Simple is best. In most situations, this kind of pattern is sufficient. Except for a few annoying sites…

When Nested

The pattern above does not expect for the appearance of a “closing bracket” within the title.

However, in reality, there are quite a few situations where a “closing bracket” appears in a title1.

## Links

 - [Link [1]](https://example.com/link1)

 - [Link [2][Part 1]](https://example.com/link2(2))

 - [Link [3][Part 2[Ongoing]]](https://example.com/link3((3)))

As someone who uses regexp to process Markdown, it’s extremely annoying, but there are no patterns that cannot be matched by regular expressions.

Subexpression Calls

Ruby’s regular expressions have a feature called subexpression calls that allows for recursive expressions not found in standard regular expressions. Using this, you can match nested parentheses. Since the expression becomes complex, I’ve broken it up with line breaks.

(?<brackets>
    \[
        (?: [^\[\]]+ | \g<brackets> )*
    \]
)
(?<parentheses>
    \(
        (?: [^\(\)]+ | \g<parentheses> )*
    \)
)

Using the notation \g<name>, regexp attempts to match the subpattern named “name”. Additionally, the notation (?: pat ) creates a non-capturing group, allowing text to be matched as a single unit. I’ve also applied the same pattern for parentheses appear within the URL, just as titles.

You might think this is the solution, but unfortunately, this pattern contains a fatal mistake. Because the termination condition for the recursive processing is insufficient, infinite backtracking (repeated match attempts) occurs. This happens because the process continues to check whether the subpattern matches, even if it fails to match within the “non-capturing group”.

To stop backtracking, you must include a termination condition within the recursive processing that says, “If it doesn’t match, just give up”.

Atomic Grouping

Ruby regexp include a feature called atomic grouping designed to prevent backtracking. If a match is found within an atomic group but the subsequent expression fails to match, the entire match for that group is rolled back — in other words, the behavior is “If it doesn’t match this group, give it up”.

By placing the title and link parts into separate atomic groups, you can achieve more stable matching.

(?<title>
    \[
        (?>
            (?: [^\[\]]+ | \g<title> )*
        )
    \]
)
(?<link>
    \(
        (?>
            (?: [^\(\)]+ | \g<link> )*
        )
    \)
)

Since the recursive call itself is self-contained, this pattern can handle multiple or deeply nested calls without any issues. If you simply need to extract links, this is the best pattern to use.

Since regular expressions can be made as complex as you like, it’s important to keep them readable to the user.

There are likely other ways to write this, but if you don’t keep it simple stupid, it will become something that beyond what humans can understand.

参考

  1. Actually, the brackets and parentheses may not always be closed, but since they wouldn’t be processed correctly as Markdown in that case, I won’t cover that case in this article.↩︎

License Information

badge

How to handle nested brackets and parentheses is licensed under a Creative Commons [Attribution 4.0 International] License.