<进阶-1> 正则表达式的匹配原理

正则表达式的正则引擎分为很多种，最常用的引擎类型有perl，tcl, python,.net,ruby,php,java.util.regex等，构建正则表达式的方式决定了某个正则表达式能否匹配一个特定字符串，在何处匹配，以及匹配成功或报告失败的速度。

正则引擎主要可以分为不同的两大类：一种是DFA(文本主导引擎，确定型有穷自动机),另一种是NFA(表达式主导，非确定型有穷自动机)。两者都有很长的历史，使用NFA的工具包括java,.net,ruby,perl,python,vi,grep的多数版本，甚至还有某些版本的egrep和awk。而采用DFA的工具主要有egrep，awk，lex和flex。也有些系统采用了混合引擎，他们会根据任务的不同选择合适的引擎。后面会慢慢引入这两种引擎。

4.1 匹配的基础
在了解不同引擎的差异之前，我们先看看他们的相似之处。
本篇会介绍匹配执行的实际流程。理想的情况是，所有的而知识都能归纳为几条容易记忆的简单规则，使用者不需要了解这些规则包含的原理。很不幸，事实并非如此。只有两条普适的原则，其他都要根据实际的引擎和模式等来综合确定：
1. 优先选择最左端的匹配结果。
2. 标准的匹配量词是匹配优先的。

4.1.1 规则1：优先选择最左端的匹配结果
根据这条规则，起始位置最靠左的匹配结果总是优先于其他可能的匹配结果。这条规则并没有规定优先的匹配结果长度，实际上可能有多个匹配结果起始位置都在最左端。所以后面会讨论优先选择哪种。

这条规则的由来是：匹配（1）先从要查找的字符串的起始位置尝试匹配。在这里，“尝试匹配”的意思是，在当前位置测试整个正则表达式能匹配的每样文本。如果在当前位置测试了所有的可能（因为可能会有多选项或量词）之后不能找到匹配结果，（2）就需要从字符串的第二个字符之前的位置开始重新尝试。在找到匹配结果以前必须在所有的位置重复此过程。只有在尝试过所有的位置都不能找到匹配结果的情况下，才会报告“匹配失败”。说完这些，是不是感觉有点眼熟？编译原理里的词法分析，语法分析是不是也这样？后面再说到回溯，那就更相像了。
所以，如果要用”ORA”来匹配FLOAT,从该字符串左边开始第一轮尝试会失败，ORA不能匹配FLO，第二轮也会失败，ORA不能匹配LOA，第三轮的尝试能够成功，所以引擎会停下来，报告匹配结果。

4.2 引擎的构造
所有的额引擎都是由不同的零部件组合而成的，正则引擎中的零件分为：文字字符，量词，字符组，括号等等，就是前面介绍过的那些。这些零件的组合方式决定了引擎的特性。首先，让我们来看看这些零件：

文字文本，例如a, 我们…
对于非元字符的文字字符，尝试匹配时需要考虑就是”这个字符与当前尝试的字符相同吗？”。如果一个正则表达式只包含纯文本，例如”usa”，那么正则引擎会将其视为一个’u’，接着一个’s’，接着一个’a’。如果进行不区分大小写的匹配时，每个字符就分别匹配其大小写形式。

字符组，点号，Unicode属性及其他
通常情况下,字符组，点号，Unicode属性及其他的匹配是比较简单的:无论字符组的长度是多少，它都只能匹配一个字符。
点号可以很方便地表示复杂的字符组，它几乎能匹配所有字符，所以他的作用也很简单，其他的简便方式还包括”\w”,”\W”和”\d”等。

捕获型括号
用于捕获文本的括号（而不是用于分组的括号）不会影响匹配的过程。

锚点（^, (?<=\d)）
锚点可以分为两大类：简单锚点（^,$,\b…）和复杂锚点（顺序环视，逆序环视等）。

说明：
在讲解DFA和NFA之前，不得不指出，捕获括号，忽略优先量词都只对NFA起作用，对DFA不起作用。这是由他们的工作方式决定的，有些工具是混合两种正则引擎的。

