二月底在做模板处理时，发现常常有 RegExp 卡住的状况，之后发现有时是因为要跑很久。
在 node, firefox, IE 三大引擎上跑都一样。
例如：
'012345678901234567890123456789;'.match(/^(?:[^;]*)*$/)
用人脑计算，这式子显然匹配不出结果；但电脑似乎还没足够聪明？
前面数字多添一点，跑出结果的时间会变长许多（呈天文数字成长？）。
看来只要 pattern 写得糟一点，确实是可能让 regular expression engine 挂掉不动的。
不过同样的式子，perl 的 engine 似乎就比较聪明，马上就跑出来了。
至于其 workaround，只好放弃一次完成，采用一个个 match。
以上例而言，就是一次次 .match(/^[^;]*/)，并侦测是否从头到尾都符合，直到完成。

这是相当常见的 Catastrophic Backtracking 问题时间复杂度至少会是 Exponential time complexity而 Perl 的 RegExp 引擎，具备有上述问题的侦测能力可在 Perl script 内，第一行加入 use re 'debug';执行后可轻易观察出其匹配的规则，以及错误侦测的方式

感谢高手补充说明 :)

以前学 compiler 的时候都只教最简单的 DFA，感觉超有效率，但是后来才知道实际上在用的复杂多了

DFA-based engine 不好写, 而且碰到这种状况状态数会爆炸多(跟 NFA-based engine 的执行时间一样是指数成长)某种程度上其实可以说 NFA based 拿时间换空间