贪婪与不情愿与占有量词

Question

我发现这个关于正则表达式的优秀教程,虽然我直观地理解"贪婪","不情愿"和"占有欲"量词的作用,但我的理解似乎存在严重漏洞.

具体来说,在以下示例中:

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.

解释提到吃完整个输入字符串,字母被消耗,匹配器退出,最右边出现的"foo"已被反刍等.

不幸的是,尽管有很好的比喻,我仍然不明白被谁吃掉了...你知道另一个教程(简明地说明)正则表达式引擎是如何工作的吗？

或者,如果有人可以用稍微不同的措辞来解释以下段落,那将非常感激:

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

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

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

Answer 1

我会试一试.

一个贪婪的量词首先匹配尽可能多地.所以.*匹配整个字符串.然后匹配器尝试匹配f以下内容,但没有剩下的字符.因此它"回溯",使得贪婪的量词匹配少一点(在字符串末尾留下"o"不匹配).这仍然f与正则表达式中的不匹配,因此它"再回溯"了一步,使得贪婪的量词再次减少一点(在字符串末尾留下"oo"无法比拟).这仍然f与正则表达式中的不匹配,因此它再回溯一步(在字符串末尾留下"foo"不匹配).现在,匹配器最终匹配f正则表达式,并且o下一个o匹配.成功!

一个不情愿或"非贪婪"的量词首先尽可能少地匹配.所以一开始.*没有匹配,让整个字符串无法比拟.然后匹配器尝试匹配f以下内容,但字符串的不匹配部分以"x"开头,因此不起作用.因此匹配器回溯,使非贪婪量词匹配更多的东西(现在它匹配"x",留下"fooxxxxxxfoo"无法比拟).然后,它尝试匹配f,这成功的,所以o,下一个o在正则表达式匹配了.成功!

在您的示例中,它然后在相同的过程之后使用字符串的剩余不匹配部分开始处理.

一个占有欲量词就像贪婪的量词,但它不会回溯.所以它从.*匹配整个字符串开始,没有任何不匹配的东西.然后没有什么可以与f正则表达式中的匹配.由于占有量词不会回溯,因此匹配失败.

Answer 2

只是我的练习输出可视化场景 -

Answer 3

我之前没有听过"反刍"或"退缩"的确切条款; 取代这些的短语是"回溯",但"反刍"似乎是一个好的短语,因为"在回溯之前暂时接受的内容再次将其丢弃".

关于大多数正则表达式引擎的重要一点是它们正在回溯:它们会尝试匹配正则表达式的全部内容,暂时接受潜在的部分匹配.如果正则表达式在第一次尝试时无法完全匹配,则正则表达式引擎将在其中一个匹配项上回溯.它会尽量匹配*,+,?,交替,或{n,m}反复不同,然后再试一次.(是的,这个过程可能需要很长时间.)

第一个例子使用贪心量词.*来找到"任何",零次或多次,然后是字母"f""o""o".因为量词是贪婪的,所以表达式的.*部分首先会占用整个输入字符串.此时,整体表达式不能成功,因为最后三个字母("f""o""o")已被消耗(由谁？).

最后三个字母,f,o,并且o已经由最初的消耗.*规则的一部分.但是,正则表达式中的下一个元素在f输入字符串中没有任何内容.引擎将被迫在其初始匹配时回溯.*,并尝试匹配所有但最后一个字符.(它可能很聪明并且可以回溯到最后三个,因为它有三个字面术语,但我不知道这个级别的实现细节.)

所以匹配器一次一个字母慢慢退回(从右到左？)一个字母,直到最右边的"foo"被反刍(这是什么意思？),

这意味着foo有初步匹配时被包括.*.因为该尝试失败,正则表达式引擎尝试接受少一个字符.*.如果曾有过一个成功的比赛之前,在.*这个例子中,那么发动机可能会尝试缩短.*匹配(从右到左,正如你所指出的,因为它是一个贪婪的资格),如果无法匹配整个输入,然后它可能被迫重新评估它在我的假设示例之前匹配的内容.*.

指向匹配成功,搜索结束.

然而,第二个例子是不情愿的,所以它首先消费(由谁？)"什么都没有".因为"foo"

