php正則之貪婪和非貪婪模式（正則的貪婪與非貪婪）

本文目錄一覽：

• 1、正則表達式之原理篇
• 2、正則表達式的貪婪模式和非貪婪模式,如何取div ,li 標籤的循環內容,採集別人網站的內容
• 3、正則貪婪模式vs非貪婪模式詳解
• 4、02-貪婪模式與懶惰模式（非貪婪模式）

正則表達式之原理篇

背景

       最近公司規範出來後，關於字符串不提倡用 “ + ”  進行拼接，於是自己寫了個function，利用正則表達式來進行匹配。對於正則表達式，之前不了解原理，每次要用的時候查一下，很浪費時間。

內容

基礎知識；

正則表達式引擎；

貪婪與非貪婪模式；

DFA與NFA引擎；

回溯機制及常見的回溯形式

基礎知識

1. 佔有字符：正則表達式匹配過程中，如果子表達式匹配到東西，而並非是一個位置，並最終保存到匹配的結果當中

2. 零寬度：只匹配一個位置，或者是匹配的內容並不保存到匹配結果中

一個字符，同一時間只能由一個子表達式匹配，而一個位置，卻可以同時由多個零寬度的子表達式匹配

3.控制權：正則表達式由左到右依次進行匹配，通常情況下是由一個表達式取得控制權，從字符串的的某個位置進行匹配，一個子表達式開始嘗試匹配的位置，是從前一子表達匹配成功的結束位置開始的（例如：（表達式一）（表達式二）意思就是表達式一匹配完成後才能匹配表達式二，而匹配表達式二的位置是從表達式一的位置匹配結束後的位置開始）。如果表達式一是零寬度，那表達式一匹配完成後，表達式二匹配的位置還是原來表達式以匹配的位置。也就是說它匹配開始和結束的位置是同一個

4. 元字符 

5. 反義元字符

6. 轉義字符：\  使元字符失去它的意義，僅代表其輸入中字符的意義

