尽管ECMA标准没有规定ECMAScript实现应使用的算法,但标准要求ECMAScript正则表达式必须支持反向引用(\1,\2等),这就排除了DFA和“Thompson NFA”实现。
{n,m}
语法并不是这个问题的原因,也不能证明。问题在于你错误地使用了“抽水引理”。以正则语言{a}为例,它只匹配字符a
。根据你回答中同样的误用,可以得出它不是一个正则语言的结论。关键在于:仅当语言中的字符串uxⁿw
(其中n
是某个有限的数值,即“抽水长度”)才能被“抽水”,这种语言才是正则语言 - 而非任意字符串。 - Ry-(a+)b\1
无法用NFA(非确定有限状态自动机)表示。 - Ry-Perl使用记忆化递归回溯搜索,并且在5.10版本的一些改进中,不再在perl -e '("a" x 100000) =~ /^(ab?)*$/;'
上崩溃。在我最近在OS X系统上进行的测试中,Perl 5.10在性能上甚至超过了awk
,即使在awk
算法本应该更好的情况下也是如此。