为什么正则表达式 ^(?:a+)+$ 会导致灾难性的回溯？

Question

我正在学习编译器原理（其正则表达式始终可以执行 中的任务O(n)）和通用正则表达式。我注意到某些正则表达式可能会出现灾难性的回溯，这似乎与理论相冲突。

理论上，^(?:a+)+$可以转化为 NFA，如下所示：

通过算法，可以将其转化为具有精确状态为 的 DFA a+。但在现实生活中，这会导致例如灾难性的回溯aaaaaab。为什么正则表达式不能编译成高效的DFA？或者一般来说，由组成的正则表达式|,*,+,(?:)应该相当于某种非回溯的DFA，顶多O(n^2)是从每一个可能的字符开始，每次都失败，但是为什么会像指数复杂度呢？编译器原理上的正则表达式和程序中使用的一般正则表达式有什么区别吗？

Answer 1

有 DFA 正则表达式引擎和回溯正则表达式引擎。一般来说，一种语言或库要么决定它需要只能由回溯引擎支持的功能（例如反向引用或任意环视），在这种情况下它会编译为那种结构 \xe2\x80\x94 或者它决定它可以不需要这些功能并编译为 DFA。

\n

尽管可以逐个模式地选择匹配策略，或者应用两种策略（在将剩余部分提供给回溯引擎之前使用 DFA 清除明确的不匹配项），但由于复杂性的原因，这几乎从未完成过。

\n

因此，DFA 引擎无法“灾难性地回溯”您的模式。回溯的人可能会也可能不会。它完全有可能分析模式并认识到^(?:a+)+$只有能匹配才能匹配a$，并尽早使匹配失败，但这是一个停止问题打地鼠的游戏：你覆盖了多少个案例，你写了多少代码，为了可能使暴力匹配短路，你需要花费多少预处理工作？

\n