為什麼回溯會成為一個陷阱

回溯可以由可選的量詞或交替構造引起，因為正規表示式引擎將嘗試探索每條路徑。如果你對 aaaaaaaaaaaaaa 執行正規表示式 a+b 沒有匹配，引擎會很快找到它。

但是如果你將正規表示式更改為 (aa*)+b，組合的數量將會快速增長，並且大多數（非優化的）引擎將嘗試探索所有路徑，並將花費一個永恆的時間來嘗試查詢匹配或丟擲超時異常。這被稱為災難性的回溯。

當然，(aa*)+b 似乎是一個新手錯誤，但它在這裡說明了這一點，有時候你會遇到同樣的問題，但模式更復雜。

一個更極端的災難性回溯發生在正規表示式（你可能在這裡和這裡之前看到過 ），這需要指數時間才能發現一個包含 xs 的字串而沒有別的東西（例如 xxxxxxxxxxxxxxxxxxxx）與之匹配。

怎麼避免呢？

儘可能具體，儘可能減少可能的路徑。請注意，一些正規表示式匹配器不容易回溯，例如 awk 或 grep 中包含的那些，因為它們基於 Thompson NFA 。