java - 理解量词

Question

我正在浏览 Java Tutorial on Quantifiers .

在 Differences Among Greedy, Reluctant, and Possessive Quantifiers 中提到了差异。

我无法理解到底有什么区别。

解释如下:

Enter your regex: .*foo  // greedy quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo  // reluctant quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo // possessive quantifier
Enter input string to search: xfooxxxxxxfoo
No match found.

第一个示例使用贪婪量词 .* 查找“任何东西”，零次或多次，后跟字母“f”“o”“o”。因为量词是贪婪的，表达式的 .* 部分首先吃掉整个输入字符串。此时，整体表达式无法成功，因为最后三个字母(“f”“o”“o”)已经被消耗掉了。因此，匹配器一次缓慢地退回一个字母，直到最右边出现的“foo”被反刍，此时匹配成功，搜索结束。

然而，第二个例子不太情愿，所以它首先消费“无”。因为“foo”没有出现在字符串的开头，它被迫吞下第一个字母(一个“x”)，这在 0 和 4 处触发了第一个匹配。我们的测试工具继续这个过程，直到输入字符串是筋疲力尽的。它在 4 和 13 处找到另一个匹配项。

第三个示例找不到匹配项，因为量词是所有格。在这种情况下，整个输入字符串都被 .*+ 消耗掉了，没有留下任何东西来满足表达式末尾的“foo”。在您想要捕获所有东西而不退缩的情况下使用所有格量词；在没有立即找到匹配项的情况下，它将优于等效的贪婪量词。

Answer 1

懒惰(不情愿)和贪婪情况的主要区别在于回溯结构的行为，而所有格情况过于激进!

• Lazy case 总是会在一次匹配之后，将匹配引擎的焦点交给正则表达式中的下一个运算符。如果下一个运算符失败，回溯结构将强制重复懒惰的情况，并且这种情况一直持续到运算符或目标文本结束；例如，在您的示例中，在每次成功匹配后传递给 char f 的匹配，因此只要您有一个 foo 短语，您就会得到一个匹配项，这就是为什么我们从其用法中获取多个匹配项。

.*?foo

xfooxxxxxxfoo
At the beginning, lazy case will have a successful match with the x (after successful empty match) and pass the focus to the next operator; foo part of the regex, and since that is present after x, we get a match for this fragment, same idea for the secondary part of the string.

• Greedy case则相反，会一直匹配直到失败，不会将焦点传递给下一个算子，只有匹配失败时回溯才会生效，下一个算子才会从反向匹配；

.*foo

xfooxxxxxxfoo
When the greedy case is at this point (last char) the matching will fail since we couldn't match the foo part of the regex. Than the backtracking will force the greedy case to backtrace its steps and enforce the next operator foo, similar of lazy case;

xfooxxxxxxfoo
At this point, the foo part will get a successful match, and thus ending with a successful match of the whole string.

• 占有式情况 与贪婪情况非常相似，除了最后一部分匹配失败导致回溯，占有式情况并非如此。若能匹配，则拥有，并在此过程中牺牲匹配成功。如果匹配字符失败，焦点才会传递给正则表达式的下一个运算符。

.*+foo

xfooxxxxxxfoo
Similar of greedy case, we have reached to the end of the string, but possessive case can still match it, thus will not pass the torch to the backtrack structure, and will cause a matching failure.