正規化表示法

**正規表示式**（英語：Regular expression，常簡寫為 regex、regexp 或 RE），又稱**規律表達式**、**正規表達式**、**正規表示法**、**規則運算式**、**常規表示法**，是電腦科學概念，用簡單字串來描述、符合文中全部符合指定格式的字串，現在很多文字編輯器都支援用正規表達式搜尋、取代符合指定格式的字串。

許多程式設計語言都支援用正規表達式操作字串，如 Perl 就內建功能強大的正規表達式引擎。正規表達式這概念最初由 Unix 的工具軟體（例如 sed 和 grep）普及開。

## 譯名問題

描述字串**規律**的**表達式**原應順理成章稱為**規律表達式**（pattern expression／rule expression），但卻叫成有欠準確的 regular expression，導致現在有多種中譯名，如將 regular 譯成**規律**、**規則**、**正則**、**正規**或**常規**，將 expression 譯成**表達式**、**表達式**、**表示法**或**運算式**等。

## 歷史

最初的正規表示式出現於理論電腦科學的自動控制理論和形式化語言理論中。在這些領域中有對計算（自動控制）的模型和對形式化語言描述與分類的研究。

1940 年，沃倫・麥卡洛克與沃爾特・皮茨將神經系統中的神經元描述成小而簡單的自動控制元。

1950 年代，數學家史蒂芬・科爾・克萊尼利用稱之為「正規集合」的數學符號來描述此模型。肯・湯普遜將此符號系統引入編輯器 QED，隨後是 Unix 上的編輯器 ed，並最終引入 grep。自此以後，正規表達式被廣泛地應用於各種 Unix 或類 Unix 系統的工具中。正規表示式的 POSIX 規範，分為基本型正規表示式（Basic Regular Expression，BRE）和擴充型正規表示式（Extended Regular Expression，ERE）兩大流派。在相容 POSIX 的 UNIX 系統上，grep 和 egrep 之類的工具都遵循 POSIX 規範，一些資料庫系統中的正規表示式也符合 POSIX 規範。grep、vi、sed 都屬於 BRE，是歷史最早的正規表示式，因此元字元必須轉譯之後才具有特殊含義。egrep、awk 則屬於 ERE，元字元不用轉譯。

Perl 的正規表示式源自於 Henry Spencer 於 1986 年 1 月 19 日發布的 regex，它已經演化成了 PCRE（Perl 相容正規表示式，Perl Compatible Regular Expressions），一個由 Philip Hazel 開發的，為很多現代工具所使用的庫。

各程式語言之間關於正規表達式的整合，目前開發進展得很差。Perl6 的子專案 Apocalypse 的設計中已考慮到了這點。

## 理論

正規表示式可以用形式化語言理論的方式來表達。正規表示式由常數和算子組成，它們分別表示字串的集合和在這些集合上的運算。給定有限字母表 Σ 定義了下列常數：

* 空集 $\varnothing $ 表示集合 $\varnothing $ 。
* 空字串 $\varepsilon $ 表示僅包含一個「不含任何字元、長度為 0 的字串」的集合。
* 文字字元 $a\in \Sigma $ 表示僅包含一個元素 $a$ 的集合 $\{a\}$ 。

定義了下列運算：

* 串接 $RS$ 表示集合 $\{\alpha \beta \mid \alpha \in R,\beta \in S\}$ ，這裡的 $\alpha \beta $ 表示將 $\alpha $ 和 $\beta $ 兩個字串按順序連接。例如： $\{ab,c\}\{d,ef\}=\{abd,abef,cd,cef\}$ 。
* 選擇 $R|S$ 表示 $R$ 和 $S$ 的聯集。例如： $\{ab,c\}|\{ab,d,ef\}=\{ab,c,d,ef\}$ 。
* 克萊尼 (Kleene) 星號 $R^{*}$ 表示包含 $\varepsilon $ 且在字串串接運算下閉合的 $R$ 的最小超集。這是可以通過 $R$ 中零或有限個字串的串接得到所有字串的集合。例如： $\{ab,c\}^{*}=\{\varepsilon ,ab,c,abab,abc,cab,cc,ababab,\cdots \}$ 。

