Article Details of Regular Expression Behavior from MSDN says, that .NET devs decide to use for regular expressions traditional NFA engine, because it is faster than POSIX NFA, but it is not clear to me, why does this pattern works exponentially slow then?
var regex = new Regex("(a|aa)*b");
var b = regex.IsMatch("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac");
This simple pattern matching take more than 30 minute to execute. But if .NET uses traditional NFA, it is possible to simulate it and find match in O(M*N) time in the worst case, where M is pattern length and N is text length, which surely is not true in this case.
Article also explains that backtracking is the reason of slow execution, but I still have some questions that can't find answers
- What is backtracking? is it only using already matched pattern again like this
(a|b)c/1? - Does traditional NFA support backtracking, if no what modification does it need?
- If NFA supports it, but need more slower algorithm to simulate, why .NET can't check if backtracking exist in the pattern, and use one algorithm and use another if it doesn't?