4.2.1 规则2:标准量词是匹配优先的
标准匹配量词(?,+,*以及{min,max})都是匹配优先的。这些匹配总是希望最长的匹配。如果最终结果并非该表达式的所有可能中最长的，原因肯定是匹配字符过多导致匹配失败的。举例，用”\b\w+s\b”来匹配”regexes”,”\w+”完全能匹配整个单词，但如果匹配整个单词，”regexes”的最后一个”s”就不能被正则表达式匹配了，为了完成匹配，”\w+”必须匹配”regexe”,把最后的”s”留出来。后面我们会知道，这不是‘留’出来的，而是‘吐’出来的，也就是回退。

过度的匹配优先
现在让我们回头看看”尽可能多的匹配”的匹配优先量词。比较下”^Subject: ”和
”^Subject: (.*)”，后者多加了一个”(.*)”，但对匹配结果不会有影响，只要前者能匹配，后者一定能匹配。那后者多加的有什么用呢？因为星号是匹配优先的，所以我们可以添加”(.*)”来作为反向引用，获取”^Subject: “之后的内容保存起来。

再来看看”^.*([0-9][0-9])”，它能够匹配一行字符的最后两位数字，如果有的话，将他们保存在变量里（perl里可以通过$1引用）。匹配过程如下：（1）”^”匹配字符串的开始位置，（2）然后”.*”尽可能多的匹配，会匹配到整行文本。（3）然后”[0-9][0-9]”是必须匹配的，在尝试匹配行末的位置时会失败，这样他会通知”.*”:“嗨，你占有的太多了，交出一些字符来吧，这样我可能能匹配”。匹配优先组件首先会尽可能多的匹配字符，但为了整个表达式的匹配，他们通常需要释放一些字符。释放总是一个一个的释放，可能会释放多次。当然，释放也是有底线的，就是释放后剩下的至少是自己的下限，比如加号至少要给自己留一个字符。仍然不能满足要求就会报告此次匹配失败。

先来先服务
前面的例子貌似已经明白了，事实应该还不够明白。看下”^.*[0-9]+”来匹配一行的最后两个数字，期望匹配的不止是最后两位数字，而是整个数。那匹配”copyright 2003.”捕获型括号里匹配到的结果是什么呢？
“^.*”会匹配完整个表达式。然后”[0-9]+”需要至少匹配一个数字，这时候会告诉星号交还一个字些字符。星号不愿意还是要交还最后一个点号。此时[0-9]+还是无法匹配，还要让星号继续交还，这次又交还一个3，[0-9]+此时可以匹配了。这时交还的动作就结束了，[0-9]+的下限已经满足了，星号不会再仁慈的交还字符。因为有个原则：先来先服务。先满足前面的匹配优先字符。

深入细节
交还的动作是如何发生的呢？这其实就是引擎类型决定的：是DFA还是NFA。

4.3 表达式主导和文本主导
DFA和NFA反映了将正则表达式在应用算法上的根本差异。NFA称为“表达式主导(regex-directed)”引擎，DFA称为“文本主导(text-directed)”引擎。

4.3.1 NFA引擎：表达式主导
我们来看用”to(nite|knight|night)”匹配文本”…tonight…”的一种办法。正则表达式从”t”开始，每次检查一部分（由引擎查看表达式的一部分），同时检查”当前文本(current text)”是否匹配表达式的当前部分。如果是，则继续表达式的下一部分，如此继续，直到表达式的所有部分都能匹配，即整个表达式能够匹配成功。
在”to(nite|knight|night)”的例子中，（1）第一个元素是’t’,它将重复尝试，直到在目标字符串中找到’t’为止。（2）之后就检查紧随其后的字符是否能由’o’匹配。（3）如果能就检查下面的元素，在本例中，下面的元素指”(nite|knight|night)”,它的真正含义是”nite”或”knight”或者”night”。引擎会一次尝试这3种可能。表达式主导的引擎必须完全测试，才能得出结论。

NFA引擎在操作上的优点
实质上，在表达式主导的匹配过程中，每一个子表达式都是独立的。这不同于反向引用，子表达式之间不存在内在联系，只是整个正则表达式的各个部分。在子表达式与正则表达式的控制结构(多选分支，括号以及匹配量词)的层级关系控制了整个匹配过程。熟知NFA的匹配原理后，正则表达式的作者可以精确控制匹配过程。