上述常數和算子形成了克萊尼代數。

很多課本使用對選擇使用符號 $\cup $ 、 $+$ 或 $\vee $ 替代豎線。

為了避免括號，假定 Kleene 星號有最高優先級，接著是串接，接著是聯集。如果沒有歧義則可以省略括號。例如：`(ab)c` 可以寫為 `abc`，而 `a|(b(c*))` 可以寫為 `a|bc*`。

例子：

* `a|b*` 表示 $\{\varepsilon ,a,b,bb,bbb,\cdots \}$ 。
* `(a|b)*` 表示包括空字串和任意數目個 _a_ 或 _b_ 字元組成的所有字串的集合： $\{\varepsilon ,a,b,aa,ab,ba,bb,aaa\cdots \}$ 。
* `ab*(c|ε)` 表示開始於一個 _a_ 接著零或多個 _b_ 和最後一個可選的 _c_ 組成的字串的集合： $\{a,ac,ab,abc,abb,abbc\cdots \}$ 。

為了使表達式更簡潔，正規表示式也定義了 `?` 和 `+`；`aa*` 等於 `a+`，表示 a 出現至少一次；而 `(a|ε)` 等於 `a?`，表示 a 出現 1 次或不出現。有的定義中增加了補算子 $\sim $ ； $\sim R$ 表示在 $\Sigma ^{*}$ 上但不在 $R$ 中的所有字串的集合。補算子在理論上並非必要，因為它可以使用其他算子來表達，但它可以使一些表達式變得更加簡潔。

這種意義上的正規表示式可以表達正規語言，是可被有限狀態自動機精確接受的語言類。但是在簡潔性上有重要區別。某類正規語言只能用大小指數增長的自動機來描述，而要求的正規表示式的長度只線性的增長。

正規表示式對應於喬姆斯基層級的類型 - 3 文法。但通常程式語言或其相關庫（例如 PCRE）中實現的正規表示式的表達能力是喬姆斯基層級中類型 - 3 文法的超集。在另一方面，在正規表示式和不導致這種大小上的爆炸的非確定有限狀態自動機（NFA）之間有簡單的對映；為此 NFA 經常被用作正規表示式的替表示式。

這種形式化中存在著冗餘，典型的體現是存在不同的正規表示式可以表達同樣的語言。有可能對兩個給定正規表示式寫一個演算法來判定它們所描述的語言是否本質上相等，即簡約每個表達式到極小確定有限自動機，確定它們是否同構（等價）。這種冗餘可以消減到什麼程度？我們可以找到仍有完全表達力的正規表示式的有趣的子集嗎？這提出了一個令人驚奇的困難問題。Kleene 星號和聯集明顯是需要的，但是我們或許可以限制它們的使用。由於正規表示式如此簡單，沒有辦法在語法上把它重寫成某種規範形式。過去公理化的缺乏導致了星號高度問題。最近 Dexter Kozen 用克萊尼代數公理化了正規表示式。

很多現實世界的「正規表示式」引擎實現了不能用正規表示式代數表達的特徵。

## 基本語法

一個正規表示式通常被稱為一個**模式**（pattern），為用來描述或者符合一系列符合某個句法規則的字串。例如：Handel、Händel 和 Haendel 這三個字串，都可以由 `H(a|ä|ae)ndel` 這個模式來描述。大部分正規表示式的形式都有如下的結構：

### 選擇

* 豎線 `|` 代表選擇（即或集），具有最低優先級。例如 `gray|grey` 可以符合 grey 或 gray。

### 數量限定

某個字元後的數量限定符用來限定前面這個字元允許出現的個數。最常見的數量限定符包括 `+`、`?` 和 `*`（不加數量限定則代表出現一次且僅出現一次）：

