这些案件中哪一个涉及回溯？

Question

我试图从多个来源研究regex，但是遇到了一个关于回溯的困惑，因为它定义了回溯，这意味着正则表达式引擎无法匹配模式时的状态，因此它返回到第一个原子与匹配的位置，因此，例如，为了匹配He captured a catfish for his cat中的cat，引擎将执行如下步骤：

• 它将搜索c，直到在c ( captured )匹配为止。
• 那么a也是一样的
• 但未能将t与p相匹配
• 引擎在c in captured后重新设置位置，因为它知道在此之前不会发生匹配。

因此，在所有情况下，没有量词，引擎将重置整个模式，以尝试匹配它再次从不同的位置。

另一个定义回溯是使用量词(如.* )的状态，因此regex引擎将匹配完整的文本，这使得它失败，因此它一个接一个地返回，直到匹配发生。我觉得这不一样。

如前所述，这里

正则表达式匹配的一个基本特征是所谓的回溯。所有正则表达式量词(即*、*、+、+？、{n，m}和{n，m}？)都(在需要时)使用哪一种。 为了使正则表达式匹配，整个正则表达式必须匹配，而不仅仅是其中的一部分。因此，如果包含量词的模式的开头成功地导致模式的后面部分失败，匹配的引擎将备份并重新计算开始部分--这就是为什么它被称为回溯。

这意味着像([A-Z][A-Z0-9]*)\b[^>]*>.*<\/\1>这样匹配Testing <B><I>bold italic</I></B> text.的模式将像这样工作：

• 它将首先匹配<B>
• 然后，模式需要匹配.*，这将匹配到字符串的末尾。
• 然后，它将尝试匹配<，但它已经到达终点，所以它将一个字符一个一个地回溯，直到它匹配。

与第一个cat示例相反，该示例完全将引擎重置到第一个原子，然后从匹配第一个原子的位置重新启动。

但在另一种情况下，如果我在?后面添加.*，正则表达式将跳过这个原子.*?，试图匹配剩余的字符，但是如果没有匹配，则返回到.进行匹配，直到有<，然后开始匹配原子。

我想这里有多个定义，谁能解释一下这些案例中哪一个是回溯的。

Answer 1

让我们检查一些回溯定义。

“NFA引擎的本质是:它依次考虑每个子表达式或组件，每当需要在两个同样可行的选项之间作出决定时，它会选择一个并记住另一个在需要时返回到稍后的。如果尝试选项成功，而regex的其余部分也成功，则将完成匹配。如果其他正则表达式中的任何内容最终导致失败，regex引擎知道它可以返回到它选择的选项的位置，并且可以通过尝试另一个选项来继续进行匹配。通过这种方式，它最终会尝试正则表达式的所有可能的排列(或者至少在找到匹配之前尽可能多地尝试)“掌握Perl和其他工具强大的正则表达式技术，Jeffrey E. F. Friedl，p.102。

另一个：

“当正则表达式包含可选的量词或替换结构时，输入字符串的求值不再是线性的。与NFA引擎的模式匹配是由正则表达式中的语言元素驱动的，而不是由输入字符串中要匹配的字符驱动的。因此，正则表达式引擎试图完全匹配可选或可选的子表达式。当正则表达式进入子表达式中的下一个语言元素而匹配失败时，正则表达式引擎可以放弃其成功匹配的一部分，返回到先前保存的状态，以便将正则表达式作为一个整体与输入字符串进行匹配。返回到以前保存的状态以查找匹配的进程称为回溯。

还有一个：

“为了使正则表达式匹配，整个正则表达式必须匹配，而不仅仅是其中的一部分。因此，如果包含量词的模式的开头以导致模式中的以后部分失败的方式成功，匹配的引擎将备份并重新计算开头部分--这就是为什么它被称为回溯。”(来源)

回溯的中心部分似乎是将“返回”进程返回到一个较早的状态，以重新计算(重新匹配)字符串，使整个表达式匹配。它不限于如何这样做来调用这一进程本身。

没有一个资源限制回溯仅限于贪婪或非贪婪的量词。你可能会读到在my 原答案，https://stackoverflow.com/questions/33869557中关于贪婪和非贪婪模式行为的区别。简而言之，它们的机制不同，取回和再匹配的方式不同，但本质是相同的，正如上述定义所描述的那样。