最初没有任何东西被消耗.?*,这将消耗允许其余正则表达式匹配的任何可能的最短量.

没有出现在字符串的开头,它被迫吞下(吞下谁？)

.?*在回溯初始失败以匹配整个正则表达式与最短匹配之后,再次消耗第一个字符.(在这种情况下,正则表达式引擎正在.*?从左到右扩展匹配,因为.*?不情愿.)

第一个字母("x"),它在0和4处触发第一个匹配.我们的测试工具继续该过程,直到输入字符串耗尽.它在4和13找到另一场比赛.

第三个例子找不到匹配,因为量词是占有性的.在这种情况下,整个输入字符串被.*+消耗,(怎么样？)

A .*+将尽可能多地消耗,并且当正则表达式整体找不到匹配时,将不会回溯以找到新匹配.因为所有格形式不执行回溯,所以你可能不会看到很多用途.*+,而是使用字符类或类似的限制:account: [[:digit:]]*+ phone: [[:digit:]]*+.

这可以大大加快正则表达式匹配,因为你告诉正则表达式引擎,如果输入不匹配,它应该永远不会回溯可能的匹配.(如果必须手动编写所有匹配的代码,这类似于永远不会用putc(3)'推回'输入字符.它与第一次尝试时可能写的天真代码非常相似.除了正则表达式引擎之外它比单向回击更好,它们可以将所有回复归零,然后再试一次.:)

但是,除了潜在的加速之外,这还可以让你编写与你需要匹配的正则匹配的正则表达式.我在提出一个简单的例子时遇到了麻烦:)但是使用所有格与贪婪量词编写正则表达式可以给你不同的匹配,而另一个可能更合适.

留下任何遗留下来以满足表达结尾处的"foo".在你想要抓住所有东西而不退缩的情况下使用占有量词(后退是什么意思？); 它会超越

在这种情况下,"后退"意味着"回溯" - 抛弃暂时的部分匹配以尝试另一个部分匹配,这可能成功也可能不成功.

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

Answer 4

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

我不确定这是互联网上最好的解释,但它的写得相当好,而且相当详细,我一直回到它.你可能想看一下.

如果你想要一个更高级别(更不详细的解释),对于简单的正则表达式,例如你正在看的那个,正则表达式引擎通过回溯来工作.从本质上讲,它选择("吃掉")字符串的一部分,并尝试将正则表达式与该部分进行匹配.如果它匹配,那很好.如果没有,引擎会改变它对字符串部分的选择,并尝试将regexp与该部分匹配,依此类推,直到尝试了所有可能的选择.

此过程以递归方式使用:在尝试将字符串与给定正则表达式匹配时,引擎会将正则表达式拆分为多个部分,并将算法单独应用于每个部分.

贪婪,不情愿和占有量词之间的差异在引擎选择要尝试匹配的字符串的哪个部分时进入,以及如果第一次不起作用则如何修改该选择.规则如下:

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

• 一个不情愿的量词告诉引擎以最短的字符串开始.如果匹配,引擎可以继续; 如果没有,它会向正在检查的字符串部分添加一个字符并尝试该字符,依此类推,直到找到匹配或整个字符串已用完为止.因此,一个不情愿的量词从最短到最长的顺序检查可能的匹配.

• 占有量词在第一次尝试时就像一个贪婪的量词:它通过检查整个字符串告诉引擎启动.不同之处在于,如果它不起作用,占有量词会报告当时和那里的匹配失败.引擎不会更改正在查看的字符串部分,并且不再进行任何尝试.

这就是为什么占有量词匹配在你的例子中失败的原因:对匹配.*+的整个字符串进行检查,但之后引擎继续查找其他字符foo- 但当然它找不到它们,因为你已经在字符串的末尾了.如果它是一个贪婪的量词,它会回溯并尝试使.*唯一的匹配到倒数第二个字符,然后到第三个到最后一个字符,然后到第四个到最后一个字符,这成功因为只有这样才是在"吃掉"字符串的前一部分foo之后有一个左边.*.

Answer 5

这是我使用细胞和指数位置的看法(参见此处的图表以区分细胞和指数).

贪婪 - 尽可能地匹配贪婪量词和整个正则表达式.如果没有匹配,请回顾贪心量词.

