指数関数的発散(1)

繰り返しがネストして計算時間が指数関数的に発散するパターンについて、対応するかどうかは決めていない。しかし、対応方法については今日考えてみた。

まず、問題のパターンは、以下のようになっている。

/(A*...B*|...)*/

ここでAとBは、両方で共通にマッチ可能な文字(列)が存在するパターンである。上記のパターンでは、AとBが同じ選択肢にあるとして書いたが、別の選択肢の中にあっても、同じ問題は起きる。

AとBが縮退して、最も単純化された場合には、以下のようになる。

/(A*)*/

これらのパターンで問題が起きる。

ついでに書いておくと、上記でグループのキャプチャがない以下のような場合には、自動的に無駄な繰り返しを省くようになっているので、問題は起きない。

/(?:A*)*/