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!
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!