《精通正则表达式》学习笔记（三）

• 《精通正则表达式》学习笔记（一） Ch.1 正则表达式入门 Ch.2 入门示例拓展
• 《精通正则表达式》学习笔记（二） Ch.3 正则表达式的特性和流派概览
• 《精通正则表达式》学习笔记（三） Ch.4 表达式的匹配原理
• 《精通正则表达式》学习笔记（四） Ch.5 正则表达式实用技巧
• 《精通正则表达式》学习笔记（五） Ch.6 打造高效正则表达式
• 《精通正则表达式》学习笔记（六） Ch.10 PHP 相关的正则表达式

正则引擎的分类

正则引擎主要分为 3 类：

1. DFA（符合或不符合 POSIX 标准的都属此类）
2. 传统型 NFA
3. POSIX NFA

• 判断是否传统型 NFA：是否支持忽略优先量词（懒惰）。使用正则表达式 nfa|nfa not 来匹配字符串 nfa not，如果只匹配了 nfa，这就是传统型 NFA。如果整个 nfa not 都能匹配，则此引擎要么是 POSIXNFA，要么是 DFA。

匹配的基础

普适规则：

1. 优先选择最左端（最靠开头）的匹配结果。
2. 标准的匹配量词（*、+、? 和 {m，n}）是匹配优先（greedy，贪婪）的。

• 标准匹配量词的结果“可能”并非所有可能中最长的，但它们总是尝试匹配尽可能多的字符，直到匹配上限为止。如果最终结果并非该表达式的所有可能中最长的，原因肯定是匹配字符过多导致匹配失败。
• 「.*」永远不会失败，因为“不匹配任何字符”也是「.*」的可能结果之一。
• 「(.*).*」结果没有变化。开头的「.*」（括号中的）会霸占整个标题的文本，而不给第二个「.*」留下任何字符。而第二个「.*」的匹配失败并不要紧，因为「.*」不匹配任何字符也能成功。如果我们给第二个「.*」也加上括号，$2将会是空白。
• 表达式中的某些部分可能“强迫”之前匹配优先的部分“释放”（或者说“交还（unmatch）”） 某些字符。例如：「^.*([0-9][0-9])」将“强迫”「.*」交还两个数字使得匹配成功。
• 多个贪婪贪婪量词之间遵循「先来先服务」原则。例如：「^.*([0-9]+)」试图匹配 copyright 2003 时，「([0-9]+)」只能匹配到「3」而非「2003」，在该例子中，首先服务「^.*」，使其满足最贪婪的要求，然后才服务「([0-9]+)」。

表达式主导与文本主导

• DFA：确定型有穷自动机
• NFA：非确定型有穷自动机

NFA 以表达式本身为依据，进行匹配尝试，DFA 以匹配文本为依据，观察子表达式是否匹配成功。

• NFA 引擎：表达式主导（regex-directed）——表达式中的控制权在不同的元素之间转换。正则表达式每次检查一部分（由引擎查看表达式的一部分），同时检查“当前文本（current text）”是否匹配表达式的当前部分。如果是，则继续表达式的下一部分，如此继续，直到表达式的所有部分都能匹配，即整个表达式能够匹配成功。
• DFA 引擎：文本主导（text-directed）——在扫描字符串时，会记录“当前有效（currently in the works）”的所有匹配可能。
• DFA引擎在扫描字符串时，会记录“当前有效（currently in the works）”的所有匹配可能。
• DFA 扫描的字符串中的每个字符都对引擎进行了控制。在本例中，某个未完成的匹配也许是任意多个（只要可行）匹配的开始。不合适的匹配可能在扫描后继文字时会被去除。文本中出现的某个字符会令所有处理中的匹配可能失效，就会返回某个之前保留的完整匹配。如果不存在这样的完整匹配，则要报告在当前位置无法匹配。

NFA 和 DFA 比较

• 一般情况下，文本主导的 DFA 引擎要快一些。正则表达式主导的 NFA 引擎，因为需要对同样的文本尝试不同的子表达式匹配，可能会浪费时间。
• 在 NFA 的匹配过程中，目标文本中的某个字符可能会被正则表达式中的不同部分重复检测（甚至有可能被同一部分反复检测）。
• DFA 引擎则是确定型的（deterministic）——目标文本中的每个字符只会检查（最多）一遍。
• DFA 引擎会同时记录所有的匹配选择，所以不同表达式最终能够捕获的文本相同，在写法上的差异并无意义，选择哪一个表达式并无区别。
• DFA 匹配很迅速、一致。

