Re: What is regular about regular expressions nowadays?

From: Kent Paul Dolan (
Date: 01/16/04

Date: Fri, 16 Jan 2004 07:22:54 +0000 (UTC)

"Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> wrote:

> I would guess that this is not true, since the algorithm writer has no idea
> what possible regular expressions may be used. ie: it is rare that
> language/api designers would use an exponential time algorithm and not at
> least mention this in the docs.

Michael, don't try to think, you'll injure yourself; put me in your
killfile and skip the pain.

>From "man perlre":

               Consider how the
               pattern above detects no-match on
               "((()aaaaaaaaaaaaaaaaaa" in several seconds, but
               that each extra letter doubles this time. This
               exponential performance will make it appear that
               your program has hung.

Looks like a "warning in the docs" about "exponential whosis" to me,
but rather than checking, you needed to pull an answer, let's be nice,
"out of the air".

No, I will not indulge in another interminable debate about how you
were right all along; I think for not having read that for a decade,
and being a total space-case, I did rather well at remembering it.

You would have done rather well remembering that I usually do, and
checking your facts before spouting off. You were early on your five
month "making a fool of yourself trying to put down Kent" cycle, by
almost five months to the day; was that yesterday, or the day before
when you last did this?

Clues, they're not just for smart people any more.


Posted via Mailgate.ORG Server - http://www.Mailgate.ORG