小議正則表達式效率 貪婪、非貪婪與回溯
更新時間：2011年04月12日 21:40:43 作者：
前幾天看了鳥哥的BLOG上寫的關于正則表達式的回溯與遞歸的限制時，對貪婪、非貪婪產(chǎn)生的回溯有疑問，遂近段時間，仔細的學習研究了一下，現(xiàn)在把經(jīng)驗心得與大家分享一下。
先掃盲一下什么是正則表達式的貪婪，什么是非貪婪？或者說什么是匹配優(yōu)先量詞，什么是忽略優(yōu)先量詞？
好吧，我也不知道概念是什么，來舉個例子吧。
某同學想過濾之間的內(nèi)容，那是這么寫正則以及程序的。
$str = preg_replace('%<script>.+?</script>%i','',$str);//非貪婪
看起來，好像沒什么問題，其實則不然。若
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
那么經(jīng)過上面的程序處理，其結果為
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+?</script>%i','',$str);//非貪婪
print_r($str);
//$str 輸出為 <script>alert(document.cookie)</script>
仍然達不到他想要的效果。上面的就是非貪婪，也有的叫惰性。其標志非貪婪的標識為量數(shù)元字符后面加? ，比如 +?、*?、??(比較特殊，以后的BLOG中，我會寫到)等。即標識非貪婪，如果不寫?就是貪婪。比如
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+</script>%i','',$str);//非貪婪
print_r($str);
//$str 輸出為 <script 只有這些了，好像還是不太合適，哈，您知道如何重寫那個正則嗎？
以上為貪婪，非貪婪的區(qū)別介紹。下面，聊下貪婪、非貪婪引起的回溯問題。先看個小例子。
正則表達式為\w*(\d+)，字符串為cfc456n，那么，這個正則匹配的$1是多少？？
如果您回答是 456,那么，恭喜你，回答錯了，其結果不是456，而是6，您知道為什么嗎？
CFC4N來解釋一下，當正則引擎用正則\w*(\d+)去匹配字符串cfc456n時，會先用\w*去匹配字符串cfc456n，首先，\w*會匹配字符串cfc456n的所有字符，然后再交給\d+去匹配剩下的字符串，而剩下的沒了，這時，\w*規(guī)則會不情愿的吐出一個字符，給\d+去匹配，同時，在吐出字符之前，記錄一個點，這個點，就是用于回溯的點，然后\d+去匹配n，發(fā)現(xiàn)并不能匹配成功，會再次要求\w*再吐出一個字符，\w*會先再次記錄一個回溯的點，再吐出一個字符。這時，\w* 匹配的結果只有cfc45了，已經(jīng)吐出6n了，\d+再去匹配6，發(fā)現(xiàn)匹配成功，則會通知引擎，匹配成功了，就直接顯示出來了。所以，(\d+)的結果是6，而不是456。
當上面的正則表達式改為 \w*?(\d+)（注意，此處為非貪婪），字符串仍然為cfc456n，那么，這時候，正則匹配的$1是多少？？
甲同學回答：結果是 456。
嗯，是的，正確，是456，CFC4N弱弱的問下，為什么是456 呢？
我在來解釋一下 為什么是456
正則表達式有條規(guī)則，是量詞優(yōu)先匹配，所以\w*?會先去匹配字符串cfc456，由于\w*?是非貪婪，正則引擎會用表達式\w+?每次僅匹配一個字符串,然后再將控制權交給后面的\d+去匹配下一個字符，同時，記錄一個點，用于在匹配不成功的時候，返回這里，再次匹配，也就是回溯點。由于\w后面是量詞是*，*表示0到無數(shù)次，所以，首先是0次，也就是\w*?匹配個空，記錄回溯點，將控制權交給\d+,\d+去匹配cfc456n的第一個字符c,然后，匹配失敗，于是乎，接著講控制權交給\w*?去匹配cfc456n的c，\w*?匹配c成功，由于是非貪婪，所以，他每次只匹配一個字符，記錄回溯點，然后再將控制權交給\d+匹配f,接著，\d+匹配f再失敗，再把控制權給\w*?，\w*?再匹配c,記錄回溯點（這時\w*?匹配結果是cfc了），再把控制權給\d+，\d+去匹配4，匹配成功，然后，由于量詞是+，就是1到無數(shù)次，所以，接著往后匹配，再匹配5，成功，再接著，再匹配6，成功，再接著，繼續(xù)匹配操作，下一個字符是n，匹配失敗，這時，\d+會吧控制權交出去。由于\d+后面已經(jīng)沒有正則表達式了，所以，整個正則表達式宣告匹配完成，其結果就是 cfc456, 其中第一組結果是456。親愛的同學，您明白剛剛的題目的結果，為什么是456了嗎？
好了，您是否從上面的例子了解了貪婪，非貪婪的匹配原理了？那您是否明白您在什么時候需要使用貪婪，非貪婪去處理您的字符串了？
鳥哥的文章里講到針對
表達式、程序為
$reg = "/<script>.*?<\/script>/is";
$str = "<script>********</script>"; //長度大于100014
$ret = preg_repalce($reg, "", $str); //返回NULL
其原因就是回溯太多了，直到造成耗盡棧空間爆棧。
再來看個例子。
字符串
$str = '<script>123456</script>';
正則表達式為
$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';
這三個正則，分別會造成幾次回溯呢？？
答案見下篇 PHP正則表達式的效率：回溯與固化分組
好吧，我也不知道概念是什么，來舉個例子吧。
某同學想過濾之間的內(nèi)容，那是這么寫正則以及程序的。
復制代碼 代碼如下:
$str = preg_replace('%<script>.+?</script>%i','',$str);//非貪婪
看起來，好像沒什么問題，其實則不然。若
復制代碼 代碼如下:
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
那么經(jīng)過上面的程序處理，其結果為
復制代碼 代碼如下:
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+?</script>%i','',$str);//非貪婪
print_r($str);
//$str 輸出為 <script>alert(document.cookie)</script>
仍然達不到他想要的效果。上面的就是非貪婪，也有的叫惰性。其標志非貪婪的標識為量數(shù)元字符后面加? ，比如 +?、*?、??(比較特殊，以后的BLOG中，我會寫到)等。即標識非貪婪，如果不寫?就是貪婪。比如
復制代碼 代碼如下:
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+</script>%i','',$str);//非貪婪
print_r($str);
//$str 輸出為 <script 只有這些了，好像還是不太合適，哈，您知道如何重寫那個正則嗎？
以上為貪婪，非貪婪的區(qū)別介紹。下面，聊下貪婪、非貪婪引起的回溯問題。先看個小例子。
正則表達式為\w*(\d+)，字符串為cfc456n，那么，這個正則匹配的$1是多少？？
如果您回答是 456,那么，恭喜你，回答錯了，其結果不是456，而是6，您知道為什么嗎？
CFC4N來解釋一下，當正則引擎用正則\w*(\d+)去匹配字符串cfc456n時，會先用\w*去匹配字符串cfc456n，首先，\w*會匹配字符串cfc456n的所有字符，然后再交給\d+去匹配剩下的字符串，而剩下的沒了，這時，\w*規(guī)則會不情愿的吐出一個字符，給\d+去匹配，同時，在吐出字符之前，記錄一個點，這個點，就是用于回溯的點，然后\d+去匹配n，發(fā)現(xiàn)并不能匹配成功，會再次要求\w*再吐出一個字符，\w*會先再次記錄一個回溯的點，再吐出一個字符。這時，\w* 匹配的結果只有cfc45了，已經(jīng)吐出6n了，\d+再去匹配6，發(fā)現(xiàn)匹配成功，則會通知引擎，匹配成功了，就直接顯示出來了。所以，(\d+)的結果是6，而不是456。
當上面的正則表達式改為 \w*?(\d+)（注意，此處為非貪婪），字符串仍然為cfc456n，那么，這時候，正則匹配的$1是多少？？
甲同學回答：結果是 456。
嗯，是的，正確，是456，CFC4N弱弱的問下，為什么是456 呢？
我在來解釋一下 為什么是456
正則表達式有條規(guī)則，是量詞優(yōu)先匹配，所以\w*?會先去匹配字符串cfc456，由于\w*?是非貪婪，正則引擎會用表達式\w+?每次僅匹配一個字符串,然后再將控制權交給后面的\d+去匹配下一個字符，同時，記錄一個點，用于在匹配不成功的時候，返回這里，再次匹配，也就是回溯點。由于\w后面是量詞是*，*表示0到無數(shù)次，所以，首先是0次，也就是\w*?匹配個空，記錄回溯點，將控制權交給\d+,\d+去匹配cfc456n的第一個字符c,然后，匹配失敗，于是乎，接著講控制權交給\w*?去匹配cfc456n的c，\w*?匹配c成功，由于是非貪婪，所以，他每次只匹配一個字符，記錄回溯點，然后再將控制權交給\d+匹配f,接著，\d+匹配f再失敗，再把控制權給\w*?，\w*?再匹配c,記錄回溯點（這時\w*?匹配結果是cfc了），再把控制權給\d+，\d+去匹配4，匹配成功，然后，由于量詞是+，就是1到無數(shù)次，所以，接著往后匹配，再匹配5，成功，再接著，再匹配6，成功，再接著，繼續(xù)匹配操作，下一個字符是n，匹配失敗，這時，\d+會吧控制權交出去。由于\d+后面已經(jīng)沒有正則表達式了，所以，整個正則表達式宣告匹配完成，其結果就是 cfc456, 其中第一組結果是456。親愛的同學，您明白剛剛的題目的結果，為什么是456了嗎？
好了，您是否從上面的例子了解了貪婪，非貪婪的匹配原理了？那您是否明白您在什么時候需要使用貪婪，非貪婪去處理您的字符串了？
鳥哥的文章里講到針對
表達式、程序為
復制代碼 代碼如下:
$reg = "/<script>.*?<\/script>/is";
$str = "<script>********</script>"; //長度大于100014
$ret = preg_repalce($reg, "", $str); //返回NULL
其原因就是回溯太多了，直到造成耗盡棧空間爆棧。
再來看個例子。
字符串
復制代碼 代碼如下:
$str = '<script>123456</script>';
正則表達式為
復制代碼 代碼如下:
$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';
這三個正則，分別會造成幾次回溯呢？？
答案見下篇 PHP正則表達式的效率：回溯與固化分組
相關文章
asp matchs函數(shù)提供了對正則表達式匹配的只讀屬性的訪問。一直都用這個函數(shù)，沒想到本站竟然沒有這類文章，汗一個，最近我會多加一些這樣的文章2008-08-08
這篇文章主要介紹了除捕獲組的語法外，其它的(?...)語法都不是捕獲組的驗證,需要的朋友可以參考下2017-04-04
本篇文章是小編日常整理有關js常用的正則表達式，比較全面，對大家學習javascript正則表達式非常有用，需要的朋友一起學習吧2015-09-09
正則表達式(Regular Expression)是一門簡單語言的語法規(guī)范，是強大、便捷、高效的文本處理工具，它應用在一些方法中，對字符串中的信息實現(xiàn)查找、替換和提取操作2017-10-10
這篇文章主要介紹了正則表達式驗證IP和端口格式的正確性，本文給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2020-01-01
由正則表達式如何匹配相同字符出發(fā)，講講正則表達式中的選擇、分組和引用，和牛逼的存在缺失很少遇到2019-10-10
今天在寫一個功能的時候，需要替換不包含指定字符串的正則，看到了一篇好文章特整理分享下，方便需要的朋友2014-09-09
該方法的返回值是布爾值，通過該值可以匹配字符串中是否存在于正則表達式相匹配的結果，如果有匹配內(nèi)容，返回ture，如果沒有匹配內(nèi)容返回false，該方法常用于判斷用戶輸入數(shù)據(jù)的合法性，比如檢驗Email的合法性2012-10-10
這篇文章主要介紹了JS 正則表達式從地址中提取省市縣的實例代碼，非常不錯，具有一定的參考借鑒價值 ,需要的朋友可以參考下2018-10-10
js判斷是否有6個連續(xù)數(shù)字的字符串的正則2009-09-09