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

Paul Rubin http
Tue Sep 12 11:50:46 CEST 2006


"Licheng Fang" <fanglicheng at gmail.com> writes:
> I think if the backtrack is carried out in an exaustive way, we may say
> the engine trys every possibility on the NFA, though it's not an NFA
> itself.

The backtracking engine really can recognize languages that are not
describable by classical regexps, by using backreferences, negation,
etc.  But exactly what it can do is nowhere near as well-understood as
what classical regexps can do.

I seem to remember that the fully general problem of recognizing
regexps with negation is very hard, so the backtracking matcher either
has to reject some strings it should really match, or else it has to
bog down horribly with certain kinds of patterns.



More information about the Python-list mailing list