4.3.2 DFA引擎：文本主导
与表达式主导的NFA不同，DFA引擎在扫描字符串时，会记录”当前有效(currently in the works)”的所有匹配可能。具体到tonight的例子，引擎移到”t”时，会在当前处理的匹配可能中添加一个潜在的可能。



有效的可能匹配变为两个(knight被淘汰出局)。扫描到g时，就只剩下一个可能匹配了。当h和t匹配完成后，引擎发现匹配已经完成，报告成功。

这种方式成为”文本主导”，是因为它扫描的字符串中的每个字符都对引擎进行了控制。例如”to(…)?”，括号内的部分并不是必须出现的，但考虑到匹配优先的性质，引擎仍然会尝试匹配括号内的部分。匹配过程中，在尝试括号内的部分时，完整匹配”to”已经保留下来，以因对括号中的内容无法匹配的情况。如果引擎发现，文本中出现的某个字符会令所有处理中的匹配可能失效，就会返回某个之前保留的完整匹配。如果不存在这样的完整匹配，则要报告在当前位置无法匹配。

4.3.3 比较NFA与DFA
根据上面介绍的知识比较NFA和DFA，可能会得出结论：一般情况下，文本主导的DFA引擎要快一些，正则表达式主导的NFA引擎因为需要对同样的文本尝试不同的子表达式匹配，可能会浪费时间（就像上面例子中的3个分支）。

这个结论是对的。在NFA的匹配过程中，目标文本中的某个字符可能会被正则表达式中的不同部分重复检测，甚至有可能被同一部分反复检测。即使某个子表达式能够匹配，为了检查表达式中剩下的部分，找到匹配，它也可能需要再一次应用（甚至可能反复多次）。单独的子表达式可能成功也可能失败，但是，直到抵达正则表达式的末尾之前，我们都无法确知全局匹配成功与否。相反，DFA引擎则是确定型的，目标文本中的每个字符只会检查一遍（最多一遍，可能剩下的不需要检查了）。
正则表达式引擎所使用的两种基本技术，都对应有正式的名字：非确定型有穷自动机(NFA)和确定型有穷自动机（DFA）。

用户需要面对的结果
因为NFA具有表达式主导的特性，引擎的匹配原理就非常重要。通过改变表达式的编写方式，用户可以对表达式进行多方面的控制（java.util.regex就是NFA）。拿tonight的例子来说，如果改变表达式的编写方式，可能会节省很多功夫，比如下面3种方式：
1）“to(ni(ght|te)|knight)”
2）“tonite|toknight|tonight”
3）“to(k?night|nite)”

给出任意文本，这3个表达式都可以捕获相同的结果，但是他们以不同的方式控制引擎。后面我们还会看到这3种写法的优劣。

DFA情况相反，引擎会同时记录所有的匹配选择，因为这3个表达式最终能捕获的文本相同，在写法上的差异并无意义，因为DFA能同时记录他们所有的匹配可能位置，所以选择哪个并无区别。如果要描述DFA，能想到的特征有：
1）匹配很迅速
2）匹配很一致
3）谈论DFA匹配很恼人…

因为NFA是表达式主导的，NFA为创造性思维提供了丰富的施展空间。调校好一个表达式能带来许多收益，调校不好则会带来严重后果。为了彻底弄明白这个问题，我们来看NFA最重要的部分：回溯(back tracking)。

4.4 回溯
NFA引擎最重要的性质是，它会依次处理各个子表达式或组成元素，遇到需要在两个可能成功的可能中进行选择的时候，它会选择其一，同时记住另一个，以备稍后可能的需要。
需要做出选择的情形包括量词（决定是否尝试另一次匹配）和多选结构（决定选择哪个多选分支，留下哪个稍后尝试）。

不论选择哪一种途径，如果他能匹配成功，而且正则表达式的余下部分也成功了，匹配即告完成。如果正则表达式余下部分最终匹配失败，引擎会知道需要回溯到之前作出选择的地方，选择其他的备用分支继续尝试。这样，引擎会尝试表达式的所有可能途径（或者说是匹配完成之前需要的所有途径）。

