Re: Extending regexes

["Daniel Shahaf" <d.s@daniel.shahaf.name>]

Peter Stephenson wrote on Mon, 04 Jul 2022 19:41 +00:00:
>> On 04 July 2022 at 20:15 Bart Schaefer <schaefer@brasslantern.com> wrote:
>> On Mon, Jul 4, 2022 at 6:53 AM Peter Stephenson
>> <p.w.stephenson@ntlworld.com> wrote:>
>> > > On 04 July 2022 at 13:03 Sebastian Gniazdowski <sgniazdowski@gmail.com> wrote:
>> > > Zsh has extensions to regular regexes - the ~ and ^ negations.
>>
>> PWS correct me if I go too far astray, but (^Y) is internally (*~Y)
>> and (X~Y) is implemented by first matching (X) and then removing
>> anything that matches (Y) ... which is where the regular-ness goes
>> astray.  My formal training on this is more than a little rusty, but I
>> believe this means chaining together two finite-state machines rather
>> than building a single one.

"X and not Y" isn't chaining; it's a Cartesian product.  Essentially one
walks both the X machine and the "not Y" machine simultaneously and
accepts iff both of them accept.

Chaining machines would create a non-deterministic machine that matches
the concatenation of the input machines' languages.

Cheers,

Daniel
(backlogged, so, replying out of order)

> That is basically how they're implemented. We have a sort of internal
> scratchpad that allows us to backtrack over the exclusions as a nested
> state of the main pattern match. You're entitled to say 'ick' at this
> point.
>
> pws