My regex is causing a stack overflow in Java; what am I missing?

Question

I am attempting to use a regular expression with Scanner to match a string from a file. The regex works with all of the contents of the file except for this line:

DNA="ITTTAITATIATYAAAYIYI[....]ITYTYITTIYAIAIYIT"

in the actual file, the ellipsis represents several thousand more characters.

When the loop that reads the file arrives on the line containing the bases, a stack overflow error occurs.

Here is the loop:

while (scanFile.hasNextLine()) {
   final String currentLine = scanFile.findInLine(".*");
   System.out.println("trying to match '" + currentLine + "'");
   Scanner internalScanner = new Scanner(currentLine);
   String matchResult = internalScanner.findInLine(Constants.ANIMAL_INFO_REGEX);
   assert matchResult != null : "there's no reason not to find a match"; 
   matches.put(internalScanner.match().group(1), internalScanner.match().group(2));
   scanFile.nextLine();
  }

and the regex:

static final String ANIMAL_INFO_REGEX = "([a-zA-Z]+) *= *\"(([a-zA-Z_.]| |\\.)+)";

Here's the failure trace:

java.lang.StackOverflowError
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3360)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4131)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4312)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3362)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4131)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4312)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3362)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4131)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4312)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
    ...etc (it's all regex).

Thanks so much!

I can see that it causes you to get an stackoverflow... :P~

Garis M Suero
– Garis M Suero

2010-09-10 03:13:24 +00:00
Commented Sep 10, 2010 at 3:13 — Garis M Suero
– Garis M Suero, Commented Sep 10, 2010 at 3:13

Community · Accepted Answer · 2023-11-10 19:48:45Z

4

This looks like bug 5050507 . I agree with Asaph that removing the alternation should help; the bug specifically says "Avoid alternation whenever possible". I think you can go probably even simpler:

"^([a-zA-Z]+) *= *\"([^\"]+)"

edited Nov 10, 2023 at 19:48

CommunityBot

11 silver badge

answered Sep 10, 2010 at 2:43

Matthew Flaschen

286k53 gold badges523 silver badges554 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Alan Moore Over a year ago

+1, but I want to emphasize that the bug report is bogus. The remarks in the Evaluation apply to any regex-directed (or NFA) regex engine, not just Java's. (That includes Perl, Python, PHP, .NET, JavaScript, and many others.)

Asaph · Accepted Answer · 2010-09-10 02:40:03Z

3

Try this simplified version of your regex that removes some unnecessary | operators (which might have been causing the regex engine to do a lot of branching) and includes beginning and end of line anchors.

static final String ANIMAL_INFO_REGEX = "^([a-zA-Z]+) *= *\"([a-zA-Z_. ]+)\"$";

answered Sep 10, 2010 at 2:40

Asaph

163k25 gold badges204 silver badges204 bronze badges

Comments

Zac Thompson · Accepted Answer · 2010-09-10 03:06:11Z

2

read this to understand the problem: http://www.regular-expressions.info/catastrophic.html ... and then use one of the other suggestions

answered Sep 10, 2010 at 3:06

Zac Thompson

12.8k48 silver badges59 bronze badges

Comments

Alan Moore · Accepted Answer · 2010-09-10 06:57:16Z

As the others have said, your regex is much less efficient than it should be. I'd take it a step further and use possessive quantifiers:

"^([a-zA-Z]++) *+= *+\"([^\"]++)\"$"

But the way you're using the Scanner doesn't make much sense, either. There's no need to use findInLine(".*") to read the line; that's what nextLine() does. And you don't need to create another Scanner to apply your regex; just use a Matcher.

static final Pattern ANIMAL_INFO_PATTERN = 
    Pattern.compile("^([a-zA-Z]++) *+= *+\"([^\"]++)\"$");

...

  Matcher lineMatcher = ANIMAL_INFO_PATTERN.matcher("");
  while (scanFile.hasNextLine()) {
    String currentLine = scanFile.nextLine();
    if (lineMatcher.reset(currentLine).matches()) {
      matches.put(lineMatcher.group(1), lineMatcher.group(2));
    }
  }

Collectives™ on Stack Overflow

My regex is causing a stack overflow in Java; what am I missing?

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related