Re: Preliminary version of new regex matcher for gawk now available

Path	csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From	Ben Bacarisse <ben@bsb.me.uk>
Newsgroups	comp.lang.awk
Subject	Re: Preliminary version of new regex matcher for gawk now available
Date	Fri, 26 Jul 2024 10:57:43 +0100
Organization	A noiseless patient Spider
Lines	17
Message-ID	<87h6cc5vc8.fsf@bsb.me.uk> (permalink)
References	<66a21e7e$0$710$14726298@news.sunsite.dk> <v7tf29$2984r$1@dont-email.me>
MIME-Version	1.0
Content-Type	text/plain
Injection-Date	Fri, 26 Jul 2024 11:57:43 +0200 (CEST)
Injection-Info	dont-email.me; posting-host="2f0e8b887f2208b0f5219b8ab3d9a2ba"; logging-data="2931602"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+6KW05qHqhswk+CJPBfKqV/nCl7QytUAs="
User-Agent	Gnus/5.13 (Gnus v5.13)
Cancel-Lock	sha1:5yuF6Scb1jOkqpAnLRy9QU2nhJM= sha1:lgIBAoCRFoEK9rp/cO386Vl+6AM=
X-BSB-Auth	1.c4a4489c72c318f7f649.20240726105743BST.87h6cc5vc8.fsf@bsb.me.uk
Xref	csiph.com comp.lang.awk:9789

Show key headers only | View raw

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:

> Well, I skimmed through the txt file on Mike's git page to learn
> about the algorithm; especially the algorithm and its complexity
> is of interest to me. The document was not quite clear about that
> (or at least made me doubt) beyond the general and typical O(N*M)
> characteristics. One thing I was astonished about was why there's
> a non-deterministic automaton model used (NFSM can be transformed
> into Deterministic FSM); isn't the non-deterministic tree-search
> (where every branch is traversed breadth-first) sub-optimal?

The non-deterministic to deterministic transformation yields (at worst)
an exponential number of states.  Keeping track of a set of states is
usually the preferred method.

-- 
Ben.

Back to comp.lang.awk | Previous | Next — Previous in thread | Find similar

Thread

Preliminary version of new regex matcher for gawk now available arnold@skeeve.com (Aharon Robbins) - 2024-07-25 09:44 +0000
  Re: Preliminary version of new regex matcher for gawk now available Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-07-25 14:05 +0200
    Re: Preliminary version of new regex matcher for gawk now available arnold@skeeve.com (Aharon Robbins) - 2024-07-26 07:31 +0000
      C++20??? (Was: Preliminary version of new regex matcher for gawk now available) gazelle@shell.xmission.com (Kenny McCormack) - 2024-07-27 16:36 +0000
        Re: C++20??? (Was: Preliminary version of new regex matcher for gawk now available) Luuk <luuk@invalid.lan> - 2024-08-10 15:42 +0200
          Re: C++20??? (Was: Preliminary version of new regex matcher for gawk now available) gazelle@shell.xmission.com (Kenny McCormack) - 2024-08-10 13:50 +0000
    Re: Preliminary version of new regex matcher for gawk now available Ben Bacarisse <ben@bsb.me.uk> - 2024-07-26 10:57 +0100

csiph-web