정규식 엔진은 실제로 어떻게 동작하나

패턴을 입력하면 뒤에서 뭐가 돌까

a(b|c)*d라고 입력해 봐. 정규식 엔진은 커튼 뒤에서 패턴을 상태 기계로 컴파일하고, 입력 문자열을 한 글자씩 따라가며 어느 상태가 활성화됐는지 추적해.

여기서 알아둘 엔진 계열은 크게 둘이야.

백트래킹 엔진. Python re, JavaScript, Java, .NET, PCRE, Perl 등이 이 계열이야. 선택 경로를 저장했다가 실패하면 되돌아가서 다른 길을 시도해. 역참조와 전후방 탐색 지원 범위는 엔진마다 다르고, 재귀는 PCRE·Perl과 일부 별도 엔진만 지원해. 모호한 패턴에서는 파국적 백트래킹이 생길 수 있어. 트랙 8에서 자세히 다룰 거야.

선형 시간 유한 오토마타 계열. RE2, Go regexp, ripgrep의 기본 Rust regex 엔진은 구현 방식은 서로 다르지만 입력 길이에 비례해 끝나도록 기능을 제한해. 기본적으로 역참조와 전후방 탐색을 지원하지 않는 대신 ReDoS 위험을 크게 줄이지. ripgrep은 --pcre2를 켜면 별도의 백트래킹 엔진을 사용해.

백트래킹을 느리게 돌려보기

백트래킹 엔진은 한 경로를 시도하고, 실패하면 이전 분기점으로 돌아가 다른 경로를 시도해. 패턴 a(b|c)d와 입력 abd를 따라가 보자.

위치 0에서 a를 기대해. a가 맞으니 위치 1로 전진해.
그룹 안에서 먼저 b를 시도해. 맞으니 위치 2로 전진해.
그룹 뒤에서 d를 기대해. 이것도 맞으니 매칭이 끝나.

이번에는 백트래킹이 필요한 경우를 보자. 패턴은 (a|ab)c, 입력은 abc야. 엔진이 먼저 a를 택하면 다음 c에서 실패해. 그러면 그룹 시작으로 돌아가 ab를 택하고, 마지막 c까지 매칭해.

메커니즘은 이게 전부야. 평소에는 눈에 보이지 않지만 패턴이 잘못 굴 때는 이 그림에서 디버깅을 시작해. 트랙 3의 탐욕적·게으른 수량자와 트랙 8의 ReDoS도 같은 기계 위에서 움직여.

Code

Python re.DEBUG로 컴파일된 패턴 구조 보기·python

import re
pattern = re.compile(r'(a|ab)c', re.DEBUG)
# 컴파일된 상태 기계가 출력돼. 한 번 돌려서 읽어봐.

선형 시간 계열과 백트래킹 계열·bash

# ripgrep 기본 엔진 — 선형 시간을 지키며 역참조를 지원하지 않음
rg '(a|ab)c' file.txt       # OK
rg '(\w+)\1' file.txt    # ERROR: 역참조 미지원

# Python re — 역참조를 지원하는 백트래킹 엔진
python -c "import re; print(re.findall(r'(\w+)\1', 'abab xyz'))"  # ['ab']

Exercise

Python REPL에서 import re를 실행한 뒤 re.compile(r'(a|ab)c', re.DEBUG)를 실행하고 출력을 읽어 봐. 한 줄씩 다 이해하려 하지 말고 컴파일된 명령과 분기 구조를 보여주는 출력이라는 것만 확인해. 실제 실행 중 백트래킹 경로를 추적하는 도구는 아니라는 점도 기억해.

패턴을 입력하면 뒤에서 뭐가 돌까

백트래킹을 느리게 돌려보기

Code

External links

Exercise

Progress

댓글 0