정규식 엔진: 탐욕·게으름·전후방탐색·백트래킹

엔진은 어떻게 찾나

JavaScript 정규식 엔진은 백트래킹(backtracking) 방식이다. 문자열의 각 위치에서 패턴을 왼쪽부터 맞춰 보고, 막히면 직전 선택(수량자가 먹은 개수, 대안 중 어느 쪽)으로 돌아가 다른 선택을 시도한다. 모든 선택이 실패하면 시작 위치를 한 칸 옮긴다.

flowchart TB
  n1["위치 0에서 시도"] --> n2["패턴 요소를 차례로 맞춤"]
  n2 -->|"성공"| n3["결과 반환<br/>(g면 끝 위치부터 다음 검색)"]
  n2 -->|"막힘"| n4["마지막 선택 지점으로 돌아가 다른 경우 시도"]
  n4 -->|"경우가 다 떨어지면"| n5["위치 1에서 다시"]

이 방식 덕분에 역참조·전후방탐색 같은 기능을 쓸 수 있지만, 경우의 수가 폭발하는 패턴에서는 매우 느려진다.

탐욕과 게으름

const s = 'a "witch" and her "broom" is one';
s.match(/".+"/g);    // ['"witch" and her "broom"']  탐욕: 하나로 뭉쳐 버린다
s.match(/".+?"/g);   // ['"witch"', '"broom"']        게으름
s.match(/"[^"]+"/g); // ['"witch"', '"broom"']        제외 세트

모드	문법	동작
탐욕(greedy, 기본)	`+`, `*`, `{n,m}`	최대한 많이 먹는다. 뒤가 안 맞으면 한 글자씩 돌려준다
게으름(lazy)	`+?`, `*?`, `{n,m}?`	최소한만 먹는다. 뒤가 안 맞으면 한 글자씩 더 먹는다

탐욕 ".+"의 흐름은 이렇다. 첫 "를 찾고, .+가 문자열 끝까지 먹는다. 끝에서 "가 없으니 한 글자씩 돌려주다가 마지막 "에서 맞는다. 게으른 ".+?"는 한 글자 먹을 때마다 다음이 "인지 확인하므로 가장 가까운 "에서 멈춘다.

?가 붙은 수량자만 게을러진다. /\d+ \d+?/를 "123 456"에 쓰면 123 4다.
게으름은 「가장 짧은 일치」를 보장하지 않는다. 시작 위치는 여전히 왼쪽부터다.

제외 세트가 더 정확한 이유

게으른 수량자도 뒤가 맞을 때까지 경계를 넘어 계속 먹는다.

const html = '<a href="link1" class="wrong">… <p style="" class="doc">';
html.match(/<a href=".*?" class="doc">/g);    // <a href="link1" class="wrong">… <p style="" class="doc"> 까지 잘못 잡힌다
html.match(/<a href="[^"]*" class="doc">/g);  // null: 정답

