贪婪在JavaScript中表现不同？

Question

有一个问题让我意识到，在某些正则表达式引擎中，量词的贪婪程度并不总是一样的。从这个问题中提取正则表达式并稍加修改：

!\[(.*?)*\]

^{（我知道*在这里是多余的，但我发现下面的行为非常有趣）}

如果我们试图与之匹敌：

![][][]

我希望第一个捕获组为空，因为（.*）是懒惰的，它会在遇到第一个]时停止。这确实是发生在：

• PCRE
• Python
• 但不是Javascript，它匹配整个][][。（jsfiddle）

我环顾了一下其他一些语言，比如ruby、java、C#，但它们的行为都像我预期的那样（即返回空的捕获组）。

（reg解释et的Go语言风味显然也获得非空捕获组）

JavaScript的正则表达式引擎似乎正在解释第二个*来转换* 从懒惰到贪婪。请注意，将第二个*转换为*似乎让正则表达式像我预期的那样工作（完全删除量词也是如此，因为我知道在这种情况下它是多余的，但这不是重点）。

在正则表达式中使用了*，但这种行为与，类似或{m，n}并将它们转换为惰性版本，得到与*相同的结果 。

有人知道到底发生了什么吗？




Answer 1

这并不是在回答为什么灰色在Javascript中表现出不同的行为，但它表明这不是一个bug，而且经过测试它的行为也是如此。我将以谷歌的v8引擎为例。我在他们的测试中发现了一个类似的例子。

/test/mjsunit/third_party/regexp pcre。js:

line 1085: res[1006] = /([a]*?)*/;
line 4822: assertToStringEquals("aaaa,a", res[1006].exec("aaaa "), 3176);

https://code.google.com/p/v8/source/browse/trunk/test/mjsunit/third_party/regexp-pcre.js#1085

此代码适用于Javascripthttp://regex101.com/r/nD0uG8但它对PCRE php和python没有相同的输出。

更新：关于你的问题：

JavaScript的正则表达式引擎似乎正在解释第二个*来转换。*？从懒惰到贪婪

https://code.google.com/p/v8/source/browse/trunk/src/parser.cc#5157

RegExpQuantifier::QuantifierType quantifier_type = RegExpQuantifier::GREEDY;
if (current() == '?') {
    quantifier_type = RegExpQuantifier::NON_GREEDY;
    Advance();
} else if (FLAG_regexp_possessive_quantifier && current() == '+') {
    // FLAG_regexp_possessive_quantifier is a debug-only flag.
    quantifier_type = RegExpQuantifier::POSSESSIVE;
    Advance();
}

Answer 2

我做了一些测试，发现在Firefox和Chrome中，如果一个组有一个贪婪的量词，并且直接或间接地包含一个或多个以零为最小迭代次数的懒惰量词，那么对于已经满足最小迭代次数的贪婪量词的迭代，如果懒惰量词要匹配零迭代，则可以匹配一个或多个迭代的最左边的懒惰量词将匹配一个迭代，如果该组会找到零长度匹配。

例如，（.{0,2}？）{5,8}匹配“abcdefghijklmnopqrstuvwxyz”中的“abc”，因为。{0,2}?为{5,8}的迭代6、7和8匹配一个迭代。

如果组后面有贪心量词无法匹配的标记，那么懒惰量词将扩展其迭代次数。从未尝试过零次迭代的置换。但是贪婪量词仍然可以回溯到它的最小迭代次数。

在同一个主题字符串上，（.{0,3}？）{5,6}[ad]匹配“abcd”，而（.{0,3}？）{5,6}a匹配“a”。

如果组中还有其他东西找到匹配项，那么懒惰量词的行为与其他正则表达式引擎中的行为相同。

在Internet Explorer中，当且仅当在使用贪婪量词的组后面有不可选的令牌时，也会发生同样的情况。如果组后面没有令牌，或者它们都是可选的，那么IE的行为就像大多数其他正则表达式引擎一样。

对Firefox和Chrome中的行为的解释似乎是JavaScript标准中15.10.2.5节中两个步骤的组合。RepeatMatcher的步骤2.1使正则表达式引擎失败了已经匹配了所需最少迭代次数的量词的零长度迭代，而不仅仅是停止继续迭代。步骤9在评估懒惰量词本身之前评估懒惰量词之后的任何内容。在这些示例中，包括贪婪量词的持续重复。当这个贪婪量词在步骤2.1中失败时，懒惰量词被迫重复至少一次。

因此，为了回答这是否是一个错误，我会说这是JavaScript规范中的一个错误。这种行为没有任何好处，并且使JavaScript正则表达式与所有其他（流行的）回溯正则表达式引擎不必要地不同。不过，我不认为未来的JavaScript规范会改变这一点。

Opera的行为不同。（.{0,2}？）{5,8}匹配“abcd”，而（.{0,2}？）{6,8}匹配“abcde”。Opera似乎强制惰性量词为贪婪量词的第一次迭代以外的所有迭代匹配至少一次，然后在贪婪量词找到所需的最小迭代次数时停止迭代。

我建议不要使用一切都是可选的分组或替代方案。确保每个备选方案和每个小组都匹配一些内容。如果组需要可选，请使用使整个组成为可选的，而不是使组内的所有内容都成为可选的。这将减少正则表达式引擎必须尝试的排列数。

Answer 3

ECMA-262规范在第15.10.2节模式语义中定义了该行为，尤其是在第15.10.2.5节中，其中讨论了生产术语：：原子量词的语义。

作为一个小小的概括：让E是一个可以匹配空字符串的模式。如果存在一个输入字符串S，其中空字符串是E中的第一个匹配选项，则包含贪婪重复模式E的模式会受到影响。例如：

(a*?)*              against     aaaa
!\[(.*?)*\]         against     ![][][]
(.*?){1,4}          against     asdf
(|a)*               against     aaaa
(a|()|b){0,4}       against     aaabbb

Firefox和其他基于Webkit的浏览器似乎严格遵循规范，而IE在受影响的模式没有续集的情况下不符合规范。

以下引用了规范的相关部分。规范的某些部分被省略（[…]）保持讨论的相关性。我将通过浓缩规范中的信息来解释，同时保持简单。

• 状态是一个有序对（endIndex，captures），其中endIndex是一个整数，captures是NcapturingParens值的内部数组。在正则表达式匹配算法中，状态用于表示部分匹配状态。endIndex是1加上模式匹配的最后一个输入字符的索引，而captures保存捕获括号的结果。[...]. 由于回溯，在匹配过程中，许多状态可能随时都在使用
• MatchResult是表示匹配失败的状态或特殊令牌失败

这里应该没有混淆。State会跟踪到目前为止已经处理过的位置（以及捕获，我们暂时不感兴趣）。MatchResult，嗯，就是匹配结果（duh！）。

• Continuation过程是一个内部闭包（即一些参数已经绑定到值的内部过程），它接受一个状态参数并返回MatchResult。如果内部闭包引用创建闭包的函数中绑定的变量，则闭包将使用这些变量在创建闭包时的值。Continuation尝试将模式的剩余部分（由闭包已经绑定的参数指定）与输入字符串相匹配，从其state参数给出的中间状态开始。如果匹配成功，则继续返回其达到的最终状态；如果匹配失败，则继续返回失败
• Matcher过程是一个内部闭包，它接受两个参数——一个状态和一个延续——并返回MatchResult。匹配器尝试将模式的中间子模式（由闭包已绑定的参数指定）与输入字符串匹配，从其状态参数给定的中间状态开始。Continuation参数应该是与模式其余部分匹配的闭包。在匹配模式的子模式以获得新状态后，匹配器然后调用该新状态的Continuation来测试模式的其余部分是否也可以匹配。如果可以，匹配器返回Continuation返回的状态；如果没有，匹配者可能会在其选择点尝试不同的选择，反复调用Continuation，直到成功或用尽所有可能性

Matcher包含与它所代表的子模式匹配的代码，它将调用继续来继续匹配。并且继续包含从Matcher停止的地方继续匹配的代码。它们都接受State作为参数，以知道从哪里开始匹配。

生产Term:: Atom Quantifier评估如下：

1. 计算Atom以获得匹配器m。

请注意，m是正在重复的原子的匹配器，延续c是从更高级别的产生式规则生成的代码中传入的。

抽象操作RepeatMatcher接受八个参数，一个匹配器m、一个整数min、一个整数（或）∞) max、布尔贪婪、状态x、连续c、整数parenIndex和整数parenCount，并html" target="_blank">执行以下操作：

