贪婪、懒惰（非贪婪）和占有量词在内部是如何工作的？

Question

贪婪、懒惰（非贪婪）和占有量词在内部是如何工作的？

3

我注意到有三种不同的量词类别：贪婪（greedy）、懒惰（即非贪婪）和占有（possessive）。

我知道，粗略地说，贪婪量词会尝试通过先读取整个输入字符串，然后逐个截断字符（如果尝试失败）来获取最长匹配；懒惰量词会尝试通过先读取空字符串，然后逐个添加字符（如果尝试失败）来获取最短匹配；占有量词会像贪婪量词一样尝试，但如果第一次尝试失败就停止匹配。

但是，我不确定上述内容是如何'内部实现'的，希望能够得到澄清（最好附有示例）。

例如，假设我们有输入字符串"fooaaafoooobbbfoo"。

如果正则表达式为"foo.*"（贪婪），那么正则表达式中的foo首先与输入字符串中的foo匹配，然后.*将aaafoooobbbfoo作为'整个字符串'读入吗？还是.*首先读入fooaaafoooobbbfoo作为'整个字符串'，然后截断fooaaafoooobbbfoo来尝试匹配正则表达式中的foo？如果是后者，在每次尝试中，fooaaafoooobbbfoo会从其左侧还是右侧被截断？

如果我用".*foo"或"foo.*foo"替换我的正则表达式，上述问题的答案是否会改变？如果我将那些贪婪量词改为懒惰量词和占有量词呢？

如果一个正则表达式中有多个量词，引擎会如何处理优先级（如果这很重要的话）？

提前感谢！

- J-A-S

3

提示：使用 Regex Debugger 实时查看步骤。 - 41686d6564 stands w. Palestine

这是一个相关答案，但这个问题询问贪婪/懒惰（非贪婪）/占有量词的内部工作原理。 - anubhava

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- anubhava · Accepted Answer

针对您的输入字符串fooaaafoooobbbfoo。

情况1：当您使用以下正则表达式时：

foo.*

首先要记住的是引擎是从左到右遍历的。

有了这个想法后，上述正则表达式将会匹配第一个在输入开头的 foo，然后 .* 将会贪婪地匹配最长的可能匹配项，即在 foo 之后直到结尾的文本。此时匹配停止，因为您的模式中在 .* 之后没有要匹配的内容。

情况2： 当您使用这个正则表达式时：

.*foo

接下来再次使用正则表达式 .*，它会将最长的可能匹配结果贪心地匹配到，直到最后一个foo出现在输入的末尾位置。

情况3： 当你使用这个正则表达式时：

foo.*foo

这将匹配首次出现的foo，即开头处的foo，然后.*将贪婪地匹配最长可能的匹配项，然后才匹配输入末尾的最后一个foo。

情况4：当您使用此正则表达式与懒惰量词一起使用时：

foo.*?foo

这将首先匹配输入中找到的第一个 foo ，也就是以 foo 开头，然后 .*? 会惰性地匹配最短的可能匹配，然后匹配下一个 foo，它是输入中从位置 6 开始的第二个 foo 实例。

Case 5：当您使用带有贪婪限定符的此正则表达式时：

foo.*+foo

首先匹配的是在输入中找到的第一个 foo，也就是以 foo 开头，然后使用 占有量词 的 .*+，这意味着尽可能多地匹配，不要回溯。这将贪婪地匹配直到最长的可能匹配，直到结尾，由于占有量词不允许引擎回溯，因此部分末尾的 foo 存在将导致匹配失败，引擎无法匹配最后一个 foo。