More on matchmarks in Regex Powertoy

The previous post mentioned Regex Powertoy matchmarks as a way to capture all settings to reproduce a bug. Of course, a matchmark can also be used to save useful or interesting regular expressions (and example target text) as web bookmarks, such as on del.icio.us and its ilk.

For example, the Perl 'perlre' regular expressions documentation contains the following warning:

WARNING: particularly complicated regular expressions can take exponential time to solve because of the immense number of possible ways they can use backtracking to try match. For example, without internal optimizations done by the regular expression engine, this will take a painfully long time to run:

     'aaaaaaaaaaaa' =~ /((a{0,5}){0,5})*[c]/

Here's a matchmark representing that operation, with Regex Powertoy animation turned on:

     'aaaaaaaaaaaa' =~ /((a{0,5}){0,5})*[c]/

You can watch the red probe cursor -- indicating which character of the target input text is currently being tested against the regex -- bounce around, banging against the end of the text and backtracking, for hours. Turning off animation speeds things up considerably, but the ultimate rejection of any matches still takes tens of seconds if not minutes: the final tally is 18,124,859 probes to test the match.

Technorati Tags: regex, powertoy, regexp, reference, tips

«»