了解量词

regex java quantifiers

2022-09-04 20:18:26

贪婪、不情愿和所有格量词之间的差异之间有一个区别。

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

说明如下：

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”“o”）已被使用。因此，匹配器一次缓慢地后退一个字母，直到最右边出现的“foo”被反刍，此时匹配成功并且搜索结束。

然而，第二个例子是不情愿的，所以它首先消耗“无”。由于“foo”不会出现在字符串的开头，因此它被迫吞下第一个字母（“x”），这会在0和4处触发第一个匹配。我们的测试工具继续该过程，直到输入字符串耗尽。它在4和13找到另一个匹配项。

第三个示例未能找到匹配项，因为量词是所有格的。在这种情况下，整个输入字符串由 .*+ 使用，不会留下任何内容来满足表达式末尾的“foo”。使用所有格量词来表示你想抓住所有东西而不退缩的情况;在没有立即找到匹配项的情况下，它将优于等效的贪婪量词。

答案 1

懒惰（不情愿）和贪婪的情况之间的主要区别在于，回溯结构的行为和所有格的情况太激进了！

在单个匹配之后，懒惰的情况将始终将匹配引擎的焦点放弃给正则表达式中的下一个运算符。如果下一个运算符失败，回溯结构将强制重复懒惰的情况，并且这种情况会一直持续到运算符或目标文本结束;例如，在您的示例中，每次成功匹配后都会传递给 char 的匹配，因此，每当您有一个短语时，您都会得到一个匹配项，这就是为什么我们从其用法中获得多个匹配项的原因。ffoo

.*？foo

xfooxxxxxxfoo
一开始，懒惰的案例将与成功匹配（在成功的空匹配后）进行成功匹配，并将焦点传递给下一个运算符; 正则表达式的一部分，并且由于在之后存在，因此我们得到了此片段的匹配项，与字符串的辅助部分的想法相同。xfoox

贪婪的情况恰恰相反，会继续其匹配直到失败，从不将焦点传递给下一个运算符，只有当匹配失败时回溯生效，并且下一个运算符将从反向匹配;

.*foo

xfooxxxxxxfoo
当贪婪的情况此时（最后一个字符）时，匹配将失败，因为我们无法匹配正则表达式的部分。比回溯将迫使贪婪的情况走到它的步伐，并强制执行下一个运算符，类似于懒惰的情况;

xfooxxxxxxfoo
此时，该部分将获得成功的匹配，从而以整个字符串的成功匹配结束。foobacktracefoofoo

所有格与贪婪情况非常相似，除了最后一部分匹配失败导致一个，这不是所有格的情况。如果可以匹配，它将拥有并将牺牲匹配过程中的成功。如果它在匹配字符时失败，则只有这样焦点才会传递给正则表达式的下一个运算符。backtracking

.*+foo

xfooxxxxxxfoo
类似的贪婪情况，我们已经到达了字符串的末端，但所有格情况仍然可以匹配它，因此不会将火炬传递到结构，并会导致匹配失败。backtrack

答案 2

一般规则

了解量词、和（分别为 “零或一”、“零或多”、“一个或多个”）的基本知识。?*+

我们说，如果量词试图阐述尽可能多的字符，那么它是贪婪的。
我们说量词是不情愿的（懒惰的），如果它试图尽可能少地阐述字符。
我们说，如果一个量词是贪婪的，并且它不允许回溯，那么它是所有格的。

只有当您知道正则表达式解析器的工作原理时，您才能理解“回溯”的含义（请参阅下面的“动态示例”）。

单一案例解释

?：首先测试 1 次发生，然后 0 次;如果您发现了1次出现，然后需要丢弃它，则可以这样做
??：首次测试 0 次出现，然后 1 次
?+：首先测试 1 次发生，然后 0 次;如果你已经找到了1个事件，然后你需要丢弃它，你不能这样做
*：尝试获取尽可能多的出现次数（偶数为 0）;如果您发现了N个匹配项，然后需要丢弃（其中一些）它们，则可以从上一个开始
*?：尽量减少发生次数（甚至 0）
*+：尝试获取尽可能多的出现次数（偶数为 0）;如果你已经发现了N个实例，然后你需要丢弃（其中一些）它们，你不能这样做
+：尝试获得尽可能多的出现次数（至少1次）;如果您发现了N个匹配项，然后需要丢弃（其中一些）它们，则可以从上一个开始
+?：尽量减少发生次数（至少 1 次）
++：尝试获得尽可能多的出现次数（至少1次）;如果你已经发现了N个实例，然后你需要丢弃（其中一些）它们，你不能这样做

动态示例

在本节中，我将尝试向您展示正则表达式解析器背后的逻辑：

1）大小写 /.*foo/：

首先是子模式的转折点。它开始详细阐述第一个字符：/.*/

xfooxxxxxxfoo
^

然后，它尝试详细说明尽可能多的字符：

xfooxxxxxxfoo
^^
xfooxxxxxxfoo
^^^
[...]
xfooxxxxxxfoo
^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^^^^

光标到达了终点，但子模式尚未发挥作用。因此，光标“返回”以允许子模式获得匹配项：/foo//foo/

xfooxxxxxxfoo
^^^^^^^^^^^^

/foo/仍然无法获得匹配项，因此我们需要再次返回：

xfooxxxxxxfoo
^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^

现在，子模式可以得到匹配项：/foo/

xfooxxxxxxfoo
^^^^^^^^^^^^^

所以匹配是整个字符串。xfooxxxxxxfoo

2）大小写 /.*？foo/：

首先是子模式的转折点。它很懒惰，所以我们希望它包含0个字符。但是如果是这样，子模式就无法匹配，因此它必须详细说明一个字符：/.*?//foo/

xfooxxxxxxfoo
^

现在轮到：foo

xfooxxxxxxfoo
^^^^

所以比赛是.xfoo

（如果设置正则表达式的类型，则解析器将在匹配后从第一个字符重新启动，从而给出第二个匹配globalxxxxxxfoo)

3）大小写 /.*+foo/：

首先是子模式的转折点。它试图阐述尽可能多的字符：/.*+/

xfooxxxxxxfoo
^
[...]
xfooxxxxxxfoo
^^^^^^^^^^^^^

光标到达了终点，但子模式尚未发挥作用。所以光标“回去”...哦不，真可惜，它不能（因为它是占有欲）！/foo/

所以我们没有匹配。