Posts tagged 编程

花了近三周的晚上的时间把《精通正则表达式》这本书看完了，说是看完，其实是只看3，4，5，6四章，前面的和后面的几章按照作者的建议觉得自己没有必要去看了。毕竟对于这本书来说，这四章才是重点，在这四章中，作者就已经把正则表达式的语法，正则表达式引擎的工作原理，以及正则表达式的调优讲完。下面是我在看这四章的过程中的一些笔记和总结。

正则表达式的语法

对于正则表达式的语法，相信大多数人都和我一样知道一些基本的语法，但是对于一些不常见的语法还是非常陌生，这边就把这些比较陌生的正则表达式语法记录一下：

• 分组且捕获的文本括号：()，文本被捕获以后可以通过反向引用（\1，\2等等）来引用。
• 分组但是不捕获的文本括号：(?:)，文本被捕获后不能通过反向引用来引用到。
• 忽略优先量词：*?，+?，??，{min,max}?：量词在正常情况下是“匹配优先”的，会尽量匹配更多的内容（Greedy），忽略优先量词则优先匹配尽量少的内容。
• 占有优先量词：?+，*+，++，{m,n}+，与匹配优先量词很相似，只是从来不交还已经匹配的字符，即如果已经匹配到了，就放弃该量词表达式内的所有的回溯可能都抛弃。
• 固化分组：(?>…)，使用固化分组的匹配与正常的匹配无差别，但是如果匹配进行到此结构之后，那么此结构体中所有的备用状态都会被放弃。占有优先量词可以看做是固化分组的特殊情况。
• 条件判断：(?if then|else)：测试if条件表达式，如果测试为真，则执行then部分表达式，如果测试失败，则执行else部分表达式，if条件表达式是特殊的表达式，大概有两种情况，一种是对捕获型括号的特殊引用，比如(?(1))这样，会测试第一组捕获型括号是否参与了匹配；另一种是对环视进行匹配，如果环视能够匹配，则返回true。
• 环视，即零宽断言：(?=…) (?!…) (?<=…) (?<!…)，具体的解释可以参考我之前关于零宽断言的一篇文章：使用零宽断言来匹配不包含连续字符串的行。
• 匹配上一次匹配结束的位置：\G，首先出现在Perl中，在用于迭代匹配的时候比较有用。

正则表达式引擎的工作原理

一般上正则表达式的引擎可以分为两种：NFA和DFA，分别表示非确定性有穷自动机和确定性有穷自动机，这两者背后的理论基础大可不必去了解，只需要知道NFA引擎是在进行匹配的时候是表达式主导的，而DFA引擎在进行匹配的时候是文本主导的，下面具体来拿一个例子来将述下这两者的区别：

NFA引擎工作原理

对于NFA引擎，它会先拿出正则表达式的第一部分，然后看看文本有没有符合这个部分的，如果是，则继续表达式的下一部分进行匹配。

现在假设我们有一个正则表达式是a+b，需要用它去匹配aaaaab这个字符串，它的匹配过程大概如下：

1. 首先找到正则表达式的第一个部分a+
2. 然后看文本是否匹配到了这个表达式，在文本中，前面的5个a是能够匹配a+的，那么继续正则表达式的下面部分
3. 后面是一个b，它能够匹配到文本中5个a后面的b，也匹配成功。
4. 这样正则表达式的所有部分都能够匹配，所以整个表达式就能够匹配成功。

NFA引擎还有一个重要的特性，这个特性对于理解NFA引擎的原理也是非常关键：回溯。具体来就讲，在遇到两个可能成功的分支时，会先尝试一个可能性，然后记住另一个，如果这个可能性失败了，那么就回溯到之前的可能，回溯的一个重要的原则是，如果需要在“进行尝试”和“跳过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”，对于忽略优先量词，引擎会优先选择“跳过尝试”；在进行回溯时，选择回溯的路径是距离最近存储的路径，即基于LIFO原则。

DFA引擎工作原理

对于DFA引擎，DFA引擎会在扫描子字符串时，记录当前有效的所有可能匹配。这个我们就拿书中的tonight的例子来讲。

现在我们拿to(nite|knight|night)来匹配tonight，它的匹配过程大致如下：

1. 引擎看拿到文本中的t，然后找到了表达式中的t可以与之匹配，这样，表达式就可能能够匹配到文本，这样引擎就会添加这样一种潜在的可能。
2. 然后引擎继续按照文本往下移动到了n，这个时候，表达式的多选分支里面只有两个分支可以与之匹配，knight这个分支不能匹配，有效的可能就变成了两个。
3. 继续往下走到文本中的g，这个nite这个分支也不能匹配了，有效的可能变成了一个。
4. 最后当匹配到之后的t时，night这个分支显然能够匹配，这样引擎发现匹配已经成功。

NFA引擎和DFA引擎的各自优缺点：

• 从上面的讲解中可以了解到，NFA引擎因为是正则表达式主导的，可能对文本中的同一个部分进行反复的扫描，DFA则只会对文本进行一次扫描，这样NFA引擎的速度就相对DFA要慢。
• 另外NFA是正则表达式主导的，所以不同的正则表达式对速度的影响比较大，但是DFA因为是文本主导，所以不同的正则表达式对其速度影响不大。
• 从上面一条我们也可以知道，NFA的可玩性就比较大了，相对来说比DFA要灵活很多。其实后面的调优也都是针对NFA引擎的，因为DFA实在是没有什么好调优。

正则表达式调优

正则表达式的调优是在了解了正则表达式的工作原理的基础上进行的，主要是针对NFA引擎，看完正则表达式的调优这一章以后，我自己总结了一条调优的规律：在正则表达式中尽量使用确定的字符：

比较(night|nite|nittt|niasdf)和ni(ght|te|ttt|asdf)这两个正则表达式，因为后面一个正则表达式把各个多选分支中的ni提出来了，这样引擎就能够通过字符扫描的方式快速找到匹配文本中的ni部分，然后再开始匹配后面的多选分支；而前面的那个表达式，引擎在文本的每一个位置都要尝试四个分支，显然速度要慢很多。相比而言，后一个正则表达式比前一个要“确定”，匹配的速度就更快。

针对这一条规律，还可以有很多调优的方式，比如能够加锚点就加锚点之类的，具体的大家可以翻看书的第六章。

总结

应该说这本书觉得是一本值得阅读的书，花时间去看绝对是值得的，特别是当你会一点正则表达式后再去看，收获可能更大。不过这书的翻译看起来有点吃力，读起来不是很顺畅，或许是因为正则表达式本身看起来就有点累，所以看这本书的过程中最好保持头脑清醒，保持注意力集中，这样才能跟上作者的思路。