我在正则表达式上找到了这个excellent tutorial，当我直观地理解"greedy"，"reluctant"和"possessive"量词时，我的理解似乎有一个严重的漏洞 .
具体来说，在以下示例中：
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.
解释提到 eating 整个输入字符串，字母为 consumed ，匹配 backing off ，最右边出现"foo"已 regurgitated 等 .
不幸的是，尽管有很好的比喻，我仍然不明白被谁吃掉了...你知道另一个教程（简明地说明）正则表达式引擎是如何工作的吗？
或者，如果有人可以用不同的措辞来解释以下段落，那将非常感激：
第一个例子使用贪婪量词 . *来找到“任何东西”，零次或多次，然后是字母“f”“o”“o” . 因为量词是贪婪的，所以表达式的 . *部分首先会占用整个输入字符串 . 此时，整体表达式不能成功，因为最后三个字母（“f”“o”“o”）已被消耗（由谁？） . 那么匹配器一次一个字母慢慢退回（从右到左？）一个字母，直到最右边出现的“foo”被反刍（这是什么意思？），此时匹配成功，搜索结束 . 然而，第二个例子是不情愿的，所以它首先消费（由谁？）“什么都没有” . 因为“foo”没有出现在字符串的开头，所以它被强制吞下（谁吞下？）第一个字母（“x”），它在0和4处触发第一个匹配 . 我们的测试工具继续该过程直到输入字符串用尽 . 它在4和13处找到另一个匹配 . 第三个例子找不到匹配，因为量词是占有性的 . 在这种情况下，整个输入字符串被 . *，（如何？）消耗，不留任何东西以满足表达式末尾的“foo” . 在你想要 grab 所有东西而不退缩的情况下使用占有量词（后退是什么意思？）;在没有立即找到匹配的情况下，它将胜过等效的贪心量词 .
7 回答
Greedy Quantification 涉及在迭代期间使用字符串的所有剩余未经验证的字符进行模式匹配 . 未经验证的字符在活动序列中开始 . 每次匹配都没有发生时，最后的字符将被隔离，并再次执行检查 .
当活动序列仅满足正则表达式的前导条件时，尝试针对隔离验证剩余条件 . 如果此验证成功，则验证隔离区中的匹配字符，并且残留的不匹配字符保持未经验证，并且将在下一次迭代中重新开始该过程时使用 .
字符流从活动序列进入隔离区 . 由此产生的行为是尽可能多地将原始序列包含在匹配中 .
Reluctant Quantification 与贪婪的资格大致相同，除了字符流相反 - 也就是说，它们从隔离区开始并流入活动序列 . 产生的行为是尽可能少的原始序列包含在匹配中 .
Possessive Quantification 没有隔离区，并且包含固定活动序列中的所有内容 .
贪心：“匹配最长的字符序列”
不情愿：“匹配最短的字符序列”
占有：这有点奇怪，因为它没有（与贪婪和不情愿相反）试图找到整个正则表达式的匹配 .
顺便说一句：没有正则表达式模式匹配器实现将使用回溯 . 所有真实模式匹配器都非常快 - 几乎与正则表达式的复杂性无关！
我之前没有听过“反刍”或“退缩”的确切条款;取代这些的短语是“回溯”，但“反刍”似乎是一个好的短语，因为“在回溯之前暂时接受的内容再次将其丢弃” .
关于大多数正则表达式引擎的重要一点是它们正在回溯：它们会尝试匹配正则表达式的全部内容，暂时接受潜在的部分匹配 . 如果正则表达式在第一次尝试时无法完全匹配，那么正则表达式引擎将在其中一个匹配项上回溯 . 它将尝试以不同方式匹配
*，+，?，交替或{n,m}重复，然后重试 . （是的，这个过程可能需要很长时间 . ）最后三个字母
f，o和o已被规则的初始.*部分消耗 . 但是，正则表达式中的下一个元素f在输入字符串中没有任何内容 . 引擎将被强制回溯其最初的.*匹配，并尝试匹配所有但最后一个字符 . （它可能很聪明并且可以回溯到最后三个，因为它有三个字面术语，但我不知道这个级别的实现细节 . ）这意味着
foo在匹配.*时暂时包括在内 . 由于该尝试失败，正则表达式引擎尝试在.*中接受少一个字符 . 如果在这个例子中.*之前有一个成功的匹配，那么引擎可能会尝试缩短.*匹配（从右到左，正如你所指出的，因为它是一个贪婪的限定符），如果它不能为了匹配整个输入，在我的假设示例中，它可能被迫重新评估它在.*之前匹配的内容 ..?*消耗了最初的任何内容，这将消耗允许其余正则表达式匹配的任何可能的最短数量 .在回溯初始失败以匹配整个正则表达式与最短匹配之后，
.?*再次消耗第一个字符 . （在这种情况下，正则表达式引擎正在从左到右扩展.*?的匹配，因为.*?是不情愿的 . ）.*+将尽可能多地消耗，并且当正则表达式整体未能找到匹配时，将不会回溯以查找新匹配 . 因为所有格形式不执行回溯，所以您可能看不到.*+的许多用法，而是使用字符类或类似限制：account: [[:digit:]]*+ phone: [[:digit:]]*+.这可以大大加快正则表达式匹配，因为你匹配 . （如果必须手动编写所有匹配的代码，这类似于从不使用
putc(3)到'push back'输入字符 . 它与第一次尝试时可能写的天真代码非常相似 . 除了正则表达式引擎更好比回传的单个字符，他们可以将所有回复归零，然后再试一次 . :)但是，除了潜在的加速之外，这还可以让你编写与你需要匹配的正则匹配的正则表达式 . 我在提出一个简单的例子时遇到了麻烦:)但是使用所有格与贪婪量词编写正则表达式可以给你不同的匹配，而另一个可能更合适 .
在这种情况下，“后退”意味着“回溯” - 抛弃暂时的部分匹配以尝试另一个部分匹配，这可能会或可能不会成功 .
http://swtch.com/~rsc/regexp/regexp1.html
我不确定这是互联网上最好的解释，但它的编写得相当好，而且相当详细，我会不断回过头来 . 你可能想看一下 .
如果你想要一个更高级别（更不详细的解释），对于简单的正则表达式，例如你正在查看的那个，正则表达式引擎通过回溯来工作 . 从本质上讲，它选择（“吃掉”）字符串的一部分，并尝试将正则表达式与该部分进行匹配 . 如果它匹配，那很好 . 如果没有，引擎会改变它对字符串部分的选择，并尝试将regexp与该部分匹配，依此类推，直到尝试了所有可能的选择 .
此过程以递归方式使用：在尝试将字符串与给定正则表达式匹配时，引擎会将正则表达式拆分为多个部分，并将算法单独应用于每个部分 .
当引擎选择要尝试匹配的字符串的哪个部分时，贪婪，不情愿和占有性量词之间的区别进入，以及如果第一次不起作用，如何修改该选择 . 规则如下：
贪婪的量词告诉引擎启动使用整个字符串（或者至少，所有字符串都没有工作，它会修剪掉另一个字符等等 . 因此，贪婪的量词会按照从最长到最短的顺序检查可能的匹配 .
一个不情愿的量词告诉引擎以尽可能短的字符串开始 . 如果匹配，引擎可以继续;如果没有，它会向正在检查的字符串部分添加一个字符并尝试该字符，依此类推，直到找到匹配或整个字符串已用完为止 . 因此，一个不情愿的量词从最短到最长的顺序检查可能的匹配 .
占有量词在第一次尝试时就像一个贪婪的量词：它通过检查整个字符串告诉引擎启动 . 不同之处在于，如果它不起作用，占有量词会报告当时和那里的匹配失败 . 引擎不会更改正在查看的字符串部分，并且不再进行任何尝试 .
这就是为什么占有量词匹配在你的例子中失败的原因：
.*+对照它匹配的整个字符串进行检查，但随后引擎继续寻找其他字符foo之后 - 当然它还没有't find them, because you'已经在字符串的结尾 . 如果它是一个贪婪的量词，它会回溯并尝试使.*只与下一个到最后一个字符匹配，然后到第三个到最后一个字符，然后到第四个到最后一个字符，这样才能成功，因为只有这样.*之后是foo还是"eaten"字符串的前一部分 .这是我使用单元格和索引位置的看法（请参阅diagram here以区分单元格与索引） .
Greedy - Match as much as possible to the greedy quantifier and the entire regex. If there is no match, backtrack on the greedy quantifier.
输入字符串：xfooxxxxxxfoo
正则表达式： . * foo
上面的Regex有两部分：
（i）'.*'和
（ii）'foo'
以下每个步骤都将分析这两个部分 . 对于'Pass'或'Fail'匹配的附加注释在大括号内解释 .
步骤1：
（i） . * = xfooxxxxxxfoo - PASS（'.*'是一个贪婪的量词，将使用整个输入字符串）
（ii）foo =在指数13之后没有任何字符匹配 - 失败
比赛失败 .
第2步：
（i） . * = xfooxxxxxxfo - PASS（回溯贪心量词'.*'）
（ii）foo = o - 失败
比赛失败 .
第3步：
（i） . * = xfooxxxxxxf - PASS（回溯贪心量词'.*'）
（ii）foo = oo - 失败
比赛失败 .
第4步：
（i） . * = xfooxxxxxx - PASS（贪婪量词回溯'.*'）
（ii）foo = foo - 通过
报告MATCH
结果：1场比赛
我发现文本"xfooxxxxxxfoo"从索引0开始到索引13结束 .
Reluctant - Match as little as possible to the reluctant quantifier and match the entire regex. if there is no match, add characters to the reluctant quantifier.
输入字符串：xfooxxxxxxfoo
正则表达式： . *？foo
上面的正则表达式有两部分：
（i）'.*?'和
（ii）'foo'
步骤1：
. *？ ='' (blank) - PASS (Match as little as possible to the reluctant quantifier ' . *？ '. Index 0 having ''是匹配 . ）
foo = xfo - FAIL（单元格0,1,2 - 即0到3之间的索引）
比赛失败 .
第2步：
. ？ = x - PASS（将字符添加到不情愿的量词'.?' . 具有'x'的单元格0匹配 . ）
foo = foo - 通过
报告MATCH
第3步：
. *？ ='' (blank) - PASS (Match as little as possible to the reluctant quantifier ' . *？ '. Index 4 having ''是匹配 . ）
foo = xxx - FAIL（单元格4,5,6 - 即4到7之间的索引）
比赛失败 .
第4步：
. ？ = x - PASS（将字符添加到不情愿的量词'.?' . 单元格4.）
foo = xxx - FAIL（单元格5,6,7 - 即5到8之间的索引）
比赛失败 .
第5步：
. ？ = xx - PASS（将字符添加到不情愿的量词'.?' . 单元格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（将字符添加到不情愿的量词'.?' . Cell 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步：
. *？ ='' (blank) - PASS (Match as little as possible to the reluctant quantifier ' . *？' . 索引13为空白 . ）
foo =没有匹配的字符 - FAIL（索引13之后没有任何内容可以匹配）
比赛失败 .
结果：2场比赛
我发现文本"xfoo"从索引0开始到索引4结束 .
我发现文本"xxxxxxfoo"从索引4开始，到索引13结束 .
Possessive - Match as much as possible to the possessive quantifer and match the entire regex. Do NOT backtrack.
输入字符串：xfooxxxxxxfoo
正则表达式： . * foo
上面的正则表达式有两个部分：' . *'和'foo' .
步骤1：
. * = xfooxxxxxxfoo - PASS（尽可能匹配占有量词'.*'）
foo =没有匹配的字符 - FAIL（索引13后无法匹配）
比赛失败 .
注意：不允许回溯 .
结果：0场比赛
我会试一试 .
greedy 量词首先尽可能匹配 . 所以
.*匹配整个字符串 . 然后匹配器尝试匹配f以下，但没有剩下的字符 . 所以它"backtracks"，使贪婪量词匹配少一点（让字符串末尾的"o"无法匹配） . 这仍然与正则表达式中的f不匹配，所以它再一步"backtracks"，使得贪婪量词再次匹配一件事（让字符串末尾的"oo"无法匹配） . 这仍然与正则表达式中的f不匹配，因此它又向后退一步（在字符串末尾留下"foo"不匹配） . 现在，匹配器最终匹配正则表达式中的f，o和下一个o也匹配 . 成功！reluctant 或"non-greedy"量词首先尽可能少地匹配 . 所以
.*最初没有匹配，只留下整个字符串不匹配 . 然后匹配器尝试匹配f跟随，但字符串的不匹配部分以"x"开头，因此不起作用 . 因此匹配器回溯，使非贪婪量词匹配更多的东西（现在它匹配"x"，留下"fooxxxxxxfoo"无法比拟） . 然后它尝试匹配成功的f，以及正则表达式匹配中的o和下一个o. 成功！在您的示例中，它然后按照相同的过程使用字符串的剩余不匹配部分开始处理 .
一个 possessive 量词就像贪婪的量词，但它没有回溯 . 所以它从
.*开始匹配整个字符串，没有留下任何不匹配的东西 . 然后没有什么可以与正则表达式中的f匹配 . 由于占有量词不会回溯，因此匹配失败 .只是我的练习输出可视化场景 -