正则原理浅析
本章节部分内容参考：正则表达式引擎执行原理——从未如此清晰！，这篇文章也有很多可以了解的内容大家也可以去围观一下，我从这篇文章学到很多，总结整理的很好。
前文我们已经讲解过了 DFA 和 NFA，即确定有限自动机和非确定有限自动机，根据前面的铺垫想必各位大佬已经可以将正则引擎与自动机关联起来了，而正则引擎大体也可以分成这样的两大类，即：DFA 正则引擎和 NFA 正则引擎。
DFA引擎
举个例子
我们直接举一个比较简单的例子：
正则表达式是 a[db]c
待匹配的字符串是 abc
此处我们使用‘[]’的原因是第三章
手摸手，带你实现简易版正则引擎我们将会去实现‘[]’
下面我们开始匹配：
网络异常，图片无法展示
|
不知道大家有没有理解，我描述一下对比的过程：
- 第一次是字符 a 和正则表达式 a 比较
- 匹配成功后，是字符 b 同时比较表达式中的 b 和 d
- 再次匹配成功，字符 c 和正则表达式 c 比较
- 匹配成功
这里面我们值得注意的点是，第二次匹配是 b 同时和 b， d 进行比较，所以可能会消耗更多的内存。
特点
我们从上面的例子可以看出一些DFA正则引擎的特点：
文本主导：按照文本顺序执行，所以保证了DFA正则引擎的确定性记录当前所有有效可能：正如前文示例中的第二次匹配一样，同时比较了 b 和 d ，所以需要消耗更大的内存每个字符只检查一次：提高了执行效率，因为没有回溯操作重复匹配的过程不能使用反向引用等功能：因为每个字符只检查一次，只记录当前比较值，所以不能使用反向引用、环视等一些功能
NFA引擎
举个例子
例子还是刚才的例子，方便大家对照：
正则表达式是 a[db]c
待匹配的字符串是 abc
下面我们开始匹配：
网络异常，图片无法展示
|
这里和前面的DFA模式做一下对比，我们会发现区别，NFA引擎在匹配之前会记录字符的位置，然后选择其中一个可能状态进行匹配，如果匹配失败，会进行回溯，进入其他分支进行匹配。
特点
我们从上面的例子可以看出一些NFA正则引擎的特点：
- 文表达式主导：按照表达式的一部分执行，如果不匹配换其他部分继续匹配，直到表达式匹配完成。
- 会记录某个位置：我们看到当执行到
[db]时，NFA引擎会记录字符的位置，然后选择其中一个先匹配。 - 单个字符可能检查多次：我们看到当执行到
[db]时，比较d后发现不匹配，于是NFA引擎换表达式的另一个分支b，同时文本位置回溯，重新匹配字符'b'。这也是NFA引擎是非确定型的原因，同时带来另一个问题效率可能没有DFA引擎高。 - 可实现反向引用等功能：因为具有回溯这一步，所以可以很容易的实现反向引用等一些功能！
对比
网络异常，图片无法展示
|
章节小结
本章结束大家已经获得了所有前置知识🌟，下面我们会利用这些知识去亲手实现一个简单的正则，也是本文的重点，下面我们一起进入下一章的内容吧📖
