evenharder's profile image

evenharder

February 10, 2019 20:30

Hello, Regex!

regex , introduction

정규 표현식이란?

정규 표현식(Regular Expression, Regex)는 일정한 규칙을 가진 문자열의 집합을 표현하는데 사용합니다. 정규 표현식은 문자열의 검색과 치환을 위해 종종 쓰입니다. 프로그래밍 코드나 그 산출물에서 규칙이 드러나는 문자열은 무궁무진합니다. 날짜, 도메인 주소 형식, 이메일 형식, 수많은 유틸리티의 출력 형식이 대표적인 예이며, 그 외에도 두 글자 이상의 공백 등 규칙이 있는 문자열을 처리해야 할 때가 있습니다. 정규 표현식을 이용하면 이들을 보다 편하게 탐색하고 감지할 수 있습니다. 정규 표현식은 특히 Perl에서 그 확장성이 뛰어나며, 그외 수많은 언어들과 CLI 툴이 정규 표현식을 지원합니다.

정규 표현식은 ‘정규 언어’에서 비롯된 언어입니다. 정규 언어의 정의는 오토마타와 연관이 있으며 여기서는 생략하도록 하겠습니다. 다만 일부 정규 표현식 구현체는 정규 언어보다 넓은 범주인 ‘문맥 자유 언어’의 특징 또한 지니고 있습니다.

형식언어론에서의 정규 언어

정규 표현식에 대해 간단히 서술하도록 하겠습니다. 형식언어론에서 모든 언어 $ L $은 그 언어에서 사용되는 문자의 집합 $\Sigma$를 가집니다 (alphabet이라고도 부릅니다). 또 언어에서 문자열(string)은 $ \Sigma $의 원소로 이루어진 유한한 길이의 수열로 정의됩니다. 예로 들어 $ \Sigma = {a, b}$이면 $ abaa $가 해당 문자를 이용한 문자열이 됩니다.

정규 표현식은 문자열들의 집합이며, 다음 세 ‘표현식’은 정규 표현식입니다.

  • $ \emptyset $ : 공집합을 뜻합니다. 해당 정규 표현식에 대응되는 문자열은 존재하지 않습니다.
  • $ \epsilon $ : 공문자열, 즉 길이가 0인 문자열이 대응됩니다.
  • $ a $ : $ \Sigma $의 임의의 원소 $ a $에 대해, 이 정규 표현식에는 해당 원소 하나로만 이루어진 문자열이 대응됩니다.

임의의 정규 표현식 $ R $과 $ S $에 대해, 다음 표현식 또한 정규 표현식입니다.

  • $ RS $ : $ R $ 에 속한 문자열과 $ S $에 속한 문자열을 연결하여 만들 수 있는 문자열들의 집합입니다. (concatenation)
  • $ R \vert S $ : $ R $에 속해있거나 $ S $에 속해있는 문자열들의 집합입니다. (alternation)
  • $ R^* $ : $ R $에 속해있는 임의의 문자열을 유한번 이어붙여 만들 수 있는 문자열들의 집합입니다. (Kleene star)

괄호를 통해 연산 순서를 조정할 수 있으며, 기본적인 연산 순서는 Kleene Star, concatenation, alternation입니다. 예를 들어 정규 표현식 $ (aa \vert aba*)b $ 엔 $ b $, $ aab $, $ abab $, $ abaabab $ 등이 속합니다.

정규 언어의 엄밀한 정의를 서술하는 이유는 두 가지입니다. 첫째로 정규 표현식이란 그저 문자열들의 집합을 의미한다는 점을 숙지시키기 위함이며, 둘째는 정규 표현식의 한계를 알려드리기 위함입니다. 다음 언어는 정규 언어에 속하지 않습니다. 즉, 이를 100% 만족하는 정규 표현식은 존재하지 않습니다. 이는 예시에 불과합니다. 이 언어들만 표현할 수 없다는 뜻이 결코 아닙니다.

  • 회문인 (뒤집어도 동일한) 문자열의 집합
  • 임의의 자연수 $ n $에 대해, $ a $가 $ n $개 연속되어 있고 바로 뒤에 $ b $가 $ n $개 연속되어 오는 문자열들의 집합
  • 올바른 괄호 문자열((와 )로만 이루어져 있고, 모든 괄호 문자열의 쌍이 맞는 문자열)의 집합
  • 올바른 정규 표현식으로 이루어진 집합

