正規表達式學習筆記

寫在前面：（一點題外話，點我跳過>>）

正如摘要裡面所說的，正規表達式是一個龐大的知識體系，不是簡單的一張元字元表，也不是幾句話能說清楚的

有人這麼評論，「...如果說在電腦發展至今的歷史上，出現過一些偉大的東西的話，正規表達式（Regular Expression）算一個，而 Web，Lisp，雜湊演算法，UNIX，關聯模型，物件導向這些東西也在此列，但這樣的東西絕對不超過 20 項...」

這麼說或許仍然不足以引起你的重視，因為雖然你也聽說過正規表達式，對著元字元表也能看懂現成的表達式，但在具體開發中卻很少用到正規表達式...

的確是這樣的，那麼，正規表達式還活著嗎？它去哪裡了？

答案是正規表達式已經滲入了我們的程式語言、作業系統及相關應用中，舉個例子，很多高階語言都會提供類似於 String.find() 這樣的方法，很多作業系統也會提供檔案內容檢索命令（如 Linux 的 grep 命令），這些都與正規表達式有關。

那麼，既然正規表達式已經「消失」（滲入）了，我們還有必要學習它嗎？當然有，正規表達式是一種技術，理解一種技術的意義要遠大於掌握一種工具。

目錄結構

1. 正規表達式工作原理

2. 正規引擎

3. 正規環視

4. 回溯

5. 正規表達式的優化

6. 如何寫出高效的正規表達式？

7. 幾個易錯點

8. 總結

9. 附表【元字元表】【模式控制符表】【特殊元字元表】

一. 正規表達式工作原理

一個正規表達式應用於目標字串的具體過程如下：

1. 正規表達式編譯

   檢查正規表達式的語法正確性，如果正確，就將其編譯為內部形式

2. 傳動開始

   傳動裝置將正規引擎「定位」到目標字串的起始位置

   P.S. 簡單解釋一下「傳動」，就是正規引擎內部的一種機制，例如，將 [abc] 應用到串 family 上，首先嘗試首位的 f，失敗，接著到第二位的 a，成功，匹配結束。注意，這個過程中是誰在控制這種「按位」處理（先第一位，失敗後嘗試第二位...）？沒錯，正是所謂的傳動裝置

3. 元素檢測

   正規引擎開始嘗試匹配正規表達式和文本，不僅有按位向前進行，還有回溯過程（回溯是一個重點，會在後面詳細解釋）

4. 得出匹配結果

   確定匹配結果，成功或者失敗，其具體過程與正規引擎的類型有關，例如找到第一個完全匹配的串就返回成功結果，或者找到第一個合格的串後繼續尋找，返回最長的合格串

5. 驅動過程

   如果在目前位置沒有找到合適的匹配，那麼傳動裝置會驅動引擎，從目前位置的下一個字元處開始新的一輪嘗試

6. 匹配徹底失敗

   如果傳動裝置驅動引擎到指定串尾，仍然沒有找到合適的匹配，那麼匹配宣告失敗（簡單點說就是，從頭到尾都沒匹配上的話就算失敗，這裡之所以描述得那麼艱澀，是為了更貼近其內部原理）

二. 正規引擎

所謂的正規引擎類型其實是一種分類，前面說過了，正規表達式是一種技術，所有人都可以運用它來解決問題，而大家解決問題的思路都不同，換言之就是正規表達式的具體實現都不同，規則各不相同。於是經過長期的發展，最終形成了一些流派，各個流派推行的規則不同。

常見的流派（正規引擎類型）有以下幾種：

1. NFA（中文是「非確定型有限自動機」，不用理會這奇怪的名字...）
2. DFA
3. POSIX NFA
4. DFA, NFA 混合型

我們不必知道各個引擎的分類標準是什麼，只需要明白相互之間的區別以及我們常用的工具所屬分類就好了，非常簡單：

