non-terminating regex match

[Maurizio Vitale]

Marc 'BlackJack' Rintsch <bj_666 at gmx.net> writes:

> On Wed, 02 Apr 2008 16:01:59 +0000, Maurizio Vitale wrote:
>
>> And yes, I'm a total beginner when it comes to Python, but it seems
>> very strange to me that a regex match on a finite length string
>> doesn't terminate
>
> It does terminate, you just don't wait long enough.  Try it with fewer
> characters and then increase the identifier character by character and
> watch the time of the runs grow exponentially.
>

Ok. Now, my assumption was that re.compile would produce a DFA (or NFA)
and the match would then being linear in the size of the string.

Apparently this is not the case, so is there anything that can be done
to the regex itself to make sure that whatever re.compile produces is
more efficient?

Thanks,

        Maurizio