2010/3/2

[Regex] 進階群組建構

Regular Expression (規則運算式, 以下簡稱為 Regex) 實在不是一個易懂的課題; 但是, 如果我們要在一大堆文字裡面挑出部份具有特定規則的隻字片語, Regex 恐怕是我們唯一能用得上的工具

如果你並不了解 Regex 的基本概念, 本篇文章對你可能略嫌困難; 我建議你先關讀「[入門文章][Regex] Regular Expression 詳論

當你可以掌握 Regex 的基本原則之後, 如果你真的把它運用在生活中或工作上, 我相信你很快就會發現那些基本技巧的不足之處。舉個例子, 你可能已經寫好一個樣式 (如 "(?<phone>\b\d{7,8}\b)" ) 來從 "12341234 1111222" 字串中擷取出電話號碼。然而, 你可能在某天發現來源字串出現了奇怪的字: "12341234 (02)12345678", 此時, 你就非得修改原本的樣式。

由於來源文字的長相很難預測, 我們縱使經由冗長的分析而得到某個可用的樣式, 但這也只是暫時的; 你永遠不知道來源格式會不會被改變, 然後你就必須修改樣式。因此, 你遲早會需要學會 Regex 的進階技巧, 因為總有一天用得上。不過, 即使你已熟知所有 Regex 技巧, 但人算不如天算, 由於 Regex 再怎麼神奇, 也都是 rule-based 的運算而已, 甚至連人工智慧都稱不上, 所以永遠都有 Regex 解析不出來的複雜樣式。我們必須對於這一點有所認識。

在這裡, 我把 Regex 的「群組建構」功能 (Grouping Constructs) 從「[入門文章][Regex] Regular Expression 詳論 」一文中抽出來, 原因是這些功能並不是天天都用得上的, 篇輻又過於龐大, 放在「入門文章」裡實在頗嫌累贅。

關於「群組建構」功能, 如果你有興趣的話, 也可以同時參考中文 MSDN 或英文 MSDN 網站。我在本文中會儘量採用中文 MSDN 網站上的用語。

相符子樣式

(subexpression) - (Matched Subexpressions, 相符子樣式)

在樣式中, 以圓括號圈住的部份就是一個子樣式 (Subexpressions), 也稱為一個群組 (Group)。有時候我們並非刻意去捕抓這個群組, 但是因為使用圓括號圈住, 使得它也算做一個群組, 所以可以在 Match.Groups[n] 裡面找到。例如樣式 "(AB | CD)", 寫成這樣是因為語法如此, 而不是因為我們刻意要捕捉這個群組。但是它仍然算是一個群組。如果你不想在 Groups 中看到這個群組, 那麼可以使用下面提到的「不予擷取的群組」, 或者改用「具名相符子樣式」。

若使用 Match.Groups[n] 來列出捕捉到的群組, 它的編號順序會以從左到右的左括號做為基準。例如, 假設我們以 "(((((.+).+).+).+).+)" 這個樣式來檢測 "ABCDE" 這個受測字串的話, 找到的群組會像以下的樣子:

  • Groups[0]: ABCDE
  • Groups[1]: ABCDE
  • Groups[2]: ABCD
  • Groups[3]: ABC
  • Groups[4]: AB
  • Groups[5]: A

在這五個群組中, Groups[0] 一律會列出整個相符的字串。但是從 Groups[1] 開始, 捕捉到的就是 "(((((.+).+).+).+).+)" 這個相符子樣式(從左邊算來第一個左括號), Groups[2] 就是 "((((.+).+).+).+)" (從左邊算來第二個左括號)... 依此類推。你可以線上看看執行範例 http://rubular.com/r/OgNEfL6BKK (其中 Groups[0] 結果列在 "Match result" 文字框裡)。

接著, 你可以看看另一個執行範例 http://rubular.com/r/mGyEFhD2Ss, 仔細研究它的邏輯。

具名相符子樣式

(?<name>subexpression) - (Named Matched Subexpressions, 具名的相符子樣式)

