正则表达式学习（三）- 正则表达式引擎

发表于 | 分类于
  • DFA - 不支持忽略有限量词，不支持捕获型括号和回溯
  • 传统型NFA - 支持忽略优先量词
  • POSIX NFA（传统型NFA增加修改之后使其满足POSIX标准）
  • DFA/NFA混合型

如果执行时间很长或者显示堆栈溢出，就是NFA

普适匹配规则

  1. 优先选择最左端（最靠开头）的匹配结果 - 匹配总是从起始位置开始尝试匹配，如果在当前位置测试了所有结果都不能找到匹配结果，就从字符串的第二个字符之前的位置开始重新尝试，直到找到匹配结果。否则匹配失败。

  2. 标准量词(?,*,+, {min, max})是匹配优先的 - 它们总是希望匹配尽可能多的字符，直到匹配上限为止。除非匹配过多会导致后续部分匹配失败，那么匹配量词会被强迫吐出一部分字符。

    举个例子，我们来看用^.*([0-9][0-9])来匹配“about 24 characters long”的过程。.*一开始会匹配整个字符串，然后第一个[0-9]的匹配要求.*释放一个字符g（最后一个字符），但这并不能匹配[0-9]，所以.*继续释放字符，直到”4”，但是此时第一个[0-9]能匹配，第二个还是不能，所以.*继续释放”2”。现在”24”分别匹配两个[0-9]，所以整个表达式匹配的是”about 24”，捕获括号捕获的值就是”24”。

    • 先来先服务 - 匹配优先的结构只会在被迫的情况下交换字符，其他情形后续部分想要更多就只能怪自己来晚了~

      再举个例子，如果用^.*[0-9]+匹配”Copyright 2017”的结果将会是”7”。在.*吃完全部字符之后，它会被强迫吐出一些字符来满足[0-9]+的匹配，在这里，只要吐出一个”7”就满足了，所以.*不会被迫交出”1”。

NFA引擎 - 表达式主导（非确定性有限自动机）

以to(nite|knight|night)来匹配”···tonight···”为例，正则表达式从t开始检查表达式的一部分，同时 检查当前文本是否匹配表达式的当前部分，如果是，则继续表达式的下一部分，直到全部匹配或匹配失败。在此例中，当正则表达式匹配到分支时，引擎会依次尝试3种可能，直到night匹配成功。在这个匹配过程中，表达式的控制权在不同的元素（子表达式）之间转换，因此称其为“表达式主导”。

在NFA中，每个子表达式是独立的，子表达式之间不存在内在联系，子表达式与正则表达式的控制结构（多选分支、括号、匹配量词）的层级关系控制了整个匹配过程。因此，NFA能让使用者直接操控匹配过程，如果运用得当会带来很大的方便。

回溯

NFA最重要的性质：依次处理各个子表达式或组成元素，遇到需要在多个可能成功的可能中进行选择（量词/多选结构）时，它会选择其一，同时记住其他分支，以备需要。

回溯最重要的两个问题:

  1. 哪个分支应该首先选择？
    • 匹配优先量词 —— 选择“进行尝试”
    • 忽略优先量词 —— 选择“跳过尝试”
  2. 回溯时应该选取哪个状态？
    后进先出，距离当前最近存储的备用状态(saved state)就是此次尝试失败后强制回溯时返回的。

备用状态 —— 保存了 正则表达式中的位置 和 未尝试的分支在字符串中的位置。

匹配优先和忽略优先

正则表达式中的某个元素，无论是匹配优先还是忽略优先，都是为全局服务的，如果全局匹配需要，无论匹配优先还是忽略优先，在遇到“本地匹配失败”时，引擎都会回归到备用状态，尝试尚未走过的路径。无论哪种优先，只要引擎报告匹配失败，它就必然尝试了所有的可能。但是，测试路径的先后顺序，在两种情况下是不同的。

举个例子，假设我们要匹配标签中间的字符，有如下两个字符串：

1
2
3
4
<!-- s1 -->
<B>Tom</B> and <B>Jerry</B>
<!-- s2 -->
<B>Tom and <B> Jerry</B>

考虑以下几种正则表达式的匹配结果：

  • <B>.*</B> - 匹配优先，在s1中会匹配第一个和最后一个
  • <B>.*?</B> - 忽略优先，在s2中也会匹配第一个和最后一个，因此忽略优先量词并不能完美替代排除类
  • <B>((?!<B>).)*?</B> - 解决与之间的会被匹配的问题
  • <B>((?!</?B>))*</B> - 在这里使用排除环视可以禁止正则表达式主体匹配和之外的内容，因此可以不用忽略优先的功能

固化分组

(?>···) 固化分组，使用固化分组的匹配与正常匹配并无差别，但是如果匹配进行到此结构之后，此结构体中的所有备用状态都会被放弃，所以回溯永远也不能选择其中的状态（至少是当此结构完成时，锁定在其中的状态）。

