バランスしたカッコの正規表現問題

結城浩

ええと、Perlに詳しい方に質問です。 「Perlでバランスしたカッコにマッチする正規表現は書けるでしょうか?」 ラクダ本(英語第三版p.214)を見ると、 以下のような再帰的なパターン(!)を書けるらしいのですが、 それ以外に方法はないんでしょうか?

$np = qr {
    \(
        (?:
            (?> [^()]+ )
            |
            (??{ $np })
        )*
    \)
}x;

これだけでは教えてクンになりそうなので(なっていますが)、以下にテストスクリプトを書きます。 知りたいのは、$givenから$answerを取り出す正規表現になります。 私の正規表現 /\((([^()]*(\([^()]*\))?)*)\)/ では最後の3つがNGになってしまいます。 つまり入れ子がうまく扱えないのですね。 /e を使ってevalしちゃうというのは避けたいのです…。

use strict;

my @pattern = (
    [ "()" , "" ],
    [ "(a)" , "a" ],
    [ "(abc)" , "abc" ],
    [ "(ab(c))" , "ab(c)" ],
    [ "(a(b)c)" , "a(b)c" ],
    [ "((a)bc)" , "(a)bc" ],
    [ "((a)b(c))" , "(a)b(c)" ],
    [ "((ab)c)" , "(ab)c" ],
    [ "((a(b))c)" , "(a(b))c" ],
    [ "(X(a(b))c)" , "(Xa(b))c" ],
    [ "abc((()a((b))c))def" , "(()a((b))c)" ],
);

for my $pattern (@pattern) {
    my ($given, $answer) = @$pattern;
    my $result;
    if ($given =~ /\((([^()]*(\([^()]*\))?)*)\)/) {
        $result = $1;
        if ($answer eq $result) {
            print "ok";
        } else {
            print "NG";
        }
    } else {
        print "Not matched";
    }
    printf("%20s %20s %20s\n", $given, $answer, $result);
}

↓

ok                  ()
ok                 (a)                    a                    a
ok               (abc)                  abc                  abc
ok             (ab(c))                ab(c)                ab(c)
ok             (a(b)c)                a(b)c                a(b)c
ok             ((a)bc)                (a)bc                (a)bc
ok           ((a)b(c))              (a)b(c)              (a)b(c)
ok             ((ab)c)                (ab)c                (ab)c
NG           ((a(b))c)              (a(b))c                 a(b)
NG          (X(a(b))c)             (Xa(b))c                 a(b)
NG abc((()a((b))c))def          (()a((b))c)

ちなみに私の正規表現は、次のようになっています。

/
    \(                                  一番外側のカッコ開き
        (                               $1で取るためのカッコ
            (
                [^()]*                  普通の文字の繰り返し
                (                       (あれば)バランスしたカッコ(入れ子なし)
                    \(
                        [^()]*
                    \)
                )?
            )*
        )
    \)                                  一番外側のカッコ閉じ
/

何人かからさっそくフィードバックをいただく。 「入れ子になったカッコ」はプッシュダウンオートマトンが生成する文脈自由文法なのに対し、 正規表現は有限オートマトンが生成する範囲までしか言語を生成できないので(何だか日本語が変だな)、 普通の方法では不可能ではないか、とのこと。ふむ、なるほど。

(2003年12月8日の日記から)

豊かな人生のための四つの法則