JavaScript使用哪种正则表达式算法来处理Regex？

Question

我今天阅读了这篇文章，介绍了两种不同的正则表达式算法。

根据这篇文章，旧的Unix工具如ed、sed、grep、egrep、awk和lex在其正则表达式中使用的是所谓的Thompson NFA算法...

然而，像Java、Perl、PHP和Python这样的新工具都使用一种不同的算法来处理它们的正则表达式，这种算法要慢得多。

这篇文章没有提到Javascript的正则表达式算法（是的，我知道有各种JS引擎），但我想知道是否有人知道它们使用的是哪种算法，以及是否应该将这些算法替换为Thompson NFA。

- leeand00

Answer 1

尽管ECMA标准没有规定ECMAScript实现应使用的算法，但标准要求ECMAScript正则表达式必须支持反向引用（\1，\2等），这就排除了DFA和“Thompson NFA”实现。

- Jan Goyvaerts

---

反向引用规则排除了确定性有限自动机 (DFA)，但还有其他解决问题的方法 (如递归回溯)。Perl 使用记忆化回溯递归，可以消除很多递归回溯的缺点（尽管在某些模式下仍会占用大量内存）。 - Chas. Owens

另外，一个简单的优化方法就是先检查正则表达式是否是“真正”的正则表达式，如果不是，则只使用较慢的算法。这很明显，但我希望得到一个回应，看看浏览器实现是否真的会这样做。 - Peter Gerdes

Answer 2

Javascript ECMA语言描述并未对正则表达式的特定实现提出要求，因此问题的这一部分不太完整。你真正想知道的是特定浏览器中的特定实现。

然而，Perl/Python等使用较慢的算法的原因是，所定义的正则表达式语言并不是真正的正则表达式。真正的正则表达式可以表示为有限状态机，但正则表达式语言是上下文无关的。这就是为什么流行的方式是只称之为“regex”，而不是谈论正则表达式。

更新：

事实上，javascript regex并不是上下文自由的。考虑使用`{n,m}`语法，即匹配从n到m个接受的regexs。设d为差值d=|n-m|。该语法意味着存在一个可接受的字符串`ux^dw`，但不存在一个可接受的字符串`ux^kw`，其中k>d。根据正则语言的泵引理，这不是一个正则语言。

（已更正）

- Charlie Martin

---

实际上，它们不仅是普通正则表达式。例如，“{n，m}”无法在任意n，m的FSA中表示。 - Charlie Martin

关于{n，m}的您的“更新”是错误的。 x{3,5}可以写成xxx | xxxx | xxxxx，这是完全正则的，并且可以在DFA引擎中完美地处理。 - Jan Goyvaerts

不加上界限的 x{3,} 可以重写为 xxxx*，这是一个正则表达式，可以用具有 4 个状态的 DFA 实现。在 http://osteele.com/tools/reanimator/ 上尝试一下吧。 - Jan Goyvaerts

你说得对，JavaScript的正则表达式并不是真正的“正则”，但{n,m}语法并不是这个问题的原因，也不能证明。问题在于你错误地使用了“抽水引理”。以正则语言{a}为例，它只匹配字符a。根据你回答中同样的误用，可以得出它不是一个正则语言的结论。关键在于：仅当语言中的字符串uxⁿw（其中n是某个有限的数值，即“抽水长度”）才能被“抽水”，这种语言才是正则语言 - 而非任意字符串。 - Ry-

JavaScript正则表达式并不是"regular"（规则的），因为它们支持反向引用。(a+)b\1 无法用NFA（非确定有限状态自动机）表示。 - Ry-

Answer 3

Perl使用记忆化递归回溯搜索，并且在5.10版本的一些改进中，不再在perl -e '("a" x 100000) =~ /^(ab?)*$/;'上崩溃。在我最近在OS X系统上进行的测试中，Perl 5.10在性能上甚至超过了awk，即使在awk算法本应该更好的情况下也是如此。

- Chas. Owens