作者colorless (colorless)
看板RegExp
标题[心得] 如何以糟糕的正规表示式使 nodejs, firefox, IE挂掉
时间Sun Mar 8 21:37:33 2015
二月底在做模板处理时，发现常常有 RegExp 卡住的状况，之後发现有时是因为要跑很久。
在 node, firefox, IE 三大引擎上跑都一样。
例如：
'012345678901234567890123456789;'.match(/^(?:[^;]*)*$/)
用人脑计算，这式子显然匹配不出结果；但电脑似乎还没足够聪明？
前面数字多添一点，跑出结果的时间会变长许多（呈天文数字成长？）。
看来只要 pattern 写得糟一点，确实是可能让 regular expression engine 挂掉不动的。
不过同样的式子，perl 的 engine 似乎就比较聪明，马上就跑出来了。
至於其 workaround，只好放弃一次完成，采用一个个 match。
以上例而言，就是一次次 .match(/^[^;]*/)，并侦测是否从头到尾都符合，直到完成。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.173.96.149
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/RegExp/M.1425821856.A.FFF.html
1F：推 LiloHuang: 这是相当常见的 Catastrophic Backtracking 问题 03/08 23:41
2F：→ LiloHuang: 时间复杂度至少会是 Exponential time complexity 03/09 00:14
3F：→ LiloHuang: 而 Perl 的 RegExp 引擎，具备有上述问题的侦测能力 03/09 00:15
4F：→ LiloHuang: 可在 Perl script 内，第一行加入 use re 'debug'; 03/09 00:16
5F：→ LiloHuang: 执行後可轻易观察出其匹配的规则，以及错误侦测的方式 03/09 00:17
6F：→ colorless: 感谢高手补充说明 :) 03/09 21:30
7F：→ carylorrk: 以前学 compiler 的时候都只教最简单的 DFA，感觉超有 03/12 01:34
8F：→ carylorrk: 效率，但是後来才知道实际上在用的复杂多了 03/12 01:35
9F：推 LPH66: DFA-based engine 不好写, 而且碰到这种状况状态数会爆炸多 03/12 18:40
10F：→ LPH66: (跟 NFA-based engine 的执行时间一样是指数成长) 03/12 18:41
11F：→ LPH66: 某种程度上其实可以说 NFA based 拿时间换空间 03/12 18:41