理解量词

Question

我正在学习关于量词的Java教程。

贪婪量词、不情愿量词和占有量词之间存在差异。

我不明白到底有什么不同。

解释如下：

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.

第一个例子使用贪婪的量词.*来查找"任何东西"，0次或更多次，后面跟着字母"f"o"o"。因为量词是贪婪的，所以表达式的.*部分首先吃掉整个输入字符串。在这一点上，整个表达式不可能成功，因为最后三个字母("f"o"o")已经被消耗掉了。因此，匹配器一次慢慢地后退一个字母，直到最右边出现的"foo"被反噬，这时匹配成功，搜索结束。

然而，第二个例子是不情愿的，所以它首先消耗"什么都没有"。因为"foo"没有出现在字符串的开头，所以它被迫吞下第一个字母(一个"x")，从而触发0和4处的第一个匹配。我们的测试工具继续这个过程，直到输入字符串用完为止。它在4点和13点找到另一个匹配。

第三个例子找不到匹配项，因为量词是所有格。在这种情况下，整个输入字符串由.*+消耗，不留下任何剩余的内容来满足表达式末尾的"foo"。在想要抓住所有东西而不退缩的情况下，使用所有格量词；在没有立即找到匹配的情况下，它将优于等价的贪婪量词。

Answer 1

懒惰(不情愿)和；贪婪的情况是回溯结构的行为，而占有的情况是太激进了！

• Lazy-case在一次匹配后，总是将匹配引擎的焦点让给正则表达式中的下一个运算符。如果下一个操作符失败，回溯结构将强制重复惰性情况，并且这种情况将持续到操作符或目标文本结束；例如，在您的示例中，在每次成功匹配后传递给charf的匹配，所以每当您有一个foo短语时，您就会得到一个匹配，这就是为什么我们从它的使用中得到多个匹配

.*？foo

x fooxxxxxxfoo
在开始时，lazy case将与x成功匹配(在成功的空匹配之后)，并将焦点传递给下一个操作符；正则表达式的foo部分，由于它出现在x之后，我们得到了该片段的匹配，与字符串的次要部分的想法相同。

• 贪婪的情况正好相反，将继续匹配直到失败，从不将焦点传递给下一个操作符，只有当匹配失败时，回溯才会生效，下一个运算符将从反向匹配

.*foo

xfooxxxxxxfoo
当贪婪情况处于此时(最后一个字符)时，匹配将失败，因为我们无法匹配正则表达式的foo部分。回溯将迫使贪婪情况下的步骤backtrace，并强制执行下一个运算符foo，类似于懒惰情况

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

• 所有格与贪婪格非常相似，除了最后一部分匹配失败导致backtracking之外，所有格的情况并非如此。如果能够匹配，它将拥有并在这个过程中牺牲比赛的成功。如果匹配字符失败，那么焦点只会传递给正则表达式的下一个运算符

.*+foo

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

Answer 2

一般规则

了解了量词?、*和+(分别为"零或一"、"零或多"、"一个或多个")的基本知识。

• 如果一个量词试图尽可能多地刻画字符，那么它就是贪婪的
• 我们说，如果量词试图尽可能少地刻画字符，它就是不情愿的(懒惰)
• 如果量词是贪婪的并且不允许回溯，那么它就是所有格

只有知道regex解析器的工作方式，才能理解"回溯"的含义(请参阅下面的"动态示例")。

单个案例说明

• ?：首先测试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。

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

3)案例/.*+foo/:

首先轮到子模式/.*+/。它试图详细说明尽可能多的字符：

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

光标到达了末尾，但子模式/foo/还没有发挥作用。所以光标"返回"。。。哦，不，真遗憾，它不能(因为它占有欲很强)！

所以我们没有对手。