为什么“ ab（cd | c）* d”完全匹配“ abcdcdd”，而“ ab（c | cd）* d”却不匹配？他们彼此一样

Question

我试过这个正则表达式：

ab(cd|c)*d

在regex101和RegExr网站上。它完全匹配此文本：

abcdcdd

现在，让我们在正则表达式中交换“ cd”和“ c”：

ab(c|cd)*d

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

regex引擎为什么不能识别出它们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将被编译成一个图表，该图表将在线性时间内应用于该字符串以无论如何匹配。