贪婪、不情愿、所有格限定词

我在正则表达式中发现了这个教程,虽然我直观地理解了“贪婪”,“不情愿”;和“;possessive"我的理解似乎有一个严重的漏洞。

具体来说,在下面的例子中:

Enter your regex: .*foo // Greedy qualifier
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 qualifier
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 qualifier
Enter input string to search: xfooxxxxxxfoo
No match found.

解释中提到整个输入字符串,字母被消耗,匹配器后退,最右边出现的"foo"令人反胃的,等等。

不幸的是,尽管有这些美好的比喻,我还是不明白谁吃什么……你知道另一个教程解释(简洁)如何正则表达式引擎的工作吗?

或者,如果有人能用不同的措辞解释下一段,那将是非常感激的:

第一个例子使用贪心量词.*来查找“anything”0次或多次,后面跟着字母"f""o""o"。因为量词是贪婪的,表达式的.*部分首先吃掉整个输入字符串。此时,整个表达式不能成功,因为最后三个字母("f""o""o")已经被[谁?]消耗掉了。所以匹配器慢慢后退[从右到左?]一次一个字母,直到"foo"最右边的位置被反刍[这是什么意思?]],此时匹配成功,搜索结束。

然而,第二个例子是不情愿的,所以它首先从消费[by whom?]“nothing"。因为"foo"没有出现在字符串的开头,它被迫吞咽[谁吞咽?]第一个字母("x"),它触发第一个匹配0和4。我们的测试工具将继续这个过程,直到耗尽输入字符串为止。它在4和13处找到另一个匹配项。

第三个例子没有找到匹配,因为量词是所有格。在这种情况下,整个输入字符串被.*+[如何?],没有留下任何东西来满足“;在表达式的末尾。使用所有格量词表示你想要抓住某物的全部而不后退(back off是什么意思?);在没有立即找到匹配的情况下,它将优于等效贪婪量词。

109434 次浏览

我会试试看的。

贪婪的量词首先尽可能匹配。所以.*匹配整个字符串。然后匹配器尝试匹配后面的f,但是没有字符了。因此它“回溯”,使贪婪量词少匹配一个字符(保留字符串末尾的“o”不匹配)。这仍然不匹配正则表达式中的f,因此它又回溯了一步,使贪婪量词再次少匹配一个字符(保留字符串末尾的“oo”不匹配)。仍然与正则表达式中的f不匹配,因此它又回溯了一步(保留字符串末尾的"foo"不匹配)。现在,匹配器最终匹配正则表达式中的f,并且o和下一个o也被匹配。成功!

不情愿的或“非贪婪”量词首先匹配的次数越少越好。所以.*一开始不匹配任何东西,使整个字符串不匹配。然后匹配器尝试匹配后面的f,但是字符串的未匹配部分以“x”开头,所以这行不通。因此匹切程序返回,使非贪婪量词再匹配一个字符(现在它匹配“x”,不匹配“fooxxxxxxfoo”)。然后它尝试匹配f,成功,并且正则表达式中的o和下一个o也匹配。成功!

在您的示例中,它将使用字符串的剩余未匹配部分“xxxxxxfoo”重新开始该过程,遵循相同的过程。

所有格量词就像贪婪量词一样,但它不会回溯。所以它以.*开始匹配整个字符串,不留下任何未匹配的内容。然后就没有东西留给它与正则表达式中的f匹配了。由于所有格量词没有回溯,匹配就失败了。

我以前没有听过确切的“反刍”或“后退”这两个词;取代这些的短语是“回溯”,但“反刍”似乎是一个很好的短语,用来表示“在回溯再次扔掉之前,暂时被接受的内容”。

关于大多数正则表达式引擎需要意识到的重要事情是,它们是回溯:它们将暂时接受潜在的部分匹配,同时试图匹配正则表达式的整个内容。如果正则表达式在第一次尝试时不能完全匹配,则正则表达式引擎将在其中一个匹配上回溯。它将尝试以不同的方式匹配*+?、alternate或{n,m}重复,并再次尝试。(是的,这个过程需要很长时间。)

第一个例子使用贪心 量词。*来找到“任何东西”,零 或者更多次,然后是信件 f, o, o。因为量词是 的。*部分 表达式首先吃掉整个输入 字符串。在这一点上,整体 表达不能成功,因为没有 最后三个字母(“f”“o”“o”)有 (由谁?).

. bb0

最后三个字母foo已经被规则的初始.*部分使用了。然而,正则表达式中的下一个元素f在输入字符串中没有任何剩余。引擎将在其初始的.*匹配时被强制回溯,并尝试匹配除最后一个字符以外的所有字符。(它可能是聪明的,并回溯到最后三个,因为它有三个字面术语,但我不知道这个级别的实现细节。)

所以这个匹配器 慢慢后退(从右到左的人吗?)一次一个字母 直到最右边的出现 "foo"已被反刍(这是什么意思?),在此

. 0

