정규 표현식

Regular expression; 정규 표현식, 정규식, regex, regexp

문자열의 집합을 몇 가지 기호로 적어 검색, 검증, 추출, 치환에 쓰는 패턴 표기법

정규 표현식은 "숫자 세 자리 뒤에 하이픈", "영문 소문자로만 된 단어"처럼 문자열이 따라야 할 모양을 짧은 패턴으로 적는 방법이다. 수학자 스티븐 클리니(Stephen Cole Kleene)가 1951년 정규 언어를 기술하려고 만든 표기에서 출발했고, 1968년 켄 톰슨(Ken Thompson)이 텍스트 편집기에 넣으면서 프로그래밍 도구가 되었다. 지금은 grep, sed, awk 같은 유닉스 명령, 거의 모든 프로그래밍 언어의 표준 라이브러리, 텍스트 편집기와 IDE의 찾기·바꾸기, 데이터베이스의 문자열 함수, 웹 방화벽의 탐지 규칙, 컴파일러의 어휘 분석기에 두루 쓰인다.

이론에서 말하는 정규 표현식은 유한 오토마타와 표현력이 같은 형식 언어다. 반면 Perl 이후의 실무 엔진은 역참조, 전후방 탐색 같은 기능을 더해 정규 언어의 범위를 넘어섰다. 그래서 둘을 구분할 때 실무 쪽을 regex 또는 패턴이라고 부르기도 한다. 엔진마다 문법이 조금씩 다르고(방언), 구현 방식에 따라 최악의 경우 실행 시간이 입력 길이에 지수적으로 늘어 서비스 거부 공격의 원인이 되기도 한다.

기본 개념

정규 표현식은 대상 문자열에서 패턴과 일치하는 부분(매치)을 찾는다. 패턴은 다음 요소로 이루어진다.

• 리터럴: a, 7, 가처럼 그 문자 자체와 일치하는 문자
• 메타문자: . ^ $ * + ? ( ) [ ] { } | \처럼 특별한 뜻을 가진 문자. 문자 그대로 찾으려면 앞에 \를 붙여 이스케이프한다(\.은 마침표 자체).
• 세 가지 기본 연산: 이어 붙이기(연결, ab), 선택(a|b), 0회 이상 반복(클리니 스타, a*). 나머지 문법은 이 셋을 줄여 쓴 것이다. 예를 들어 a+는 aa*, a?는 "a 또는 빈 문자열"과 같다.
• 우선순위: 반복 > 연결 > 선택. ab*는 a, ab, abb와 일치하고 abab와는 일치하지 않는다. ab 전체를 반복하려면 (ab)*처럼 괄호로 묶는다. 같은 이유로 ^cat|dog$는 "cat으로 시작하거나 dog로 끝나는" 뜻이 되므로 한 단어만 허용하려면 ^(cat|dog)$로 쓴다.
• 수량자는 바로 앞의 원자 하나에만 붙는다. abc+는 abcc, abccc와 일치하고, abc 전체의 반복은 (abc)+다.

패턴은 대상의 일부와 일치하면 매치로 친다. 문자열 전체가 패턴과 같아야 한다면 ^와 $로 양끝을 고정하거나 언어가 제공하는 전체 일치 함수(Python re.fullmatch, Java matches())를 쓴다. 예를 들어 [0-9]+$는 "숫자로 끝나는" 문자열을 찾을 뿐이어서 a123도 뒷부분 123이 매치된다. "숫자로만 된 문자열"은 ^[0-9]+$이다.

형식 언어 이론

정의

알파벳(문자 집합) Σ 위의 정규 표현식은 다음 규칙으로 귀납적으로 정의된다.

• ∅는 아무 문자열도 나타내지 않는다. ε는 빈 문자열 하나를 나타낸다. Σ의 문자 a는 문자열 "a" 하나를 나타낸다.
• R과 S가 정규 표현식이면 R|S(합집합), RS(연결), R*(0회 이상 반복)도 정규 표현식이다.

정규 표현식이 나타내는 언어를 정규 언어라고 한다. 정규 언어는 유한 오토마타가 인식하는 언어와 정확히 같다(클리니 정리). 촘스키 위계에서는 가장 안쪽의 3형 언어이고 정규 문법(우선형 또는 좌선형 문법)으로 생성된다. 정규 표현식이라는 표기 자체의 문법은 괄호 짝을 맞춰야 하므로 정규 언어가 아니라 문맥 자유 언어다.

오토마타와의 변환

