PHP中的递归正则

May 10th, 2010 Categories: 教程, 翻译

之前一篇文章翻译了Perl语言中的递归正则表达式. 其实不少语言中的正则都是支持递归的, 例如本文要介绍的PHP正则递归. 虽然, 工作中最常用的正则表达式都很”正则”, 只用最基本的语法就能解决85%以上的问题, 而且合理有效地使用普通正则来解决复杂问题也是一门技巧与学问; 但是高级一点的语法的确有它存的价值, 有时不用它还真办不了事儿; 况且学习正则的乐趣也在于尝试各种各样的可能性, 满足自己无穷无尽的好奇心.

本文内容, 整理自网文Finer points of PHP regular expressions. 其分析过程剥茧抽丝, 丝丝入扣, 值得一读. 该文系统地列出了PHP中正则表达式常见特性, 我只摘取其中递归部分翻译整理出来.

正文

例子

什么时候会用到递归正则表达式呢? 当然是待匹配的字串中递归地出现某种模式时(貌似废话). 最经典的例子, 就是递归正则处理嵌套括号的问题了. 例子如下.

假设你的文本中包含了正确配对的嵌套括号. 括号的深度可以是无限层. 你想捕获这样的括号组.

恕我剧透, 标准答案是这样的:

1
2
3
4
5
6
7
<?php
$string = "some text (a(b(c)d)e) more text";
if(preg_match("/\(([^()]+|(?R))*\)/",$string,$matches))
{
    echo "<pre>"; print_r($matches); echo "</pre>";
}
?>

其输出结果是:

1
2
3
4
5
Array
(
    [0] => (a(b(c)d)e)
    [1] => e    
)

可见, 我们所需要的文本, 已经捕获到$matches[0]中了.

原理

现在思考原理.

上面的正则表达式中的关键点是(?R). (?R)的作用就是递归地替换它所在的整条正则表达式. 在每次迭代时, PHP 语法分析器都会将(?R)替换为”\(([^()]+|(?R))*\)“.

因此, 具体到上述的例子, 其正则表达式等价于:

"/\(([^()]+|\(([^()]+|\(([^()]+)*\))*\))*\)/"

但是上面的代码只适合深度为3层的括号. 对于未知深度的括号嵌套, 就只好使用这种正则了:

"/\(([^()]+|(?R))*\)/"

它不但能够匹配无限深度, 还简化了正则表达式的语法. 功能强大, 语法简洁.

现在来细看一下"/\(([^()]+|(?R))*\)/"是怎样匹配"(a(b(c)d)e)"的:

  1. "(c)"这部分被正则式 "\(([^()]+)*\)" 匹配. 请注意, (c) 其实就相当于整个递归的一个缩影, 麻雀虽小五脏俱全, 因此它用到了整个正则表达式.
    换言之, 下一步中的(c), 可以使用(?R) 来匹配.
  2. (b(c)d)的匹配过程为:
    1. "\("匹配"(";
    2. "[^()]+"匹配"b";
    3.  (?R)匹配"(c)";
    4. "[^()]+"匹配"d";
    5. "\)"匹配")".

根据上面的匹配原理, 不难理解为什么数组的第2个元素$matches[1]与'e'等价. 子串'e'是在最后一次匹配迭代中被捕获. 匹配过程中, 只有最后一次的捕获结果才会保存到数组中.

rex注: 关于这个特性, 可以自行尝试一下, 看看使用正则式([a-z]+[0-9]+)+来匹配字串abc123xyz890, 其捕获结果$1是什么. 注意, 其结果与 Left Longest 原理并不冲突.

如果我们只需要捕获 $matches[0], 可以这样做:

1
2
3
4
5
6
7
<?php
    $string = "some text (a(b(c)d)e) more text";
    if(preg_match("/\((?:[^()]+|(?R))*\)/",$string,$matches))
    {
        echo "<pre>"; print_r($matches); echo "</pre>";
    }
?>

产生的结果相同:

1
2
3
4
Array
    (
     [0] => (a(b(c)d)e)
    )

所做的改动是捕获括号()改为非捕获捕获括号(?:)了.

还可以进一步完善为:

1
2
3
4
5
6
7
<?php
    $string = "some text (a(b(c)d)e) more text";
    if(preg_match("/\((?>[^()]+|(?R))*\)/",$string,$matches))
    {
        echo "<pre>"; print_r($matches); echo "</pre>";
    }
?>

这里我们用到了所谓的一次性模式(rex注: 余晟先生译的《精通正则表达式v3.0》中, 谓之”固化分组”. 可参考该书.) PHP手册也推荐只要条件允许, 就尽可能使用这种模式, 以便提升正则表达式的速度.

