I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is that the simple parts of the regex (like .*.*) should still be matched in linear time no matter whether the backreferences match immediately or go full exponential.

Thompson's NFA algorithm seems to be a very promising base algorithm as it can match a regex of size $m$ to a string of size $n$ with a worst-case time complexity $O(mn)$ and a worst case space complexity $O(m)$.

It could be easily modified to support capturing parentheses by embedding in the active states the set of captured substrings that lead to the current state. When a given state is reachable from two path, some rules is used to decide which set of substrings is kept (e.g. left-most longest). Correct me if I'm wrong, I don't think this method change the worst-case time complexity. However, the worst-case memory usage goes to $O(m^2)$ instead of $O(m)$ since each active state has to know at least one set of substrings for all the previous capturing parentheses.

Backreferences are where I'm stuck. I know a worst-case exponential time is unavoidable (unless P = NP). But the only solution I could think of takes an exponential amount of memory. The idea would be to take the algorithm above and keep all the combinations of matched substrings so that future backreferences could pick the ones that match.

I feel like there would be a way to make an algorithm that would save the regex engine state (which states of the NFA were active their associated data) when an active state exits a backreferenced capturing parentheses. So that we commit to the first match, and if later the backreference fail, it backtracks to the saved state and try the next match for that pair of parentheses.

The issue with that idea is that it doesn't allow to have some preference when several substrings could match. For instance we might want to choose the longest match when a greedy operator is used.

Any idea how this could be done? Maybe there is already a known solution that didn't come up in my research.

Two notes:

I found a paper that propose an algorithm that either is wrong or that I didn't understand.

There's the Henry Spencer's hybrid regex engine that manage to mix Thompson's NFA (sometime called a DFA engine) with some backtracking (sometime called NFA engine). The only documentation I could find about it is posgres' README for a high level view, and Russ Cox on comp.compilers who explain that submatch extraction has an $O(n^4)$ worst-case. And I still have no information about how backreferences are supported or how they interact with the simple parts of the regex.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.