2010年9月12日日曜日

Perl best practices[Perlベストプラクティス] 12章 正規表現 12.13~12.17


このエントリーをはてなブックマークに追加


ターミネータ(区切りとなる文字)がわかっている場合は、.*ではなく補完文字クラスを使用する


.*という正規表現はとても処理が重くなる可能性がある。

 例えば以下の例では、最初の.*は隣の%ともマッチし、その後、文字列の終わりまでマッチする。その後、次の正規表現である%を文字列の続きから探そうとするが、すでに.*によって文字列の最後までマッチが進行しているので、%がマッチする箇所は存在せず、マッチは失敗する。このとき、正規表現エンジンは、%がマッチに失敗した箇所から一文字後ろの文字に着目して、マッチを試みる(バックトラック)。マッチが成功するまでこの一文字ずつのバックトラックを繰り返すため、効率はとても悪い。



$sorce =~ m/\A (.*) % (.*) & (.*) /xms;



とりあえず.*を.*?にしてみても、処理は改善されない

 このような正規表現を作成して、処理がとても遅い場合、とりあえず.*を.*?にして問題を解決してみようと思うかもしれないけれど、たぶんあまり上手くいかない。
 .*?は.*とは違い、マッチする文字列をできるだけ少なくしようとする「けちけちした繰り返し」ではあるが、これは結局、文字の先読みをしているので、ターミネータ(区切り文字。この場合、%と&のこと)が単一文字よりも複雑である場合は、処理が遅くなる可能性がある。


.*と.*?はエラーを隠蔽する可能性がある

 正規表現をみる限り、おそらく製作者はデータに%と&が一つずつ含まれていることを想定しているが、%と&が文字列に複数含まれていても.*と.*?はエラーにならない。文字列が...%....%....&...となっていた場合、2回目の%までは、.*か.*?にマッチする。そうしないと、全体でマッチが成功しないから。


補完文字クラスを使用する

 上記の理由から、解決策は%や&といったターミネータ以外を表現する正規表現を使用すること。つまり、以下のようにする。



$source =~ m/\A ([^%]*) % ([^&]*) & (.*) /xms;


 補完文字クラスを使用することにより、.*?の先読みも、.*のバックトラックも行われない。かつ余分なターミネータが含まれていた場合、マッチに失敗するようになる。
 また最後の(.*)に着目して欲しい。これは常にマッチに成功するので、バックトラックは行われない。逆に、(.*?)が正規表現の最後にあるのは常に間違いである。(.*?)は「けちけち繰り返し」なので、(.*?)の後に正規表現がないならば、最もケチなのは、まったくマッチをしないことになる。そのため、常にNothingにマッチし、成功する。このため、最後の(.*?)は余計であるか、書き手が(.*?)の挙動を理解していないために、書き手の意図とは異なったものであるか、\zアンカーの付け忘れのいずれかである。(\zアンカーがあれば、(.*?)は文字列の最後までマッチさせる義務が生じる)


補足のための括弧は、補足のためだけに使用する


単純なグループ化のために括弧を使用しない

 グループ化には(?:)を使用すること。後方参照する必要がないならば、こっちのほうが、余計な補足をしなくていい。余計な補足は、余計な処理をする以上に、保守をする人間に誤った意図を伝えることが問題となる。例えば、以下の例では、perform_cleanup()サブルーチンの中で補足された文字が使われていないか探し回るハメになる。(そして結局使われていないことがわかる)



if ( $cmd =~ m/\A (q | quit | bye | exit) \n? \z/xms ) {
perform_cleanup();
exit;
}



(補足した正規表現が、そのままサブルーチンの中で使えるなんて知らなかった)


補足変数$1,$2などは、パターンマッチが成功した場合にのみ使用する


 パターンマッチが成功したかどうかは、$1,$2などが定義されているかをチェックするのではなく、常に以下のようにパターンマッチ全体が成功したかどうかを評価すること。



