書寫正規表示式

讀懂一個正規表示式是一種技能；而為你心中的某個樣式寫出一個表示式，則是更難、也更有用的技能。這就像把一句英文翻譯成一條精簡的公式。好消息是，有些可靠的習慣能把「描述所有滿足……的字串」轉成正確的表示式，正如 DFA 設計也有它的訣竅。

一個實用的配方：首先盡可能精確地用文字陳述這個語言（「{a, b} 上至少含一個 a 的所有字串」）。接著把它拆成結構性的部分，逐一翻譯。「前面任意」或「後面任意」變成 (a+b)*。「至少一個 a」變成 (a+b)*a(a+b)*。「恰好兩個 b」變成 a*ba*ba*。「以 a 開頭」變成 a(a+b)*。把各個選項聯集起來、把有順序的部分串接起來、把可重複的部分加星號。然後拿幾個應該匹配與幾個不應匹配的範例字串去測試你的表示式，這能抓出大多數的優先序與邊界情形錯誤。

常見的樣式值得記下來。(a+b)* 是「任意字串」，而 ε 加上一份清單是「這些特定字串」。在 {a} 上「偶數個 a」是 (aa)*。「不含子字串 bb」在一種常見寫法裡是 a*(baa*)*b 加上選擇性的尾巴，但先建一台 DFA 再轉換會更容易做對。誠實的界限是：許多聽起來自然的樣式根本不是正規的（例如「a 與 b 的數目相等」），所以在埋頭苦寫表示式之前，先問問這個語言是否真的正規；若它需要無上限地計數，就不存在任何正規表示式。