Perl の正規表現マッチングは左貪欲であるため、正規表現は
/\A (a+) (.+) \z/x
文字列 'aaab' に一致すると、$1='aaa' と $2='b' が設定されます。( \A と \z は、文字列の開始と終了を強制するだけです。)
次のように、貪欲でない修飾子を指定することもできます。
/\A (a+?) (.+?) \z/x
これでも一致しますが、$1='a' と $2='aab' を指定します。
しかし、文字列を生成するすべての可能な方法を確認したいと思います。
$1='aaa' $2='b'
$1='aa' $2='ab'
$1='a' $2='aab'
最初の方法はデフォルトの左貪欲な動作に対応し、3 番目の方法は最初の一致を非貪欲にすることに対応しますが、これらの両極端の間に方法があるかもしれません。指定された正規表現が指定された文字列を生成するすべての可能な方法を試すことができる正規表現エンジン (Perl のもの、または PCRE や RE2 などの他のもの) はありますか?
とりわけ、これにより、最長の合計一致が選択される「POSIX互換」正規表現マッチングを実装できます。私の場合、あらゆる可能性を本当に見たいと思っています。
(1 つの方法は、正規表現自体を変更し、最初の試みで + 修飾子を {1,1} に置き換え、次に {1,2}、{1,3} などに置き換えます - + 修飾子と * 修飾子の組み合わせごとにこれは非常に骨の折れる作業であり、処理が遅く、停止するタイミングが明確ではありません。もっとスマートなものを期待しています。)
バックグラウンド
これによりどのような問題が解決されるかについての Jim G. の質問に答えるために、ルールによって与えられる 2 つの言語間のルールベースの翻訳システムを考えてみましょう。
translate(any string of one or more 'a' . y) = 'M' . translate(y)
translate('ab') = 'U'
次に、translate('aaab') の可能な結果、つまり 'MU' があります。次のように、これらのルールを正規表現に基づいて Perl コードに入れようとするかもしれません。
our @m;
my @rules = (
[ qr/\A (a+) (.*) \z/x => sub { 'M' . translate($m[1]) } ],
[ qr/\A ab \z/x => sub { 'U' } ],
);
ここで、translate は各 @rules に対して実行され、順番に適用しようとします。
sub translate {
my $in = shift;
foreach (@rules) {
my ($lhs, $rhs) = @$_;
$in =~ $lhs or next;
local @m = ($1, $2);
my $r = &$rhs;
next if index($r, 'fail') != -1;
return $r;
}
return 'fail';
}
ただし、translate('aaab') を呼び出すと、'fail' が返されます。これは、(a+)(.*) に一致する最初のルールを適用しようとし、正規表現エンジンが「a」の可能な限り長い文字列との一致を検出するためです。
池上が提案した答えを使用して、正規表現が文字列を生成するすべての方法を試すことができます。
use re 'eval';
sub translate {
my $in = shift;
foreach (@rules) {
my ($lhs, $rhs) = @$_;
local our @matches;
$in =~ /$lhs (?{ push @matches, [ $1, $2 ] }) (*FAIL)/x;
foreach (@matches) {
local @m = @$_;
my $r = &$rhs;
next if index($r, 'fail') != -1;
return $r;
}
}
return 'fail';
}
これで、translate('aaab') は 'MU' を返します。