正則表達式（英文：Regular Expression），在計算機科學(xué)中，是指一個用來描述或者匹配一系列符合某個句法規(guī)則的字符串的單個字符串。在很多文本編輯器或其他工具里，正則表達式通常被用來檢索和/或替換那些符合某個模式的文本內(nèi)容。許多程序設(shè)計語言都支持利用正則表達式進行字符串操作。例如，在Perl中就內(nèi)建了一個功能強大的正則表達式引擎。正則表達式這個概念最初是由Unix中的工具軟件（例如sed和grep）普及開的?！罢齽t表達式”通常縮寫成“regex”，單數(shù)有regexp、regex，復(fù)數(shù)有regexps、regexes、regexen。

[編輯] 基本概念

一個正則表達式通常被稱為一個模式 (pattern)，為用來描述或者匹配一系列符合某個句法規(guī)則的字符串。例如：Handel、H?ndel 和 Haendel 這三個字符串，都可以由 "H(a|?|ae)ndel" 這個模式來描述。大部分正則表達式的形式都有如下的結(jié)構(gòu)：

替換

|

豎直分隔符代表替換。例如"gray|grey"可以匹配grey或gray。

數(shù)量限定

某個字符后的數(shù)量限定符用來限定前面這個字符允許出現(xiàn)的個數(shù)。最常見的數(shù)量限定符包括“+”，“”和“*”（不加數(shù)量限定則代表出現(xiàn)一次且僅出現(xiàn)一次）：

+

加號代表前面的字符必須至少出現(xiàn)一次。(1次，或多次)。例如，"goo+gle"可以匹配google，gooogle，goooogle等;

 

問號代表前面的字符最多只可以出現(xiàn)一次。(0次，或1次)。例如，"colou?r"可以匹配colour或者color;

*

星號代表前面的字符可以不出現(xiàn)，也可以出現(xiàn)一次或者多次。(0次，或1次，或多次)。例如，"0*42"可以匹配42，042，0042，00042等。

匹配

圓括號可以用來定義操作符的范圍和優(yōu)先度。例如，"gr(a|e)y"等價于"gray|grey"，"(grand)?father"匹配father和grandfather。

上述這些構(gòu)造子都可以自由組合，因此，"H(ae?|?)ndel"和"H(a|ae|?)ndel"是相同的。

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

[編輯] 歷史

最初的正則表達式出現(xiàn)于理論計算機科學(xué)的自動控制理論和形式語言理論中。在這些領(lǐng)域中有對計算（自動控制）的模型和對形式語言描述與分類的研究。1940年代，Warren McCulloch與Walter Pitts將神經(jīng)系統(tǒng)中的神經(jīng)元描述成小而簡單的自動控制元。在1950年代，數(shù)學(xué)家斯蒂芬·科爾·克萊尼利用稱之為正則集合的數(shù)學(xué)符號來描述此模型。肯·湯普遜將此符號系統(tǒng)引入編輯器QED，然后是Unix上的編輯器ed，并最終引入grep。自此，正則表達式被廣泛地使用于各種Unix或者類似Unix的工具，例如Perl。

Perl正則表達式源自于Henry Spencer寫的regex，它已經(jīng)演化成了pcre（Perl兼容正則表達式Perl Compatible Regular Expressions），一個由Philip Hazel開發(fā)的，為很多現(xiàn)代工具所使用的庫。

各計算機語言之間的正則表達式的整合目前開展的很差。未來的Perl6的子項目Apocalypse的設(shè)計中已考慮到了這點。

[編輯] 形式語言理論

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

• (“空集”) ? 指示集合 ?
• (“空串”) ε 指示集合 {ε}
• (“文字字符”) 在 Σ 中的 a 指示集合 {a}

定義了下列運算:

