[心得] 如何以糟糕的正規表示式使 nodejs, firefox, IE掛掉

[colorless (colorless)]

二月底在做模板處理時，發現常常有 RegExp 卡住的狀況，之後發現有時是因為要跑很久。

在 node, firefox, IE 三大引擎上跑都一樣。

例如：

'012345678901234567890123456789;'.match(/^(?:[^;]*)*$/)

用人腦計算，這式子顯然匹配不出結果；但電腦似乎還沒足夠聰明？

前面數字多添一點，跑出結果的時間會變長許多（呈天文數字成長？）。

看來只要 pattern 寫得糟一點，確實是可能讓 regular expression engine 掛掉不動的。

不過同樣的式子，perl 的 engine 似乎就比較聰明，馬上就跑出來了。



至於其 workaround，只好放棄一次完成，採用一個個 match。

以上例而言，就是一次次 .match(/^[^;]*/)，並偵測是否從頭到尾都符合，直到完成。


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.173.96.149
※ 文章網址: https://www.ptt.cc/bbs/RegExp/M.1425821856.A.FFF.html
推 LiloHuang: 這是相當常見的 Catastrophic Backtracking 問題
→ LiloHuang: 時間複雜度至少會是 Exponential time complexity
→ LiloHuang: 而 Perl 的 RegExp 引擎，具備有上述問題的偵測能力
→ LiloHuang: 可在 Perl script 內，第一行加入 use re 'debug';
→ LiloHuang: 執行後可輕易觀察出其匹配的規則，以及錯誤偵測的方式
→ colorless: 感謝高手補充說明 :)
→ carylorrk: 以前學 compiler 的時候都只教最簡單的 DFA，感覺超有
→ carylorrk: 效率，但是後來才知道實際上在用的複雜多了
推 LPH66: DFA-based engine 不好寫, 而且碰到這種狀況狀態數會爆炸多
→ LPH66: (跟 NFA-based engine 的執行時間一樣是指數成長)
→ LPH66: 某種程度上其實可以說 NFA based 拿時間換空間