임의의 괄호 문자열에 대한 판별이 불가능하므로 당연히 열고 닫는 쌍이 존재하는 html 문서는 정규 표현식으로 나타낼 수 없습니다. 물론 어느 정도 수준에서 일치하는 정규 표현식은 작성할 수 있으며, 대부분의 정규 표현식 엔진은 정규 언어를 넘어선 경우가 많습니다. 그러나 정규 표현식이 만능이 아니라는 점을 아셨으면 합니다.

정규 표현식 문법

정규 표현식은 문자열의 집합입니다. 정규 표현식에 해당되는 문자열이 등장하면 대응(매칭이라고도 부릅니다)이 되고, 정규 표현식 엔진들은 대응될 경우 그 결과를 반환합니다. 텍스트에서 조건에 맞는 문자열을 찾는다고 생각하면 편합니다. 정규 표현식 매칭의 원칙은 다음과 같습니다.

  • 매칭은 기본적으로 첫 글자부터 모든 가능성을 탐색하면서 이루어집니다.
  • 때문에, 더 긴 문자열이 나중에 매칭될 수 있어도, 먼저 매칭된 문자열이 결과로 반환됩니다.
  • 추가적으로 현재 상황에서 매칭은 가능한 한 길게 진행됩니다. 자세한 의미는 예제를 통해 설명하도록 하겠습니다.

일반적으로 정규 표현식은 /로 감싸 나타냅니다.

# 정규 표현식
/cat/

# 문자열
cacat
Was it a cat I saw?
concatenate
dog

각 줄별로 처리되며, 매칭된 부분문자열은 볼드처리하였습니다. cat이 문자열에 있으면 정규 표현식 cat에 따라 매칭이 되는 것을 알 수 있습니다. 첫 번째 예시의 대응 과정을 설명하면 다음과 같습니다.

  • 첫 번째 글자부터 시작합니다.
    • 정규 표현식의 c와 문자열의 첫 글자 c가 대응되는지 확인합니다.
      • 대응이 되므로 다음으로 넘어갑니다.
      • 정규 표현식의 a와 문자열의 두 번째 글자 a가 대응되는지 확인합니다.
        • 역시 대응이 되어 다음으로 넘어갑니다.
        • 정규 표현식의 t와 문자열의 세 번째 글자 c가 대응되는지 확인합니다.
        • 대응이 되지 않으므로 매칭이 되지 않습니다. 현재 정규 표현식 t와 대응이 될 수 있는 다른 방법이 없으므로 실패하여 이전 단계로 돌아갑니다.
      • 역시 다른 방법이 없으므로 이전 단계로 돌아갑니다.
    • 역시 다른 방법이 없으므로 이전 단계로 돌아갑니다.
  • 더 돌아갈 곳이 없으므로 두 번째 글자로 넘어갑니다.
    • 정규 표현식의 c와 문자열의 두 번째 글자 a가 대응되는지 확인합니다.
    • 대응되지 않으므로 이전 단계로 돌아갑니다.
  • 더 돌아갈 곳이 없으므로 세 번째 글자로 넘어갑니다.
    • 정규 표현식의 c와 문자열의 세 번째 글자 c가 대응되는지 확인합니다.
      • 대응이 되므로 다음으로 넘어갑니다.
      • 정규 표현식의 a와 문자열의 네 번째 글자 a가 대응되는지 확인합니다.
        • 역시 대응이 되어 다음으로 넘어갑니다.
        • 정규 표현식의 t와 문자열의 다섯 번째 글자 t가 대응되는지 확인합니다.
          • 대응이 되므로 다음으로 넘어갑니다.
          • 정규 표현식의 끝에 도달했습니다. 매칭에 성공하였습니다.

