360ITO技术社区  > 快讯

订阅新闻

Python下的正则表达式原理和优化笔记

天生叛逆 发布于 6年前 ( comment 0条评论  查看:2140  收藏:0 )
  最近的时间内对正则表达式进行了一点点学习。所选教材是《mastering regular expressions》，也就是所谓的《精通正则表达式》。读过一遍后，顿感正则表达式的强大和精湛之处。其中前三章是对正则表达式的基本规则的介绍和铺垫。七章以后是对在具体语言下的应用。而核心的部分则是四五六这三章节。
        其中第四章是讲了整个正则表达式的精华，即传统引擎NFA的回溯思想。第五章是一些例子下对回溯思想的理解。第六章则是对效率上的研究。根源也是在回溯思想上的引申和研究。
        这篇文章是我结合python官方re模块的文档以及这本书做一个相应的总结。
        其中官方的文档： http://docs.python.org/3.3/library/re.html 
        由于我都是在python上联系和使用的，所以后面的问题基本都是在python上提出来的，所以这本书中的其它正则流派我均不涉及。依书中，python和perl风格差不多，属于传统NFA引擎，也就是以“表达式主导“，采用回溯机制，匹配到即停止（ 顺序敏感，不同于POSIX NFA等采用匹配最左最长的结果）。 
        对于回溯部分，以及谈及匹配的时候，将引擎的位置总是放在字符和字符之间，而不是字符本身。比如^对应的是第一个字符之前的那个”空白“位置。

基础规则的介绍

python中的转义符号干扰

        python中，命令行和脚本等，里面都会对转义符号做处理，此时的字符串会和正则表达式的引擎产生冲突。即在python中字符串'\n'会被认为是换行符号，这样的话传入到re模块中时便不再是‘\n’这字面上的两个符号，而是一个换行符。所以，我们在传入到正则引擎时，必须让引擎单纯的认为是一个'\'和一个'n'，所以需要分别加上转义符，成为'\\\n'，针对这个情况，python中使用raw_input方式，在字符串前加上r，使字符串中的转义符不再特殊处理（即python中不处理，统统丢给正则引擎来处理），那么换行符就是r'\n'

基本字符

1 .        #普通模式下，匹配除换行符外的任意字符。（指定DOTALL标记以匹配所有字符）

量词限定符

1 *        #匹配前面的对象0个或多个。千万不要忽略这里的0的情况。
2 +        #匹配前面的对象1个或多个。这里面的重点是至少有一个。
3 ?        #匹配前面的对象0个或1个。
4 {m}      #匹配前面的对象m次
5 {m,n}    #匹配前面的对象最少m次，最多n次。

锚点符

1 ^        #匹配字符串开头位置，MULTILINE标记下，可以匹配任何\n之后的位置
2 $        #匹配字符串结束位置，MULTILINE标记下，可以匹配任何\n之前的位置

正则引擎内部的转义符号

01 \m    m是数字，所谓的反向引用，即引用前面捕获型括号内的匹配的对象。数字是对应的括号顺序。
02 \A    只匹配字符串开头
03 \b    可以理解一个锚点的符号，此符号匹配的是单词的边界（"单词边界符"）。这其中的word定义为连续的字母，数字和下划线。
04       准确的来说，\b的位置是在\w和\W的交界处，当然还有字符串开始结束和\w之间。
05 \B    和\b对应，本身匹配空字符，但是其位置是在非"边界"情况下，比如r'py\B'可以匹配python，但不能匹配'py,','py.' 等等
06 \d    匹配数字
07 \D    匹配非数字
08 \s    未指定UNICODE和LOCALE标记时，等同于[ \t\n\r\f\v]，注意\t之前是一个空格，表示也匹配空格。
09 \S    与\s相反
10 \w    未指定UNICODE和LOCALE标记时，等同于[a-zA-Z0-9_]
11 \W    和\w相反
12 \Z    只匹配字符串的结尾
其他的一些python支持的转移符号也都有支持，如前面的'\t'

字符集

1  
尤其注意，这个字符集最终 只匹配一个字符（既不是空，也不是一个以上）！所以，前面的一些量词限定符，在这里失去了原有的意义。 
另外，'-'符号放在两个字符之间的时候，表示ASCII字符之间的所有字符，如[0-9]，表示0到9. 
而当放在字符集开头或者结尾，或者被'\'转义时候，则只是表示特指'-'这个符号 
最后，当在开头的地方使用'^',表示排除型字符组.

括号的相关内容

普通型括号 

1 (...)    普通捕获型括号，可以被\number引用。

扩展型括号