1. NFA

   此類工具：Java, GNU Emacs, grep, dotNet, PHP, Python, Ruby 等等

   區別：NFA，我們可以稱之為正規表達式主導型引擎，因為其匹配效率與正規表達式密切相關（例如表達式中多選分支的順序）

2. DFA

   此類工具：awk, egrep, flex, lex, MySQL, Procmail 等等

   區別：DFA，我們稱之為文本主導的引擎，其匹配效率與文本（目標串）有關（等價但不同形式的表達式效率相同，例如 [a-d] 與 [abcd]，注意，在 NFA 中這兩者效率是不同的，一般來說前者更好一些）

3. POSIX NFA

   此類工具：mawk, Mortice Kern System's utilities 等等

   區別：無論匹配成功與否，都要嘗試所有可能，試圖找出能夠匹配的最長串

4. DFA, NFA 混合型

   此類工具：GNU awk, GNU grep/egrep, Tcl

   區別：此類引擎應該說是最好最成熟的，引擎內部優化做的相對完善，集 DFA 與 NFA 二者的優點於一身，但目前應用此類引擎的工具很少

說了這麼多，其實我們要知道的是：

使用一個支援 Regex 的工具之前，首先要知道它的引擎所屬類型，這是極其重要的，因為不同的引擎具體工作機制不同，比如，PHP 的三套正規庫都屬於 NFA 型，其匹配與表達式密切相關，所以我應該對表達式進行合理優化，以提高效率。

三. 正規環視（lookaround）

[其實這個東西沒有必要單獨列出來，因為它只是正規表達式很小的一部分內容，但鑑於一部分人不知道「環視」，也有一部分人聽過，但不了解，覺得這東西很高深...所以還是單獨拿出來討論一下（絕對不難）]

1. 什麼是「環視」？

單純理解漢字，「環視」就是向四周觀望，正規環視其實也就是這個道理——驅動到一個位置，先向左右看看���個位置是不是我們要找的位置

舉個例子，用 (this|that) 來匹配 there is a boy lying under that tree. 很明顯，這個表達式在 NFA 引擎下效率很低，它是這樣工作的：

1. 首先，遇到第一位 t，按位檢查 this，發現 i 與 e 不匹配，就按位檢查 that，發現 a 與 e 不匹配；
2. 驅動前進一位，到 h，按位檢查 this...按位檢查 that...；
3. 驅動前進一位，到 e，.......
4. 。。。

做了很多無用功，那麼要怎麼優化？

可以把前綴提取出來（常用的優化方式之一，後面有總結），變成 th(is|at)

當然，我們在這裡討論的是環視，就用環視來解決，變成 (?=th)(this|that)，哎呀，前面的 (?=) 看不懂怎麼辦？

沒關係，這個就是肯定順序環視，表示的意思是：我從開頭向後走，遇到 th 就停下來，比對 (?=th) 後面的表達式部分——(this|that)【注意，反之就是說如果沒遇到 th 就不停，直接向後繼續走...效率是不是有點變化呢？】

優化後比較的次數明顯降低，當然這裡用環視似乎有些大材小用了，我們只是舉個應用環視的簡單例子而已，不必較真

2. 正規環視的種類極其作用

類型	正規表達式	匹配成功的條件
肯定順序環視	(?=...)	子表達式能夠匹配右側文本
肯定逆序環視	(?<=...)	___________________左______
否定順序環視	(?!...)	子表達式不能匹配右側文本
否定逆序環視	(?<!...)	___________________左______

P.S. 上面的左右側指的是匹配進行的目前位置的左右側，這與一般的匹配不同，舉個例子：

用肯定順序環視 (?=a)abc 匹配串 family，初始位置是 f 的前面而不是 f 所在位置，為什麼會這樣？

因為【環視結構不匹配任何字元，只匹配文本中的特定位置】，如果目前位置是 f 與 a 之間的話，肯定順序環視匹配成功，開始按位檢測 abc。

我們發現：肯定順序環視能夠限制真正開始比較的位置，從而減少嘗試次數

3. 環視的應用