[^"]*는 따옴표를 아예 넘지 못하므로 속성 값 하나 안에서만 움직인다. 「구분자가 나올 때까지」는 게으른 .*?보다 제외 세트 [^구분자]*로 쓴다. 백트래킹도 적어 빠르다.

전방탐색과 후방탐색

전후방탐색(lookaround)은 조건만 검사하고 결과에 넣지 않는 폭 0의 검사다.

문법	이름	예	결과
`X(?=Y)`	긍정 전방탐색	`\d+(?=€)` on `30€`	`30`
`X(?!Y)`	부정 전방탐색	`\d+\b(?!€)` on `2개 60€`	`2`
`(?<=Y)X`	긍정 후방탐색	`(?<=\$)\d+` on `$30`	`30`
`(?<!Y)X`	부정 후방탐색	`(?<!\$)\b\d+`	`$` 없는 숫자

조건을 여러 개 이으면 모두 만족해야 한다. ^(?=.*\d)(?=.*[a-z]).{8,}$는 숫자와 소문자를 하나씩 포함한 8자 이상(비밀번호 규칙)이다.
조건 안의 내용을 결과로도 받으려면 안쪽을 괄호로 감싼다. /\d+(?=(€|kr))/의 [1]이 통화 기호다.
후방탐색은 모든 주요 브라우저가 지원하며(Baseline), JavaScript는 다른 많은 언어와 달리 길이가 바뀌는 후방탐색((?<=\$\d*))도 허용한다.
전후방탐색은 「바꾸지 않고 사이에 넣기」에 유용하다. 천 단위 쉼표: '1234567'.replace(/\B(?=(\d{3})+(?!\d))/g, ',') → 1,234,567. 실무에서는 Intl.NumberFormat이 낫다(→ 숫자와 Math).

재앙적 백트래킹(catastrophic backtracking)은 단순해 보이는 정규식이 특정 입력에서 사실상 끝나지 않는 현상이다. 정규식은 메인 스레드에서 돌고 중간에 멈출 수 없으므로 페이지 전체가 굳는다. 서버(Node.js)에서는 요청 하나가 프로세스를 묶어 서비스 거부가 된다. 일부러 이런 입력을 보내는 공격을 ReDoS(정규식 서비스 거부)라 한다.

/^(\d+)*$/.test('0'.repeat(24) + '!');   // 수백 ms. 숫자가 하나 늘 때마다 두 배
/^(\w+\s?)*$/.test('An input string that takes a long time or even makes this regex hang!');

왜 느린가

(\d+)*는 숫자 n개를 \d+ 덩어리 여러 개로 나누는 모든 방법을 시도할 수 있다. 123456789를 (123456789), (12345678)(9), (1234567)(89), (1234567)(8)(9)… 로 쪼개는 경우는 약 2ⁿ⁻¹가지다. 끝의 ! 때문에 결국 실패하므로 엔진은 실패를 확인하려고 모든 경우를 다 돈다. 성공하는 입력에서는 첫 시도에 끝나서 테스트에서 드러나지 않는다.

원인은 같은 글자를 두 수량자가 나눠 먹을 수 있는 구조다. 중첩 수량자 (a+)+, (\w+\s?)*, 겹치는 대안 (a|a)*, (\w|\d)+가 대표적이다.
게으른 수량자로 바꿔도 소용없다. 시도 순서만 바뀌고 경우의 수는 같다.

고치는 법

방법	예	원리
경우의 수를 줄인다	`^(\w+\s?)$` → `^(\w+\s)\w*$`	단어마다 공백이 반드시 따라와야 해서 한 단어를 여러 `\w+`로 쪼갤 수 없다
겹침을 없앤다	`(\d+)` → `\d`	같은 뜻을 중첩 없이 쓴다
원자 그룹을 흉내 낸다	`\w+` → `(?=(\w+))\1`	전방탐색 안에서 최대로 잡은 뒤 역참조로 통째 소비한다. 전방탐색은 한 번 끝나면 백트래킹으로 다시 열리지 않으므로 단어를 돌려주며 쪼개지 못한다
입력을 제한한다	길이 상한, 정규식 전에 간단한 검사	최악의 경우 자체를 막는다
정규식을 쓰지 않는다	`split`, `includes`, 파서	구조가 있는 데이터(HTML, JSON, 이메일 전체 규칙)는 전용 파서로

/^((?=(\w+))\2\s?)*$/.test(longInput);                  // 바로 false
/^((?=(?<word>\w+))\k<word>\s?)*$/.test(longInput);     // 명명된 그룹으로 쓰면 읽기 쉽다

JavaScript에는 다른 언어의 소유 수량자(\w++)·원자 그룹((?>…))이 없어 이 전방탐색 기법을 쓴다. 사용자 입력으로 패턴 자체를 만들 때는 RegExp.escape()로 이스케이프한다(RegExp.escape). 서버에서 신뢰할 수 없는 패턴을 실행해야 하면 선형 시간을 보장하는 RE2 계열 엔진(백트래킹 없음, 대신 역참조·전후방탐색 미지원)을 쓴다.

정리

엔진은 왼쪽부터 맞추고, 막히면 직전 선택으로 돌아간다.
탐욕은 최대한, 게으름은 최소한 먹는다. 구분자까지 읽기는 제외 세트 [^"]*가 가장 정확하고 빠르다.
전후방탐색은 결과에 넣지 않는 조건이며, 여러 개를 이어 AND 조건을 만든다.
같은 글자를 여러 방식으로 나눠 먹을 수 있는 중첩·겹침 수량자는 실패할 때 지수 시간이 걸린다.
경우의 수를 줄이거나 (?=(\w+))\1로 백트래킹을 막고, 신뢰할 수 없는 입력에는 길이 제한과 이스케이프를 건다.

버그 제보