• 정규 표현식 → NFA: 톰슨 구성법(Thompson's construction). 패턴 길이에 비례하는 크기의 비결정적 유한 오토마타(NFA)가 나온다.
• NFA → DFA: 부분집합 구성법. 상태 수가 최악의 경우 지수적으로 늘어난다. 예를 들어 "끝에서 k번째 글자가 a"인 문자열의 언어는 (a|b)*a(a|b)(a|b)...처럼 길이가 k에 비례하는 식으로 쓸 수 있지만, 이를 인식하는 DFA는 상태가 최소 2^k개 필요하다.
• 오토마타 → 정규 표현식: 클리니 알고리즘, 상태 제거법.
• 두 정규 표현식이 같은 언어를 나타내는지는 각각을 최소 DFA로 바꿔 비교하면 판정할 수 있다.
• 반대로 DFA로는 간단하지만 식으로 쓰면 거대해지는 언어도 있다. 11로 나눈 나머지를 따지는 ISBN 검사는 상태 11개짜리 DFA로 되지만 정규 표현식으로 바꾸면 수 MB 크기가 된다.

표현력의 한계

정규 언어는 유한한 상태만 기억할 수 있으므로 임의 깊이로 중첩된 괄호의 짝 맞추기, aⁿbⁿ(a와 b의 개수가 같음) 같은 언어를 나타낼 수 없다. 이는 펌핑 보조정리로 증명된다. 괄호 짝을 맞추려면 적어도 푸시다운 오토마타(문맥 자유 언어)가 필요하다. 깊이가 정해진 괄호는 경우를 모두 나열하면 쓸 수 있다. HTML, JSON, 프로그래밍 언어 소스처럼 중첩 구조가 있는 형식을 정규 표현식만으로 제대로 파싱할 수 없는 이유가 이것이다. 실무에서는 정규 표현식으로 토큰을 자르고(어휘 분석), 구조는 파서가 맡는다.

실무 엔진이 정규 언어를 넘는 부분

역참조를 쓰면 정규 언어가 아닌 언어도 나타낼 수 있다. (.+)\1은 papa, WikiWiki처럼 같은 문자열이 두 번 반복된 문자열(제곱 언어)과 일치하는데, 이 언어는 정규 언어도 문맥 자유 언어도 아니다. 역참조가 임의 개수 있는 패턴의 매칭 문제는 NP-완전이다. 이 때문에 역참조를 지원하는 엔진은 백트래킹을 쓸 수밖에 없다. Perl의 재귀 패턴 (?R)이나 .NET의 균형 그룹은 괄호 짝 맞추기까지 할 수 있다. PCRE로 소수가 아닌 길이의 1 문자열만 고르는 ^1?$|^(11+?)\1+$ 같은 "합성수 판별" 패턴이 알려져 있는 것도 역참조 덕분이다. 반대로 전후방 탐색 중 일부는 정규 언어 안에서 흉내 낼 수 있다. Perl을 만든 래리 월(Larry Wall)은 이런 확장된 패턴이 진짜 정규 표현식과는 거의 관계가 없다며 regex라는 말을 쓰겠다고 했다.

역사

연도	사건
1951	클리니가 RAND 연구 메모 RM-704 "Representation of Events in Nerve Nets and Finite Automata"에서 정규 사건(regular events)을 정의했다. 매컬러-피츠 신경망이 반응할 수 있는 사건을 기술하려는 연구였다. 1956년 논문집 Automata Studies에 실려 널리 알려졌다.
1968	켄 톰슨이 Communications of the ACM 11권 6호에 "Regular Expression Search Algorithm"을 발표했다. 정규 표현식을 NFA로 바꿔 여러 상태를 동시에 따라가는 방법(톰슨 NFA)이다. 톰슨은 이 방법을 CTSS(IBM 7094) 위의 편집기 QED에 넣었고, 속도를 위해 패턴을 기계어로 컴파일했다. 초기 JIT 컴파일의 예로 꼽힌다. 같은 해 컴파일러의 어휘 분석에 정규 표현식을 쓰는 연구도 나왔다.
1970년대	톰슨이 유닉스 편집기 ed에 정규 표현식을 넣었고, ed의 명령 g/re/p(전역으로 정규식을 찾아 출력)를 떼어 낸 것이 grep이다. ed와 초기 grep은 톰슨 NFA 대신 단순한 재귀 백트래킹을 썼다. 이후 벨 연구소에서 lex, sed, awk, expr가 나왔고 vi와 Emacs도 각자의 문법을 갖췄다.
1986	헨리 스펜서(Henry Spencer)가 백트래킹 방식의 정규 표현식 라이브러리를 새로 작성해 공개했다. 이 라이브러리가 Perl, PCRE, Python 등 이후 엔진의 바탕이 되었다. 스펜서는 나중에 Tcl용으로 NFA/DFA 혼합 엔진(Advanced Regular Expressions)도 만들었고, PostgreSQL이 이를 쓴다.
1987~1997	Perl이 스펜서의 라이브러리를 바탕으로 문법을 크게 확장했다. Perl 5(1994)에서 전방 탐색 (?=...), 비캡처 그룹, 게으른 수량자가 들어갔고, 후방 탐색 (?<=...)은 1997년 Perl 5.005 개발 중에 추가되었다. Java, JavaScript, Python, .NET 등 대부분의 언어가 Perl 문법을 따라갔다.
1992	POSIX.2가 유닉스 도구의 문법을 기본 정규 표현식(BRE)과 확장 정규 표현식(ERE)으로 표준화했다.
1997	필립 헤이즐(Philip Hazel)이 메일 서버 Exim용으로 PCRE(Perl Compatible Regular Expressions)를 공개했다. PHP, Apache, Nginx, Postfix, Nmap 등이 쓴다. 2015년 API를 바꾼 PCRE2가 나왔고 구 PCRE는 8.45를 끝으로 지원이 끝났다.
2006~2010	러스 콕스(Russ Cox)가 구글 코드 검색을 만들면서, 누구나 넣을 수 있는 패턴을 PCRE로 처리하면 서비스 거부 공격에 약하다고 보고 선형 시간 엔진 RE2를 작성했다. RE2는 2010년 3월 오픈 소스로 공개되었다. Go의 regexp 패키지와 Rust의 regex 크레이트도 같은 방식이다.
2015~2024	ECMAScript가 u·y 플래그(ES2015), 후방 탐색·명명 그룹·s 플래그·유니코드 속성(ES2018), d 플래그(ES2022), v 플래그(ES2024)를 추가했다. .NET 7(2022)이 선형 시간 모드 RegexOptions.NonBacktracking을, Python 3.11(2022)이 소유 수량자와 원자 그룹을 추가했다. IETF는 2023년 10월 여러 엔진에서 같은 결과를 내는 최소 부분집합 I-Regexp(RFC 9485)를 발표했다. POSIX.1-2024는 ERE에 최소 일치 수정자 ?(예: *?)를 넣었다.

정규 표현식 이전의 검색 도구는 대개 *(임의 문자열), ?(임의 한 글자) 정도의 와일드카드만 지원했다. 그 흔적이 파일 이름 글롭(*.txt)과 SQL의 LIKE(%, _)에 남아 있다. 글롭의 *는 정규 표현식의 .*에 해당하므로 둘을 섞어 쓰면 안 된다.

문법

아래는 Perl 계열(PCRE, JavaScript, Python, Java, .NET) 공통 문법을 기준으로 하고, 차이는 방언 비교 절에 정리한다.

메타문자

기호	뜻	예
.	줄바꿈을 뺀 아무 문자 하나(s 플래그를 켜면 줄바꿈 포함)	a.c → abc, a1c
^	문자열의 시작(m 플래그면 줄의 시작)	^Hello
$	문자열의 끝(m 플래그면 줄의 끝)	\.txt$
*	앞 원자 0회 이상	ab* → a, ab, abbb
+	앞 원자 1회 이상	[0-9]+
?	앞 원자 0회 또는 1회	colou?r → color, colour
{n}, {n,}, {n,m}	정확히 n회, n회 이상, n회 이상 m회 이하	[0-9]{1,4} → 숫자 1~4자리
[...]	문자 클래스: 괄호 안 문자 중 하나	[aeiou]
(...)	그룹(묶기와 캡처)	(ab)+
|	선택(OR)	jpg|png
\	이스케이프, 또는 특수 시퀀스 시작	\., \d

자리수를 [0-9]{1.4}처럼 쓰는 것은 흔한 실수다. 쉼표 대신 마침표를 쓰면 대부분의 엔진은 수량자로 보지 않고 "{1.4}"라는 글자 그대로 찾는다. 올바른 표기는 [0-9]{1,4}이다.

문자 클래스

표기	뜻
[abc]	a, b, c 중 하나
[^abc]	a, b, c가 아닌 문자 하나(대괄호 맨 앞의 ^만 부정)
[a-z], [0-9], [가-힣]	코드 포인트 범위. 시작이 끝보다 크면 오류
[-a], [a-], [a\-z]	하이픈 자체. 맨 앞이나 맨 뒤에 두거나 이스케이프
\d / \D	숫자 / 숫자 아님
\w / \W	단어 문자(영문자, 숫자, 밑줄) / 그 밖
\s / \S	공백 문자(스페이스, 탭, 줄바꿈 등) / 그 밖
[[:alpha:]] 등	POSIX 문자 클래스. 대괄호 안에서만 쓴다. alnum, alpha, blank, cntrl, digit, graph, lower, print, punct, space, upper, xdigit 12개
\p{...} / \P{...}	유니코드 속성에 해당하는 문자 / 해당하지 않는 문자(아래 유니코드 절)

• 쉼표는 문자 클래스에서 구분자가 아니다. 기존 예시의 [1,3,4]는 1, 3, 4와 쉼표까지 네 문자 중 하나와 일치한다. 1, 3, 4만 원하면 [134]다.
• [A-z]는 대문자와 소문자 사이에 있는 [ \ ] ^ _와 억음 부호까지 포함하므로 [A-Za-z]로 쓴다.
• \d와 \w의 범위는 엔진마다 다르다. Python 3의 str 패턴과 .NET은 기본값이 유니코드여서 \d가 아랍·인도 숫자 등 유니코드 10진 숫자 전체와 일치하고 \w가 한글과도 일치한다. [0-9]만 원하면 [0-9]로 쓰거나 Python은 re.ASCII 플래그를 켠다. JavaScript와 Java는 기본이 ASCII다(Java는 UNICODE_CHARACTER_CLASS로 유니코드 확장).
• 대괄호 안에서는 대부분의 메타문자가 평범한 문자가 된다. [.]은 마침표, [$]는 달러 기호다. 특별한 문자는 ] \ ^ - 정도다. JavaScript 등에서 [\b]는 백스페이스 문자다(대괄호 밖의 \b는 단어 경계).
• 이스케이프 문자: \n(줄바꿈), \r, \t(탭), \f(폼 피드), \v(수직 탭), \0(널), \xhh(16진 코드), \uhhhh(유니코드), \cX(제어 문자).

