[스크립트] 정규표현식 알아보기(3)

XHTML 태그 <p>와 </p> 쌍과 그 사이의 텍스트에 일치되는 정규식은 다음과 같다. 두 태그 사이의 텍스트에는 다른 태그들이 들어있어도 일치돼야 한다.

 

<p>.*?</p>

정규식 일부분을 특정횟수로 반복하기 위한 정량자들은 대부분 탐욕 정량자다. 말 그대로, 정규식의 나머지 부분을 대조하도록 명령받기 전까지는 탐욕스럽게 가능한 최대 횟수만큼 반복해서 일치를 시도한다. 이런점 때문에 XHTML에 들어있는 태그들의 짝을 맞추기가 어려울 수도 있다. (모든 시작 태그는 종료 태그에 대응되어야 한다.)

 

<p>.*</p>

위 정규식은 원하는 결과를 만들어내지 못한다. 애스터리스크 뒤에 추가 물음표 기호가 없다는 것이 완전한 해결책과의 유일한 차이다. 위 불완전한 정규식에서는 탐욕스런 애스터리스크가 사용된다.

 

대상 텍스트 안의 첫번째 <p> 태그와 일치된 후 정규식 엔진은 <.*>와 만난다. 마침표는 개행문자를 비롯한 모든 문자와 일치된다. 애스터리스크는 그 문자에 0회 이상 반복해서 일치를 시도한다. 애스터리스크의 탐욕스런 성격으로 인해 <.*>는 대상 텍스트 끝까지의 모든 문자와 일치된다. 다시 말해서, <.*>는 첫 단락부터 시작해서 XHTML 파일을 통째로 훑게 된다.

 

<.*> 탐욕스러운 순회가 끝나고, 엔진은 대상 텍스트의 끝에서 <를 대조하지만 이미 끝에 있는 태그까지 모두 집어삼킨 상황이 되어 그 위치에서 일치에 실패한다. 그러나 정규식 엔진은 backtracking한다.

 

애스터리스크는 최대한 많은 텍스트를 집어삼키는 취향이지만, 전혀 일치되는 대상이 없어도 만족한다. 어떤 정량자가 그 정량자의 최소 횟수를 넘어 반복될때마다, 정규식은 역행 위치를 저장한다. 역행 위치란 정량자 뒤에 있는 정규식 일부가 실패할 경우 정규식 엔진이 되돌아갈 수 있는 위치를 뜻한다.

 

<<>이 실패하면 엔진은 <.*>로 하여금 일치부 중 한 문자를 버리게 해서 역행한다. 그 다음 <<>가 파일의 마지막 문자 위치에서 다시 대조된다. 만일 또다시 실패하면 엔진은 한번 더 역행하여 파일 끝에서부터 두번재 문자 위치에서 <<>를 대조한다. 이 과정은 <<>가 성공할 때까지 계속된다. <<>가 끝내 성공하지 못하면 결국 <.*>가 역행 위치 밖에서 실행되고 전체 일치 시도는 실패한다.

 

그러한 역행 도중 <<>가 어느 지점에서 일치되면 </>가 시도된다. 만일 </>가 실패하면 엔진은 다시 역행한다. 이 과정은 </p>가 완전히 일치될 수 있을때까지 반복된다.

 

애스터리스크는 탐욕적인 순회를 하기때문에, 부정확한 정규식이 XHTML 파일에 들어있는 맨앞의 <p>부터 맨뒤의 </p>까지의 전부와 일치돼버린다. XHTML 단락과 정확히 일치되게 하려면 맨 앞의 <p>를 그 뒤에 나오는 맨 앞의 </p>와 짝지어야 한다.

 

이럴때 바로 나태 정량자가 필요해진다. 물음표를 뒤에 붙이면 정량자의 성격이 나태해진다. <*?>,<+?>,<??>,<{7,42}?>는 전부 나태 정량자들이다.

 

나태 정량자도 역행을 하지만 탐욕 정량자와는 방식이 정반대이다. 나태 정량자는 필요한 최소한의 횟수를 반복하고, 하나의 역행 역행 지점을 저장한 후, 정규식을 계속 진행시킨다. 만일 정규식의 나머지 부분이 실패해서 엔진이 역행하면, 나태 정량자는 한번 더 반복한다. 만일 정규식이 역행을 계속하면, 나태 정량자는 최대 반복 횟수까지 확장되거나 반복 중인 정규식 토큰이 일치에 실패할 때까지 확장된다.

 

