正则表达式的原理通读
正则表达式
阅读本文需要有高中以上的集合论的知识，以及一般程度的java代码阅读能力。在阅读完本文以后，读者应当能从概念上高屋建瓴地掌握什么是正则表达式，并拥有一定的正则表达式的阅读和书写能力。
零、引言
字符串匹配这件事情说难不难，假如有一个集合c={"a","abc","bcd"}，给定一个目标字符串，我们要怎么判断目标字符串是否是集合c中的一员呢？
// 有一个集合c，包含了三个字符串
Set<String> c = new HashSet<>(Arrays.asList("a","abc","bcd"));
// 现在有一个被查询出来的字符串，怎么判断它是否在c中
String queryString = queryFromUserInput();
// queryString 在集合c中吗
这个问题很简单，上面的代码片段中，我们使用的是 java 的API，因此可以很轻易地用contains方法来判断字符串是不是在集合中。
// match 表示匹配的结果
boolean match = c.contain(queryString);
在match匹配之上，我们可以轻易构建出一个子串匹配的程序。
异常简单。不值一看，实在是不值一看。但它表现了一个字符串匹配的基本思想，上面短短三行代码，完整地体现了使用正则表达式匹配的基本过程。
一、匹配集合由何而来
根据上述的匹配流程，我们首先要定义一个用于匹配集合。
// 有一个集合c，包含了三个字符串
Set<String> c = new HashSet<>(Arrays.asList("a","abc","bcd"));
在这个简单的例子中，我们使用了穷举的手法来表示这个集合。
众所周知，穷举在表达所谓无穷的概念时非常吃力。在定义集合的时候，你可能这样——{1,2,3...}来向观众表达你的无穷集合。然而这个集合仍然是不明确的，当你使用省略号时，它就开始依赖于读者自身的常识。如果读者不会数数（这当然是不可能的），那么他就不能读懂这个集合表达的意思。
这迫使我们用运算表示"无穷"。换而言之，当我们想表达无穷多元素的集合时，我们运算。
在字符串集合上，我们定义三种基本运算，并且使用下面的java代码来阐述它们的具体含义。
// 正则集合的计算类
class RegularSetComputor{
// 并计算
// 这里简单
public static Set<String> union(Set<String> a, Set<String> b){
Set<String> result = new HashSet<>(a);
result.addAll(b);
return result;
}
// 连接计算
// 结果为a*b
// 我们看到，这个运算的本质是在笛卡尔积的基础上进行了字符串的加运算
public static Set<String> connect(Set<String> a, Set<String> b){
Set<String> result = new HashSet<>();
for(String factorA : a){
for(String factorB : b){
result.add(factorA + factorB);
}
}
return result;
}
// 闭包运算
// 从直观上看，闭包运算是对同一个集合进行0-n次的connect运算
// 但作为匹配方法，这样实现是不切合实际的，此外，一个集合抽象表现与它的具体实现也没有必要完全一致
// 读者最好在脑海里能有经closure运算后返回集合的大致画像
public static Set<String> closure(Set<String> a, boolean positive){
Set<String> result = new HashSet<>(){
// 这里覆盖了contains 方法
public boolean contains(String o){
// 空串检验
// 这里要与下面的positive变量检测呼应
if("".equal(o)){
return super.contains(o);
}
// 循环当前集合中的所有元素，this表示当前集合
for(String factor: this){
String toMatch = o;
// 这段代码展示了一个如何用计算表示无穷的例子
// 通常来说，在计算中表示无穷，不是迭代就是递归。
while(toMatch.startsWith(factor){
toMatch = toMatch.substring(toMatch.indexOf(factor));
}
// 截成空串意味着匹配完成
if("".equal(toMatch)){
return true;
}
}
// 没有匹配到任何一个字符串
return false;
}
};
result.addAll(a);
if(!positive){
// 非正闭包, 添加空串
result.add("");
}
return result;
}
}
对于最后一个闭包运算，这里需要做一些简单的解释。这个运算获得了一个看似无穷的结果，但需要澄清的是，计算机同样无法表示一个无穷的结果，因此我们针对集合的运算进行了重新覆盖，但也因为如此，我们没有覆盖元素获得的方法，这意味着如果你穷举这个集合的话，它仍然是一个有限的。不过，就字符串匹配用到"contains"方法来说，它确实是无穷的。
总得来说我们大致上通过上述三种运算来获得了下面这个关系——
[字符串集合] [运算] [另一个字符串集合] = [一个新的字符串集合]
我们甚至通过最后的闭包运算获得了——
[字符串集合] [闭包运算] = [一个新的无穷的字符串集合]
此外，在如何表达这个无穷的字符串集合的问题上，我建议读者多加思考一下为什么要这么做。
我们来看具体的例子。
假如我们有两个集合{a},{b}（方便起见，我不再使用双引号，默认集合里元素只有字符串类型）。
如果你对它们使用了union运算——我们用|来表示union运算。即{a}|{b}，我们获得了一个新的集合{a,b}。从上面的代码以及运算结果来看，这和集合本身的并计算没有什么两样，如果你对集合有基本的认识的话，这点应该是很好理解的。
如果你对它们使用了connect运算——我们用·来表示connect运算运算，即{a}·{b}，我们获得了一个新的集合{ab}，注意，这里的结果仅有一个元素"ab"，而上面并运算的结果是两个字符串"a","b"。
如果你对{a}使用了闭包运算——当positive参数为真时，我们用+表示，反之用*表示——{a}会变成{a,aa,aaa,aaaa,aaaa...}，这里无奈用上了省略号的表述方式，但读者应当清楚其中的规律。这里还要对positive参数进行一个说明，它表示最后的结果集中是否包含一个空串(非null)。
也就是说，我们可以使用一些基本的集合来进行运算，最终能够获得一些更复杂的集合。正则表达式正是如此。
此外，需要注意的是，上面指出的只是三种最基本的计算，当具体到一个正则表达式的实现引擎时，我们会介绍更多的集合运算。
二、正则中的基本集合
假如你写下一个字母a，它代表的是集合{a}。
·
假如你写下两个字母ab，它代表的是集合{a}·{b}, 按照connect计算的定义，结果也就是{ab}。
假如你写下三个符串a|b，它代表的是集合{a}|{b}，按照union计算的定义，结果也就是{a,b}。
我们先不关注运算，从上面的描述中，我们很快发现，在正则表达式中，一个字母代表的其实是一个基本集合。
a代表{a}，b代表{b}, c代表{c}。
还有哪些基本集合呢？
我们这里使用Java的正则引擎来逐步认识正则式，这里参考的是 Java Platform SE 8，读者可以点击链接以获得进一步的信息。
1. 普通字符和转义字符
一个字符是一个基本字符串集合。
例如 a,b,c,d,e,f,g，分别代表{a},{b},{c},{d},{e},{f},{g}。
一个转义字符是基本字符串集合。
例如 \t,\n,\r,\f，分别代表{\t},{\n},{\r},{\f}。
它们定义了字符串长度为1，且集合长度为1的情况。
2. 抽象字符
抽象字符通常不在一个字符集中指定具体的编码。一个常见的抽象字符的例子就是换行符。
你要如何判断一个字符行结束了呢？有经验的程序员会告诉你，这取决于你现在处于哪个操作系统上。如果你是在Linux，那么换行符是\n；而如果你在windows上，换行符就是\r\n。
有些抽象字符与普通字符的区别主要是历史原因，或者说人为因素。例如换行符完全可以在字符集上指定一个单独的编码。
在正则中，抽象字符主要指那些边界（Boundary ）字符。
最常见的，^代表一个字符行的开始。
$ 代表一个字符行的结束。
3. 字符类
字符是可以分类的。
譬如 1,2,3,4,5,6,7,8,9，这些字符代表数字类。
又譬如 a,b,c,d....，这些字符代表字母类。
我们用一个类似转义的符号标识一个字符类，例如\d代表数字类，它表示集合{0,1,2,3,4,5,6,7,8,9}。
字符类简化了一个基本集合的表达方式，如果没有字符类，我们就要通过运算来表示这个集合。
{0,1,2,3,4,5,6,7,8,9} = {0} | {1} | {2} | {3} | {4} | {5} | {6} | {7} | {8} | {9} = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
通常认为简化的表达方式有助于推动思考。
比如当我们想表达一个“由4个数字组成的字符串”时，我们能把注意力从数字这个细枝末节中移开——我们知道\d表示数字类，然后重复四次，只需要对数字类集合进行四次笛卡尔积，然后连接字符串即可，结果就是\d{4}。其中{4}是一个类似于closure的计算，closure表示允许0到正无穷次正交运算，而{4}把这个数字限制在了一个具体的4次。
通常正则表达式引擎定义好了一组预定义好的字符类，例如上面提到的\d, 又比如代表所有字符的点.。
此外，它还允许你定义自己的字符类。
一个自定义的字符类以[开头，以]结束，要出现的字符无间隙地出现在中间。
例如[kfc]代表了{k,f,c}。这里比较反直觉，kfc不是"kfc"，需谨慎。
三、正则引擎中的计算实现
集合计算的实现是定义无穷集合关键性的一环。
正则引擎提供了两类计算，一种是逻辑计算，另一种是类闭包计算，后者可以简单记为量词计算，或者说quantifiers，有英语基础的读者可以直接记这个词，因为中文里的量词原义和quantifiers本不是一回事。
1. 逻辑计算
按照Java SE 8的记载，逻辑计算有三种，分别是连接运算、并运算以及捕获运算。
连接运算和并运算合并两个集合，具体描述在RegularSetComputor.union和RegularSetComputor.connect中已有体现，这里不再赘述。
至于捕获运算暂且搁置，留到后文在说。
是的，这确实等于是什么都没有说的一节，其目的仅在于构建一个合理的逻辑结构。
2. 类闭包运算
类闭包运算逻辑上基于connect和 union计算来实现，而其进一步又可以分为贪婪算法与懒惰算法两大类。
基本的用法列在下面，我们用一个X代表一个基本字符集，并以半文半代码的形式描述计算。
X? = X union 空串
X* = (X 与自身进行了0~n次connect运算) union 空串
X+ = X 与自身进行了0~n次connect运算
X{n} = X 与自身进行了n-1次connect运算
X{n,} = X 与自身至少进行了n-1次connect运算
X{n,m} = X 与自身进行了n-1~m-1次connect运算
在不特别指定的情况，默认使用贪婪匹配。如果在每一个符号后多加上?，则会变成懒惰匹配。例如:
X?? = X union 空串
X*? = (X 与自身进行了0~n次connect运算) union 空串
X+? = X 与自身进行了0~n次connect运算
X{n}? = X 与自身进行了n-1次connect运算
X{n,}? = X 与自身至少进行了n-1次connect运算
X{n,m}? = X 与自身进行了n-1~m-1次connect运算
读者似乎发现了我们对它们的描述没有任何区别，事实上，贪婪和懒惰匹配模式不影响字符串的定义，它事关匹配的实现。我们可以用下面的例子来说明它们的区别）。
Set<String> c = new HashSet<>(Arrays.asList("a","abc","abcbbc"));
// 给定一个待匹配串
String queryString = "abcbbc";
// 贪婪模式匹配出"abcbbc"
String greedySubString = greedySubStringMatch(queryString, c);
// 懒惰模式匹配中"abc"
String reluctantSubString = reluctantSubStringMatch(queryString, c);
鉴于我们现在已经了解了正则表达式的基本构成。
我们用a.+c或a.+?c来表示new HashSet<>(Arrays.asList("a","abc","abcbbc"));。当然，实际上后者是前者的子集。但无论如何，我们在这里想说的是，从概念模型来说，a.+c和a.+?c不会影响它所定义的集合，它只是指示匹配阶段的算法。
四、捕获运算
1. 捕获组
我们反复提到使用计算来描述无穷集合，现在让我们重新回到之前的例子。
Set<String> result = new HashSet<>(){
// 这里覆盖了contains 方法
public boolean contains(String o){
// 空串检验
// 这里要与下面的positive变量检测呼应
if("".equal(o)){
return super.contains(o);
}
// 循环当前集合中的所有元素，this表示当前集合
for(String factor: this){
String toMatch = o;
// 这段代码展示了一个如何用计算表示无穷的例子
// 通常来说，在计算中表示无穷，不是迭代就是递归。
while(toMatch.startsWith(factor){
toMatch = toMatch.substring(toMatch.indexOf(factor));
}
// 截成空串意味着匹配完成
if("".equal(toMatch)){
return true;
}
}
// 没有匹配到任何一个字符串
return false;
}
};
首先，我们限定，每一个无穷集合都有一个可描述的规律，随机无穷集合不在我们讨论范围当中，这种集合是不可匹配的。
Set<String> infinite = getInfiniteSet();
infinite是一个上述无穷集合, 调用它的contains方法会发生什么呢？
infinite.contains("ababab");
假设我们的无穷集合内部集合中存在一个"ab"元素。当我们传入"ababab"后，它就会开始自左向右扫描传入的字符串，判断给定的字符串是否符合此无穷集合的规律。
在这个集合中，它需要是自身某一个元素的不断重复。
这个模拟匹配过程实现有两个通用实现的特征：1. 自左向右；2. 符合无穷集合的规律。
捕获运算是这么一种运算，它允许你在自左向右的匹配过程中，将一部分已经符合规律的字符串作为变量保存下来。
举例来说我们有正则式(abc)b+\1。
然后我们一个待匹配字符串abcbbbbabc，在自左向右的匹配过程中，我们在匹配完成abc这个部分后，就将它保存下来，并自动命名为\n。其中，n是从1开始计数的第n个捕获组。
继续看，abc匹配到了(abc)，bbbb将匹配到b+，而当引擎看到\1时，就可以粗暴的认为接下来要匹配的字符串是之前存好的abc，而它向后看待匹配串，发现确实如此，于是匹配完成。
我们可以使用(?<name>X)的形式为分组命名。
如果我们在同一个正则串的后半部分引用前面的捕获组，就叫作反向引用，就像前一个例子一样。但捕获组还可以在替换字符串的时候使用，在java中，java.util.regex.Matcher对象的replaceAll和replaceFirst提供了以${}的形式来引用捕获组的功能。
2. 非捕获组
此外，需要提到的是，(?:X)用以构造一个非捕获组，它通常用来作为构成一个逻辑结构，但排除了被捕获的必要。也就是说，对既没有反向引用的必要，也没有替换的必要。合理使用非捕获组使得正则的结构更加清晰，同时也不占有多余的内存空间。
但更多情况下，我们使用这个结构来进行一些额外的控制，我们不想捕获它，而只是想对一个分组进行额外控制，如——
(?idmsux-idmsux:X)，其中idmsux是一组标记选项，可以单独使用。例如(?i:abc)这种写法使得此组匹配不区分大小写。
3. 条件匹配
正则表达式中的条件匹配分为两类，一类是由贪婪和懒惰所定义的条件，即如果是选择了贪婪模式，只要还能继续向后读，就不停止。反之，懒惰模式下，如果匹配器读到一个字符，使得当前模式已经匹配完成，就不再继续向后读字符。
这里的条件是指，当模式已经匹配完成时，是否还要向后继续读字符，以获得最大匹配。
第二类条件匹配指前看匹配和后看匹配。
我们以向前匹配为例——它具有一个通用格式(?=X)。
假如我们有一个正则表式达ab(?=mc)。给定待匹配串abmc，匹配过程是什么样的呢?首先ab正常匹配完成，引擎读到了(?=标记，于是它在这里做一个标记，然后继续向下匹配。之后的匹配过程没有什么不同，mc顺利匹配完成。但引擎知道自己曾经遇到过(?=标记，于是它把自己当前状态“向前看”到了标记的时间。
这里要解释一下“向前看”、“向后看”的含义。由于我们采用自左向右的读取规则，向后看一个字符指当前指针向右移动一个字符（通常还意味着读取这个字符），而向前看一个字符意味着当前指针向前移动一个字符。
引擎回到了向前看，回到标记时的状态，并表现出自己好像没有读过后面的字符一样。然而事实上，它不仅读过，而且如果后面的字符没有匹配上的话，还会抛出一个匹配失败错误。最终我们匹配到了ab，对于mc来说，引擎好像就只是去看看，看完马上回到原来的地方。
这形成了一个事实上的条件，我们想要匹配一个后面跟着mc的ab串。换而言之，ab串得到匹配的条件是后面须跟着一个mc串。
(?<=X)，后看匹配拥有相似的语义。但向后看本来就是正常的匹配过程，因此它也不需要进行状态标记，只需要把它看过前面的结构这件事丢掉即可，读者可以自行举例理解。
五、总结
正则表达式匹配拥有两个不同的侧面，一是正则表达式匹配过程的抽象——它不过是定义了一个集合，然后从集合中查找有没有符合条件子串而已；二是匹配引擎的具体实现可能还包含一些额外的控制项，这些控制项有些可以作为集合的运算理解，例如忽略大小写控制，有些可以作为匹配算法的控制，例如贪婪和懒惰，前看与后看匹配，其本质是匹配状态的转移和保存。
关于从集合中匹配这件事，看似没有什么作用，但它是一种通用思想。更一般的说，我们所使用的编程语言——甚至是自然语言，也可以纳入集合论的范畴，它们不过是一些字符串的无穷集合而已。编译器的一项主要工作（语法解析），就是判断一个给定的文件中的字符串是否符合这个无穷集合的规律。雕塑家米开朗基罗曾说“雕塑就是去掉不要的部分”，而我们程序员同样可以说“编程就是从编程语言集合所表示的串中去除那些不正确的部分”。伟大的艺术是相通的。