環視多用於表達式的優化，與其他一些特殊的場合（不用環視不行的場合，當然，一般來說，環視都可以用其他複雜一些的結構來代替）

例如，要匹配 the land blongs to these animals 中的單字 the，如何避免匹配到 these 中的 the？

我們很容易想到單字分界符（如果引擎支援的話），用 \bthe\b 進行全域匹配就可以了

其實針對此例，我們還可以用 the(?!\w) 來完成目標，前面的 the 即便匹配了 these 中的 the 也不要緊，後面的否定順序環視 (?!\w) 會將 these 排除（這裡的否定順序環視限定了 e 的後面不能是單字的字母，具體地說 \w 等價於 [a-zA-Z0-9]，在這裡或許不是很合適，但勉強能說明問題）

四. 回溯（在提及優化之前，回溯絕對是一個重點問題）

簡單地說，回溯就是倒退到未嘗試過的分支（或者是回到備用狀態，當然，對不熟悉正規表達式的人來說第一種說法更容易理解，而第二種說法則更確切一些）

舉個簡單的例子，用 .*! 來匹配串 "An idel youth, a needy age!", an old saying said.

1. 首先，* 修飾 . 可以匹配任意多個任意字元（點號表示任意字元，* 表示任意數量），而且 * 是匹配優先的（就是 * 會盡可能長地匹配串）
2. 所以 .* 匹配了整個串（從 A 到 .），這時檢測發現 ! 無法匹配了，怎麼辦？
3. .* 匹配的串必須交還一部分來讓 ! 有機會匹配，交還了句末的點號， ! 還是無法匹配
4. 繼續交還，這次是 d，無法匹配
5. 。。。
6. 到 age 後面的 ! 被交還，匹配成功

整個過程中從 .* 佔有整個串到被迫交還 ! 的時間裡，進行的動作就是回溯（簡單地說就是引擎的驅動在往回走）

類似這樣的回溯顯然是毫無意義而且浪費時間的，我們要做的大部分優化工作就是減少回溯次數。

從另一個角度看，減少回溯的作用是提高了匹配的效率，或者說是縮短了引擎從開始工作到回饋匹配結果（成功/失敗）的時間，這不正是優化嗎？

五. 正規表達式的優化

1. 效率指標

   考察一個正規表達式的效率，參考指標主要有兩個：嘗試（比較）次數與回溯次數

   在保證表達式正確性的基礎上，嘗試次數與回溯次數越少越好，次數少意味著能夠更快速地找到合適的匹配（或者更快速地回饋匹配失敗）

2. 優化操作

   優化操作有兩個方向：

   1. 加快某些操作

      這需要結合具體的引擎內部實現來考慮，例如，一般來說，在 NFA 引擎下， [\d] 要比 [0-9] 快， [0-9] 要比 [0123456789] 快

   2. 避免冗餘操作

      也就是精確限制，比如上面提到的正規環視的例子，對匹配開始位置加以限制，就能大大提高效率

      當然，做此類優化時需要權衡，如果花費了很大一部分時間用來限定位置，而匹配的效率卻下降了，那麼這樣的優化是不可取的

   要不要優化？優化到什麼程度？這都需要我們結合具體應用場景來權衡