这意味着在匹配.*时,foo已经包含了暂时。由于该尝试失败,正则表达式引擎尝试在.*中少接受一个字符。如果在这个例子中有一个成功的匹配之前 the .*,那么引擎可能会尝试缩短.*匹配(从右到左,正如你指出的那样,因为它是一个贪婪的限定符),如果它无法匹配整个输入,那么它可能会被迫重新计算它在我的假设例子中匹配的之前 the .*

点匹配成功 搜索结束。< / p >

然而,第二个例子是 不情愿,所以先下手为强 消费(由谁?)“没什么”。因为“foo”< / p >

.?*将消耗初始的nothing,它将消耗允许正则表达式其余部分匹配的尽可能短的任何量。

属性的开头没有出现> 字符串,它被迫吞下(吞下?)

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

第一个字母(一个“x”),触发 第一场比赛在0和4。我们的测试 Harness继续此过程,直到 输入字符串已耗尽。它

第三个示例中查找不到a Match是因为量词是 所有格。在这种情况下,整个 输入字符串被。*+,(如何?)

使用

.*+将消耗尽可能多的量,而不会反悔则在正则表达式整体无法找到匹配时查找新的匹配。因为所有格形式不执行回溯,所以你可能不会经常看到.*+的使用,而是与字符类或类似的限制:account: [[:digit:]]*+ phone: [[:digit:]]*+

这可以极大地加快正则表达式匹配,因为您告诉正则表达式引擎,如果输入不匹配,它永远不应该回溯潜在的匹配。(如果你必须手写所有匹配的代码,这将类似于从不使用putc(3)来“回推”输入字符。这与第一次尝试时编写的简单代码非常相似。除了正则表达式引擎比单个字符的推回要好得多之外,它们可以将所有内容倒回到零并重新尝试。:)

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

不留下任何满足 的末尾的“foo” 表达式。使用所有格 量词的情况,你 想要抓住所有没有的东西 永远后退(back off是什么意思?);它将优于

在这里,“back off”意味着“回溯”——放弃一个试探性的部分匹配来尝试另一个部分匹配,这可能会成功,也可能不会成功。

中的等效贪婪量词 不匹配的情况 立即发现。< / p >

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

我不确定这是互联网上最好的解释,但它写得相当好,细节也适当,我一直在想它。你可能会想去看看。

如果您想要更高级的(不太详细的解释),对于简单的正则表达式(例如您正在查看的正则表达式),正则表达式引擎通过回溯工作。从本质上讲,它选择(“吃掉”)字符串的一个部分,并尝试根据该部分匹配正则表达式。如果匹配,那就太好了。如果不是,引擎改变它对字符串部分的选择,并尝试与该部分匹配regexp,等等,直到尝试了所有可能的选择。

这个过程是递归地使用的:在尝试将字符串与给定的正则表达式匹配时,引擎将把正则表达式分割成块,并将算法单独应用于每个块。

贪婪量词、不情愿量词和所有格量词之间的区别出现在引擎选择匹配字符串的哪一部分时,以及如果第一次不成功如何修改该选择时。规则如下:

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

  • 不情愿的量词告诉引擎从字符串中最短的部分开始。如果匹配,引擎可以继续;如果不是,则添加一个字符到正在检查的字符串部分,并尝试这样做,直到找到匹配或整个字符串已用完为止。因此,不情愿的量词按照从最短到最长的顺序检查可能的匹配项。

  • 所有格量词就像第一次尝试时的贪婪量词:它告诉引擎从检查整个字符串开始。区别在于,如果它不起作用,所有格量词会报告匹配当场失败。引擎不会改变被查看的字符串部分,也不会再进行任何尝试。

这就是所有格量词匹配在你的例子中失败的原因:.*+会根据它匹配的整个字符串进行检查,但之后引擎会继续寻找额外的字符foo -但当然它不会找到它们,因为你已经在字符串的末尾了。如果它是一个贪婪的量词,它将返回并尝试使.*只匹配倒数第二个字符,然后是倒数第三个字符,然后是倒数第四个字符,这是成功的,因为只有在.*“吃掉”了字符串的前面部分之后,才会剩下foo

贪婪:“匹配最长的字符序列”

勉强:“匹配最短的字符序列”

所有格:这有点奇怪,因为它并不(与贪婪和不情愿相反)试图为整个正则表达式找到一个匹配。

顺便说一句:任何正则模式匹配器实现都不会使用回溯。所有现实生活中的模式匹配器都非常快——几乎与正则表达式的复杂性无关!

下面是我使用单元格和索引位置(参见相图来区分单元格和索引)

贪婪-匹配尽可能多的贪婪量词和整个正则表达式。如果没有匹配,则回溯贪婪量词。

输入字符串: xfooxxxxxxfoo
Regex: < / em >。* foo

上面的正则表达式有两部分:
.

(我)”。*'和
(2)“foo”

