How to get the "longest possible" match with Python's RE module?

Bryan Olson fakeaddress at nowhere.org
Wed Sep 13 02:51:48 CEST 2006


Tim Peters wrote:

> [Bryan Olson]
>> Unfortunately, the stuff about NFA's is wrong. Friedl's awful
>> book
> 
> Strongly disagree: [...]

I know I'm disagreeing with a lot of smart people in panning
the book.

>> What Python uses is search-and-backtrack. Unfortunately such
>> engines don't have much theory behind them, and it's hard to
>> reason generally about what they do.
> 
> Yup X 3, and the last is precisely why Friedl's book is valuable for
> people using "NFA" implementations:  Friedl does a good job of
> explaining when and why you're likely to trigger atrocious runtime
> performance, and gives practical general techniques for avoiding those
> problems.  None of that has anything to do with CompSci regexps
> either, but is vital knowledge for people hoping to make happy
> non-trivial use of Python/Perl/etc regexps.

I read the first edition, minus some engine-specific stuff.
General techniques are what I want, and I didn't see them in the
book. He had things to do and not do, but it didn't add up to
building (ir-)regular expressions with reliably tractable
behavior.


-- 
--Bryan



More information about the Python-list mailing list