regex - 是否可以编写一个使用分组但不进行回溯的正则表达式引擎？

Question

我正在尝试详细了解重做，并且或多或少清楚为什么字符串(a|a)+x失败aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab，但我很好奇是否有任何不使用分组的示例？我读到 Thompson 引擎不容易受到这个问题的影响，因为它不进行回溯，但据我了解，这意味着它也不能进行分组。是否可以在没有回溯的情况下进行分组以及随之而来的漏洞？

标签： regexdenial-of-service

Answer 1

好的，所以根据 Wiktor Stribiżew 的说法，答案是 Re2。无需回溯即可支持分组。Re2 不支持反向引用之类的东西，这是完全可以理解的，至少我怀疑很多引擎都准备好这样的模式/(a)(a|\1)+b/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaax")。他们写道，也因此不完全支持环视。所以这些引擎有限制，但它们已经足够好了。许多人试图用单一模式解决所有问题，这助长了这个问题。