为什么回溯会成为一个陷阱

回溯可以由可选的量词或交替构造引起，因为正则表达式引擎将尝试探索每条路径。如果你对 aaaaaaaaaaaaaa 运行正则表达式 a+b 没有匹配，引擎会很快找到它。

但是如果你将正则表达式更改为 (aa*)+b，组合的数量将会快速增长，并且大多数（非优化的）引擎将尝试探索所有路径，并将花费一个永恒的时间来尝试查找匹配或抛出超时异常。这被称为灾难性的回溯。

当然，(aa*)+b 似乎是一个新手错误，但它在这里说明了这一点，有时候你会遇到同样的问题，但模式更复杂。

一个更极端的灾难性回溯发生在正则表达式（你可能在这里和这里之前看到过 ），这需要指数时间才能发现一个包含 xs 的字符串而没有别的东西（例如 xxxxxxxxxxxxxxxxxxxx）与之匹配。

怎么避免呢？

尽可能具体，尽可能减少可能的路径。请注意，一些正则表达式匹配器不容易回溯，例如 awk 或 grep 中包含的那些，因为它们基于 Thompson NFA 。