asin:477413404X
入門正規表現
岩谷宏

ちがうよ!バグじゃないよ!

404 Blog Not Found:perl - Encode-2.31 Released, 2.30 zapped, regexp bug in 5.10.0
ちょっと調べてみると.... 
% perl5.10.0  -le 'print "perl" =~ /^\w{1,8}+$/'
1
% perl5.8.8   -le 'print "perl" =~ /^\w{1,8}+$/'
Nested quantifiers in regex; marked by 
 <-- HERE in m/^\w{1,8}+ <-- HERE $/ at -e line 1.
というわけで、Perl 5.10.0 の bug を偶然にも踏んでいたようです。

これは possessive quantifier というもの。「入門正規表現」は「独占的量指定子」、「詳説 正規表現 第3版」は「絶対最大量指定子」と訳しています。Javaには以前からあったものですが、Perlでは5.10から入りました。

どういうものかというと、こういうものです。

NAME regular expression regex regexp - search.cpan.org
By default, when a quantified subpattern does not allow the rest of the overall pattern to match, Perl will backtrack. However, this behaviour is sometimes undesirable. Thus Perl provides the "possessive" quantifier form as well. 
    *+     Match 0 or more times and give nothing back
    ++     Match 1 or more times and give nothing back
    ?+     Match 0 or 1 time and give nothing back
    {n}+   Match exactly n times and give nothing back (redundant)
    {n,}+  Match at least n times and give nothing back
    {n,m}+ Match at least n but not more than m times and give nothing back

greedy quantifiers (最大量演算子)と似ていますが、最大の違いはバックトラックしないということです。例を説明しましょう。まず以下の表現を考えてみます。

"backtracking" =~ /([a-z]+)(ing)/;

このmatchは成功し、$1, $2はそれぞれbacktrack, ingとなります。この時 regexp エンジンは以下のような挙動を示します。

backtracking
^^^^^^^^^^^^ まずここまでmatch。でも"ing"がみつからない
backtracking
^^^^^^^^^^^< まだ見つからない
backtracking
^^^^^^^^^^<< まだ見つからない
backtracking
^^^^^^^^^<<< 見つかった!

要するに、見つけなおしているわけです。

次に、以下の例を考えてみましょう。

"backtracking" =~ /([a-z]++)(ing)/;

今度のmatchは失敗します。なぜなら[a-z]++はbacktrackingまでmatchした後、後戻りしないためingが見つからないからです。

"backtracking" =~ /([a-z]++)(?:ing)?/;

とすると、$1がbacktrackingとなってこのことがよく理解できます。

これに対して、例えば

'<img alt="backtrack" src="bt.png">' =~ /"([^\"]+)"/;

と

'<img alt="backtrack" src="bt.png">' =~ /"([^\"]++)"/;

は、どちらもbacktrackを見つけますが、後者の方が高速です。

実はこの量指定子は、以下の構文糖衣でもあり、以前のバージョンのPerlでも右に書き直すことで利用yすることが出来ます。

NAME regular expression regex regexp - search.cpan.org 
    Quantifier Form     Bracketing Form
    ---------------     ---------------
    PAT*+               (?>PAT*)
    PAT++               (?>PAT+)
    PAT?+               (?>PAT?)
    PAT{min,max}+       (?>PAT{min,max})

この possessive quantifier に関しては、「入門正規表現」P. 38 と、「詳説 正規表現 第3版」の P. 247 で議論していますが、この点に関しては前者の方が充実した解説となっています。両方とも読んでいたので、存在は知っていたのですが Perl 5.10 に入ったことは失念していました。

Dan the Regular Expressionist