3

こんにちは、いつもお世話になっています。

javascriptで正規表現を使うプログラムを書いているのですが、プログラムが動かなくなってしまいます。

試してみたところ、以下のコードで同じ状況が発生しました。

let regex = /(\w+(,|\s)*)+;/;
let text = "XXXX,XXXX,XXX,XXX,XXXX,XXX,XXXX,XXX,XXX,XXX,XXXX, XXXXX";

// ここでフリーズ
let matched = text.match(regex);

console.log(matched[0]);

このコードの場合、textはセミコロンで終わっていないため、一致するものがなくmatchedがnullになると思ったのですが、プログラムの実行が完了しません。

何故このようなことになるのか、教えて頂けないでしょうか?

よろしくお願い致します。

3
  • 2
    フリーズするというよりは「ものすごく時間がかかっている」というのが正しそうです(Intel i9-9900Kの環境で74.5秒かかりました)。カンマ区切りの項目が増えるたびに評価の組み合わせパターンが増えていく(しかも最終的にマッチしない)ことが原因となることがありますが、それに近そうな印象を受けました。 moyolab.blog57.fc2.com/blog-entry-73.html
    – harry0000
    Commented 2020年5月30日 6:53
  • テキスト先頭のカンマ(複数)は無視してマッチ、テキスト先頭以外の連続するカンマは許容する正規表現になっているようですが、これがやりたいことですか?なお harry0000さんのコメントのようセミコロンが末尾にないケースでもnullが返ってきます。私の環境では100秒かかりました。 Commented 2020年5月30日 8:07
  • Catastrophic backtracking が参考になるかと思います。この記事の Lookahead to the rescue! に lookahead(先読み)を使う解決策が提示されていて、本質問の場合には let regex = /((?=(\w+))\2(,|\s)*)+;/ とします。余談ですが、Perl の regexp engine(PCRE) では自動的に catastrophic backtracking を回避してくれます。
    – user39889
    Commented 2020年5月30日 12:45

1 件の回答 1

3

組み合わせ爆発が起っているのでしょう。

regex = /(\w+(,|\s)*)+;/

; の有無で null になるはずということですが、regex 表現の最後尾にあるため、コンピューターは、その前の (\w+(,|\s)*)+ の部分のパターンを作ってから最後に ; を付けたパータンを考え、そこで初めて与えられた文字列にマッチするかしないかを、律儀に全パターンを作って試して行きます。

特に、(,|\s)* で単語区切りがあってもなくてもどちらでもいいような表現になってしまっているのも組み合わせ爆発の一因だと思います。(,|\s)+ とすれば、必ず XXXX, 毎に部分的マッチが確定します。なので、自分なら、こうしますかね:

let regex = /(\w+(,|\s)+)+(\w+);/;

ideone で試した分には、null で無事終了しました。

3
  • その場合、X,,XX,,,XXX; というテキストにもマッチしてしまいます。
    – user39889
    Commented 2020年5月30日 11:15
  • @metropolis いけませんか? 質問者は特にそのような場合を回避するべきとも述べられていないのと、あくまでも趣旨としては、元の regex の問題が発生していた部分に対する改善点を示すということで、これが best / ideal というつもりではありません。そもそもやりたいことの詳細が述べられておらず、単に、「プログラムの実行が完了しない」ということが質問の主眼であると思いますので。
    – hata
    Commented 2020年5月30日 11:20
  • 良いと思いますよ。
    – user39889
    Commented 2020年5月30日 11:31

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。