表达式的匹配原理

Created Friday 02 August 2013

优先选择最左端的匹配结果

起始位置最靠左的匹配总是优先于其他可能的匹配结果。这条规则并没有规定优先的匹配结果的长度，只是规定在所有可能的匹配结果中，优先选择开始位置最左端的。实际上，因为可能有多个匹配结果的起始位置都在最左端，也许我们应该把这条规则中的“某个匹配结果”改为“该匹配结果”。
匹配先从需要查找的字符串的起始位置尝试匹配。
尝试匹配的意思是，在当前位置测试整个正则表达式能匹配的每样文本。如果在当前位置测试了所有的可能之后不能找到匹配结果，就需要从字符串的第二个字符之前的位置开始重新尝试。在找到匹配结果以前必须在所有的位置重复此过程。只有在尝试过所有的起始位置都不能找到匹配结果的情况下，才能报告“匹配失败”。

正则引擎中的零件分为几类：文字字符(literal character)、量词(qualifiers)、字符组(character classes)和括号等等。

标准量词是匹配优先的

标准匹配量词(?、*、+以及{min, max})都是匹配优先的。它们总是希望获得最长的匹配。匹配优先量词之所以得名，是因为它们总是或尝试匹配多余匹配成功下限的字符。
例如\b\w+s\b可以匹配regexes，按照匹配优先则\w+会匹配regexes，但这样s就无法匹配，因此\w+会匹配regexe以达到其他部分能够成功匹配。

NFA：表达式主导

如果表达式不匹配，引擎就会尝试另一种可能，如此继续下去，直到匹配成功或是报告失败。表达式中的控制权在不同的元素之前转换，所以称为表达式主导。
实质上，在表达式主导的匹配过程中，每一个子表达式都是独立的。这不同于反向引用，子表达式之间不存在内在联系，而只是整个正则表达式的各个部分。在子表达式于正则表达式的控制结构（多选分支、括号以及匹配量词）的层级关系（layout）控制了整个匹配过程。

DFA：文本主导

与表达式主导的NFA不同，DFA引擎扫描字符串时，会记录“当前有效”的所有匹配可能。它扫描字符串中的每个字符都对引擎进行了控制。在本例中，某个未完成的匹配也许是任意多个匹配的开始，不合适的匹配能在扫描后继文字时被除去。

回溯的两个要点

1.面对众多选择时哪个分支应当首先选择？

如果需要在“进行尝试”和“跳过尝试”之间选择，对于优先匹配量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“跳过尝试”。

2.回溯进行时，应该选取哪个保存的状态？

距离当前最近存储的选项就是当本地失败强制回溯时返回的。使用的原则是LIFO（last in first out）。