在入門文章裡已經提過了, 就是給予這個群組一個名字; 我們也可以使用 ?'name' 來取代 ?<name> 這種寫法。

對稱群組定義

(?<name1-name2>subexpression) - (Balancing Group Definitions, 對稱群組定義)

如果前面已定義過 name2, 那麼這裡可以擷取出 name2 到 name1 中間的文字, 然後將它命名為 name1。如果你在式子中並未定義 name2 則會出現錯誤。以下我用一個範例來說明。例如輸入的受測字串為

<input id="ID" name="NAME" type="BUTTON" />

把 Regex 樣式定義為 (?<Quote>\")[^"]+(?<Text-Quote>\")

那麼我們就能擷取出 ID, NAME 與 BUTTON 三個符合 Text 群組的字。至於 Quote 群組, 雖然我們有定義它, 也有找到, 但並不會出現在結果中。換句話說, 這個範例中的 Quote 群組變成一個暫用的群組; 它只是被用來得到 Text 群組而已。

不予擷取的群組

(?:subexpression) - (Noncapturing Groups, 不予擷取的群組)

這個功能很單純, 只是讓括號括住的部份不列入 Group 而已。我個人認為本功能如同雞肋, 用得上的機會根本少之又少。不過由於 MSDN 對本功能的解釋過於簡單, 範例也舉得不好, 所以恐怕會令許多人感覺困惑。我使用白話說明一下好了。原本我們在 Regex 的 Pattern 中, 凡是使用括號括住的部份, 都會列入 Group 裡面, 之後我們就可以使用 Group[i] 逐個取出。然而, 如果你把一個括住的部份加上 ?: 符號, 那麼這個括住的部份就不會列入 Group[i]。

例如我們有一個 Pattern 如下:

(a(b*))+

如果 Match 的話, 你可以使用 Group[0], Group[1] 和 Group[2] 取出三個符合的群組。然而, 如果你把以上的式子改寫為:

(a(?:b*))+

那麼你只能取到 Group[0] 和 Group[1], 就不會有 Group[2] 了。

或許你會認為上述的例子也可以寫成 (ab*)+ 即可, 結果會是一樣的。不過你總會踫上遠比 b* 還要複雜的群組, 使得你不得不使用括號把它給括住; 如果你又不想列入 Group[i] 的時候, 就可以使用這一招。就像在這個範例, 你也可以把式子改成:

(?:a(?:b*))+

那麼就只有 Group[0] 存在, 其它都沒有了。當然, 對我個人而言是幾乎用不上這個功能的, 因為我習慣採用 Named Matched Subexpressions (也就是採用 ?<Name> 這種標注方法), 所以我除了測試之外, 根本不會去列舉 Group[i], 這就是為什麼本功能對我如同雞肋的原因了。

群組選項

(?imnsx-imnsx:subexpression) - (Group Options, 群組選項)

我們在建立 Regex 物件時可以指定其選項, 但我們也可以在 Pattern 裡的某個群組中強制開啟或關閉這些選項, 方法是透過 ?imnsx-imnsx 前置標注來達成。其語法如下

?X-Y

這裡 X 指的是要開啟的功能, 而跟在減號後面的 Y 則是要關閉的功能。這裡 X 跟 Y 可以代表數個不同的字元; 這些字元與其所代表的意義可以參考 MSDN。我把最常用的幾個列在下面:

  • i - 不區分大小寫 (case-insensitive matching, 預設為開啟)
  • m - 多行 (multi-line):
    設定多行模式後, ^ 與 $ 可以適用於每行的行首與行末 (但別期望它會認得 <br /> 或 <p> 這種 HTML 標記)
  • n - 擷取明確命名的群組 (Explicit Capture):
    凡是非以 ?<Name> 標注的群組將不予擷取, 也不列入 Group 集合
  • s - 單行 (single line):
    與多行相反; 不再將 \n 字元視為字與字的間隔符號
  • x - 略過 Pattern 中的空白字元 (ignore pattern whitespace, 預設為不略過):
    原本 pattern 中的空白字元等同於 \s, 如果開啟此選項則, 那麼你就必須明確的使用 \s 來代表空白字元(當然, 你也不能期望它認得 &nbsp; 這種標示)。不過我個人建議你忘記 Regex 有提供這種功能。你最好在該使用 \s 或 \t  的地方乖乖的使用 \s 或 \t, 否則最後可能會以混亂收場。

這些代表字元可以寫在一起, 像 ?mx 或 ?mx-is 等等。以下我舉幾個例子來說明。

假設受測字串為 "AB AC A D", 如果 pattern 為 "(a.)", 那麼在預設情況下會檢測不到任何東西, 但改成 "(?i:a.) 則會找到 "AB", "AC" 和 "A "。如果 pattern 是 "(?i:a .)" (注意這裡在 a 跟句點中間夾了一個空白), 則可以找到 "A D", 但如果改成 "(?ix:a .)" 則可以找到 "AB", "AC" 與 "A "; 但如果改成 "(?i-x: a .)", 那麼又只能找到 "A D"。

不過, 請留意不同的語言的群組選項有不同的實作方式, 例如 JavaScript 根本不支援這種群組。但是對於有支援的語言(.Net, Java, PHP, Ruby 等等), 總體而言差異並不大。

另外還有一個值得特別注意之處。如果你使用 RegexOptions 來設定樣式的選項, 那麼它對整個樣式都有效。但是如果你使用這裡介紹的 inline 群組選項的話, 該群組出現的位置會影響樣式的比對結果。例如, 如果你把 (?i) 寫在樣式的最前面, 那麼整個樣式都不區大小寫, 請看 http://rubular.com/r/8KiaorwpNc 這個範例。但是如果你把它寫在樣式的中間, 那麼它會從那個位置開始生效, 在它之前並不受影響, 請看 http://rubular.com/r/kWc9yyHq7Z 這個範例 (把樣式中的 "Ab" 改成 "ab" 就檢核不出來)。而且, 它的寫法有很大的彈性, 把樣式寫成 Ab\d+(?i)cd 也可以, 寫成 Ab\d+(?icd) 也可以; 但是寫成 Ab\d+(?i:)cd 就不可以了。

如果你既使用了 RegexOptions 來設定選項, 又使用了 inline 的群組選項, 那麼 inline 的群組選項具有較高的優先權。

非回溯子樣式

(?> subexpression ) - (Nonbacktracking Subexpressions, 非回溯子樣式, 也稱為窮盡 (Greedy) 子樣式)

根據中文 MSDN 的說明, 「子運算式會完全比對一次, 然後中止逐步的回溯 (backtracking)」; 看懂了嗎?

在繼續說明這個運算式之前, 我們先來看看這裡所謂的「回溯」是什麼意思。基本上, .Net 機制在解析樣式時, 它並不是一條路直挺挺走到底, 而是會視情況分解成樹狀路徑; 當走過一個節點之後, 會回到前一個分支, 再走另一個分岔路徑, 直到整顆樹都巡覽過一遍為止。像這種會回頭走另一條路徑的行為, 就稱為「回溯」(backtracking)。

現在假設我們有一個受測字串為 "001 2223 4444 55556", 我們先使用一個平常的 pattern 如下:

(\w)\1+(\w\b)

其用意是檢出開頭以一個以上的疊字方式出現 (即開頭的 "(\w)\1+" ), 後面再跟著另一個字元結尾 (即隨後的 "(\w\b)" ) 的字串。根據以上樣式, 我們可以檢出 "001"、"2223"、"4444" 和 "55556", 亦即受測字串中的所有子字串都全部被檢出。這裡我們可能會對 "4444" 產生疑義, 為什麼它也可以被檢測出來? 其實根據樣式, "4444" 可以被拆成 "444" + "4", 所以它為什麼不會被檢出?

但是, 如果我們把 pattern 改成非回溯子樣式:

(?>(\w)\1+)(\w\b)

那麼我們就只會檢出 "001"、"2223" 和 "55556" 而已, 其中的 "4444" 不會被檢出。為什麼? 因為我們在樣式的前半段 (即 "(?>(\w)\1+)") 已經指明它為非回溯子樣式, 而一旦被指定為非回溯子樣式, .Net 只會直接採用最多的匹配數量來評估一次而已 (即 "4444"), 而不會再把 "4444" 拆成 "44" + "44"、"444" + "4" 和 "4444" 來評估三次。在這裡, "4444" 雖然符合 (?>(\w)\1+) 這個子樣式, 但是這串字的後面並未再跟著任何字元以符合後面的 (\w\b) 子樣式, 所以最後就被評估為 No Match。相對的, 其它像 "001"、"2223" 和 "55556" 卻可以完全符合, 所以被評估為 Match。

所以如果我們剛好想要檢測出 aab, aaab 這種出現規則的字串, 而排除 aaaa 這種字串的話, 非回溯子樣式就是最佳選擇了。

邊界檢測群組

以下會列出幾個專做「邊界檢測」(assertion, 又稱斷字、斷言) 的群組。這幾個群組都是所謂「環顧」(Look Around) 群組, 意思就是做邊界檢查用的, 而不是用來擷取出什麼資訊。所以我們可以看到這些群組的名稱多半都有「無寬度」(Zero-Width) 這個字眼, 它們通常也不會被列入 matched groups 裡。

所謂的「邊界檢測」, 意思是專門用來檢查邊界的條件, 例如, 我們可以使用 \A 來檢查整個字串的起始位置, 用 ^ 檢查一行的起始位置, 用 $ 來檢查一行的結束位置, 用 \b 來檢查字的邊界條件, 諸如此類。但是如果邊界條件不是什麼文字邊界、行首、行末等等, 而是比較複雜的文字, 那麼我們就可以使用這些邊界檢測群組。

值得注意的是, 並不是所有語言都支持所有的邊界檢測群組, 例如 Ruby 在 1.8 以前並不支援。JavaScript 也不全部支援。幸好 .Net 是完全支援的。以下我會使用 Rubular 網站展示幾個範例, 使用的是 Ruby 2.0, 而且也不會展示 Ruby 和 .Net 不一致的地方。所以這些範例的用法和結果在 .Net 中應該是完全相同的。

無寬度右合子樣式

(?=subexpression) - (Zero-Width Positive Lookahead Assertions, 無寬度右合子樣式)

此功能在中文 MSDN 翻譯中稱為「無寬度右合樣判斷式」。你可能一開始看不懂這個翻譯, 但這個描述實際上是正確的。所有環顧群組的主要功能是用來做邊界的檢查, 而不是用在擷取(這就是為什麼這幾個群組被稱為「無寬度」)。在這種群組的左邊, 一定會跟著真正要擷取的樣式(如果沒有, 也不會發生錯誤, 只是使用 Group[i] 取不到任何結果而已; 你仍然能使用 IsMatch 取得檢測成不成功的資訊, 但是這麼做是沒有意義的 - 除非是運用在另一種應用的方法, 下面會再提到)。

我在下面會使用幾個 rubular.com 的線上範例。在其中幾個範例中, 如果你仔細觀查的話, 會發現網頁中會把符合之處反白, 但是這些反白處, 凡以邊界群組檢測出來的, 在受測字串中的對應位置其實並沒有空白字元。換句話說, rubular 會幫我們特別標示此種邊界檢查的符合處; 這實在是蠻貼心的功能。

此外, 我們要知道 Regex 的比對絕大多數都是從左往右進行的。所以如果我們一次就比對到最右邊之處, 那不就是把比對的動作「提前」進行了嗎? 所以所謂右合子樣式名稱中的 "Lookahead" 這個字就是這樣來的。同時, 這也就是為什麼我們稱之為「右合」的由來。此外, 稍後我們會談到 "Lookbehind" 和「左合」, 也是基於同樣的道理。

現在以範例來介紹無寬度右合子樣式。如果受測字串是 "ab22 cd33 eeff", 而 pattern 是 "(\b[a-zA-Z]+)(?=\d+\b)" (用意是找出所有以英文字母開頭, 以數字結尾的字, 但只取英文字元的部份), 那麼我們可以擷取出 "ab" 和  "cd" (分別在兩個 Match 中)。換句話說, "ab22" 和 "cd33" 雖然都符合整個 pattern, 但右合樣式(對應 "22" 與 "33")本身並不會被取出來。線上實作範例請見 http://rubular.com/r/8KbaIOY52Q

關於右合樣式還有另一種應用的方法, 剛好和上述寫法相反, 是把右合樣式寫在左邊。例如, 我們若使用 "\d{9,}" 作為 pattern, 我們會擷取出所有九位數以上的電話號碼。但如果我們只想擷取所有以 02 開頭的電話, 怎麼辦? 當然我們可以把 pattern 改成 "02\d{7,}" 即可; 但我們也可以使用右合樣式來做過濾, 亦即改成 "(?=02\d*)(\d{10})"。若採用後面的樣式, 那麼程式一開始便檢查字串中有沒有符合 "(02\d{10})" 樣式的子字串, 若有, 再從中擷取出這個子字串。線上實作範例請見 http://rubular.com/r/P939CLDkAR

無寬度右合樣式實在是一種很好用的工具; 雖然可能有人會堅持一定要去修改要擷取的 pattern, 但我卻寧可保持原始的擷取樣式不變, 而是把右合樣式一個一個疊加上去。例如在上例中, 我們使用 "(?=02\d*)(\d{7,})" 就可以濾出台北的電話, 但如果我要濾出台北跟高雄的電話, 怎麼辦? 很簡單, 加上去就好了:

"(   (?=02\d*)   |   (?=07\d*)   )   (\d{7,})"   <- 式子裡面的空白是不必要的, 只是為了容易看而已

換句話說, 你可以使用 "(  zwpla1  |  zwpla2 ) (pattern)" 這種寫法達到「或」的效果。至於個中巧妙就端看你怎麼搭配使用了。線上實作範例請見 http://rubular.com/r/OUbrY2E5FX

不過, 請注意 不管你把右不合子樣式放在左邊或是右邊, 請把它放在最左邊或最右邊(亦即最左邊或最右邊的群組)。如果你偏偏把它放在中間, 像是 "(\w*)\s*(?=ABC)\s*(\w*)", 那麼這個原本不應該被捕捉到的群組可能又會被捕捉到。請務必了解, 第一種用法(放在右邊)與第二種用法(放在左邊)使用在不同情境之下, 使用的樣式普遍上不同。所以除非你知道你在做什麼, 否則我建議你不要把無寬度右合子樣式放在兩個整個樣式的中間(以下的無寬度左合子樣式也是一樣)。

無寬度右不合子樣式

(?!subexpression) - (Zero-Width Negative Lookahead Assertions, 無寬度右不合子樣式)

剛好和上一個功能相反; 所以中文 MSDN 翻譯成「無寬度右合樣判斷式」, 意思是只有當此樣式不符合時, 才會繼續比對它右邊的其它樣式。至於用法和右合樣式一模一樣, 我就不再特別說明了。在上一個範例中, 如果我們想找出「台北以外」的電話號碼, 那麼就是這個功能可以辦到的。

無寬度左合子樣式

(?<=subexpression) - (Zero-Width Positive Lookbehind Assertions, 無寬度左合子樣式)

此功能在中文翻譯中稱為「無寬度左合樣判斷式」, 和「無寬度右合樣判斷式」使用方式類似, 只是兩者位於不同邊。例如, 如果有一個受測字串是 "1998 1999 2000 2001 2002 2009 0212345678", 我們要把裡面符合西元年度樣式的子字串挑出來, 但我們只要西元 2000 (含)以後的, 而且我們只取百位數以下的兩個數字, 這時候我們就可以採用左合樣式:

(?<=\b2)\d(?<ShortenYear>\d\d)\b

順利取出 "00", "01", "02" 與 "09"。在此例中, (?<=\b2) 代表位於左側、以 2 開頭的一個字元, 而藍色的 \d(?<ShortenYear>\d\d)\b 則代表三個數字字元結尾的字元(如 "001", 但只取右邊兩個字元 "01")。

跟右合樣式一樣, 左合樣式也有一種另類的用法, 也就是把它當作一個單純的檢驗式, 只不過這次它是放到右邊。現在假設有一個受測字串是 "8 AM 11 AM 1 PM 3 PM", 我們原本可以使用 (\b(?<Hour>\d{1,2})\s*(AM|PM)\b) 取出 "8 AM"、"11 AM"、"1 PM" 和 "3 PM", 但如果我們只想取下午的時間, 那麼我們就可以在它的右邊加上一個左合樣式:

(\b(?<Hour>\d{1,2})\s*(AM|PM)\b)(?<=\b\d{1,2}\s*PM\b)

如此, 我們就可以只取出 "1 PM" 和 "3 PM" 了。

無寬度左不合子樣式

(?<!subexpression) - (Zero-Width Negative Lookbehind Assertions, 無寬度左不合子樣式)

中文 MSDN 翻譯為「無寬度左合樣判斷式」, 和上一個功能恰恰相反。如果借用上面的那個例子 (受測字串為 "1998 1999 2000 2001 2002 2009 0212345678"), 我們可以使用以下的 pattern:

(?<!2)\d(?<ShortenYear>\d\d)\b(?<=\b\d{4}\b)

取出開頭不為 2 且符合四位數字格式的二位數年份: "98"、"99"。請注意我們在樣式最右邊加上了一個左合判斷式 (藍色部份) 以檢查是否為四位數的數字。如果你在式子中使用了左不合判斷式, 那麼你只能如上例般採用左合判斷式來做預先檢查, 而不能採用放在左邊的右合判斷式 (請參考上面對於 ?= 及  ?<= 兩種判斷式的說明); 這是值得特別注意之處。

在某些語言中 (例如 Ruby) 左合和左不合子群組都不允許使用變動長度的量詞 (例如 + * 等等), 換句話說, 這些語言的左合和左不合子群組中只能使用固定長度的樣式 (但是右合和右不合子群組倒是可以)。例如 "(?<=a*)" 這種樣式會引發編譯器錯誤, 例如這個線上範例: http://rubular.com/r/ehOMzRmhd5。把這個範例中的樣式裡的 (?<=a*) 中的星號拿掉, 就能正確執行了。所幸在 .Net 中並無這種限制。

應用時機與場合

了解上述四種邊界檢測群組之後, 如果你還不知道這四種檢測群組可以應用在什麼場合裡, 那麼我可以舉一個例子。基本上, 我們可以這樣用:

(不)符合左邊的樣式 + 真正要擷取的資訊 + (不)符合右邊的樣式

HTML 和 XML 標籤剛好很適合用來做示範。一個正規的 HTML 標籤就是一個 "<" 加上幾個字, 再加上 ">"。例如 "<b>"。所以用白話來說, 我們就可以檢測「左邊必須是 <」, 以及「右邊必須是 >」。以邊界檢測群組來做, 就是把 (?<=<) 放在式子的最左邊, 把 (?=>) 放在式子的最右邊。完整的式子如下:

(?<=<)\s?(?<OpenTag>[^ >]+)\s?(?<Content>[^\/>]*)(?<SelfClose>\/)?(?=>)

線上實作範例請見 http://rubular.com/r/oaWzDTABDA。在這個範例中, 我們可以一次取出 Open Tag、標籤內所有屬性, 以及 Self-Closing 字元。檢查取得的 Self-Closing 字元是否為 "/", 就可以判斷這個 HTML 標籤是否為 Self-closed。此外, 把取出的 Content 字串拿去分析, 就可以取得各個屬性。

不過, 憑良心說, 這個範例並非最好的範例。它只是容易示範而已。為什麼它不是最好的範例? 因為你可以把 (?<=<) 簡單地以 "<" 取代、把 (?=>) 簡單地以 ">" 取代, 結果相同。兩者的差別只是使用 "<" 和 ">" 的話, 會讓 Matched Groups[0] 連同 "<" 和  ">" 都一起取到而已。

沒有留言:

張貼留言