java - 正規表現マッチングで JVM が動かなくなる

Question

JBehave ライブラリにいくつか問題があり、JRE が CPU の作業でスタックする正規表現に行き着きました。

式は(.*?)?(\{((.*?)(\|)?)*?\})(.*)、私はそれを照合していますcreate entity of type $entityType {set properties $propertyNames to values $propertyValues- 閉じていない中括弧に注意してください。

上記の式を最適化する方法や、適切に回避する方法はありますか?

Answer 1

これは、ループするということではなく、フェイルファストとはほど遠いということです。原因は次の部分です。

((.*?)(\|)?)*?

1 番目と 2 番目のものは何と一致するはず*?ですか? 失敗した場合、正規表現エンジンはすべての組み合わせを試すためにバックラクトする必要があります。(まあ、DFA エンジンではありませんが、Java 正規表現エンジンは NFA です)

ここで、正気の正規表現を作成できるように、この正規表現が何に一致するかを指定する必要があります。

ちなみに、これが怠惰な量指定子がダメな理由です。

Answer 2

同じことを行うこのパターンを試してください (同じキャプチャで):

([^\n{]*+)(\{(([^|}]++)(\|)?+)*+\})([^\n]*+)

ここでのアイデアは、できるだけ早く失敗することです。そのため、文字クラスを所有量指定子で制約することにより、遅延量指定子を置き換えました。

しかし、あなたはこれの最終目標を与えていないので、より良いパターンを与えることはできません.