1 (?aiLmsx)
2 a        re.A
3 i        re.I    #忽略大小写
4 L        re.L
5 m        re.M
6 s        re.S    #点号匹配包括换行符
7 x        re.X    #可以多行写表达式
01 (?:......)      #非捕获型括号，此括号不记录捕获内容，可节省空间   
02 (?P<name>...)   #此捕获型括号可以使用name来调用，而不必依赖数字。调用时使用(?P=name)
03 (?#...)         #注释型括号，此括号完全被忽略
04 (?=...)         #lookahead assertion 如果后面是括号中的，则匹配成功
05 (?!...)         #negative lookahead assertion    如果后面不是括号中的，则匹配成功
06 (?<=...)        #positive lookbehind assertion    如果前面是括号中的，则匹配成功
07 (?<!...)        #negative lookbehind assertion    如果前面不是括号中的，则匹配成功
08                 #以上<span><b>四种类型断言</b></span>，本身均不匹配内容，只是告知正则引擎是否开始匹配或者停止。
09                 #另外在后两种后项断言中，必须为<b>定长断言</b>。
10 (?(id/name)yes-pattern|no-pattern)
11                 #如有由id或者name指定的组存在的话，将会匹配yes-pattern，否则将会匹配no-pattern，通常情况下no-pattern也可以省略。

匹配优先/忽略优先符号

在量词限定符中，默认的情况都是匹配优先，也就是说，在符合条件的情况下，正则引擎会尽量匹配多的字符（ 贪婪规则）
在这些符号后面加上'?'，则正则引擎会成为忽略优先，此时的正则引擎会优先匹配 尽可能少的情况。

如'??'会优先匹配没有的情况，然后才是1个对象的情况。而{m,n}?则是优先匹配m个对象，而不是占多的n个对象。

相关进阶知识

首先放在最前面，python属于perl风格，属于传统型NFA引擎，与此相对的是POSIX NFA和DFA。所以大部分讨论都针对传统型NFA

传统型NFA中的顺序问题


NFA是基于正则表达式主导的引擎，同时，传统型NFA引擎会在找到符合状态的情况下立即停止。即得到匹配之后就停止引擎。相对来说，POSIX NFA 中不会立刻停止，其会在所有可能匹配的结果中寻求最长结果。这也是有些bug在传统型NFA中不会出现，但是放到后者中，会出现无法结束的情况。
引申一点，NFA学名为”非确定型有穷自动机“，DFA学名为”确定型有穷自动机“
这里的非确定和确定均是指被匹配的目标文本中的字符来说的，在NFA中，每个字符在一次匹配中即使被检测通过，也不能确定他是否真正通过，因为NFA中会出现回溯！甚至不止一两次。图例见后面例子。而在DFA中，由于是目标文本主导，所有对象字符只检测一遍，到文本结束后，过就是过，不过就不过。这也就是”确定“这个词的来历。

回溯/备用状态

备用状态

当出现可选分支时，会将其他的选项存储起来，作为备用状态。当前的匹配失败时，引擎进行回溯，则会回到最近的备用状态。
匹配的情况中，匹配优先与忽略优先某种意义上是一致的，只是顺序上有所区别。当存在多个匹配时，两种方式进行的情况很可能是不同的，但是当不存在匹配时，他们俩的情况是一致的，即必然尝试了所有的可能。

回溯机制两个要点

1 1，在是进行尝试还是跳过尝试时，匹配优先量词和忽略优先量词会作出相应决定。
2 2，匹配失败时，回溯需要返回到上一个备用状态，原则是后进先出（LIFO）
回溯典型举例：
 
这里可以看到，传统型NFA到D点即匹配结束。而在POSIX NFA中，需要找到所有结果，并在这些结果中取最长的结果返回。
当无法出现匹配时，如下图，我们看到POSIX NFA和传统型NFA的匹配路径是一致的。
 


以上的例子引发了一个匹配时的思考，我们尽量避免使用'.*' ,因为其总是可以匹配到最末或者行尾，既然我们只寻求引号之间的数据，往往可以借助排除型数组来完成工作。此例中，使用'[^'']*'这个的作用显而易见，我们只匹配非引号的内容，那么遇到第一个引号即可退出*号控制权。

固化分组思想

 固化分组的思想很重要， 但是python中并不支持。即在使用(?>...)括号中的匹配时产生的备选状态一旦离开括号，便会被引擎抛弃掉。举个典型的例子如： 
1 '\w+:'

这个匹配的情况是这样的，会优先去匹配所有的符合\w的字符，然后假如字符串的末尾没有:，即匹配未找到冒号，此时触发回溯机制，他会迫使前面的\w+释放字符，并且在交还的字符中重新尝试与':'作比对。但是问题出现在\w是不包含冒号的，显然无论如何都不会匹配成功，但是依照回溯机制，就会造成无谓的比对，这是对资源的浪费。所以我们就需要避免这种回溯，对此的方法就是将前面匹配到的内容固化，不令其存储备用状态，那么引擎就会因为没有备用状态可用而结束匹配过程。大大减少回溯的次数。

Python模拟固化过程

虽然python中不支持，但书中提供了利用前向断言来模拟固化过程。

1 (?=(...))\1
这里注意的是断言中的结果是不会保存备用状态的，虽然他本身不匹配内容，但是可以巧妙的添加一个捕获型括号来利用反向引用来达到此效果。对应上面的例子则是： 
1 '(?=(\w+))\1:'

多选结构

多选结构在传统型NFA中， 既不是匹配优先也不是忽略优先。而是按照顺序进行的。这样就更可以很好的利用此特点进行调试。
1 1，在相对的应用中，在结果保证正确的情况下，应该优先的去匹配更可能出现的结果。即将可能性大的分支尽可能放在靠前。
2 2，多选结构的代价。不能滥用多选结构，因为当匹配到多选结构时，缓存会记录下相应数目的备用状态。举例子如：[abcdef]和‘a|b|c|d|e|f’这两个表达式很可能经过稍
0 有用 0 无用
正则表达式 Python

共有0个评论 我要评论»

网友回复/评论仅代表其个人看法，并不表明本社区同意其观点或证实其描述。

请尽量让自己的回复能够对别人有帮助

热门标签

相关文章

周热点

月热点