Re: Interesting paper on regex NFA matching

In article 24-01-003, John R Levine <johnl@taugh.com> wrote:
>The easiest way to implement regular expressions is to turn them into
>NFAs, but that has well known problems that if you feed hostile input
>to the NFAs, they can take exponential time and it's a way to DDoS the
>server. If you translate the NFA to a DFA it runs in linear time, but
>if the regex is ambiguous, as many are, the DFA may match something
>different from the NFA.


NFAs won't take exponential time if implemented carefully,
though they may be superlinear. Still, we're talking quadratic,
not exponential.


Backtracking implementations can take exponential time, but
those aren't all NFAs.


Converting an NFA to a DFA could be exponential, however.


https://swtch.com/~rsc/regexp/regexp1.html


>This paper on the Arxiv preprint server proposes some rather complex
>tweaks to NFA regex matching to fix many performance issues while giving
>the same answers as before.
>
>https://arxiv.org/abs/2401.12639


If I'm reading the abstract right, they modify a backtracking
implementation so that they can efficiently match some extended
regex's. Note however, that such so-called "extended" regexs
are not really regular expressions in the formal sense; that is,
they do not describe members of the regular languages, but
rather languages beyond those expressible as a DFA. Regardless
this work is interesting, since AFAIK the speedup for this
class of regex to linear time is novel. Thanks for passing it
on.


- Dan C.

Return to the comp.compilers page.
Search the comp.compilers archives again.