[Python-ideas] Regular expression algorithms

Greg Ewing greg.ewing at canterbury.ac.nz
Fri Apr 13 02:12:32 CEST 2007

Josiah Carlson wrote:
> a base Thompson NFA
> will move on to the next state as early as possible, making a* with
> Thompson analagous to a*? in the Python

Are you sure that's an inherent characteristic of
a Thompson NFA?

As I understood it, using a Thompson NFA is no
different from building an NFA and converting it
to a DFA, except it does the conversion lazily.

And when using a DFA, whether it matches greedily
or not depends on how you drive it. If you stop
as soon as you reach the first accepting state,
it's non-greedy; if you keep going until you
can't go any further, it's greedy.


More information about the Python-ideas mailing list