[정규표현식] .*? 패턴의 의미

 

정규표현식을 어느 정도 다루어본 사람이라면 .* 패턴의 의미를 쉽게 알 수 있다. 하지만 .*? 패턴은 쉽게 해석되지 않는다. .* 패턴이 줄바꿈 문자를 제외한 문자를 최대한 매칭하는 패턴이고, ?는 {0, 1}에 해당하는 수량한정자(quantifier)인데 .*와 ? 기호가 결합되어 어떤 역할을 하는지 추론하기 어렵다.

 

결론부터 이야기하자면 '*' quantifier 뒤에 위치하는 ? 기호는 {0, 1}을 의미하는 quantifier가 아니다. 이 조건에서 ?는 앞에 위치한 quantifer의 성질을 변경시켜주는 지시자 역할을 한다. 

 

· Backtracking
Quantifier의 종류를 살펴보기 앞서 먼저 backtracking에 대해 살펴볼 필요가 있다. Backtracking은 quantifier를 가진 패턴에 의해 매칭된 문자열 집합이 문자 하나를 내어놓거나(backward backtracking), 하나를  가져가는(forward backtracking) 행동이다.

Backward backtracking은 greedy quantifier를 포함한 패턴에서 일어나며, forward backtracking은 reluctant quantifier를 포함한 패턴에서 일어난다. 어떤 패턴이 왜 어떤 종류의 backtracking 활동을 하는지는 패턴의 종류를 보면 쉽게 알 수 있다. 이제 아래 greedy, reluctant, 그리고 possesive quantifier를 살펴보자.

 

· Greedy quantifier
Greedy quntifier는 조건을 만족하는 최대한 많은 문자들을 가져온다(=매칭시킨다). 아래 예를 보자.

예) pat = .*foo
str = xfooxxxxxxfoo

.*는 str의 모든 문자를 가져온다. 더 이상 남은 문자들은 없다. 이 상태에서 .*뒤에 이어지는 f 문자를 찾기위해 .*문자가 가져온(매칭한) 문자열 중 맨 마지만 문자를 하나 내어놓는다. 즉, (backward) backtracking이 일어난다. 하지만 내어놓은 문자 'o'는 f와 매칭되지 않는다. 매칭을 조사하는 프로그램은 다시 .*가 매칭한 문자열로부터 o를 하나 더 꺼내지만 역시 매칭이 일어나지 않는다. 매칭을 조사하는 프로그램이 .*가 매칭한 문자열에서 뒤로 부터 o, o, f 즉 foo를 꺼내고 나면 패턴에 기술된 foo를 찾을 수 있게된다. 결과적으로 xfooxxxxxxfoo를 찾게되지만 그 과정은 앞서 서술한 greedy 매칭과 backtracking 과정을 통해서 이루어진것이다.

· Reluctant quantifier
예) pat = .*?foo
str = xfooxxxxxxfoo

위 예의 경우 .*뒤에 위치한 ?를 {0, 1}로 보아서는 안된다. 여기서 '*' quantifier 뒤에 위치하는 ? 기호는 '*' quantifier를 reluctant quantifier(try smallest matching)로 만들어주는 역할을 한다. 즉 *?를 하나의 quantifier로 보아야한다.

다시 예로 돌아가면 .*?는 대상 str의 어떤 것과도 매치하려고 하지 않는다. 이 상태에서 남은 문자열의 첫 글자를 보면 x이고 .*?뒤에 이어진 foo의 첫 글자인 'f'와 매칭되지 않는다. 매칭을 조사하는 프로그램은 .*? 매칭 조건에 따라 한 글자를 가져온다. 즉 (forward) backtracking이 발생한다. 이제 남은 문자열을 보면 'f', 'o', 'o'를 순차적으로 찾을 수 있다. 결과적으로 xfoo를 매칭 결과로 얻게된다. 그리고 xfoo는 앞서 서술한 reluctant 매칭과 backtracking 과정을 통해 얻어지게 된 것이다.

· Possesive quantifier
앞 서 살펴본 ?기호가 어떤 quantifier를 reluctant quantifer로 만들어 준다면 +기호는 앞에 위치하는 quantifier를 possesive quantifier로 만들어준다. Possesive quantifier는 backtracking을 하지 않는 즉, 소유만 하고 내어놓지 않는 greedy quantifier이다. 다시 예를 통해 살펴보자.

예) pat = .*+foo
str = xfooxxxxxxfoo

.*+ 조건은 str의 모든 문자를 가져간다. 하지만 backtracking을 하지 않기 때문에 .*+뒤에 이어지는 foo와 매칭할 문자가 남아있지 않다. 따라서 xfooxxxxxxfoo 문자열에서는 .*+foo 패턴과 매칭되는 문자를 찾을 수 없게된다.

[출처: https://stackoverflow.com/questions/5319840/greedy-vs-reluctant-vs-possessive-qualifiers]

 

---

Possesive quantifier는 잘 쓰이지 않는다. 따라서 사용하는 정규 표현식 라이브러리에 따라 구현이 안 되어 있는 경우도 있다.

정리하면 아래와 같다.
· Greedy quantifier .*: 조건을 만족하고 최대한 많은 수의 문자를 포함하고 있는 문자열을 찾는다.
· Reluctant quantifier .*?: 조건을 만족하고 최소한의 문자들로 이루어진 문자열을 찾는다.