StackOverflowError wenn passende große Eingabe mit RegEx

Bekam ich StackOverflowError beim Abgleich das Ergebnis mit einem RegEx pattern.

Das Muster ist (\d\*?(;(?=\d))?)+. Diese regex wird verwendet, um überprüfen die Eingabe:

12345;4342;234*;123*;344324

Die Eingabe aus einem string besteht, der die Werte (nur Ziffern), getrennt durch ;. Jeder Wert könnte auch der eine * am Ende (als Platzhalter für andere "matching"). Es gibt keine ; am Ende der Zeichenfolge.

Das problem ist, dass dieser regex funktioniert einwandfrei, die kleine Anzahl der Werte. Aber wenn die Zahl der Werte ist zu groß (über 300), wird es zu 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

Und den stacktrace:

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)
    ...

Ich denke, dass die lookahead-Funktion, die in das Muster zu diesem Fehler führen, da es viele lookup-aber ich habe nicht herausgefunden, wie es zu reduzieren oder zu umgehen.

Ich bin wirklich dankbar für jede Anregung da ich keine Erfahrung mit RegEx.

InformationsquelleAutor Genzer | 2013-02-26

7

Vor der Befestigung das problem mit StackOverflowError...
1. Möchte ich darauf hinweisen, dass Ihre aktuelle regex (\d\*?(;(?=\d))?)+ Fehler bei der überprüfung dieser Bedingung.
  
  Jeder Wert kann umfassen ein * am Ende (als Platzhalter für andere matching)
  
  Es nicht ablehnen, den Fall 23*4*4*;34*434*34 gesehen hier¹.
2. Ihre regex tun wird unnötiges backtracking auf einer nicht passenden Eingabe.
3. Java verwendet einen stack-frame für jede Wiederholung der Gruppe (\d\*?(;(?=\d))?) (wiederholt 1 oder mehr Zeit +).
Einen richtigen regex wäre:
```
\d+\*?(?:;\d+\*?)*
```
Beachten Sie, dass dies abzulehnen *, die nicht allzu deutlich von Ihren Anforderungen, ob Sie anzunehmen oder abzulehnen.

Diese nicht beheben StackOverflow problem, da jeder Wiederholung der Gruppe (?:;\d+\*?) ist auch zu verwenden, bis Stapel. Um dies zu beheben, stellen Sie alle Quantoren besitzergreifend, da es keine Notwendigkeit für Rückverfolgung, da die Grammatik ist nicht mehrdeutig:
```
\d++\*?+(?:;\d++\*?+)*+
```
Alles in die string-literal:
```
"\\d++\\*?+(?:;\\d++\\*?+)*+"
```
Ich getestet habe die regex oben mit passenden und nicht passenden Eingang, die mehr als 3600 tokens (getrennt durch ;).

Fußnote

¹: regex101 verwendet PCRE-Variante, die geringfügig von Java-regex-Geschmack. Allerdings sind die Funktionen, die Sie in Ihrem regex sind gemeinsame zwischen Ihnen, so dass sollte es keine Diskrepanz.

Anhang
- Eigentlich von meinen Tests mit deinem regex (\d\*?(;(?=\d))?)+ (das ist falsche entsprechend Ihrer Anforderung), so dass die äußeren + besitzergreifend ++ scheinen fix die StackOverflowError problem, zumindest in meinen Tests mit rund 3600 tokens (getrennt durch ;, der string ist um 20k Zeichen lang). Es scheint auch nicht dazu führen, dass lange Ausführung, Zeit beim Test gegen einen nicht-passenden string.
- In meiner Lösung machen, die * Quantifizierer für die Gruppe (?:;\d+\*?) besitzergreifend ist genug, um zu beheben StackOverflowError.
```
"\\d+\\*?(?:;\\d+\\*?)*+"
```
  Jedoch, ich mache alles besitzergreifend um auf der sicheren Seite.
- Ich kannte die Fälle, die meine ursprüngliche Muster findet, da ich nicht die Fälle in den tests.
- Ich habe vorschlagen, eine richtige regex für Sie.
- Erstaunlich, dein Vorschlag hat Bestand alle meine Prüfungen gerade jetzt, einschließlich der test für StackOverflowError. Ich wusste nicht, über die possessive Zeug. Konnte Sie schlagen alle RegEx-Referenzen, die ich verbessern kann?
- href="http://docs.oracle.com/javase/tutorial/essential/regex/quant.html" >docs.oracle.com/javase/tutorial/essential/regex/quant.html erklärt, über possessive Quantifizierer, aber zu verstehen, müssen Sie verstehen, wie die Zuordnung erfolgt. Wenn das nicht hilft, überprüfen Sie diese: regular-expressions.info/possessive.html . Possessive Quantifizierer ist besonders nützlich, wenn Sie tun, passt nicht erfordern backtracking, wenn Sie schreiben, der normale code.
- Vielen Dank im Voraus.
InformationsquelleAutor nhahtdh
1

Du regexp ist ein wenig ineffektiv und nicht Ihrer Beschreibung entsprechen. Sie haben '\d\*?' - es ist eine Ziffer folowed durch optional *. Dann optional ';(?=\d)' - ';' mit lookahead-stellige. String '1*2*3*' passen Sie regexp, aber nicht deine Beschreibung.
Könnten Sie Folgen regexp. Es entspricht der Eingabe-und ein bisschen mehr iffective.
```
final String TEST_REGEX = "(\\d+\\*?)(?:;\\d+\\*?)+";
```
Wird es den test bestehen, wenn count < 300, aber noch immer nicht für größere Werte.
Benutzen Sie unformatierten string operation wie indexOf und substring zum überprüfen der Eingabe.
- Danke für deine regex. Ja, ich habe gerade entdeckt einige Fehler in meiner regex. Aber das wahre problem ist der StackOverflowError immer noch Auftritt.
InformationsquelleAutor ijrandom
0

Die Sache, möchten Sie vielleicht zu tun ist, erhöhen Sie die maximale Größe Ihres Stacks, damit es nicht überläuft. Sie können nachlesen, wie Sie das hier tun.

Grundsätzlich beginnen Sie Ihr Programm mit der -Xss option. Zum Beispiel -Xss4m Als ich begann, Ihren code mit -Xss4m, dein Programm lief ohne ein stack-overflow für mich (es gibt true).
- Danke für die Anregung. Aber ich wirklich don ' T wollen, passen Sie die JVM-Optionen, aber ich betrachte es als letzten Ausweg.
InformationsquelleAutor Daniel Kaplan

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.