最短一致マッチで誤解しやすいこと

問題

文字列'abcccde'に対して、以下の最短一致マッチ(non-greedy match)を使った(1)から(4)の正規表現をかけたときのマッチ結果は？ (マッチするかしないかではなく、どの部分がマッチして $& に入るかです。)

foreach my $regexp (
    qr/bc*/  , # (1)
    qr/bc*?/ , # (2)
    qr/c*d/  , # (3)
    qr/c*?d/ , # (4)
){
    if( 'abcccde' =~ $regexp ){
        print $regexp, " -> match: $&\n";
    }else{
        print "no match.\n";
    }
}

実行せずに(4)がわかれば、通です。オレは間違えました(笑。

解説

comp.lang.perl.moderatedグループに同様の話を見つけました。

要は、「最短一致はマッチの開始位置の変更はしてくれない」ってことです。上の例だと、'abcccde'の三文字目の'c'からマッチングをスタートするとマッチできてしまうので、これで処理が終わってしまいます。四文字目や五文字目の'c'から始めてマッチするかは試行してくれないってことです。

正規表現エンジンは、'abcccde'を左から順に 'abcccde' 、 'bcccde' 、 'cccde'、 'ccde'、 'cde'、 'de'、 'e' と細切れにし、それぞれの文字列で前方一致的な評価サイクル*1を順番に実行して行き、成功したところでマッチングを完了します。よって実装面から考えれば、'c*?d'が'cccde'のサイクルでマッチした結果('cccd')を返すというのはとても自然な動きです。

追記

読み直して思ったんですが、普段「最短一致」って呼んでるから間違えるんですね。「欲張り」「控えめ」でいいわけるとこういう勘違いはしないのかもしれません。

*1:平たく言えば、先頭に'^'をつけた正規表現をかけるイメージ。