수량자: 탐욕, 게으름, 소유

탐욕(greedy)	게으름(lazy, reluctant)	소유(possessive)	동작
*	*?	*+	0회 이상
+	+?	++	1회 이상
?	??	?+	0~1회
{n,m}	{n,m}?	{n,m}+	n~m회

• 탐욕 수량자는 가능한 한 많이 먹은 뒤 뒤쪽이 실패하면 한 글자씩 돌려준다(백트래킹).
• 게으른 수량자는 가능한 한 적게 먹고 뒤쪽이 실패할 때마다 한 글자씩 더 먹는다.
• 소유 수량자는 한 번 먹은 것을 돌려주지 않는다. 불필요한 백트래킹을 막아 빠르지만 결과가 달라질 수 있다. ".*+"는 .*+가 마지막 따옴표까지 먹어 버려 아무것과도 일치하지 않고, "[^"]*+"처럼 부정 문자 클래스와 함께 쓸 때 쓸모가 있다. Java, PCRE, Python 3.11+가 지원하고 JavaScript와 .NET은 지원하지 않는다.
• 원자 그룹 (?>...)은 그룹 단위로 같은 효과를 낸다. ^(wi|w)i$는 wi와 wii 둘 다와 일치하지만 ^(?>wi|w)i$는 wii만 일치한다. 그룹이 wi를 먹은 뒤 w로 되돌아가지 못하기 때문이다.