1. 如果max为零，则调用c（x）并返回其结果

1. 调用c（x）并让z成为其结果。
2. 如果z不是失败，则返回z。
3. 调用m（xr， d）并返回其结果。

第2步定义了一个延续d，我们尝试在其中匹配重复原子的另一个实例，该实例稍后在第7步（min）中调用

步骤5和6创建当前状态的副本，用于回溯目的，并在步骤2中检测空字符串匹配。

从这里开始的步骤描述了3种不同的情况：

>

由于步骤7中的条件，从该点开始，最小值为0。第8步处理量词懒惰的情况。第9、10、11步处理量词贪婪的情况。注意调用的相反顺序。

调用m（xr， d）意味着匹配Atom的一个实例，然后调用Continationd继续重复。

调用Continuation c（x）意味着摆脱重复，匹配接下来发生的任何事情。请注意，延续c是如何被传递到延续d中的RepeatMatcher的，这样它就可以用于重复的所有后续迭代。

步骤2.1是导致PCRE和JavaScript结果不一致的罪魁祸首。

1. 如果min为零，y的endIndex等于x的endIndex，则返回failure

当量词最初将0作为min（*或{0，n}）或通过步骤7达到条件min=0，该步骤必须与min一样长时间调用

当min=0且量词贪婪时，将调用匹配器m（在步骤9中），它尝试匹配Atom的实例，并调用在步骤2中设置的延续d。延续d将递归调用RepeatMatcher，RepeatMatcher将再次调用Matcher m（步骤9）。

如果没有步骤2.1，如果Matcher m将空字符串作为其在输入中提前的第一个可能选择，则迭代将（理论上）永远继续而不提前。鉴于JavaScript RegExp支持的有限功能（没有前向声明的反向引用或其他花哨的功能），当当前迭代匹配空字符串时，没有必要继续进行另一次迭代——无论如何都会再次匹配空字符串。步骤2.1是JavaScript处理空字符串重复的方法。

正如在步骤2.1中设置的，当min=0时，当匹配器m匹配空字符串时，JavaScript正则表达式引擎将进行修剪（返回失败）。这有效地拒绝了“有限次重复的空字符串是空字符串”。

步骤2.1的另一个副作用是，从min=0开始，只要有一个实例Matcherm匹配非空字符串，原子的最后一次重复就保证是非空的。

相比之下，似乎PCRE（和其他引擎）接受"无限重复多次的空字符串是一个空字符串"，并继续其余的模式。这解释了PCRE在上面列出的情况下的行为。至于算法，PCRE在连续两次匹配空字符串后停止重复。