正則表達式，又稱規則表達式、常規表示法（Regular Expression，簡寫為regex、regexp或RE），是計算機科學的一個概念。正則表達式是對字符串操作的一種邏輯公式，用事先定義好的一些特定字符及這些特定字符的組合，組成一個“規則字符串”，這個“規則字符串”用來表達對字符串的一種過濾邏輯。通常用于查找、替換符合特征的字符串，或者用來驗證某個字符串是否符合指定的特征。
正則表達式最初的想法源于1940年，神經學家沃倫·麥卡洛克（Warren McCulloch）和數學家沃爾特·皮茨（Walter Pitts）在對人類神經系統如何工作的早期研究中，研究出的一種數學描述方式。1951年，數學家斯蒂芬·克萊尼（Stephen Cole Kleene）在發表的《神經網事件的表示法》論文中首次提出了正則表達式的概念。1968年，unix操作系統之父肯尼斯·藍·湯普森（Kenneth Lane Thompson）將正則表達式應用到了UNIX的QED編輯器的搜索算法中。到現在為止，正則表達式已經成為文本編輯器和搜索工具的一個重要部分，并被應用到各種編程語言中。
正則表達式主要有POSIX標準和PCRE流派。不同的流派支持的元字符和這些元字符代表的意義存在著細微的差異，元字符的類型有轉義符、字符組、分組、匹配量詞、錨點和零寬斷言，以及多選結構和嵌入條件等。正則表達式可應用于各種編程語言和文本處理工具中，在數據科學、文本分析、網絡爬蟲、字符串搜索和替換等領域都有廣泛的應用。
發展歷史
起源
正則表達式最初的想法源于1940年，神經生理學家沃倫·麥卡洛克（Warren McCulloch）與數學家沃爾特·皮茨（Walter Pitts）研究出了一種用數學化的方式來描述神經網絡的模型，他們將神經系統中的神經元描述成小而簡單的自動控制元。1951年，美國數學家斯蒂芬·克萊尼（Stephen Cole Kleene）在麥卡洛克和皮茨早期工作的基礎上，發表了一篇標題為《神經網事件的表示法》的論文，引入了正則表達式的概念。正則表達式就是用來描述他稱為“正則集的代數”的表達式，因此采用“正則表達式”這個術語。
發展
1968年，unix操作系統之父肯尼斯·藍·湯普森（Kenneth Lane Thompson）將正則表達式應用到了UNIX的QED編輯器的搜索算法中，隨后湯普森又將正則表達式引入了UNIX下的文本編輯器ed，這是正則表達式第一次在非技術領域大規模使用。1971年，湯普森申請的一項基于正則表達式的快速文本匹配機制的專利獲得批準，它是最早的軟件專利之一。
ed編輯器有條命令——顯示正在編輯的文件中能夠匹配特定正則表達式的行，該命令“g/Regular Expression/p”，讀作“Global Regular Expression Print”（應用正則表達式的全局輸出）。這個功能非常實用，最終成為獨立的工具GREP（之后又產生了egrep——擴展的grep）。自此，正則表達式被廣泛地應用到各種unix操作系統或類UNIX操作系統中。
1986年，POSIX誕生，它是Portable Operating System 接口（可移植操作系統接口）的縮寫，由電氣與電子工程師學會（Institute of Electrical and 電子學 Engineers，簡稱IEEE）制定。POSIX是一系列標準，確保操作系統之間的移植性，該標準的某些部分關乎正則表達式和使用他們的傳統工具。POSIX把正則表達式常見的流派分為兩大類：Basic Regular Expressions （BREs）和Extended Regular Expressions（EREs）。同年，亨利·斯賓塞（Henry Spencer）發布了用c語言寫的正則表達式包，這個包可以置入其他程序中。
1987年12月，拉里·沃爾（Larry Wall）發布了Perl Version 1。Perl Version 1提供了傳統上只有專用工具sed和Awk才提供的正則表達式操作符，這在通用腳本語言中是首創。1988年6月，Perl 2發布。Larry完全放棄了原有的正則表達式代碼，而采用了斯賓塞的正則表達式包的增強版。此外，添加了/i量詞，能夠進行不區分大小寫的匹配。Perl 3和Perl 4分別于1989年和1991年發布。1994年10月，Perl 5發布。就正則表達式來說，Perl 5進行了更多內部優化，添加了少量元字符、非捕獲的括號、忽略優先（lazy）的量詞、順序環視功能以及/x量詞。2015年12月25日，Perl 6正式發布，后改名為Raku。
1997年，菲利普·黑澤爾（Philip Hazel）開發了PCRE庫。PCRE是一個軟件正則表達式匹配庫，兼容Perl5 正則表達式的語法定義，現該庫主要有兩個版本：PCRE和PCRE2。PCRE是目前得到廣泛應用的正則表達式匹配解決方案，被集成在編程語言 （PHP）、網絡瀏覽器、電子郵件系統、網絡安全系統等多種應用場景。
現狀
2009年，谷歌提供了基于軟件的正則表達式匹配庫——RE2，由曾在貝爾實驗室任職的Russ Cox推出。正則表達式字符串匹配算法有單字符串匹配KMP算法、單字符串匹配BM算法、多字符串匹配AC算法、SHIFT-OR算法等。
21世紀，正則表達式在計算機編程和文本處理中變得越來越流行，很多基本的硬件都兼容正則表達式引擎的實現，可應用于各種編程語言和文本處理工具中，例如C/C++、Java、TCL科技、Python、Perl和PHP等，在數據科學、文本分析、網絡爬蟲、字符串搜索和替換等領域都有廣泛的應用。
基本語法
概述
完整的正則表達式是由普通字符和元字符組成的文本模式。普通字符包括大寫和小寫字母、所有的數字，以及沒有特殊定義的標點和符號。元字符則是在正則表達式中具有特殊含義的一些符號，例如字符組的開方括號[、閉方括號]，錨點^、$等。正則表達式元字符的類型有轉義符、字符組、分組、匹配量詞、錨點和零寬斷言，以及多選結構和嵌入條件等。匹配模式共有4種，分別是不區分大小寫模式、單行模式、多行模式和注釋模式。
此外，元字符是有特殊含義的字符，如果要匹配“元字符”自身則必須轉義，也就是在元字符之前添加反斜線\，即轉義元字符。比如元字符點號.，可以匹配除換行符以外的任何字符，如果要準確匹配字符串中的點號.，正則表達式中就必須寫\.。
相關標準
自Ken Thompson將正則表達式引入qed編輯器之后，越來越多的unix操作系統或者類UNIX操作系統開始使用正則表達式，例如grep、egrep、lex、awk和sed等。不同的開發語言，例如C/C++、Java、TCL科技、Python、Perl和PHP等也都包含了各自的正則表達式包。
不同的工具和不同的開發語言在自身的發展過程中對正則表達式支持的元字符和這些元字符的意義的規定存在著較多的差異，導致形成眾多正則表達式的流派。不同流派之間的差異給正則表達式的發展和使用造成了一定程序的混亂，不同流派的整合和相關標準的制定成為一個必然的趨勢。
Perl和PCRE
1987年12月，拉里·沃爾發布了Perl Version 1。Perl 是一種通用編程語言，最初是為文本操作而開發的，現在用于廣泛的任務，包括系統管理、We開發、網絡編程、GUI開發等。它的主要特點是易于使用，支持過程和面向對象編程，具有強大的內置文本處理支持。
PCRE是由菲利普·黑澤爾（Philip Hazel）在1997年發布的一套兼容Perl正則表達式的庫。PCRE的正則引擎質量很高，繼承了Perl的正則表達式的語法和語義。開發者可以把PCRE整合到自己的工具和語言中，為用戶提供豐富且極具表現力的各種正則功能。許多軟件都使用了PCRE，例如PHP、Apache2和Nmap等。
PCRE有兩個主要的版本，當前版本是PCRE2，于2015年發布，最新版本號是10.39。而目前使用得最廣泛的仍然是1997年發布的PCRE，當前版本號是8.45。PCRE支持大量語法，可總結成幾種不同的類別，包括字符類、有界重復、分支結構、反向引用等。PCRE2提供了與PCRE類似的語法支持，但做了少量調整，例如增加了一些Python、.NET和Oniguruma語法。PCRE語法從嚴格意義上來說是正則表達式的一個流派，而不是正則表達式的一個標準，但是由于PCRE使用廣泛和受歡迎程度高，開發者也常常把兼容PCRE語法稱為符合PCRE標準。
POSIX標準
正則表達式POSIX標準把正則表達式分成兩大類：基本正則表達式（Basic Regular Expression，BRE）和擴展正則表達式（Extended Regular Expression，ERE），遵循POSIX標準的程序必須支持其中任意一種。
在傳統的unix常用工具中，grep、vi、sed等屬于BRE流派。當使用像()、{}這樣的元字符時，元字符前面必須要加轉義符。此外，BRE流派也不支持+和?量詞，以及…|…多選結構和反向引用\1、\2等。但是，今天純粹的BRE已經很少見了，GNU對BRE做了擴展，使得BRE也能支持+、?量詞，以及…|…多選結構，不過這些元字符前面都必須要加轉義符變成\+、\?、\|。所以，GNU的GREP等工具嚴格地說應該屬于GNU BRE。
在傳統的unix常用工具中，egrep、grep-E、awk等屬于ERE流派。ERE名為擴展，但其并不是BRE的擴展，而是自成一體。ERE中元字符使用時前面無須加轉義符，并且支持+和?量詞，支持…|…多選結構。值得注意的是，POSIX ERE標準中并沒有明確規定支持反向引用。GNU同樣對ERE做了擴展，使得ERE能夠支持反向引用的功能。所以，GNU的egrep等工具嚴格地說屬于GNU ERE。
在POSIX標準中，支持[AZ]和[^a-z]這樣的字符組。此外，POSIX標準還支持一種特別的字符組表示，類似于[[:alnum:]]和[[:alpha:]]，這是POSIX標準方括號表達式的一種特殊功能。POSIX方括號表達式與PCRE字符組[...]和[^...]最主要的區別在于，POSIX方括號表達式內部\不是用來轉義的，所以在POSIX中[\d]匹配的是\和d兩個字符。
POSIX字符組就是在POSIX方括號表達式內使用幾種特殊元字符。值得注意的是，POSIX字符組表示的是當前語言環境下對應的字符，因此POSIX字符組詳細的列表會根據當前語言環境的變化而變化。此外，這種特殊的元字符只有在方括號表達式內部才是有效的，所以使用完整的POSIX字符組時必須寫成[[:alnum:]]。
元字符
不同的流派支持的元字符和這些元字符代表的意義存在著細微的差異，這里參考了Perl兼容正則表達式（Perl Compatible Regular Expression，PCRE）的語法。正則表達式的元字符之間也有優先權順序。在匹配過程中，按照正則表達式中從左到右、不同優先權先高后低來匹配相應的元字符。下面列舉了優先權從高到低的正則表達式元字符的類型：轉義符、字符組、分組、匹配量詞、錨點和零寬斷言，以及多選結構和嵌入條件等。
轉義符
轉義符用來清晰簡便地表示一些特定的字符，包括一些不可打印字符。
字符組
字符組（Character Class）是正則表達式最基本的結構之一，在正則表達式中的某個位置表示一組指定的字符。常見的字符組表示方法有點號、普通字符組和字符組簡記法。
分組
分組主要包括捕獲型分組和非捕獲型分組。
匹配量詞
匹配量詞能夠用來限制前面子表達式的匹配次數。匹配量詞又可以分為標準匹配量詞、忽略優先量詞和占有優先量詞。
錨點和零寬斷言
正則表達式中的錨點和零寬斷言都不會匹配實際的字符，而是尋找和定位字符在文本中的位置，可以認為都是定位符。
多選結構和嵌入條件
多選結構常常和嵌入條件一起使用。例如上海市地區固定電話號碼一般寫成021-12345678或者(021)12345678，可以用正則表達式(\()?021(?(\1)\)|-)\d{8}來匹配這兩種寫法。其中(?(\1)\)|-)部分表示如果前面(\()捕獲到了匹配，那么繼續匹配一個右括號)，否則匹配一個橫線-。
模式修飾符
正則表達式可以通過模式修飾符(?modifier)來設置匹配的模式，常見的模式modifier的值有i、s、m。
量詞
標準匹配量詞
標準匹配量詞（+、?、+，以及{m,n}）都是優先匹配的。
例如郵政編碼201203、100858，其正則表達式為\d\d\d\d\d\d。使用量詞簡化，可得\d{6}。
量詞還可以表示不確定的長度，其通用形式是{m,n}。其中m和n是兩個數字（量詞中的逗號之后不能有空格），它限定之前的元素能夠出現的次數，m是下限，n是上限（均為閉區間）。比如\d{4,6}，表示這個數字字符串的長度最短是4個字符（“單個數字字符”至少出現4次），最長是6個字符。如果不確定長度的上限，也可以省略，只指定下限，寫成\d{m,}，比如\d{4,}，表示“數字字符串的長度必須在4個字符以上”。量詞限定的出現次數一般都有明確下限，如果沒有，則默認為0。
{m,n}是通用形式的量詞，正則表達式還有3個常用量詞，分別是+、?、*。它們的功能與{m,n}是相同的。
忽略優先量詞
忽略優先量詞（lazy quantifier或reluctant quantifier，也有人將其翻譯為懶惰量詞），如果不確定是否要匹配，忽略優先量詞會選擇“不匹配”的狀態，再嘗試表達式中之后的元素，如果嘗試失敗，再回溯，選擇之前保存的“匹配”的狀態。
標準匹配量詞與忽略優先量詞逐一對應，只是在對應的標準匹配量詞之后添加？，兩者限定的元素能出現的次數也一樣，遇到不能匹配的情況同樣需要回溯；唯一的區別在于，忽略優先量詞會優先選擇“忽略”，而標準匹配量詞會優先選擇“匹配”。
占有優先量詞
占有優先量詞是在標準匹配量詞之后接+字符，即*+、++、?+、{n}+、{n,}+和{n,m}+。占有優先量詞類似于標準匹配量詞，但是匹配的結果不會“交還”或者說回溯。
舉例來說，當正則表達式a.*b和a.*+b同時去匹配字符串acccb時，a.*b會匹配成功，而a.*+b會匹配失敗。原因是不管是.*還是.*+，它們都是匹配優先的，并且“貪婪”地匹配到了字符串acccb中的cccb，但是.*+不會回溯已匹配到的結果，所以正則表達式a.*+b中的b會發現這時候字符串中已經沒有b可以匹配，從而整個正則表達式匹配失敗。占有優先量詞能夠控制匹配和不能匹配的內容，在某些場合下使用占有優先量詞能夠提高匹配效率。
括號
分組
分組，將相關的元素歸攏到一起，構成單個元素。如果用量詞限定出現次數的元素不是字符或者字符組，而是連續的幾個字符甚至子表達式，就應該用括號將它們“編為一組”。比如，要求字符串ab重復出現一次以上，正則表達式為(ab)+，此時(ab)成為一個整體，由量詞+來限定；如果不用括號而直接寫ab+，受+限定的就只有b。
多選結構
多選結構，規定可能出現的多個子表達式。多選結構的形式是(…|…)，在括號內以豎線|分隔開多個子表達式，這些子表達式也叫多選分支（option）；在一個多選結構內，多選分支的數目沒有限制。在匹配時，整個多選結構被視為單個元素，只要其中某個子表達式能夠匹配，整個多選結構的匹配就成功；如果所有子表達式都不能匹配，則整個多選結構匹配失敗。
此外，多選結構的一般表示法是(option1|option2)（其中option1和option2是兩個作為多選分支的正則表達式），多選結構中一般會同時使用括號()和豎線|；但是如果沒有括號()，只出現豎線|，仍然是多選結構。
引用分組
引用分組，將子表達式匹配的文本存儲起來，供之后引用。
使用括號之后，正則表達式會保存每個分組真正匹配的文本，等到匹配完成后，通過group(num)之類的方法“引用”分組在匹配時捕獲的內容。其中，num表示對應括號的編號，括號分組的編號規則是從左向右計數，從1開始。因為“捕獲”了文本，所以這種功能叫作捕獲分組（capturing group）。對應的，這種括號叫作捕獲型括號。諸如2010-12-22、2011-01-03這類表示日期的字符串，從中提取出年、月、日之類的信息，就可借助捕獲分組來實現。
反向引用（back-reference），允許在正則表達式內部引用之前的捕獲分組匹配的文本，其形式是\num，其中num表示所引用分組的編號。根據反向引用，可以用來查找連續重疊字母。其表達式是([a-z])\1，其中的[a-z]匹配第一個字母，再用括號將匹配分組，然后用\1來反向引用。
在Python中，命名分組的記法為(?P
非捕獲分組
非捕獲分組（non-capturing group），用來標識那些不需要引用的分組。在開括號后緊跟一個問號和冒號(?:…)，這樣的括號叫作非捕獲型括號，它只能限定量詞的作用范圍，不捕獲任何文本。在引用分組時，分組的編號同樣會按開括號出現的順序從左到右遞增，只是必須以捕獲分組為準，會略過非捕獲分組。
斷言
并不真正匹配文本，而只負責判斷在某個位置左/右側的文本是否符合要求，這種結構被稱為斷言（assertion）。常見的斷言有三類：單詞邊界、行起始/結束位置、環視。
單詞邊界
單詞邊界（word boundary），記為\b。它匹配的是“單詞邊界”位置，而不是字符。即\b能夠匹配這樣的位置：一邊是單詞字符，另一邊不是單詞字符。其準確解釋為：一端必須出現\w能匹配的字符，另一端不出現\w能匹配的字符。在JavaScript、PHP、Python2、Ruby中，\w只能匹配[0-9a-zA-Z_]。所以在這些語言中，\b\w+\b能用來匹配幾乎所有的英文單詞。
單詞邊界并不區分左右，在“單詞邊界”上，單詞字符只能出現在一側；單詞字符要求“另一邊不是單詞字符”，即一邊必須出現單詞字符，另一邊可以出現非單詞字符，也可能沒有任何字符。所以，如果字符串只包含單詞word，用\bword\b應該是可以匹配的，雖然w之前和d之后都沒有任何字符。
行起始/結束位置
單詞邊界匹配的是某個位置而不是文本，在正則表達式中，這類匹配位置的元素叫作錨點（anchor），它用來“定位”到某個位置。除了\b，常用的錨點還有^和$。通常來說，它們分別匹配字符串的開始位置和結束位置，用來判斷“整個字符串能否由表達式匹配”。
一般情況下，^匹配整個字符串的起始位置。例如，正則表達式^Some可以準確驗證字符串“是否以Some開頭。因為^會把整個表達式的匹配“定位”在字符串的開始位置。這樣，即便表達式的其他部分可以在字符串中其他位置找到匹配，整個表達式也無法匹配成功。在某些情況下，^也可以匹配字符串內部的“行起始位置”。
$通常匹配的是整個字符串的結尾位置。如果最后是行終止符則匹配行終止符之前的位置，否則匹配最后一個字符之后的位置。如果指定了多行模式，$會匹配每個行終止符之前的位置。最后一行的情況有點特殊：如果最后一行沒有行終止符，則匹配字符串的結尾位置；否則，匹配行終止符之前的位置。與$類似的還有兩個特殊標記\Z和\z，它們不受多行模式的影響，在任何情況下都匹配整個字符串的結束位置。\Z和\z的主要差別在于：\Z等價于默認模式（非多行模式）下的$；\z則不管行終止符，只匹配整個字符串的結束位置。
環視
環視（look-around）用來“停在原地，四處張望”。環視類似單詞邊界，在它旁邊的文本需要滿足某種條件，而且本身不匹配任何字符。環視一共分為4種：肯定順序環視（positive-lookahead）、否定順序環視（negative-lookahead）、肯定逆序環視（positive-lookbehind）、否定逆序環視（negative-lookbehind）。在當前位置，如果是朝右判斷，則是順序環視；如果是朝左判斷，則是逆序環視；如果要求子表達式能匹配的字符串必須出現，則為肯定環視；如果要求子表達式能匹配的字符串不能出現，則為否定環視。
比如正則表達式<(?!/)，其中的(?!/)是一個環視結構，(?!…)是這個結構的標識，/才是真正的表達式，整個結構的意思是“當前位置之后（右側），不允許出現/能匹配的文本”。如果<(?!/)匹配成功，正則表達式真正匹配完成的只有<，而不包括<之后的那個字符，這樣，就能準確表示“匹配<，同時這個<之后不能是/”。
再如正則表達式(?，其中的(?，同時>之前不能是/”。
匹配模式
匹配模式（match mode），是正則表達式一個常用功能，指的是匹配時遵循的規則。設置特定的模式，可能會改變對正則表達式的識別，也可能會改變正則表達式中字符的匹配規定。常用的匹配模式一共有4種：不區分大小寫模式、單行模式、多行模式、注釋模式。
模式指定方式
通常，有兩種辦法指定匹配模式：以模式修飾符指定，或者以預定義的常量作為特殊參數傳入來指定。模式修飾符即模式名稱對應的單個字符，使用時將其填入特定結構(?modifier)中（其中的modifier為模式修飾符），嵌在正則表達式的開頭，常見的模式modifier的值有i、s、m。JavaScript是例外，JavaScript不支持模式修飾符(?modifier)的記法。另一種指定模式的方式是使用預定義的常量作為參數，傳入正則函數。
不區分大小寫模式
不區分大小寫的匹配模式對應的模式修飾符是i（case Insensitive）。例如，對the指定此模式，完整的正則表達式就是(?i)the，就可以匹配the、The、THE等各種大小寫形式的the。
單行模式
元字符點號.匹配除了換行符（\n）之外的任意一個字符。但是當需要匹配“任何字符”，比如在處理HTML源代碼時，經常會遇到跨越多行的腳本代碼，所以正則表達式提供了單行模式。在這種模式下，所有文本似乎只在一行里，換行符是這一行中的“普通字符”，所以可以由點號.匹配。即在單行模式下，點號.可以匹配包括換行符在內的任何字符。
單行模式對應的模式修飾符是s（Single line），所以如果用模式修飾符，可以在表達式的開頭用(?s)指定，因此上述HTML的正則表達式可以寫為(?s)
多行模式
多行模式影響的是^和$的匹配規則：在默認模式下，^和$匹配的是整個字符串的起始位置和結束位置，但在多行模式下，它們也能匹配字符串內部某一行文本的起始位置和結束位置。
多行模式的模式修飾符是m（Multi line），所以在表達式的開頭用(?m)指定多行模式，^定位到字符串內部每一行的起始位置，\d是匹配數字字符的表達式，.*匹配之后的整行文本，得到正則表達式為(?m)^\d.*。
注釋模式
指定注釋模式后，正則表達式可以添加注釋，對應的字符串可以跨越多行，方便閱讀和維護。注釋模式對應的模式修飾符是x（extended mode，擴展模式，但更常見的寫法是free-spacing mode，寬松格式模式）。
匹配算法
正則表達式的匹配通常是用有限自動機來解決的，具體又可以分為非確定性有限狀態自動機（Non-deterministic FiniteAutomata，NFA）和確定性有限狀態自動機（DeterministicFinite Automata，DFA）兩種，后者可以由前者轉化而來。另一方面，字符串是正則表達式的特殊情況，它本身不一定需要借助生成自動機來匹配，它的匹配有更豐富的算法可選擇。經典的字符串匹配算法有高德納Morris-Pratt（KMP），Boyer-Moore（BM），Aho-Corasick（AC）和吳語Manber（WM）等。
純字符串匹配
KMP （Knuth-Morris-Pratt）算法是一種用于單字符串匹配的傳統算法，其時間復雜度為O(n)，其中n為搜索串長度。其匹配過程中依次將搜索串每個位置的字符與模式串特定位置的字符做比較。工作特點為搜索串的位置不做回溯。當前位置匹配的情況下搜索串位置和模式串位置同步遞增1，而失配的情況下搜索串停留原位置與模式串當前位置的失配跳轉位置再做比較。其運行期算法很簡潔，關鍵在于預處理，即根據模式串自身的特點計算出失配函數，即模式串每個位置的失配跳轉位置。
BM（Boyer-Moore）算法是進行單字符串匹配的經典算法，其時間復雜度為O(n)，其中n為搜索串長度。相比KMP算法，BM算法的效率更高，各種文本編輯器（如Vim）大多采BM算法來實現查找功能。與KMP算法從模式串頭部開始向后進行比較不同，BM算法從模式串尾部開始向前進行比較。
AC（Aho-Corasick）算法是進行多字符串匹配的經典算法，廣泛應用于各類入侵防御系統（Intrusion Prevention System，IPS）/入侵檢測系統（Intrusion Detection System，IDS），以及深度報文檢測（Deep Packet Ispetion，DPI）解決方案做預過濾處理。有別于對單條字符串分別進行匹配，AC算法同時對所有字符串進行匹配，該算法的時間復雜度為O(n)，其中n為搜索串長度。
AC算法的本質是根據多字符串規則構造基于前綴樹（trie，又稱為字典樹）的DFA。該DFA運行過程中發生失配時跳轉至某前綴的其他分支，避免重復匹配前綴。這種方法比構造普通的NFA要高效，當然，可以對NFA做確定化處理得到DFA，AC算法構造DFA的過程更簡潔。
在 AC 算法構造的前綴樹中，根節點對應空字符串，其余每個節點保存一個字符。一個節點對應的字符串為從根節點到自身的路徑上經過的字符序列。每個節點都是其子孫節點的前綴。多字符串規則對應了前綴樹的所有葉子節點和部分內部節點。
表達式優先級
正則表達式的元素之間的組合關系有4種，分別是普通拼接、括號、量詞、多選結構。
正則引擎
正則表達式由正則表達式引擎驅動工作。正則引擎主要分為基本不同的兩大類：DFA（確定型有窮自動機）和NFA（非確定型有窮自動機）。經過多年的發展，DFA和NFA都產生了許多不必要的變體，為了規范這種現象出現了POSlX標準。POSIX規定了正則引擎應該支持的元字符和特性和使用者期望由表達式獲得的準確結果。如今各類程序的正則引擎可分為DFA、傳統的NFA、POSIX NFA、DFA/NFA混合四大類。
DFA和NFA反映了將正則表達式在應用算法上的根本差異。NFA稱為“表達式主導（regex-directed）”引擎，DFA稱為“文本主導（text-directed）引擎。
DFA引擎
確定型有窮自動機（DefiniteFinite Automata，簡稱DFA），它是詞法分析和模式識別領域中的常見工具。所謂“確定性”，指的是自動機運行過程中下一狀態轉移的唯一性：不同于NFA，在DFA中，每讀入一個輸入符號，當前狀態都會確定地轉入由狀態轉移規則所指定的下一個“唯一的”狀態。DFA仍然有初始狀態和結束狀態，但在自動機運行的任何時刻，都有且僅有一個激活狀態。
DFA由五元組形式定義：。其中，S是一個有限狀態集合，它的每一個元素稱為一個狀態。∑是一個字母表，它的每一個元素稱為一個輸入字符。δ是一個狀態轉移函數，本質是從S×∑到S的單值映射。對于S中的狀態s與s'，∑中的字符a，δ(s,a)=s'表示當激活狀態為s、輸入字符為a時，自動機將會轉換到下一個狀態s'。s0屬于S，是初始狀態；F'屬于S，是結束狀態集合（可以為空，也可以有多個）。
從形式定義來看，NFA和DFA的主要區別在于狀態轉換函數的映射屬性。如果允許δ是一個多值映射，顯然就可以得到NFA的概念，即DFA是NFA的特例。而且，對于每一個NFA，都存在一個DFA，使得二者能識別的正則表達式是相同的。DFA可以從NFA轉化而來。
NFA引擎
非確定型有窮自動機（Non-definiteFinite Automata，簡稱NFA），其“非確定”的含義是指在NFA的某個狀態上，通過某個字符輸入可能跳轉到多個后繼狀態，也可能沒有后繼狀態。NFA在任意時刻可以存在多個激活狀態，在運行時需要保存所有狀態的激活情況，并對所有激活狀態進行處理。
NFA的正式定義是一個五元組。其中，Q是一個有限狀態集；∑是一個有限的輸入字符集；Δ是狀態轉移函數：Q×∑→P(Q)，即Q與∑的勒內·笛卡爾積到Q的冪集的映射；q0是初始狀態；F是結束狀態集。從狀態轉移函數Δ可以看出，每一對狀態和字符被映射到冪集P(Q)的一個元素，而P(Q)中的元素可以是Q中任意狀態的集合或空集，從而可以看出NFA在給定狀態和字符條件下的跳轉終點是非確定的。
NFA又有傳統型NFA（Traditional NFA）和POSIX NFA兩種。兩者的主要區別在于，如果多選分支中的多個分支都能匹配，傳統型NFA優先選擇左側的分支，而POSIX NFA一定要選擇最長的分支。
回溯
回溯是NFA引擎最重要的特性，也是區分NFA引擎和DFA引擎的重要標志。NFA引擎會依次處理各個子表達式或組成元素，遇到需要在兩個可能成功的可能中進行選擇的時候，它會選擇其一，同時記住另一個，以備稍后可能的需要。即當NFA正則表達式中出現量詞（決定是否嘗試另一次匹配）和多選結構（決定選擇哪個多選分支，留下哪個稍后嘗試）這種需要做出選擇的情形時，回溯就可能會發生。
不論選擇那一種途徑，如果它能匹配成功，而且正則表達式的余下部分也成功了，匹配完成。如果正則表達式中余下的部分最終匹配失敗，引擎會知道需要回溯到之前做出選擇的地方，選擇其他的備用分支繼續嘗試。這樣，引擎最終會嘗試表達式的所有可能途徑（或者是匹配完成之前需要的所有途徑）。
Unicode編碼
Unicode是一組字符設定或者是從數字和字符之間的邏輯映射的概念編碼。Unicode由兩大部分組成，一部分是UCS（Universal Character Set），它定義了一個廣闊的空間，能把各種不同語言中的字符全部裝進去，為每個字符分配唯一的碼值（Unicode中的術語是Code Point）。另一部分是UTF（Unicode Transformation Format），它定義了UCS中的每個碼值以什么樣的方式來傳輸（和存儲）。
“Unicode編碼嚴格來說是指UCS，也可以叫“字符集”，它關心每個字符對應的碼值是多少，比如中文字符“正”的碼值是十進制的27491，十六進制的表示是6B63。討論Unicode時，常用的表示法是U+6B63。
Unicode屬性
每一個Unicode字符，除了有Code Point與之對應外，還具有其他屬性在正則表達式中常用到3種Unicode屬性：Unicode Property、Unicode Block、Unicode Script，分別對應字符的功能、所屬代碼區段、書寫系統；它們的表現形式類似\p{property}。
每個Unicode字符都只能屬于一個Unicode Property。BMP中所有的Unicode Property共分為7大類，30小類。大類的名字只有單個字母，小類的名字則包含多個字母，開頭字母與所在大類的名字相同，小類包含的字符都屬于它所在的大類。
Unicode Block不同于Unicode Property，它按照編碼區間劃分Unicode字符，各個區間彼此聯系但互不相交，所以每個Unicode編碼中的每個字符都有唯一歸屬的Unicode Block。在Unicode編碼表中，同一種語言的字符通常是落在同一區間的，所以Uni-code Block也可以粗略表示某類語言的字符，比如\p{InHebrew}表示希伯來語字符，\p{InCJK_Unified_ldeographs}表示兼容CJK（中文、日文、韓文）統一表意字符。
Unicode Script按照字符所屬的書寫系統來劃分Unicode字符，比如\p{Greek}表示希臘語字符，lp{Han}表示漢語（中文字符）。
POSIX字符組
解決具體問題
三種邏輯
正則表達式提供了一整套描述文本特征的方法，它的匹配就是查找符合所描述特征的文本的過程。按照元素（單個字符、字符組、多選分支等）的出現情況，這些特征分為三類，也可稱為三種邏輯：必須出現、可能出現、不能出現。
“必須出現”是正則表達式中最普通的邏輯關系，它表示某個元素必須出現。通常，這些元素是所要匹配文本的最重要特征：查找tag，則必須出現的是字符<和>；查找E-mail地址必須出現的元素是@。
如果某個元素必須出現，通常不會（也不應該）用量詞（*、?）來限制，也不出現在多選結構中（如果把普通的字符串也看作正則表達式，那么其中每個字符都是必須出現的）。所以，如果在匹配tag的正則表達式中，<和>出現在某個多選結構內，或者之后跟有？、*之類的量詞，那么這個表達式多半有問題；同樣，匹配E-mail地址的正則表達式中的@字符，也不應該有量詞限定，或者出現在多選結構內部。
與普通字符串處理相比，“可能出現”可以算作正則表達式最明顯的特征，也是最常用的邏輯。它分為兩種情況：從元素外來看，元素可能出現也可能不出現，或者出現次數不確定；從元素內來看，元素可能表現為一種形態，也可能表現為另一種形態。
第一種情況需要用量詞。在匹配雙引號字符串的正則表達式中，兩個雙引號字符是必須出現的，它們之間的文本可能出現，也可能不出現，如果出現，長度沒有限制，所以用*來限制；在匹配tag的正則表達式中，<和>之內的tag名必須包括至少一個字符，所以用+來限制。
第二種情況需要使用字符組或多選結構。如果各種可能形態都是單個字符，則使用字符組，比如匹配數字字符串正則表達式中的[-+]它說明“此處可能出現+號，也可能出現-號”。如果某一種可能形態不只是一個字符，比如this或that，則應該使用多選分支(this|that)。
正則表達式中的“不能匹配”，最簡單的情況可以用排除型字符組直接表示，但它只能表示“某個字符不能出現”；如果要表示“某個字符串不能出現”，一般都要用到否定環視，其邏輯是：在文本中的每個位置，都用環視否定“不能出現”的字符串。不過，一些比較古老的工具（比如Apache 13，以及Linux/unix下的某些工具）并不支持否定環視。
常見操作
正則表達式執行的操作，可以粗略分為三大類：匹配、替換、切分。其中，匹配是最基本的操作。廣義的“匹配”又可以分為兩類：提取和驗證。
提取
數據提取，就是“用正則表達式遍歷整個字符串，找出能夠匹配的文本”，它主要用來提取所需要的數據，常見的任務有：找出文本中的電子郵件地址，找出HTML代碼中的圖片、超鏈接······
Python數據提取使用到的方法為re.findall(pattern,string)。其中pattern是正則表達式，string是字符串。這個方法會返回一個數組，其中的元素是在string中依次尋找pattern能匹配的文本。
驗證
數據驗證是另一類“匹配”操作，它用來“檢查字符串能否完全由正則表，主要用來測試和保證數據達式匹配”的合法性，比如Web編程中經常用正則表達式驗證用戶輸入數據，比如手機號碼、郵件地址、QQ號碼等。驗證返回的是布爾值。
針對驗證操作的特點，有些語言中提供了專門的方法進行正則表達式驗證，以保證正則表達式匹配的起始/結束位置就是字符串的起始/結束位置而且返回布爾值。如果沒有提供專門的方法，通常的辦法是手動在正則表達式的首尾加上匹配字符串起始/結束位置的\A和\z，再通過返回值判斷。
提取返回的是字符串，驗證返回的是布爾值；提取時，正則表達式最終匹配的起始/結束位置都是不確定的，需要逐次試錯才能確定；驗證時，正則表達式的起始/結束位置必須定位于字符串的起始/結束位置，從字符串起始位置開始嘗試匹配，只要表達式中任意一個必須匹配的元素出現無法匹配的情況，即宣告驗證失敗，不必逐次試錯。假設正則表達式是\d{6}，字符串是a123456b，很明顯，提取操作中應當返回123456，但驗證操作應當返回False，因為表達式匹配的并不是整個字符串。
替換
替換操作也是一種“匹配”，它通常需要三個參數，其中regex（或pattern）表示查找需要替換文本的正則表達式，replacement表示“要替換成”的字符串，subject（或string、input）則是要進行替換處理的文本。
在默認情況下，替換是對所有的匹配實行的，也就是說，匹配發生了n次替換就會發生n次，但替換發生的最大次數往往可以用一個可選參數指定如果這個參數設定為負數，則會對所有匹配進行替換。
切分
切分操作一般需要兩個參數，即regex和string，它以regex能匹配的文本為間隔，將string切分開來。它返回的通常是一個數組，元素是切分之后的片段。
切分操作的簡單示例是切分單詞尤其是英文文本的單詞。英文文本用空格分隔各個單詞，比如This is a example of using regex，其中包含7個單詞，用6段空白分隔一其中的空白可能是空格符，也可能是制表符，還有可能是換行符。不過，無論這些空白字符是什么都可以由正則表達式\s+匹配；所以以這些空白為間隔，就可以把文本分隔為7段，每段一個單詞。
正則表達式提供了對Unicode Property的支持，Unicode Property按照字符的功能分類，\p{Po}表示“除橫線、括號、引號和連接符之外的任何標點符號”。
通常，切分會在所有匹配發生的地方進行，假設正則表達式能匹配n次，就切分n次，結果數組包含n+1個元素。不過，通常也可以用一個可選參數限制切分，將它設定為一個小于n的正數，則會進行n-1次切分（只有Python是例外，它會切分n次），返回數組的最后元素包含了“正則表達式第n-1次匹配右側的所有文本”。
SQL日志文件的每一行都包含三個字段，分別是發生時間、執行時間、SQL語句，以逗號分隔，而SQL語句中可能就包含逗號，這時需要顯式限定切分次數，否則就會麻煩很多。
語法支持情況
字符及字符組
①可以指定RegexOptions.ECMAScript恢復到ASCII匹配規則。
②Python2默認采用ASCI匹配規則，但指定Re.U模式可以變換為Unicode匹配規則；Python3默認采用Unicode匹配規則，但指定Re.A模式可以變換為ASCII匹配規則。
③Ruby1.9的POSIX字符組支持Unicode字符，且不需要顯式指定Unicode模式。
括號
①.NET中用(?人名>regex)表示命名分組，用\k
②PHP中用(?P
③Python中用(?P
④只有Ruby1.9支持命名分組，用(?
⑤Objective-C中用(?
⑥Golang中用(?P ①Java中的\w采用ASCII匹配規則，但\b采用Unicode匹配規則。 ②Ruby 1.9中的\b采用Unicode匹配規則。 ③objective-C中的\b和\w默認采用Unicode匹配規則，如果指定ASCII匹配規則，受影響的只有\b。 ④Ruby默認采用多行模式，^和$可以匹配行的起始/結束位置。 ⑤ECMAScript中的$無法匹配文本末尾行結束符之前的位置。 ⑥Python中的\Z等價于其他語言中的\z。 ⑦逆序環視中的正則表達式能匹配的文本長度必須有上限。 ⑧JavaScript必須到ES2017(TC39)之后才支持逆序環視，此時逆序環視的表達式沒有限制。 ⑨PHP中的逆序環視中的正則表達式匹配文本的長度可以不確定，可以是若干個值，但必須是固定值，多選結構只能出現在頂層。 ⑩Python的逆序環視中的正則表達式匹配的文本長度必須是固定的。 ?Ruby 1.8不支持逆序環視，Ruby 1.9的逆序環視中的正則表達式匹配的文本長度必須是固定的。 案例背景：實現過濾敏感詞admin和manager，忽略大小寫并將匹配到的內容（敏感詞admin和manager）替換成“*”。案例使用HTML語言。 首先在頁面中定義兩個文本域和一個按鈕，第1個文本域用來顯示用戶輸入的內容，第2個文本域用來顯示替換后的內容，當用戶輸入內容后，單擊“過濾”按鈕即可執行替換操作，具體代碼如下。 保存代碼，在瀏覽器中進行測試。在“過濾前”文本域中輸入“Admin and Manager”，然后單擊“過濾”按鈕，查看過濾后的頁面效果。在“過濾后”文本域中，敏感詞Admin和Manager都被替換成了“*”，說明利用正則表達式和replace()方法實現了替換敏感詞。 案例背景：已知某網站的HTML源代碼部分內容如下，要將該網頁內容存儲到計算機的D:/web.txt中。要求：請解析網頁中所有以https開頭的URL，并輸出。該案例使用Python。 模擬新用戶注冊網站賬號過程，由新用戶輸入注冊信息，包括注冊賬號、登錄密碼和手機號。網站在接收到用戶信息后進行驗證，驗證賬號、密碼和手機號的有效性。要求：賬號長度為6~10個字符，包含漢字、字母、數字、下劃線；密碼長度為6~10個字符，包含大小寫字母及下劃線，以字母開頭；手機號為中國大陸手機號。該案例使用Python。 參考資料 > 正則表達式 - 簡介.菜鳥教程.2023-12-21 正則表達式匹配器.北京大學數學科學學院.2024-01-07 34 年了，“殺”不死的 Perl！. CSDN微信公眾平臺.2024-01-06 perlintro.perl.2024-01-12 PCRE - Perl Compatible Regular Expressions.PCRE.2023-12-22斷言
匹配模式
代碼示例
過濾并替換敏感詞
網頁解析
驗證用戶注冊信息