What's Regular Expression? The Panacea of the Programming World.

一開始接觸編程嘅時候，我會注重Think Like a Computer，對我黎講就係點樣用手頭上有嘅資源去解決當前嘅問題。當我逐步邁入底層原理同應用實作時，會更常見到一啲需要利用文字規律的情況：例如編譯器如何認出編程語言中的關鍵字、用戶輸入時嘅資料驗證、Linux 主機上的 grep 指令、學習NLP時，電腦如何理解其他語言等。呢啲技術都指向咗 正則表達式 aka Regular Expression aka Regex。

Regular Expression

Regex 是一種文字規律表達的標記法（Notations）。它的應用層面很廣泛，就如前文提到的，只要有需要從大量文本中抽取特定規律的文字就能用上。由於我們生活上充滿著不同的語言，基本上所有的應用中都會有著讓電腦識別人類語言的硬需求，導致 Regex 不僅僅在單一系統或語言中被使用，而是成為了所有語言當中的必備元素。

以上圖片中，上方的輸入欄是regex的語法，透過 /rem/g 去表示我們想要獲取的文字。後面我們會提到其他的方法，除了用特定文字外，還能通過一些規律或標點符號去獲取。

Regex引擎

前文提到的 Regex 是一種標記法，要套用到應用上前先要經過引擎去編譯。而主要的引擎（或算法）是這兩種，確定有限狀態自動機 和 非確定有限狀態自動機。兩種方法都能夠用狀態圖來表示，由起始點狀態開始後，透過達成相對應的條件去到下一個狀態，重複直到達到終結狀態。又或是沒有達到終結狀態，結果為沒有找到 Regex 語法相對應的文字。

當一個Regex語法可以確定文字長度是就會使用 DFA，這樣就可以一個一個按順序去比較。當語法是有動態長度，例如電子郵件的格式：當中會有 @ 和 . 去分隔著名稱和郵件域名，而我們並不知道其他部分的文字會有多長時，則會使用 NFA。

確定有限狀態自動機 / Deterministic Finite Automata (DFA)： DFA 的特點是每一個字符都只檢查一次，寫好的Regex或壞的都不會影響到速度。由於不會測試相同的字元兩次，所以多於一個條件時會同時比較，缺點是需要更多內存。優點是時間複雜度是線性，所以比較穩定。
非確定有限狀態自動機 / Non-deterministic Finite Automation (NFA)： NFA 的特點是它可以使用回溯的功能，因為不像 DFA 可以確認文字的順序和長度，所以預設會使用 貪婪模式 去匹配字符，例如一個字元的長度是不確定是，會把通過所有過測試的字符。但當下一個指定字元比較不匹配時則要回溯到前一個字符和下一個標記法字元去比較。這個做法雖然功能更強大，但是時間複雜度會增加，壞做法時更會造成災難性回溯（catastophic backtracking）。

從上圖可以看到 DFA 的狀態圖是呈現線性的，而 NFA 則是呈現非線性。

Regex語法

Regex 的使用語法繁多，不過初學用可以分成四個類別去上手。學習時可以去regex101測試。

元字符 / Meta Characters：元字符是一些幫助配對的保留字符，可以用於指示目標字串的位置進行配對。
量記號 / Quantifier：也是一些保留字符，用於指示指定字符的長度。（一個或沒有、一個或多於一個等）
範圍 / Ranges：用數字或英文字去表示字符可配對的範圍。（注意是範圍不是數量）
字符集 / Character Sets：用類似轉義符號的做法，可用於表示配對字符的範圍，功能上跟範圍語法一樣。
轉義字符 / Escape Characters：當想配對的字符是保留字符時，則可以在字符前放置 \ 去表示要配對保留字符。

元字符

保留符號：. ^ $ * + ? [] | \ [^] ()

量記號

用法：* + ? {n} {n,} {n,m}

範圍

用法：[n-m]

字符集

用法：\s \S \0 \a \d \D \n \w \W \b

參考資料

https://pgrandinetti.github.io/compilers/page/where-compilers-use-regular-expressions/

https://www.circuitsjournal.com/archives/2021.v2.i2.A.23

https://www.tutorialspoint.com/natural_language_processing/natural_language_processing_introduction.htm

https://linuxize.com/post/regular-expressions-in-grep/#:~:text=grep%20is%20one%20of%20the,matching%20line%20to%20standard%20output

https://www.cnblogs.com/Renyi-Fan/p/9694695.html

https://segmentfault.com/a/1190000021787021

https://www.readfog.com/a/1658037048954687488

https://www.cnblogs.com/study-everyday/p/7426862.html

https://github.com/fooozhe/Regex-Learning/blob/master/regexp1.md