Question

正则表达式原理

Answer 1

首先先讲解下正则表达式的基础知识：

　　1.字符串的组成

　　对于字符串”123“而言，包括三个字符四个位置。如下图所示：

　　2.占有字符和零宽度

　　正则表达式匹配过程中，如果子表达式匹配到东西，而并非是一个位置，并最终保存到匹配的结果当中。这样的就称为占有字符，而只匹配一个位置，或者是匹配的内容并不保存到匹配结果中，这种就称作零宽度，后续会讲到的零宽度断言等。占有字符是互斥的，零宽度是非互斥的。也就是一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配。

　　3.控制权和传动

　　正则表达式由左到右依次进行匹配，通常情况下是由一个表达式取得控制权，从字符串的的某个位置进行匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的（例如：（表达式一）（表达式二）意思就是表达式一匹配完成后才能匹配表达式二，而匹配表达式二的位置是从表达式一的位置匹配结束后的位置开始）。如果表达式一是零宽度，那表达式一匹配完成后，表达式二匹配的位置还是原来表达式以匹配的位置。也就是说它匹配开始和结束的位置是同一个。

　　

　　举一个简单的例子进行说明：正则表达式：123

　　源数据：123

　　讲解：首先正则表达式是从最左侧开始进行匹配，也就是位置0处进行匹配，首先得到控制权的是正则表达式中的“1”，而不是源数据中的“1”，匹配源数据中的“1”，匹配成功，将源数据的“1”进行保存到匹配的结果当中，这就表明它占有了一个字符，接下来就将控制权传给正则表达式中的“2”，匹配的位置变成了位置1，匹配源数据中的“2”，匹配成功，将控制权又传动给了正则表达式的“3”，这时候匹配的位置变成了位置2，这时候就会将源数据中的“3”进行匹配。又有正则表达式“3”进行传动控制权，发现已经到了正则表达式的末尾，正则表达式结束。

Answer 2

。

正则表达式的基础运算符
正则表达式包含很多的元字符来表达规则，不过本文不是要介绍如何使用正则表达式，关于正则表达式规则最好的参考书是《精通正则表达式》。

实际上，正则表达式核心的运算符只有以下几种：

名称 示例 备注
或运算 r|s 匹配的语言是L(r)和L(s)的并集
连接运算 rs 匹配的语言是L(r)和L(s)连接
Kleene运算 r* 匹配的语言是L(r)和L(s)连接
括号 (r) 匹配的语言与L(r)一致
kleene运算符优先级最高，且是左结合的，连接第二，或运算优先级最低。

运算定律:

示例 备注
r|s = s|r | 运算满足交换律
r|s|t = r|(s|t) | 满足结合律
r(st) 连接可以结合
r(s|t) = rs|rt 连接对|可以分配
ℇr = rℇ = r ℇ是连接的单位元
r* = (r|ℇ)\* 闭包中一定包含ℇ
r** = r* *具有幂等性
扩展运算符使得正则表达式更具表达力，下面仅举几个例子：

扩展运算符 等价形式
+ r+ = rr* = r*r
？ r? = r | ℇ
字符类 [a1a2…an] = a1|a2|…|an；如果是连续的字符类，可以写成[a1-an]
高级特性：

正则表达式具备很多高级特性，比如捕获、环视、固化分组等等，这些特性是为了提高正则表达式的实用价值被设计出来的，不属于正则文法的范畴。

NFA和DFA
前面说过，正则文法对应于有限状态自动机，又分确定型有限状态自动机(DFA)和非确定型有限状态自动机(NFA)，这两种状态机的能力是一样的，都能识别正则语言。正则表达式的识别引擎，都是基于DFA或NFA构造的。关于状态机的基础理论，这里就不描述了，只要稍微有点印象，就不妨碍继续阅读。

NFA

一个字母可以标记离开状态的多条边，并且ℇ 也可以标记一条边；这说明NFA的匹配过程面临很多的岔路，需要做出选择，一旦某条岔路失败，就需要回朔。

下图是正则表达式(a|b)*abb对应的NFA，它相当直观，基本可以从正则表达式直接转换而来。

DFA

对于每个状态以及字母表中的每个字母，只能有一条以该字母为标记的，离开该状态的边；这说明DFA的匹配过程是确定的，每个字母是需要匹配一次。

与上面NFA等价的DFA如下图，相当地不直观：

将NFA转化成DFA
由于NFA和DFA的能力是一样的，每个NFA必然可以转化成一个等价的DFA。既然DFA对每个输入可以到达的状态时是确定的，那么输入串s在NFA中可能达到的状态集合对应为等价DFA中某个状态。从这个思路出发，可以构造出DFA。

