为了账号安全,请及时绑定邮箱和手机立即绑定

贪婪的与不情愿的所有格量词

/ 猿问

贪婪的与不情愿的所有格量词

摇曳的蔷薇 2019-06-05 13:50:17

贪婪的与不情愿的所有格量词

我发现了这个优秀教程关于正则表达式,虽然我直觉地理解了“贪婪”、“不情愿”和“所有格”量词的作用,但我的理解似乎有一个严重的漏洞。

具体而言,在以下示例中:

Enter your regex: .*foo  // greedy quantifierEnter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.Enter your regex: .*?foo  
// reluctant quantifierEnter 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 quantifierEnter input string to search: xfooxxxxxxfooNo match found.

解释提到整个输入字符串,字母是消耗掉马彻退却,最右边出现的“foo”是反流

不幸的是,尽管有很好的比喻,我还是不明白谁吃了什么.你知道另一个教程解释(简明扼要)吗?多么,怎样正则表达式引擎能工作吗?

或者,如果有人可以用一些不同的措辞解释以下段落,我们将不胜感激:

第一个示例使用贪婪的量词。*查找“任何”,0次或多次,后面跟着字母“f”o“。因为量词是贪婪的,表达式的.*部分首先吃掉整个输入字符串。此时,整个表达式无法成功,因为最后三个字母(“f”o“)已经被使用(是谁干的?)。所以这场比赛慢慢地退却了。从右到左?)一次只写一个字母,直到“foo”的最右边出现被反拨(这是什么意思?),此时匹配成功,搜索结束。

然而,第二个例子不太情愿,所以它从第一个消费开始(是谁干的?)“什么都没有”。因为“foo”没有出现在字符串的开头,所以它被迫吞下(燕子?)第一个字母(“x”),它在0和4处触发第一次匹配。我们的测试工具将继续这个过程,直到输入字符串耗尽为止。它在4点和13点找到了另一个匹配点。

第三个例子找不到匹配,因为量词是所有格的。在本例中,整个输入字符串由.*+、(多么,怎样?)没有留下任何东西来满足表达式末尾的“foo”。如果您想在不退却的情况下捕获所有的东西,请使用所有格量词(后退是什么意思?);在没有立即找到匹配的情况下,它将优于等效的贪婪量词。


查看完整描述

3 回答

?
慕虎7371278

我试试看。

贪心量词首先尽可能匹配。所以.*匹配整个字符串。然后匹配器试图匹配f跟随,但没有剩下的字符。因此,它“回溯”,使贪婪的量词匹配少了一件事(留下字符串末尾的“o”不匹配)。仍然不符合f在regex中,它又“回溯”了一步,使贪婪的量词再匹配一次(使字符串末尾的“oo”不匹配)。那,那个仍然不匹配f在regex中,因此它再返回一个步骤(使字符串末尾的“foo”不匹配)。现在,匹配器终于匹配了f在regex中,而o下一个o也是匹配的。成功!

勉强或者“非贪婪”量词首先匹配尽可能少。所以.*一开始不匹配,使整个字符串无法匹配。然后匹配器试图匹配f如下所示,但是字符串的不匹配部分以“x”开头,因此不起作用。所以Matcher回溯,使非贪婪的量词再匹配一件事(现在它匹配“x”,留下“fooxxxxxfoo”不匹配)。然后尝试匹配f,它成功了,而o下一个o在regex比赛中。成功!

在您的示例中,它随后按照相同的进程,使用字符串中剩余的不匹配部分重新启动该进程。

占有性量词就像贪婪的量词,但它不会倒退。所以一开始.*匹配整个字符串,没有什么是无法匹配的。则没有任何东西可以与f在看守所里。因为所有格量词不会回溯,所以匹配失败。


查看完整回答
反对 回复 2019-06-05
?
富国沪深

我以前没有听过确切的术语‘反悔’或‘后退’;取代这些的短语是“回溯”,但‘反悔’似乎和任何一个短语一样好,因为“在回溯之前已经暂时接受的内容又扔掉了”。

对于大多数regex引擎来说,最重要的是它们是回溯*他们会试探性接受潜在的部分匹配,同时尝试匹配正则表达式的全部内容。如果第一次尝试无法完全匹配regex,那么regex引擎将回溯在其中一个火柴上。它会尝试匹配*+?、交替,或{n,m}以不同的方式重复,然后再试一次。(是的,这个过程能,会,可以要花很长时间。)

第一个示例使用贪婪的量词。*查找“任何”,0次或多次,后面跟着字母“f”o“。因为量词是贪婪的,表达式的.*部分首先吃掉整个输入字符串。此时,整个表达式无法成功,因为最后三个字母(“f”o“)已经被使用(是谁干的?).

最后三封信,fo,和o已经被.*规则的一部分。然而,regex中的下一个元素,f,输入字符串中什么都没有。发动机将被迫回溯初值.*匹配,试着匹配除了最后一个角色以外的所有角色。(可能是聪明回溯到最后三个,因为它有三个字面术语,但我不知道这个级别的实现细节。)

所以这场比赛慢慢地退却了。从右到左?)一次只写一个字母,直到“foo”的最右边出现被反拨(这是什么意思?),其中

