正则表达式(regular expression)有着强大的功能,但也不是万能的,匹配(match)匹配(balanced)的括号(parentheses)就是一个挺头疼的问题。不过perl正则表达式中的一个扩展(??{ code })却能很好的处理这个问题。直接就能把上下文无关文法(Content-Free Grammar, CFG)

P --> <empty>
P --> ( P )
P --> P P

改写成对应的正则表达式

$paren = qr#|\((??{$paren})\)|(??{$paren})(??{$paren})#;

不过由于(??{$paren})(??{$paren})中的第一个(??{$paren})可以不断匹配0个字符,因此它不能正常工作,不过只要稍加修改,其等价形式

$paren = qr#|\((??{$paren})\)(??{$paren})?#;

就能够完成匹配balanced parentheses的工作了。

(??{ code })是动态正则表达式,code将在运行时求值,所求值再作为正则表达式。

This is a “postponed” regular subexpression. The “code” is evaluated at run time, at the moment this subexpression may match. The result of evaluation is considered as a regular expression and matched as if it were inserted instead of this construct.

其很重要的一个用途就是实现正则表达式的递归(recursion)

利用这个扩展,可以实现一个简单利用递归判断html标签是否合法匹配的正则表达式:

$html = qr{
    [^<>]*                                      # plain text
    (
        <(?<tag>[[:alnum:]]+)(?![[:alnum:]])    # start tag
            [^>]*                               # optional properties
        (
            />                                  # empty-element tag
            |
            (?<!/)>                             # not empty-element tag
                (??{ $html })                   # inner html
            </\k<tag>>                          # end tag
        )
        [^<>]*                                  # plain text
    )*
}xi;

while (<DATA>) {
    print /^$html$/ ? "YES\n" : "NO\n";
}

__DATA__
It works.
<html><head><title>title</title></head> <body bgcolor="#ffffff">content</body></html>
<ooxx>prefix <A>ab<b> <c>&lt;</c> <e E="e"/> <D>&gt;</D> </B>ba</a> postfix</ooxx>
<form method="POST">Gao: <input type="text" name="gao"/></form>

<a><b></a></b>
<HTML></H>
<H></HTML>
<$/>
<form><input type="submit"></form>

然而(??{ code })亦不是万能的。首先在perldoc中就有WARNING说feature很可能在未来发生变动。而且对于比较复杂的情况,其效率也会严重下降。比如对于SPOJ 384. Any fool can do it

#!/usr/bin/perl
# FOOL.pl

$set = qr/(
    \{
    (
        ([{},]|(??{ $set }))
        (,
            ([{},]|(??{ $set }))
        )*
    )?
    \}
)/x;
$pat = qr/^$set$/;

chomp($re = <>);
for $ri (1 .. $re) {
    chomp($_ = <>);
    print "Word #$ri: ", (/$pat/ ? "Set" : "No Set"), "\n";
}

这段程序对于较短的输入,都能正确求解;但对于长而复杂的输入,根本不能在短时间内返回结果。

4 Responses to “递归正则表达式 —— (??{ code })”
  1. RainFlying says:

    请收下我的膝盖。

  2. lemontv says:

    大姐好强…为什么找正则的递归也能找到你这里。

  3. Navi says:

    各种扩展…

  4.  
Leave a Reply