正则表达式，又称规则表达式、常规表示法（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< name >regex)，其中的name是赋予这个分组的名字，regex则是分组内的正则表达式。例如，匹配年月日的正则表达式中可以给年、月、日的分组分别命名，再用 group (name)来获得对应分组匹配的文本。
非捕获分组
非捕获分组（non-capturing group），用来标识那些不需要引用的分组。在开 括号 后紧跟一个问号和冒号(?:…)，这样的括号叫作非捕获型括号，它只能限定量词的作用范围，不捕获任何文本。在引用分组时，分组的编号同样会按开括号出现的顺序从左到右递增，只是必须以捕获分组为准，会略过非捕获分组。
断言
并不真正匹配文本，而只负责判断在某个位置左/右侧的文本是否符合要求，这种结构被称为断言（assertion）。常见的断言有三类：单词边界、行起始/结束位置、环视。
单词边界
单词边界（word boundary），记为\b。它匹配的是“单词边界”位置，而不是 字符 。即\b能够匹配这样的位置：一边是单词字符，另一边不是单词字符。 其准确解释为：一端必须出现\w能匹配的字符，另一端不出现\w能匹配的字符。在 JavaScript 、 PHP 、 Python 2、 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)<script\s.*?</script>。
多行模式
多行模式影响的是^和$的匹配规则：在默认模式下，^和$匹配的是整个字符串的起始位置和结束位置，但在多行模式下，它们也能匹配字符串内部某一行文本的起始位置和结束位置。
多行模式的模式修饰符是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匹配规则； Python 3默认采用Unicode匹配规则，但指定Re.A模式可以变换为ASCII匹配规则。
③ Ruby 1.9的POSIX字符组支持Unicode字符，且不需要显式指定Unicode模式。
括号
①.NET中用(? 人名 >regex)表示命名分组，用\k<name>在表达式中引用分组，用${name}在替换中引用。
② PHP 中用(?P<name>regex)表示命名分组，用(P=name)在表达式中引用分组，替换中不能引用命名分组。
③ Python 中用(?P<name>regex)表示命名分组，用(P=name)在表达式中引用分组，用\g<name>在替换中引用。
④只有 Ruby 1.9支持命名分组，用(?< name >regex)表示命名分组，用\k<name>在表达式中引用分组，用\k<name>在替换中引用。
⑤ Objective-C 中用(?<name>regex)表示命名分组，用\k<name>在表达式中引用分组，在替换中引用的方法未知。
⑥Golang中用(?P<nameregex)表示命名分组，命名分组的反向引用和在替换中引用的方法未知。
断言
①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 。