正規表示式

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
「正規表示式」的各地常用名稱
中國大陸正則表達式
臺灣正規表示式[1]、正規表示法、
正規表達式[2]、規則運算式[3][4]
港澳正則表達式

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

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

譯名問題[編輯]

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

歷史[編輯]

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

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

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

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

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

理論[編輯]

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

  • 空集表示集合
  • 空字串表示僅包含一個「不含任何字元、長度為0的字串」的集合。
  • 文字字元英語String literal表示僅包含一個元素的集合

定義了下列運算:

  • 串接 表示集合,這裡的表示將兩個字串按順序連接。例如:
  • 選擇 表示聯集。例如:
  • 克萊尼(Kleene)星號 表示包含且在字串串接運算下閉合的最小超集。這是可以通過中零或有限個字串的串接得到所有字串的集合。例如:

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

很多課本使用對選擇使用符號替代豎線。

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

例子:

  • a|b*表示
  • (a|b)*表示包括空字串和任意數目個ab字元組成的所有字串的集合:
  • ab*(c|ε)表示開始於一個a接著零或多個b和最後一個可選的c組成的字串的集合:

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

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

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

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

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

基本語法[編輯]

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

選擇[編輯]

  • 豎線|代表選擇(即或集),具有最低優先級。例如gray|grey可以符合greygray

數量限定[編輯]

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

  • 加號+代表前面的字元必須至少出現一次。(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?|ä)ndelH(a|ae|ä)ndel是相同的,表示{"Handel", "Haendel", "Händel"}。

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

PCRE表達式全集[編輯]

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

