了解量词

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.

第一个例子使用贪心量词.*来找到"任何",零次或多次,然后是字母"f""o""o".因为量词是贪婪的,所以表达式的.*部分首先会占用整个输入字符串.此时,整体表达式不能成功,因为已经消耗了最后三个字母("f""o""o").因此,匹配器一次缓慢地退回一个字母,直到最右边的"foo"被反刍,此时匹配成功并且搜索结束.

然而,第二个例子是不情愿的,所以它首先消耗"没有".因为"foo"没有出现在字符串的开头,所以它被强制吞下第一个字母("x"),这会在0和4处触发第一个匹配.我们的测试工具继续进程直到输入字符串为累.它在4和13找到另一场比赛.

第三个例子找不到匹配,因为量词是占有性的.在这种情况下,整个输入字符串由.*+消耗,不留下任何东西以满足表达式末尾的"foo".使用占有量词对于你想要抓住所有东西而不会退缩的情况; 在没有立即找到匹配的情况下,它将胜过等效的贪心量词.

Answer 1

懒惰(不情愿)和贪婪的情况之间的主要区别在于回溯结构的行为和占有欲太过激进了!

• 在一次匹配之后,懒惰的情况总是会将匹配引擎的焦点放在正则表达式中的下一个运算符上.如果下一个运算符失败,则回溯结构将强制重复惰性情况,并且这将继续,直到运算符或目标文本结束; 例如,在你的例子中,f在每次成功匹配后传递给char 匹配,所以每当你有一个foo短语时,你就会得到一个匹配,这就是为什么我们从它的用法中得到多个匹配.

.*？foo

x fooxxxxxxfoo
开始时,懒惰的情况将与x(成功的空匹配后)成功匹配并将焦点传递给下一个运算符; foo正则表达式的一部分,并且由于之后存在x,我们得到这个片段的匹配,字符串的次要部分的相同想法.

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

.*foo

xfooxxxxxxfo o
当贪婪的情况出现时(最后一个字符),匹配将失败,因为我们无法匹配foo正则表达式的部分.比回溯将迫使贪婪的案件进入backtrace其步骤并强制执行下一个操作员foo,类似于懒惰案件;

xfooxxxxxx f oo
此时,该foo部件将获得成功匹配,从而以整个字符串的成功匹配结束.

• 占有案例与贪婪案件非常相似,除了匹配失败导致的最后一部分backtracking,这不是占有欲的情况.如果它可以匹配,它将拥有并将在此过程中牺牲比赛的成功.如果它在匹配字符时失败,那么焦点将传递给正则表达式的下一个运算符.

.*+ foo

xfooxxxxxxfo o
类似于贪婪的情况,我们已到达字符串的末尾,但占有情况仍然可以匹配它,因此不会将火炬传递给backtrack结构,并且会导致匹配失败.

Answer 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.

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

3)案例/.*+foo/:

首先是转向子模式/.*+/.它试图详细说明尽可能多的字符:

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

光标到达结尾,但子模式/foo/尚未发挥作用.所以光标"回去"......哦不,多么可惜,它不能(因为它占有欲)!

所以我们没有比赛.