以下是来自孟岩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 后进先出)。

明白这个道理写出高效的正则表达式非常有帮助。