javascript - 贪婪在 JavaScript 中表现不同？

Question

有 this question这让我意识到量词的贪婪在某些正则表达式引擎中并不总是相同的。从那个问题中取出正则表达式并稍微修改一下:

!\[(.*?)*\]

(我知道 * 在这里是多余的，但我发现接下来的行为非常有趣)。

如果我们尝试匹配:

![][][]

我希望第一个捕获组为空，因为 (.*?)很懒，会停在第一个 ]它遇到了。这确实发生在:

PCRE

Python

但不是 Javascript它匹配整个 ][][ . ( jsfiddle )

我环顾了一些其他语言，例如 ruby , java , C#但所有行为都像我期望的那样(即返回空的捕获组)。

(regexplanet 的 golang flavor 显然也获得了非空捕获组)

似乎 JavaScript 的正则表达式引擎正在解释第二个 *转换 .*?从懒惰到贪婪。注意转换第二个 *至 *?似乎使正则表达式按我的预期工作(完全删除量词也是如此，因为我知道在这种情况下它是多余的，但这不是重点)。
*在正则表达式中使用，但此行为与 + 类似, ?或 {m,n}并将它们转换为惰性版本会产生与 *? 相同的结果.

有谁知道真正发生了什么？

Answer 1

简答

该行为在 15.10.2 模式语义部分中的ECMA-262 specs中定义，特别是在 15.10.2.5中，它讨论了产生式的语义::.Atom

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

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

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

长答案

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

词汇

• A State is an ordered pair (endIndex, captures) where endIndex is an integer and captures is an internal array of NcapturingParens values. States are used to represent partial match states in the regular expression matching algorithms. The endIndex is one plus the index of the last input character matched so far by the pattern, while captures holds the results of capturing parentheses. [...]. Due to backtracking, many States may be in use at any time during the matching process.
• A MatchResult is either a State or the special token failure that indicates that the match failed.

这里应该没有混淆。状态跟踪到目前为止已处理的位置(以及我们暂时不感兴趣的捕获)。 MatchResult，嗯，是比赛结果(废话!)。

• A Continuation procedure is an internal closure (i.e. an internal procedure with some arguments already bound to values) that takes one State argument and returns a MatchResult result. If an internal closure references variables bound in the function that creates the closure, the closure uses the values that these variables had at the time the closure was created. The Continuation attempts to match the remaining portion (specified by the closure's already-bound arguments) of the pattern against the input String, starting at the intermediate state given by its State argument. If the match succeeds, the Continuation returns the final State that it reached; if the match fails, the Continuation returns failure.
• A Matcher procedure is an internal closure that takes two arguments -- a State and a Continuation -- and returns a MatchResult result. A Matcher attempts to match a middle subpattern (specified by the closure's already-bound arguments) of the pattern against the input String, starting at the intermediate state given by its State argument. The Continuation argument should be a closure that matches the rest of the pattern. After matching the subpattern of a pattern to obtain a new State, the Matcher then calls Continuation on that new State to test if the rest of the pattern can match as well. If it can, the Matcher returns the State returned by Continuation; if not, the Matcher may try different choices at its choice points, repeatedly calling Continuation until it either succeeds or all possibilities have been exhausted.

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

生产术语::原子量词

The production Term :: Atom Quantifier evaluates as follows:

1. Evaluate Atom to obtain a Matcher m.
2. Evaluate Quantifier to obtain the three results: an integer min, an integer (or ∞) max, and Boolean greedy.
3. If max is finite and less than min, then throw a SyntaxError exception.
4. Let parenIndex be the number of left capturing parentheses in the entire regular expression that occur to the left of this production expansion's Term. [...]
5. Let parenCount be the number of left capturing parentheses in the expansion of this production's Atom. [...]
6. Return an internal Matcher closure that takes two arguments, a State x and a Continuation c, and performs the following:
   1. Call RepeatMatcher(m, min, max, greedy, x, c, parenIndex, parenCount) and return its result.

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

The abstract operation RepeatMatcher takes eight parameters, a Matcher m, an integer min, an integer (or ∞) max, a Boolean greedy, a State x, a Continuation c, an integer parenIndex, and an integer parenCount, and performs the following:

1. If max is zero, then call c(x) and return its result.
2. Create an internal Continuation closure d that takes one State argument y and performs the following:
   1. If min is zero and y's endIndex is equal to x's endIndex, then return failure.
   2. If min is zero then let min2 be zero; otherwise let min2 be min - 1.
   3. If max is ∞, then let max2 be ∞; otherwise let max2 be max - 1.
   4. Call RepeatMatcher(m, min2, max2, greedy, y, c, parenIndex, parenCount) and return its result.
3. Let cap be a fresh copy of x's captures internal array.
4. For every integer k that satisfies parenIndex < k and k ? parenIndex + parenCount, set cap[k] to undefined.
5. Let e be x's endIndex.
6. Let xr be the State (e, cap).
7. If min is not zero, then call m(xr, d) and return its result.
8. If greedy is false, then
   1. Call c(x) and let z be its result.
   2. If z is not failure, return z.
   3. Call m(xr, d) and return its result.
9. Call m(xr, d) and let z be its result.
10. If z is not failure, return z.
11. Call c(x) and return its result.

第 2 步定义了一个 Continuation d，我们尝试匹配重复 Atom 的另一个实例，稍后通过匹配器 m在第 7 步(min > 0 情况)、第 8.3 步(懒惰情况)和第 9 步(贪婪情况)中调用”。

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

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

第 7 步涵盖了量词具有非零最小值的情况。不管贪婪，我们需要匹配至少 min 个 Atom 实例，然后才能调用 Continuation c。

由于步骤 7 中的条件，从此时起 min 为 0。步骤 8 处理量词懒惰的情况。步骤 9、10、11 处理量词贪婪的情况。注意调用的相反顺序。

调用 m(xr, d) 意味着匹配 Atom 的一个实例，然后调用 Continuation d 继续重复。

调用 Continuation c(x) 意味着摆脱重复并匹配接下来发生的任何事情。请注意 Continuation c 如何传递到 Continuation d 中的 RepeatMatcher，以便它可用于重复的所有后续迭代。

JavaScript RegExp 中的怪癖解释

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

1. If min is zero and y's endIndex is equal to x's endIndex, then return failure.

当量词最初有 0 作为 min( *或 {0,n})或通过第 7 步时达到条件 min = 0，只要 min > 0 就必须调用它(原始量词为 +或 {n,})或 {n,m})。

当 min = 0 和 量词贪婪时，Matcher m 将被调用(在步骤 9 中)，它尝试匹配 Atom 的实例并调用在步骤 2 中设置的 Continuation d。Continuation d 将递归调用RepeatMatcher，它又会再次调用Matcher m(步骤9)。

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

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

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

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