博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
DFA和NFA的区别
阅读量:6456 次
发布时间:2019-06-23

本文共 1164 字,大约阅读时间需要 3 分钟。

正则表达式引擎分成两类,一类称为DFA(确定性有穷自动机),另一类称为NFA(非确定性有穷自动机)。两类引擎要顺利工作,都必须有一个正则式和一个文本串,一个捏在手里,一个吃下去。DFA捏着文本串去比较正则式,看到一个子正则式,就把可能的匹配串全标注出来,然后再看正则式的下一个部分,根据新的匹配结果更新标注。而NFA是捏着正则式去比文本,吃掉一个字符,就把它跟正则式比较,匹配就记下来:“某年某月某日在某处匹配上了!”,然后接着往下干。一旦不匹配,就把刚吃的这个字符吐出来,一个个的吐,直到回到上一次匹配的地方。

DFA与NFA机制上的不同带来5个影响:
  1. DFA对于文本串里的每一个字符只需扫描一次,比较快,但特性较少;NFA要翻来覆去吃字符、吐字符,速度慢,但是特性丰富,所以反而应用广泛,当今主要的正则表达式引擎,如Perl、Ruby、Python的re模块、Java和.NET的regex库,都是NFA的。
  2. 只有NFA才支持lazy和backreference等特性;
  3. NFA急于邀功请赏,所以最左子正则式优先匹配成功,因此偶尔会错过最佳匹配结果;DFA则是“最长的左子正则式优先匹配成功”。
  4. NFA缺省采用greedy量词(见item 4);
  5. NFA可能会陷入递归调用的陷阱而表现得性能极差。

例如用正则式/perl|perlman/来匹配文本 ‘perlman book’。如果是NFA,则以正则式为导向,手里捏着正则式,眼睛看着文本,一个字符一个字符的吃,吃完 ‘perl’ 以后,跟第一个子正则式/perl/已经匹配上了,于是记录在案,往下再看,吃进一个 ‘m’,这下糟了,跟子式/perl/不匹配了,于是把m吐出来,向上汇报说成功匹配 ‘perl’,不再关心其他,也不尝试后面那个子正则式/perlman/,自然也就看不到那个更好的答案了。

如果是DFA,它是以文本为导向,手里捏着文本,眼睛看着正则式,一口一口的吃。吃到/p/,就在手里的 ‘p’ 上打一个钩,记上一笔,说这个字符已经匹配上了,然后往下吃。当看到 /perl/ 之后,DFA不会停,会尝试再吃一口。这时候,第一个子正则式已经山穷水尽了,没得吃了,于是就甩掉它,去吃第二个子正则式的/m/。这一吃好了,因为又匹配上了,于是接着往下吃。直到把正则式吃完,心满意足往上报告说成功匹配了 ‘perlman’。

由此可知,要让NFA正确工作,应该使用 /perlman|perl/ 模式

 

JS的正则引擎是NFA,NFA是“非确定型有限自动机”的简写。

大部分语言中的正则都是NFA,为啥它这么流行呢?

答:你别看我匹配慢,但是我编译快啊,而且我还有趣哦。

转载于:https://www.cnblogs.com/fpcbk/p/11004913.html

你可能感兴趣的文章
javascript基础
查看>>
查询插入
查看>>
最全的spark基础知识解答
查看>>
NEU OJ 1651 Great number
查看>>
VSCode + PYQT5 + QtDesigner 环境搭建和测试
查看>>
The process could not execute 'sp_MSadd_replcmds'错误解决方案
查看>>
runas /user:administrator cmd 以管理员身份运行CMD
查看>>
配置tomcat允许跨域访问,cors跨域资源共享
查看>>
基本数据结构:链表(list)
查看>>
[LUOGU] P3275 [SCOI2011]糖果
查看>>
[LUOGU] P3469 [POI2008]BLO-Blockade
查看>>
非结构化数据与结构化数据提取---- 案例:使用bs4的爬虫
查看>>
二分图匹配
查看>>
三层架构dal 层基本代码 非查询/查询
查看>>
CSS制作三角形和按钮
查看>>
java 并发多线程显式锁概念简介 什么是显式锁 多线程下篇(一)
查看>>
Python学习心得!
查看>>
支付宝的性能测试
查看>>
iOS 网络请求 NSURLSession 的上传文件方法
查看>>
devDependencies 和 dependencise 的区别
查看>>