import re
html = '<b>굵게</b> 그리고 <b>또 굵게</b>'
re.findall(r'<b>(.+)</b>', html)    # ['굵게</b> 그리고 <b>또 굵게']  탐욕: 가장 멀리 있는 </b>까지
re.findall(r'<b>(.+?)</b>', html)   # ['굵게', '또 굵게']            게으름: 가장 가까운 </b>까지
re.findall(r'<b>([^<]+)</b>', html) # ['굵게', '또 굵게']            부정 클래스: 백트래킹이 적다

Vim은 게으른 수량자를 \{-}, \{-n,m}으로 쓴다.

앵커와 경계

표기	뜻
^, $	문자열(또는 m 플래그에서 줄)의 시작과 끝. 많은 엔진에서 $는 문자열 끝의 줄바꿈 바로 앞에서도 일치한다.
\A, \z	플래그와 관계없이 문자열 전체의 시작과 끝(JavaScript에는 없음). Python은 끝을 \Z로 쓴다.
\Z	(Perl, Java, .NET) 문자열 끝 또는 마지막 줄바꿈 앞
\b, \B	단어 경계(단어 문자와 비단어 문자 사이) / 단어 경계가 아닌 곳. \bcat\b는 cat과 일치하고 category와는 일치하지 않는다.
\G	직전 매치가 끝난 위치(Perl, PCRE, Java, .NET)

앵커와 경계는 문자를 소비하지 않는 "너비 0" 조건이다.

그룹과 역참조