回溯

• 如果正则表达式中余下的部分最终匹配失败，引擎会知道需要回溯到之前做出选择的地方，选择其他的备用分支继续尝试。

• 回溯仅发生于 NFA 引擎执行匹配时，这是由 NFA 的特性导致——NFA 引擎是表达式主导，在每次扫描文本后都检测是否满足量词和多选结构，如果不满足且无待扫描文本，则会一次又一次「撤销」扫描，取出最近一次满足匹配的结果。这个回滚动作就是「回溯」。

• 回溯的机制类似于面包屑 / 压栈（LIFO，Last In First Out，后进先出），也可以说面包屑即为压栈存储的一个个备用状态。

  举个栗子，用「[0-9+]」来匹配 a 1234 num 的过程中：

  

  锚点从上到下形如面包屑，在匹配失败时回到上一级继续尝试匹配。 四个锚点的的状态都会作为保留状态记录下来，依次查看最长的匹配文本，并在匹配失败时一个接一个回溯回来。

• 回溯机制不但需要重新计算正则表达式和文本的对应位置，也需要维护括号内的子表达式所匹配文本的状态。

• 在匹配过程中，每次回溯都把当前状态中正则表达式的对应位置指向括号之前。

• 回溯对括号的这种处理，不但需要同时维护 $1 的状态，也会影响匹配的效率。

• 由星号（或其他任何匹配优先量词）限定的部分不受后面元素影响，而只是匹配尽可能多的内容。

• 忽略优先的匹配（懒惰）的原因在于，其首先考虑尝试忽略，如「b??」中的懒惰量词「??」会首先匹配零个文本 b（注意并不是不匹配）

• 简单说，懒惰量词就是匹配其能力的下限，比如「b{3,8}?」在匹配 bbbbbbb 时只匹配 3 个 b；「b+?」在匹配 bbbbbbb 时只匹配 1 个 b。

关于贪婪、懒惰和回溯的要点

