Re: How are regexen implemented in Emacs?

[<tomas@tuxteam.de>]

[-- Attachment #1: Type: text/plain, Size: 1267 bytes --]

On Thu, Dec 15, 2022 at 11:46:13AM -0500, Stefan Monnier via Users list for the GNU Emacs text editor wrote:
> > 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.

I stand corrected. Thanks.

> [ 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.  ]

Shudder :-)

> > 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.

Interestingly, Tcl seems to "do" Thompson (the article mentioned
upthread has Tcl as one of the examples, AFAIR), and they do back
references and non-greedy repetitions. There seems to be a way.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]