JavaScript中的贪婪表现不同？

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

Run Code Online (Sandbox Code Playgroud)

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

答案很长

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

词汇

阿州是一个有序对(endIndex的,捕捉),其中endIndex的是整数,并且捕获是的内部数组NcapturingParens值.状态用于表示在正则表达式匹配算法部分匹配的状态.所述endIndex的是一加由图案迄今匹配的最后一个输入字符的索引,而捕获持有捕获括号的结果.[...].由于回溯,许多国家可能在匹配过程中随时使用.

一个MatchResult的或者是一个国家或特殊标记失败,指示比赛失败.

这里应该没有混淆.State跟踪到目前为止已处理的位置(以及我们目前不感兴趣的捕获).MatchResult,是匹配结果(呃!).

甲继续过程是内部的封闭件(即,与已经被绑定到值一些参数的内部程序),它有一个国家参数,并返回一个MatchResult的结果.如果内部闭包引用了在创建闭包的函数中绑定的变量,则闭包使用这些变量在创建闭包时具有的值.在继续尝试将图案的剩余部分(通过封闭的已结合的参数中指定)与输入字符串匹配时,开始在由其给定的中间状态状态参数.如果匹配成功,则Continuation返回它到达的最终状态 ; 如果匹配失败,则Continuation返回失败.

一个匹配器程序是一个内部封闭有两个参数-一个国家和一个延续 -并返回MatchResult的结果.甲匹配器试图匹配图案的中间子模式(由封闭的已结合的参数中指定)相对于输入的字符串,在开始通过其给定的中间状态状态参数.在延续参数应该是一个封闭该模式的其他部分相匹配.在匹配模式的子模式以获得新状态之后,匹配器然后在该新状态上调用Continuation以测试模式的其余部分是否也匹配.如果可以的话,匹配器返回的国家通过返回的延续 ; 如果没有,匹配者可以在其选择点尝试不同的选择,反复调用Continuation,直到它成功或所有可能性都已用尽.

一个匹配器包含的代码来匹配它代表一个子模式,它会调用延续,继续比赛.并且Continuation包含代码以继续匹配Matcher中断的位置.他们都接受State作为参数来知道从哪里开始匹配.

生产期限 :: Atom Quantifier

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

评估Atom以获得Matcher m.

评估Quantifier以获得三个结果:整数min,整数(或∞)max和布尔贪心.

如果max是有限且小于min,则抛出SyntaxError异常.

令parenIndex为此生产扩展的Term左侧出现的整个正则表达式中左捕获括号的数量.[...]

让parenCount成为此生产Atom扩展中左侧捕获括号的数量.[...]

返回一个内部Matcher闭包,它接受两个参数,一个State x和一个Continuation c,并执行以下操作:

调用RepeatMatcher(m,min,max,greedy,x,c,parenIndex,parenCount)并返回其结果.

请注意,正在重复的是Atomm的匹配器,并且从更高级别的生产规则生成的代码中传递Continuation c.

抽象操作RepeatMatcher接受八个参数,Matcher m,整数min,整数(或∞)max,布尔贪心,状态x,Continuation c,整数parenIndex和整数parenCount,并执行以下操作:

如果max为零,则调用c(x)并返回其结果.

创建一个内部Continuation闭包d,它接受一个State参数y并执行以下操作:

如果min为零且y的endIndex等于x的endIndex,则返回失败.

如果min为零,那么让min2为零; 否则让min2成为min - 1.

如果max是∞,那么让max2为∞; 否则让max2为max - 1.

调用RepeatMatcher(m,min2,max2,greedy,y,c,parenIndex,parenCount)并返回其结果.

让帽是的新副本X的捕获内部数组.

对于每个整数ķ满足parenIndex < ķ和ķ？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步定义了一个Continuation d,我们尝试匹配重复Atom的另一个实例,后来在步骤7(min > 0 case),步骤8.3(lazy case)和步骤9(greedy case)中通过Matcher调用m.

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

这里的步骤描述了3个不同的案例:

步骤7包括量词具有非零最小值的情况.贪婪无论如何,我们需要至少匹配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中的quirk说明

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

如果min为零且y的endIndex等于x的endIndex,则返回失败.

当量词最初具有0作为min(或)或通过步骤7时,达到条件min = 0 ,只要min > 0(原始量词是或或),必须调用该步骤.*{0,n}+{n,}{n,m}

当分钟 = 0 和量词是贪婪的,匹配器米将被称为(步骤9),其试图匹配原子的实例,并且呼叫继续d,它被设置在第2步继续d将递归调用RepeatMatcher,这在转身将再次呼叫Matcher m(步骤9).

如果没有步骤2.1,如果匹配器m具有空字符串作为其在输入中向前推进的第一个可能选择,则迭代将(理论上)在没有提前的情况下永久地继续.鉴于JavaScript RegExp支持的功能有限(没有前向声明的反向引用或其他花哨功能),当前迭代匹配空字符串时,无需继续进行另一次迭代 - 无论如何,空字符串将再次匹配.步骤2.1是JavaScript处理空字符串重复的方法.

如步骤2.1中所设置的,当min = 0时,当匹配器m匹配空字符串时(返回失败),JavaScript正则表达式引擎将修剪.这有效地拒绝了"有限多次重复空字符串是一个空字符串".

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

相比之下,似乎 PCRE(和其他引擎)接受"有限多次重复空字符串是空字符串",并继续使用其余模式.这解释了上面列出的案例中PCRE的行为.对于算法,PCRE在连续两次匹配空字符串后停止重复.

归档时间：	11 年，10 月前
查看次数：	522 次
最近记录：	9 年，4 月前