<<p>.*?</p>>는 XHTML 단락을 정확히 일치시키기 위해 나태 정량자를 사용한다. <p>가 일치되면 나태한 <.*?>는 처음에는 아무것도 하지 않은채로 있는다. <</p>>가 <p>의 바로 뒤에 있으면 빈 단락이 일치되고, 그렇지 않으면 엔진은 <.*?>으로 역행하는데 이것은 한 문자와 일치된다. 그래도 여전히 <</p>>가 실패하면 <.*?>는 다음 문자를 대조한다. 이 과정은 <</p>>가 성공하거나 <.*?>가 확장에 실패할 때까지 계속된다. 마침표는 모든 문자와 일치되므로 <.*?>가 XHTML 파일 끝까지의 모든 문자와 일치될때까지는 실패할 가능성이 없다.

 

정량자 <*>와 <*?>는 똑같은 정규식 일치부를 사용할 수 있다. 다만 일치부에 대한 일치 시도 순서만 다르다. 탐욕 정량자는 제일 긴 유력 일치부를 우선적으로 검색하는 반면, 나태 정량자는 제일 짧은 유력 대조부를 먼저 검색한다.

 

가능하면 최선책은 유력 일치부를 하나만 존재하게 하는 것이다. 일치 숫자에 대한 정규식들은 모두 정량자를 나태하게 만들어도 여전히 같은 숫자들과 일치된다. 그 이유는 정량자가 들어있는 그 정량자가 들어있는 그 정규식들의 일부준과 그 뒤에 오는 부분이 서로 상충하기 때문이다. <\d>는 숫자와 일치되고 <\b>는 그 다음 문자가 숫자나 단음문자가 일때만 <\d> 뒤에서 일치된다.

 

<\d+\b>와 <\d+?\b>가 서로 다른 두 대상 텍스트에 어떤 식으로 동작하는지 비교해 보면 탐욕적 반복과 나태한 반복의 원리를 이해하는데 도움이 될 수 있다. 탐욕 반복과 나태 반복 모두 결과는 같지만, 대상 텍스트를 다른 순서로 검사한다.

 

<\d+\b>를 1234에 사용하면 <\d+>가 전체 숫자와 일치된다. 그 다음에 <\b>가 일치된 후 전체 일치부 발견이 완료된다. <\d+?\b>를 사용하면 <\d+?>가 먼저 1하고만 일치된다. <\b>는 1과 2사이에서 실패한다. <\d+?>는 12까지 확장되므로 <\b>는 실패한다. 이 과정은 <\d+?>가 1234와 일치될때까지 계속된 후 <\b>가 성공한다.

 

대상 텍스트가 1234X라면 첫번째 정규식 <\d+\b>는 이번에도 <\d+>가 1234와 일치된다. 하지만 그 후 <\b>는 실패한다. <\d+>는 123 위치로 역행하고 <\b>가 또 실패한다. 이 과정은 <\d+>가 최소 반복 범위인 1로 역행할 때까지 계속 된후, <\b>가 다시 실패한다. 결국 전체 일치 시도는 실패한다.

 

<\d+?\b>는 1234X에 사용하고 먼저 <\d+?>가 1하고만 일치된다. <\b>는 1과 2 사이에서 실패한다. <\d+?>는 12로 확장되고 <\b>는 또 실패한다. 이 과정은 <\d+?>가 1234와 일치될때까지 계속된 후, <\b>가 또 실패한다. 정규식 엔진은 <\d+?>를 한번더 확장하려고 시도하지만 <\d>는 X와 일치되지 않는다. 결국 전체 일치시도는 실패로 끝난다.

 

<\d+>를 단어 경계 사이에 넣으면, 이 정규식은 반드시 대상 텍스트에 들어있는 모든 숫자와 일치되거나 실패한다. 정량자를 나태하게 만들어도 정규식의 최종 일치 여부는 변함없다. 

 

---

