深入入门正则表达式（java） - 1 - 入门基础
深入入门正则表达式（java） - 2 - 基本实例
深入入门正则表达式（java） - 3 - 正则在java中的使用
深入入门正则表达式（java） - 匹配原理 - 1 - 引擎分类与普适原则
深入入门正则表达式（java） - 匹配原理 - 2 - 回溯
本节第一部分主要介绍正则引擎的分类，由于java属于NFA，所以只重点介绍此类。其余类型简要或不做介绍。
| 引擎类型 | 程序 |
| DFA | awk（大多数版本）、egrep（大多数版本）、flex、lex、MysqL、Procmail |
| 传统NFA | GNU Emacs、Java、grep（大多数版本）、less、more、.NET语言、PCRE library、Perl、PHP（所有三套正则库）、Python、Ruby、sed（大多数版本）、vi |
| POSIX NFA | mawk、Mortice Kern Systems'utilities、GNU Emacs（明确指定时使用） |
| DFA/NFA混合 | GNU awk、GNU grep/egrep、Tcl |
NFA（非确定型有穷自动机）：表达式主导
正则：“to(nite|knight|night)”
目标文本：“tonight”
正则表达式从“t”开始，每次检查一部分（由引擎查看表达式的一部分），同时检查当前文本是否匹配表达式的当前部分。如果是，则继续表达式的下一部分，直到表达式的所有部分都能匹配。
此例中第一个元素是“t”，它会重复尝试，在目标字符串中找到“t”为止，然后检查“o”，过程与此一致。然后是“(nite|knight|night)”部分，表达式会一次尝试，直到宣告匹配成功或失败才会停止。表达式中的控制权在不同元素之间转换，所以作者称其为“表达式主导”
所以正则：“nfa|nfa not”，目标字符串：“nfa not”中，也只是匹配“nfa”而已，而不会完整的匹配。
DFA（确定型有穷自动机）：文本主导
DFA引擎在扫描字符串时，会记录“当前有效”的所有匹配可能。
还是最初的例子，引擎移动到“t”时，它会在当前处理匹配可能中添加一个潜在的可能
接下来扫描的每个字符，都会更新当前的可能匹配序列。继续扫描两个字符之后的情况如上图。分支“knight”被排除。
书中作者称其问文本主导，是因为扫描每个字符的时候都对引擎进行了控制
测试引擎类型
1.如果支持忽略优先量词，那么基本就是传统NFA。DFA不支持忽略优先量词，POSIX NFA中也没有意义。
2.DFA不支持捕获型括号和回溯。在这两种混合类型的引擎中，如果没有使用捕获型括号，就会使用DFA
ps：在RegexBuddy中似乎只有传统NFA，起码做1的验证时结果是这样的，所以DFA和混合型引擎在这就不做验证了，本文也主要针对java，所以这里指着重介绍和java相关内容
两条普适原则（来自《精通正则表达式》v3）：
1.优先匹配最左面（最靠开头）的匹配结果
注意：此原则并没有规定优先匹配结果的长度，而只是规定在所有可能的匹配结果中，优先选择最左边的（可能有）。
作者关于此原则的解释：匹配先从需要查找的字符串的起始位置尝试匹配。这里的“尝试匹配”的意思是：在当前位置测试整个正则表达式能匹配的每个可 能。如果在当前位置测试了所有的可能之后找不到匹配结果，就需要从字符的第二个字符之前的位置开始重新尝试……只有在尝试过所有的起始位置（直到字符串的 最后一个字符）都找不到匹配结果的情况下，才会报告失败。
下面给出一个例子：
目标字符串“This is a cat.”
我想匹配字符“is”，我的正则为“is”
结果如下（图1）：
这里找到了两个结果，根据原则1，最先找到的是“this”中的“is”，而并没有找到“is”这个单词。这也很容易理解。下面我们看看RegexBuddy中debug的过程
这里怎么会有这么多字符，目标字符串实际只有13个字符，那么多出来的那些都是哪来的呢？
我觉得，RegexBuddy是把字符与字符之间的位置也算为一个character。再来看看图1
我之所以把每一个字符都装在表格里，就是让大家看的清楚。这里，每一个竖线（其实是不存在的）也作为一个character，我觉得这样是有道理的，比如零宽断言，它的匹配就是在某一个竖线的位置。我们不妨用“^”测试一下，看看debug的结果。
当正则以“字符串起始位置锚点”开头，引擎就会知道如果能匹配，那么肯定是从字符串开头，所以不需要做更多的尝试。
ps：这和RegexBuddy上面的debug结果似乎是矛盾的。确实是这样，不知道是不是其一个bug，起码v3.5.4是这样的
RegexBuddy暂时是不支持字符组的集合操作的，不知这算功能缺失还是算个bug
2.标准的量词（*，+，?，{m,n}）是匹配优先的
目标字符串：“copyright 2003”
正则：“.*”，那么匹配的结果为全部字符
正则：“.*[0-9]*”，这个时候，由于量词是匹配优先的，所以“.*”会匹配整个字符串，而后面的“[0-9]*”怎什么也匹配不到，这并不影响最终结果，因为“*”表示0个也可以，我们可以添加一组括号来验证这个结果，如下图显示的一样
我们现在将正则改成这样：“.*[0-9]+”，这时候“.*”也会先把字符串全部匹配，之后是“[0-9]+”这个部分，发现它要求至少匹配到一 个数字才行，所以它会强迫“.*”吐出它之前匹配到的内容给自己使用，当“.*”吐出字符“3”之后，“[0-9]+”成功匹配，至此匹配结束，不再进行 其他尝试。
我们来debug看看这一过程：
书中作者总结为：先来先服务。我觉得，也就是说，多个匹配优先量词时，如果目标字符串“不能无法同时满足其需求”，那么写在前面的量词会得到尽量多的字符，后面的量词会像“类似”忽略优先量词一样进行匹配 - 给点就行。
转贴请保留以下链接
本人blog地址
