Somehow it seems a bit odd to argue that comparison with perl, python and
ruby and pcre is irrelevant. True, they are slow, but regexp matching is
supposed to be one of their strengths (esp of perl). And most people think
of them as being only maybe 10 or 1000 times slower than C, precisely when
the computation is dominated by library calls such as regular expression
matching, not 1e6 times slower than C. Of course, the point is that the
algorithm is at issue, not the language.
Admittedly, it seems like pretty weird regular expressions are needed in
order to trigger this exponential behavior. But then again, taking a minute
to match a 29 character string with a 29 character regular expression does
seem pretty excessive...