00-1010，当音符随机组合在一起，可能是噪音。当同样的音符通过作曲家的手，你可以创作出非常优美的音乐。表演者也可以根据乐谱演奏优美的音乐，但他/她可能不知道如何改变音符的组合来使音乐更加优美。作为一个普通用户，如果不知道正则引擎的原理，也可以写一个符合自己需求的正则，但是如果不知道原理，很难写出一个高效无隐患的正则。所以对于经常使用正则或者对深入研究正则感兴趣的人来说，了解正则引擎的匹配原理是很有必要的。00-1010常规发动机可以分为两个不同的类别：DFA和NFA，而NFA基本上可以分为传统的NFA和POSIX NFA。一个DFA确定性有限自动机确定性有限自动机NFA非确定性有限自动机确定性有限自动机传统的NFAPOSIX NFADFA引擎匹配速度快，因为它不需要回溯，但是不支持捕获组。因此，不支持反向引用和$number。目前使用DFA引擎的语言和工具主要有awk、egrep和lex。POSIX NFA主要指符合POSIX标准的NFA发动机。它的主要特点是提供最长最左匹配，即在找到最左最长匹配之前会继续回溯。像DFA一样，非贪婪模式或者忽略优先级量词对POSIX NFA也是没有意义的。大多数语言和工具使用传统的NFA引擎，该引擎有一些DFA不支持的特性：捕获组、反向引用和$number引用；环顾四周。=…)、(?…)、(?=…)、(?))，或者有些文章叫预搜；忽略优化的量词(？*?{m，n}？{m、}？)，或者有些文章叫非贪婪模式；优先量词(？*、{m，n}、{m，}，目前只支持Java和PCRE)，以及固化分组(？…)。发动机的区别不是本文的重点，仅做简单介绍，感兴趣的可以参考相关文献。

1 为什么要了解引擎匹配原理

2 正则表达式引擎

对于字符串“abc”，它包括三个字符和四个位置。

3 预备知识

在正则表达式匹配过程中，如果子表达式匹配的是字符内容，而不是位置，并保存在最终的匹配结果中，则认为子表达式占用了字符；如果子表达式只匹配位置，或者匹配内容没有保存在最终的匹配结果中，那么子表达式被认为是零宽度的。占有字符互斥，零宽度不互斥。即一个字符只能同时匹配一个子表达式，而一个位置可以同时匹配多个宽度为零的子表达式。

3.1 字符串组成

常规匹配过程通常由子表达式(可能由普通字符、元字符或元字符序列组成)控制。从字符串的某个位置开始尝试匹配，子表达式开始尝试匹配的位置从上一个子表达式成功匹配的结束位置开始。例如，正则表达式：(子表达式1)(子表达式2)假设(子表达式1)是宽度为零的表达式。由于其匹配的开始和结束位置相同，例如位置0，因此(子表达式2)尝试从位置0开始匹配。假设(子表达式1)是一个字符被占用的表达式，因为它匹配的开始和结束位置不一样，如果成功匹配从位置0开始，到位置2结束，那么(子表达式2)尝试从位置2开始匹配。至于整个表达式，通常从字符串位置0开始尝试匹配。如果在位置0尝试到字符串的某个位置时，整个表达式未能匹配，引擎将驱动正则向前，整个表达式将从位置1再次尝试匹配，以此类推，直到尝试到最后一个位置后报告匹配成功或失败。

3.2 占有字符和零宽度

3.3 控制权和传动

来源：abc正则表达式：abc匹配过程：首先字符“A”获得控制权，匹配从位置0开始，“A”匹配“A”。匹配成功后，控制权交给字符“B”；由于“A”已被“A”匹配，“B”尝试从位置1匹配，“B”匹配“B”。匹配成功后，控制权交给“C”。用“c”匹配“c”，匹配成功。此时，正则表达式匹配完成，并报告匹配成功。匹配结果为“abc”，起始位置为0，结束位置为3。

4 正则表达式简单匹本过程

来源：ab正则表达式：ab？量词“？”属于匹配优先量词。当它可以匹配或不匹配时，它会选择先尝试匹配。只有当这种选择使得整个表情无法成功匹配时，才会尝试放弃匹配的内容。量词“？”这里。它用来修饰字符“b”，那么“b？”是一个整体。匹配过程：首先字符“a”获得控制权，匹配从位置0开始，“a”匹配“a”。匹配成功后，控制权交给角色“b？”。因为“？”是一个匹配的优先量词，所以我们会先尝试匹配它，也就是“b？”匹配“B”，匹配成功，控制权交给“C”，同时记录一个备选状态；用“c”匹配“c”，匹配成功。该记录的替代状态被丢弃。此时，正则表达式匹配完成，并报告匹配成功。匹配结果为“abc”，起始位置为0，结束位置为3。