一次性模式很简单, 这里不再详述. 如果感兴趣, 可以参考PHP 官方手册. 如果您想深入学习PERL兼容式正则表达式, 请参考文末链接.

提到的链接

Tags: ,
Leave a comment | Trackback

9 Responses to “PHP中的递归正则”

  1. jlake
    May 10th, 2010 at 18:30
    1

    PHP 里面，
    preg_ 开头的函数，其正则表达式是 perl 兼容模式 （PCRE）。
    ereg_ 开头的函数就不是 perl 兼容，而是 POSIX。

    [Reply]

    rex Reply:
    May 10th, 2010 at 9:25 pm

    个人习惯用preg_.

    [Reply]

    Reply
  2. 老张
    May 10th, 2010 at 21:47
    2

    正则用起来很麻烦，但是会用了很方便

    [Reply]

    rex Reply:
    May 11th, 2010 at 6:06 am

    如果您需要频繁地处理字符串的话，花一点时间学习正则表达式，会非常有帮助。

    [Reply]

    Reply
  3. 神の呼出
    August 2nd, 2010 at 23:23
    3

    我想用PHP格式化html代码，可是匹配相当麻烦啊。
    比如

    1
    2
    <div></div>
    <div></div>

    和

    1
    2
    3
    4
    <div>
        <div>
        </div>
    </div>

    这样只有递归正则才能实现，但是还有一些标签，如：

    1
    <img src="" />

    等并非成对出现。这样就麻烦了。更何况不知道代码有几层，更不要说如：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    <div>
        some content<img src="" />
        <div>
            <img src="" />
            <ul>
                <li>some content</li>
                <li>some content</li>
                ...
            </ul>
        </div>
    </div>
    <div></div>

    这样乱七八糟的代码了。请教高手，要将没一个标签按层匹配放入数组，正则到底能不能实现？若能，该怎么写？谢谢！
    PS: 逆向引用是不是不能和递归并存？

    [Reply]

    rex Reply:
    August 3rd, 2010 at 8:14 am

    这个问题很有意思。能否详细地描述一下您的问题？例如，需要格式化的文本是什么，格式化之后的文本是什么的，格式化中，有哪些问题。等等。上面您的描述再加上一些具体的格式化的例子就更好了。谢谢。

    [Reply]

    神の呼出 Reply:
    August 4th, 2010 at 12:13 am

    我想格式化的文本为任意html代码，目前代码里面的标签是平衡的，即有个

    1
    <label>

    就有一个

    1
    </label>

    相对应，当然也包含独立标签如

    1
    <img />

    、

    1
    <meta />

    等，需要格式化的代码为一长字符串，即不包含任意\t，\n等空白符。我需要的是将这一段代码按如下方式格式化：
    每出现一组成对标签，即缩进一个tab
    最内层的成对标签应处于同行
    若出现的是独立标签，则将其与它的父标签（一定是成对的）置于同一行
    所有文字与其父标签置于同一行
    表单独立元素input实现同级缩进（即不在同一行）
    若可以的话，对不平衡组也进行格式化（按出现顺序增加tab）。

    这个用js很方便，但是要用php处理生成网页就麻烦了。WordPress自带的函数经常把\n和\t去掉，给出一大堆东西。虽然说没人会在意源代码，但是我有点完美主义，最好把html源代码也搞的漂亮些。

    我能写出的正则如

    1
    $pattern = "/<[\w]+[^>]*>.*<\/\\2>/";

    这样只能贪婪匹配，却并无方法匹配如

    1
    2
    3
    4
    <div>
        <div>
        </div>
    </div>

    这样的形式，若用

    1
    (?R)

    又没有办法使用逆向引用。还有判断独立标签我用的是零宽断言

    1
    (?!=\/)

    （因为独立标签末尾应该是

    1
     />

    这样的）似乎也不是很好，因为有时带有属性(class,id,src等)的标签就没法匹配。所以虽然比较麻烦，但还是请高手赐教。无论写出的正则多长都没关系。谢谢！

    PS:我现在的做法有点傻，就是先用正则找到一个成对标签的头，即

    1
    <label>

    然后每找到一个

    1
    <label>

    加一个tab,若找到的是

    1
    </label>

    则减少一个tab，但显然不符合正则的精神啊

    [Reply]

    rex Reply:
    August 4th, 2010 at 9:17 am

    我写了一个简单的标签格式化脚本，一会写发一篇博文介绍一下，希望有所帮助。

    [Reply]

    Reply

Leave a Comment