转载：正则表达式

简单地讲正则引擎工作原理

莫言	2013年07月17日 10:27:36

莫言最开始的时候是用的 PHP 的正则去匹配网页内容，从中抓取需要的内容。后来莫言学习了 Perl，Perl 的正则比 PHP 的还强大，自然就花了很多时间去学习，直到最后清楚了正则引擎是怎么工作的，才发现原来是很简单的事。但是现在在网上能搜到的正则教程要么就是教很基础的 正则，要么就像《精通正则表达式》一样讲得很复杂，终于莫言感觉有必要的自己理解的系统地讲一遍，以帮助后来者少走弯路。

正则表达式的概念。
正则表达式起源自对字符串相同“模式”的描述，比如

ab
aab
aaab

人可以很容易看到上述 3 个字符串之间的相似之处，用语言描述就是多个 a 之间紧跟着 b，但是用计算机语言怎么描述？用正则表达式描述就是 /a+b/。

但 是正则表达式描述的是一些相似字符串的集合，佷可能大于你要求的，比如上面的例子，如果你理解是 1 到 3 个 a，再紧接着 b，用正则表达式描述就是 /a{1,3}b/。明显 /a{1,3}b/ 比 /a+b/ 严格。这两个表达式之间，哪一个更好？没办法简单判断，这取决于你的意图或者应用场景。

任何字符串都可以被 /.*/ 匹配。 /.*/ 表示任意字符重复任意次（这里为简单，假定 . 可以匹配换行符）。但很明显这样子的正则表达式不是我们要的。我们要的正则表达式应该可以达到以下目标：

1. 不能有漏匹配。
2. 多余的匹配应该尽可能少。
3. 匹配速度快。

下面，开始讲正则表达式里的元字符。

大多数字符在正则表达式里表示字面量，比如 /a/ 就匹配 a。如果所有字符在正则表达式里只表示字面量的话，那正则表达式跟所要匹配的字符串之间就无异了。正则表达式的能力主要在元字符上，我们可以简单的分类：

1. 字符和字符集。
2. 分组。
3. 分支。
4. 量词。
5. 锚定和零宽断言。

字符和字符集如单个字符 a，[a-z]等。
分组用来表达如一小段字符串相同的模式，如 (?:abc) 表达由 abc 组成的匹配。/abc/ 跟 /(?:abc)/ 的差别在哪里？ (?:abc) 被当成一个整体，可以被量词修饰，如 (?:abc)+ 匹配 abcabcabc... 这样的字符串。
分支如 (?:a|b)。表达如果第一个分支匹配不上，尝试第二个分支，直到有一个分支匹配上或者都不匹配。
量词可以用来修饰“字符和字集集”和分组，用于表达重复的模式。量词分贪婪和非贪婪。
锚定和零宽断言。在 Perl 里锚定有 4 个， ^ $ \b \B 分别表示字符串开始或行开始，字符串结束或行结束，单词间隔，非单词间隔。零宽断言之后讲匹配的过程时再详细讲。

下面，开始讲正则引擎的匹配过程。

我们不搬出 DFA 和 NFA 这些名词，单从能观察到的正则引擎行为来说。引擎拿着正则表达式在目标字符串上匹配，这一个匹配是一个过程，涉及如何调整使之尽量能匹配成功。这个调整的过程可以简单分为两个：一个是回溯，另一个右移。

所谓回溯，就是因为存在量词和分支等情况，第一次匹配错误，调整量词匹配的程度或尝试下一个分支的过程。举例说明：

目标字符串： aaab
正则表达式：/a*ab/

首先 /a*/ 会匹配掉 aaa，接着的 /ab/ 不匹配 b ，这时 /a*/ 会被调整为匹配 aa，接着下的 /ab/ 就匹配成功，整个匹配过程成功。回溯的具体的方法有：

1. 调整贪婪量词少匹配一位。
2. 调整非贪量词多匹配一位。
3. 尝试下一个分支。

那有多个量词和分支出现时，哪一个会先被调整？答案是从不匹配的位置处，从右到左依次调整，比如：

目标字符串： aabb
正则表达式：/a*b*.{4}/

首先 /a*/ 会匹配掉 aa，接着 /b*/ 匹配掉 bb，再接着 /.{4}/ 不匹配，而 /.{4}/ 又不能调整，所以开始调整 /b*/ 和 /a*/， 列表表示如下：

b*    b
b*    ""
a*    a
a*    ""

这时 /a*/ 和 /b*/ 都匹配空字符串，这时 /.{4}/ 匹配成功，整个匹配过程成功。

那是否回溯就保证一定能成功匹配呢？答案是否定的。举例子说：

目标字符串： faabb
正则表达式：/a*ab/

正则表达式不可能在字符串位置0 字符 f 匹配成功，这时要下移到位置 1 字符 a 处。这种调整我们可以称之为右移。

总的来说，引擎在目标字符串上从左到右匹配。先尝试回溯，回溯的方法如上所述。回溯失败后右移，直到有一次成功或者完全不成功。

零宽断言的问题。零宽断言只有一个作用，断言成功什么事都没有，断言失败会引起引擎回溯和右移。

另一个是如何用正则表达式做否定匹配。因为引擎倾向于有一次匹配，如果要做否定匹配，就表示着你要否定所有可能的匹配，举例子说，要表示字符串不包含 4个连续的a 或以上，你的正则表达式要这么写：

/^(?:(?!a{4,}).)+$/

做为对比，肯定匹配只要这么写：

/a{4,}/

显然复杂很多。也正因为正则做否定难，Perl 里才提供了 !~ 操作符，要表示字符串不包含 4个连续的a 或以上，只要这么表达：

$str !~ /a{4,}/

以上就是关于正则引擎原理的个人一点经验总结，难免有不严格的地方，欢迎大家指正。

 

转自：http://www.moyan.tk/article/programming/perl/15.html