Bug in regex?

[freewave@…]

void RegexTest() {

char *pszMessage = "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15"; static const boost::regex e("^{(.*?,){11}P"); boost::cmatch result; if (boost::regex_search(pszMessage, result, e)) {}

cout << result.str() << "$" << result.length() << endl;

} else

cout << "result empty" << endl;

}

An exception raised by the boost regex-engine when testing with the code above in visual c++ 6.0

[John Maddock]

This is expected behaviour: Perl-style regular expression matching is an NP-complete problem in general, and any expression that looks like: (something*)* may experience these issues eventually. Boost.Regex tries to prevent "runaway" expressions by throwing an exception if the complexity of the match looks like it's going to exceed a certain maximum - and this is what's happening here.

Using a more precise expression would fix this - for example

"([^,]*?,){11}P"

or

"(?>.*?,){11}P"

would fix this - and improve performance a lot into the bargain.

HTH, John Maddock.