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

패턴을 입력하면 뒤에서 뭐가 도나

a(b|c)*d 라고 입력해. 커튼 뒤에서 정규식 엔진은 패턴을 state machine 으로 컴파일하고, 입력 문자열을 한 글자씩 걸으면서 어느 state 가 active 인지 추적해.

엔진 패밀리는 크게 둘:

NFA (비결정적 유한 오토마타) — Python, JavaScript, Java, .NET, PCRE, Perl 이 사용. 강력함: backreference, lookaround, recursion 지원. 비용: 특정 패턴에서 catastrophic backtracking 발생 가능 (트랙 8 전체가 이거 다룸).

DFA (결정적 유한 오토마타) — grep 기본 모드, ripgrep (RE2 패밀리), Go regexp. 제약: backreference 없음, lookaround 없음. 트레이드오프: linear time 보장, 절대 안 터져.

Backtracking, 슬로우모션으로

NFA 엔진은 한 경로 시도, 실패하면 롤백 후 다른 경로. 패턴 a(b|c)d, 입력 abd:

엔진 위치 0, state "a 기대". a 매칭. 위치 1 로 전진.
state "그룹 안, b 시도". b 매칭. 위치 2 로.
state "그룹 후, d 기대". d 매칭. 끝.

이제 매칭 안 되는 경우 — backtrack 필요한 경우. (a|ab)c, 입력 abc: a 시도, 다음 c — 실패. 그룹 시작으로 backtrack, ab 시도, c — 매칭.

이게 메커니즘 전부. 대부분 시간엔 invisible. 잘못 굴 때 (트랙 3 greedy/lazy, 트랙 8 ReDoS) 이 그림에서부터 디버그 시작해.

Code

Python re.DEBUG 로 backtracking 보기·python

import re
pattern = re.compile(r'(a|ab)c', re.DEBUG)
# 컴파일된 state machine 출력 — 한 번 돌려서 출력 읽어 봐.

DFA vs NFA 실전·bash

# RE2/ripgrep — DFA, backtrack 못함, ReDoS 안 일어남, backref 없음
rg '(a|ab)c' file.txt   # OK
rg '(\w+)\1' file.txt    # ERROR: backreference 미지원

# Python re — NFA, backref 됨, ReDoS 위험
python -c "import re; print(re.findall(r'(\w+)\1', 'abab xyz'))"  # ['ab']

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

패턴을 입력하면 뒤에서 뭐가 도나

Backtracking, 슬로우모션으로

Code

External links

Exercise

Progress

댓글 0