当前位置:网站首页>正则引擎的几种分类
正则引擎的几种分类
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特有的功能决定使用哪个引擎。
边栏推荐
- 生成上传密钥和密钥库
- 史上最猛“员工”,疯狂吐槽亿万富翁老板小扎:那么有钱,还总穿着同样的衣服!...
- h264协议
- Nature:猪死亡1小时后,器官再次运转
- WebView注入Js代码实现大图自适应屏幕点击图片预览详情
- 用场景定义硬件,英码科技破解“边缘计算”密码
- FFmpeg compiles and installs on win10 (configure libx264)
- 1-hour live broadcast recruitment order: industry big names share dry goods, and enterprise registration opens丨qubit·viewpoint
- ABP中的数据过滤器 (转载非原创)
- Introduction to Flutter advanced trip Dialog&Toast (10)
猜你喜欢
Rust from entry to proficient 04 - data types
两分钟录音就可秒变语言通!火山语音音色复刻技术如何修炼而成?
Scala Advanced (7): Collection Content Summary (Part 1)
自定义VIEW实现应用内消息提醒上下轮播
Flutter入门进阶之旅(六)Layout Widget
注释、关键字、标识符的区别你知道吗?
数据挖掘-05
合并两个有序列表
1-hour live broadcast recruitment order: industry big names share dry goods, and enterprise registration opens丨qubit·viewpoint
MySQL principle and optimization of Group By optimization techniques
随机推荐
WebView注入Js代码实现大图自适应屏幕点击图片预览详情
AI篮球裁判火了,走步算得特别准,就问哈登慌不慌
中科院打脸谷歌:普通电脑追上量子优越性,几小时搞定原本要一万年的计算...
罗振宇折戟创业板/ B站回应HR称用户是Loser/ 腾讯罗技年内合推云游戏掌机...今日更多新鲜事在此...
How to save Simulink simulation model as image or PDF
#Internet of Things essay#Xiaoxiong pie equipment development actual combat
WeChat Mini Program Payment and Refund Overall Process
数据挖掘-05
win10编译x264库(也有生成好的lib文件)
Adalvo acquires its first branded product, Onsolis
WeChat payment development process
位图与位运算
WeChat side: what is consistent hashing, usage scenarios, and what problems does it solve?
听声辨物,这是AI视觉该干的???|ECCV 2022
Use RecyclerView to implement three-level collapsed list
WebView injects Js code to realize large image adaptive screen click image preview details
ABAP interview questions: how to use the System CALL interface of the ABAP programming language, direct execution ABAP server operating System's shell command?
HAproxy: load balancing
造自己的芯,让谷歌买单!谷歌再度开源 180nm 工艺的芯片
MySQL备份与恢复 (转载非原创)