regex - 为什么 "ab(cd|c)*d"完全匹配 "abcdcdd"但 "ab(c|cd)*d"不匹配？尽管他们彼此相似

Question

我试过这个正则表达式:

ab(cd|c)*d

在 regex101 和 RegExr 网站中。它完全匹配这段文字:

abcdcdd

现在让我们在正则表达式中交换 "cd" 和 "c" :

ab(c|cd)*d

当我在网站上尝试这个正则表达式时，我发现这个正则表达式与相同的文本不完全匹配。

为什么正则表达式引擎不识别 ab(cd|c)*d 和 ab(c|cd)*d 是相同的，我如何说服 ab(c|cd)*d 匹配最长的字符串？

正则表达式: ab(cd|c)*d
在 13 步骤中匹配的完整文本: abcdcdd

正则表达式: ab(c|cd)*d
9 步骤中匹配的部分文本: abcd cdd

Answer 1

@MurrayW 的回答很好，但我想添加一些背景信息。

正则表达式作为有限状态自动机

当我第一次在大学学习正则表达式时，我们学会了将它们转换为有限状态自动机，本质上是将它们编译成图形，然后对其进行处理以匹配字符串。当你这样做时，(cd|c) 和 (c|cd) 被编译到同一个图中，在这种情况下，你的两个正则表达式都将匹配整个字符串。这就是 grep 实际上所做的:

两个都

echo abcdcdd | grep --color -E 'ab(c|cd)*d'

和

echo abcdcdd | grep --color -E 'ab(cd|c)*d'

将整个字符串涂成红色。

我们称之为“正则表达式”的模式

真正的有限状态自动机有许多程序员不喜欢的限制，例如无法捕获匹配的组，无法在模式中稍后重用这些组，以及我忘记的其他限制，所以我们在大多数编程中使用的正则表达式库语言实现了更复杂的形式。我不记得它们到底是下推自动机，但我们有内存，我们有回溯，以及我们不假思索地使用的各种好东西。

冒着看起来迂腐的风险，我们使用的模式根本不是“常规”的。我知道，差异通常是不相关的，我们只是希望我们的代码能够工作，但偶尔它很重要。

因此，虽然正则表达式 (cd|c) 和 (c|cd) 将被编译成相同的有限状态自动机，但这两个(非正则)模式被转变成逻辑，表示从左到右尝试变体，并且仅在其余部分时回溯模式稍后无法匹配，因此您观察到的结果。

速度

虽然我们的“正则表达式”库支持的模式为我们提供了许多我们喜欢的好东西，但这些都是以性能为代价的。真正的正则表达式非常快，而我们的模式虽然通常很快，但有时可能非常昂贵。在此站点上搜索“灾难性回溯”以获取许多需要指数时间失败的模式示例。与 grep 一起使用的相同模式将被编译成一个图形，该图形以线性时间应用于字符串以无论如何匹配。