为什么不创建一个反向引用？

Question

我知道在正则表达式的括号开始处放置?:可以防止它创建一个反向引用，从而提高速度。我的问题是，为什么要这样做？速度的增加足以值得考虑吗？在什么情况下，它会很重要，以至于每次都要小心地跳过不使用反向引用？另一个缺点是它使正则表达式更难以阅读、编辑和更新（如果您最终想要使用反向引用）。因此，总之，为什么要费心地不创建反向引用？

- Explosion Pills

---

就像编程中的任何事情一样，对于一个小集合来说，速度从来都不值得担心。如果你在几兆字节的文本上运行这个正则表达式，那么差异将是很大的。 - Travis Webb

@Travis，一些实现不良的正则表达式引擎会进行指数回溯，在即使是小输入上也可能非常缓慢。我在将一些Perl移植到Python时遇到了这个问题。Python已经修复了其re模块的许多问题，但是无论如何，您往往会看到与正则表达式边角情况相关的故障模式可能是O(2 ** n)最坏情况。 - Mike Samuel

@Mike 我听说过糟糕的回溯实现，但是你是如何达到O(2^n)的？其中n =？ - Travis Webb

Answer 1

我认为你可能混淆了像\1这样的反向引用和捕获组(...)。

反向引用通过使语言变得非正则，防止进行各种优化。

捕获组使正则表达式引擎做更多的工作以记住组的起始和结束位置，但不像反向引用那么糟糕。

http://www.regular-expressions.info/brackets.html详细解释了捕获组和反向引用。

编辑：

关于反向引用使正则表达式变得非正则，考虑以下匹配 lua 注释的正则表达式：

/^--(?:\[(=*)\[[\s\S]*?(?:\]\1\]|$)|[^\r\n]*)/

所以--[[...]]是注释，--[=[...]=]也是注释，--[==[...]==]同样是注释。 你可以通过在方括号之间添加额外的等号来嵌套注释。

这不能被严格的正则语言匹配，因此简单的有限状态机无法在O(n)时间内处理它--你需要一个计数器。

Perl 5正则表达式可以使用反向引用处理此问题。但是一旦您需要非正则模式匹配，您的正则表达式库就必须放弃简单的状态机方法并使用更复杂、效率更低的代码。

- Mike Samuel

---

好的。因为他提供了正确的解决方案，即使他没有正确地提出问题，所以加一分。 - Travis Webb

这不是一个好的答案，我也没有混淆反向引用和捕获组的创建。这个答案根本没有回答问题。我问为什么要强制正则表达式防止创建反向引用（使用捕获组）。没有混淆。至于答案，第二段有一些好的回应，但你没有提供任何解释或示例。什么是使语言非正则的意思？我不关心捕获组与反向引用的比较，我只谈论跳过反向引用的创建。 - Explosion Pills

@tandu，我不知道“强制正则表达式防止创建反向引用”的意思。正则表达式包含捕获组。通常只有捕获组1到9可以在替换字符串中被引用为$1...$9，这是不将所有括号分组作为捕获组的原因之一。反向引用与捕获组不同。反向引用是出现在正则表达式中（而不是替换字符串中）的一个序列，它指回一个捕获组，perl 5使用\1...\9语法来表示它们。 - Mike Samuel

你说的“通常只有1-9组可以在替换中被引用为$1⋯$9”，是什么意思？Perl肯定允许您使用任意数量的编号组，因此如果您愿意，可以拥有一个$388。其他编程语言是否对这种事情施加任意限制？ - tchrist

@tchrist，一些例子。来自http://www.grymoire.com/Unix/Regular.html#uh-10 "您可以使用“\”后跟单个数字来调用已记忆的模式。因此，要搜索两个相同的字母，请使用“\（[a-z] \）\ 1”。您可以有9种不同的记忆模式。" Python允许最多99个：http://docs.python.org/library/re.html。我相信Java是无限制的。JavaScript允许超过9个，但我还没有测试过极限。 - Mike Samuel

Answer 2

你说得对，性能并不是避免捕获组的唯一原因，事实上，它甚至不是最重要的原因。

另一个缺点是它使正则表达式更难以阅读、编辑和更新（如果你最终想要使用后向引用）。

我从另一个角度来看待这个问题：如果你习惯使用非捕获组，在那些你选择捕获内容的场合，你会更容易跟踪组号。同样地，如果你正在使用命名组（假设你的正则表达式支持它们），你应该始终使用命名组，并且始终通过名称而不是数字来引用它们（在后向引用或替换字符串中）。始终遵循这些规则将至少部分抵消非捕获组的可读性惩罚。

是的，这样弄起来确实很麻烦，编写/维护正则表达式的人也知道这一点。在.NET中，你可以设置“ExplicitCapture”选项，从而将所有“裸”括号视为非捕获组，只有命名组才会捕获。在Perl 6中，圆括号（带或不带名称）总是捕获，方括号用于非捕获组。其他的正则表达式风格最终可能也会采用这种方式，但在此期间，我们只能依靠良好的习惯。

- Alan Moore

---

Perl5语法的问题在于，如果您想要做的是使用许多 (?:⋯) 进行简单无名分组，并使用 (?<ɴᴀᴍᴇ>⋯) 进行命名捕获和 \k<ɴᴀᴍᴇ> 进行命名反向引用，则会变得混乱。尽管它们要好得多，但这些都比 (⋯), \1 和 $1 更加冗长/嘈杂。 - tchrist