[Regular Expression]正規表達式教學，使用狀態機輔助說明-基礎篇

感謝設計師 Elim 大大幫忙

#**目錄**
##**一、前言**
##**二、極度懶人包**
##**三、Regular Expression 介紹**
##**四、基礎語法介紹**
##**五、練習用習題**
##**六、資料來源**

# 一、前言
最近被要求幫同事上課(OS: 壓力山大QQQ)，為了不讓自己上課沒材料，同時讓部落格有新文章之外，其實也沒啥目的，主要就是把最近學習到關於 Regular Expression(正規表達式)的內容好好記錄下來，在學習過程中發現這玩意兒，其實不只是工程師的工具，也可以是一般人都能以掌握且在日常生活中使用到的，雖然我不曉得什麼時候用得到，但確實 Regular Expression 會出現在許多地方，為此盡可能簡化入手難度而寫出這系列教學，比較屬於工程師的內容還是有，沒相關知識者不去看也沒差ＸＤ。

# 二、極度懶人包
下方為沒有時間，習慣於一邊吃飯一邊看影片的人們使用，關於這邊文章中所要提到的知識以及操作。

# 三、Regular Expression 介紹

## 1.什麼是 Regular Expression？
Regular Expression(正規表達式)又可簡寫為 Regex，他不是新的東西，而是大家早已會的技能，他是語言，也可以說是程式語言，也有人會說他是強大的工具，這些都是對的，只是大家又不同的角度去看待 Regex，而有不同的心得，Regex 在數學上是狀態機，電腦實作中是採用樹狀結構方式實現，也因為他是程式語言，就代表是可以被維護，被實作，被重寫的，因此每次在寫新的 Regex 同時，用對待其他語言的方式對待他，就不會覺得他是麻煩而且難以學習的新事物了。Regex 是各位早已熟悉的東西，早已熟悉的存在。

```
狀態機補充
狀態機是表示有限個狀態以及在這些狀態之間的轉移和動作等行為的數學模型。Regex 中 為判斷接收到的事件是否滿足，如果滿足則移動到下一個狀態，直到整個狀態機滿足為止。
```
```
樹狀結構補充
舉例來說這組 Regex 規則這樣寫 /(ab+c)* + aca/，在樹狀結構表示如下圖所示
當中優先度為
| 大於 +*? 大於 () 大於 [] 大於 abc 大於 range([a-z]) 大於 縮寫(\w) 大於 空白(\s)
大概就是這樣。
```

## 2.什麼時候使用 Regex ？
其實會使用 Regex 的場合大家早就在使用，最普遍來講就是搜尋，在 Excel 中找尋特定數字，在網頁中尋找特定文字，再任意地方找尋特自文字......等，簡單來說，平常在電腦上按下 ctrl + F 的地方都可以使用 Regex，而且他也早就存在在那，例如下圖所示

網頁開發者工具右上角

IDE當中

Google文件中

只是之前我們不知道他所以不會用它ＸＤ，就如同之前所說， Regex 是各位早已熟悉的東西，早已熟悉的存在。生活中不是缺少 Regex，而是缺少發現（誤）。

## 3.為什麼使用 Regex ？
Regex 存在在各個地方，Java, .NET, python, Perl...等，不只是程式語言中可以使用，日常生活中使用到 ctrl + f 的地方也可以用到，上一段的圖片已經證明了，這意味著 Regex 不是限定在程式上面，而是可以被普羅大眾掌握的技能，Regex 是學一次，哪裡都可以用(learn once use anywhere)，這種效益不是超高的嗎ＸＤ，而且撰寫 Regex 也可以讓你嚇嚇旁邊不會的同事或是朋友ＸＤ，最重要的是 Regex 可以幫你省下時間，在你要找尋的東西越複雜且越大量時，這種感覺越明顯。

## 4.常見問題
這邊列出幾個常見的問題，待我們走過之後的學習，相信這邊的問題，各位都是可以迎刃而解的，甚至比之前不用 Regex 時要簡單許多，也不是說一定要學才會解，而是學完後，可以有不同的解決方式，而且通常比之前輕鬆不少。

