3

StackOverflowErrorRegExパターンを使用して結果を照合したときに得られました。

パターンは(\d\*?(;(?=\d))?)+です。この正規表現は、入力を検証するために使用されます。

12345;4342;234*;123*;344324

入力は、で区切られた値（数字のみ）で構成される文字列;です。各値には*、最後に1つ含めることができます（他の一致のワイルドカードとして使用されます）。;文字列の最後にはありません。

問題は、この正規表現が正常に機能し、値の数が少ないことです。ただし、値の数が多すぎる（300を超える）と、が発生しStackOverflowErrorます。

final String TEST_REGEX = "(\\d\\*?(;(?=\\d))?)+";

// Generate string
StringBuilder builder = new StringBuilder();
int number = 123456;
for (int count = 1; count <= 300; count++) {
    builder.append(Integer.toString(number).concat(";"));
    number++;
}
builder.deleteCharAt(builder.lastIndexOf(";"))

builder.toString().matches(TEST_REGEX); //<---------- StackOverflowError

そしてスタックトレース：

java.lang.StackOverflowError
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079)
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079)
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079)
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079)
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
    ...

ルックアップがたくさんあるので、パターンの先読みがこのエラーの原因になると思いますが、それを減らす方法や回避する方法がわかりません。

私は正規表現の経験がないので、どんな提案にも本当に感謝しています。

4

3 に答える 3

8

問題を修正する前にStackOverflowError...

  1. (\d\*?(;(?=\d))?)+現在の正規表現ではこの条件を検証できないことを指摘しておきます。

    各値には、最後に1つの*を含めることができます（他のマッチングのワイルドカードとして使用されます）

    ここで23*4*4*;34*434*34見られるように、ケースを拒否することはできません1。

  2. 正規表現は、一致しない入力に対して不要なバックトラックを実行します。

  3. Javaは、グループの繰り返しごとに1つのスタックフレームを使用します(\d\*?(;(?=\d))?)（これは1回以上繰り返されます+）。

正しい正規表現は次のようになります。

\d+\*?(?:;\d+\*?)*

これは拒否することに注意してください。これは*、これを受け入れるか拒否するかは要件からあまり明確ではありません。

(?:;\d+\*?)グループを繰り返すたびにスタックが使い果たされるため、これでStackOverflowの問題が修正されるわけではありません。これを修正するには、文法があいまいではないため、バックトラックの必要がないため、すべての数量詞を所有格にします。

\d++\*?+(?:;\d++\*?+)*+

文字列リテラルに入れる：

"\\d++\\*?+(?:;\\d++\\*?+)*+"

上記の正規表現を、3600を超えるトークン（で区切られている）を持つ一致および不一致の入力でテストしました;。

脚注

1：regex101はPCREフレーバーを使用しますが、これはJavaregexフレーバーとは少し異なります。ただし、正規表現で使用される機能はそれらの間で共通であるため、矛盾はないはずです。

付録

  • 実際、正規表現を使用したテスト(\d\*?(;(?=\d))?)+（要件によっては正しくありません）から、少なくとも約3600トークン（で区切られた、文字列の長さは約20k文字）を使用したテストでは、外側の+所有格を作成することで問題++が解決するようです。。また、一致しない文字列に対してテストする場合、実行時間が長くなることはないようです。StackOverflowError;

  • 私の解決策では*、グループの量指定子を(?:;\d+\*?)所有格にするだけで解決できますStackOverflowError。

    "\\d+\\*?(?:;\\d+\\*?)*+"

    ただし、安全を期すためにすべてを所有格にします。

于 2013-02-26T08:22:58.803 に答える
1

あなたの正規表現は少し効果がなく、あなたの説明と一致しません。'\ d \ *？'があります -オプションの*が続く1桁です。次に、オプションの';（？= \ d）'-';' 先読み桁付き。文字列「1*2 * 3 *」は正規表現と一致しますが、説明とは一致しません。followregexpを使用できます。それはあなたの入力と一致し、もう少し効果的です。

final String TEST_REGEX = "(\\d+\\*?)(?:;\\d+\\*?)+";

カウントが300未満の場合はテストに合格しますが、それよりも大きい値の場合は失敗します。indexOfやsubstringなどのプレーンな文字列操作を使用して、入力を確認します。

于 2013-02-26T06:50:43.083 に答える
0

スタックの最大サイズを増やして、オーバーフローしないようにすることをお勧めします。 あなたはここでそれを行う方法について読むことができます。

基本的に、-Xssオプションを使用してプログラムを開始します。たとえば、-Xss4m コードをで開始したとき-Xss4m、プログラムはスタックオーバーフローなしで実行されました（が返されますtrue）。

于 2013-02-26T05:42:09.753 に答える