* 加號 `+` 代表前面的字元必須至少出現一次。（1 次或多次）。例如，`goo+gle` 可以符合 google、gooogle、goooogle 等；
* 問號 `?` 代表前面的字元最多只可以出現一次。（0 次或 1 次）。例如，`colou?r` 可以符合 color 或者 colour；
* 星號 `*` 代表前面的字元可以不出現，也可以出現一次或者多次。（0 次、1 次或多次）。例如，`0*42` 可以符合 42、042、0042、00042 等。

### 符合

* 圓括號 `()` 可以用來定義運算子的範圍和優先度。例如，`gr(a|e)y` 等價於 `gray|grey`，`(grand)?father` 符合 father 和 grandfather。

上述這些構造子都可以自由組合，因此 `H(ae?|ä)ndel` 和 `H(a|ae|ä)ndel` 是相同的，表示 {"Handel", "Haendel", "Händel"}。

精確的語法可能因不同的工具或程式而異。

## PCRE 表達式全集

正規表示式有多種不同的風格。下表是在 PCRE 中元字元及其在正規表示式上下文中的行為的一個完整列表，適用於 Perl 或者 Python 程式語言（grep 或者 egrep 的正規表示式文法是 PCRE 的子集）：

## Unicode 處理

在.NET、Java、JavaScript、Python 的正規表示式中，可以用 `\uXXXX` 表示一個 Unicode 字元，其中 `XXXX` 為四位 16 進位數字。

Unicode 字元的三種性質：

* Unicode Property：字元屬於標點、空格、字母等等。每個 Unicode 字元只能屬於唯一 Unicode Property。.NET、Java、PHP 和 Ruby 等語言支援。具體分類為：
  * 字元 `\p{L}`
    * `\p{Ll}` 或 `\p{Lowercase_Letter}`：小寫字元（必須有大寫的形式）。
    * `\p{Lu}` 或 `\p{Uppercase_Letter}`：大寫字元（必須有小寫的形式）。
    * `\p{Lt}` 或 `\p{Titlecase_Letter}`：全詞首字母大寫的字元。
    * `\p{L&}` 或 `\p{Cased_Letter}`：存在大小寫形式的字元（Ll, Lu, Lt 的組合）。
    * `\p{Lm}` 或 `\p{Modifier_Letter}`：音標修飾字元。
    * `\p{Lo}` 或 `\p{Other_Letter}`：不具有大小寫的字元或字形。
  * 附加符號 `\p{M}`
    * `\p{Mn}` 或 `\p{Non_Spacing_Mark}`：與其他字元結合，不額外占用空間的字元，例如日耳曼語元音變音。
    * `\p{Mc}` 或 `\p{Spacing_Combining_Mark}`：與其他字元結合，額外占用空間的字元，例如馬拉雅拉姆文 #元音字母及附標。
    * `\p{Me}` 或 `\p{Enclosing_Mark}`：包含其他字元的字元，例如圓圈、方塊。
  * 分隔符 `\p{Z}`
    * `\p{Zs}` 或 `\p{Space_Separator}`：不可見的空格，但占據空間。
    * `\p{Zl}` 或 `\p{Line_Separator}`：分隔綫字元 U+2028。
    * `\p{Zp}` 或 `\p{Paragraph_Separator}`：分段字元 U+2029。
  * 符號 `\p{S}`
    * `\p{Sm}` 或 `\p{Math_Symbol}`：數學符號。
    * `\p{Sc}` 或 `\p{Currency_Symbol}`：通貨符號。
    * `\p{Sk}` 或 `\p{Modifier_Symbol}`：組合為其他字元的符號。
    * `\p{So}` 或 `\p{Other_Symbol}`：其他符號。
  * 數值字元 `\p{N}`
    * `\p{Nd}` 或 `\p{Decimal_Digit_Number}`：所有文字中的數字 0 至 9 字元，不含形意符號。
    * `\p{Nl}` 或 `\p{Letter_Number}`：看起來像字母的符號，包含羅馬數字。
    * `\p{No}` 或 `\p{Other_Number}`：上角標或下角標數字，或者其他不屬於 0 至 9 的數字。不含形意符號。
  * 標點符號 `\p{P}`
    * `\p{Pd}` 或 `\p{Dash_Punctuation}`：任何種類的連字號或連接號。
    * `\p{Ps}` 或 `\p{Open_Punctuation}`：任何種類開括號。
    * `\p{Pe}` 或 `\p{Close_Punctuation}`：任何種類閉括號。
    * `\p{Pi}` 或 `\p{Initial_Punctuation}`：任何種類開引號。
    * `\p{Pf}` 或 `\p{Final_Punctuation}`：任何種類閉引號。
    * `\p{Pc}` 或 `\p{Connector_Punctuation}`：連接詞的標點符號，如底線。
    * `\p{Po}` 或 `\p{Other_Punctuation}`：其他標點符號。
  * 其它符號 `\p{C}`（包括不可見控制字元與未用碼位）
    * `\p{Cc}` 或 `\p{Control}`：ASCII 或 Latin-1 控制字元 `0x00-0x1F` 與 `0x7F-0x9F`。
    * `\p{Cf}` 或 `\p{Format}`：不可見的格式化指示字元。
    * `\p{Co}` 或 `\p{Private_Use}`：私用碼位。
    * `\p{Cs}` 或 `\p{Surrogate}`：UTF-16 編碼的代理對的一半。
    * `\p{Cn}` 或 `\p{Unassigned}`：未被使用的碼位。