<\b\d+\b>에는 탐욕 정량자가 사용되었으며, <\b\d+?\b>에는 나태 정량자가 사용되었다. 둘다 정수와 일치된다. 대상 텍스트가 같으면 둘 다 똑같은 일치부를 찾아낸다.  이 정규식을 보다 효율화하기 위해, 역행이 전부 제거되도록 할 수 있다.

 

소유 정량자는 탐욕 정량자와 비슷하다. 소유 정량자도 최대 횟수만큼 반복을 시도한다. 다만, 소유 정량자는 역행만이 정규식의 나머지 부분이 일치될 유일한 방법이더라도 역행을 하지 않는다는 점이 다르다. 소유 정량자는 역행 지점을 저장하지 않는다.

 

정량자 뒤에 플러스 기호를 붙이면 그 정량자는 소유욕이 생긴다. 예컨대 <*+>, <++>, <?+>, <{7,24}+>는 전부 소유 정량자이다.

 

탐욕 정량자를 최소단위 그룹으로 묶어도 소유 정량자와 같은 결과를 얻을 수 있다. 정규식 엔진이 최소단위 그룹을 빠져나오는 순간, 그 그룹 안의 정량자와 다자택일에 저장돼 있던 모든 역행 지점이 제거된다. 최소단위 그룹의 문법은 <(?>정규식)>이다. 최소단위 그룹은 기본적으로 비 캡처 그룹이며, 부가적으로 역행을 거부한다. 물음표 기호는 정량자가 아니며, 시작 괄호는 오직 3개의 문자 <(?>>로만 구성된다.

 

정규식 <\b\d++\b>를 123abc 456에 적용하면 <\b>는 대상 텍스트 시작 지점에서 일치되고 <\d++>는 123과 일치된다. 여기까지는 <\b\d+\b>(탐욕)와 차이가 없지만, 그 뒤의 <\b>는 3과 a 사이에서 일치에 실패한다. 

 

소유 정량자는 역행 지점을 아예 지정하지 않는다. 이 정규식에는 다른 정량자나 다자선택이 없기때문에 두번째 단어 경계가 실패하면 시도할 다른 방법이 없다. 정규식 엔진은 1 위치에서 시작되는 일치 시도에 대해 즉시 실패를 선언한다.

 

대개의 스타일에서 <x++>는 <(?>x+)>보다 깔끔해 보이는 구문일 뿐 둘의 기능은 동일하다. 정규식 엔진이 역행 지점을 아예 저장하지 않든지 저장했던 역행 지점을 나중에 삭제하든지 간에, 일치 시도의 최종 결과는 같다. 소유 정량자는 한 개의 정규식 토큰에만 적용되는 반면, 최소단위 그룹은 전체 정규식을 감쌀 수 있다는 점이 다르다.

 

<\w++\d++>와 <(?>\w+\d+)>는 전혀 다르다. <\w++\d++>는 <(?>\w+)(?>\d+)>와 같으며 abc123과 일치되지 않는다. <\w++>는 abc123과 통째로 일치된다. 그런 다음 이 정규식 엔진은 <\d++>를 대상 텍스트 끝에서 대조한다. 뒤에서 일치될 수 있는 문자가 전혀 없으므로 <\d++>는 실패한다. 저장된 역행지점이 없어서 결국 일치 시도는 실패한다.

 

<(?>\w+\d+)>에는 한 최소단위 그룹 안에 탐욕 정량자가 2개 들어있다. 최소단위 그룹 안에서 역행은 정상적으로 수행된다. 역행 지점은 엔진이 그룹 전체를 빠져나오는 순간에만 삭제된다. 대상 텍스트가 abc123이면 <\w+>는 abc123과 일치된다. 탐욕 정량자는 역행 지점을 저장한다. <\d+>가 일치에 실패하면 <\w+>는 한문자를 포기한다. 그 후 <\d+>가 3과 일치된다. 이제 정규식 엔진은 최소단위 그룹을 빠져나옴과 동시에 <\w+>와 <\d+>에 저장했던 역행 지점들을 전부 삭제한다. 정규식의 끝에 도달했으므로 역행 지점을 삭제한다고 해도 전혀 달라질 건 없다.

 

소유 정량자와 최소단위 그룹이 오로지 정규식 최적화 역할만 하는 것은 아니다. 이 둘은 역행 지점 삭제를 통해 정규식이 찾아낸 일치부들을 변경할 수도 있다.

 

---

아래는 한 개의 정규식을 사용하여 완전한 HTML 파일을 대상으로 적절한 포함관계로 구성된 html, head, title, body 태그를 찾아내는 정규식이다. 부적절한 태그로 구성된 HTML 파일과는 일치되지 않아야 한다.

 <html>(?>.*?<head>)(?>.*?<title>)(?>.*?</title>)(?>.*?</head>)(?>.*?<body[^>]*>)(?>.*?</body>).*?</html>

JavaScript와 Python은 최소단위 그룹을 지원하지 않아서, 이 스타일들에서는 불필요한 역행을 제거할 방법이 없다. JavaScript나 Python으로 프로그래밍할때는 각 태그를 하나씩 리터럴 텍스트를 검색하면서, 최종 태그 일치부가 발견되면 대상 텍스트의 나머지 부분에서 다음 태그를 검색하면 이 문제점을 해결할 수 있다.

 

<html>.*?<head>.*?<title>.*?</title>.*?</head>.*?<body[^>]*>.*?</body>.*?</html>

멀쩡한 HTML 파일을 대상으로 정규식을 검사하면 정규식이 제대로 작동된다. '마침표는 개행문자와 일치' 옵션을 설정할 것이므로 <.*?>은 모든 것을 건너뛴다. 나태한 애스터리스크로 인해 이 정규식은 한 번에 한 문자만 진행하면서 매번 다음 태그가 일치될 수 있는지 여부를 검사한다.

 

그러나 이 정규식으로 HTML 태그가 불완전하게 들어있는 대상 텍스트를 처리하면 문제가 생긴다. 대상 텍스트에 </html> 태그가 없다면 최악이다.

 

정규식 엔진이 앞의 모든 태그와 일치된 후 이제 마지막 <.*?>를 확장하는 중이라고 가정하자. <</html>>은 결코 일치될 수 없으므로 <.*?>는 파일 끝가지로 대조 범위를 완전히 확장한다. 더 이상 확장할 수 없으면 <.*?>는 실패한다.

 

하지만 아직 끝난 것이 아니다. 나머지 6개의 <.*?>에는 더 확장할 수 있는 역행 지점이 모두 저장돼 있다. 마지막 <.*?>가 실패하면 그 앞의 <.*?>가 확장하면서 </body>와 점진적으로 일치된다. 그 텍스트는 앞서 정규식에 들어있는 리터럴 <</body>>와 일치된다. 이 <.*?>는 나태 정량자 앞에 마침표밖에 없으므로 파일 끝까지로 범위를 확장한다. 첫번째 <.*?>가 파일 끝에 도달할 때만 정규식 엔진은 실패를 선언한다.

 

이 정규식은 최악의 경우를 고려한 복잡도가 O(n^7), 즉, 대상 텍스트의 길이의 7승이다. 잠재적으로 파일 끝까지로 확장할 가능성이 있는 7개의 나태한 마침표가 존재한다. 그 파일 크기가 두 배이면 정규식은 그 파일이 일치되지 않는지 알아내기 위해 128배의 단계를 거쳐야 할 수도 있다.

 

역행이 지나치게 많으면 정규식 대조에 엄청난 시간이 걸리거나 애플리케이션 충돌이 발생한다. 일부 정규식은 기민해서 그런 과도한 일치 시도를 조기에 종료하지만, 이후에도 그 정규식으로 인해 애플리케이션 성능은 계속 떨어지게 된다.

 

이 해결책은 최소단위 그룹을 사용해서 불필요한 역행을 방지하는 것이다. 

 

사실은 정규식의 두 부분 이상이 하나의 텍스트와 일치될 수 있는 경우를 주목해야 한다. 이럴때 정규식 엔진이 정규식의 그 두 부분 사이에 있는 대상 텍스트를 분할하기 위해 모든 방법을 동원하지 않게 하지 않으려면 최소단위 그룹을 사용해야 할 수도 있다. 전체가 아닌 부분적으로 일치될 수 있는 텍스트가 들어있는 긴 테스트용 대상 텍스트를 가지고 작성한 정규식을 항상 테스트하는 습관을 들여야 한다.