一个简单的例子
现在来看个完整的例子，用先前的”to(nite|knight|night)”匹配字符串”hot tonic tonight!”。第一个元素”t”从字符串的最左端开始尝试，因为无法匹配文本的’h’，所以从第二个位置开始尝试，同样也失败，然后第三个，这时候’t’能够匹配，接下来的’o’无法匹配空格，至此，本轮尝试也失败。
继续下去，从… tonic…的’t’开始，to匹配成功后，剩下的3个多选分支都成为可能，引擎选取其中之一进行尝试，然后留下其他的选择作为备用。我们假定引擎首先选择的是”nite”，这个表达式被分解为’n’+’i’+’t’+’e’，在正则进行到”toni”匹配后匹配’c’的时候失败，但这种失败并不意味着整个表达式匹配失败，现在就会回到上一次选择的地方，尝试其他多选分支。假设引擎这次选择了”knight”，那么马上就会遭遇失败，因为子表达式的’k’不能匹配文本的’n’，这次选择也失败。现在只剩下最后的选项”night”，仍然会失败。
这时，匹配会回退到正则的最开始，接着从匹配文本的下一个字符开始上面的过程，直到匹配到… tonight!，这一次，多选分支”night”终于匹配到字符串的结尾部分，于是整个匹配成功。

4.4.1 回溯的两个要点
回溯机制的基本原理并不难理解，但是有些细节对实际应用很重要。他们时，面对众多选择时，哪个分支应当首先选择？回溯进行时，应该选取哪个保存的状态？

下面的原则能解答这些问题，原则1：
如果需要在”进行尝试”和“跳过尝试“之间选择，对于匹配优先量词，引擎会优先”进行尝试”，而对于忽略优先量词，会选择“跳过尝试”。

回溯前可能多次保存了备用分支，就像走路时路过了很多岔路口，那回溯的时候使用的是之前保存的哪个分支？原则2：
距离当前最近储存的选项就是当本地失败强制回溯时返回的，使用的原则是LIFO(last in first out，后进先出)。也就是返回到离自己最近的那个备用路径。

在一个多选分支面前要选择哪个呢？原则3：
选择离自己最近的分支，也就是按照列出的顺序，从左到右选择。

4.4.2 备用状态
用NFA正则表达式的术语来说，那些备选路径的位置相当于”备用状态， saved state”。他们用来标记：在需要的时候，匹配可以从这里重新开始尝试。他们保存了两个位置：正则表达式中的位置和未尝试的分支在字符串中的位置（相当于cpu执行指令时要保存下一条指令，这里未尝试的位置就是失败时下一次要匹配的位置）。
总之，NFA是以正则表达式来驱动匹配和回溯的，下面举例再次说明如何保存备用状态和回溯的：

1.未进行回溯的匹配


2.进行了回溯的匹配


3.不成功的匹配




4.忽略优先的匹配


4.4.3 回溯与匹配优先
如果工具使用的是NFA正则表达式主导的回溯引擎，理解正则表达式的回溯原理就成了高效完成任务的关键。前面看到”?”的匹配优先和”??”的忽略优先是如何工作的，现在来看看星号和加号。

星号，加号及其回溯
如果认为”x*”基本等同于”x?x?x?x?x?...”那么情况与之前没有大的差别。每次测试星号作用的元素之前，引擎都会保存一个状态，这样，如果测试失败，还能够从保存的状态开始匹配。这个过程不断重复，直到包含星号的尝试完全失败为止。
所以，如果用”[0-9]+”来匹配”a 1234 num”, 正则的”[0-9]”遇到‘4’之后的空格无法匹配，而此时加号能偶回溯的位置对应了4个保存的状态：


也就是说，在每个位置，”[0-9]”的尝试都代表一种可能。在”[0-9]”遇到空格匹配失败时，引擎回溯到最近保存的状态。

需要注意的是：
第一，回溯机制不但需要重新计算正则表达式和文本的对应位置，也需要维护括号内的子表达式所匹配文本的状态。不但需要同时维护反向引用的状态，也会影响匹配的效率。
第二，由星号（或其他任何匹配优先量词）限定的部分不受后面元素影响，而只是匹配尽可能多的内容。

