Javascript使用哪种正则表达式算法用于正则表达式？

Question

我今天在阅读这篇文章的两个不同的正则表达式算法.

根据文章旧的Unix工具,如ed,sed,grep,egrep,awk和lex,都在他们的常规表达中使用所谓的Thompson NFA算法......

然而,像Java,Perl,PHP和Python这样的新工具都使用不同的算法来处理速度慢得多的正则表达式.

这篇文章完全没有提到Javascript的regex algorthim,(并且我知道那里有各种各样的JS引擎)但是我想知道是否有人知道他们使用了哪些算法,以及是否应该将这些算法换成Thompson NFA.

Answer 1

Javascript ECMA语言描述并未强制要求正则表达式的特定实现,因此部分问题的格式不正确.您真的很想知道特定浏览器中的特定实现.

Perl/Python等使用较慢算法的原因是,定义的正则表达式语言不是真正的正则表达式.真正的正则表达式可以表示为有限状态机,但正则表达式的语言是无上下文的.这就是为什么时尚只是称它为"正则表达式"而不是谈论正则表达式.

是的,实际上javascript正则表达式不是~~免费的~~常规内容.考虑使用`{n,m}'的语法,即从n到m接受的正则表达式的匹配.设d差d = | nm |.语法意味着存在可接受的字符串ux ^d w,但字符串ux ^{k> d} w不是.通过常规语言的泵浦引理,这不是常规语言.

(听说Thinko纠正了.)

无界x {3,}可以重写为xxxx*,这是常规的,可以用4个状态的DFA实现.请访问http://osteele.com/tools/reanimator/ (5认同)
关于{n,m}的"更新"是错误的.x {3,5}可以写成xxx | xxxx | xxxxx,这是完全正规的并且使用DFA引擎处理得非常好. (4认同)
你是正确的,JavaScript正则表达式不规则,但`{n,m}`语法不是原因,也不是证据.问题是你误用了泵浦引理.考虑常规语言{a}.它只匹配`a`.在你的答案中,同样的误用也是因为它不是常规语言.关键是语言*中的字符串uxⁿw*具有"n"*至少一些有限数*(抽取长度)可以用常规语言抽取 - *不是*只是任何字符串. (3认同)
实际上,它们比完整的正则表达式更多*.例如,"{n,m}"不能在FSA中表示任意n,m. (2认同)
@Bamieh：JavaScript正则表达式不是常规的-它们支持反向引用。NFA不能代表（a +）b \ 1。 (2认同)

Answer 2

虽然ECMA标准没有规定ECMAScript实现应该使用的算法,但标准要求ECMAScript正则表达式必须支持反向引用(\ 1,\ 2等)的事实排除了DFA和"Thompson NFA"实现.

反向引用排除了DFA（确定性有限自动机），但是还有其他方法可以解决该问题（例如，递归回溯）。Perl使用了记忆化的回溯递归，它消除了递归回溯的许多缺点（尽管在某些模式下仍会消耗大量内存）。 (2认同)