How to get the "longest possible" match with Python's RE module?
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
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