3. 常用優化方法

   優化方法非常多，這裡只列舉出最常用的一些優化方法（有興趣的可以參考相關書籍）

   1. 消除不必要的括號

      在很多場合，添加 () 只是為了限定兩次的作用範圍，而不是為了擷取匹配文本，這時應該用非擷取型括號 (?:) 代替擷取型括號 ()，不僅能減少記憶體開銷，還能大大提高效率

   2. 消除不需要的字元組

      有的人習慣用 [.] 這樣的字元組來表示單個特殊字元，其實可以用 \. 來替換，類似的有 [\*] -> \\* 等等

   3. 避免反覆編譯

      這一點是說在其他工具中應用正規表達式時需要注意的，比如，用 Java 來將一個正規表達式應用到一串文本上，首先需要對正規表達式進行編譯，不同的正規表達式只需要編譯一次，所以編譯的部分不應該放在迴圈內部，以此避免反覆編譯，節省額外的時間

   4. 使用起始錨點

      這是應當養成的一個良好習慣，例如，大多數以 .* 開頭的正規表達式都可以在前面加上 ^ 或者 \A 來表示行或者段落的開頭，這樣做有什麼好處？

      在一些落後的引擎中，這樣的優化效果非常明顯，設想一下，如果 .* 對目標串進行一輪嘗試後發現沒有合適的匹配，那麼如果表達式前面沒有 ^ 或者 \A，那麼引擎要做的工作就是從目標串的第二個字元位置開始進行一輪新的嘗試...當然，很明顯這樣做沒有意義（我們很清楚地一輪匹配結束後匹配結果就出來了，根本不需要第 2 輪甚至第 n 輪）

      而一些發展比較成熟的引擎可以對這樣的表達式做自動優化，如果檢測到 .* 開頭的表達式前面沒有 ^ 或者 \A，引擎會自動為表達式加上起始位置標誌，避免無意義的嘗試

      對於我們而言，在 .* 前面加上起始標誌應當成為一個習慣

   5. 將文字文本獨立出來

      例如 [xx*] 比 [x+] 更快， x{3, 5} 沒有 xxxx{0, 2} 快， th(?:is|at) 比 (?:this|that) 快

六. 如何寫出高效的正規表達式？

寫正規表達式應當遵循以下步驟：

1. 匹配期望文本
2. 排除不期望的文本
3. 易於控制和理解
4. 保證效率，儘快得出結果（匹配成功/匹配失敗）

前兩點保證了表達式的正確性，後兩點需要在效率與易用性之間做出恰當的取捨，這就是寫正規表達式的原則

這裡有一句非常經典的話，基本可以說明一般原則——不要把孩子連同洗澡水一起倒掉

七. 幾個易錯點

1. [-./] 與 [.-/] 與 [./-] 的區別

   乍看好像沒什麼區別，其實第一個和第三個是等價的，表示目前位置上的字元必須是中劃線、點號或者斜槓

   第二個表達式是錯誤的，表示目前位置上的字元必須是從點號到斜槓之間所有字元中的任意一個（簡單地說就是這裡的 - 表示範圍，類似於 [a-z]），但明顯點號到斜槓之間存在什麼字元與字元集環境有關，如果是 Unicode 字元集，則會出現很多奇怪的字元，與我們的原意不符

   所以在字元組中使用 - 時，必須仔細查看 - 所處的位置，避免此類錯誤

2. ^ 在 [] 內外的區別

   ^ 在外面表示行的開頭，$ 表示行的末尾， ^ 在裡面表示「非」（[^...] 即所謂的排除型字元組）或者普通字元（[...^]）

3. [ab]* 與 (a*|b*) 的區別

   二者看似等價，其實存在一種特殊情況：前者能夠匹配 aba 而後者不能，除此之外，前者的效率要更高一些

4. 使用量詞修飾符（?+*）時的易錯點

   當存在嵌套使用的量詞時，應當仔細揣摩語義，避免造成迴圈（無限回溯），例如用 "(\\.|[^\\"]+)*" 來匹配文本中的連續雙引號部分，引號中的部分可以包括用反斜槓轉義的雙引號，這個表達式就會造成迴圈，幾乎永遠得不到匹配結果

   而存在量詞嵌套並不一定導致迴圈，總之，表達式中出現量詞嵌套時應當非常謹慎地對待

八. 總結

個人對正規表達式的看法是：

如果對正規表達式理解得不是很透徹，那麼儘量不要嘗試用正規表達式去解決複雜的問題（或者說是嘗試應用很長的正規表達式），因為其中存在的一些陷阱會讓你百思不得其解，構造一個完美的正規表達式需要相當縝密的思維，而在一般應用中，我們用程式進行串的匹配要更易於控制一些。

當然，也不是說儘量不要用正規表達式（不能因噎廢食），不得不承認在某些場合，正規表達式有著不可替代的神奇作用（例如從文本中提取 URL...）

