首页 > 代码库 > js 正则学习小记之NFA引擎

js 正则学习小记之NFA引擎

原文:js 正则学习小记之NFA引擎

之前一直认为自己正则还不错,在看 次碳酸钴,Barret Lee 等大神都把正则玩的出神入化后发现我只是个战五渣。

 求抱大腿,求大神调教、

 

之前大致有个印象,正则有很多种引擎,但我根本不知道有哪些引擎。

今天在读《精通正则表达式》才发现有Traditional NFA,POSIX NFA 和 DFA (具体自己百度下吧)。
可用了这么久的正则,还不知道 js 属于哪一种呢。
在《精通正则表达式》里有个简单是方法检测属于哪一种。

/nfa|nfa not/ 去匹配 "nfa not"
如果匹配结果是 ‘nfa‘,那这个就是Traditional NFA(传统型NFA)了。
如果是 ‘nfa not‘,那有可能是 POSIX NFA 也可能是 DFA。

那我们先来试试这个正则吧。

"nfa not".match(/nfa|nfa not/);

得到的结果是 nfa,那么可以确定 js 的引擎是 传统型NFA 了。


如果是 ‘nfa not‘,那么要进行下一步测试来确定到底是 POSIX NFA 还是 DFA。
/X(.+)+X/ 去匹配 "==XX============================="
如果执行时间长,则是 NFA (Traditional NFA在上一步已经可以确定了)。
如果执行时间短,基本就是DFA,也可能是高级优化的NFA。
另外,如果执行时溢出,超时,那也可以肯定是 NFA 了。

我们来试试这个吧,

console.time(‘/X(.+)+X/ test‘);
"==XX=============================".match(/X(.+)+X/);
console.timeEnd(‘/X(.+)+X/ test‘);

/X(.+)+X/ test: 17300.000ms
天哪,一个小小的正则竟然匹配了17秒,我吓尿了。(这个结果跟电脑配置有关系,你的神机也许比我快N倍)

当然现在我还解释不了,只能先告诉你这个貌似是 NFA 引擎的回溯失控导致的。
所以才能用这个方法检测 NFA 和 DFA 了。

NFA 是 表达式主导引擎,DFA 则是 文本主导引擎,而我们已经得知了js是传统型NFA,那么之后我们就围绕这NFA深入学习了。

今天的分享就是这些了,我要去修炼了,明天继续分享。