Java Regex 정규표현식 사용시 java.lang.StackOverflowError 가 발생하는걸까

java.lang.StackOverflowError 발생 장면

 

 자바에서 정규표현식을 활용하다보면, BuiltIn 클래스인 Pattern 과 Matcher 이 두 가지를 사용하는 경우가 많다.

Pattern 과 Matcher 을 사용할 때 주의해야될 점이 있다. 바로 재귀로 인해 무한한 루프에 빠질 수 있다는 것이다. 이로인해 위에서 말하 StackOverflowError 가 발생한다.

public class RegexTest {
    public static void main(String[] args) {
        // 재귀적으로 일치하는 패턴
        Pattern pattern = Pattern.compile("(a|b)*c");
        Matcher matcher = pattern.matcher("aaa" +
                "aaa");
        System.out.println(matcher.matches()); // StackOverflowError 발생
    }
}

 

위 코드를 실행시키면 StackoverflowError 발생한다. 패턴에 맞는 값이 계속 등장하기 때문에 재귀를 타게되면서 문제가 발생한다.

재귀를 일으키지 않기 위해서는 정규표현식의 내역을 변경해야한다. a*c 으로 변경하면 문제를 해결할 수 있다. 

그럼 어떻게 해결해야 될까?

1. 정규식 패턴을 단순화한다: 정규식 패턴에서 불필요한 복잡성을 제거한다.
2. 게으른 양자화기 사용: 정규식 패턴에 중첩 양자화기가 있는 경우 게으른 양자화기 대신 탐욕스러운 양자화기를 사용하기. 예를 들어, 모든 문자를 게으르게 0회 이상 일치시키려면 .*? 대신 .*을 사용하기
3. 스택 크기를 늘리기: 여전히 'StackOverflowError'가 발생하는 경우, Java 프로그램에 할당된 스택 크기를 늘리기 위해 -Xss 명령줄 옵션을 사용할 수 있다. 예를 들어, 다음 명령을 사용하여 스택 크기를 1MB로 늘릴 수 있다: java -Xss1m MyClass.
4. 다른 정규식 라이브러리 사용: 위의 모든 해결책이 작동하지 않으면, 'java.util.regex' 라이브러리와 같이 스택 오버플로 오류에 덜 민감한 다른 정규식 라이브러리를 사용해야 한다.

 

그럼 왜 자바에서만 이런 문제가 발생하는걸까?

 String 클래스에 replaceAll() 에서도 같은 문제가 발생할 수 있는데, 그 이유는 바로 Pattern 과 Matcher 에 대한 이해가 필요하다. Matcher 클래스는 주어진 문자열을 패턴과 일치시키려고 시도합니다. 패턴이 문자열과 정확히 일치하면 'true' 를 반환하고, 일치하지 않으면 'false'를 반환합니다.

 조금더 구체적으로 이야기해보자. Matcher 에는 크게 2가지의 메서드가 있다.  Matcher.matches() 와 Matcher.find() 두 개의 메서드 모두 Matcher 클래스에서 설명한대로 주어진 문자열을 패턴과 일치시키려는 시도를 하는데, matches() 는 전체 문자열에서 정규표현식이 일치하는지 살펴본다면, find() 는 주어진 문자열에서 패턴과 일치하는 부분을 찾습니다. 패턴이 문자열의 일부분에만 일치해도 검색을 중지하지 않습니다.

결론적으로, 자바에서는 Matcher가 정규표현식과 일치하는 문자열을 찾기 위해 시도하게 되는데, 위 코드에서 (a|b) 를 재귀적으로 일치하는 문자열에서 찾게 되므로 이때 StackOverflowError 가 발생하게 됩니다.

이 패턴은 재귀적으로 일치하므로, 문자열이 a로만 구성되어 있을 경우, 스택 오버플로 오류가 발생합니다.

재귀적으로 일치하는 문자열 이란?
하위 패턴이 다시 자신과 일치할 수 있다는 것을 의미합니다.
(abc|def)* 라고 한다면, abc 또는 def 가 0번이상 반복되는 문자열과 일치한다는 것을 의미하는데, 이때 주어진 문자열이 abcabcabcabc 또는  defdefdefdef 와 같은 문자열과 일치하게 되는데, 이러한 문자열은 하위 패턴이 자신과 일치하므로, 재귀적으로 일치하는 문자열이라 말할 수 있다.

 일반적으로 괄호를 사용하여 그룹화하게 되는데, 그룹화된 하위패턴이 자신과 일치하는 경우, 해당 하위패턴은 그룹화된 전체 패턴과 일치하게 된다. 이를 통해 재귀적으로 일치하는 문자열을 생성한다.