if ($full_name =~ m/\A (Mrs?|Ms|Dr) \s+ (\S+) \s+ (\S+) \z/xms) {
($title, $first_name, $last_name) = ($1, $2, $3);
}


 なぜなら、パターンマッチに失敗した場合、$1などの変数には何も代入はされないが、以前に成功したパターンマッチの結果が保持されているから。


補足変数をそのまま使用せず、適切な名前を付ける


 $1,$2などは$_[0],$_[1]などと同じく、何も意味のない値で保守に苦労する。また$1と$2の間に新しく補足変数を追加した場合、従来の$2は$3になるため、その後のコードをすべて書き直す必要がある。
 このようなことをしないためにも、適切な名前をつけた変数に代入するようにすること。この際、リストコンテキストを用いて補足した値を直接リストに渡すことができる。これは、常に補足した値をすべて返すため、変数に代入し忘れることがない点で推奨される。



my ($opt_name, $operator, $opt_val, $comment)
= $config =~ m/\A (\S+) \s* (=|[+]=) \s* ([^;]+) ; \s* \# (.*)/xms;


 ただし、次節で説明するように、/gc修飾子を使用する場合は適していない。


トークンごとのパターンマッチ


発見したトークンを置換で文字列から削り取るのは処理が遅い

 文字列をトークンに分解する際には、以下のように少しずつ文字列を削り取っていくのが常套手段だが、処理が遅くなってしまう点が良くない。



while (length $input > 0) {
if ($input =~ s{\A ($KEYWORD)}{}xms) {
my $keyword = $1;
push @tokens, start_cmd($key_word);
}
else if ($input =~ s{\A ($IDENT)}{}xms) {
my $ident = $1;
push @tokens, start_ident($key_word);
}
else if ($input =~ s{\A ($BLOCK)}{}xms) {
my $ident = $1;
push @tokens, start_block($key_word);
}
else {
my ($content) = $input =~ m/ \A ([^\n]*) /xms;
croak "Error near: $content";
}
}


削らずに前回位置を記憶するだけにする


 このため、マッチした部分を置換によって削るのではなく、/gcフラグをセットし、前回マッチした位置を記憶し、組み込み関数pos()を使用して、記憶した位置から次のトークンを探すようにする。/gは前回位置を記憶し、/cはマッチに失敗しても位置記憶(前回マッチに成功した位置)をリセットしないようにする。



cフラグを伴って\Gを使う局面は、典型的にはtokenizerのようにあるマッチが失敗したときに別のマッチを試したいときです。
perlfaq6 - Regular Expressions ($Revision: 1.31 $, $Date: 2005/03/27 07:17:28 $) 訳出 2005/11/2



 さっきのコードと違うところは、while文の終了条件にposを使用していること。\A(削り取った文字列の先頭)が\G(前回マッチした終わりの位置)になっていること。置換は必要ないので、s{ }{ }ではなくm{ }であること。



pos $input = 0;

while (pos $input < length $input) {
if ($input =~ m{\G ($KEYWORD) }gcxms) {
my $keyword = $1;
push @tokens, start_cmd($key_word);
}
else if ($input =~ m{\G ($IDENT)}gcxms) {
my $ident = $1;
push @tokens, start_ident($key_word);
}
else if ($input =~ m{\G ($BLOCK)}gcxms) {
my $ident = $1;
push @tokens, start_block($key_word);
}
else {
my ($content) = $input =~ m/\G ([^\n]*) /gcxms;
croak "Error near: $content";
}
}



三項演算子の正規表現版

 この場合、条件文が同じ@tokensに値を設定しているので6章で説明した三項演算子が有効である。



#略
push @tokens, (
$input =~ m{ \G ($KEYWORD) }gcxms ? start_cmd($1)
#略



gcフラグはリストコンテキストで使わない

 /gフラグはスカラコンテキストとリストコンテキストでは動作が異なる。リストコンテキストでは、正規表現にマッチした部分文字列がリストとして返されるようになる。





0 件のコメント:

コメントを投稿