字元 描述
\ 將下一個字元標記為一個特殊字元(File Format Escape,清單見本表)、或一個原義字元(Identity Escape,有「^$()*+?.[\{|」共計12個)、或一個向後參照(backreferences)、或一個八進位跳脫符。例如,「n」符合字元「n」。「\n」符合一個換行符。序列「\\」符合「\」而「\(」則符合「(」。
^ 符合輸入字串的開始位置。如果設定了RegExp物件的Multiline屬性,^也符合「\n」或「\r」之後的位置。
$ 符合輸入字串的結束位置。如果設定了RegExp物件的Multiline屬性,$也符合「\n」或「\r」之前的位置。
* 符合前面的子表達式零次或多次。例如,zo*能符合「z」、「zo」以及「zoo」。*等價於{0,}。
+ 符合前面的子表達式一次或多次。例如,「zo+」能符合「zo」以及「zoo」,但不能符合「z」。+等價於{1,}。
? 符合前面的子表達式零次或一次。例如,「do(es)?」可以符合「does」中的「do」和「does」。?等價於{0,1}。
{n} n是一個非負整數。符合確定的n次。例如,「o{2}」不能符合「Bob」中的「o」,但是能符合「food」中的兩個o。
{n,} n是一個非負整數。至少符合n次。例如,「o{2,}」不能符合「Bob」中的「o」,但能符合「foooood」中的所有o。「o{1,}」等價於「o+」。「o{0,}」則等價於「o*」。
{n,m} mn均為非負整數,其中n<=m。最少符合n次且最多符合m次。例如,「o{1,3}」將符合「fooooood」中的前三個o。「o{0,1}」等價於「o?」。請注意在逗號和兩個數之間不能有空格。
? 非貪心量化(Non-greedy quantifiers):當該字元緊跟在任何一個其他重複修飾詞(*,+,?,{n},{n,},{n,m})後面時,符合模式是貪婪的。非貪婪模式儘可能少的符合所搜尋的字串,而預設的貪婪模式則儘可能多的符合所搜尋的字串。例如,對於字串「oooo」,「o+?」將符合單個「o」,而「o+」將符合所有「o」。
. 符合除「\r」「\n」之外的任何單個字元。要符合包括「\r」「\n」在內的任何字元,請使用像「(.|\r|\n)」的模式。
(pattern) 符合pattern並取得這一符合的子字串。該子字串用於向後參照。所取得的符合可以從產生的Matches集合得到,在VBScript中使用SubMatches集合,在JScript中則使用$0…$9屬性。要符合圓括號字元,請使用「\(」或「\)」。可帶數量字尾。
(?:pattern) 符合pattern但不取得符合的子字串(shy groups),也就是說這是一個非取得符合,不儲存符合的子字串用於向後參照。這在使用或字元「(|)」來組合一個模式的各個部分是很有用。例如「industr(?:y|ies)」就是一個比「industry|industries」更簡略的表達式。
(?=pattern) 正向肯定預查(look ahead positive assert),在任何符合pattern的字串開始處符合尋找字串。這是一個非取得符合,也就是說,該符合不需要取得供以後使用。例如,「Windows(?=95|98|NT|2000)」能符合「Windows2000」中的「Windows」,但不能符合「Windows3.1」中的「Windows」。預查不消耗字元,也就是說,在一個符合發生後,在最後一次符合之後立即開始下一次符合的搜尋,而不是從包含預查的字元之後開始。
(?!pattern) 正向否定預查(negative assert),在任何不符合pattern的字串開始處符合尋找字串。這是一個非取得符合,也就是說,該符合不需要取得供以後使用。例如「Windows(?!95|98|NT|2000)」能符合「Windows3.1」中的「Windows」,但不能符合「Windows2000」中的「Windows」。預查不消耗字元,也就是說,在一個符合發生後,在最後一次符合之後立即開始下一次符合的搜尋,而不是從包含預查的字元之後開始
(?<=pattern) 反向(look behind)肯定預查,與正向肯定預查類似,只是方向相反。例如,「(?<=95|98|NT|2000)Windows」能符合「2000Windows」中的「Windows」,但不能符合「3.1Windows」中的「Windows」。
(?<!pattern) 反向否定預查,與正向否定預查類似,只是方向相反。例如「(?<!95|98|NT|2000)Windows」能符合「3.1Windows」中的「Windows」,但不能符合「2000Windows」中的「Windows」。
x|y 沒有包圍在()里,其範圍是整個正規表示式。例如,「z|food」能符合「z」或「food」。「(?:z|f)ood」則符合「zood」或「food」。
[xyz] 字元集合(character class)。符合所包含的任意一個字元。例如,「[abc]」可以符合「plain」中的「a」。特殊字元僅有反斜線\保持特殊含義,用於跳脫字元。其它特殊字元如星號、加號、各種括號等均作為普通字元。脫字元^如果出現在首位則表示負值字元集合;如果出現在字串中間就僅作為普通字元。連字元 - 如果出現在字串中間表示字元範圍描述;如果如果出現在首位(或末尾)則僅作為普通字元。右方括號應跳脫出現,也可以作為首位字元出現。
[^xyz] 排除型字元集合(negated character classes)。符合未列出的任意字元。例如,「[^abc]」可以符合「plain」中的「plin」。
[a-z] 字元範圍。符合在Unicode編碼表指定範圍內的任意字元。例如,「[a-z]」可以符合「a」到「z」範圍內的任意小寫字母字元。
[^a-z] 排除型的字元範圍。符合任何不在Unicode編碼表指定範圍內的任意字元。例如,「[^a-z]」可以符合任何不在「a」到「z」範圍內的任意字元。
[:name:] 增加命名字元類(named character class[註 1]中的字元到表達式。只能用於方括號表達式
[=elt=] 增加當前locale下排序(collate)等價於字元「elt」的元素。例如,[=a=]可能會增加ä、á、à、ă、ắ、ằ、ẵ、ẳ、â、ấ、ầ、ẫ、ẩ、ǎ、å、ǻ、ä、ǟ、ã、ȧ、ǡ、ą、ā、ả、ȁ、ȃ、ạ、ặ、ậ、ḁ、ⱥ、ᶏ、ɐ、ɑ 。只能用於方括號表達式。
[.elt.] 增加排序元素collation elementelt到表達式中。這是因為某些排序元素由多個字元組成。例如,29個字母表的西班牙語, "CH"作為單個字母排在字母C之後,因此會產生如此排序「cinco, credo, chispa」。只能用於方括號表達式。
\b 符合一個單詞邊界,也就是指單詞和空格間的位置。例如,「er\b」可以符合「never」中的「er」,但不能符合「verb」中的「er」。
\B 符合非單詞邊界。「er\B」能符合「verb」中的「er」,但不能符合「never」中的「er」。
\cx 符合由x指明的控制字元。x的值必須為A-Za-z之一。否則,將c視為一個原義的「c」字元。控制字元的值等於x的值最低5位元(即對3210進位的餘數)。例如,\cM符合一個Control-M或回車字元。\ca等效於\u0001, \cb等效於\u0002, 等等…
\d 符合一個數字字元。等價於[0-9]。注意Unicode正規表示式會符合全形數字字元。
\D 符合一個非數字字元。等價於[^0-9]。
\f 符合一個換頁符。等價於\x0c和\cL。
\n 符合一個換行符。等價於\x0a和\cJ。
\r 符合一個回車字元。等價於\x0d和\cM。
\s 符合任何空白字元,包括空格、制表符、換頁符等等。等價於[ \f\n\r\t\v]。注意Unicode正規表示式會符合全形空格符。
\S 符合任何非空白字元。等價於[^ \f\n\r\t\v]。
\t 符合一個制表符。等價於\x09和\cI。
\v 符合一個垂直制表符。等價於\x0b和\cK。
\w 符合包括底線的任何單詞字元。等價於「[A-Za-z0-9_]」。注意Unicode正規表示式會符合中文字元。
\W 符合任何非單詞字元。等價於「[^A-Za-z0-9_]」。
\xnn 十六進位跳脫字元序列。符合兩個十六進位數字nn表示的字元。例如,「\x41」符合「A」。「\x041」則等價於「\x04&1」。正規表達式中可以使用ASCII編碼。.
\num 向後參照(back-reference)一個子字串(substring),該子字串與正規表示式的第num個用括號圍起來的捕捉群(capture group)子表達式(subexpression)符合。其中num是從1開始的十進位正整數,其上限可能是9[註 2]、31[註 3]、99甚至無限[註 4]。例如:「(.)\1」符合兩個連續的相同字元。
\n 標識一個八進位跳脫值或一個向後參照。如果\n之前至少n個取得的子表達式,則n為向後參照。否則,如果n為八進位數字(0-7),則n為一個八進位跳脫值。
\nm 3位八進位數字,標識一個八進位跳脫值或一個向後參照。如果\nm之前至少有nm個獲得子表達式,則nm為向後參照。如果\nm之前至少有n個取得,則n為一個後跟文字m的向後參照。如果前面的條件都不滿足,若nm均為八進位數字(0-7),則\nm將符合八進位跳脫值nm
\nml 如果n為八進位數字(0-3),且m和l均為八進位數字(0-7),則符合八進位跳脫值nml。
\un Unicode跳脫字元序列。其中n是一個用四個十六進位數字表示的Unicode字元。例如,\u00A9符合著作權符號(©)。

Unicode處理[編輯]

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

Unicode字元的三種性質:[5]

  • Unicode Property:字元屬於標點、空格、字母等等。每個Unicode字元只能屬於唯一Unicode Property。.NET、JavaPHPRuby等語言支援。具體分類為:
    • 字元\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}音標修飾字元英語Spacing Modifier Letters
      • \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}ASCIILatin-1控制字元0x00-0x1F0x7F-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字元。PHPRuby(版本不低於1.9)支援Unicode Script。例如\p{Han}表示漢字(中文字元)。

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

POSIX字元組[編輯]

POSIX字元組 說明 ASCII環境 Unicode環境
[:alnum:] 字母字元和數字字元 [a-zA-Z0-9] [\p{L&}\p{Nd}]
[:alpha:] 字母 [a-zA-Z] \p{L&}
[:ascii:] ASCII字元 [\x00-\x7F] \p{InBasicLatin}
[:blank:] 空格字元和制表符 [ \t] [\p{Zs}\t]
[:cntrl:] 控制字元 [\x00-\x1F\x7F] \p{Cc}
[:digit:] 數字字元 [0-9] \p{Nd}
[:graph:] 空白字元之外的字元 [\x21-\x7E] [^\p{Z}\p{C}]
[:lower:] 小寫字母字元 [a-z] \p{Ll}
[:print:] 類似[:graph:],但包括空白字元 [\x20-\x7E] [^\P{C}]
[:punct:] 標點符號 [][!"#$%&'()*+,./:;<=>?@\^_`{|}~-] [\p{P}\p{S}]
[:space:] 空白字元 [ \t\r\n\v\f] [\p{Z}\t\r\n\v\f]
[:upper:] 大寫字母字元 [A-Z] \p{Lu}
[:word:] 字母字元 [A-Za-z0-9_] [\p{L}\p{N}\p{Pc}]
[:xdigit:] 十六進位字元 [A-Fa-f0-9] [A-Fa-f0-9]

優先權[編輯]

 優先權 符號
最高 \
()(?:)(?=)[]
*+?{n}{n,}{n,m}
^$、中介字元
次最低 串接,即相鄰字元連接在一起
最低 |

範例[編輯]

  • 以下使用PHP語言
  • 驗證字串是否只含數字與英文,字串長度並在4~16個字元之間:
    <?php
    $str = 'a1234';
    if (preg_match("/^[a-zA-Z0-9]{4,16}$/", $str)) {
        echo "CONFIRM";
    } else {
        echo "FAILED";
    }
    ?>
    
  • 簡易的中華民國國民身分證字號驗證:
    <?php
    $str = 'a1234';
    if (preg_match("/^[A-Za-z][1289]\d{8}$/", $str)) {
        echo "CONFIRM";
    } else {
        echo "FAILED";
    }
    ?>
    
  • 以下使用Perl語言
  • 驗證字串是否只含數字與英文,字串長度並在4~16個字元之間:
    print $str = "a1234" =~ m:^[a-zA-Z0-9]{4,16}$: ? "CONFIRM" : "FAILED";
    
  • 簡易的中華民國身分證字號驗證:
    print $str = "a1234" =~ m"^\w[1289]\d{8}$" ? "CONFIRM" : "INVALID";
    
  • 使用正規表示式符合ip位址:
    import re
    s=' 192.137.1.336  192.168.1.137.123  192.168.1.138 '
    print(re.findall(r'(?<![\.\d])(?:25[0-5]\.|2[0-4]\d\.|[01]?\d\d?\.){3}(?:25[0-5]|2[0-4]\d|[01]?\d\d?)(?![\.\d])',s))
    

相關條目[編輯]

注釋[編輯]

  1. ^ 命名字元類。對於C++11的regex_traits::lookup_classname,預設返回字元類的名字:"alnum", "apha", "blank", "cntrl", "digit", "graph", "lower", "print", "punct", "space", "upper", "xdigit", "d", "s", "w"
  2. ^ 命名字元類BREgrep最多只能向後參照到9
  3. ^ Visual C++的regex庫最多只能向後參照到31
  4. ^ ECMAScript不限向後參照的上限

參考文獻[編輯]

  1. ^ 雙語詞彙、學術名詞暨辭書資訊網. 國家教育研究院. [2018-12-24]. (原始內容存檔於2018-12-24). 
  2. ^ 正規表達式 - JavaScript. 社群編輯. [2023-06-10]. 原始內容存檔於2023-06-28.  已忽略文字「MDN」 (幫助)
  3. ^ 軟體操作小撇步 –Dreamweaver CS4規則運算式介紹. 師友會電子報第 181 期. 財團法人中華民國電腦技能基金會. 2009-11-25. (原始內容存檔於2023-06-10). 
  4. ^ EmEditor 如何: 規則運算式語法. Emurasoft, Inc. (原始內容存檔於2023-03-29). 
  5. ^ Unicode Regular Expressions. [2017-09-19]. (原始內容存檔於2021-04-01). 

外部連結[編輯]