Groups | Search | Server Info | Login | Register

Groups > comp.lang.awk > #9789

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

Show all headers | 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