下面的每个步骤都将分析这两个部分。匹配“Pass”或“Fail”的附加注释在大括号内解释。
< / p > < p >步骤1:
(i) .* = xfooxxxxxxfoo - PASS('。*'是一个贪婪的量词,将使用整个输入字符串)
(ii) foo =索引13后没有字符可以匹配- FAIL
比赛失败了。< / p > < p >步骤2:
(i) .* = xfooxxxxxxfo - PASS(贪量词'.*'上的回溯)
(ii) foo = o - FAIL
比赛失败了。< / p > < p >步骤3:
(i) .* = xfooxxxxxxf - PASS(贪量词'.*'上的回溯)
foo = oo - FAIL
比赛失败了。< / p > < p >步骤4:
(i) .* = xfooxxxxxx - PASS(贪量词'.*'上的回溯)
foo = foo - PASS
报告匹配< / p >

Result: 1 match(es)
我发现文本“xfooxxxxxxfoo”从索引0开始,在索引13结束。

勉强-尽可能少地匹配勉强量词,并匹配整个正则表达式。如果没有匹配,则为不情愿量词添加字符。

< p > 输入字符串: xfooxxxxxxfoo
Regex: < / em > . * ?喷火

上面的正则表达式有两部分:
(我)”。* ?和
(2)“foo”< / p > < p >步骤1:
. * ?= "(空白)- PASS(尽可能少匹配不情愿的量词'.*?'。
.
. foo = xfo - FAIL(单元格0,1,2 -即索引在0到3之间)
比赛失败了。< / p > < p >步骤2:
. * ?= x - PASS(为不情愿量词'.*?'添加字符。单元格0包含'x'是匹配的。)
foo = foo - PASS
报告匹配< / p > < p >步骤3:
. * ?= "(空白)- PASS(尽可能少匹配不情愿的量词'.*?'。
.
. foo = xxx - FAIL(单元格4,5,6 -即索引在4到7之间)
比赛失败了。< / p > < p >步骤4:
. * ?= x - PASS(为不情愿量词'.*?'添加字符。细胞4。)
foo = xxx - FAIL(单元格5,6,7 -即索引在5到8之间)
比赛失败了。< / p > < p >第五步:
. * ?= xx - PASS(为不情愿量词'.*?'添加字符。单元格4到5)
foo = xxx - FAIL(单元格6,7,8 -即索引在6到9之间)
比赛失败了。< / p > < p >第六步:
. * ?= xxx - PASS(为不情愿量词'.*?'添加字符。单元格4到单元格6)
foo = xxx - FAIL(单元格7,8,9 -即索引在7到10之间)
比赛失败了。< / p > < p >第七步:
. * ?= xxxx - PASS(为不情愿量词'.*?'添加字符。单元格4到单元格7)
foo = xxf - FAIL(单元格8,9,10 -即索引在8到11之间)
比赛失败了。< / p > < p >第八步:
. * ?= xxxxx - PASS(为不情愿量词'.*?'添加字符。单元格4到单元格8)
foo = xfo - FAIL(单元格9,10,11 -即索引在9和12之间)
比赛失败了。< / p > < p >步骤9:
. * ?= xxxxxx - PASS(为不情愿量词'.*?'添加字符。单元格4到9)
foo = foo - PASS(单元格10,11,12 -即索引在10到13之间)
报告匹配< / p > < p >第十步:
. * ?= "(空白)- PASS(尽可能少匹配不情愿的量词'.*?'。索引13为空)
foo =没有字符需要匹配- FAIL(索引13之后没有任何字符需要匹配)
. foo =没有字符需要匹配- FAIL(索引13之后没有任何字符需要匹配 比赛失败了。< / p >

Result: 2 match(es)
我发现文本“xfoo”从索引0开始,在索引4结束。
我发现文本“xxxxxxfoo”从索引4开始,在索引13结束

所有格-尽可能匹配所有格量词并匹配整个正则表达式。不要反悔。

< p > 输入字符串: xfooxxxxxxfoo
Regex: < / em >。* + foo

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

< p >步骤1:
.*+ = xfooxxxxxxfoo - PASS(尽可能匹配所有格量词'.*')
foo =没有要匹配的字符- FAIL(索引13后没有要匹配的字符)
. foo =没有要匹配的字符 比赛失败了。< / p >

注意:不允许回溯。

结果: 0 match(es)

贪婪的量化涉及在迭代期间使用字符串中所有剩余的未验证字符进行模式匹配。未验证的字符从活跃的序列开始。每次没有匹配时,末尾的字符为隔离,并再次执行检查。

当活动序列仅满足正则表达式模式的前导条件时,将尝试针对隔离验证其余条件。如果验证成功,则验证隔离区中匹配的字符,剩余的未匹配字符仍未验证,并将在下一次迭代中重新开始该流程时使用。

字符流是从活动序列进入隔离区的。结果的行为是尽可能多地将原始序列包含在匹配中。

不情愿的量化基本上与贪婪限定相同,除了字符流相反——也就是说,它们从检疫开始,流入活跃的序列。结果是匹配中尽可能少地包含原始序列。

占有欲强的量化没有检疫,它包含了一个固定的活跃的序列中的所有内容。

这只是我的实践输出可视化的场景-

Visual Image