作者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/m.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