User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; sv-SE; rv:1.9.2.28)
            Gecko/20120306 Thunderbird/3.1.20
MIME-Version: 1.0
References: <CACKZBPX-udskZ1JNVDwBzgFOfS8wMr3cBw9JwMbZwuLodfS5=A@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Message-ID:  <5268D3D0.1050209@residenset.net>
Date:         Thu, 24 Oct 2013 10:01:20 +0200
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
Sender: Mailing list for the LaTeX3 project <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
From: =?ISO-8859-1?Q?Lars_Hellstr=F6m?= <Lars.Hellstrom@RESIDENSET.NET>
Subject: Re: l3regex feature request + a question about the implementation
To: LATEX-L@LISTSERV.UNI-HEIDELBERG.DE
In-Reply-To:  <CACKZBPX-udskZ1JNVDwBzgFOfS8wMr3cBw9JwMbZwuLodfS5=A@mail.gmail.com>
Precedence: list
Content-Transfer-Encoding: quoted-printable
Envelope-To: <rainer.schoepf@GMX.NET>
Status: R

Michiel Helvensteijn skrev 2013-10-24 02.12:
> Secondly, an implementation question (which might lead to a
> discussion): You're now running a regex as a NFA (Nondeterministic
> Finite Automaton), keeping track of all active branches while matching
> against an input. Is there a particular reason you're not translating
> it into a DFA (Deterministic Finite Automaton) during the compilation
> phase, i.e., applying the powerset construction?

Not knowing the details of the implementation, I anyway hazard the guess=20
that this is because running the NFA tends to be faster in practice. Sure=
,=20
when executing an NFA you need to keep track of all active branches for t=
his=20
particular input, but in carrying out the powerset construction you need =
to=20
consider any possible set of active branches for any possible input! You=20
need to have run the match against a rather long string before NFA matchi=
ng=20
work starts to catch up with the work required by the powerset constructi=
on.=20
So unless you plan to run a single regexp against a very large amount of=20
text, it's in all likelyhood not worth it.

Even in cases such as yours, where you actually do mean to run the same=20
regexp against lots of text, it's not entirely clear that it's worth it. =
The=20
reason is that once the machinery is there, it is easy to underestimate h=
ow=20
large the NFA is, and the exponential computational complexity of the=20
powerset construction really penalises even small NFA size increases. At =
the=20
same time, it's easy to overestimate the amount of text a matching on=20
average gets applied to.

An optimal approach for your setting would perhaps be a lazy powerset=20
construction: don't carry it out for a particular state in the DFA until =
you=20
actually reach that state, but then record the result; matching typically=
=20
doesn't reach all the states of the DFA, since you don't match against=20
arbitrary data. This, however, assumes that you have some efficient metho=
d=20
of memoising the results from lazy computations. (I suppose a family of=20
control sequence names could do the trick.)

Lars Hellstr=F6m