표기	뜻
(...)	캡처 그룹. 여는 괄호 순서대로 1, 2, 3... 번호가 붙고, 0번은 매치 전체
(?:...)	비캡처 그룹. 묶기만 하고 저장하지 않아 가볍다
(?<name>...)	명명 그룹(JavaScript, Java, .NET, PCRE). Python은 (?P<name>...)
\1, \2	번호 역참조: 앞 그룹이 실제로 일치한 문자열과 같은 문자열
\k<name>	이름 역참조. Python은 (?P=name)
(?i:...)	그룹 안에서만 플래그 적용(인라인 수정자)
(?#...)	주석(PCRE, Python, .NET)

\b(\w+)\s+\1\b는 "the the"처럼 같은 단어가 연달아 나온 곳을 찾는다. (['"]).*?\1은 여는 따옴표와 같은 종류의 따옴표로 닫힌 문자열을 찾는다.

전후방 탐색

	뒤에 오는 것 검사(전방 탐색, lookahead)	앞에 온 것 검사(후방 탐색, lookbehind)
긍정	X(?=Y): 뒤에 Y가 오는 X	(?<=Y)X: 앞에 Y가 있는 X
부정	X(?!Y): 뒤에 Y가 오지 않는 X	(?<!Y)X: 앞에 Y가 없는 X

탐색 부분은 조건만 확인하고 매치 결과에 포함되지 않는다. 비밀번호 규칙처럼 여러 조건을 한꺼번에 거는 데 자주 쓴다.

^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[^\w\s]).{12,}$     소문자, 대문자, 숫자, 특수문자를 각각 하나 이상 포함한 12자 이상
\d+(?=원)                                                "원" 앞의 숫자만 (1500원 → 1500)
(?<=\$)\d+(\.\d{2})?                                    $ 뒤의 금액만
\b(?!test)\w+                                            test로 시작하지 않는 단어

후방 탐색 안에 쓸 수 있는 패턴의 길이 제한은 엔진마다 다르다. Python re는 고정 길이만 허용하고(a|bc처럼 길이가 다른 선택도 불가), Java는 최대 길이가 정해진 패턴까지, JavaScript와 .NET은 임의 길이를 허용한다. JavaScript는 후방 탐색 안을 오른쪽에서 왼쪽으로 매칭한다. RE2와 Go는 전후방 탐색을 아예 지원하지 않는다.

플래그(수정자)

기능	JavaScript	Python	Java	.NET	인라인
대소문자 무시	i	re.I	CASE_INSENSITIVE	IgnoreCase	(?i)
^ $를 줄 단위로	m	re.M	MULTILINE	Multiline	(?m)
.이 줄바꿈과도 일치	s	re.S	DOTALL	Singleline	(?s)
공백·주석 무시(읽기 쉬운 패턴)	없음	re.X	COMMENTS	IgnorePatternWhitespace	(?x)
모든 매치 찾기	g	findall, finditer	while (m.find())	Matches	없음
유니코드 모드	u, v	기본값(str)	UNICODE_CHARACTER_CLASS	기본값	(?u)
현재 위치에서만 매칭	y	re.match	\G	\G	없음
그룹 위치 정보	d	m.span()	m.start(n)	Group.Index	없음

• JavaScript의 g는 "문자열 전체에서 모든 매치를 찾는" 전역 검색 플래그다. ^ $의 의미를 바꾸는 것은 m이다.
• 대소문자 무시는 대소문자가 없는 한글, 한자, 가나에는 영향이 없다. 유니코드 대소문자 변환에는 튀르키예어의 점 있는/없는 i, 독일어 ß 같은 예외가 있어 엔진과 로캘에 따라 결과가 다를 수 있다.
• x 플래그를 켜면 패턴 안의 공백이 무시되고 # 뒤가 주석이 되어 긴 패턴을 여러 줄로 나눠 쓸 수 있다. 공백 자체는 \ 나 [ ]로 쓴다.

유니코드 속성

유니코드 정규 표현식 기술 표준(UTS #18)은 \p{속성} 형태로 문자 속성을 지정하는 문법을 정한다.

• 일반 범주: \p{L}(모든 문자), \p{Lu}(대문자), \p{N}(숫자), \p{P}(문장 부호)
• 문자 체계(script): \p{Script=Hangul}, \p{sc=Han}, \p{Script=Latin}
• 블록: \p{InHangul_Syllables}(Java, Perl), \p{IsHangulSyllables}(.NET)
• 이진 속성: \p{White_Space}, \p{Alphabetic}, \p{Emoji}

지원 범위: Perl, PCRE, Java, .NET, Ruby, JavaScript(u 또는 v 플래그 필요)는 지원하고, Python 표준 re는 지원하지 않아 서드파티 regex 모듈을 쓴다. 블록은 여러 문자 체계가 섞일 수 있어 보통 script 속성이 더 정확하다.

구분자와 문자열 이스케이프

Perl, JavaScript, PHP 같은 언어는 패턴 앞뒤를 구분자로 감싸고 뒤에 플래그를 붙인다. JavaScript의 /(http|https|ftp):\/\/[^"'\s()]+/i는 구분자 /, 패턴, 구분자 /, 플래그 i로 나뉜다. 구분자와 같은 문자가 패턴에 나오면 이스케이프해야 해서(\/) 읽기 어려워진다. Perl과 PHP는 영숫자, 역슬래시, 공백이 아닌 문자라면 무엇이든 구분자로 쓸 수 있어 #https?://#처럼 바꿔 쓰기도 한다. Python, Java, C#처럼 패턴을 일반 문자열로 넘기는 언어에서는 문자열 이스케이프와 정규식 이스케이프가 겹치므로 역슬래시를 두 번 써야 한다(Java "\\d+"). Python은 원시 문자열 r"\d+", C#은 축자 문자열 @"\d+"로 이를 피한다.

방언 비교

기능	POSIX BRE	POSIX ERE	Perl/PCRE2	JavaScript	Python re	Java	.NET	RE2/Go/Rust
그룹	\( \)	( )	( )	( )	( )	( )	( )	( )
+ ? |	표준 아님(GNU는 \+ \? \|)	O	O	O	O	O	O	O
반복 {n,m}	\{n,m\}	O	O	O	O	O	O	O
비캡처 (?:)	X	X	O	O	O	O	O	O
명명 그룹	X	X	(?<n>), (?P<n>)	(?<n>)	(?P<n>)	(?<n>)	(?<n>), (?'n')	(?P<n>)
역참조	O(\1~\9)	표준 아님(GNU는 지원)	O	O	O	O	O	X
전방 탐색	X	X	O	O	O	O	O	X
후방 탐색	X	X	O(고정 길이 중심)	O(임의 길이)	O(고정 길이)	O(유한 길이)	O(임의 길이)	X
게으른 수량자	X	POSIX.1-2024부터	O	O	O	O	O	O
소유 수량자·원자 그룹	X	X	O	X	3.11+	O	원자 그룹만	X
\p{...}	X	X	O	O(u/v 플래그)	X(regex 모듈)	O	O	O
재귀·조건식	X	X	O	X	조건식만	X	균형 그룹, 조건식	X
여러 후보 중 선택 규칙	가장 왼쪽·가장 긴 매치	가장 왼쪽·가장 긴 매치	가장 왼쪽·먼저 적은 후보	먼저 적은 후보	먼저 적은 후보	먼저 적은 후보	먼저 적은 후보	먼저 적은 후보(POSIX 모드 선택 가능)
선형 시간 보장	구현에 따라	구현에 따라	X	X	X	X	NonBacktracking 모드(.NET 7+)	O

POSIX는 여러 매치가 가능하면 가장 왼쪽에서 시작하는 것 중 가장 긴 것을 고른다. 백트래킹 엔진은 선택지를 적힌 순서대로 시도해 처음 성공한 것을 고른다. 그래서 (a|ab)를 "ab"에 적용하면 POSIX는 ab, Perl 계열은 a와 일치한다.

도구별 문법

도구	기본 문법	바꾸는 옵션	비고
grep	BRE	-E(ERE, 옛 egrep), -F(고정 문자열), -P(PCRE, GNU grep)	-o 매치 부분만, -i 대소문자 무시
sed	BRE	-E 또는 -r(ERE)	치환 s/패턴/바꿀말/g, 역참조 \1, 매치 전체 &
awk	ERE	없음	역참조 없음. gawk는 gensub로 \1 사용 가능
vi/Vim	자체 문법(magic)	\v(very magic: 대부분 메타문자를 이스케이프 없이)	게으른 수량자 \{-}, 단어 경계 \< \>
Emacs	자체 문법	없음	그룹 \( \), 문자열 안에서 역슬래시 이중 이스케이프
PostgreSQL	스펜서 ARE	~, ~*(대소문자 무시), regexp_replace	SQL 표준 SIMILAR TO도 지원
MySQL 8.0+	ICU	REGEXP, REGEXP_REPLACE	8.0 이전은 스펜서 라이브러리

엔진 구현

패턴이 문자열과 일치하는지 판정하는 방법은 크게 셋이다.

방식	원리	매칭 시간(패턴 길이 m, 입력 길이 n)	기능	사용처
DFA	패턴을 결정적 오토마타로 미리 바꾼 뒤 입력을 한 글자씩 한 번만 읽는다	O(n). 대신 DFA 구성에 최악 O(2m)	캡처, 역참조, 게으른 수량자 처리가 어렵다	lex/flex, GNU grep, awk 일부 구현
NFA 시뮬레이션(톰슨 방식), 지연 DFA	NFA의 가능한 상태 집합을 동시에 따라가고, 필요한 DFA 상태만 만들어 캐시한다	O(mn)	캡처는 가능(Pike VM 등), 역참조·전후방 탐색은 불가	RE2, Go, Rust regex, .NET NonBacktracking, Hyperscan
백트래킹	선택지 하나를 골라 진행하다 실패하면 되돌아와 다른 선택지를 시도한다	최악 O(2n)	역참조, 전후방 탐색, 재귀 등 모든 확장 가능	Perl, PCRE, Python, Java, JavaScript(V8 Irregexp), .NET 기본, Ruby

• 백트래킹 엔진은 흔히 "NFA 엔진"이라고도 불리지만 톰슨 NFA와는 동작이 전혀 다르다.
• 콕스의 측정에서 a?를 n번 반복한 뒤 a를 n번 붙인 패턴을 a가 n개인 문자열에 적용하면, n=29일 때 Perl은 60초 넘게 걸렸고 톰슨 NFA 구현은 약 20마이크로초가 걸렸다.
• GNU grep은 먼저 보이어-무어 방식으로 후보를 거르고 DFA로 매칭하며, 역참조를 만났을 때만 백트래킹 매처로 확인한다.
• 성능을 위해 패턴을 기계어로 컴파일하는 엔진도 많다. PCRE2 JIT, .NET의 RegexOptions.Compiled와 소스 생성기, V8 Irregexp가 그렇다.
• 역참조가 k개일 때 백트래킹 없이 다항 시간으로 푸는 이론적 방법도 있지만, 지수에 k가 들어가 실용적이지 않다.

ReDoS와 파국적 백트래킹

백트래킹 엔진은 한 입력을 여러 방식으로 나눠 먹을 수 있는 패턴을 만나면, 결국 실패할 입력에 대해 가능한 분할을 모두 시도한다. 이를 파국적 백트래킹(catastrophic backtracking)이라고 하고, 이를 노려 서버 CPU를 소진시키는 공격을 ReDoS(Regular expression Denial of Service)라고 한다. 일반 서비스 거부 공격처럼 대량 트래픽이 필요 없고, 짧은 요청 하나로 스레드 하나를 오래 묶어 둘 수 있다.

위험한 패턴의 전형:

• 중첩 수량자: (a+)+$, (\w+)*$. 입력 "aaaa...a!"에서 a 덩어리를 나누는 방법이 2ⁿ가지다.
• 겹치는 선택지의 반복: (a|aa)*b, (\d|\d\d)+$
• 같은 문자를 먹을 수 있는 수량자가 연달아 나오는 경우: .*.*=.*, \s*\s*$. 다항식(2차, 3차) 폭발이지만 입력이 길면 충분히 치명적이다.

실제 장애:

사례	원인 패턴	내용
Stack Overflow, 2016-07-20, 34분	^[\s\u200c]+|[\s\u200c]+$	앞뒤 공백을 지우는 패턴이 공백 약 2만 개가 이어진 게시물을 만났다. 공백 뒤에 다른 문자가 있어 매번 실패하고 다음 위치에서 다시 시도하느라 문자 클래스 검사가 약 2억 번 일어났다(2차 시간). 로드 밸런서가 이 게시물이 걸린 홈페이지로 상태 검사를 해서 웹 서버가 모두 빠지며 사이트 전체가 멈췄다.
Cloudflare, 2019-07-02, 27분	...(?:.*=.*)를 포함한 XSS 탐지 규칙	웹 방화벽 관리형 규칙에 새 XSS 탐지 규칙을 전 세계에 한 번에 배포했는데, 이 패턴이 과도한 백트래킹을 일으켜 HTTP 처리 서버의 CPU가 전부 소진되었다. 대응으로 CPU 사용량 보호 장치를 되살리고, 규칙 3,868개를 모두 점검하고, 선형 시간이 보장되는 RE2나 Rust regex 엔진으로 바꾸고, 규칙을 단계적으로 배포하기로 했다.

대응 방법:

• 사용자가 패턴을 넣는 서비스나 큰 입력을 처리하는 곳에는 선형 시간 엔진(RE2, Go regexp, Rust regex, .NET NonBacktracking)을 쓴다. RE2는 원칙상 백트래킹으로만 풀 수 있는 역참조와 전후방 탐색을 지원하지 않는다.
• 중첩 수량자와 겹치는 선택지를 없앤다. (a+)+는 a+로, .*는 가능한 한 [^,]*처럼 구체적인 부정 클래스로 바꾼다.
• 소유 수량자나 원자 그룹으로 되돌아가기를 막는다.
• 매칭 시간 제한을 둔다. .NET은 Regex 생성자에 시간 제한(matchTimeout)을 줄 수 있다.
• 입력 길이를 먼저 제한하고, 배포 전에 최악 입력으로 성능 시험을 한다. .NET 문서는 NonBacktracking 모드도 입력 폭발만 막을 뿐 악의적인 패턴까지 막지는 못하므로 패턴은 신뢰할 수 있어야 한다고 설명한다.

자주 쓰는 패턴

용도	패턴	주의
숫자만	^[0-9]+$	빈 문자열도 허용하려면 *
영문자만	^[A-Za-z]+$ 또는 /^[a-z]+$/i
영문자와 숫자	^[A-Za-z0-9]+$
휴대전화 번호 형식	^01[016789]-?\d{3,4}-?\d{4}$	형식만 본다. 실제 번호인지는 알 수 없다
날짜 형식 YYYY-MM-DD	^\d{4}-(0[1-9]|1[0-2])-(0[1-9]|[12]\d|3[01])$	2월 30일 같은 날짜는 걸러지지 않는다. 날짜 라이브러리로 다시 검사
IPv4 주소	^((25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)\.){3}(25[0-5]|2[0-4]\d|1\d\d|[1-9]?\d)$	\d{1,3}(\.\d{1,3}){3}는 999.999.999.999도 통과한다. IPv6는 축약 규칙 때문에 정규식이 매우 길어지므로 언어의 IP 주소 파서(Python ipaddress 등)를 쓰는 편이 낫다
이메일 주소	아래 설명
URL 추출	https?://[^\s"'<>()]+	문장 끝 마침표나 괄호가 섞일 수 있다
앞뒤 공백 제거	^\s+와 \s+$를 따로 적용	합친 ^\s+|\s+$는 백트래킹 엔진에서 긴 공백에 느려질 수 있다(Stack Overflow 사례). 언어의 trim/strip이 낫다
연속 공백 하나로	\s+ → " "
중복 단어	\b(\w+)\s+\1\b

이메일 주소는 RFC 5322 문법을 그대로 정규식으로 옮기면 주석, 따옴표 문자열 등 때문에 대단히 길어지고, 실제로 메일이 가는지는 어차피 확인 메일로만 알 수 있다. HTML 표준은 <input type="email">의 검사 규칙을 RFC 5322에서 일부러 벗어나 단순화했고, 이를 JavaScript·Perl 호환 정규식으로 제시한다.

/^[a-zA-Z0-9.!#$%&'*+\/=?^_`{|}~-]+@[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?(?:\.[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*$/

이 규칙도 국제화 도메인(한글 도메인)이나 비ASCII 로컬 파트는 허용하지 않는다. 검증용 정규식은 "명백히 틀린 입력을 거르는" 정도로 느슨하게 쓰는 것이 보통이다.

HTML이나 XML에서 태그를 정규식으로 뽑는 방법은 한 줄짜리 간단한 경우에만 쓸 수 있다. 태그 중첩, 속성값 안의 >, 주석, CDATA 등을 처리하려면 HTML 파서를 써야 한다.

한글

패턴	범위	비고
[가-힣]	U+AC00~U+D7A3	현대 한글 음절 11,172자 전부. KS X 1001 완성형 2,350자에 없는 글자(똠, 쀍 등)도 포함한다
[ㄱ-ㅎ], [ㅏ-ㅣ]	U+3131~U+314E, U+314F~U+3163	한글 호환 자모(자음만, 모음만 입력한 "ㅋㅋ", "ㅠㅠ" 같은 글자)
[ㄱ-ㅎㅏ-ㅣ가-힣]	위 둘의 합	자모 낱자를 포함한 현대 한글
[\u1100-\u11FF]	한글 자모(첫가끝)	초성·중성·종성을 따로 적는 조합용 자모. 옛한글과 NFD 정규화된 한글에 쓰인다
\p{Script=Hangul}	한글 문자 체계 전체	음절, 호환 자모, 조합용 자모, 반각 자모 등을 모두 포함. JavaScript는 u 플래그, Java는 \p{IsHangul}

• 이 범위들은 엔진이 유니코드 코드 포인트 단위로 동작할 때만 맞다. EUC-KR이나 CP949 바이트열을 바이트 단위로 처리하는 환경에서는 [가-힣]이 의도대로 동작하지 않는다.
• macOS 파일 시스템처럼 한글을 NFD(자모 분해형)로 저장하는 곳에서 가져온 문자열은 "가"가 U+1100 U+1161 두 글자라서 [가-힣]과 일치하지 않는다. 비교 전에 NFC로 정규화한다(Python unicodedata.normalize('NFC', s), JavaScript s.normalize('NFC')).
• 완성형 2,350자만 허용해야 한다면 범위로는 표현할 수 없으므로 글자 목록을 문자 클래스로 나열하거나 CP949 인코딩 가능 여부로 검사한다.

치환

캡처 그룹은 바꿀 문자열에서 다시 불러 쓸 수 있다. 문법은 도구마다 다르다.

환경	번호 그룹	이름 그룹	매치 전체	달러 기호 자체
JavaScript replace	$1	$<name>	$&	$$
Python re.sub	\1, \g<1>	\g<name>	\g<0>	그대로
Java replaceAll	$1	${name}	$0	\$
.NET Regex.Replace	$1, ${1}	${name}	$0, $&	$$
PHP preg_replace	$1, \1, ${1}	없음(콜백 사용)	$0	\$
Perl s///	$1	$+{name}	$&	\$
sed	\1~\9	없음	&	그대로
Vim :s	\1	없음	&, \0	그대로
VS Code, IntelliJ 찾기·바꾸기	$1	도구마다 다름	$0	$$

$10이 10번 그룹인지 1번 그룹 뒤에 0인지 모호할 때는 ${1}0(.NET, PHP)이나 \g<1>0(Python)으로 경계를 밝힌다. Perl, GNU sed, Vim은 바꿀 문자열 안에서 \U, \L, \u로 대소문자를 바꿀 수 있다.

예: 1~4자리 숫자와 공백 뒤 한글 한 글자 사이에 마침표를 넣는다.

찾기:   ([0-9]{1,4}) ([가-힣])
바꾸기: $1. $2        (sed, Vim, Python에서는 \1. \2)

변경 전: 442 오
변경 후: 442. 오

언어별 사용 예

// JavaScript
const re = /(?<year>\d{4})-(?<month>\d{2})-(?<day>\d{2})/g;
const s = '시작 2024-03-15, 종료 2024-12-31';
for (const m of s.matchAll(re)) console.log(m.groups.year, m.index);
s.replace(re, '$<day>/$<month>/$<year>');   // '시작 15/03/2024, 종료 31/12/2024'
/^[가-힣]+$/.test('정규식');                // true
/\p{Script=Hangul}+/u.exec('abc한글')[0];   // '한글'

# Python
import re
pat = re.compile(r'(?P<key>\w+)=(?P<val>[^;]*)')
[m.groupdict() for m in pat.finditer('a=1;b=hello')]  # [{'key': 'a', 'val': '1'}, {'key': 'b', 'val': 'hello'}]
re.sub(r'(\d+)원', r'\1 KRW', '가격 1500원')          # '가격 1500 KRW'
re.fullmatch(r'\d{3}-\d{4}', '123-4567') is not None   # True, 전체 일치
re.split(r'\s*,\s*', 'a , b,c')                        # ['a', 'b', 'c']

// Java
import java.util.regex.*;
Pattern p = Pattern.compile("(\\w+)@(\\w+)\\.com");   // 역슬래시를 두 번 쓴다
Matcher m = p.matcher("id: [email protected]");
if (m.find()) System.out.println(m.group(1) + " / " + m.group(2));  // kim / example
"2024-03-15".matches("\\d{4}-\\d{2}-\\d{2}");          // true, matches()는 전체 일치
"a1b22c333".replaceAll("\\d+", "#");                    // a#b#c#

// C# (.NET)
using System.Text.RegularExpressions;
var re = new Regex(@"^(?<user>[^@\s]+)@(?<host>[^@\s]+)$",
                   RegexOptions.IgnoreCase, TimeSpan.FromMilliseconds(100)); // 매칭 시간 제한
var m = re.Match("[email protected]");
Console.WriteLine(m.Groups["host"].Value);   // example.com
var safe = new Regex(@"(a+)+$", RegexOptions.NonBacktracking);  // .NET 7+, 선형 시간

// Go (RE2 문법: 역참조와 전후방 탐색 없음)
re := regexp.MustCompile(`(?P<k>\w+)=(\d+)`)
fmt.Println(re.FindAllStringSubmatch("a=1 b=22", -1)) // 매치마다 전체, 1번, 2번 그룹: (a=1, a, 1), (b=22, b, 22)
fmt.Println(re.ReplaceAllString("a=1", "${k}:$2"))    // a:1

// PHP (PCRE)
preg_match('/^(\d{3})-(\d{4})$/', '123-4567', $m);   // $m[1] = '123'
echo preg_replace('#https?://([^/\s]+)\S*#', '[$1]', '링크 https://example.com/a');  // 링크 [example.com]
preg_match('/^\p{Hangul}+$/u', '한글');                // 1, u 수정자로 UTF-8 처리

# 셸 도구
grep -E '^[0-9]{3}-[0-9]{4}$' phone.txt         # ERE
grep -oP '(?<=id=)\d+' access.log                # PCRE 후방 탐색(GNU grep)
sed -E 's/([0-9]{4})-([0-9]{2})-([0-9]{2})/\3.\2.\1/g' dates.txt
awk '$3 ~ /^ERR/ { print $1 }' app.log           # 3번째 필드가 ERR로 시작하는 줄

-- PostgreSQL
SELECT * FROM users WHERE email ~* '^[a-z0-9._%+-]+@example\.com$';
SELECT regexp_replace('010-1234-5678', '(\d{3})-(\d{4})-(\d{4})', '\1-****-\3');
-- MySQL 8.0+
SELECT * FROM users WHERE name REGEXP '^[가-힣]+$';

주의점

• 같은 패턴이 엔진마다 다르게 동작한다. \d의 범위, $가 끝 줄바꿈 앞에서 일치하는지, .이 \r과 일치하는지, 후방 탐색 지원 여부가 다르므로 대상 환경에서 확인한다.
• 셸에서는 작은따옴표로 패턴을 감싸 셸의 글롭 확장과 변수 치환을 막는다. sed로 파일을 직접 고치는(-i) 치환은 먼저 출력만으로 확인한다.
• 긴 패턴은 x 플래그로 줄을 나누고 주석을 달거나, 조각을 변수로 나눠 조립한다.
• 반복해서 쓰는 패턴은 한 번 컴파일해 재사용한다(Python re.compile, Java Pattern.compile). 루프 안에서 매번 새로 만들면 느리다.
• 사용자 입력을 패턴 일부로 넣을 때는 메타문자를 이스케이프한다(Python re.escape, Java Pattern.quote, .NET Regex.Escape). 그러지 않으면 의도하지 않은 패턴이나 ReDoS 패턴이 주입될 수 있다.
• 보안 필터(블랙리스트)를 정규식으로만 만들면 우회되기 쉽다. 대소문자, 인코딩, 공백 변형을 모두 고려해야 하고, 가능하면 허용 목록 방식이나 전용 파서를 쓴다.

도구와 학습 자료

• regex101: PCRE2, JavaScript, Python, Java, .NET, Go, Rust 방언을 골라 패턴을 시험하고 단계별 설명과 매칭 단계 수를 보여 준다. 백트래킹 폭발을 확인할 때도 쓴다.
• RegExr: JavaScript와 PCRE 방언을 지원하는 시험·학습 사이트.
• Regexper, Debuggex: 패턴을 철도 다이어그램(railroad diagram)으로 그려 준다.
• RegexOne: 단계별 연습 문제.
• MDN 정규 표현식 안내서, Python Regular Expression HOWTO
• VerbalExpressions: 메서드 체인으로 패턴을 만드는 라이브러리. 여러 언어판이 있다.
• 대부분의 텍스트 편집기와 IDE(VS Code, IntelliJ, Notepad++, Vim)의 찾기·바꾸기가 정규식 모드를 지원한다.

같이 보기

• 유한 오토마타
• 어휘 분석
• 컴파일러
• POSIX
• 리눅스 grep
• 리눅스 awk
• 유니코드
• 서비스 거부 공격
• 웹 방화벽
• JIT 컴파일

참고 문헌

• Russ Cox, Implementing Regular Expressions (연재 글 모음)
• POSIX.1-2024, Regular Expressions
• PCRE2 pattern 문서
• Perl, perlre
• Java, java.util.regex.Pattern
• Microsoft Learn, Regular Expression Language Quick Reference
• RE2 Syntax
• ECMAScript, RegExp Objects