4.5 关于匹配优先和回溯的更多内容
NFA和DFA都具备许多匹配优先相关的特性（DFA不支持忽略优先，所以只需要关注匹配优先）。
NFA的匹配优先很值得一谈，因为NFA是表达式主导的，所以匹配优先的特性能产生许多神奇的结果。除了忽略优先，NFA还提供了其他许多特性，比如环视，条件判断，反向引用以及固化分组。最重要的是NFA能让使用者直接操控匹配的过程，如果运用得当，这会带来很大的方便，但也可能带来某些性能问题（下一篇会讨论正则的性能）。

4.5.1 匹配优先的问题
前面我们看到，”.*”经常会匹配到一行文本的末尾。这是因为”.*”匹配时只从自身出发，匹配尽可能多的内容，只有在全局匹配需要的情况下才会”*”交还一些字符。
有些时候问题很严重。举例，如果我们要匹配双引号里的文本该怎么做？使用”.*”吗？比如要匹配的文本是：
the name “MCDonald’s ” is said “makudonarudo” in Japanese.
最开始的双引号匹配之后，”.*”能匹配任何字符，所以它会一直匹配到字符串的末尾。为了让最后的双引号能匹配，”.*”不断交还字符，直到满足位置，最后，这个正则匹配到的内容是：
”McDonald’s” is said “makudonarudo”

这显然不是我们期望的结果。那么我们如果能够只取得”McDonald’s”呢？关键的问题在于要认识到，我们希望匹配的不是双引号之间的“任何文本”，而是“除双引号之外的任何文本”。如果用”[^"]*”来取代”.*”（也就是”[^"]*”）就不会出现上面的问题。事实上，可能还有一种出乎意料的问题，因为在大多数流派中”[^"]”能够匹配换行符，而点号则不能。所以更精确的表达是”[^"\n]*”。

这种用法仍然有限制，也就是说当需要排除的不是单个字符时，这样就不能做到，比如提取<B>和</B>之间的字符。下面还会介绍其他更通用的方法。

4.5.2 使用忽略优先量词
上面的问题之所以出现，是因为标准量词是匹配优先的。某些NFA支持忽略优先的量词，*?就是*对应的忽略优先量词。我们用”<B>.*?</B>”就可以提取一对<B>标签里的内容。所以我们知道了，星号之类的匹配优先量词有时候的确方便，但有时候也会带来大麻烦。这时候，忽略优先的量词就能派上用场了。但忽略优先量词也有局限性，比如我们用刚才的”<B>.*?</B>”来匹配：
…<B>Billions and <B>Zillions</B> of suns…
这时候匹配到的结果就是<B>Billions and <B>Zillions</B>，这也不是我们希望的结果。
这个例子也说明了，通常情况下，忽略优先量词并不是排除类的完美替身。

如果支持排除环视，我们就能得到与排除型字符组相当的结果。比如”(?!<B>)”,只有当<B>不在字符串中的当前位置时才能成功。所以，把正则改为：”<B>((?!<B>).)*?</B>”就能准确的匹配我们期望的内容。分开讲解：


现在，环视功能会禁止正则表达式的主体匹配<B>和</B>之外的内容，这也是我们之前试图用忽略优先量词解决的问题，所以现在可以不用忽略优先功能了。这个表达式还有能够改进的地方，后面分析效率的时候还会看到它。

4.5.3 匹配优先和忽略优先都期望获得匹配
再回顾下前面的例子，因为浮点数的显示问题，”1.625”或”3.00”有时候会变成”1.62500000002828”或”3.00000000028822”,为了解决这个问题，我们使用：
$price =~ s/(\.\d\d[1-9]?)\d*/$1/;
来保存$price小数点后面两到三位小数。”\.\d\d”匹配最开始两位数字，而”[1-9]?”用来匹配可能出现的不等于零的第三个小数。
到现在一切正常，但是，如果$price的数据本身就是规范的格式，如$price = 27.625，结果就是我们使用.625替换了.625，相当于白费功夫。结果虽然是我们需要的，但是否存在更有效的办法只进行必要的替换，如果本身复合格式就不替换了呢？我们会想，如果最后的\d*能匹配到数字，那应该就能达到目的，把最后的”\d*”换成”\d+”：
$price =~ s/(\.\d\d[1-9]?)\d+/$1/;
对于1.635000000002828这样的复杂数字，仍然有效。但如果对9.43这样的数字，末尾的”\d+”无法匹配，就不会替换。但这样仍然达不到要求，试想如果数字是27.625，结果会怎样，对了，它会被替换成27.62。这已经不是效率的问题了，结果是错的。
那再改进，把”[1-9]?”改为忽略优先的”[1-9]??”,得到的结果是一样的，忽略优先并不能解决这个问题。

