목차
전단을 든 순경은 골목을 하나씩 들어가 본다. 아니면 돌아 나와 다음 골목으로 간다. 정규식 엔진이 하는 일이 딱 그것이다.
엔진은 한 번에 알아보지 않는다
사람은 \d{2,3}-\d{3,4}-\d{4}를 보고 “아, 전화번호” 하고 한눈에 안다. 엔진은 그렇게 못 한다. 엔진이 아는 일은 이 세 가지뿐이다.
- 지금 자리의 글자가 패턴의 지금 조각과 맞나 본다
- 맞으면 둘 다 한 칸 앞으로 간다
- 안 맞으면 실패다
abc라는 패턴이면 이걸로 끝난다. 갈림길이 없으니 맞거나 안 맞거나 둘 중 하나다. 이야기가 시작되는 건 한 조각이 여러 가지로 맞을 수 있을 때다.
막히면 돌아 나온다
\d+는 숫자를 한 자 먹을 수도, 세 자 먹을 수도, 다섯 자 먹을 수도 있다. 엔진은 그중 하나를 고른다. 그런데 고른 값이 뒤에 오는 조각과 어긋나면 어떻게 하나. 고른 자리로 되돌아가 다른 값을 골라 본다.
이것이 백트래킹이다. 골목에 들어갔다 아니면 돌아 나와 다음 골목으로 가는 것과 같은 절차다. 순경이 골목 지도를 미리 보고 정답 골목을 찍는 게 아니듯, 엔진도 어느 값이 맞을지 미리 알지 못한다.
낯선 이름이지만 새로운 발상은 아니다. 후보를 하나씩 다 해보는 방법에 “아니다 싶으면 그 가지를 접는다”를 얹은 것이고, 갈라져 들어갔다 돌아 나오는 구조는 자기를 부르는 함수가 그리는 모양 그대로다.
갈림길은 반복과 선택이 만든다
되돌아갈 일이 생기려면 되돌아갈 자리가 있어야 한다. 갈림길을 만드는 문법은 둘뿐이다.
하나는 반복이다. + * ? {2,5}는 전부 “몇 개를 먹을지”를 엔진이 고르게 한다. 고른다는 건 갈림길이라는 뜻이다.
다른 하나는 선택이다. (고양이|고양)처럼 |로 갈라 놓으면 어느 쪽부터 볼지를 고른다.
그리고 갈림길의 폭은 문자 부류가 정한다. .은 아무 글자나 받으니 고를 수 있는 범위가 넓고, [0-9]는 좁다. 같은 +라도 .+가 \d+보다 훨씬 많은 경우를 만든다. 갈림길이 몇 개이고 각각 몇 갈래냐, 이 두 수가 정규식의 비용을 정한다.
탐욕 - 일단 끝까지 삼킨다
기본 수량자는 탐욕적이다. 탐욕 수량자는 일단 먹을 수 있는 만큼 다 먹고, 뒤가 안 맞으면 한 칸씩 게워 낸다.
패턴 \d+-\d+를 12345에 대 보자. 하이픈이 없으니 이 매칭은 실패한다. 문제는 실패하기까지 하는 일이다.
엔진은 먹은 것을 한 칸씩 게워 내며 다시 맞춰 본다. 그 계단이 끝나면 시작 위치를 옮겨 같은 계단을 또 오른다.
\d+가 다섯 자를 다 먹고 시작했다. -가 필요한데 글자가 끝났으니 한 칸 게워 낸다. 다음 글자는 5, 아니다. 또 게워 낸다. 4, 아니다. 그렇게 다섯 번을 다 실패하고 나서야 시작 위치를 한 칸 옮겨 처음부터 또 해본다.
성공하는 경우에도 이 성질은 그대로 드러난다. <.+>로 <a><b>에서 태그 하나를 뽑으려 하면 <a>가 아니라 <a><b> 전체가 걸린다. .+가 끝까지 삼킨 뒤 마지막 > 하나만 게워 냈기 때문이다. 엔진이 잘못한 게 아니라 그렇게 하라고 적은 것이다.
게으름 - 최소한만 집는다
반대쪽도 있다. 수량자 뒤에 ?를 붙이면 게으른 수량자가 된다. .+?는 최소한만 먹고 시작해서, 뒤가 안 맞으면 한 칸씩 늘린다.
<.+?>로 같은 문자열을 보면 이번엔 <a>가 걸린다. .+?가 a 한 자만 먹고 멈춘 뒤 바로 >를 만났기 때문이다.
여기서 잡고 갈 것이 있다. 탐욕과 게으름은 다른 규칙이 아니라 같은 절차의 반대 방향이다. 탐욕은 최대에서 출발해 줄이고, 게으름은 최소에서 출발해 늘린다. 둘 다 갈림길에서 되돌아가는 절차 위에 있다.
그래서 “게으른 쪽이 빠르다”는 흔한 말은 틀렸다. 찾는 것이 앞에 있으면 게으른 쪽이 빨리 만나고, 뒤에 있으면 탐욕 쪽이 빨리 만난다. 어느 쪽이 유리한지는 패턴이 아니라 데이터가 정한다.
되돌아간 골목을 기억하지 않는다
여기서 전단 비유가 깨진다. 밝혀 두고 가야 한다.
순경은 이미 뒤진 골목을 기억한다. 한 번 들어가 본 골목에는 다시 안 들어간다. 그런데 백트래킹 엔진은 대개 기억하지 않는다. 시작 위치를 한 칸 옮기고 나면 방금 확인한 것을 처음부터 다시 확인한다.
앞의 그림에서 시도 6과 7이 그 자리다. 2345를 먹고 끝에서 막히는 일은 시도 1에서 이미 겪었다. 그런데 엔진은 그걸 모르고 똑같은 실패를 반복한다.
한 번 푼 것을 적어 두고 다시 안 푸는 방법이 있는데도 왜 안 쓰나. 적어 두려면 무엇을 적을지 정해야 하고, 되돌아보기나 조건부 같은 문법이 들어오면 “같은 상태”를 정의하는 일 자체가 어려워진다. 대부분의 엔진은 그 복잡함 대신 단순한 되풀이를 택했다. 그 선택의 청구서가 다음 글의 주제다.
실패가 성공보다 비싸다
절차를 알고 나면 따라 나오는 사실이 하나 있다. 매칭이 성공할 때보다 실패할 때가 훨씬 비싸다.
성공은 하나만 찾으면 끝난다. 맞는 길을 하나 찾는 순간 남은 갈림길은 볼 필요가 없다. 실패는 그렇지 않다. “어떤 길로도 안 되더라”를 말하려면 모든 길을 다 가봐야 한다.
이 비대칭이 실무에서 얄궂게 작동한다. 검증 정규식은 정상 입력에는 성공하고 이상한 입력에는 실패한다. 즉 가장 비싼 경로를 타는 입력은 정상 사용자가 아니라 이상한 값을 넣은 쪽이다. 그리고 이상한 값을 고를 수 있는 사람이 있다.
실무에서: 느린 정규식의 생김새
패턴을 보고 위험한지 알아보는 눈이 붙으면 대부분의 사고를 코드 리뷰에서 막는다. 신호는 몇 개 안 된다.
- 수량자 안에 수량자가 또 있다.
(\d+)+,(\s*\w+)*같은 꼴. 같은 글자를 나누는 방법이 여러 가지가 되어 갈림길이 곱해진다 .*가 한 패턴에 둘 이상 있다. 넓은 문자 부류에 넓은 반복이라 갈림길이 가장 넓다- 앵커가 없는 긴 패턴. 실패할 때마다 시작 위치를 옮겨 처음부터 다시 돈다
- 선택지끼리 겹친다.
(a|ab)+처럼 같은 글자를 두 갈래로 받으면 나누는 방법이 늘어난다
손질하는 법도 정해져 있다.
문자 부류를 좁힌다. 따옴표 안을 잡을 때 ".*" 대신 "[^"]*"라고 적으면 .이 따옴표까지 삼키지 않아 갈림길이 사라진다. 이 한 줄이 대부분의 문제를 없앤다.
앵커를 박는다. ^와 $가 있으면 시작 위치를 옮겨 가며 반복할 일이 없다.
게워 내지 못하게 막는 문법도 있다. 원자 그룹 (?>...)이나 소유 수량자 ++는 한 번 먹은 것을 되돌려 주지 않는다. 되돌아갈 자리 자체를 없애는 것이라 성능이 예측 가능해지지만, 매칭 결과가 달라질 수 있으니 테스트를 갖춘 뒤에 쓴다. 자바·PCRE 계열은 지원하고 자바스크립트 기본 엔진은 지원하지 않는 등 언어별로 갈린다.
확인은 재보면 된다. 입력 길이를 두 배로 늘려 걸린 시간을 잰다. 두 배쯤 되면 정상이고, 네 배가 되면 눈여겨보고, 그보다 크게 뛰면 이미 위험한 패턴이다.
정리
- 엔진은 패턴을 알아보지 않는다. 한 조각씩 대 보고 맞으면 전진, 아니면 실패하는 절차만 있다.
- 여러 가지로 맞을 수 있을 때 갈림길이 생기고, 어긋나면 그 자리로 되돌아가 다른 값을 고른다. 이게 백트래킹이다.
- 갈림길을 만드는 문법은 반복과 선택 둘뿐이고, 갈림길의 폭은 문자 부류가 정한다.
- 탐욕은 최대에서 출발해 줄이고, 게으름은 최소에서 출발해 늘린다. 다른 규칙이 아니라 같은 절차의 반대 방향이다.
- 엔진은 이미 해본 시도를 기억하지 않는다. 시작 위치를 옮기면 같은 실패를 처음부터 되풀이한다.
- 실패가 성공보다 비싸다. 없다는 걸 말하려면 모든 길을 다 가봐야 하기 때문이다.
다음 글은 이 되풀이가 어디까지 커질 수 있는지를 본다. 갈림길이 겹치기 시작하면 경우의 수가 두 배씩 늘어나고, 그때 한 줄짜리 정규식이 서버를 세운다.