[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: How are regexen implemented in Emacs?
From: |
tomas |
Subject: |
Re: How are regexen implemented in Emacs? |
Date: |
Thu, 15 Dec 2022 18:56:15 +0100 |
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
signature.asc
Description: PGP signature
- Re: How are regexen implemented in Emacs?, (continued)
- Re: How are regexen implemented in Emacs?, tomas, 2022/12/12
- Re: How are regexen implemented in Emacs?, Marcin Borkowski, 2022/12/12
- Re: How are regexen implemented in Emacs?, Stefan Monnier, 2022/12/12
- Re: How are regexen implemented in Emacs?, Emanuel Berg, 2022/12/15
- Re: How are regexen implemented in Emacs?, tomas, 2022/12/15
- Re: How are regexen implemented in Emacs?, Stefan Monnier, 2022/12/15
- Re: How are regexen implemented in Emacs?,
tomas <=
- Re: How are regexen implemented in Emacs?, Emanuel Berg, 2022/12/17
- Re: How are regexen implemented in Emacs?, Emanuel Berg, 2022/12/15
- Re: How are regexen implemented in Emacs?, tomas, 2022/12/15
Re: How are regexen implemented in Emacs?, Emanuel Berg, 2022/12/15