Go 正则表达式中没有灾难性的回溯吗？

Question

今天在 regex101.com 上测试这个正则表达式 ^([a-z0-9]+(-)*)*([a-z0-9])$ 时，我在这个字符串上测试它时遇到“灾难性回溯”错误：带有风味的PHP：啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊带有风味的 Python：啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊使用风味 ECMAScript，这个较长的字符串会出现“可能是灾难性回溯的迹象”的超时啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊带有风味的Java 8超时字符串啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊但是风味 Go 没有给出更长的此类字符串的错误或超时事件。相反，它显示no match (0.0ms)那么当我的正则表达式在 Go 中使用时，我可以忽略该错误/警告吗？我也对此原因感兴趣，但以上是我的关键问题。

Answer 1

是的，在 Go 中使用正则表达式时，可以安全地忽略灾难性回溯警告。

Go 对正则表达式使用 RE2 算法，而 RE2 不使用回溯，因此 Go 不会出现问题。 https://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times有更多关于正则表达式匹配的替代实现的信息。Go (RE2) 对输入字符串长度和正则表达式字符串长度具有线性性能：O(mn)。

然而，其他使用回溯的语言/库可能具有指数运行时间，具体取决于正则表达式和输入字符串。regex101.com 显示了针对输入字符串运行正则表达式的步骤数，您可以看到步数随着您增加正则表达式的字符串长度（(a*)*$如aaaaaaaaaaaaaaaaX. regex101.com 上的调试器可以一次显示模式匹配执行的一个步骤，因此您可以看到回溯如何处理呈指数增长的备选方案。

@sln提供了我原来的正则表达式的替代方法，它消除了指数回溯。将输入字符串之前/之后的正则表达式简化为aand需要大约 300,000 步（每增加一倍），但 需要大约 100 步XaaaaaaaaaaaaaaaaZ ^(a+X*)*a$a^(aX*)*a$

我不知道将易受攻击的正则表达式映射到安全正则表达式的任何一般方法 - 除非@sln 关心提供服务;-)

原始正则表达式的目的是检查输入字符串是否仅包含 [a-z0-9] 并且-以 [a-z0-9] 开头和结尾。 a, a-b, ab--c, a-b--aa---bbb, ...