需要轉義的字符列表 \ * + ? | { [ ( ) ^ $ . # 和 空白

7. 重複限定符：匹配優先量詞，忽略優先量詞，即：貪婪與非貪婪

{n,}、 {n, m}、 {, m}、 ’+’ 、‘?’、 ‘*’

8. 字符類：[ ]，區分大小寫

9. 分支條件： |

10. 分組 ：（）指定子表達式，可限制多選項的範圍、將若干字符組合為一個單元、受問號或星號之類的量詞作用，例：(\d{1,3}){3}\d{3}

斷言；(?

11. 括號及反向引用：（子表達式一）（子表達式二）\1      此時括號作用為分組，它具有記憶的功能，即在正則表達式內部仍然能回憶上次匹配到的是什麼；\1、\2、\n 是用在正則表達式的匹配環節。在正則表達式的替換環節，則要使用像 $1、$2、$n 這樣的語法

12. 平衡組 參考

正則表達式引擎

有兩個主要特點：

1. 默認貪婪匹配；（ 貪婪匹配與非貪婪匹配 ）

2. 返回最先匹配到的結果

針對簡單的正則匹配進行分析，例：

        當把cat應用到“He captured a catfish for his cat”，引擎先比較c和“H”，結果失敗了。於是引擎再比較c和“e”，也失敗了。直到第四個字符，c匹配了“c”。a匹配了第五個字符。到第六個字符t沒能匹配“p”，也失敗了。引擎再繼續從第五個字符重新檢查匹配性。直到第十五個字符開始，cat匹配上了“catfish”中的“cat”，正則表達式引擎急切的返回第一個匹配的結果，而不會再繼續查找是否有其他更好的匹配

Rubular: 基於 Web 的 Ruby 正則表達式編輯器

貪婪與非貪婪（又稱惰性、懶惰等）模式

兩者影響的是被量詞修飾的子表達式的行為。

貪婪模式在整個表達式匹配成功的前提下，儘可能多的匹配；而非貪婪模式（只被部分NFA引擎支持）在整個表達式匹配成功的前提下，儘可能少的匹配。

匹配優先量詞（屬於貪婪模式的量詞）：

“{m,n}”、“{m,}”、“?”、“*”和“+”。

忽略優先量詞（匹配優先量詞後加上“?”：非貪婪模式的量詞）：

“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”

例：

源字符串：aa

正則表達式一：

正則表達式二：

DFA與NFA引擎（JS的正則引擎是NFA：非確定型有限自動機）

參考： 正則表達式引擎及其分類

DFA引擎：在線性時狀態下執行，不要求回溯（因此永遠不測試相同的字符兩次）；確保匹配最長的可能的字符串；因為只包含有限的狀態（？），所以它不能匹配具有反向引用的模式；並且因為它不構造顯示擴展，所以它不可以捕獲子表達式

傳統的NFA引擎：運行匹配回溯算法——以指定順序測試正則表達式的所有可能的擴展並接受第一個匹配項。因為傳統的 NFA 構造正則表達式的特定擴展以獲得成功的匹配，所以它可以捕獲子表達式匹配和匹配的反向引用。但傳統 NFA的 回溯使它可以訪問完全相同的狀態多次（如果通過不同的路徑到達該狀態）。因此，在最壞情況下，它的執行速度可能非常慢。因為傳統的 NFA 接受它找到的第一個匹配，所以它還可能會導致其他（可能更長）匹配未被發現

POSIX NFA 引擎：與傳統 NFA 引擎類似，不同點：在可以確保已找到了可能的最長的匹配之前，它們將繼續回溯（更慢）；並且在使用 POSIX NFA 時，您恐怕不會願意在更改回溯搜索的順序的情況下來支持較短的匹配搜索，而非較長的匹配搜索

例：

字符串： this is yansen’s dog

正則表達式： /ya(msen|nsen|nsem)/

NFA工作方式：先在字符串中查找 y， 然後匹配其後是否為 a；  如果是 a 則繼續查找其後是否為 m； 如果不是則匹配其後是否為 n (此時淘汰 msen 支分支)； 然後繼續看其後是否依次為 s,e； 接着測試是否為 n ，是 n 則匹配成功，不是則測試是否為 m 。為什麼是 m ？因為 NFA 工作方式是以正則表達式為標準，反覆測試字符串，這樣同樣一個字符串有可能被反覆測試了很多次！

DFA：從 this 中 t 開始依次查找 y ，定位到 y ，已知其後為 a ，則查看錶達式是否有 a ，此處正好有 a； 然後字符串 a 後為 n ，DFA依次測試表達式，此時 msen 不符合要求淘汰。 nsen 和 nsem 符合要求，然後DFA依次檢查字符串，檢測到 sen 中的 n 時只有 nsen 分支符合，則匹配成功！

由此兩種引擎是完全不同的工作方式：NFA以表達式為主導，更容易操縱；DFA以文本為主導（搜索更快）

回溯機制

引擎是如何來處理那些模糊的條件匹配？

從問題的某一種狀態（初始狀態）出發，搜索從這種狀態出發所能達到的所有“狀態”，當一條路走到“盡頭”的時候（不能再前進），再後退一步或若干步，從另一種可能“狀態”出發，繼續搜索，直到所有的“路徑”（狀態）都試探過。這種不斷“前進”、不斷“回溯”尋找解的方法，就稱作“回溯法”

–來自百度百科

本質上就是深度優先搜索算法：嘗試匹配失敗時的下一步通常就是回溯

JS中正則表達式會產生回溯的地方都有哪些呢？

常見的回溯形式

1.貪婪量詞

例：正則：/ab{1,3}c/

可視化形式

1. 沒有回溯的匹配：當目標字符串是”abbbc”時

匹配過程

2. 有回溯的匹配：當目標字符串是“abbc”時

匹配過程

上圖第5步有紅顏色（僅表示匹配不成功）：此時b{1,3}已經匹配到了2個字符“b”，準備嘗試第三個時，結果發現接下來的字符是“c”。那麼就認為b{1,3}就已經匹配完畢。然後狀態又回到之前的狀態（即第6步，與第4步一樣），最後再用子表達式c，去匹配字符“c”。當然，此時整個表達式匹配成功了；上圖的第6步，就是“回溯”

即：嘗試可能的順序是“從多往少”的方向去嘗試：首先會嘗試”bbb”，然後再看整個正則是否能匹配。不能匹配時，吐出一個”b”，即在”bb”的基礎上，再繼續嘗試。如果還不行，再吐出一個，再試。如果還不行呢？只能說明匹配失敗了

另一個清晰的回溯：

正則：/”.*”/

目標字符串：”acd”ef

省略了嘗試匹配雙引號失敗的匹配過程

其實“.*”最簡單但也是非常影響效率的

2.惰性量詞

雖然惰性量詞不貪，但也會有回溯的現象（為了整體匹配成）

正則表達式

目標字符串：”12345″

匹配過程

3.分支結構

分支也是惰性的，比如/Java|JavaScript/，去匹配字符串”JavaScript”，得到的結果是”Java”，因為分支會一個一個嘗試，如果前面的滿足了，後面就不會再試驗了。

分支結構中可能前面的子模式會形成了局部匹配，如果接下來表達式整體不匹配時，仍會繼續嘗試剩下的分支。這種嘗試也可以看成一種回溯：

正則表達式

匹配過程

雖然第五步沒有回到之前的狀態，但仍然回到了分支結構，嘗試下一種可能

總結：有回溯的過程，那麼匹配效率肯定比DFA相對低一些；別看匹配慢，但是編譯快而且還挺有趣

參考： 正則表達式的回溯機制

正則表達式的貪婪模式和非貪婪模式,如何取div ,li 標籤的循環內容,採集別人網站的內容

MTracer正則表達式驗證工具，一般好用，我是只下載了個這個玩了一會覺得上手挺簡單的，就推薦下。正則表達式工具下載地址：MTracer.rar（首先打開工具，在右邊有上下兩個輸入框，上面那個是輸入正則的，下面那個是輸入要匹配字符串的，上下內容輸入好以後，就可以單擊匹配按鈕了，如果覺得匹配ok的話，就可以直接單擊上面菜單的代碼生成，來生成你要的C#代碼，java代碼，Script代碼等等）比如我要匹配兩個標籤里的所有東西如asdawdsadwdasdmwioasdasd我要匹配兩個Div之間的東西，那麼就應該寫[/S/s]*注意，你用request對象去請求回來的頁面是帶有/r 、/n 、/t這些標籤的，所有你要學會如何去表示這些標籤，另外捕獲標籤的時候，你是否要最大限度的匹配還是要最小限度的去匹配,下面就說明下這兩種模式 貪婪模式 和 非貪婪模式 :在正則表達式的匹配次數後面再添加一個 ? 表示 非貪婪模式

常用的匹配次數有 *、{m.n}、+貪婪模式:表達式在可匹配可不匹配的時候，也是儘可能的 “要匹配”。

非貪婪模式表達式儘可能少的匹配，使可匹配可不匹配的表達式，儘可能的 “不匹配”。

如bdxxx taaaa

表達式A1： .*

結果： 匹配1次

表達式A2：.*?

結果：匹配2次

表達式B1：[/w/s/]{1,}?

結果：匹配2次去掉問號結果：匹配1次同理 將{1,}改＋ 也可以得到相同的匹配結果，好了今天就寫這麼多了，哪天有空了再寫寫

正則貪婪模式vs非貪婪模式詳解

作為開始，我們看看下面的正則：

我們本來預想上面會匹配得到 witch 和 broom 兩個字符串，運行上面的例子，卻發現結果只匹配到 “witch” and her “broom” 一個字符串。

之所以出現這個結局，是因為正則的貪婪模式在起作用。查找算法首先我們假設自己是正則引擎，來模擬搜索實現的過程。 正則引擎先從字符串的第0位開始搜索。 1. 第一個查找字符是 ” ，正則引擎在第三個位置匹配到了它：

. 代表任意字符重複一次到多次，因此正則引擎匹配到所有字符

當文本結束後，點的匹配停止了，但仍然有剩餘的的正則需要匹配，即： ”

因此，正則引擎開始倒過來回溯，換句話說，就是一個字符一個字符縮減匹配。

因此正則繼續縮減 . 所重複的字符，再繼續嘗試。

現在 ” 終於匹配上了。 如果正則是global的，正則引擎會從上次匹配結果之後繼續查找更多結果。

再看一個例子：

在這個例子中，因為 * 的存在，使得正則表達式具有貪婪屬性，操作模式同上，先匹配第一個 ” 找到了witch前的 ” ，第二步匹配 . ，因為可以代表除了行結束符和換行符號的所有符號，因此直接跳到文本結尾 e ，接下來匹配 ” ,找到 m 後面的 ” ,接着匹配 ” 後的空格，在匹配空格後的 a ，此時發現沒有，則失敗，重新尋找 ” ；最終匹配到 “witch” a 。

總結：在貪婪（默認）模式下，正則引擎儘可能多的重複匹配字符

非貪婪模式

非貪婪模式和貪婪模式相反，可通過在代表數量的標示符後放置 ? 來開啟非貪婪模式，如 ? 、 +? 甚至是 ?? 。

我們來看看非貪婪模式 .? 是怎麼運轉的。

下面是二者的重要區別。 正則引擎嘗試用 最小可能 的重複次數來進行匹配，因此在 . 匹配了 w 後，它立即嘗試 ” 的匹配

下面終於匹配上了

因為正則是global的，所以正則引擎繼續後面的匹配，從引號後面的 a 字符開始。後面有匹配到第二個字符串

總結：在非貪婪模式下，正則引擎儘可能少的重複匹配字符

（ 本文引用若愚老師博客，僅用於學習使用，特此聲明！ ）

02-貪婪模式與懶惰模式（非貪婪模式）

以字符串“daaadcccd”為源字符串作為栗子。

同理，除了”+”之外，帶 “*” 和 “{m,n}” 的表達式都是儘可能地多匹配，這種匹配原則就叫作 “貪婪” 模式 。

在修飾匹配次數的特殊符號（+、*、{m,n}）後再加上一個 “?” 號，就由貪婪模式變成懶惰模式。

以字符串“daaadcccd”為源字符串作為栗子。

舉例來講就可以明白，對於“daaadcccd”字符串“daaad”和“daaadcccd”都符合 (d)(\w+)(d) 正則，取最長的那個“daaadcccd”。而 (d)(\w+?)(d) 正則則取最短的那個“daaad”。

(d)(\w+) 和 (d)(\w+?) 也是同理。

以字符串“tdpaa/p/td tdpbb/p/td”為源字符串作為栗子。