• 身分證字號=>我想知道特定縣市中(例如：花蓮桃園台南嘉義）的男生或是女生數量。
• email=> 為阻擋對手成長，我想要阻止特定的hostname在我的服務中被使用。
• 電話=>我想知道這台電信交換機底下的特定號碼是否已經被註冊。
• 檔案名稱與延伸檔名=> IMG_XXX.jpg 轉乘 IMG_XXX.PNG
• HTML=>請告訴我特定tag中的內容
• URL=>https://foobar-maybe:7181/path/to/index.html，幫我抓出這段網址的 port以及 address。
• 幫我抓出這系列 youtube 的檔案連結。
• DTOS=>幫我把這份檔案中所有的數字轉成字串

#四、基礎語法介紹
## 工具介紹
開始學習之前，我得先介紹一下這次所需使用到的工具人[Regex101](https://regex101.com/)，這網站除了不會即時把狀態機表現出來之外，其他提供的功能已經滿足我們的需求了，接下來的內容皆是基於 PCRE 編譯版本，所有有些語法若與你熟悉的有些出入，請不要過於驚慌，至於這網站的使用方式與介紹請參閱下張圖表 。

Regex101 解說

如果圖片＋文字說明還是不懂的話，這裡也有錄製影片幫助各位瞭解如何操作這個網站來學習 Regex 。

廢話這麼多，讓我們開始學習如何使用 Regex 吧！

##Match Character(配對字元)
先讓我從簡單的地方開始吧，先從配對字元開始，假設我們有一組 email 帳號，如下所示

• hangxiu1013@gmail.com
• hengxiu1013@gmail.com
• hingxiu1013@gmail.com
• hongxiu1013@gmail.com
• hungxiu1013@gmail.com

我們想要抓出其中 gmail 的字樣，在 Regex 中，我們需打上
```
/gmail/
```
在 / / 中範圍內的為 regex 規則，也就是我們欲找尋的規則，接著讓我們點開[連結](https://regex101.com/r/P1pSz4/24)，看看實際中是如何被使用的，各位可以看到在email 當中有找到 gmail 的地方都會被顯示出來，各位可以嘗試看看輸入/com/其他的規則來了解運作方式。

## Match Number(配對數字)
我們如果要找數字的話，也可以輕鬆反推就是打上
```
/ 要找的數字 /
```
例如說/2017/ 或是 /1013/，我們一樣透過連結來了解在實際應用中的樣子 [這個連結](https://regex101.com/r/P1pSz4/26)，相信目前為止都是十分直覺的，因為跟過去在找文字沒啥不同ＸＤ

### Match Character 與 Match Number 在狀態機上的表現
為了徹底了解 Regex 的運作機制，我們一定得要了解 Regex 在狀態機中的表現方式，在上述的例子中，我們想找到 / gmail /，在理解上不是找到 gmail，而是找到 g 再來 m 再來 a 再來 i 再來 l ，只用寫的實在很難表達完整ＸＤ，我們還是來看圖吧～


如同圖片中的 Node0 接收到事件 g 後，往 Node1 移動，Node1 接收到事件 a 後，往 Node2 移動，以此類推，直到全部配對成功，同理可以應用於上述的 /1013/ 中，而如果 NodeN 接收不同的事件時，狀態機就會倒退回去，倒退回去的動作稱為 backtrack，例如說 在 Node1 時，接收到事件 K，則此時會啟動 Backtrack回去到 Node0，Backtrack的觀念到了 Loop 時會再提一次，只是希望大家記得配對成功與失敗狀態機會有的行為，之後重要例子中也會帶有狀態機，請諸位不用擔心：）

## Match Character set（配對集合)
如果 Regex 只有這樣那就大材小用了，我們知道一個一個配對的運作方式了，那我們想要配對的是一個集合的呢？ 繼續用上面的 email 做舉例，[點我開啟連結](https://regex101.com/r/P1pSz4/26)，email 中我們可以發現帳號只差在第二個字元aeiou，但我又不可能一一去輸入規則/hang/、/heng/這樣，為此 Regex 提供了集合概念的語法，在 regex 中我們在集合的語法為 [ ]，這次要求中我們輸入
```
/[aeiou]/
```
如此一來就是配對說屬於 aeiou 這集合中任一個的就算ＯＫ，點[我開啟連結](https://regex101.com/r/P1pSz4/27)觀看語法使用方始與解釋。

###  Match Character set 在狀態機上的表現
如上述所敘，這是集合的表現，因此在狀態機中的表現是很好推的，如下圖所示。
![h[aeiou]ng](https://imgur.com/N9B1B8K.png)
一開始 Node0 接收到事件 h 後，往 Node1 狀態移動，接著收到的事件如果是集合[aeiou]中任一個才往 Node2 移動，這邊請各位留意的是，圖中對於狀態機的跑法，是先從先上方開始跑起，在這例子中就是會先判斷是 a 再來 e......，這樣去跑。

## Match Not in Range (配對集合以外)

在掌握強大的範圍後，我們也會想，這集合內的不一定會是我要的，也有可能是我不要的，
這時候只要替 Regex 寫上規則 [^] 就樣就可以了，例如說
```
/[^a-z]/
```
這表示所有小寫英文字母我都不要，只要這集合以外的，在實際應用中如 [這個連結](https://regex101.com/r/P1pSz4/28)，這裡我先偷渡了範圍的觀念

## Abbreviation(縮寫)
有很多情況不會如同上述的那麼簡單，例如說在身分證字號驗證時，你會期望開頭第一個字一定要大寫，這時候你可能會寫下 [ABCDEFGHIJKLMNOPQRSTUVWXYZ]，如此長的規則，但只為了做一件事情"找到大寫英文字母"，由於這是很常見的想法，因此在 regex 幫你簡化成 / [A-Z] /，這樣就可以了，數字也是相同 / [0-9] /，而英文數字及＿也經常使用到所以出現 / \w / 的縮寫字，這個不是要 match w 也不是要 match \w ，而是與 / [A-Za-z0-9_] / 同義，數字也有縮寫字 / \d /，由於是集合，所以也有集合外的語法，只要改成大寫就可。
```
/[A-Za-z0-9_]/ 同義於 [\w] /
/[^A-Za-z0-9_]/ 同義於 [\W] /
/[0-9]/ 同義於 [\d] /
/[^0-9]/ 同義於 [\D] /
```
各位可以在[這個連結](https://regex101.com/r/P1pSz4/29)來測試上述的規則。

## Match any(配對任何)
這是 Regex 中最懶惰的配對方式 / . /，就是個點ＸＤ，他的效果是配對任何字元，也就是 any 的概念，例如說 / ... /，這樣就是幫我配對任意三個字元，注意到，這個是任意字元，不是代表字母或是數字，而是連同特殊字元也都進去了，點開[這個連結](https://regex101.com/r/P1pSz4/30)，了解運用方式與解析。

## Quantifier：？/*/+/{}
OK，感謝各位看到現在，我們已經建立了 Regex 相當的基礎，如果閱讀到此處已經累了，可以小休息一下，我們接著要講重複的概念了，在loop中以下幾種表達方式

### a. ?: 表該配對可有可無
有些時候，有些字元我們不確定他會不會存在，例如說 Https 或是 Http，就差在那個 S，這時候規則可以寫 / https? /，這代表說 s 這個規則可有可無，是 optional 的，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/31)<<

#### Quantifier 中 ? 在狀態機上的表現
先從簡單的開始講起，我們用/a?/為舉例，/a?/代表 a 可有可無，如下圖所示
Node0 可以在不收到事件 a 情況下往 Node1 狀態移動，收到事件 a 時，有會往 往 Node1 狀態移動。

我們沿用上面的 /https?/ 畫圖，如下圖所示，相信各位應該能夠明瞭在前面的例子中的配對機制。

### b. *: 表該配對為零次或一次以上 (Zero-to-many)
許多時候我們對於字的要求不只是不一定存在，甚至是很多存在，例如基因排序，或是電話號碼使用，規則/ ac* /表示說一定要配對 a ，至於是否配對 c 就不一定，如果 c 出現一次以上才會配對，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/32)<<

#### Quantifier 中 * 在狀態機上的表現
如同前面所說， / a* / 代表 a 要配對零次或一次以上，如下圖所示
Node0 可以不用收到事件 a 就往 Node1 狀態移動，或是收到一個以上事件 a 之後，直到不是 a 再往 Node1 移動，也就是 a、aa、aaa，這三種情況都會成功，每一次配對失敗的時候呢，就會從該 Node 退回去上一個 Node，這個退回去的動作稱為 backtrack，backtrack 的觀念在後面的 Greedy, Lazy, and Possessive quantifier 很重要。

我們沿用上面例子來畫圖，如下圖所示，相信各位應該能夠明瞭在前面的例子中的配對機制。

### c. +: 表該配對為一次或一次以上 (One-to-many)
基本上和 + 相同，是基於使用的情境不同而有所不同，規則/ ac+ /表示說一定要配對 a ，c 則是要出現一次以上才會配對，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/33)<<

#### Quantifier 中 + 在狀態機上的表現
如同前面所說， / a+ / 代表 a 要配對一次或一次以上，如下圖所示
Node0 收到事件 a 後，移動到 Node1 ，之後同 * 的狀態，收到零個或是多個 a 後，移往 Node2

我們一樣沿用上面例子來畫圖，如下圖所示，相信各位應該能夠明瞭在前面的例子中的配對機制。

### d. {3}: 表該配對需重複 3 次
這是表達重複特定的次數，例如說我想找到文章中出現 brabrabra 的字眼，所以給他規則 / (bra){3} /，這裡我提早導入了 capture 的概念，他還有更多用法會在後面說明，這個規則表示說 (bra) 這組配對方式要出現3次的我才配對，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/34)<<

#### Quantifier 中 {number} 在狀態機上的表現
如同前面所說，/ a{3} / 代表 a 要收到3次，如下圖所示，node 0 收到3次事件 a 之後才往 node1 移動。

我們一樣沿用上面例子來畫圖，如下圖所示，相信各位應該能夠明瞭在前面的例子中的配對機制。

### e. {2,5}: 表該配對至少 2 次，至多 5 次
那這個應該不難理解了，/ (bra){2,5} /表示說 (bra)這組配對方式出現2次或是到5次的都可以配對起來，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/35)<<

#### Quantifier 中 {min,max} 在狀態機上的表現
如同前面所說，/ a{2,5} / 代表 a 要收到至少2次，至多5次，如下圖所示
Node2 要收到至少 2 次 a 之後才可往 Node3 移動，期間收到 3,4,5次也可以往 node6 移動，如果到第 6 次，就不算這次配對。

## or(或)： / cat|dog /
or 語法應該很直覺你想的那樣，因此我要直接帶你看例子以及狀態機了，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/36)<<。

### 狀態機上的表現
從上圖中你可以很明顯看到，當 Node0 接收到 c 或 d 之後才往下移動到 Node1 或 Node4，以此類推之結束，這是相當直覺的概念。

## Group(群組) and Name Capture: / I love (cat|dog)/
終於可以講到這個語法啦！雖然前面有偷用但是都沒有講解，主要是怕建立觀念是亂掉，所以才放比較後面的，如果悟性高或是有類似經驗的朋友，應該在前面看過用法後，就大概能推出一二了，如同這標頭寫的 Group，指將配對包起來，拿上面或的範例好了，如果缺少()的話，規則就會變成/I love cat|dog/，變成是配對 I love cat 或者 dog ，這很明顯跟我們要的想法不同，所以我們把 cat, dog 包起來，這樣就會在電腦中去做額外處理了。[點我開連結](https://regex101.com/r/P1pSz4/37)了解詳情

什麼？你說 Name Capture 沒解說到，好吧，這是我的失誤，Name capture 是指當你用 () 把特定範圍文字包起來之後，如果後續有配對成功的話，就會給你 group N 或是 Match N 用來表達，每圈出一個()就會有新的 Group，然後跟你說這是第幾個配對成功的結果，所以 ()，也可以用在抓出特定範圍文字，例如這次例子中我們想知道到底是愛貓還是愛狗，我們再回傳的結果中就會知道。

順帶一提，這裡是可以替群組命名的，在群組前面打上 ?<你要的命名>，這樣就可以了，這個使用在後面的維護以及管理上會有很大的幫助，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/38)<<。

## Boundary(邊界)
後面的主題基本上會使用的話，可以提高搜尋的精準度，降低搜尋時間，當然前面的語法都會的話，就已經很夠用了。

### Start|end of the line (換行符號前與後): /^edge\$/
這個語法是判斷說前面是不是 \n ，也就是經過換行(鍵盤上的 enter)，這樣就會是那一行中的第一個字，例如說找到開頭是 T 的，就在 Regex 規則打上 /^T/，這樣就會去配對出來，若是想找到換行前最後一字，通常是句點吧，就在 Regex 規則打上 /。$/，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/12)<<

### Word-boundary(搜尋規則邊界): /\b edge \b/
我覺得相比上面的規則，這個會比較實用啦，因為這語法不會限定說一定要在頭或是尾巴，只有配對到，而且邊界判定有成功的就可以成功，這個需要多練習幾次才會抓到感覺，後面的 Lazy 以及 possessive 也會有類似的感覺，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/14)<<。

## Lookahead and LookBehind
離最後的最後就剩下一點點啦！接下要要介紹的語法是看前看後（ＯＳ：要用成中文來說好難呀！），直覺上就是辨別出欲配對的前面或是後面的條件設置，例如說：想找出'file_XXXXX'中file_後面的字眼，我們替 Regex 規則寫上 /(?<=file_)\w+/，其實規則還滿好記的，先記住 ? 表固定語法, = 表等於, != 表不等於, ?< 表前面文字，如此一來就有四種表達方式 (?=), (?!=), (?<=), (?<!=)，在實際應用中如下連結 >> [這個連結](https://regex101.com/r/P1pSz4/21)<<，相信你已經注意到了，連結中的註解寫法以大量的改變，這個寫法我們會在實作篇補述完成。

## Greedy, Lazy, and Possessive quantifier
終於來到基礎篇的最後了，在這裡我們要講述關於配對與循環的問題，在前面的語法介紹中，大家已經認識到 .(any) 與 *(zero-to-many) 這兩個語法，那他們放在一起就是配對任何可有可無的字元，這時期很強大但同時也很懶惰，必要時盡可能把這種組合改寫掉ＸＤ，他們不是你的好朋友。

例如說這個[例子](https://regex101.com/r/P1pSz4/22)，我們想配對出頭是 a 尾巴是 t ，不管中間是什麼字元的規則有多少個，然後在最下面的配對中，雖然也找到了，然而卻是從第一個 a 到最後一個 t 都配對成功ＸＤ，想當然這樣只有配對成功一個而已，這很明顯不是我們要的，這時候我們需要 Lazy 的手段，不要讓 regex 一次配對這麼多只要求最小限度的即可，這也是他被稱作 Lazy 的由來，也被稱為 Non-greedy，我們只要替 regex 規則加上 ? 即可，延續上面[例子](https://regex101.com/r/P1pSz4/23)，看到差別沒有，我們最後回傳了 8 個結果而不再是一個了。

這裡我們是改變了狀態機中使用 backtrack 的機制，先上原本沒有使用 Lazy 的狀態機圖
這是我們熟悉的 Loop 在狀態機的表現，Node0 接收到 a 前往 Node1，Node1 接收到 any 或是無前往 Node2，Node2 接受到 a 之後前往 Node3，最後配對成功。這期間如果有失敗的地方一樣 backtrack。

這是後來有用到 Lazy 的狀態機圖
注意到 any 的地方是比較慢判斷的了嗎？前面有提過圖中狀態機的順序是由上而下，所以在這張圖裡面 Node1 會是接收到無或是 any 之後移往 Node2，因此會變成 at, a..t, aat, atttt，這種都會配對成功，只要能夠先滿足條件直接配對成功，這就是 Lazy(non-greedy)。

Possessive 是個給詭異的語法，我到現在還不曉得什麼時候會去用它ＸＤ感覺是個因為可以存在所以存在的語法，簡單來說，他就是原本 Greedy的用法，但是不具備 backtrack 機制，也就是說，一定要通通符合，而且配對圖中有錯誤的話就不找了ＸＤ，在 Regex 語法中為 / *+ / 替原本的 Quantifier 加上 + 即可。

# 五、練習用習題
恭喜你已經具備了 Regex 的基本知識了，接下來我們就直接拿題目來練手吧，回到一開始介紹的地方，我們曾提及過幾個現實生活中的問題，關於身分證字號, email, HTML...... 等議題，請依一點開下方的練習來做練習與與嘗試吧，有想查的使用規則，就直接使用網站右下方的 sheet 做查詢吧。

出題篇.[配對身分證字號](https://regex101.com/r/Dyi5q9/3)
解篇.[身分證字號](https://regex101.com/r/Dyi5q9/5)

出題篇.[配對電子郵件](https://regex101.com/r/Dyi5q9/6)
解篇.[電子郵件](https://regex101.com/r/Dyi5q9/7)

出題篇.[配對 HTML 格式](https://regex101.com/r/Dyi5q9/8)
解篇. [HTML 格式](https://regex101.com/r/Dyi5q9/9)

出題篇.[配對特定檔案名稱與格式](https://regex101.com/r/Dyi5q9/10)
解篇.[特定檔案名稱與格式](https://regex101.com/r/Dyi5q9/11)

出題篇.[配對 URL](https://regex101.com/r/Dyi5q9/12)
解篇.[URL](https://regex101.com/r/Dyi5q9/13)

出題篇.[配對電話號碼](https://regex101.com/r/Dyi5q9/14)
解篇.[電話號碼](不想寫了)

這邊提供出題篇以及解篇範本供各位發想，你可以使用在任何學習 Regex 的場合，例如說：某個講座、某堂課程、某場會議、同學間互丟練習的場合、同事間相互學習的地方，你也可以把覺得不錯的題目留言至下方，讓大家相互觀摩各種寫法。

出題[Template](https://regex101.com/r/Dyi5q9/1)
解篇[Template](https://regex101.com/r/Dyi5q9/2)

# 六、資料來源
**看cheat sheet 的地方**
[1.LogicBig](http://www.logicbig.com/tutorials/core-java-tutorial/java-regular-expressions/regex-possessive-quantifiers/)
[2.Rexegg](http://www.rexegg.com/regex-quantifiers.html)

**互動式教學網站**
[1.Regexone.com](https://regexone.com/lesson/optional_characters)

**線上編譯環境**
[1.Regex101](https://regex101.com/)
[2.Regexr](https://regexr.com/)

**繪製狀態機工具網站**
[1.Debuggex](https://www.debuggex.com/)
[2.可看狀態機彩色版本](https://jex.im/regulex/#!embed=false&flags=&re=%5E(a%7Cb)*%3F%24)
[3.有點數學](http://hackingoff.com/compilers/regular-expression-to-nfa-dfa)
[4.簡單狀態機](https://regexper.com/#abc%7Cabx)
[5.目前最棒的 DFA+NFA! 但是支援有限](https://rawgit.com/msnak14909/reviz/master/sample/page/index.html)
[6.看起來很有希望](http://ivanzuzak.info/noam/webapps/fsm_simulator/)
[7.手動繪製狀態機](http://madebyevan.com/fsm/)

**樹狀結構**
[1.Regex_Coach](http://www.weitz.de/regex-coach/)
[2.隨手找到的 slide](https://www.slideshare.net/VolhaBryl/ld4ie2014-v5)
[3.學校案例介紹](http://cs.geneseo.edu/~baldwin/csci342/fall2012/0921re2nfa.html)