再帰グループがマッチしすぎる理由

SkRegExp の「再帰グループがマッチしすぎる」とは、このブログにもSkRegExpのヘルプにも書いています。

再帰グループの仕様は、PCREと同様、再帰グループの中にはバックトラックしない仕様です。

それなのに、PCRE でマッチしない正規表現パターンが SkRegExp ではマッチしていました。

たとえば、^(<(?:[^<>]+|g<3>|g<1>)*>)()(!>!>!>)$ と言うパターンを <<!>!>!>><>>!>!>!> にマッチさせたとき、PCRE ではマッチしませんが、SkRegExp version 1.5.5 ではマッチします。

注)SkRegExp version 1.5.4 以前はバグのためマッチしません。実は、これがマッチしてしまったのが原因究明に繋がりました。

これに何年も悩み続けていましたが理由がわかりました。

「バックトラックしない」範囲を私が間違えていたからでした。

バックトラックしないのは再帰グループが終わった後だと思い込んでいたのです。

3回再帰が起こったら、3回の再帰が終了する間はバックトラックしていました。

だから、「マッチしすぎる」となっていたのでした。

さて、原因はわかったもののどう対処するかが問題です。

と言うのも PCRE と本当に同じにするとマッチしないパターンが大量に発生するのは明らかです。

今までマッチしなかったものがマッチするより、マッチしていたものがマッチしなくなる方が困ることが多いですよね。

実は私自身が一番困ります。

と言う訳で、再帰グループの仕様を変更することにします。

Perl 5.8 以降と同様、再帰グループの中にバックトラックする仕様に変更します。

この方が今使っているパターンへの影響も少ないでしょうし、何より、こちらの方がカンタンなのです。

SkRegExp の構造だと PCRE と同じにする方が難しいんです。

最大の懸念だった幾何級数的マッチ対策も今のままで行けそうです。

と言う訳で、近日、1.6 を公開します。

コメントを残す

メールアドレスが公開されることはありません。