举个例子来说明一下固化分组的作用，先看问题：我们希望将浮点数截取到三位小数，如果第三位是0，则只保留两位小数。 考虑如下替换：

1
$price =~ s/(\.\d\d[1-9]?)\d*/$1/; //perl

当以上替换遇到”.625”时，由于表达式能够匹配成功而做”.625”替换”.625”这样白费功夫的事情，降低了效率。

那么，我们考虑如下改进：

1
$price =~ s/(\.\d\d[1-9]?)\d+/$1/; //perl

我们想到用\d+，预想在\.\d\d[1-9]?“.625”匹配之后\d+无法匹配而导致匹配失败。但是，事情真的会如预料般发生吗？并不会哦，因为在\d+匹配失败后，它的前面的[1-9]?是匹配优先的，虽然它目前选择了匹配”5”，但它还有个备用状态未尝试而且是允许回溯的，因此”5”会被强迫释放给\d+使用，而$1最终只会匹配到”.62”，这并不是我们想要的结果。

这时，我们就可以引入固化分组了！如果我们使用(\.\d\d(?>[1-9]?))\d+来匹配浮点小数时，如果[1-9]不能匹配，正则表达式会返回?留下的备用状态，然后匹配脱离固化分组，继续前进到\d+，当控制权离开备用分组时，没有备用状态需要放弃。如果[1-9]能够匹配，匹配脱离固化分组后，?保存的备用状态因为属于已经结束的固化分组而被抛弃。这时如果用来匹配”.625”，\d+将因为无法匹配而又无法回溯而导致整体匹配失败，这样”.625”就不需要处理了。

固化分组会放弃某些可能的路径，根据具体情况的不用，放弃备用状态会导致不同的结果：

  • 毫无影响
  • 导致匹配失败
  • 改变匹配结果

  • 加快报告匹配失败的速度

    举个例子，使用^\w+:来匹配”Subject”，虽然我们知道这一定会匹配失败，但是对于正则表达式来说，\w+先吃掉了整个字符串，发现不能匹配:，然后从备用状态中依次回溯，要回溯到第一个字符后的位置才会报告失败。即使从一开始我们就知道回溯是没有用的。因此，我们可以显示告诉正则引擎不必检查之前的备用状态了，用^(>?\w+):，这样就可以使得正则引擎更快地得出无法匹配的结论。

占有优先量词 ?+, ++, *+, {m, n}+

占有优先量词与匹配优先量词很相似，只是它们从来不交还已经匹配的字符。所以，它们跟固化分组很相像哦！例如\w++和(?>\w+)的效果就一样。

DFA引擎 - 文本主导（确定性有限自动机）

DFA引擎在扫描时 会记录“当前有效”的所有匹配可能，还是以”tonight”为例，如下图所示：

dfa.png-285kB
这种方式被称为“文本主导”是因为它扫描的字符串中的每个字符都对引擎进行了控制。某个未完成的匹配也许是任意多个可行的匹配的开始，不合适的匹配可能在扫描后继文字时会被去除。如果引擎发现，文本中出现的某个字符会使所有处理中的匹配可能失效，就会返回某个之前保留的完整匹配，如果不存在完整匹配，则报告当前位置无法匹配。

DFA不支持反向引用。

比较

###预编译阶段
DFA引擎需要更多的时间（初始时）和内存，在第一次遇见正则表达式时，DFA引擎在作出任何尝试之前会用比NFA详细得多的办法来分析这个正则表达式，在开始尝试匹配时，它已经内建了一张路线图(map)，这可能需要花费相当的时间和内存。不过当map建立好后，就可以应用到任意长度的文本上了。

现代DFA引擎经常会尝试在匹配需要时再进行预编译，减少时间和内存（lazy evaluation）。

匹配速度

一般情况下，DFA比NFA要快，不过对于简单文本匹配测试一般也看不出差别。DFA的速度与正则表达式无关，而NFA中两者直接相关。NFA因为要对同样的文本尝试不同的子表达式匹配，可能会浪费时间（所以分支顺序很重要）。DFA是deterministic的，目标文本中的每个字符只会检查（最多）一遍，对于一个已经匹配的字符，即使无法知道它是否属于最终匹配，但因为引擎同时记录了所有可能，所以这个字符只需要检测一次。

匹配结果

DFA（和POSIX NFA）返回最左最长匹配文本，而传统型NFA则不一定。不同的引擎的具体实现可能不一样，但目前似乎还没有不一样的。

匹配能力

NFA提供了如下DFA不支持的功能

  • 捕获由括号内的子表示匹配的文本，提供反向引用和后匹配信息
  • 环视(lookaround)，零长度断言(zero-width assertion)
  • 非匹配优先量词，有序的多选结构
  • 占有优先量词和固化分组
© 2015 — 2022 Jane Liao
由 Hexo 强力驱动
|
主题 — NexT.Mist v5.1.4