以下是来自孟岩CSDN博客对两类正则引擎做的解释，我觉得挺好的。
正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式和一个 文本串，一个捏在手里，一个吃下去。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新 的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下 干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。
而.NET就是传统性的NFA正则引擎。
一、匹配基础
规则1：优先选择最左端的匹配结果
简单来说，当你的表达式可以匹配多个结果出来的时候，最左边的结果优先于其他结果。直接一点说就是只得到第一匹配结果。
用[哪里]来匹配：在哪里跌倒，就在哪里躺下。
结果是【在哪里跌倒】而不是【就在哪里躺下】，由于【在哪里跌倒】中的【哪里】出现得更早。这个比喻很烂，来自书上的一个示例：
用[fat|cat|belly|your]来匹配：The dragging belly indicates that you cat is too fat.
结果并不是【fat】而是【belly】，因于NFA加规则1所以他的结果就是这样。
规则2：标准量词是匹配优先的
记住：NFA正则引擎是拿着表达式来匹配文本的。
尝试匹配尽可能多的字符，直接匹配上限为止。
比如：用[\b\w+s\b]来匹配[regexes]，[\w+]是能够完全匹配整个单词，但是如果用[\w+]来匹配整个单词那就无法匹配[s\b]。而为了完成匹配，[\w+]就必须吐出一个[s]并把它保留给[s\b]来匹配。这个示例中告诉我们两个原则。
A：过度的匹配优先原则
说的是[\w+]她会一直吃吃吃吃吃直到整行结束，然而[s\b]是必须匹配的，所以[s\b]会拿着一把枪对着[\w+]说：“兄弟，你吃太多了，交出一些字符出来吧，没准我也可以匹配”，在枪的作用下[\w+]只好乖乖的吐一字符让[s\b]去玩，结果匹配上了，那么整个表达式匹配成功。
B：先来先服务原则
而为什么只需要吐一个呢？原因就是[s\b]最低下限只需要一个字符即可。谁叫[\w+]优先匹配到，那么她就享受到先服务的原则。
二、比较NFA、DFA
直接一点的说DFA比NFA更快。但是NFA为创造性思维提供了丰富的施展空间，假设有三种方式对某一文本进行匹配得到结果一样，那么这三种写法不同的正则，她的有效率也就不一样。当然了，前提必须是你要了解NFA的原理。而NFA最重要的部分：回溯（backtracking）。
三、回溯
其实前面那吐的过程就是一个回溯。就像走迷宫一样当遇到分支的时候你做个记号，然后选择其中一条走，当无法走出去的时候，你再回到那个做记号的位置走另一条。
在众从选择时，哪些分支应当首先选择？回溯过程中又是如何保存状态的？
对于匹配优先量词，引擎会优先“进行尝试”，而对于忽略优先量词进行“跳过尝试”。距离当前最近储存的选项就是当本地失败强制回溯时返回的，使用的原则就是LIFO（last in first out 后进先出）。
明白这个道理写出高效的正则表达式非常有帮助。
近期评论