简单地讲正则引擎工作原理
莫言 | 2013年07月17日 10:27:36 |
莫言最开始的时候是用的 PHP 的正则去匹配网页内容,从中抓取需要的内容。后来莫言学习了 Perl,Perl 的正则比 PHP 的还强大,自然就花了很多时间去学习,直到最后清楚了正则引擎是怎么工作的,才发现原来是很简单的事。但是现在在网上能搜到的正则教程要么就是教很基础的 正则,要么就像《精通正则表达式》一样讲得很复杂,终于莫言感觉有必要的自己理解的系统地讲一遍,以帮助后来者少走弯路。
正则表达式的概念。
正则表达式起源自对字符串相同“模式”的描述,比如
ab aab aaab
人可以很容易看到上述 3 个字符串之间的相似之处,用语言描述就是多个 a 之间紧跟着 b,但是用计算机语言怎么描述?用正则表达式描述就是 /a+b/。
但 是正则表达式描述的是一些相似字符串的集合,佷可能大于你要求的,比如上面的例子,如果你理解是 1 到 3 个 a,再紧接着 b,用正则表达式描述就是 /a{1,3}b/。明显 /a{1,3}b/ 比 /a+b/ 严格。这两个表达式之间,哪一个更好?没办法简单判断,这取决于你的意图或者应用场景。
任何字符串都可以被 /.*/ 匹配。 /.*/ 表示任意字符重复任意次(这里为简单,假定 . 可以匹配换行符)。但很明显这样子的正则表达式不是我们要的。我们要的正则表达式应该可以达到以下目标:
1. 不能有漏匹配。 2. 多余的匹配应该尽可能少。 3. 匹配速度快。
下面,开始讲正则表达式里的元字符。
大多数字符在正则表达式里表示字面量,比如 /a/ 就匹配 a。如果所有字符在正则表达式里只表示字面量的话,那正则表达式跟所要匹配的字符串之间就无异了。正则表达式的能力主要在元字符上,我们可以简单的分类:
1. 字符和字符集。 2. 分组。 3. 分支。 4. 量词。 5. 锚定和零宽断言。
字符和字符集如单个字符 a,[a-z]等。
分组用来表达如一小段字符串相同的模式,如 (?:abc) 表达由 abc 组成的匹配。/abc/ 跟 /(?:abc)/ 的差别在哪里? (?:abc) 被当成一个整体,可以被量词修饰,如 (?:abc)+ 匹配 abcabcabc... 这样的字符串。
分支如 (?:a|b)。表达如果第一个分支匹配不上,尝试第二个分支,直到有一个分支匹配上或者都不匹配。
量词可以用来修饰“字符和字集集”和分组,用于表达重复的模式。量词分贪婪和非贪婪。
锚定和零宽断言。在 Perl 里锚定有 4 个, ^ $ \b \B 分别表示字符串开始或行开始,字符串结束或行结束,单词间隔,非单词间隔。零宽断言之后讲匹配的过程时再详细讲。
下面,开始讲正则引擎的匹配过程。
我们不搬出 DFA 和 NFA 这些名词,单从能观察到的正则引擎行为来说。引擎拿着正则表达式在目标字符串上匹配,这一个匹配是一个过程,涉及如何调整使之尽量能匹配成功。这个调整的过程可以简单分为两个:一个是回溯,另一个右移。
所谓回溯,就是因为存在量词和分支等情况,第一次匹配错误,调整量词匹配的程度或尝试下一个分支的过程。举例说明:
目标字符串: aaab 正则表达式:/a*ab/
首先 /a*/ 会匹配掉 aaa,接着的 /ab/ 不匹配 b ,这时 /a*/ 会被调整为匹配 aa,接着下的 /ab/ 就匹配成功,整个匹配过程成功。回溯的具体的方法有:
1. 调整贪婪量词少匹配一位。 2. 调整非贪量词多匹配一位。 3. 尝试下一个分支。
那有多个量词和分支出现时,哪一个会先被调整?答案是从不匹配的位置处,从右到左依次调整,比如:
目标字符串: aabb 正则表达式:/a*b*.{4}/
首先 /a*/ 会匹配掉 aa,接着 /b*/ 匹配掉 bb,再接着 /.{4}/ 不匹配,而 /.{4}/ 又不能调整,所以开始调整 /b*/ 和 /a*/, 列表表示如下:
b* b b* "" a* a a* ""
这时 /a*/ 和 /b*/ 都匹配空字符串,这时 /.{4}/ 匹配成功,整个匹配过程成功。
那是否回溯就保证一定能成功匹配呢?答案是否定的。举例子说:
目标字符串: faabb 正则表达式:/a*ab/
正则表达式不可能在字符串位置0 字符 f 匹配成功,这时要下移到位置 1 字符 a 处。这种调整我们可以称之为右移。
总的来说,引擎在目标字符串上从左到右匹配。先尝试回溯,回溯的方法如上所述。回溯失败后右移,直到有一次成功或者完全不成功。
零宽断言的问题。零宽断言只有一个作用,断言成功什么事都没有,断言失败会引起引擎回溯和右移。
另一个是如何用正则表达式做否定匹配。因为引擎倾向于有一次匹配,如果要做否定匹配,就表示着你要否定所有可能的匹配,举例子说,要表示字符串不包含 4个连续的a 或以上,你的正则表达式要这么写:
/^(?:(?!a{4,}).)+$/
做为对比,肯定匹配只要这么写:
/a{4,}/
显然复杂很多。也正因为正则做否定难,Perl 里才提供了 !~ 操作符,要表示字符串不包含 4个连续的a 或以上,只要这么表达:
$str !~ /a{4,}/
以上就是关于正则引擎原理的个人一点经验总结,难免有不严格的地方,欢迎大家指正。
转自:http://www.moyan.tk/article/programming/perl/15.html
相关推荐
网上整理的,学习正则表达式不错的东东~ 也许还有人不知道什么是正则表达式吧~ 但是一旦你弄懂它们,你就能把数小时辛苦而且易错的文本处理工作压缩在几分钟(甚至几秒钟)内完成。 看看吧~
网上看到的一篇介绍Javascript正则表达式的文章,感觉非常不错,整理了一下导出成PDF,有兴趣的看一下。文章属于转载,文档中注明了出处。
正则表达式30分钟入门教程-附常用表达式.chm 本资源转载自网络,供学习研究之用,如用于商业用途,请购买正版,如有侵权,请联系我或CSDN删除。
NULL 博文链接:https://chengtong-java.iteye.com/blog/2272426
正则表达式袖珍版-带详细目录书签.pdf 本资源转载自网络,供学习研究之用,如用于商业用途,请购买正版,如有侵权,请联系我或CSDN删除。
1.正则匹配数字,\为转义字符,d+为匹配一次或多次 ... 您可能感兴趣的文章:Python 正则表达式匹配数字及字符串中的纯数字python字符串中匹配数字的正则表达式python正则表达式去掉数字中的逗号(pyt
半年前我对正则表达式产生了兴趣,在网上查找过不少资料,看过不少的教程,最后在使用一个正则表达式工具RegexBuddy时发现他的教程写的非常好,可以说是我目前见过最好的正则表达式教程。于是一直想把他翻译过来。这...
本资源转载自网络,供学习研究之用,如用于商业用途,请购买正版,如有侵权,请联系我或CSDN删除。
RPA之家转载的RPA全套视频教程,想系统学习RPA的,可以下载该资源学习。在学习的过程中,如果碰到任何问题,也可以在评论区里面交流。
本文是Jan Goyvaerts为RegexBuddy写的教程的译文,版权归原作者所有,欢迎转载。但是为了尊重原作者和译者的劳动,请注明出处!谢谢!
这个一个正则表达式快速入门教程,是转载,如意侵权。上传只是提供大家参考,希望能有所帮助
正则表达式(Regular Expression, abbr. regex) 功能强大,能够用于在一大串字符里找到所需信息。它利用约定俗成的字符结构表达式来发生作用。不幸的是,简单的正则表达式对于一些高级运用,功能远远不够。若要进行...
正则表达式实现资料验证的技术总结来自教师的转载
后文预告:jQuery中的正则表达式分析 2.4 常用正则表达式 在网上找到一篇广为流传的文章《常用正则表达式》,逐一分析,不足地方进行补充和纠正。 代码如下: 常用的数字正则(严格匹配) 正则 含义 ^[1-9]\d*$ 匹配...
regular正则表达式(regular expression).chm 本资源转载自网络,供学习研究之用,如用于商业用途,请购买正版,如有侵权,请联系我或CSDN删除。
模板类实现普通成员函数作为回调函数,deelx正则表达式库的使用示例,交互式控制台调试模块以及磁盘检测模块的封装类。转载请保留版权。
转载的,但的确是很好的正则表达式文档!
Regular_Expressions_正则表达式-英文版-带详细目录书签.pdf 本资源转载自网络,供学习研究之用,如用于商业用途,请购买正版,如有侵权,请联系我或CSDN删除。
文章转载自:http://www.phpchina.com/31423/viewspace_9417.html 匹配中文字符的正则表达式: [\u4e00-\u9fa5]评注:匹配中文还真是个头疼的事,有了这个表达式就好办了匹配双字节字符(包括汉字在内):[^\x00-\xff]...
版权声明:本文为博主博客园原创文章,转载请著名作者和出处。 原文地址:https://www.cnblogs.com/zenglintao/p/12812804.html 对于在职场工作的朋友们如果需要批量提取文本信息就可以使用本方法 import java.io....