大前端

前端学习之家-大前端

零基础java自学流程-Java语言进阶94

想要系统学习JAVA               推荐JAVA300集
Java300集零基础适合初学者视频教程←点击


给定一个正则表达式和另一个字符串,我们可以达到如下的目的:

1. 给定的字符串是否符合正则表达式的过滤逻辑(称作“匹配”):

2. 可以通过正则表达式,从字符串中获取我们想要的特定部分。

正则表达式的特点是:

1. 非常灵活,逻辑性和功能性;

2. 字符串的复杂控制可以以一种非常简单的方式快速实现。

3.对于刚接触它的人来说很难理解。

由于正则表达式的主要应用对象是文本,它已被应用于各种文本编辑器中,如EditPlus、Microsoft Word、Visual Studio等大型编辑器,可以使用正则表达式来处理文本内容。

常规引擎可以分为两大类:DFA和NFA。这两种引擎都有很长的历史(现在已经超过20年了),两种引擎都有很多变体!引入POSIX是为了防止不必要的变体继续存在。这样,主流的重新引擎可以分为三类:DFA、传统NFA和POSIX NFA。

DFA引擎在线性时间状态下执行,因为它们不需要回溯(因此它们不会对相同的字符进行两次测试)。DFA引擎还确保匹配最长的可能字符串。但是,因为DFA引擎只包含有限数量的状态,它不能用反向引用匹配模式;而且因为它不构造显示扩展,所以它不能捕获子表达式。

传统的NFA引擎运行所谓的“贪婪”匹配回溯算法,以指定测试所有可能的正则表达式扩展并接受第一个匹配的顺序。因为传统的NFA构造正则表达式的特定扩展来成功匹配,所以它可以捕获子表达式匹配和对匹配的反向引用。然而,由于传统的NFA回溯,它可以多次访问完全相同的状态(如果它采用不同的路径到达那里)。因此,在最坏的情况下,它执行起来可能非常慢。因为传统NFA接受它找到的第一个匹配,它也可能导致其他(可能更长的)匹配未被发现。

POSIX NFA引擎与传统NFA引擎相似,只是它们会继续回溯,直到确定找到了最长的可能匹配。因此,POSIX NFA引擎比传统NFA引擎慢;当使用POSIX NFA时,在更改回溯搜索的顺序时,您可能不想支持较短的匹配搜索而不是较长的匹配搜索。

使用DFA引擎主要包括:awk、egrep、flex、lex、MySQL、Procmail等;

使用传统NFA引擎的程序主要有:GNU Emacs、Java、ergp、less、more、。NET语言,PCRE库,Perl, PHP, Python, Ruby, sed, vi;

使用POSIX NFA引擎的程序包括:MAWK,Mortice Kern Systems' Utilities,GNU Emacs(在使用时可以显式指定);

也有混合使用DFA/NFA的引擎:GNU AWk、GNU grep/egrep和Tcl。

举例说明NFA和DFA的区别:

例如string this is yansen 's blog,一个正则表达式as/ya (msen | nsen | nsem)/(不关心表达式如何,这里只是说引擎工作之间的区别)。NFA是这样工作的:它看起来y的字符串,然后是否匹配。如果它是,它仍在继续,发现无论是m .如果不是,它匹配是否N(在这种情况下,MSEN选择分支是消除)。然后我们继续看它后面是否有se,然后我们测试它是否为n,如果它是匹配的,如果不是,我们测试它是否为m,为什么是m?因为NFA的工作原理是在正则表达式上重复测试字符串,所以同一个字符串可能会被多次测试!

然而,DFA并不相同。DFA将在这里从t开始依次查找y,定位到y,并检查表达式是否有a,而表达式恰好有a。然后字符串a后面跟着n, DFA依次测试表达式。在这种情况下,MSEN不符合要求,被淘汰。Nsen和NSEM满足要求,DFA依次检查串。当检测到SEN中的n时,只有NSEN分支匹配,则匹配成功!

如您所见,这两个引擎以完全不同的方式工作,一个(NFA)由表达式控制,另一个(DFA)由文本控制!一般来说,DFA引擎更快!但NFA更面向表达式,更容易操作,所以一般程序员更喜欢NFA引擎!这两种引擎都有各自的优势,但实际引用取决于您的需求和使用的语言。


想要系统学习JAVA               推荐JAVA300集
Java300集零基础适合初学者视频教程←点击

发表评论:

Copyright Your WebSite.Some Rights Reserved.