결과적으로는 백트래킹을 통한 대응을 한다는 것을 알 수 있습니다.

문자 (literal)

이미 설명한 내용입니다. 대부분의 문자는 이와 같이 그 문자를 찾는 것과 동일한 의미를 가집니다. 다만 \, ^, $, ., |, ?, *, +, (, ), [, {는 특수한 의미와 용도를 지닙니다.위의 특수 문자들 (메타문자라고도 부릅니다)을 제외하고는 각 글자 하나와 대응이 됩니다. 메타 문자 .의 경우 줄바꿈 문자를 제외한 모든 문자와 대응이 됩니다.

# 정규 표현식
/c.p/

# 문자열
accepted
Nunc posuere faucibus magna id pretium
temp.cpp
c
p

대부분의 프로그래밍 언어처럼 \를 통해 escape 처리를 할 수 있습니다. \.는 "."와 대응되며, \\는 "\"와 대응됩니다.

문자 클래스 (character set)

문자 클래스란 문자들의 집합입니다. 여러 개의 문자 중 하나와 대응시키고자 할 때 사용합니다.

  • [ : 문자 클래스를 생성하는 대괄호 안에 구문을 넣으면 그 안에 있는 문자들이 대응이 됩니다. 예시로 [ae]는 a랑 e와, gr[ae]y는 gray랑 grey와 매칭됩니다.
    • 일부 문자들은 -를 통해 연속적으로 나타낼 수 있으며, [a-z]의 경우 알파벳 소문자 전체를, [A-Za-z]의 경우 알파벳 전체를, [1-9]의 경우 0을 제외한 아라비아 숫자와 대응됩니다. 보다 엄밀히 말하자면, 해당 캐릭터 코드 사이에 있는 모든 문자들이 포함됩니다.
    • 추가적으로 이 안에서는 다른 문법이 적용되며, 예시로 [.]은 점(".")을 뜻하지 줄바꿈 문자를 제외한 모든 문자를 뜻하지 않습니다.
  • [^ : 대괄호에 포함된 문자를 제외한 모든 문자와 대응됩니다. [^a-z]의 경우 알파벳 소문자를 제외한 모든 문자를 의미합니다.
  • \w : 기본적으로는 [A-Za-z0-9_]과 동일합니다 (word character). 그러나 유니코드를 지원하는 구현체의 경우 다른 문자를 추가적으로 포함할 수 있습니다.
  • \d : [0-9]와 동일합니다 (digit).
  • \s : [ \t\r\n\f]와 동일합니다 (whitespace character).
  • \W : [^\w]와 동일합니다.
  • \D : [^\d]와 동일합니다.
  • \S : [^\s]와 동일합니다.
# 정규 표현식
/gr[ae]y/

# 문자열
gray clouds
grey

# 정규 표현식
/[A-Z][a-z][0-9]/

# 문자열
aa2 Qz9 xyz 3ej

# 정규 표현식
/[가-힣]/

# 문자열
뷃
ㅈㅓㅇ

# 정규 표현식
/word[^.\w]/

# 문자열
word.
Is this a word?
Word word words

맨 마지막 줄의 경우 word 뒤의 공백까지 매칭에 포함됩니다.

그 외에도 축약형으로 쓸 수 있는 경우들이 있으나 구현체에 따라 다릅니다.

반복 문자 (repetition)

반복 문자는 특정 정규 표현식을 반복해서 사용하고 싶을 때 사용합니다.

  • * : 바로 앞에 있는 구문이 0번 이상 반복된 문자열과 대응됩니다.
  • + : 바로 앞에 있는 구문이 1번 이상 반복된 문자열과 대응됩니다.
  • {m} : 바로 앞에 있는 구문이 m번 반복된 문자열을 대응됩니다.
  • {min,max} : 바로 앞에 있는 구문이 최소 min번 최대 max번 반복된 문자열과 대응됩니다. min이 생략되면 하한이, max가 생략되면 상한이 생략됩니다.
  • ? : 바로 앞에 있는 구문이 0번 또는 1번 반복된 문자열과 대응됩니다.
# 정규 표현식
/ab*/

# 문자열
a
bbabbbb
abbbbbbbbbbbbbbbbbbbbbbbbbbbbcc

# 정규 표현식
/[\w]{8,16}/

# 문자열
password
1q2w3e4r!
123456
thispasswordistoolong

# 정규 표현식
favou?rite

# 문자열
favorite
favourite
favouurite

정규 표현식 /ab*/의 경우, abb도 abbbbbbb도 매칭이 됩니다. 그러나 모든 b와 대응이 된 이유를 알기 위해서는 기본적으로 정규 표현식 엔진이 어떻게 작동하는지 알아야 합니다. 기본적인 원칙은 greedy하게, 각 상황에서 최대한 매칭을 진행하고 성공할 경우 넘어가며 실패할 경우 매칭의 정도를 줄이는 방식이기 때문입니다. /[\w]{8,16}/에서도 8글자부터 16글자까지 매칭이 되는 상황에서 16글자가 매칭이 되었습니다.

앵커 (anchor)

앵커는 문자 자체랑 대응되기보다는 위치에 대응되며, 문자를 소모하지 않습니다 (zero-length token).

  • ^ : 문자열의 맨 처음에 대응됩니다.
  • $ : 문자열의 맨 끝에 대응됩니다.
  • \b : word boundary라고 불리며, 다음 조건 중 하나를 만족하는 위치에 대응됩니다.
    • 문자열의 맨 처음이면서, 첫 글자가 word character일 때
    • 문자열의 맨 끝이면서, 마지막 글자가 word character일 때
    • word character와 non-word character 사이에 있을 때
  • \b는 단어의 경계 역할을 한다고 보면 편합니다. word character는 위의 \w에 포함되는 문자입니다.
# 정규 표현식
/[a-z]+$/

# 문자열
Beer
Hello regex
Welcome to programming!

# 정규 표현식
/^miss/

# 문자열
mississippi
admission

# 정규 표현식
/\bis\b/

# 문자열
This is an example.
missing island

\b의 경우, This의 is에는 앞의 \b가 대응되지 않기 때문에 넘어간 것을 확인할 수 있습니다.

교체 구문 (alternation)

문자 클래스는 여러 문자 중 하나를 선택해서 대응시킵니다. |는 여러 정규 표현식 중 하나를 선택해서 대응시킵니다. |의 연산자 우선순위는 가장 낮습니다.

# 정규 표현식
/cat|dog/

# 문자열
I love cats
I like dogs
But what about cadog and catog?

# 정규 표현식
/100+1+|01/

# 문자열
1001100011
0110

cat|dog는 cat 또는 dog를 뜻하지, ca[td]og를 뜻하지 않습니다. 두 번째 예시의 경우 처음에 10011과 성공적으로 매칭되기 때문에 (1001도 해당 정규 표현식과 매칭됩니다) 뒤의 100011이 더 길게 매칭될 지라도 결과는 10011이 됩니다. 왜냐하면 정규 표현식 엔진은 가장 먼저 성공하는 결과를 반환하기 때문입니다.

또 하나 주목할 점은 10011 뒤의 01도 매칭이 되어야 하나 되지 않았다는 사실입니다. 기본적으로 매칭은 단 한 번만 이루어집니다.

그룹 (grouping)

그룹을 통해 정규 표현식을 묶어서 표현할 수 있습니다. 사용법은 상당히 직관적입니다. 소괄호로 묶으면 그룹이 됩니다. (cat|dog)이 예시이며, 괄호 뒤에 +나 *를 붙여서 반복횟수를 설정할 수도 있습니다. 이와 같은 그룹을 capturing group이라고 하며, 순서대로 그룹 번호가 지정됩니다.

그룹을 (?:cat|dog)으로도 나타낼 수 있습니다. 문법적인 기능은 똑같으나 그룹 번호가 지정되지 않는다는 차이가 있습니다.

# 정규 표현식
/-?\d+(\.\d+)?\s[-+*/]\s-?\d+(\.\d+)?/

# 문자열
3 = 1 + 2
4.35 * -12
1232-2.89

문자 클래스 안에 -를 넣고자 하면 맨 처음에 넣으면 됩니다.

역참조 (backreference)

그룹을 통해 매칭이 진행되면 매칭이 된 값이 내부적으로 저장이 되며, 이전에 매칭된 문자열을 다시 매칭하고자 할 때 사용할 수 있습니다. 첫 번째 그룹에서 매칭된 값을 다시 매칭하고자 하면 \1, 두 번째 그룹은 \2이며, 일반적으로 \99까지 지원합니다. 이 값은 프로그램에서 변수로도 받아올 수 있습니다.

# 정규 표현식
/([1-9]\d)\1/

# 문자열
2323
0101
45645

# 정규 표현식
/(([a-f])\2)+\1/

# 문자열
aa
acaaaccccaa
ffeeffaaccbbbb

두 번째 정규 표현식에 대해 설명해보겠습니다. \1은 첫 번째 그룹, 즉 (([a-f])\2)을 의미합니다. 이 그룹을 해석하면 aa, bb, cc, dd, ee, ff만 가능됩니다. 두 번째 그룹은 a, b, c, d, e, f만 매칭됩니다. 이 때 \1과 \2에는 가장 최근에 매칭된 문자열이 저장됩니다. ff까지 매칭이 되었을 때는 \2에는 f가 저장되며 (\1에는 ff가 저장됩니다) ee까지 진행되면 \2에는 새롭게 e가 저장되고 \1에는 새로 ee가 저장됩니다. 결과적으로 \2가 b이고 \1이 bb일 때 전 문자열이 매칭이 됩니다.

정방탐색 (lookaround)

정방탐색은 앵커와 비슷하게 zero-length token입니다. 다만 앵커와는 다르게 특정 위치에서의 글자에 대한 제약조건을 설정합니다. 제약조건을 거는 위치에 따라 전방탐색과 후방탐색으로 나뉩니다. 방향은 문자열의 진행방향과 일치합니다.

  • (?=) : 긍정 전방탐색(positive lookforward)으로, regex1(?=regex2) 꼴의 경우 regex1 뒤에 오는 문자열이 regex2와 대응이 될 때 대응됩니다.
  • (?!) : 부정 전방탐색(negative lookforward)으로, regex1(?!regex2) 꼴의 경우 regex1 뒤에 오는 문자열이 regex2와 대응이 되지 않을 때 대응됩니다.
  • (?<=) : 긍정 후방탐색(positive lookbehind)’으로, (?<=regex1)regex2 꼴의 경우 regex2 앞에 오는 문자열이 regex1과 대응이 될 때 대응됩니다.
  • (?<!) : 부정 후방탐색(negative lookbehind)’으로, (?<!regex1)regex2 꼴의 경우 regex2 앞에 오는 문자열이 regex1과 대응이 되지 않을 때 대응 됩니다.

일부 구현체는 후방탐색을 지원하지 않습니다.

# 정규 표현식
/a(?=p)/

# 문자열
an apple
leap year

# 정규 표현식
/\b\w+(?<!s)\b/

# 문자열
apparently...
Mary's
regularexpressions lookaround

두 번째 예제는 s로 끝나지 않는 단어와 매칭이 됩니다.

최대일치, 최소일치 (greedy, lazy matching)

정규 표현식 엔진은 기본적으로 주어진 위치에서 최대로 매칭을 진행하려고 합니다. 해당 성질을 ‘최소로’ 매칭하도록 바꿀 수 있습니다. 수량이나 반복을 의미하는 +, {} 뒤에 ?를 붙이면 됩니다.

# 정규 표현식
/\*\*.+?\*\*/

# 문자열
A **bold** text and another **bold** text.

# 정규 표현식
/\w{5,9}?/

# 문자열
strings
lazy manner

첫 번째 예제의 경우 뒤에 ?를 붙여 최소탐색으로 설정하지 않으면 **bold** text and another **bold**까지 매칭이 됩니다.

플래그 (flag)

정규 표현식의 패턴구분자 뒤에는 플래그를 붙일 수 있습니다.

  • g : 매칭이 된 이후에도 그 위치에서 다시 처음부터 매칭을 진행합니다. (global)
  • i : 대소문자의 차이를 무시합니다. (case-insensitive)
  • m : 각 줄의 시작이 ^와, 줄의 끝이 $와 대응됩니다. (multiline)
  • y : 변수 lastIndex의 값에 따라 시작 위치를 정하고, 그 위치에서만 매칭을 시도합니다. (sticky)
# 정규 표현식
/\b\w+\b/g

# 문자열
The quick brown fox jumps over......the lazy dog.

# 정규 표현식
/IMG\d+\.PNG/i

# 문자열
img0219.png
IMG02876.PNG

여담

정규 표현식 구현체

정규 표현식에도 표준이 있습니다. IEEE POSIX에서 제정을 하였으나 실질적으로는(de facto) Perl의 정규 표현식 시스템이 표준 취급을 받습니다. 다른 프로그래밍 언어도 정규 표현식 엔진을 제공하는 경우가 많으나 문자 클래스에서, 역참조 및 후방탐색 문법에서, 유니코드 지원에서, 그외 다양한 기능에서 차이가 나며, 한 정규 표현식이 다른 시스템에서는 작동하지 않거나 의도하지 않은 결과를 야기할 수 있습니다. 때문에 각 프로그래밍 언어가 제공하는 엔진의 특성과 API를 숙지할 필요가 있습니다.

정규 표현식 고급 기능

정규 표현식 엔진의 기본적인 원리는 모든 경우를 다 해보는 백트래킹이기 때문에 비효율적인 문구는 엄청난 성능 저하를 야기할 수 있습니다. 이를 Catastrophic Backtracking이라 부르며, 최악의 경우 지수 시간의 복잡도를 가질 수 있습니다.

때문에 아무리 탐색을 더 해도 현재 상태에서는 매칭이 되지 않을 경우 빠르게 백트래킹을 종료할 수 있게 도와주는 Atomic grouping, Possessive Quantifiers 등이 있습니다. 그 외에도 Character Class Subtraction, Forward Reference, Nested Reference, Infinite Recursion, Named Captured Group 등 정규 표현식의 확장성을 늘려주는 기능들이 존재하나 본 문서에서는 다루지 않습니다.

결론

당장은 정규 표현식이 그렇게 쓸모있어보이지도 않고, 언제 사용하게 될지 감이 오지 않을 수도 있습니다. 다만 문자열을 다룰 일은 생각보다 자주 생기며, 정규 표현식은 강력한 무기가 됩니다. 어떤 문자열이 올바른 이메일 주소인지 판별하는 것이 대표적인 예시입니다. 굳이 멀리 가지 않아도, 글을 쓸 때 들여쓰기를 제외하고 연속된 whitespace를 찾으려면 /(?<!^|\s)[ \t\r]{2,}/g를 통해 찾을 수 있습니다. 기본을 숙지해놓으시면 언젠가 정규 표현식을 유용하게 활용할 날이 올 것입니다.

참고자료

정규 표현식을 공부하고자 할 때 참고하면 좋은 사이트들입니다.

  • Regular-Expressions.info : 정규 표현식 설명 사이트의 알파이자 오메가입니다. 정규 표현식을 제대로 공부하고자 싶으면 이 사이트만으로 충분합니다.
  • RegExr : 정규 표현식을 시험해보고자 할 때 좋은 사이트입니다.
  • Regex Golf : 정규 표현식의 한계를 시험해보는 사이트입니다. 정규 표현식으로 3의 배수나 소수가 매칭이 되게 할 수 있을까요?