为什么Javascript不支持lookbehind断言?

问题描述 投票:22回答:2

最近我意识到(通过一些尴尬)在lookbehind assertions不可能正则表达式Javascript

这种断言缺席的(事实)理由是什么似乎很常见?

I realize there are alternate ways to achieve the same thing perhaps,虽然这是工作中禁止功能的基本语义,还是究竟是什么?

似乎那些从正则表达式模式生成Javascript代码的regex testing tools似乎忽略了这个事实 - 这让我觉得有些奇怪。

javascript regex
2个回答
26
投票

Today

Lookbehind现在是ES 2018 specification的官方部分。 Axel Rauschmayer给出了good introduction in his blog post

History

It looks like at the time, Brendan Eich wasn't aware of its existence(因为Netscape是基于旧版本的Perl构建的):

这是1998年,我在97年做的Netscape 4工作是基于Perl 4(!),但是我们提议ECMA TC39 TG1(JS组 - 事情不同,包括大写)基于Perl 5的东西。我们没有得到一切,我们不得不理顺一些明显的怪癖。

我不记得lookbehind(在1998年7月出现在Perl 5.005中)被故意排除在外。 Waldemar可能还记得更多,我在netscape.com里面把他的JS密钥递给了mozilla.org。

如果你是写游戏或迷你规格的游戏(甚至是ES5的风格),请告诉我。我将在下周与其他TC39的人聊聊这件事。

/是

尝试将其包含在邮件列表中有很多不同,但它似乎仍然是性能相当复杂的功能,因为EcmaScript Regular Expressions是基于backtracking的,并且在使用捕获组时需要回溯。如果使用不当,这可能会导致catastrophic backtracking等问题。

在某些时候,它被建议用于ES6 / Es 2015,但它从未制定过草案,更不用说规范了。在last post in the discussion,似乎没有人承担实施它的任务。如果有人感觉被要求编写实现,他们可以注册ES Discuss list并提出建议。

Update May 2015:

2015年5月,Nozomu Katō has proposed an ES7 look-behind implementation

Update September 2015:

Regex Look-behind被添加为stage 0 proposal

Update May 2017:

The proposal is now at stage 3。这意味着现在至少有两个浏览器需要实现它才能成为下一个EcmaScript标准的一部分。正如@martixy在评论中提到的那样,Chrome has implemented it behind the JS experimental flag


7
投票

从结论来看,我认为在JavaScript中没有实现后视,因为没有人知道它应该如何表现,现有的实现表明添加对后视镜头的支持相当复杂。

JavaScript / ECMAScript与其他语言的不同之处在于规范包含正则表达式引擎的抽象实现,而大多数其他语言仅在描述每个正则表达式语法的行为时停顿不足,并且对不同标记如何与之交互的描述很少描述彼此。

展望?易于实施

预见的实施非常简单。您只需要以与前瞻模式相同的方式处理前瞻中的模式,并按照惯例执行从左到右的匹配,除了在前瞻成功之后1)当前位置是在进入前瞻之前恢复到,并且2)内部前瞻中的选择点在匹配后被丢弃。

对于可以包含在内部预测中的内容没有限制,因为它是对现有自然左右匹配设施的非常简单的扩展。

向后看?不那么容易

另一方面,后视的实施并不是那么简单。

想象一下如何实现以下后视构造:

(?<=fixed-string)
(?<=a|fixed|string)
(?<=t[abc]{1,3})
(?<=(abc){2,6})
(?<=^.*abc.*)
(?<=\G"[^"]+");
(?<=^(.....|.......)+)
\b(\w+)\b(?<!\b\1\b.*\1)

除了基本情况(?<=fixed-string),任何后备实现必须支持,(?<=a|fixed|string)是一个非常理想的支持案例。

不同的正则表达式引擎对上面的正则表达式有不同程度的支持。

让我们看看它们是如何在.NET和Java中实现的。 (这是我研究过的两种风格。)

.NET implementation

在Microsoft .NET实现中,上面的所有正则表达式都是有效的,因为.NET通过使用从右到左模式实现后视,并在当前位置使用起始偏移量。后视构造本身不会产生任何选择点。

但是,如果你在后视中使用捕获组,它会开始变得混乱,因为模式中的原子是从右到左解释的,as demonstrated in this post。这是这种方法的缺点:在编写一个后视时,你需要把思路从右到左思考。

Java implementation

相比之下,Java正则表达式实现通过重用从左到右的匹配工具来实现后视。

它首先分析了后视内部的模式,了解模式的最小和最大长度。然后,通过尝试从左到右匹配内部模式,从(current position - minimum length)(current position - maximum length)来实现后视。

有什么遗漏?是!由于我们从左到右匹配,我们需要确保匹配在进入后视(current position)之前的位置结束。在Java中,这是通过在模式的末尾附加一个节点来实现的。

这种实现非常低效,因为在我们甚至讨论由后视图中的模式创建的选择点之前,在后视本身中创建了maximum - minimum + 1选择点。

后视边界检查也是低效的,因为它被放置在模式的末尾,并且不能修剪明显无望的选择点(那些已经远远超过模式中间的current position)。

Summary

如您所见,添加对后视镜头的支持并不容易:

  • 从右到左的方法似乎相当有效。但是,它需要对其他现有构造的从右到左匹配行为的额外规范。
  • 重复使用从左到右匹配设施的方法很复杂,而且效率很低。它还需要在规范中引入模式分析,以免性能被抛到窗外。

(注意,当在内部预测中使用后视时我还没有涵盖这种行为,反之亦然。在为后置构造定义语义时也应该考虑这一点)。

the mail引用的nils' answer中,Waldemar Horwat(编写ES3正则表达式规范)也提到了这些技术障碍:

目前还没有人提出明确定义的关于外观的提案。 Lookbehinds难以转化为规范所使用的语言,并且当正则表达式的部分评估顺序很重要时会变得非常模糊,如果涉及捕获括号则会发生这种情况。你从哪里开始寻找外观?最短的第一个,最长的第一个或反向字符串匹配?贪婪与否?回溯到捕获结果?

© www.soinside.com 2019 - 2024. All rights reserved.