• (“串接”) RS 指示集合 { αβ | α ∈ R ∧ β ∈ S }。例如 {"ab"|"c"}{"d"|"ef"} = {"abd", "abef", "cd", "cef"}。
• (“選擇”) R|S 指示 R 和 S 的并集。
• (“Kleene星號”) R* 指示包含 ε 并且閉合在字符串串接下的 R 的最小超集。這是可以通過 R 中的零或多個字符串的串接得到所有字符串的集合。例如，{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }。

上述常量和算子形成了克萊尼代數(shù)。

很多課本使用對選擇使用符號 ∪, + 或 ∨ 替代豎杠。

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

例子:

• a|b* 指示 {ε, a, b, bb, bbb, ...}。
• (a|b)* 指示由包括空串、任意數(shù)目個 a 和 b 字符組成的所有字符串的集合。
• ab*(c|ε) 指示開始于一個 a 接著零或多個 b 和最終可選的一個 c 的字符串的集合。

正則表達式的形式定義故意非常精簡，避免定義多余的量詞 和 +，它們可以被表達為: a+ = aa* 和 a? = (a|ε)。有時增加補算子 ~ ；~R 指示在 Σ* 上的不在 R 中的所有字符串的集合。補算子是多余的，因為它使用其他算子來表達(盡管計算這種表示的過程是復(fù)雜的，而結(jié)果可能指數(shù)性的增大)。

這種意義上的正則表達式可以表達正則語言，精確的是可被有限狀態(tài)自動機接受的語言類。但是在簡潔性上有重要區(qū)別。某類正則語言只能用大小指數(shù)增長的自動機來描述，而要求的正則表達式的長度只線性的增長。正則表達式對應(yīng)于喬姆斯基層級的類型-3文法。在另一方面，在正則表達式和不導(dǎo)致這種大小上的爆炸的非確定有限狀態(tài)自動機(NFA)之間有簡單的映射；為此 NFA 經(jīng)常被用作正則表達式的替代表示。

我們還要在這種形式化中研究表達力。如下面例子所展示的，不同的正則表達式可以表達同樣的語言: 這種形式化中存在著冗余。

有可能對兩個給定正則表達式寫一個算法來判定它們所描述的語言是否本質(zhì)上相等，簡約每個表達式到極小確定有限自動機，確定它們是否同構(gòu)（等價）。

這種冗余可以消減到什么程度? 我們可以找到仍有完全表達力的正則表達式的有趣的子集嗎? Kleene 星號和并集明顯是需要的，但是我們或許可以限制它們的使用。這提出了一個令人驚奇的困難問題。因為正則表達式如此簡單，沒有辦法在語法上把它重寫成某種規(guī)范形式。過去公理化的缺乏導(dǎo)致了星號高度問題。最近 Dexter Kozen 用克萊尼代數(shù)公理化了正則表達式。

很多現(xiàn)實世界的“正則表達式”引擎實現(xiàn)了不能用正則表達式代數(shù)表達的特征。

[編輯] 表達式全集

正則表達式有多種不同的風(fēng)格。下表是在PCRE中元字符及其在正則表達式上下文中的行為的一個完整列表：

[編輯] 范例

以下以PHP的語法所寫的范例

• 驗證字串是否只含數(shù)字與英文，字串長度并在4~16個字符之間

<?php
$str = 'a1234';
if (preg_match("^[a-zA-Z0-9]{4,16}$", $str)) {
echo "驗證成功";
} else {
echo "驗證失敗";
}
?>

• 簡易的臺灣身份證字號驗證

<?php
$str = 'a1234';
if (preg_match("^[A-Z]{1}[1-2]{1}[0-9]{8}$", $str)) {
echo "驗證成功";
} else {
echo "驗證失敗";
}
?>

[編輯] 相關(guān)條目

• Perl
• PHP
• Python
• Ruby

[編輯] 外部鏈接

• 各種不同風(fēng)格的正則表達式
• 正則表達式30分鐘入門教程
• 正則表達式綜合實例