真實世界的 Regex，以及理論在何處止步

收束這一階梯：你現在握有什麼

這一階梯交給你一套小而完整的代數。一個正規表示式由幾個基底情形搭起——字母表裡的符號、空字串 epsilon（長度為零的字串）、以及空語言——再用恰好三個運算黏合：聯集（在兩個模式之間做選擇）、串接（一個模式接著另一個）、以及克林尼星號（零次或多次重複）。配上優先順序（星號結合得最緊，其次是串接，再來才是聯集）與用來推翻它的括號，每個表示式都恰好命名了唯一一個字串集合——也就是它所表示的語言。而代數恆等式讓你在不改變語言的前提下改寫表示式，就像 2+3 與 3+2 命名同一個數。

接著就是那塊拱心石。克林尼定理說，這些表示式並不是比前幾階的機器更弱或更強的記號——它們描述的恰好是同一個類別：正規語言。而且雙向都是建構式的。要把 regex「變成」機器，你用了湯普森構造，把一個個用 epsilon 黏起來的小零件拼起來，一個運算配一塊。要把機器「變回」regex，你在廣義 NFA上用了狀態消去法（或等價地，用阿登法則像解代數一樣解狀態方程）。Regex、NFA、DFA：三張臉，一種威力。

從搜尋框到詞法分析器

除了定理之外，為什麼要在乎？因為這是整個自動機理論裡最常被使用的想法。每當你敲入一個搜尋模式、驗證一個電子郵件欄位、或 grep 一份日誌檔，你都是在寫一個正規表示式，而一個 regex 引擎正把它編譯成一台機器、再讓那台機器掃過你的文字。這個引擎就是把克林尼定理變成了產品：它拿過表示式，建出一台 NFA（湯普森）或一台 DFA，然後一個符號一個符號地把字串餵進去。你學到的那套乾淨數學，字面上就是引擎蓋下的實作策略。

最重要的工業用途，是每個編譯器的第一個階段：掃描器，或稱詞法分析器。原始碼到來時是一長串字元，在任何東西能剖析它之前，詞法分析器必須把它切成語彙單元（token）——這一團是個數字、那一團是關鍵字 `while`、這個是識別字、那個是加號。每一種 token 都由一個正規表示式描述（一個整數大致是 `digit digit*`，一個識別字是 `letter (letter | digit)*`），詞法分析器產生器把它們全部併成一台大 DFA，那台 DFA 沿著輸入飛奔，在單一一趟線性掃描中決定每個 token 的邊界。這就是 regex 最美好的樣子：一個宣告式的模式被編譯成一台機器，運行時間與輸入長度成正比，沒有任何意外。

Token rules (regular expressions)        Merged DFA scans the stream:
  NUMBER  ->  d d*                          input:  while x = 12
  ID      ->  L (L | d)*                              | | |  | | | |
  WHILE   ->  w h i l e                      tokens: WHILE  ID(x)  '='  NUMBER(12)
  PLUS    ->  +
  ASSIGN  ->  =                              one left-to-right pass, linear time
      (d = digit, L = letter)                longest match wins at each step

微縮版的詞法分析器：每一種 token 都是一個正規表示式；它們合起來編譯成一台 DFA，在單趟線性掃描中把原始碼切成 token。

教科書裡的那個物件在哪裡止步

這裡有個誠實的轉折，沒人在你入門的第一週告訴你：程式語言裡的 `regex` 並不是這一階梯裡那個正規表示式的同一個物件。工程師們不斷加上方便的功能，而其中有幾個悄悄地離開了正規的世界。最有名的是反向參照：像 `(.+)\1` 這樣的模式說的是「先匹配某段文字，再匹配那段一模一樣的文字一次」。這要求記住一段任意長的先前子字串並重現它——而這正是有限自動機沒有的那種無界記憶。你學過的有限記憶體極限禁止了它，所以反向參照無法被編譯成任何 DFA。它們描述的語言完全落在正規類別之外；它們只是借用了「regex」這個名字。

還有第二個、更痛的意外：速度。許多引擎並不去建那台來自克林尼定理的乾淨 DFA；它們改用回溯式搜尋，因為反向參照需要它。在大多數模式上這沒問題，但在某些模式上它會引爆。經典的陷阱長得像 `(a*)*b`，把它跑在一長串沒有結尾 b 的 a 上：引擎在承認失敗之前，會嘗試把這串 a 分配到那些巢狀星號之間的天文數字種方式，運行時間於是爆炸——常常隨輸入長度呈指數增長。這就是災難性回溯，而單單一個壞模式作用在攻擊者可控的輸入上，就曾經凍結過真實的線上伺服器。

認清你手裡握的是哪一種 regex

實用的教訓是：在腦中把兩個盒子清楚地分開。在「理論」盒裡：聯集、串接、克林尼星號、基底情形——這一階梯所搭起的整個世界。任何只用這些寫出來的東西都會編譯成一台有限自動機，運行時間與輸入成線性關係，永遠不會爆炸。在「工程」盒裡：那個核心，加上各種簡寫（字元類、加號與問號運算子、錨點），再加上那些逃逸者（反向參照）。簡寫純粹是方便、仍停留在正規範圍內；反向參照則悄悄越界，可能把你拖進回溯的泥沼。

問問你的模式需要什麼。如果它從不需要回憶並重現先前的文字，它就活在正規世界裡——安全又快速。
如果你伸手去用反向參照，停一下：你已離開了正規語言，DFA 再也撐不住你了。很多時候，一小段真正的程式碼能把這件事做得更清楚、也更安全。
面對不受信任的輸入時，優先選用以湯普森／DFA 方法打造的引擎（其最壞情況是線性的），而非天真的回溯器，並避免在相同字元上巢狀套用星號，例如 (a*)*。
拿不定主意時，就用對抗性輸入測試（又長又重複、幾乎匹配卻又差一點的字串），而不只是測那些順利的情形。

向階梯上方望去

退一步，看看這單單一層伸得多遠。你現在能讀或寫一個正規表示式，並精確知道它命名的字串集合；你能把它轉成自動機、再轉回來；你明白為什麼詞法分析器很快，又為什麼反向參照根本不正規。也請記得自 DFA 那一階梯就成立的那道邊界：「正規」並「不」等於「有限」——a* 與 Sigma-star（字母表加星號）都是無限的，卻完美地正規——而反過來，正規語言仍被有限記憶體圈在牆內。

那道牆，正是接下來的階梯要去推撞的對象。那個著名的例子 `a^n b^n`（n 個 a 後面跟著 n 個相配的 b）需要無界地計數，而沒有任何有限機器——也沒有任何正規表示式——能做到。要「證明」這樣的語言不正規，你會遇見幫浦引理，它是喬裝過的鴿籠原理；現在就先提醒你，它是一個單向的測試（沒通過它能顯示不正規，但通過了卻什麼也證明不了）。要「越過」這道牆，你會加上一段記憶：一疊只能從頂端碰的盤子，於是有了下推自動機與上下文無關文法——這正是真正的剖析器拿來處理這一階梯的詞法分析器所產出的那串 token 的東西。你在這裡證明的那個乾淨等價 regex = 自動機，是你初嚐一個會一路向上、直到圖靈機與 NP 都反覆出現的主題：同一種計算威力，可以穿上許多不同的戲服。