4.5.4 匹配优先，忽略优先和回溯的要旨
无论是匹配优先，还是忽略优先，都是为全局匹配服务的，在这一点上他们没有区别。如果全局匹配需要，无论是匹配优先还是忽略优先，在遇到“本地匹配失败”时，引擎都会回归到备用状态，然后尝试未尝试的路径。只要引擎报告了失败，它就已经尝试了所有的可能。
测试路径的先后顺序，在匹配优先和忽略优先的情况下是不同的，但是只有在测试完所有可能的路径之后，才会最终报告匹配失败。
最后，如果只有一条可能的路径，那两者都能找到结果，只是尝试路径的次序不同，并不会影响匹配的结果，只是需要尝试的次数，这是关于效率的问题。如果存在不只一种可能的结果，那匹配优先会返回最长的结果，而忽略优先会匹配最短的结果。

4.6占有优先量词和固化分组
仍然考虑”.625”的例子，我们知道，如果匹配能够进行到”(\.\d\d[1-9]\d+)”的”(\.\d\d[1-9]”之后，我们就不希望进行回溯，继续向前匹配如果成功就成功，失败就失败，就能满足我们的要求。
那么，如果我们能避免这些备用状态，[1-9]?的匹配就不会交还，就是我们需要的。但是，如果匹配”.5000”，此时[1-9]不能匹配，就确实需要回溯，放弃[1-9]，让之后的\d+能匹配需要删除的数字。听起来，这是两种相反的要求，一会要回溯，一会不要回溯。但我们真正需要的是只有在某个可选元素已经匹配成功的情况下才抛弃此元素的“忽略”状态。也就是说如果”[1-9]”能够匹配成功该，就放弃备用状态，不再回溯，如果匹配失败就允许回溯。

这需要的正是固化分组(?>…)或者占有优先量词[1-9]?+。

4.6.1 用(?>…)实现固化分组
具体来说，使用”(?>…)”的匹配与正常的匹配并无差别，但是如果匹配进行到此结构之后，也就是进行到闭括号之后，那么此结构体中的所有备用状态都会被放弃。也就是说，固化分组匹配结束时，它已经匹配的文本固化为一个单元，只能作为整体而保留或放弃。括号内的子表达式中未尝试过的备用状态都不复存在了，多以回溯永远也不能选择其中的状态。

所以，我们用”(\.\d\d(?>[1-9]?))\d+”。固化分组内，量词能正常工作。完全能符合我们的需要，类似6.135，3.12不会被替换，其余情况正常工作。

4.6.2 固化分组的要旨
前面说过，匹配优先和忽略优先都不会影响需要检测路径的本身，而只会影响检测的顺序。如果不能匹配，无论是按照匹配优先还是忽略优先的顺序，每条路径都会被测试。然而，固化分组与他们截然不同，因为固化分组会放弃某些可能的路径。根据具体情况不同，放弃备用状态可能会导致不同的结果：
1）毫无影响：如果在使用备用状态之前能完成匹配，固化分组就不会影响匹配。
2）导致匹配失败：放弃备用状态可能意味着，本来有可能成功的匹配现在不可能成功了。
3）改变匹配结果：在某些情况下，放弃备用状态可能得到不同的匹配结果。
4）加快报告匹配失败的速度：如果不能找到匹配对象，放弃备用状态可能让正则引擎更快地匹配失败。

我们将在后面看到，固化分组非常有价值，也是最常用的提高效率的技巧。

4.6.3 占有优先量词，?+, *+, ++, {min, max}+
占有优先量词与匹配优先量词很相似，只是他们从来不交还已经匹配的字符。只要已经匹配，也会放弃备用状态。
你也许会想，占有优先量词和固化分组关系非常紧密。像”\w++”与”(?>\w+)”的匹配结果完全相同，只是写起来更加方便。使用占有优先量词，”^(?>\w+):”可以写作”^\w++:”。
请务必区分”(?>M)+”和”(?>M+)”，前者放弃’M’创建的备用状态，但单字符’M’不会创造任何状态，所以这样做没有意义；而后者”M+”创造备用状态，这样做才有意义。”(?>M+)”又等价于”M++”。

4.7 环视中的回溯
初看时并不容易认识到，环视与固化分组和占有优先量词有紧密的联系。环视分为4种：肯定性和否定性的顺序环视和逆序环视，他们只是简单测试，其中表达式能否在当前位置的后面（顺序环视）或前面（逆序环视）。
深入点看，在NFA的世界中包含了备用状态和回溯，环视是怎么实现的？环视结构中的子表达式有自己的世界。它也会保存备用状态，进行必要的回溯。如果整个子表达式能够成功匹配，结果如何呢？肯定型环视会认为自己匹配成功；而否定环视会认为匹配失败。在任何一种情况下，因为关注的只是匹配存在与否，此匹配尝试所在的世界，包括在尝试中创造的所有的备用状态，都会被放弃。如果环视中的子表达式无法匹配，结果如何呢？因为它只应用到自己的世界中，所以回溯时只能选择当前环视结构中的备用状态。
所以我们知道，只要环视结构的匹配尝试结束，他就不会留下任何备用状态。这里用到的就是固化分组和占有优先量词。

作为替换，如果正则流派不支持固化分组，可以使用肯定环视来模拟固化分组。

4.8 DFA,NFA和POSIX
最左最长规则：POSIX标准规定，如果在字符串中的某个位置存在多个可能的匹配，应当返回的是最长的匹配。因为在所有同样从最左边开始的可能的匹配文本中它是最长的，所以叫”最左最长”匹配。

4.9 速度和效率
如果传统型NFA的效率是我们应当关注的问题，那么POSIX NFA的效率更值得关注，因为它需要进行更多的回溯。POSIX NFA需要尝试正则表达式的所有变体。正则表达式写的糟糕的话，匹配的效率就会很低。

4.9.1 DFA的效率
文本主导的DFA巧妙地避免了回溯造成的效率问题。DFA同时记录了所有可能的匹配，这样来提高速度。
DFA引擎需要更多的时间和内存。它第一次遇见正则表达式时，在作出任何尝试之前就会用比NFA详细的多的办法来分析这个正则表达式。开始尝试匹配之前它已经内建了一张路线图。描述“遇到这个字符就该选择这个或那个可能的匹配”，字符串中的每个字符都会按照这张路线图来匹配。
有时候，构造这张路线图可能需要相当的事件和内存，不过只要建立了针对特定正则表达式的路线图，结果就可以应用到任意长度的文本。

4.9.2 NFA和DFA的比较
1.DFA和NFA：在预编译阶段的区别
在使用正则表达式搜索之前，两种引擎都会编译表达式，得到一套内化形式，适应各自的匹配算法。NFA的编译过程通常要快一些，需要的内存也少一些。传统型NFA和POSIX NFA之间并没有实质的差别。

2.DFA与NFA:匹配速度的差别
对于“正常”情况下的简单文本匹配测试，两种引擎的速度差不多。一般来说，DFA的速度与正则表达式无关，而NFA中两者直接相关。(让我突然觉得这有点像oracle中的优化器RBO和CBO模式分别与sql语句的关系。)

传统的NFA在报告无法匹配以前，必须尝试正则表达式的所有变体。这也是为什么后面我们要单独讨论提高NFA表达式的匹配速度技巧。传统型NFA如果能找到一个匹配，肯定会停止匹配。而POSIX NFA必须尝试正则表达式的所有变体，确保获得最长的匹配文本。因此，对POSIX NFA的效率问题更为重要。

DFA不需要做太多的优化，因为它的匹配速度很快。

4.DFA和NFA:匹配结果的差别
DFA返回最左边的最长的匹配文本。传统型NFA可能返回同样的结果，当然也可能返回别的文本。针对某一型具体的引擎，同样的正则表达式，同样的文本，总是得到同样的结果，在这个意义上说，它不是随机的。

5.DFA与NFA:能力的差异
NFA引擎能提供DFA不支持的功能，例如：
1)捕获由括号内的子表达式匹配的文本。
2)环视，以及其他复杂的零长度确认。
3)非匹配优先的量词，以及有序的多选结构。
4)占有优先量词和固化分组。