Perl 与 Javascript 正则表达式

Question

为什么下面的正则表达式在 Javascript 中捕获（通过捕获组）字符串 'abc' 而在 PCRE 中不捕获（尽管它仍会匹配）？

(.*)*

Answer 1

PCRE 中捕获组为空的原因如下：

• 初始状态

  (.*)*     abc
   ^        ^
  

• 首先将(.*)部分与abc进行匹配，将输入的位置提前到末尾。此时捕获组包含 abc。

  (.*)*     abc
      ^        ^
  

• 现在，输入位置是后c字符，剩下的输入是空串。 Kleene 明星发起第二次匹配 (.*) 组的尝试：

  (.*)*     abc
   ^           ^
  

• (.*)组匹配abc后的空字符串。由于匹配，先前捕获的字符串被覆盖。

• 由于输入位置没有前进，*到此结束迭代，匹配成功

JS 和 PCRE 之间的行为差​​异是由于指定正则表达式引擎的方式所致。 PCRE 的行为与 Perl 一致：

PCRE:

$ pcretest
PCRE version 8.39 2016-06-14

  re> /(.*)*/
data> abc
 0: abc
 1:

Perl:

$ perl -e '"abc" =~ /(.*)*/; print "<$&> <>\n";'
<abc> <>

让我们compare this with .NET，它具有相同的行为，但支持多次捕获：

当第二次匹配捕获组时，.NET 会将捕获的值添加到捕获堆栈。 Perl 和 PCRE 将简单地覆盖它。

---

至于JavaScript：

这里是ECMA-262 §21.2.2.5.1 运行时语义：RepeatMatcher 抽象操作：

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 steps:

1. If max is zero, return c(x).
2. Create an internal Continuation closure d that takes one State argument y and performs the following steps when evaluated:
   • a. If min is zero and y's endIndex is equal to x's endIndex, return failure.
   • b. If min is zero, let min2 be zero; otherwise let min2 be min‑1.
   • c. If max is ∞, let max2 be ∞; otherwise let max2 be max‑1.
   • d. 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 List.
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, return m(xr, d).
8. If greedy is false, then
   • a. Call c(x) and let z be its result.
   • b. If z is not failure, return z.
   • c. 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.

这基本上是对计算量词时应该发生的事情的定义。 RepeatMatcher 是处理内部操作匹配的操作 m.

您还需要了解什么是 State（§21.2.2.1，强调我的）：

A State is an ordered pair (endIndex, captures) where endIndex is an integer and captures is a List 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. The nth element of captures is either a List that represents the value obtained by the nth set of capturing parentheses or undefined if the nth set of capturing parentheses hasn't been reached yet. Due to backtracking, many States may be in use at any time during the matching process.

对于您的示例，RepeatMatcher 参数是：

• m：Matcher负责处理子模式(.*)
• min: 0（Kleene 星号量词的最小匹配数）
• max: ∞ (Kleene star 量词的最大匹配数)
• greedy: true（使用的Kleene星量词是贪心的）
• x: (0, [undefined])（见上面的状态定义）
• c：延续，在这一点上它将是：a 总是return作为成功的状态参数的延续MatchResult，折叠父规则后
• parenIndex: 0（根据 §21.2.2.5 这是 整个正则表达式左侧出现的左捕获括号的数量 生产)
• parenCount: 1（相同的规格段落，这是本产品的 Atom 扩展中左捕获括号的数量 - 我不会粘贴完整的spec here 但这基本上意味着 m 定义了一个捕获组)

规范中的正则表达式匹配算法是根据continuation-passing style定义的。基本上，这意味着 c 操作意味着 接下来会发生什么。

让我们展开这个算法。

第一次迭代

第一次通过时，x₁状态为(0, [undefined])。

1. max不为零
2. 此时我们创建了延续闭包 d₁，它将在第二遍中使用，所以我们稍后会回到这一步。
3. 复制捕获列表cap₁
4. 将cap₁中的捕获重置为undefined，这是fist pass
中的空操作
5. 令e₁=0
6. 令xr₁ = (e₁,cap₁)
7. min为零，跳过此步
8. greedy为真，跳过此步
9. 设z₁ = m(xr, d₁) - 这评估子模式 (.*)

现在让我们退后一步 - m 将匹配 (.*) 与 abc，然后调用我们的 d₁ 关闭，让我们展开那个。

d₁ 使用状态 y₁ =(3, ["abc"]):

• min是0，但是y₁的endIndex是3而x ₁的endIndex是0，所以不要returnfailure
• 令 min2 = min = 0 因为 min = 0
• 设max2=max=∞因为max=∞
• 调用RepeatMatcher(m, min2, max2, greedy, y, c, parenIndex, parenCount)并return其结果。即：RepeatMatcher(m, 0, ∞, false, y₁, c, 0, 1)

第二次迭代

所以，现在我们要进行第二次迭代 x₂ = y₁ = (3, ["abc"]).

1. max不为零
2. 此时我们创建延续闭包d₂
3. 复制捕获列表 cap₂ ["abc"]
4. 将cap₂中的捕获重置为undefined，我们得到cap₂ = [undefined]
5. 设e₂=3
6. 令xr₂ = (e₂,cap₂)
7. min为零，跳过此步
8. greedy为真，跳过此步

9. 设z₂=m(xr₂ , d₂) - 这会评估子模式 (.*)

   这次 m 将匹配 abc 之后的空字符串，并用那个调用我们的 d₂ 闭包。让我们评估一下 d₂ 做了什么。它的参数是y₂ = (3, [""])

   min还是0，但是y₂的endIndex是3而x₂的endIndex也是3（记住这次x是上次迭代的y状态），闭包简单的returns failure.

10. z₂是failure，跳过这一步
11. returnc(x₂)，也就是本次迭代中的c((3, ["abc"]))

c 简单地 return 是一个有效的匹配结果，因为我们在模式的末尾。这意味着 d₁ returns 这个结果，并且第一次迭代 returns 从第 10 步传递它。

基本上，如您所见，导致 JS 行为不同于 PCRE 的规范行如下：

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

结合使用时：

11. Call c(x) and return its result.

return如果迭代失败，先前捕获的值。