而且，即便自己不用，也應該充分理解正規表達式，因為別人會用，所以我們總會遇到

### 引用匹配

一種不常見的用法，可以在正規表達式中引用已匹配的部分，示例如下：

// js code
var regex = /(\w{2,4}).+\1.+\1/i;
console.log(regex.test('qwer11qwe213234qw'));   // true
console.log(regex.test('qwer11qwe213234q'));    // false

用於檢測含有未知重複序列的串（只知道重複序列出現的次數，不知道重複序列具體是什麼），上例中的重複序列是 qw

九. 附表【元字元表】【模式控制符表】【特殊元字元表】

1. 元字元表（此處提供大多數工具共同支持的元字元）

元字元	名稱	含義
^	脫字元	表示行開始位置
$	美元符	表示行結束位置
.	點號	表示任意字元（一般不能表示行尾的 \n）
[]	字元組	表示括號中字元的任意一個（必須要匹配一個字元）
[^]	排除型字元組	表示除括號中字元外的任意一個字元（必須要匹配一個字元）
\char	轉義字元	表示 char 的另一種含義，例如 \^ 表示普通字元 ^ 而不再表示行開始位置
()	（擷取型）括號	表示量詞的作用範圍或者擷取匹配的文本（可以在反向引用中獲取擷取到的文本）
(?:)	非擷取型括號	與括號功能相同，但不擷取文本
?	問號	量詞，表示左邊的部分可有可無
*	星號	量詞，表示左邊的部分可以有任意多個（當然，也可以一個都沒有）
+	加號	量詞，表示左邊的部分至少出現一次，至多不限
{min, max}	區間	量詞，表示左邊的部分至少出現 min 次，至多出現 max 次
{num}	特殊區間	量詞，表示左邊的部分必須出現 num 次
|	豎線	表示或者，用來實現多選結構
\<	單字分界符	表示單字開始位置
\>	單字分界符	表示單字結束位置
\num	反向引用	表示第 num 個擷取型括號擷取的文本（括號計數是按照左括號出現的順序算的，注意嵌套括號）

2. 模式控制符表（此處提供一些模式控制符例子，在具體的工具中可能不同）

控制符	含義
i	匹配忽略大小寫
g	全域匹配，找出目標文本中所有能夠匹配的部分，預設只找出第一個
x	寬鬆排列，正規表達式可以分散到多行並且可以包含注釋
m	增強的行錨點模式，把段落分割成邏輯行，使得 ^ 和 $ 可以匹配每一行的相應位置，而不是整個串的開始和結束位置
s	點號通配模式，在此模式下，點號可以匹配任意字元（預設點號只能匹配除換行符外的任意字元）

3. 特殊元字元表（此處提供某些工具支持的特殊元字元）

元字元	含義
\d	數字，等價於 [0-9]
\D	非數字字元，等價與 [^0-9]
\w	數字及字母，等價於 [a-zA-Z0-9]
\W	非數字和字母，等價於 [^a-zA-Z0-9]
\s	空白字元，例如空格符、定位字元、進紙符、回車符、換行符等等
\S	非空白字元
\b	單字分界符，表示單字的開始或者結束位置
(?>...)	固化分組，不交還任何與之匹配的字元，例如 (?>\w+!) 不能匹配 Hi!
??與+?與*?與{min, max}?	忽略優先量詞，盡可能少的匹配內容（在能夠匹配的情況下只匹配最短的內容）
?+與++與*+與{min, max}+	佔有優先量詞，語義同固化分組

聲明，以上所有內容來自筆者對參考書籍內容的理解

參考書籍：《精通正規表達式》（Jeffrey E.F Friedl 著）

書評：這本書在章節進度安排、內容穿插強調，甚至排版方面都很不錯（特殊的排版方式：書中提出的所有思考問題，都必須翻一頁才能看到答案），對於深入理解正規表達式很有幫助，有興趣的朋友可以參閱