Thomas Ploch wrote: > Fredrik Lundh wrote: > > Nick Craig-Wood wrote: > > > >> A regular expression matcher uses a state machine to match strings. > > > > unless it's the kind of regular expression matcher that doesn't use a > > state machine, like the one in Python. > > > > </F> > > > > How is the matching engine implemented then? > > I thought regular languages can be described by deterministic / > non-deterministic finite state machines. I am just curious ...
Regular expressions are described by N?DFAs, but Perl-compatible regular expressions (which pretty much every language implements now) are not true regular expressions. They are actually Turing complete, and thus have features that cannot be implemented in N?DFAs. -- http://mail.python.org/mailman/listinfo/python-list
