.2020-12-30
< view all posts正则相关的介绍通常很少提到正则的工作原理，也就是编辑器或编程语言具体是如何对正则进行匹配的。不过了解正则的执行方式实际上对理解正则是很有帮助的。
这篇文章参考了regular-expressions.info、正则表达式30分钟入门教程、微软的正则表达式参考文档。尤其是其中的第一个，对于希望深入理解正则的同学来说是非常好的学习资源。
在编程语言内部，正则表达式会被编译为自动机或树，在得到一个编译好的正则引擎之后，机器就会从第一个字符开始，对每个字符都使用这个引擎判断一次。
例如对字符串"abcababa"，匹配正则表达式"aba"，首先将字符串的第1个字符'a'输入正则引擎，发现和正则表达式的第一位规则a匹配，接着继续判断第2个字符'b'，发现和正则表达式的第二位规则b匹配，继续判断第3个字符'c'，和正则表达式的第3位a不匹配，说明从第1个字符开始输入无法和表达式匹配。因此下一步，从第2个字符开始，将'b'输入正则引擎，发现匹配失败。再输入第三个字符'c'，匹配失败。
接着输入第四个字符'a'，匹配成功，继续向后判断'b'和'a'，也匹配成功，此时成功找到了匹配，匹配会立刻停止。下一次再开始匹配时，会从已经匹配成功的部分的后面一个字符开始输入到正则引擎。在这个例子中也就是从剩下的"ba"开始再做匹配，匹配均失败。所以"ababa"只会匹配到一个结果"aba"，而不是两个。
字符串向正则引擎的输入顺序是从左到右的，引擎对正则规则的判断顺序也是从左到右的。有一点需要注意的是，当正则中匹配到anchors（也就是^ $ \b和\B）时，正则引擎以输入字符的前后两个位置为基准作匹配，而非以“字符本身的位置”为基准。
例如字符串"ax a"匹配正则"\b a\b"（注意a前有空格），首先将第1个字符'a'输入正则引擎，判断第一位规则\b，此时因为'a'的左边位置是字符串的起始位置，并且'a'本身属于\w，所以匹配成功。因为刚匹配的\b只是一个对位置的断言，所以此时不会判断下一个字符，而是对同一个字符'a'继续匹配下一个规则，即字符为空格，匹配失败。此时输入第2个字符'x'，首先对'x'的左边位置匹配规则\b，可以理解成放了一个光标在'x'左边，要求这个光标的左右至少有一个\W（非单词字符）。发现这个位置的左边是'a'右边是'x'，都是单词字符，匹配失败。接着输入第3个字符空格，匹配\b时同样的，把一个光标标放到空格的左边，因为这个光标的右边是空格本身，所以肯定可以匹配\b成功，接下来匹配规则字符为空格，成功。继续判断后面一个字符'a'，匹配规则a，成功，最后匹配第二个\b，发现'a'右边是字符串的结束位置，而且它本身是\w，所以匹配成功。找到匹配" a"。
为什么上面强调了对于anchor，匹配的基准是前后两个位置而非字符本身呢。可以想一下，如果错误理解成匹配字符的话，上面的例子是匹配不到结果的，因为在向正则引擎输入空格字符时，空格本身的前后都是字母，不符合至少有一个\W的条件，不会被匹配到。
当正则中含有数量词时，执行方式需要引入新的机制：循环和回退/前探。在贪婪模式下，对一个有数量词后缀的正则规则，只要输入的字符能够满足规则，就不断向后读新的字符，直到规则不再满足。此时如果对循环次数存在要求，判断循环次数，如果循环次数也符合要求，那就将不满足当前规则的字符交给下一条规则判断。如果判断为不匹配，则需要涉及到回退。回退稍微有点复杂，通过下面的例子来说明：
例如对字符串"bxaxc!"匹配正则"[abcx]+x"，首先将第1个字符'b'输入正则引擎，满足规则[abcx]，继续输入下一个字符，循环进行，直到输入了'!'，不再满足规则[abcx]，停止循环，因为循环进行的次数大于等于1，满足规则+的要求，所以把'!'交给下一个规则x来判断，发现不能匹配规则x。注意这时候虽然匹配失败了，但是我们却不能像之前那样直接开始输入第2个字符：从上帝视角我们能看到，显然字符串的开头"bxax"是满足"[abcx]+x"的，但因为这个正则是贪婪的，循环并没有在这个匹配处停下来而是继续向前走了。换句话说，正则引擎此时不知道是不是由于贪婪而导致自己循环过头了。因此，引擎需要开始回退。
回退的过程是这样的："bxaxc"是引擎已知的满足规则[abcx]+的最长长度，对这个结果向前回退一个字符，得到"bxax"，首先判断它的长度还是不是满足+的要求，也就是大于等于1，发现是满足的，那么就把"bxax"的下一个字符'c'交给规则x匹配，发现依然不能匹配；引擎接着回退两个字符，得到"bxa"，检验长度后把"bxa"的下一个字符'x'交给规则x匹配，发现匹配成功了。这时候成功找到了一个满足整个正则表达式的匹配，引擎立刻停止并报告结果"bxax"。这也说明了为什么在贪婪模式下不会匹配到前一个"bx"，而是会匹配最长的"bxax"：回退是从右向左的。
如果引擎把已知的字符串回退到了符合规则的最小长度还没有发现匹配，才会认为对第1个字符的匹配失败了，输入第2个字符。
注意贪婪模式使用不当可能导致写出错误的正则。例如对于字符串"<tag>a</tag>"，我们希望匹配其中的标签，看上去好像可以用正则"<.+>"，但实际上这会匹配到整个字符串。这是因为在循环中输入'>'时，会判断规则.（点号），显然尖括号和正则.是匹配的，所以循环会一直继续下去，直到来到字符串末尾。如何处理循环到末尾的情况呢，我们可以认为字符串末尾存在着一个虚拟字符，它不能和任何正则表达式相匹配。在循环到这个虚拟字符时，规则.匹配失败了，循环停止，且引擎将这个虚拟字符交给下一个规则>去匹配，也必然是失败的，此时引擎开始回退。因为整个字符串，即"<tag>a</tag>"是引擎已知的满足"<.+"规则的最长长度，回退一位后，发现退出来的'>'立刻就满足了规则>，引擎此时停止匹配，并报告找到了结果，也就是整个字符串。
而在懒惰模式下，引擎的循环不使用回退而是使用前探机制：只要循环的次数达到了下限，每循环一次就尝试一下当前正则是否已经满足。在上面的例子中，使用懒惰正则"<.+?>"，流程是这样的：规则+要求循环.（点号）至少一次，因此在输入't'之后立刻达到了次数的下限，引擎此时暂停循环，先尝试一下后面一个字符'a'是否满足下一个规则>，发现不能满足，继续循环一次，然后暂停并判断……当循环停在输入'g'时，发现整个正则可以被满足了，立刻停止。
补充一点，在这个例子中用懒惰的+是可以完成对标签的匹配的，但是我们可以看到，懒惰匹配时每循环一次就要停下来前探一次，因此在这个例子里，用正则"<[^>]+>"效率会更高。
替换构造的实现机制：例如匹配a(b|c)d，先匹配a，匹配到之后匹配bd，如果失败，匹配cd。替换构造有一个容易写错的地方，下面进行说明：
之前提到了，正则引擎在成功找到一个匹配时会立刻停止并报告这个匹配，再让它继续查找的话，会从已经找到的匹配的后面一个字符开始输入。因此，比如我们要从一个名册中匹配三个名字：Dan Daniel 和 Danny，如果使用正则"Dan|Daniel|Danny"，实际上只能匹配到所有的"Dan"。这是因为正则规则从左向右判断，当Dan为真时，整个正则就已经匹配成功了，引擎就会立刻停下。
那怎么写是正确的呢，最简单的方法是调整一下位置，用"Daniel|Danny|Dan"，或者可以改成让正则引擎必须在匹配到单词边界之后才能停下："\b(Dan|Daniel|Danny)\b"
另一个和替换构造相关的内容是原子组。原子组的含义是如果正则引擎发现在原子组（外）右侧的规则匹配失败，则不再尝试原子组内的其它替换选项。
例如我们希望匹配文本中所有的"good!"或"nice!"或"cool!"，可以写出正则"\b(good|nice|cool)!"，这个正则是正确的，但是对于一个"good."，正则引擎在匹配到good之后，会发现右边是句号'.'而非感叹号'!'，实际上正则已经不可能成立，但按照替换构造的逻辑，此时依然需要继续匹配剩下的两种可能性。如果使用原子组，把正则写成"\b(?>good|nice|cool)!"，就会在匹配进行到原子组右边并且失败之后，不再回溯原子组内的其它可能性。
原子组可以提高执行效率，不过当然不是所有的分组构造都适合改成原子组。例如我们把前面的例子中的正则"\b(Dan|Daniel|Danny)\b"改成原子组："\b(?>Dan|Daniel|Danny)\b"，它将无法匹配到Daniel或Danny。例如匹配"Daniel"，首先能够匹配成功的部分是\bDan，接着输入下一个字符'i'，因为正则引擎在对分组中的第一种可能性进行尝试，所以用来和'i'匹配的规则是\b，匹配失败，而由于\b已经处于原子组的外面，引擎不再回溯去尝试组内的其它可能性，所以不会匹配到结果。
回顾后发断言（lookbehind）是一个比较麻烦的机制，它的意思是，让正则引擎从当前输入的字符向前回溯，判断前面的部分是否满足条件。此处的问题就在于，正则引擎并不知道应该向前回溯多长，所以很多情况这个用法只用来回溯一个字符。一些语言和编辑器不支持在回顾后发断言里面使用更加复杂的规则，而支持的一般有三种实现方案，一种是从正则表达式中推断出需要向前匹配的长度，因此*和+等规则不允许在其中使用；另一种是对不同的长度进行多次尝试，例如先向前回溯7个字符进行尝试，如果没有匹配，则改为回溯8个字符，直到达到设定的上限（Java 6-13就是这样实现的，因此对回顾后发断言的匹配效率很低）。最后一种则是对回顾后发断言的正则做特殊处理，例如编译为从可以对右向左的输入顺序进行匹配的特殊正则引擎。那么我们在手动推理的时候，可以先将回顾后发断言内的部分改写成一个逆序的等价正则表达式，之后的判断就等于是匹配一个从右向左输入的预测先行断言（lookahead）。这种方法只需要一次回溯即可匹配任意长度，效率较高。关于这种机制在程序中是如何实现的，这里是我找到的一篇相关资料。.NET framework和ECMAScript 2018向后的JavaScript中使用的就是类似的实现方法。
当一个正则表达式只包含零宽度断言时，只会匹配位置，而如果断言的内容也为空，例如正则(?=)，正则对这种情况有特别的规定：它会匹配所有位置。在某些语言中可以利用这个特性，通过匹配位置做字符串分割。
例如有字符串，"abcdefghi"，用数字下标来表示这个字符串里的所有位置，也就是："0a1b2c3d4e5f6g7h8i9"。我们希望对这个字符串做两两分割，也就是把它分割成"ab","cd","ef","gh","i"，这时候如果直接用正则".."，每次只能匹配到两个字符，需要手动转存。而如果能够匹配到每两个字符之间的位置，也就是编号为2、4、6、8的四个位置，使用语言自带的split方法，只要一行就可以完成分割。那么能不能实现呢，在某些语言中是可以的。
我们可以写出这样的正则：(?<=\G..)，这个正则只包含一个零宽度回顾后发断言。来推演一下它的执行过程：首先，上面已经说过，空正则(?<=)会匹配到所有的位置，所以正则引擎输入的不是字符，而是位置：首先输入位置'0'。前面介绍了回顾后发断言的执行方法，我们选择其中的第一种，也就是从正则的内容对回顾的长度进行推断。很明显，正则..需要我们回顾两个字符。而'0'位置的前面没有任何内容，所以回顾后发断言的匹配必然失败。再输入位置'1'，因为前面的内容长度不够两个字符，也匹配失败。下面输入位置'2'，回顾到的内容是"0a1b"，正则\G的匹配方法是：在尚未有匹配时匹配字符串的第一个位置，已有匹配则匹配上一个匹配的结束位置。所以'0'可以和\G匹配，而剩下的"a1b"显然可以和..匹配。所以对位置'2'匹配成功。再继续寻找下一个匹配，此时\G已经变成了上一个匹配的结束位置，因为上一个匹配只包含一个位置，所以就是'2'本身。因此输入'3'时匹配失败，再向后，输入'4'时能成功回顾到"2c3d"。以此类推。
这样在Java中确实可以完成字符串的分割，但是我个人不推荐使用这种仅有零宽度回顾后发断言的正则。原因也很简单，因为不同语言上的实现一致性很差。对于上面的例子，下面列了一个表格展示它在不同语言上的测试结果：
| 语言 | 分割结果 |
|---|---|
| Java | [ab,cd,ef,gh,i]，符合预期 |
| .Net (C#) | [ab,cd,ef,gh,i]，符合预期 |
| PCRE(PHP) | [ab, cde, fgh, i]，分割错误 |
| Perl | [ab, cdefghi]，分割错误 |
| Python | [abcdefghi]，未分割 |
| JavaScript | 报错（JS不支持\G符号） |
| Go等一些其它 | 报错，不支持回顾后发断言 |
可以看到，仅有Java和.Net能够对给出的例子做到正确的分割。PHP给出了一个很接近但是错误的结果，从形式上可以推断出，很可能是因为PHP在实现回顾的时候对位置的判定（边缘位置的包含与否）出了一点问题。而其它语言则每种都存在比较大的问题。另外，这种写法的可读性也比较差，所以虽然在Java或者C#里面用起来方便，但不建议使用。
实际上有些语言对这种需求提供了本地化的语法糖，例如在Python中用正则(..)对上面的例子作分割，就可以起到相同的效果：Python的 re.split 方法会认为整个表达式包裹在一个分组中的正则是一种特殊的形式，分割时会保留用于分割的部分。如 re.split(r'(b)', 'abc') 会得到 ['a', 'b', 'c']。
从上面的例子也可以看出，不同语言对正则其实都有一套各自的实现，有一些可能也提供了特殊的规则和语法糖。虽然在大多数情况下正则都是可以通用的，但是遇到一些冷僻和特别用法的时候，需要仔细测试，不能直接在不同语言之间照搬。
Feel free to comment by raising an issue .