News for hackers. Stuff that matters.
Re:ECMAScript regular expressions are getting better (2017) by burntsushi on Wednesday November 28, 2018 @02:31PM (#18554822)
> Well the Rust docs say "all searches execute in linear time with respect to the size of the regular expression and search text."

Yeah, that's ambiguous phrasing on my part. I meant that it was linear time with respect to both the size of the regex and the search text.

> Their engine compiles to a DFA, not an NFA or PikeVM; I suppose this is the basis for their claim.

No, it doesn't. rust/regex uses some combination of the Pike VM, (bounded) backtracking and a lazy DFA. It will compile a DFA ahead of time in some cases where Aho-Corasick can be used.

> Rust compiles to a DFA that supports capture groups.

No, it uses a lazy DFA to answer "where does it match," but it still must use either the Pike VM or the bounded backtracker to resolve capture groups.

> My question is whether capture groups ruin the linearity of the DFA matching.

Yeah I think I would probably look at Tagged DFAs to answer this. You'll want to check out recent papers that cite Laurikari's work, since I think there have been some developments!

There are no comments on this comment yet.