为何该正则表达式会导致VC++程序出现“冻结”现象？

Let's break down why your regex is causing the program to hang—this is almost certainly catastrophic backtracking, a common issue with overly flexible regex patterns that forces the engine to explore an exponential number of match possibilities when a full match fails.

The Root of the Problem #

Looking at your regex, here are the key culprits:

• Overuse of non-greedy wildcards (.*?): You have multiple .*? segments alternating with capture groups. Every time the engine hits a point where a capture group doesn't match, it has to backtrack—letting the previous .*? consume one more character, then rechecking the group. With 10+ such segments, the number of possible combinations explodes exponentially, tying up the CPU indefinitely.
• Vague capture group patterns: Groups like (?:[a-z][a-z0-9_]*) are broad, and when combined with the flexible .*?, the engine has to test countless ways to split the string between wildcards and these groups. For example, if the input doesn't have a digit in the expected position, the engine will keep trying to shift where .*? stops and the group starts, over and over.
• VC++/Boost regex engine behavior: While Boost's regex is robust, it doesn't always handle extreme backtracking scenarios as efficiently as some other engines. When faced with this kind of pattern, it can get stuck in a loop of trying every possible split instead of bailing out early.

Fixes to Try #

Here are actionable steps to fix the freeze:

1. Replace .*? with specific character ranges: Instead of matching any character, define what can't be in the segment between groups. For example, if a group should only contain lowercase letters, use [^a-z]* instead of .*? to skip non-letter characters without unnecessary backtracking.
2. Use atomic groups ((?>...)): Wrap capture groups in atomic groups to prevent the engine from backtracking into them once they've matched. For example, change (?:[a-z][a-z]+) to (?>[a-z]{2,})—this tells the engine that once it's matched 2+ lowercase letters, it won't unmatch them to try a different split with the preceding .*?.
3. Use possessive quantifiers: Add a + to quantifiers like + or * (e.g., [a-z]++ instead of [a-z]+) to make them "possessive"—the engine won't give up characters it's matched, eliminating backtracking for that segment.
4. Simplify and test incrementally: Build your regex step by step. Start with the first few groups, test them with sample inputs, and add more only when you're sure the current pattern works without hanging. This helps isolate which part of the regex is causing the backtracking.

Example Optimization #

For instance, your first few groups:

.*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z]+))

Could be rewritten to avoid unnecessary backtracking:

[^a-z]*([a-z]{2,})[^a-z]*([a-z]{2,})

This is more specific and tells the engine exactly what to skip between the letter groups, cutting down on backtracking possibilities.

内容的提问来源于stack exchange，提问作者cyberbot