输入字符串: xfooxxxxxxfoo正则
表达式:.*foo

上面的正则表达式有两部分:
(i)'.*'和
(ii)'foo'以下

每个步骤都将分析这两部分.大括号中解释了对"通过"或"失败"匹配的附加注释.

步骤1:
(i).*= xfooxxxxxxfoo - PASS('.*'是一个贪婪的量词,将使用整个输入字符串)
(ii)foo =索引13后没有剩下的字符匹配 - 失败
匹配失败.

第2步:
(i).*= xfooxxxxxxfo - PASS(回溯贪婪量词'.*')
(ii)foo = o - FAIL
匹配失败.

第3步:
(i).*= xfooxxxxxxf - PASS(回溯贪婪量词'.*')
(ii)foo = oo - 失败
失败.

第4步:
(i).*= xfooxxxxxx - PASS(回溯贪婪量词'.*')
(ii)foo = foo - PASS
Report MATCH

结果:1匹配
我发现文本"xfooxxxxxxfoo"从索引0开始到索引13结束.

不情愿 - 尽可能少地与不情愿的量词匹配并匹配整个正则表达式.如果没有匹配,则将字符添加到不情愿的量词.

输入字符串: xfooxxxxxxfoo正则
表达式:.*？foo

上面的正则表达式有两部分:
(i)'.*？' 和
(ⅱ)"富"

第1步:
.*？=''(空白) - 通过(尽可能少地匹配不情愿的量词'.*？'.索引0有''匹配.)
foo = xfo - FAIL(单元格0,1,2 - 即之间的索引0和3)
匹配失败.

第2步:
.*？= x - PASS(将字符添加到不情愿的量词'.*？'.具有'x'的单元格0匹配.)
foo = foo - PASS
Report MATCH

第3步:
.*？=''(空白) - 通过(尽可能少地匹配不情愿的量词'.*？'.索引4有''匹配.)
foo = xxx - FAIL(单元格4,5,6 - 即之间的索引4和7)
比赛失败.

第4步:
.*？= x - PASS(将字符添加到不情愿的量词'.*？'.单元格4.)
foo = xxx - FAIL(单元格5,6,7 - 即5到8之间的索引)
匹配失败.

第5步:
.*？= xx - PASS(将字符添加到不情愿的量词'.*？'.Cell 4到5.)
foo = xxx - FAIL(单元格6,7,8 - 即6到9之间的索引)
匹配失败.

第6步:
.*？= xxx - PASS(将字符添加到不情愿的量词'.*？'.单元格4到6.)
foo = xxx - FAIL(单元格7,8,9 - 即7到10之间的索引)
匹配失败.

第7步:
.*？= xxxx - PASS(将字符添加到不情愿的量词'.*？'.单元格4到7.)
foo = xxf - FAIL(单元格8,9,10 - 即8到11之间的索引)
匹配失败.

第8步:
.*？= xxxxx - PASS(将字符添加到不情愿的量词'.*？'.单元格4到8.)
foo = xfo - FAIL(单元格9,10,11 - 即9到12之间的索引)
匹配失败.

第9步:
.*？= xxxxxx - PASS(将字符添加到不情愿的量词'.*？'.单元格4到9.)
foo = foo - PASS(单元格10,11,12 - 即10到13之间的索引)
报告MATCH

第10步:
.*？=''(空白) - 通过(尽可能少地匹配不情愿的量词'.*？'.索引13为空.)
foo =没有匹配的字符 - 失败(索引13之后没有任何内容匹配)
匹配失败.

结果:2匹配
我发现文本"xfoo"从索引0
开始到索引4结束.我发现文本"xxxxxxfoo"从索引4开始到索引13结束.

占有 - 尽可能匹配占有量,并匹配整个正则表达式.不要回溯.

输入字符串: xfooxxxxxxfoo正则
表达式:.*+ foo

上面的正则表达式有两部分:'.*+'和'foo'.

步骤1:
.*+ = xfooxxxxxxfoo - PASS(尽可能多地匹配占有量词'.*')
foo =没有匹配的字符 - FAIL(索引13后没有匹配)
匹配失败.

注意:不允许回溯.

结果: 0场比赛