在Node / V8中如何实现正则expression式匹配?

我遇到过一篇文章 ,显示正则expression式匹配通常使用潜在的低性能algorithm与build议的Thompson NFAalgorithm实现。

考虑到这一点,如何在Node或V8中实现? 是否有可能使用Thompson NFA的JS实现来提高性能,也许如果只使用了有限的特性子集(可能会去除超前或其他“高级”特性)?

正如Chrome发展小组在本次发布中提到的那样,V8引擎使用了Irregexp正则expression式引擎:

下面是关于这个引擎的实现的一些引用:

我们在deviseIrregexp时做出的一个基本决定是,如果能够更快地运行它,我们将会花费额外的时间编译正则expression式。 编译期间,Irregexp首先将正则expression式转换为中间自动机表示forms。 这在很多方面都是“自然”且最容易理解的表示,并且使分析和优化正则expression式变得更容易。 例如,当编译/ Sun / Mon /自动机表示让我们认识到这两个选项都有一个'n'作为他们的第三个字符。 我们可以快速扫描input,直到find一个'n',然后开始匹配前面两个字符的正则expression式。 Irregexp提前查找四个字符,一次最多匹配四个字符。

优化后,我们生成本机机器码,使用回溯来尝试不同的select。 回溯可能非常耗时,所以我们使用优化来尽可能避免这种情况。 有些技术可以完全避免回溯,但JavaScript中正则expression式的本质使得它很难在我们的应用中使用,尽pipe这是我们将来可能实现的。

所以V8编译成本地自动机表示 – 虽然它不使用汤普森NFA。

就性能而言, 本文将V8正则expression式与其他库/语言进行比较。