c# - .NET 真的使用 NFA 作为正则表达式引擎吗？

Question

文章Details of Regular Expression Behavior从 MSDN 说，.NET 开发者决定对正则表达式使用传统的 NFA 引擎，因为它比 POSIX NFA 更快，但我不清楚，为什么那么这种模式的工作速度呈指数级下降？

var regex = new Regex("(a|aa)*b");
var b = regex.IsMatch("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac");

这个简单的模式匹配需要 30 多分钟才能执行。但是如果 .NET 使用传统的 NFA，则可以模拟它并在最坏的情况下在 O(M*N) 时间内找到匹配，其中 M 是模式长度，N 是文本长度，这肯定在这种情况下是不正确的。

文章也解释了回溯是执行慢的原因，但是我还有一些问题找不到答案

1. 什么是回溯？是否像这样再次使用已经匹配的模式 (a|b)c/1？
2. 传统的NFA是否支持回溯，如果不支持需要做哪些修改？
3. 如果 NFA 支持它，但需要更慢的算法来模拟，为什么 .NET 不能检查模式中是否存在回溯，并且使用一种算法，如果不存在则使用另一种？

Answer 1

您可以将正则表达式编译为 NFA 或 DFA，尽管从 NFA 计算出的 DFA 可能大得不切实际。您可以在有或没有回溯的情况下匹配 NFA，尽管在没有回溯的情况下工作的方案通常会对正则表达式语言施加更多限制，并且在有许多可能的匹配项时找到匹配项。

您的示例很慢，因为匹配器必须经常决定是匹配 a 还是 aa，以及是否尝试匹配最后的 b。回溯就像运行递归函数一样，在每个步骤中，递归调用自身以寻找每种可能性 - 递归匹配 a，如果失败则递归匹配 aa，如果失败则递归匹配 b。

Microsoft 似乎在说他们的那种回溯比 POSIX 更快，因为 POSIX 回溯将安排递归搜索，直到确定找到可能的最长匹配为止。 Microsoft 版本仍在回溯，但它不会进行额外的检查，直到可以保证找到最长的可能匹配为止。 http://msdn.microsoft.com/en-us/library/dsy130b4%28v=vs.110%29.aspx 中有一个示例.

没有回溯的正则表达式匹配器可以通过一次接受输入一个字符来工作，并跟踪当时 NFA 中的哪些状态是事件的——可能有很多这样的状态。很难用反向引用来完成这项工作，因为那样的话，NFA 的状态不能仅仅通过状态是否存在来描述。