[정규표현식] Greedy and lazy quantifiers

Greedy and lazy quantifiers

 

Greedy Search

수량사는 처음 봤을 때 간단해보이지만 사실 굉장히 까다롭다. 'a "witch" and her "broom" is one'이라는 문장에서 시작하는 쌍따옴표부터 기호 안의 단어와 끝나는 쌍따옴표까지 검색하고 싶다. 정규표현식 /".+"/g를 이용하여 검색한다면 검색 결과로 우리가 원하는  "witch"와  "broom"이 아니라 "witch" and her "broom"이 나올 것이다. 그 이유는  정규표현식의 검색 알고리즘을 이해해야 알 수 있다.

 먼저 표현식이 가장 첫번째 글자는 "이다.  정규표현식 엔진은 0번째부터 "를 찾는다. 첫 글자인 a는 "가 아니기 때문에 다음 순서의 글자로 넘어간다. 바로 다음 "를 찾은 뒤, 다음 패턴인 .를 찾는다. .는 다음 줄인 \n을 제외한 모든 문자를 찾는다. .에 수량사 +가 붙었기 때문에 하나 이상의 문자를 찾는데 .와 맞는 모든 문자를 찾는다. "의 다음 문장인 witch" and her "broom" is one는 모두 .+에 부합하므로 문장의 끝까지 찾았다. 문장의 끝인 one까지 왔으나 아직 패턴의 "를 찾지 못했다. 이제 역순으로 "를 찾기 위해 돌아간다. e, n, o의 순서로 다시 문장을 탐색하다가 가장 처음 나오는 broom"의 "를 찾는다. 정규표현식의 패턴에 맞는 내용을 찾았다. 이 방식은 우리가 기대한 결과는 아니지만 정규식 검색 알고리즘의 방식이다. 우리가 원하는 방식으로 찾기 위해서는 Lazy mode를 이용해야 한다.

 

Lazy mode

알고리즘 강의를 들을 때 Greedy Algorithm을 탐욕 알고리즘이라 했는데 그렇다면 탐욕 검색이라도 해도 될 것 같다. 탐욕 검색의 반대 방식은 게으른 방식이다. 탐욕 검색의 경우 .+를 찾을 때 최대한으로 찾아 문장 끝에 도달했다. 게으른 방식은 그 반대로 최소한의 것을 찾는다. 같은 패턴인 .+의 경우 하나 이상의 문자를 의미하므로 하나를 찾은 뒤 그 다음에 "를 검색하는 것이다. 이 때 수량사인 0개와 1개를 의미하는 ?를 이용한다. ?만 쓰는 것은 아니고 다른 수량사의 다음에 붙인다. 이번 정규식의 경우 /.+?/로 표현하는 것이다. 이렇게 표현하면 정규식 검색 엔진이 탐욕 방식이 아니라 게으른 방식으로 검색을 한다. 

 위에서 예로 든 문장을 다시 이용하면 똑같이 a 다음 "를 찾은 뒤, .+를 찾는다. w를 찾고, 그 다음 .+를 계속 찾는 것이 아니라 .+의 다음인 "를 먼저 찾는다. w 다음은 i이므로 다음 순서로 넘어가 .+인지 확인하고 "인지 확인한다. 이렇게 함으로써 우리가 원하는 결과인 "witch"와 "broom"을 찾을 수 있다.