• 由于「*」是贪婪的量词，所以在使用时还需谨慎，不能过分依赖。举个栗子： 文本：The name "McDonald's" is said "makudonarudo" in Japanese.

  1. RegEx：".*"
     结果："McDonald's" is said "makudonarudo" 释义：贪婪量词尽可能多地进行匹配

  2. RegEx："[^"]*"
     结果："McDonald's" 释义：「[^"]」尽可能多地匹配非"的字符，即"前的字母

• 善用懒惰量词解决成对标签的问题。举个栗子： 文本：...<B>Billions</B> and <B>Zillions</B> of suns.... 期望：<B>Billions</B>

  1. RegEx：<B>[^</B>]</B>
     结果：匹配失败 释义：[]是字符范围元字符，无法表达非</B>的含义，可以使用环视功能进行匹配

  2. RegEx：<B>.*?</B>
     结果：<B>Billions</B> 释义：「*?」为懒惰量词，可以尽可能少地匹配文本

• 懒惰量词有时在处理成对符号时并不完美。举个栗子： 文本：...<B>Billions and <B>Zillions</B> of suns.... 期望：<B>Zillions</B>

  1. RegEx：<B>.*?</B>
     结果：<B>Billions and <B>Zillions</B> 释义：「.*?」会匹配左边的<B>标签，这是不满足期望的，可以使用排除环视功能进行匹配

  2. RegEx：
     结果：<B>Billions</B>

  3. RegEx：
     结果：<B>Billions</B>

• 有一些问题是贪婪和懒惰都无法解决的问题，举个例子： 文本：1.62500000002828，9.43，27.625 期望：替换过长小数为三位小数 1.625，9.43，27.625

  1. RegEx：$prive =~ s/(\.\d\d[1-9]?)\d*/$1/;
     结果：$1 = 1.625 释义：对于匹配三位小数，此表达式效率还不够高，部分匹配过程存在浪费

  2. RegEx：$prive =~ s/(\.\d\d[1-9]?)\d+/$1/;
     结果：$1 = 1.625（正常替换），$1 = 9.43 （不替换），$1 = 27.62 释义：「\.\d\d」匹配了 27.62，「\d+」匹配了 5，「[1-9]?」为可选分支，优先级别比「\d+」低，不进行任何匹配，于是最终导致 27.625 被替换为 27.62

• 在只有一条可能的匹配路径时，使用贪婪和懒惰量词的正则表达式对结果无影响,只是因其尝试路径的次序不同，引擎尝试匹配的次数不同，即效率不同。

固化分组

• 在固化分组「(?>……)」匹配结束时，它已经匹配的文本已经固化为一个单元，只能作为整体而保留或放弃。回溯永远也不能选择其中的状态。举个例子：「(\.\d\d(?>[1-9]?))\d+」中固化分组「(?>[1-9]?)」使得 .625 末尾的 5 会遭遇 「[1-9]?」的固化匹配，然后再「\d+」需要回溯时匹配失败，从而导致 .625 整个文本匹配失败，从而不被处理，提升执行效率。
• 贪婪和懒惰影响检测顺序，固化分组影响备用状态（面包屑）的取舍。
• [(?>.*?)」是一个相当复杂的正则表达式，它永远无法匹配任何字符。「.*?」是「.*」的忽略优先（懒惰）表示，它限定的是一个点号，所以首选的分支是忽略点号，把匹配点号的状态保留下来备用。但该备用状态马上又会因为匹配退出了固化分组而被放弃。
• 「^\w+:」无法匹配 Subject，但正则表达式必须从末尾依次向前尝试匹配各种备用状态后才能得出匹配失败的结论。使用固化分组正则表达式「^(?>\w+):」将在尝试「:」匹配失败后直接抛弃固化分组内容「\w+」，即只需尝试 1 次匹配便得出匹配失败结论。大大提高匹配效率。

环视

• 环视结构的匹配尝试结束，它就不会留下任何备用状态。
• 在肯定环视中使用捕获括号，就能模拟实现固化分组和占有优先量词。「(?>regex)」可以用「(?=(regex))\1」来模拟。举个栗子：
  • 「(?>\w+):」为固化分组表达式
  • 「^(?=(\w+))\1:」为环视表达式，环视中的「\w+」是贪婪匹配的，匹配整个单词。当环视结束之后，备用状态都会被放弃(和固化分组一样)。但与固化分组不同：虽然此时捕获了单词，但它不是全局匹配的一部分。「\1」的使用是为了把匹配从这个单词结束的位置进行下去。

多选结构

• 对 NFA 来说，多选结构既不是匹配优先的，也不是忽略优先的，而是按顺序排列的。
• 对 DFA 来说，多选结构匹配所有多选分支中能匹配最多文本的那个。
• 如果多选分支是按顺序排列的。，而能够匹配同样文本的多选分支又不只一个，就要小心安排多选分支的先后顺序。

文本：Jan 31 is Dad's birthday 期望：Jan 31

1. RegEx：Jan (0?[1-9]|[12][0-9]|3[01]) 结果：Jan 3 释义：「0?」不会匹配成功，但后续的「[0-9]」会匹配 3，此时完成所有匹配需求，故匹配成功。

2. RegEx：Jan ([12][0-9]|3[01]|0?[1-9]) RegEx：Jan (31|[123]0|[012?[1-9]]) 结果：Jan 31 释义：上述两个 RegeEx 的多选结构顺序保证了匹配的内容与期望相符

3. RegEx：Jan (0[1-9]|[12][0-9]?|3[01]?|[4-9]) 结果：Jan 31 释义：上述多选结构不受内部多选分支的顺序影响，均可匹配成功

NFA、DFA 和 POSIX

NFA 和 DFA 引擎理应匹配相同文本，提供相同功能。但在实际中，因为人们需要更强的功能，更具表达能力的正则表达式，它们各自的表达式语意（解析方式）发生了变化。

最左最长规则

• 如果传动装置在文本的某个特定位置启动 DFA 引擎，而在此位置又有一个或多个匹配的可能，DFA 就会选择这些可能中最长的。
• POSIX 标准规定，如果在字符串的某个位置存在多个可能的匹配，应当返回的是最长的匹配。

速度和效率

• POSIX NFA 需要进行更多的回溯，尝试正则表达式的所有变体。所以表达式的差异会极大影响其匹配的效率。
• DFA 引擎用更多时间和空间来换取匹配效率。