* Unicode Block：按照編碼區間劃分 Unicode 字元，每個 Unicode Block 中的字元編碼屬於一個編碼區間。例如 Java 語言 `\p{ InCJK_Compatibility_Ideographs }`，.NET 語言 `\p{IsCJK_Compatibility_Ideographs}`。
* Unicode Script：按照字元所屬的書寫系統來劃分 Unicode 字元。PHP 和 Ruby（版本不低於 1.9）支援 Unicode Script。例如 `\p{Han}` 表示漢字（中文字元）。

這三種 Unicode 性質對應的字元組補集是將開頭的 `\p` 改為 `\P`，其它不變。

## POSIX 字元組

## 優先權

## 範例

* 以下使用 PHP 語言

　
: * 驗證字串是否只含數字與英文，字串長度並在 4~16 個字元之間：
* 簡易的中華民國國民身分證字號驗證：

* 以下使用 Perl 語言

　
: * 驗證字串是否只含數字與英文，字串長度並在 4~16 個字元之間：

　
: * 簡易的中華民國身分證字號驗證：

* 以下使用 python 語言

　
: * 使用正規表示式符合 ip 位址：

## 相關條目

* 正規表示式引擎對比
* 擴充巴科斯範式
* Thompson 構造法

## 注釋

## 參考文獻

## 外部連結

* 各種語言或工具軟體的不同風格的正規表示式文法規定 （頁面存檔備份，存於網際網路檔案館）（英文）
* 正規表示式 30 分鐘入門教學 （頁面存檔備份，存於網際網路檔案館）（簡體中文）
* 正規表示式應用範例 （頁面存檔備份，存於網際網路檔案館）（繁體中文）
* 正規化表示法 - ProgWiki （頁面存檔備份，存於網際網路檔案館）（繁體中文）
* Regexper （頁面存檔備份，存於網際網路檔案館）
* RegExr: Learn, Build, & Test RegEx （頁面存檔備份，存於網際網路檔案館） —— 公式上的懸浮氣泡 UI 解釋該規則符合的字串；符合結果有對應的解釋；右側邊欄有正規表示式的詳細規範及圖中的小抄
* regex101.com （頁面存檔備份，存於網際網路檔案館） —— 檢視符合訊息，並且會用不同的顏色將 Group 標記出來。
* Debuggex: Online visual regex tester. JavaScript, Python, and PCRE. （頁面存檔備份，存於網際網路檔案館） —— 另一個正規表示式的網頁線上除錯 / 驗證器，用狀態機圖解輸入的正規表示式的語意，並可檢測輸入的測試字串是否符合該正規表示式