匹配基础
对于正则表达式，有两条普适原则：
- 优先选择最左端的匹配结果；
- 标准的匹配量词（
*、+、?和{min, max}）是优先匹配的。
规则1：优先选择最左端的匹配结果
正则引擎在目标文本的某一位置检测整个正则表达式能匹配的每样文本，若在所有可能的匹配尝试失败之后，则从当前位置的下一位置开始重新开始检查。在尝试过所有的起始位置都不能找到匹配结果的情况下，报告匹配失败，反之则报告匹配成功。
例如，用cat来匹配The dragging belly indicates that your cat is too fat.在非全局匹配模式（/g）下，匹配的结果是indicates中的cat，而非后来的cat。若不了解这条规则，在执行文本替换操作时，会产生令人困惑的结果。
规则2：标准量词是优先匹配的
标准匹配量词都是匹配优先的，它们总是尝试匹配尽可能多的字符，直至匹配上限。以\b\w+s\b为例，\w+完全能够匹配regexes整个单词，但为了表达式的余下部分能够成功匹配，\w+被迫“交还”之前匹配的字符s，该过程被称作回溯，将在下文讲到。
当正则表达式中存在多个标准量词，这条规则总是优先保证前面量词限定的部分不受后面元素的影响。如^.*(\d+)匹配CA 95472 USA时，\d+只能匹配一个数字2。
实际上，对表达式.*而言，存在滥用情况。因为.可以匹配除换行符以外的所有字符，它总是引起过多不必要的回溯。比如用^.*(\d\d)来匹配about 24 characters long，在.*匹配整个字符串之后，必须循环回溯17次，直到它释放字符2和4来满足余下的表达式\d\d匹配成功。
正则引擎
正则引擎主要可以分为两大类：DFA和NFA。两类引擎经过多年发展，产生了多种不必要的变体，为规范这种现状，出台了POSIX标准。POSIX标准规定了引擎应该支持的元字符和特性，以及使用者期望由表达式获得的准确结果。而传统NFA引擎根据该标准衍生出新的引擎类型，POSIX NFA。
在主流的程序中egrep、awk、MySQL使用DFA引擎，而JAVA、grep、.Net、PHP、Python、Ruby等使用传统NFA引擎。
NFA引擎
NFA（非确定型有穷自动机）引擎是以正则表达式为主导的引擎。NFA引擎每次检查表达式的一部分，同时检查当前文本是否匹配表达式的当前部分（这里用部分表示需要匹配的可能是一个字符，或一个子表达式），若匹配，则继续表达式的下一部分，直至所有部分都能匹配，即表达式匹配成功。以to(nite|knight|night)匹配文本... tonight ...为例，引擎从t开始，在目标文本找到t为止，然后检查紧随其后的字符是否能匹配o。当碰到分支结构时，引擎会依次选择分支所列的多种匹配模式，直至匹配成功。
由于传统NFA引擎使用的是顺序结构的多选分支，在安排分支的先后顺序时需格外小心，以免写出无意义的多选结构。如a((ab)*|b*)，因为第一条分支(ab)*永远不会匹配失败，所以第二条分支毫无意义。
NFA引擎匹配的过程中，每一个子表达式都是独立的，子表达式之间不存在内在联系，而只是整个表达式的各个部分。
DFA引擎
DFA（确定型有穷自动机）引擎是以文本为主导的引擎。DFA引擎在扫描字符串时，会记录当前有效的所有匹配可能。具体到... tonight ...例子，引擎每扫描一个字符，都会更新当前的可能匹配序列，直至引擎发现匹配已经完成，则报告匹配成功。若在扫描过程中，引擎发现目标文本中的某个字符会令所有处理中的匹配失效，则返回某个之前保留的完整匹配，若不存在这样的完整匹配，则报告在当前位置无法匹配。在多选分支结构中，DFA引擎总是优先匹配所有分支中匹配最多文本的那条分支。
| 字符串中的位置 | 正则表达式中的位置 |
|---|---|
| ... t¦onight ... | 可能匹配的位置：t¦o(nite|knight|night) |
| ... toni¦ght ... | 可能匹配的位置：to(ni¦te|knight|ni¦ght) |
<small>注：此处用¦作为引擎当前进行匹配的位置，下同</small>。
值得一提，DFA引擎不支持捕获型括号、反向引用、忽略优先量词这些特性。
在使用正则表达式进行检索文本之前，两种引擎都会编译表达式，得到一套内化形式，适应各自的匹配算法。NFA的编译过程通常要更快一些，所需内存也更小。而在NFA匹配过程中，目标文本的某个字符可能会被正则表达式重复检测，在DFA中，目标文本中的字符至多只会被检测一次，所以，在一般情况下，DFA是要比NFA快一些（若只是简单文本的匹配测试，两者速度倒是相差无几）。NFA是表达式主导的，能提供一些DFA不支持的功能，相对而言它具有更开阔的施展空间。
回溯
NFA引擎最重要的性质是，在遇到多个可能成功的可能（包括量词、多选结构）中进行选择时，它会选择其一，并记住其它，当匹配失败时，引擎会回溯到之前记录的位置继续尝试匹配。记录的位置包含两个位置信息：正则表达式中的位置，和未尝试的分支在字符串中的位置。在NFA正则表达式中，这些记录的位置被称为备用状态。
回溯机制有两个要点：
- 如果需要在“进行尝试”和“跳过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“跳过尝试”。
- 距离当前最近存储的选项就是当本地失败强制回溯时返回的，使用的原则是LIFO。
未进行回溯的匹配
用ab?c匹配abc：
- 匹配
a，当前状态为a¦bc和a¦b?c； - 记录备用状态
a¦bc和ab?¦c，当前状态仍同1所示； - 匹配
b，当前状态为ab¦c和ab?¦c； - 匹配
c，匹配完成，丢弃之前保存的备用状态。
进行了回溯的匹配
用ab?c匹配ac：
- 匹配
a，当前状态为a¦c和a¦b?c； - 记录备用状态
a¦c和ab?¦c； - 匹配
b失败，返回之前记录的备用状态； - 匹配
c，匹配完成。
不成功的匹配
用ab?c匹配abd：
- 1-3步匹配过程同例1，但在匹配
c时失败，而返回备用状态记录位置仍失败，由于不存在记录的备用状态，本次匹配失败，故字符串前进，再次尝试正则表达式。当前状态为a¦bc和¦ab?c； - 重新开始的整个匹配失败，字符串继续前进，直至随后的
ab¦c和abc¦都失败，引擎宣告匹配失败。
忽略优先的匹配
用ab??c匹配abc：
- 匹配
a，当前状态为a¦bc和a¦b??c； - 忽略
b??，记录备用状态a¦bc和a¦b??c，当前状态为a¦bc和ab??¦c； -
c无法匹配b，回溯到状态a¦bc和a¦b??c； - 匹配
b，当前状态为ab¦c和ab??¦c； - 匹配
c，匹配完成。
同理，每次测试*或+作用的元素之前，引擎都会保存一个状态，若测试失败，便回退到之前保存的状态开始匹配。这个过程会不断重复，直到所有的尝试完全失败为止。
匹配优先与回溯
有一种常见的错误是，当我们希望用".*"来检索“双引号之间的文本”，而在匹配The name "McDonald's" is said "makudonarudo" in Japanese.这种带有多对双引号的文本时，总是输出如"McDonald's" is said "makudonarudo"这种错误。这也是之前提到关于.*表达式滥用的情况之一。正确的答案是用"[^"]*"代替".*"。尽管".*?"也能达到相同的效果，但是较之[^"]*，.*?存在许多不必要的回溯，效率方面有所欠缺。
但不幸的是，对于... <B>Billions</B> and <B>Zillions</B> of ...，并不能用<B>[^</B>]*</B>匹配。字符组只能代表单个字符，而这里需要的</B>是一组字符，事实是[^</B>]和[^<>B/]并无本质区别。此时，使用忽略优先量词*?就派上了用场。但通常情况下，忽略优先量词并不是排除类的完美替身。若用<B>[^</B>]*?</B>来匹配... <B>Billions and <B>Zillions</B> of ...，我并不认为输出的<B>Billions and <B>Zillions</B>就是用户所期望的。在支持零宽断言的程序中，把表达式改为<B>((?!</?B>).)*</B>，就能准确匹配我们期望的内容。因为断言禁止了表达式主体匹配<B>和</B>之外的内容。
无论是匹配优先，还是忽略优先，都是为全局匹配服务的，只要引擎报告匹配失败，则必然尝试了所有可能的匹配。若只存在一条可能的匹配路径，两种模式就都能找到这个结果，区别只在于找出这个结果的效率而已。若最后可能的匹配结果不唯一，则需要根据实际情况自行选择。
在零宽断言的子表达式结构中，它会保存自己的备用状态，进行必要的回溯。但只要零宽断言的匹配尝试结束，它就不会留下任何备用状态，所有备用状态会在断言成功时被放弃（断言失败时意味着所有可能的匹配路径都已经被尝试，也就无所谓放弃）。在不支持固化分组的流派中，通常可以使用零宽断言来模拟。比如用(?=(regex))\1来模拟(?>regex)，用^(?=(\w+))\1:来模拟(?>\w+):。
占有优先量词与固化分组
如果流派支持固化分组或者占有优先量词，我们可以选择在某个可选元素已经成功匹配的情况下，抛弃此元素的备用状态来阻止回溯。
固化分组
使用固化分组，(?>expression)，的匹配和正常的匹配并无差别，但若匹配进行到次结构之后，那么此结构内的所有备用状态都会被放弃。即，在固化分组匹配结束时，它已经匹配的文本已经固化为一个单元，只能作为整体而保留或放弃。放弃备用状态可能对匹配结果毫无影响，也可能导致匹配失败，或者改变匹配结果。比如\b(?>\S+)ing\b就无法匹配listening a song中的listening。
如果当我们确定保留的备用状态毫无作用时，那么存在可以匹配的文本时，固化分组不会有任何影响，但若不存在能够匹配的文本，放弃这些备用状态会让引擎更快地得出无法匹配的结论。比如用^(?>\w+):来代替^\w+:匹配Subject，可以加快报告匹配失败的速度。
占有优先量词
占有优先量词与匹配优先量词相似，只是占有优先量词从不交还已经匹配的字符。占有优先量词不会创造已经匹配字符的备用状态。
| 匹配优先量词 | 占有优先量词 |
|---|---|
| * | *+ |
| + | ++ |
| ? | ?+ |
| {min, max} | {min, max}+ |