首先NFA的初始状态0不接受ℇ ，因此可以构造出DFA的初始状态(0)；
集合(0)输入a，在NFA中能够到达(0，1)，于是构造出此状态，以及从(0)到(0，1)的边，标记为a
集合(0)输入b，能到到达的还是(0)，因此构造出从(0)到自身的一条标记为b的边
集合(0，1)输入a，能能够到达的还是(0，1)，与上一步类似
集合(0，1)输入b，能够给到达的是(0，2)，构造状态(0，2)及相应的边
集合(0，2)输入a， 能够到达(0，1)，没有新状态，添加一条边
集合(0，2)输入b，能够给达到(0，3)，构造新状态(0，3)
集合(0，3)输入a，能够到达(0，1)，添加一条边即可
集合(0，3)输入b，能够给达到(0)，添加一条边即可
没有新状态，结束
最终得到的DFA如下，(0，3)包含了NFA的终结状态3，因此也是DFA的中介状态，对状态重新命名可以得到上面同样的DFA。

DFA和NFA的效率差异

很容易理解，构造DFA的代价远大于NFA，假设NFA的状态数为K，那么等价DFA的状态数目理论上可达2的k次方，不过实际上几乎不会出现这么极端的情况，可以肯定的是构造DFA会消耗更多的时间和内存。

但是DFA一旦构造好了之后，执行效率就非常理想了，如果一个串的长度是n，那么匹配算法的执行复杂度是O(n);而NFA在匹配过程中，存在大量的分支和回朔，假设NFA的状态数为s，因为每输入一个字符可能达到的状态数做多为s，那么匹配算法的复杂度及时输入串的长度乘以状态数O(ns)。

正则表达式的NFA&DFA构造、转化、简化有一整套理论及方法，远比上面的例子复杂，本文仅通过一个简单的例子来说明原理。

NFA与DFA的能力差异
NFA和DFA这两种匹配算法，除了效率上的差别外，从更高的视点看，形成了两种风格的引擎，进而对正则表达式的匹配的其他方面能力造成差异。NFA被称之为"表达式主导"引擎，而DFA被称之为“文本主导”引擎。

NFA：表达式主导
从表达式的第一个部分开始，每次检查一部分，同时检查当前文本是否匹配表达式的当前部分，如果是，则继续表达式的下一部分，如此继续，直到表达式的所有部分都能匹配，即整个表达式匹配成功。

我们来看表达式to(nite|knight|night)匹配文本...tonight...的过程: 表达式的第一个部分是t，它会不断重复扫描，直到在字符串中找到t，之后就检查随后的o，如果能匹配就继续检查下面的元素。这个例子中，下面的元素是(nite|knight|night)，意思是nite或者knight或者night，引擎会依次尝试这三种可能。

整个过程，控制权在表达式的元素之间转换，因此被称之为“表达式主导”。“表达式主导”的特点是每个子表达式都是独立的，不存在内在联系。 子表达式与整个正则表达式的控制结构(多选、量词)的层级关系控制了整个匹配过程。

DFA：文本主导
DFA在读入一个文本的时候，会记录当前有效的所有匹配的表达式位置(这些位置集合对应于DFA的一个状态)。 以上面的匹配过程为例：

当引擎读入文本t时，记录匹配的位置是to(nite|knight|night)；
接着读入o，匹配位置to(nite|knight|night)；
读入n，匹配位置to(nite|knight|night)，两个位置，knight被淘汰出局；
...
这种方式被称之“文本主导”是因为被扫描的字符串，控制了引擎的执行过程。

差异之一：NFA表达式影响引擎
NFA表达式主导的特性，使得通过修改正则表达式来影响引擎，因此下面三个表达式尽管能够匹配同样的文本，但是引擎的执行过程各不相同：

to(nite|knight|night)
tonite|toknight|tonight
to(k?night|nite)
但是对于DFA来说，没有任何区别。

差异之二：DFA能保证最长匹配
对于包含或选项的表达式，NFA在成功匹配一个选项之后可能报告匹配成功，此时并不知道后面的选项是否也会成功，是否包含一个更长的匹配。

假设使用one(self)?(selfsufficient)?来匹配oneselfsufficient，NFA首先匹配one，然后匹配self，此时发现selfsufficient无法匹配剩余子串，但是这个子表达式不是必须的，因此可以立即返回成功，此时匹配的串为oneself。

实际上NFA引擎的匹配结果与具体实现有关，而DFA必然会成功匹配oneselfsufficient。

差异之三：NFA支持更多功能
NFA能够支持“捕获group”，“环视”，“占有优先量词”，“固话分组”等高级功能，这些功能都基于“子表达式独立进行匹配”这一特点。 而DFA无法记录匹配历史与子表达式之间的关系，因而也无法实现这些功能。

可见NFA引擎具备更大的实用价值，因而，我们在编程语言里面使用的正则表达式库都是基于NFA的。java的Pattern就是基于NFA的，Pattern.compile()方法显然就是在构造NFA状态图。

参考资料