可変長テキストの戻り読み

プログラミング


なんだか最近、正規表現ネタが多い気がするが、仕事では本当によく使う*1ので、
必然的にそんな話が多くなってしまうのかもしれない。
そして平日の昼間は+とか*とか(?<=)とか(?:)みたいな記号が僕の頭の中を駆け巡っていたりする。
いや、もちろんそんなことばっかりやってるわけじゃありませんが。

文字列を指定の位置に挿入する


Perlやその他巷でよく使われている(?)言語に搭載されている正規表現エンジンには
文字列の指定の位置に文字列を挿入するために、先読み(?=)と戻り読み(?<=)の機能がある。
この2つは指定した文字列自体ではなく、文字列の位置にマッチする。


例えば、次の場合、$strの中身はabcdefghiとなる。

<?php
$str = 'abcghi';
$str = preg_replace('/(?<=abc)/', 'def', $str);
?>

しかし、次のように可変長な正規表現でマッチさせようとすると固定長じゃないと使えませんよと怒られる。

<?php
$str = 'abbbbbbbbbbcghi';
$str = preg_replace('/(?<=ab+c)/', 'def', $str);
?>

Warning: preg_replace(): Compilation failed: lookbehind assertion is not fixed length at offset 8

Perlでも試してみたが、同じようなメッセージが表示された。

#!/usr/bin/perl
$str = 'abbbbbbbbbbcghi';
$str =~ s/(?<=ab+c)/def/;

Variable length lookbehind not implemented in regex; marked by <-- HERE in m/(?<=ab+c) <-- HERE 
/ at regextest.pl line 3.

理由


昨日、これで少しハマったので、フクロウ本を読み返してみたら、可変長テキストによる戻り読みをサポートしているのは、
.NETを含めたごく一部だけらしい(先読みは可変長でも問題ない)。さらに以下のような記述がある。

任意の可変長テキストにマッチできる戻り読みに出会うと、正規表現エンジンは文字列の先頭から戻り読み部分の表現をチェックする必要があるため、長い文字列の終わり近くでそのような戻り読みを要求されると、大変無駄な処理を強いられることになる。 (「詳説 正規表現 第2版」 P.127)

先頭からチェックし直す理由がよくわからなかったので、調べてみたのだが、
ここによると、どうやら戻り読みを行う場合、正規表現エンジン内部では右から左にマッチが進むらしい。
一例として、鬼車のソースを眺めてみると、確かに戻り読みの処理の部分では右から左に進んでいる。
このため、可変長テキストの場合は先頭まで戻った後、再びその可変長な表現にマッチするか
調べなければならないようだ。(つまり、↑に書かれてあるようにパフォーマンス的によろしくない)
つか、何でこれを戻り読みって言うのかわからなかったんだけど、内部で戻りながら読んでるってことだったのね。


ちなみにRuby1.8.5のソースも眺めてみたのだが、こっちはそもそも戻り読みの機能自体がない模様。
鬼車のソースを眺めてみると、この機能が実装されているっぽいので、
そのうち使えるようになるんだろうけど。(1.9系列で採用されるらしい)

解決策


先読みや戻り読みを使った挿入はキャプチャを使って書き直すことができる。

<?php
$str = 'abbbbbbbbbbcghi';
$str = preg_replace('/(ab+c)/', '\1def', $str);
?>

なんか冗長な気がするが、こっちの方がわかりやすい気もする。

*1:たまに調子に乗って使わなくてもいいところで使ってしまったりするが