JavaScript中贪婪行为有所不同？

 

有一个问题让我意识到，在某些正则表达式引擎中，量词的贪婪并不总是相同的。 从这个问题的正则表达式中修改一下： 

![(.*?)*]

（我知道*在这里是多余的，但我发现以下是一个非常有趣的行为）。

如果我们尝试匹配： 

![][][]

我希望得到的第一个捕获组是空的，因为(.*?)是懒惰的，并会在第一站]它遇到。 这确实发生在：

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

    • 我看了一些其他语言，例如ruby，java，C＃，但都表现得像我期望的那样（即返回空捕获组）。

    （regexplanet的golang味道显然也会获得非空的捕获组）

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

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

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

    简短的回答

    该行为在15.10.2 模式语义中的ECMA-262规范中定义，特别是在15.10.2.5中讨论生产Term :: 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在与受影响的模式无关的情况下不符合规范。

    长答案

    规格的相关部分在下面引用。 有些规范的一部分被忽略（[...]）以保持讨论的相关性。 我将通过简化说明中的信息来解释这些信息。

    词汇

  • 状态是一个有序对（endIndex，captureures），其中endIndex是一个整数，capture是一个NcapturingParens值的内部数组。 状态用于表示正则表达式匹配算法中的部分匹配状态。 endIndex是一个加上该模式迄今为止匹配的最后一个输入字符的索引，而捕获包含捕获括号的结果。 [...]。 由于回溯，许多国家可能在匹配过程中随时使用。
  • 一个MatchResult的或者是一个国家或特殊标记失败 ，指示比赛失败。

    • 这里不应该有混乱。 State保留跟踪迄今为止已处理的位置（以及我们目前不感兴趣的捕获）。 MatchResult，是，匹配结果（杜！）。

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

    • 匹配器包含代码以匹配它所代表的子模式，并且它将调用Continuation继续匹配。 And Continuation包含代码，用于继续匹配Matcher离开的地方。 他们都接受国家作为参数来知道从哪里开始匹配。

    生产条款:: Atom Quantifier

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

  • 评估Atom获得Matcher m。
  • 评估量词以获得三个结果：整数min，整数（或∞）max和布尔型贪婪。
  • 如果max是有限且小于min，则抛出一个SyntaxError异常。
  • 设parenIndex为整个正则表达式中左侧捕获括号的数量，该数量出现在此生产扩展的Term的左侧。 [...]
  • 让parenCount为扩展此制作的Atom中左侧捕获括号的数量。 [...]
  • 返回一个内部的Matcher闭包，它带有两个参数，一个State x和一个Continuation c，并执行以下操作：
  • 调用RepeatMatcher（m，min，max，greedy，x，c，parenIndex，parenCount）并返回其结果。

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

    抽象操作RepeatMatcher采用八个参数：Matcher m，整数min，整数（或∞）max，布尔贪婪，状态x，Continuation c，整数parenIndex和整数parenCount，并执行以下操作：

  • 如果max为零，则调用c（x）并返回其结果。
  • 创建一个采用一个状态参数y的内部继续闭包d并执行以下操作：
  • 如果min为零且y的endIndex等于x的endIndex，则返回失败 。
  • 如果min为零，则让min2为零; 否则让min2为min-1。
  • 如果max为∞，则令max2为∞; 否则让max2为max - 1。
  • 调用RepeatMatcher（m，min2，max2，greedy，y，c，parenIndex，parenCount）并返回其结果。
  • 设cap是x的新副本捕获内部数组。
  • 对于满足parenIndex <k和k的每个整数k？ parenIndex + parenCount，将cap [k]设置为undefined 。
  • 让e是x的endIndex。
  • 让xr成为国家（e，cap）。
  • 如果min不为零，则调用m（xr，d）并返回其结果。
  • 如果贪婪是假的 ，那么
  • 调用c（x）并让z为其结果。
  • 如果z不是失败 ，则返回z。
  • 调用m（xr，d）并返回其结果。
  • 调用m（xr，d）并让z为结果。
  • 如果z不是失败 ，则返回z。
  • 调用c（x）并返回其结果。

    • 步骤2限定了继续d，我们尝试匹配重复原子，这将在后面被称为在步骤7（分钟> 0的情况下）的另一实例中，经由匹配器步骤8.3（懒惰情况下）和步骤9（贪婪情况） m 。

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

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

  • 步骤7涵盖量词具有非零最小值的情况。 贪婪无论如何，在允许我们调用Continuation之前，我们需要至少匹配Atom的最小实例。

  • 由于步骤7中的条件，从这一点起，min为0。 步骤8处理量词懒惰的情况。 步骤9,10,11处理量词是贪婪的情况。 请注意调用的相反顺序。

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

    调用延续c（x）意味着退出重复并匹配接下来的任何内容。 请注意Continuation c如何传递给Continuation d中的RepeatMatcher，以便它可用于重复的所有后续迭代。

    JavaScript RegExp中的怪癖解释

    步骤2.1是导致PCRE和JavaScript之间结果差异的罪魁祸首。

  • 如果min为零且y的endIndex等于x的endIndex，则返回失败 。

    • 当量词最初具有0作为min（ *或{0,n} ）或通过步骤7时达到条件min = 0，只要min> 0（原量词是+或{n,}或{n,m} ）。

    当min = 0 且量词贪婪时，Matcher m将被调用（在步骤9中），它试图匹配Atom的一个实例并调用步骤2中设置的Continuation d。继续d将递归调用RepeatMatcher，它在转向将再次调用Matcher m（步骤9）。

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

    正如步骤2.1中设置的那样，当min = 0时， JavaScript正则表达式引擎会在匹配空字符串（返回失败 ）时删除空字符串。 这有效地拒绝了“空串重复有限多次是空串” 。

    步骤2.1的另一个副作用是，从时分= 0，只要有一个实例，其中匹配器的点m非空字符串匹配时，原子的最后的重复是保证非空。

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

    我做了一些测试，发现在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似乎迫使惰性量词匹配至少一次除贪婪量词第一次迭代以外的所有迭代，然后在贪心量词找到所需的最小迭代次数时停止迭代。

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

    这不是回答为什么grediness在Javascript中表现不同，但它表明这不是一个错误，而是经过测试表现如此。 我将以谷歌的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

    此代码适用于Javascript http://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();
}
    链接地址: http://www.djcxy.com/p/76919.html

    上一篇: Greediness behaving differently in JavaScript?

    下一篇: Greedy vs. non