4.1 基础匹配过程

来源：ac正则表达式：ab？c匹配过程：首先字符“a”获得控制权，从位置0开始匹配，“a”匹配“a”。匹配成功后，控制权交给角色“b？”。先试着匹配，通过“b？”匹配“C”，同时记录一个备选状态。如果匹配失败，回去找备选状态，“B？”。无视匹配，放弃控制权，交给“C”；用“c”匹配“c”，匹配成功。此时，正则表达式匹配完成，并报告匹配成功。匹配结果为“ac”，起始位置为0，结束位置为2。其中的" b "什么都不匹配。

4.2 含有匹配优先量词的匹配过程——匹配成功（一）

来源：abd正则表达式：ab？c匹配过程：首先字符“a”获得控制权，从位置0开始匹配，“a”匹配“a”。匹配成功后，控制权交给角色“b？”。先试着匹配，通过“b？”匹配“B”，并记录备选状态，匹配成功，控制权交给“C”；用“c”匹配“d”，匹配失败。这时，回去找记录的替代状态，“b？”。忽略匹配，即“b？”如果与“B”不匹配，放弃控制权，交给“C”；用“c”匹配“b”失败。此时，第一次匹配尝试失败。正则化引擎向前驱动正则化，并尝试从位置1开始匹配，“A”匹配“B”。匹配失败，没有替代状态，第二轮匹配尝试失败。继续向前行驶，直到匹配尝试在位置3失败，匹配结束。此时会报告整个表达式匹配失败。

4.3 含有匹配优先量词的匹配过程——匹配成功（二）

来源：ab正则表达式：ab？c量词"？"忽略优先量词。如果可以匹配或者不匹配，会先选择不匹配。只有当这个选择会让整个表达式匹配不成功时，才会尝试匹配。这里的量词"？"是用来修饰字符“b”的，那么“b？"是一个整体。匹配过程：首先字符“a”获得控制权，匹配从位置0开始，“a”匹配“a”。匹配成功，控制权交给角色“b？"；先试着忽略匹配，也就是“b？"不匹配，同时记录一个备选状态，给“C”控制；用“c”匹配“b”，匹配失败。这时，回去找记录的替代状态，“b？"尽量匹配，也就是“b？"要匹配“B”，匹配成功，控制权交给“C”；用“c”匹配“c”，匹配成功。此时，正则表达式匹配完成，并报告匹配成功。匹配结果为“abc”，起始位置为0，结束位置为3。在哪个“b？"匹配字符“b”。

4.4 含有匹配优先量词的匹配过程——匹配失败

源字符串：a12正则表达式：(？=[a-z])[a-z0-9] $元字符" "和" $ "仅匹配位置，并四处查看”(？=[a-z])"只匹配，不占用字符，不保存匹配内容到最终匹配结果，所以都是零宽度。这种规律性的含义是字母和数字匹配，第一个字符是一串字母。匹配过程：首先，元字符“”获得控制权，匹配从位置0开始，其中“”匹配起始位置“位置0”。匹配成功后，控制权交给顺序环视”(？=[a-z])”；"(?=[a-z])”要求其位置右侧必须是字母才能匹配成功，零宽度子表达式不互斥，即同一个位置可以被多个零宽度子表达式匹配，因此也尝试从位置0开始匹配，位置0右侧是字符“a”，符合要求，匹配成功，控制权赋予“[a-z0-9]”；因为”(？=[a-z])“仅匹配，不将匹配的内容保存到最终结果，以及”(？=[a-z])”位于位置0，因此“[a-z0-9]”也尝试从位置0开始匹配。“[a-z0-9]”先尝试匹配“a”，再尝试匹配成功，可以成功匹配下一个“1”和“2”。字符“$”尝试从位置3开始匹配，它匹配结束位置，即“位置3”，匹配成功。此时，正则表达式匹配完成，并报告匹配成功。匹配结果为“a12”，起始位置为0，结束位置为3。其中“”与位置0匹配。=[a-z])“匹配位置0，“[a-z0-9]”匹配字符串“a12”，而“$”匹配位置3。