Re: How are regexen implemented in Emacs?

[Stefan Monnier via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org>]

> Nitpick: The Emacs regexp engine is a FA based one, but a DFA,
> not a NFA (the famous Thompson NFA).

No, it's definitely not DFA because it uses a stack to implement
the backtracking.

It's usually considered to be an NFA that's processed via backtracking
rather than via "parallel execution" as "Thompson's NFA" does.
[ For Haskeller's out there, it's a bit like the difference between the
  Cont monad and the List monad with the added twist that "Thompson's
  NFA" replaces the List monad with a "Set monad", which is what changes
  its complexity.  ]

> NFAs seem to be quite the beast, judging by how few implementations
> are out there. I don't even know how easy it is to implement, e.g.
> capture or (gasp!) back references,

It's not hard to implement, no.
At least not until you consider things like *? and backreferences.


        Stefan