Re: How are regexen implemented in Emacs?

[tomas]

On Mon, Dec 12, 2022 at 08:09:42PM +0100, Marcin Borkowski wrote:
> 
> On 2022-12-12, at 19:16, Stefan Monnier via Users list for the GNU Emacs text 
> editor <help-gnu-emacs@gnu.org> wrote:
> 
> >> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
> >> and started to wonder if the hints there mean that Emacs has a "naive",
> >> backtracking regex engine or a FA-based one?
> >
> > Naive!
> 
> And what are the reasons?  Out of curiosity: would implementing
> a FA-based one be a very big undertaking?  (And no, I won't do it, if
> only because I don't know C.)

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

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,

Cheers
-- 
t

signature.asc
Description: PGP signature