[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: How are regexen implemented in Emacs?
From: |
Stefan Monnier |
Subject: |
Re: How are regexen implemented in Emacs? |
Date: |
Thu, 15 Dec 2022 11:46:13 -0500 |
User-agent: |
Gnus/5.13 (Gnus v5.13) |
> 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
- Re: How are regexen implemented in Emacs?, (continued)
- Re: How are regexen implemented in Emacs?, Emanuel Berg, 2022/12/15
- Re: How are regexen implemented in Emacs?, Akib Azmain Turja, 2022/12/16
- Re: How are regexen implemented in Emacs?, Emanuel Berg, 2022/12/17
- Re: How are regexen implemented in Emacs?, Jean Louis, 2022/12/18
- Re: How are regexen implemented in Emacs?, Emanuel Berg, 2022/12/20
- 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 <=
- Re: How are regexen implemented in Emacs?, tomas, 2022/12/15
- 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