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

Question

我正在学习编译器原理（其正则表达式总是可以完成

O(n)

中的任务）和通用正则表达式。我注意到某些正则表达式可能会出现灾难性的回溯，这似乎与理论相冲突。

理论上，

^(?:a+)+$

可以变成NFA，如：

并且通过算法，它可以变成一个具有精确状态为

a+

的DFA。但在现实生活中，这会导致灾难性的回溯，例如

aaaaaab

。为什么正则表达式不能编译成高效的DFA？或者一般来说，一个由

|,*,+,(?:)

组成的正则表达式应该相当于某种非回溯的DFA，如果我们从每一个可能的字符开始，每次都失败的话，最多就是

O(n^2)

，但为什么会像指数复杂度呢？编译器原理上的正则表达式和程序中使用的一般正则表达式有什么区别吗？

Answer 1

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

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

因此，DFA 引擎无法“灾难性地回溯”您的模式。回溯的人可能会也可能不会。它完全有可能分析模式并认识到

^(?:a+)+$

只能在

a$

可以匹配的情况下才能匹配，并提前失败匹配，但这是一个停止问题打地鼠的游戏：你覆盖了多少种情况，为了也许短路暴力匹配，你写了多少代码，以及你花了多少预处理工作？