当前位置:网站首页>正则引擎的几种分类
正则引擎的几种分类
2022-08-09 12:23:00 【xindoo】
正则表达式引擎是正则表达式匹配算法的基础。其有多种不同的实现,但大多数都是基于Henry Spencer的NFA引擎。
正则引擎有两个大分类,DFA和NFA,像Perl、Java、.Net、PHP、Python、Ruby……等大多是工具都是用了NFA引擎。少数广泛被使用的工具如mawk
使用了POSIX NFA引擎(NFA的一种变种)。以高效著称的工具采用了更为高效的DFA引擎。诸如GNU awk,GNU egrep和Tcl之类的一些工具结合了NFA / DFA两种引擎,将两者的优点结合在一起。
基于不同类型引擎的实现的正则表达式,主要有以下几点差异。
- 语法
- 匹配内容
- 零宽断言(环视) 功能
- 捕获功能
- 性能
所有的引擎都会对文本做从左向右的最长匹配,但具体细节取决于使用了何种引擎。
传统的NFA引擎
NFA引擎中使用的非确定有限状态机(Nondeterministic finite automation)是一种由要匹配的表达式驱动的算法。这使得正则表达式像一个小的编程语言一样,可控制引擎在匹配失败时候的行为。
正则引擎从正则表达式其实位置开始,尝试正则表达式与文本的开头进行匹配,如果匹配成功,都前进一个配置,否则文本一直前进到下一个字符,直到匹配。 如果正则表达式需要作出选择(例如使用替代词或可选的量词),它将选择其中之一,并记住其他选择以及在文本中进行选择的位置。如果在之后的处理中,匹配失败,并且还有其他可选的路径,则引擎将回溯做之前作出选择的位置,并尝试其他的选择。如果没有其他可用的替代方案,则匹配失败,引擎前进到下一个字符并从头开始匹配正则表达式。
如果引擎到达了正则表达式的末尾并且所有内容都已匹配,则引擎就会认为匹配成功,并最终放弃所有剩下的替代方法,甚至不再继续探索。这里有很重要的一点:选择不同路径的顺序很重要,它决定是是否能做到最长匹配。
引擎会真正按照正则表达式进行匹配,让你选择达到完全匹配所需的每个步骤。你必须很谨慎地告诉它,首先检查哪种选择才能达到您的期望。你也有机会调整正则表达式,以最大程度地减少回溯并尽早进行匹配。 NFA引擎中使用的方法的一些示例也可以帮助你了解回溯是如何工作的。
POSIX NFA 引擎
POSIX NFA引擎类似于传统NFA引擎,但是当找到成功的匹配项时,它将会记录匹配结果,并且尝试其他可用的替代方法以查找是否可以找到更长的最左边的匹配。 这消除了传统NFA引擎中不能保证最长最左匹配的问题。
以弗里德尔(Friedl)的书中的这个有趣的例子为例:用one(self)?(selfsufficient)?
去匹配oneselfsufficient,传统的NFA将匹配oneself
,而POSIX NFA将匹配oneselfsufficient
,因为(self)?
有两种选择,匹配self或者啥都不匹配,显然最终匹配到的更长。
DFA引擎
DFA引擎中使用的确定性有限自动机(Deterministic finite automaton)是一种由要搜索的文本驱动的算法。 对于搜索到的文本中的每个字符,DFA引擎只会查看一次。 实际上,它相当于并行尝试了NFA中所有可能的替代方法,并将返回其中最长的匹配。
这种方法确实更高效,但也有很多缺点:
- 你无法控制表达式返回匹配项的方式,无论您如何构造表达式,它始终将返回最长最左匹配。
- 没有回溯,因此所有重复的运算符都是贪婪的。 原子分组和所有格修饰符也是无稽之谈。 (更多详细信息,请查阅RegularExpressionsBacktracking)
- 不支持零宽断言(环视)
- 捕获和反向引用也不可能实现
- 正则表达式预编译时间更长,占用更多内存
NFA和DFA混合引擎
由于DFA引擎速度快,但NFA引擎的功能多,因此,混合NFA / DFA引擎试图将二者的优势结合起来。 迄今为止唯一可用的完全混合实现是Tcl中使用的Henry Spencer引擎,它是对原始实现的完全重写。 像GNU egrep和awk只是将两个独立的引擎放一起,然后根据是否使用了NFA特有的功能决定使用哪个引擎。
边栏推荐
- The latest interview summary in 20022 brought by Ali senior engineer is too fragrant
- Adalvo收购其首个品牌产品Onsolis
- How to upload local file trial version in binary mode in ABAP report
- 鹅厂机器狗花式穿越10m梅花桩:前空翻、单桩跳、起身作揖...全程不打一个趔趄...
- Flutter Getting Started and Advanced Tour (4) Text Input Widget TextField
- Nature:猪死亡1小时后,器官再次运转
- Flutter入门进阶之旅(七)GestureDetector
- Say goodbye to the AI era of hand looms
- 【HCIP持续更新】IS-IS协议原理与配置
- Flutter Getting Started and Advanced Tour (8) Button Widget
猜你喜欢
ansible-cmdb friendly display ansible collects host information
AQS Synchronization Component - FutureTask Analysis and Use Cases
8、IDEA提交代码出现: Fetch failed fatal: Could not read from remote repository
Too much volume... Tencent was asked on the side that the memory was full, what would happen?
一甲子,正青春,CCF创建六十周年庆典在苏州举行
Flutter Getting Started and Advanced Tour (3) Text Widgets
链表噩梦之一?5000多字带你弄清它的来龙去脉
AI篮球裁判火了,走步算得特别准,就问哈登慌不慌
保存Simulink仿真模型为图片或者PDF的方法
Scala 高阶(七):集合内容汇总(上篇)
随机推荐
保存Simulink仿真模型为图片或者PDF的方法
JVM内存泄漏和内存溢出的原因
两分钟录音就可秒变语言通!火山语音音色复刻技术如何修炼而成?
ABAP interview questions: how to use the System CALL interface of the ABAP programming language, direct execution ABAP server operating System's shell command?
Introduction to Flutter advanced trip Dialog&Toast (10)
GPT-3组合DALL·E,60秒内搞定游戏设定和原型动画!网友看后:这游戏想玩
随机快排时间复杂度是N平方?
微服务架构的核心关键点
Report: The number of students who want to learn AI has increased by 200%, and there are not enough teachers
Here comes the question: Can I successfully apply for 8G memory on a machine with 4GB physical memory?
Rust 入门指南(使用JSON)
【微服务~远程调用】整合RestTemplate、WebClient、Feign
AQS同步组件-FutureTask解析和用例
WebView注入Js代码实现大图自适应屏幕点击图片预览详情
无需精子卵子子宫体外培育胚胎,Cell论文作者这番话让网友们炸了
在已打开图片上加水印(文字)
自定义VIEW实现应用内消息提醒上下轮播
李开复花上千万投的缝纫机器人,团队出自大疆
Flutter Getting Started and Advanced Tour (8) Button Widget
win10编译x264库(也有生成好的lib文件)