Regexp Greedy

RegExp Greedy Mode

正则表达式中的量词符号默认会尽可能多的匹配字符,在某些情形下这正是你想要的,但是在另一些情形下却不是,本文将会介绍哪些量词存在贪心模式,以及如何根据具体的情况开关贪心模式

具有贪心模式的量词以及关闭贪心的方法

正则表达式中的量词: *, +, {m, n}, ? 都具贪心模式,要关闭量词的贪心模式只需紧跟在量词后面添加 ?,关闭贪心意味着匹配量词的最后少次数,下面将会各个量词的贪心和非贪心模式下的匹配一一进行举例说明:

    aaab            # 待匹配的字符串

    a*              # 匹配结果为aaa

    a*?             # 匹配结果为空,因为量词*的最少匹配次数为零次

    a+              # 匹配结果为aaa

    a+?             # 匹配结果为a,因为量词+的最少匹配次数为一次

    a{2,3}          # 匹配结果为aaa

    a{2,3}?         # 匹配结果为aa,因为量词{2,3}的最少匹配次数为两次

    a?              # 匹配结果为a

    a??             # 匹配结果为空,因为量词?的最少匹配次数为零次

使用场景

下面是要用于匹配的字符串,为了待会儿讲解上的方便,我将下面<p></p>都紧跟一个数字标注了起来

    <p>1

        This is a paragarph

    4</p>

    <p>5 

        This is a paragraph too

    6</p>

我们的任务是要匹配出其中的所有段落,接下来我们通过不断修正我们的代码来实现此目的

    <p>.*</p>               # 匹配的内容是从<p>1到6</p>,这样的匹配显然有误,因为<p>1和6</p>并不构成一个段落,<p>1跟4</p>匹配才是我们想要的

    <p>.*?</p>              # 匹配的内容是从<p>1到4</p>(通过不断迭代匹配最终会匹配出所有段落),看来关闭贪心解决了我们的问题

递归匹配

将上面的用例扩展一下,仅仅是将第一段中嵌套了一个段落,这种结构还可以继续嵌套构成更复杂的字符串,这里仅以此为例

    <p>1

        This is a paragarph

        <p>2 this sub-paragraph is contained by paragarph 3</p>

    4</p>

    <p>5 

        This is a paragraph too

    6</p>

我们的任务仍然是要匹配出其中的所有段落

    <p>.*?</p>          # 匹配的内容是从<p>1到3</p>,可以看到连关闭贪心也无能为力了,

                        # 可以看到,关闭贪心只能匹配到3</p>,未能到达4</p>,

                        # 如果使用贪心的话会匹配到6</p>,超过了目标4</p>,

                        # 这看来是一个左右为难的事情,多了不行,少了也不行

直接联想到的解决方案,可以使用一个栈来解决这个问题,顺序读入字符串,遇到<p>就将其压栈,直到遇到</p>时将栈顶弹出,生成一个匹配,这样的话,第一个被匹配的是<p>2 this sub-paragraph is contained by paragarph 3</p>,当然这样做就不仅仅是使用正则代码了,得动手写处理压栈出栈的逻辑,那么正则表达式有没有直接简便的解决方案呢?

正则表达式对递归匹配的支持取决于语言本身,PHP,Perl都实现了递归匹配,新发布的python中的regex也将实现递归匹配

PHP的解决方案

    <p>([^<]*|(?R))*</p>        # (?R)将会根据需要不断的扩展成整个正则表达式

python的解决方案,就是不支持,你可以使用即将取代re模块的regex模块或者试试pyparsing模块,或者正如上面所说自己实现压栈出栈的程序

Xiao Wenbin
Xiao Wenbin
Natural Language Processing Engineer

My research interests include machine learning, information retrieval and natural language processing.

Related