这意味着foo试探性包括在匹配时.*..由于尝试失败,regex引擎尝试接受在.*..如果有一场成功的比赛以前这个.*在本例中,引擎可能会尝试缩短.*匹配(正如您指出的,因为它是一个贪婪的限定符),如果它无法匹配整个输入,那么它可能被迫重新评估它匹配的内容。以前这个.*在我假设的例子中。

指出匹配成功,搜索结束。

然而,第二个例子不太情愿,所以它从第一个消费开始(是谁干的?)“什么都没有”。因为“福”

初始的“无”被.?*,这将消耗最短数量的任何允许其他正则表达式匹配的内容。

没有出现在字符串的开头,而是被迫吞下(燕子?)这个

再一次.?*使用第一个字符,在对初始失败进行回溯后,将整个正则表达式与尽可能最短的匹配。(在本例中,regex引擎扩展了匹配的.*?从左到右,因为.*?是不情愿的。)

第一个字母(“x”),在0和4处触发第一次匹配。我们的测试工具将继续这个过程,直到输入字符串耗尽为止。它在4点和13点找到了另一个匹配点。

第三个例子找不到匹配,因为量词是所有格的。在本例中,整个输入字符串由.*+、(多么,怎样?)

.*+会尽可能多地消耗,不会回溯若要在正则表达式作为一个整体无法找到匹配项时查找新的匹配项,请执行以下操作。因为拥有式表单不执行回溯,所以您可能不会看到.*+,而是使用字符类或类似的限制:account: [[:digit:]]*+ phone: [[:digit:]]*+.

这可以大大加快regex匹配的速度,因为您告诉regex引擎,如果输入不匹配,它就不应该回溯到潜在的匹配。(如果您必须手工编写所有匹配的代码,这将类似于从不使用putc(3)向后推输入字符。这将非常类似于人们在第一次尝试时可能编写的简单代码。除了regex引擎比单一的推回字符要好得多,它们还可以将所有的引擎倒带到零,然后再试一次。*)

但是,除了潜在的速度提升之外,这还可以让您编写与您需要匹配的内容完全匹配的regexs。我想出了一个简单的例子:)但是使用占有式和贪婪的量词来编写正则表达式可以给出不同的匹配,其中一个可能更合适。

没有留下任何东西来满足表达式末尾的“foo”。如果您想在不退却的情况下捕获所有的东西,请使用所有格量词(后退是什么意思?);它的表现将优于

在这种情况下,“后退”意味着“回溯”

在没有立即找到匹配的情况下,等效的贪婪量词。


查看完整回答
反对 回复 2019-06-05
?
不负相思意

http://swtch.com/~rsc/regexp/regexp1.html

我不确定这是互联网上最好的解释,但它写得相当好,也有适当的细节,我不断地回到它。你可能想去看看。

如果您想要更高级别(较少详细的解释),对于简单的正则表达式,比如您正在查看的正则表达式,正则表达式引擎可以通过回溯来工作。本质上,它选择字符串的一个部分(“吃”),并尝试将正则表达式与该节匹配。如果匹配的话,很好。否则,引擎会更改对字符串部分的选择,并尝试将regexp与该节匹配,以此类推,直到它尝试了所有可能的选择。

这个过程是递归使用的:在尝试将字符串与给定的正则表达式匹配时,引擎会将正则表达式分割成几个部分,并将算法分别应用于每个片段。

当引擎选择要尝试匹配的字符串的哪一部分时,贪婪、不情愿和占有式量词之间的区别就会出现,以及如果第一次不工作,如何修改该选择。这些规则如下:

  • 一个贪婪的量词告诉引擎从字符串(或者至少,正则表达式的以前部分尚未匹配的所有字符串)并检查它是否与regexp匹配。如果是这样的话,很好;引擎可以继续使用regexp的其余部分。如果没有,则再试一次,但从要检查的字符串段中修整一个字符(最后一个字符)。如果这不起作用,它就会削弱另一个角色,等等。因此,贪婪的量词检查可能的匹配顺序从最长到最短。

  • 一个不情愿的量词告诉引擎从字符串中尽可能短的部分开始。如果匹配,则引擎可以继续;如果不匹配,则可以继续。一个字符到要检查的字符串的区段,然后尝试它,以此类推,直到找到匹配或整个字符串已经用完为止。因此,一个不情愿的量词检查可能的匹配,以便从最短到最长。

  • 拥有式量词就像第一次尝试时的贪婪量词:它告诉引擎从检查整个字符串开始。区别在于,如果它不工作,占有式量词报告匹配失败的时候和那里。引擎不会更改正在查看的字符串部分,也不会再尝试。

这就是为什么在示例中拥有量词匹配失败的原因:.*+获取与其匹配的整个字符串进行检查,但随后引擎将继续查找其他字符。foo在那之后-但是它当然找不到它们,因为你已经在字符串的末尾了。如果它是一个贪婪的量词,它会回溯并尝试使.*只匹配下一个字符,然后再匹配到第三个字符到最后一个字符,然后再匹配到第四个字符到最后一个字符,这是成功的,因为只有这样,才会有一个foo离开后.*已经“吃掉”了字符串的早期部分。


查看完整回答
反对 回复 2019-06-05

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信