HTML을 정규 표현식만으로 파싱할 수 있을까?

이번 포스팅에서는 이름만 들어도 땀이 나기 시작하는 마성의 그 녀석, 정규 표현식에 대한 세 번째 이야기를 해보려고 한다.

필자도 알고 여러분도 알고 세상 모두가 다 알다시피 정규 표현식은 평소 악랄한 문법으로 유명한 녀석이기 때문에, 지난 번 필자가 썼던 불규칙 속에서 규칙을 찾아내는 정규 표현식 포스팅처럼 정규 표현식의 문법을 분석하고 사용법을 알려주는 포스팅들 또한 굉장히 많다.

반면 그 악랄한 문법에 익숙해지고 나면 문자열과 관련된 굉장히 다양한 문제를 짧은 정규 표현식만으로 빠르게 해결할 수 있기 때문에, 개발자들에게는 상당한 애증의 대상이라고 할 수 있다. (필자 주변 개발자들도 대부분 정규식 별로 안 좋아한다…)

그래서 정규 표현식으로 어떤 문제를 해결할 때, 구글링을 통해 찾은 정규 표현식을 복붙하거나 regexr 같은 사이트에서 삽질을 하며 해결하는 경우가 많은데, 이 과정에서 잘못된 정규 표현식을 아무 검증없이 사용하여 피를 보는 케이스가 왕왕 존재한다.

물론 어떤 정규 표현식을 보고 이게 올바른 정규 표현인지 아닌지를 파악하는 것은 쉽지 않다. 하지만 정규 표현식이라는 것이 왜 세상에 나오게 되었는지, 어떤 환경에서 구동되는 것을 전제로 만들어진 것인지부터 알고 나면 자연스럽게 정규 표현식의 한계점도 이해할 수 있게 된다.

이번 포스팅에서는 필자와 같은 프론트엔드 개발자에게는 너무나도 익숙한 HTML이라는 언어를 정규 표현식만으로 파싱할 수 있는가라는 질문을 통해 정규 표현식이 개발된 목적과 한계에 대해서 이야기 해보려고 한다.

잘못된 정규 표현식이 만드는 야근 상황

본격적인 설명에 들어가기에 앞서, 잘못 작성된 정규 표현식이 어떤 상황을 불러올 수 있는지부터 함께 살펴보자.

필자가 이 포스팅에서 이야기하는 잘못 작성된 정규 표현식은 “정규 표현식이 a를 찾아야 하는데, b를 찾았어”와 같은 느낌은 아니다. 사실 이런 문제는 그냥 정규 표현식 문법이 익숙하지 않아서 실수한 것이기 때문에, 시간을 가지고 정규 표현식을 조금만 자세히 들여다 보면 누구든지 잘못 작성한 표현을 찾아낼 수 있다.

필자가 이야기하고 싶은 것은 정규 표현식이 작동하는 원리를 잘 모르고 사용했을 때 발생할 수 있는 퍼포먼스 이슈나, 혹은 정규 표현식으로는 아예 해결이 불가능한 문제를 어떻게든 해결하려고 붙잡고 있는 슬픈 상황들이다.

물론 개발자들이 이런 원리 같은 건 몰라도 정규 표현식을 사용할 수 있도록 정규 표현식 엔진이라는 추상화 계층이 존재하는 것이기는 하지만, 그렇다고 너무 엔진만 믿고 있다가는 믿었던 정규 표현식한테 뒷통수를 얻어맞는 상황이 얼마든지 발생할 수 있다.

영원히 끝나지 않는 정규 표현식

첫 번째 뒷통수 상황은 정규 표현식이 패턴을 매칭하는 과정을 잘 모르고 사용했을 때 발생할 수 있는 퍼포먼스 이슈이다.

정규 표현식은 DFS(깊이 우선 탐색) 알고리즘을 기반으로 하는 백트래킹 알고리즘을 사용하여 문자열의 패턴을 매칭한다. 즉, 어떤 노드를 어떤 조건으로 탐색하냐에 따라서 패턴을 매칭하는 시간이 생각보다 많이 길어질 수도 있다는 것이다.

특히 자바스크립트 엔진에 포함되어있는 정규 표현식 엔진은 비동기가 아닌 동기식으로 작동하기 때문에 정규 표현식이 패턴 매칭하느라 시간을 오래 잡아먹는다면, 그 시간 동안 다른 일을 전혀 수행할 수 없는 눈물나는 상황이 발생할 수도 있다.

이게 어떤 상황인지 이해가 되지 않는다면 브라우저에서 새 탭을 열고 아래 코드를 콘솔에서 실행해보도록 하자. (이 탭에서 하면 글을 못 읽을테니 다른 탭에서 하자…)

// 문자열 길이와 상관없이 무조건 탐색 8회
/^(\d+)*$/.test('123123123123123123');

// 탐색 26회
// 이 정도는 금방 끝난다
/^(\d+)*$/.test('123!');

// 탐색 98,306회
/^(\d+)*$/.test('123123123123123!'); 

// 어...? 연산이 안 끝난다....
/^(\d+)*$/.test('123123123123123123123123123123123123123123!'); 

첫 번째 예시는 문자열 길이와 상관없이 무조건 8회의 탐색만으로 빠르게 패턴을 매칭하고 결과를 반환하지만 두 번째 예시를 보면 문자열 끝에 특수문자가 하나 붙었을 뿐인데 연산 횟수가 기하급수적으로 늘어나더니, 급기야 연산이 끝나지 않는 수준까지 도달한다.

만약 이런 상황이 실제 비즈니스 어플리케이션에서 발생했다면 유저는 어떠한 UI 요소와도 상호 작용을 하지 못하고 멈춰버린 화면만 보고 있게 될 것이다. 심지어 이런 정규 표현식의 작동원리를 악용하여 시스템을 멈추게 하는 ReDoS라는 공격 방식도 존재한다.

바로 이런 경우가 정규 표현식의 작동 원리를 제대로 알지 못하고 사용하게 되면 가끔 맛 볼 수있는 야근 상황이다.

더 화딱지가 나는 건 저런 정규 표현식을 작성해도 그저 수행 시간만 기하급수적으로 늘어날 뿐 에러는 아니라는 것이다. 그래서 믿었던 정규 표현식한테 뒷통수 맞기가 더 쉬운 상황이다. 게다가 이런 종류의 에러는 진짜 찾기도 힘들다. (어찌어찌 찾았아도 정규 표현식이 원인이란 걸 알면 눈앞이 막막해진다…)

내 야근이 잘못 작성한 정규 표현식 한 줄 때문이란 것을 알았을 때의 표정.jpg

이렇게 백트래킹 알고리즘을 사용하는 정규 표현식의 특성 상 어떤 탐색 과정을 거치냐에 따라서 퍼포먼스가 많이 떨어질 수도 있기 때문에, 정규 표현식을 사용할 때는 이런 뜻하지 않은 상황이 발생할 수도 있다는 것을 항상 염두에 둬야한다.

정규 표현식으로는 해결할 수 없는 문제

그리고 두 번째 뒷통수 상황은 정규 표현식만으로는 절대 해결할 수 없는 문제를 정규 표현식으로 해결하려고 하는 상황이다.

첫 번째 상황은 퍼포먼스 모니터링을 통해 “정규 표현식이 이상한데?”라는 문제라도 알아낼 수 있지만, 이 두 번째 상황은 정규 표현식의 원리와 한계를 모른다면 진짜 일주일 내내 삽질만 하며 시간만 날릴 수도 있는 상황이기 때문에 개인적으로는 이 두 번째 상황이 조금 더 슬픈 상황이라고 생각한다.

아래에서 다시 후술하겠지만, 사실 정규 표현식은 세상 모든 문자열의 패턴을 찾아낼 수 있는 만능 열쇠가 아니라 오히려 엄격한 한계가 존재하는 도구이다.

대표적으로 HTML, CSS와 같이 무한하게 열릴 수 있는 태그나 괄호가 존재하는 언어는 정규 표현식으로 검증이 불가능하다. 그래서 이 포스팅의 제목이었던 “HTML을 정규 표현식으로 파싱할 수 있을까?”라는 질문에 대한 대답은 바로

"No" 이다.

만약 여러분이 HTML을 정규 표현식만으로 파싱하는 것은 불가능하다는 사실을 모르고 있었다면, 절대 해결할 수 없는 문제를 해결하기 위해 많은 시간을 날려먹을 수도 있다는 것이다.

그런데 필자를 포함한 많은 분들이 평소에 정규 표현식을 사용하여 HTML 태그가 올바르게 열리고 닫혔는지를 검사해본 경험이 있는데, 왜 필자는 정규 표현식으로 HTML을 파싱할 수 없다고 이야기하는 것일까?

그 이유를 알기 위해서는 정규 표현식이라는 도구가 어떤 맥락에서 개발된 것인지, 어떤 환경에서 구동되는 것을 전제로 하고 있는 것인지를 살펴보며 정규 표현식이 가지고 있는 한계가 무엇인지 알아봐야 할 필요가 있다.

정규 표현식은 왜 만들어진 것일까?

개발자들에게 정규 표현식이라는 단어는 이미 익숙하다. 개발자들 사이에서 정규 표현식의 줄임말인 정규식을 규식이형처럼 변형해서 부르는 것이 밈이 될 정도이기도 하니 말이다.

하지만 정규 표현식이 왜 “정규 표현식”이라는 요상한 이름으로 불리는 지를 궁금해 하는 사람은 그렇게 많지 않다. 그러니 정규 표현식이 정확히 어떤 역할을 하는 도구인지를 알기 위한 첫 걸음으로 우리에게 이미 익숙한 이 “정규 표현식”이라는 이름의 의미부터 한번 생각해보도록 하자.

정규(正規)라는 단어의 의미는 규칙적인 무언가, 패턴이다. 즉, 정규 표현이라는 것은 결국 말 그대로 규칙적인 패턴을 표현하고 있다는 의미이기 때문에 우리는 일반적으로 정규 표현식이 문자열에서 내가 원하는 패턴을 매칭하는 도구라고 알고 있다.

이 패턴이라는 단어는 12121212처럼 단순히 반복되는 규칙만을 의미하는 것이 아니라, 우리가 정규 표현식을 사용할 때 정의하는 규칙처럼 “a가 2번 나오고 그 뒤에 바로 b가 나타난다”와 같이 사용자가 정의하는 모든 규칙까지 포함하는 의미이다.

이처럼 정규 표현식의 가장 기본적인 용도는 문자열 속에서 패턴을 찾는 것이지만, 사실 정규 표현식은 단순히 문자열의 패턴을 찾을 수 있다는 니즈만을 위해서 만들어진 것이 아니다. 그렇다면 정규 표현식은 도대체 무엇을 위한 패턴을 표현하고 있는 것일까?

기계가 알아들을 수 있는 언어를 표현해보자

앞서 이야기했듯이 정규 표현식은 어떤 패턴을 표현하기 위해 태어난 도구이지만, 사실 정규 표현식의 탄생 배경을 이해하려면 “왜 문자열 내에서 패턴을 찾으려고 했는지”를 아는 것이 더 중요하다.

결론부터 이야기하자면 정규 표현식의 시작은 바로 기계가 알아들을 수 있는 언어를 표현하기 위한 고민에서부터 출발했다. 즉, 기계가 언어라는 개념을 인지할 수 있도록 언어를 수학적으로 표현하기 위해 태어난 개념이라는 것이다.

1951년, 처음으로 정규 집합을 사용하여 언어를 수학적으로 기술한 클레이니 형

단, 이 시절에 이야기하는 기계가 알아들을 수 있는 언어라는 것은 오늘 날 연구하고 있는 것처럼 사람이 사용하는 자연어 같은 고수준의 언어를 의미하는 것은 당연히 아니다.

여기서 언어라고 하는 것은 한국어나 영어 같은 자연어가 아니라 조금 더 추상적인 의미이다. 평소에 우리가 사용하는 프로그래밍 언어도 “언어(Language)“라고 부르는 것처럼 컴퓨터 과학과 수학의 세계에서 언어라는 것은 단순히 어떤 특정한 규칙을 가진 문자열의 집합을 의미하기 때문이다.

수학적으로 정의된 언어의 의미

우리는 언어라고 하는 것이 무엇인지 느낌적으로는 알고 있지만 정확히 이게 무엇이라고 고민해본 적은 많이 없을 것이다.

하지만 컴퓨터 과학이나 수학의 세계에서는 이런 느낌적인 지식을 절대 허용하지 않기 때문에, 언어라는 개념을 이 세계에서 사용하고 싶다면 언어가 정확히 어떤 것이라고 정의하는 과정이 반드시 필요하다.

사실 수학과 컴퓨터 과학에서 정의하는 언어라는 것은 단순하게 어떤 문자열들의 집합을 의미하는 것 그 이상 그 이하도 아니다.

자바스크립트는 대충 이런 문자열들이 모인 집합이지 않을까

하지만 당연하게도 아무 문자열이나 막 집어넣은 집합을 의미하는 것은 아니기 때문에, 언어를 구성하는 문자열의 집합은 반드시 다음 3가지 조건을 만족해야한다.

1. 유한한 길이의 기호들의 집합 S가 반드시 존재한다
2. S의 원소들로 만든 문자열의 집합인 S*를 형성하는 규칙이 반드시 존재한다
3. 규칙에 맞게 만들어진 문자열들이 어떤 의미를 가지는지 결정할 수 있다

즉, 이 3가지 조건을 만족하는 문자열의 집합은 정말로 기초적인 언어라고 부를만한 자격이 되는 것이다. 이제 언어의 정의에 대해 알았으니 이제 1번부터 하나하나 만족시켜보면서 언어를 만들어보도록 하자.

우선 첫 번째 조건인 기호들의 집합 S는 무엇을 의미하는 걸까?

잘 생각해보면 지구 상에 존재하는 모든 언어들은 그 언어에서 사용되는 기호들을 가지고 있다. 한글은 ㄱ, ㄴ, ㄷ과 같은 자음과 ㅏ, ㅑ, ㅓ 같은 모음을 나타내는 기호들, 그리고 영어는 a, b, c와 같은 기호들을 가지고 있는 것 처럼 말이다. 우리는 이런 기호들의 모음을 “알파벳”이라고 부르고, 바로 이 알파벳이 언어의 첫 번째 조건인 기호들의 집합 S이다.

그럼 한번 알파벳을 정해보도록 하자. 필자는 이 예시에서 그냥 소박하게 a, b라는 간단한 기호 2개로만 알파벳을 구성하려고 한다.

S = ['a', 'b']

자 이제 언어의 첫 번째 조건인 “유한한 길이의 기호들의 집합 S“를 만들었다. 다음으로는 ”S의 원소들로 만든 문자열의 집합인 S*“를 만들 차례이다. 두 번째 조건을 보면 이 문자열의 집합을 형성하기 위해서는 어떠한 규칙이 필요하다고 한다.

그리고 이 규칙이 바로 이 언어의 문법(Syntax)를 의미한다. 지구 상에는 같은 알파벳을 사용하는 언어가 한 두개가 아니기 때문에, 이 두 번째 규칙, 즉 문법이 이 언어의 특색을 만들어낸다.

[같은 라틴 알파벳을 쓰지만 문자열을 조합하는 규칙이 다름]

영어: I love you
프랑스어: je t'aime
이탈리아어: ti amo

위 예시에서 볼 수 있듯이 영어에서 사용되는 라틴 알파벳은 프랑스어나 이탈리아어에서도 대부분 사용되고 있다. 똑같이 “사랑”이라는 의미를 가진 단어라고 해도 영어는 love라는 4개의 알파벳이 조합된 문자열로 표현하고, 프랑스어는 l'amour라는 '를 포함하여 7개의 알파벳이 조합된 문자열로 표현할 수 있는 것을 생각해보면 된다.

그래서 알파벳만 정의한다고 해서 어떤 언어를 정의했다고 말하기가 어렵다는 것이다. 필자는 이 문자열의 집합 S*의 규칙을 “알파벳 a와 b로 만들 수 있는 모든 3자리 이하의 글자”라고 정하도록 하겠다. 그럼 필자가 만들고 있는 이 언어를 구성하는 문자열의 집합 S*는 이런 모양이 될 것이다.

S* = [
  "",
  "a", "b",
  "aa", "ab", "ba", "bb",
  "aaa", "aab", "aba", "abb",
  "baa", "bab", "bba", "bbb",
]

이제 두 번째 조건인 ”S의 원소들로 만든 문자열의 집합인 S*를 형성하는 규칙”도 정의하고나니 필자의 언어가 어떤 문자열들을 포함하고 있는 집합인지 알 수 있게 되었다. 여기까지 오고나면 사실 마지막 조건은 자동으로 충족된다.

필자가 S*의 규칙으로 정의한 조건인 “알파벳 a와 b로 만들 수 있는 모든 3자리 이하의 글자”는 유한한 개수의 문자열의 원소만 만들 수 있기 때문에, 이렇게 만들어진 모든 문자열에 의미를 각각 부여해주는 것이 가능하기 때문이다.

a = 배가 고파요
b = 퇴근하고 싶어요
aa = 서버에서 500이 떨어져요
...

필자는 이렇게 단 5분 만에 언어의 조건 3개를 모두 충족시켜서 허접한 언어를 만들어낼 수 있었다. 앞으로의 설명에서 이 언어는 “에반어”라고 부르도록 하겠다.

기계야 내 언어를 이해해줘

사실 어떤 언어를 만드는 규칙 자체는 단순하기 때문에 누구라도 에반어처럼 허접한 언어를 만들어낼 수는 있다. 그런데 문제는 이 언어를 기계가 이해할 수 있냐는 것이다.

결국 어떤 기계가 언어를 이해할 수 있다는 것은 이 언어를 구성하는 문자열에 특정한 패턴이 있어야 한다는 의미이다. 즉, 언어를 구성하는 문자열의 패턴을 수학적으로 표현할 수만 있다면 이 언어는 기계가 이해할 수 있는 언어라고 이야기할 수 있는 것이다.

물론 같은 언어라고 해도 우리가 일상 속에서 사용하는 한국어, 영어와 같은 자연어는 문맥이 굉장히 자유롭고 시대의 흐름에 따라 문법이나 의미가 변경되는 일도 있기 때문에 절대적인 패턴이라는 것이 존재할 수 없다. 하지만 필자가 방금 만든 에반어처럼 문자열들을 구성하는 규칙이 명확하다면 이것은 기계가 이해할 수 있는 언어가 된다.

필자가 만든 에반어는 a와 b로 이루어진 3자리 이하의 문자열이라는 명확한 규칙이 존재하기 때문에 이렇게 수식으로 표현하는 것이 가능하다.

에반어는 “a, b로 만들 수 있는 3자리 이하의 문자열”의 집합으로 구성되어 있는 언어이기 때문에 빈 문자열 또한 이 규칙에 포함된다. 그래서 수식에서도 빈 문자열을 뜻하는 $\epsilon$(앱실론)을 각 자리마다 더해주는 방식으로 표현해야하며, 위 식이 표현하는 문자열의 집합으로 구성된 언어, 에반어도 빈 문자열인 $\epsilon$을 포함하고 있다.

그리고 이 수식을 기계가 알아들을 수 있게 특정한 언어로 바꿔준 것이 바로…

^[ab]{0,3}$

우리가 일반적으로 알고 있는 정규 표현식인 것이다.

즉, 기계가 언어를 인지하기 위한 첫 번째 발걸음은 언어를 구성하는 문자열이 생성되는 “규칙”을 표현할 수 있는 방법을 만드는 것이고, 이게 바로 정규 표현식의 기원이다. 위키피디아의 정규 표현식 항목을 보면 이 맥락이 정규 표현식의 정의에 그대로 녹아있는 것을 볼 수 있다.

정규 표현식(正規表現式, 영어: regular expression, 간단히 regexp[1] 또는 regex, rational expression)[2][3] 또는 정규식(正規式)은 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어이다.

물론 필자가 이 포스팅에서 설명하고 있는 언어의 정의는 굉장히 단편적인 내용을 이야기하고 있는 것이므로, 이 부분에 대해 더 관심이 있으신 분들은 “형식 언어”, “촘스키 위계” 등의 키워드로 구글링을 한번 해보는 것을 권한다.

정규 표현식이 구동되는 환경, 유한 오토마타

우리는 이제 정규 표현식이라는 것이 단순히 문자열의 패턴을 표현하기 위한 언어가 아니라, 언어를 기계에게 인지시키기 위한 노력의 과정 끝에 태어난 기술이라는 것을 알게 되었다. 그런데 필자가 아까부터 “기계”라는 말을 계속 하고 있는데, 이 기계는 도대체 무엇을 말하는 것일까?

참고로 정규 표현식이라는 개념이 태어난 년도는 1951년이다. 물론 이 당시에도 컴퓨터라는 것이 있기는 했지만 컴퓨터의 메모리로 수은을 쓰네 자기코어를 쓰네 어쩌네하던 질풍노도의 시기였기 때문에, 현재 우리가 일반적인 프로그램을 작성할 때처럼 메모리의 한계성에 대한 큰 걱정없이 코딩하던 시대는 아니였다.

그래서 이 시기에 기계를 대상으로 하는 연구는 우리가 생각하는 컴퓨터가 아니라 그냥 계산 능력이 있는 기계를 머릿 속으로 상상해서 진행하는 경우가 많았다. (본격 상상코딩의 원조…)

본격 1952년 발 최신형 컴퓨터의 메모리인 자기 드럼의 위용

그 중에서도 정규 표현식은 유한 오토마타라는 추상 기계가 알아들을 수 있는 언어를 표현하는 연구에서 파생된 이론이다.

오토마타는 자동(Auto) 기계(Mata)라는 의미인데, 이건 말 그대로 자동화된 추상적인 기계이기 때문에 반드시 컴퓨터처럼 물리적인 장치가 필요한 것은 아니다. 그냥 이론이나 설계로만 존재할 수도 있다는 것이다.

이렇게 오토마타를 연구하는 학문은 근본적으로 어떤 기계가 할 수 있는 것은 무엇이고 할 수 없는 것은 무엇인지에 대한 해답을 찾는 학문이기 때문에, 현재 우리가 공부하는 컴퓨터 과학의 모태가 되는 학문이라고도 볼 수 있다.

그 중에서도 유한 오토마타는 간단하게 얘기해서 유한 개의 상태 중 한 번에 하나의 상태만을 가질 수 있는 기계이다. 유한 오토마타를 설계할 때는 다이어그램을 사용하여 오토마타의 상태가 변경되는 과정을 그림으로 나타내게 되는데,대충 이런 느낌이다.

위 상태 전이도는 유한 오토마타의 상태가 어떻게 변경되는 지를 표현한 것인데, 이 기계는 인풋으로 어떤 문자열을 받아서 이 문자열이 a라면 상태1로 변경되며, 그 이후에 오는 문자열이 b라면 상태2로 변경되는 간단한 기계이다. 그리고 상태2는 이 기계가 변경할 수 있는 최종 상태이기 때문에 겹동그라미로 표현해주었다.

결국 이 기계가 인풋으로 어떤 문자열을 받은 후에 상태가 끝까지 나아갔다면 ab, aab, aaa...b 등의 문자열이라는 것이 보장되는 것이다. 그리고 이 기계는 a+b이라는 정규 표현식으로도 표현할 수 있다. 즉, 필자가 그린 기계와 a+b라는 정규 표현식은 개념적으로 같은 것이며, 이 정규 표현식은 위의 기계를 표현했다고 봐도 무방하다. (유한 오토마타와 정규 표현은 동치관계라고도 표현한다)

이렇게 어떤 상태에서 다른 상태로 변경될 수 있는 길이 하나 밖에 없는 기계는 위의 상태 전이도 그림만 봐도 이 기계가 어떻게 작동할 지 단번에 알 수 있다. 그 이유는 어떤 상태에서 다음 상태로 나아갈 수있는 길이 단 하나만 존재하기 때문인데, 이런 유한 오토마타는 상태가 변경되는 길이 이미 다 결정되어있다고 해서 결정적 유한 오토마타(Deterministic Finite Automaton, DFA)라고 불린다.

DFA는 이처럼 구조가 간결하고 기계의 상태를 모두 예측 가능하기 때문에 프로그램으로 작성하기도 편하고 효율도 잘 나오지만 한 가지 단점이 존재한다.

제한적인 상태 변경만 가능한 DFA로는 언어의 구조를 표현하기가 너무 빡세다...

이게 왜 어려운 걸까? 물론 방금 필자가 예시로 들었던 a+b라는 간단한 정규 표현식이라면 상태 전이도도 DFA로 간단하게 그려낼 수 있지만 만약 OR를 의미하는 (a|b)b같은 정규 표현식을 DFA로 표현하려고 하면 생각보다 빡세다. DFA는 어떤 인풋을 받았을 때 변경될 수 있는 상태가 무조건 한 개 뿐이어야 하기 때문이다. 이건 마치 if문 없이 조건을 처리해야 하는 상황이랄까.

이런 이유로 언어를 인식하는 기계를 표현할 때는 변경될 수 있는 상태가 반드시 한 개만 존재하는 DFA가 아닌 여러 개도 존재할 수 있는 기계를 표현하게 되는데, 이런 기계는 어떤 인풋이 들어오냐에 따라서 변경될 상태가 변경되기 때문에 상태 전이도만 봐서는 이 기계가 어떻게 작동할지 예측하는 것이 불가능하다.

그리고 이런 기계는 어떤 상태에서 다음 상태로 나아가는 길이 미리 결정되어있는 것이 아니라 인풋에 따라 길이 변경되기 때문에 비결정적 유한 오토마타(Nondeterministic Finite Automata, NFA)라고 한다.

위 기계는 빈 문자열을 의미하는 $\epsilon$을 받아들이는 것으로 시작하여, 그 다음 문자열이 a라면 상태2로, b라면 상태3으로 변경되는 구조를 가지고 있다. 즉, 어떤 상태에서 다른 상태로 변경될 수 있는 개수가 2개 이상인 것이다. 즉, 이 기계는 추상 전이도만 봐서는 특정 상태의 다음 상태가 무엇이 될지 알 수가 없기 때문에 “비결정”적 유한 오토마타라고 불리는 것이다.

이게 바로 정규 표현식이 구동되는 기계인 유한 오토마타의 대략적인 개념이며, 정규 표현식은 바로 이런 개념의 추상 기계에게 언어를 인지시키는 것을 목표로 만들어졌다. 여기서 분명히 짚고 넘어가야 할 점은 이 유한 오토마타라는 기계는 “기억할 수 있는 상태가 단 하나 밖에 없다는 것”이다.

바로 이 제약 조건으로 인해서 정규 표현식이라는 언어의 한계가 발생하게 된다.

정규 표현식의 한계

이처럼 정규 표현식으로 표현할 수 있는 언어, 즉 유한 오토마타가 이해할 수 있는 언어를 정규 언어(Regular Language)라고 부른다.

앞서 알아보았듯이 애초에 정규 표현식은 수학적으로 표현할 수 있는 규칙이 존재하는 언어를 표현하는 용도인데다가 한 번에 한 가지 상태만 가질 수 있는 유한 오토마타에서 구동되는 것을 전제로 하기 때문에 모든 언어를 다 표현할 수 있는 것이 아니다.

쉽게 생각해서 정규 표현식으로 문맥이 굉장히 자유로운 한국어나 영어같은 언어는 정규 표현식으로 표현할 수 없는 것을 생각해보면 된다. (애초에 자연어를 정규 표현식으로 표현할 수 있었으면 머신러닝을 쓰지도 않는다)

즉, 정규 표현식으로 표현할 수 있는 언어에는 분명한 한계가 있다는 것이며, 이렇게 정규 표현식으로 표현할 수 있는 언어를 정규 언어라고 부르는 것이다.

언어들의 위계를 표현한 촘스키 위계에서도 정규(Regular) 언어는 가장 아래 쪽을 차지한다.

사실 우리가 일반적인 비즈니스 레벨에서 다루는 문자열들 중에도 정규 언어가 아닌 것들이 꽤나 존재하는데, 그 중 대표적인 것이 바로 HTML 같은 언어이다. 즉, 어떤 문자열이 제대로 된 HTML인지 아닌지를 정규 표현식으로 알아내는 것은 불가능하다는 것이다.

어라? 저는 분명 정규 표현식으로 HTML을 매칭해본 적이 있는데요?

물론 필자도 정규 표현식으로 HTML을 매칭해본 경험은 있다. 하지만 아마 우리가 당시 HTML을 매칭할 때의 규칙은 전체 HTML이 유효한지 아닌지가 아니라 ”<div> 태그가 열렸다가 닫혔어?”와 같은 HTML의 일부분을 검증하는 작은 규칙이었을 것이다.

그렇다면 왜 필자는 정규 표현식으로 HTML의 유효성을 검증할 수 없다고 한 것일까? 그 답은 정규 표현식이 사실은 상태를 하나만 기억할 수 있는 유한 오토마타를 표현하고 있다는 것을 생각하며 HTML의 생김새를 보면 쉽게 알 수가 있다.

정규 표현식이 HTML을 이해하지 못 하는 이유

필자도 알고 여러분도 알고 모두가 알다시피 HTML은 어떤 태그가 열고 닫히며 그 내부에는 무한히 태그가 중첩될 수 있는 구조를 가지고 있다.

<main>
  <section>
    <h1>
      ...
    </h1>
  </section>
</main>

그렇다면 만약 어떤 기계가 이런 HTML 문자열을 인풋으로 받았을 때, 이 HTML이 유효하다는 것을 검증해내려면 어떻게 해야할까?

올바른 HTML이라고 부를 수 있는 문자열은 반드시 여는 태그와 닫는 태그가 함께 존재해야한다. 즉, 태그가 한번 열렸으면 무조건 닫혀야 한다는 것이다. 결국 올바른 HTML을 판별하는 기계는 문자를 하나씩 읽으면서 그와 동시에 태그의 열고 닫음을 알 수 있어야 한다는 것이고, 대충 이런 느낌으로 작동할 것이다.

1. <main> 문자열을 만났다. 이후 <main> 태그가 열렸다는 상태를 저장한다.
2. <section> 문자열을 만났다. 이후 <section> 태그가 열렸다는 상태를 저장한다.
3. …반복
4. </main> 문자열을 만났다. 만약 <main> 태그가 열린 상태가 저장되어있다면 올바르게 닫혔다고 판단한다.
5. </section> 문자열을 만났다. 만약 <section> 태그가 열린 상태가 저장되어있다면 올바르게 닫혔다고 판단한다.
6. 문자열의 끝까지 탐색했을 때 열린 상태로 끝난 태그가 없다면 이 HTML은 올바른 HTML이다.

여러분이 만약 이런 기계를 만든다고 생각해보자. 이 기계는 몇 개의 상태를 저장할 수 있도록 설계되어야할까?

답은 무한대이다

혹여나 잘 이해가 가지 않는다면, 여러분이 직접 HTML 파서를 만든다고 상상해보자. 앞서 말했듯이 이 파서는 태그가 열리고 닫혔다는 사실을 검증해야 하기 때문에, 문자열을 순차적으로 탐색하면서 어떤 태그가 열린 것을 의미하는 문자열을 만났다면 이 상태를 어딘가에 저장해놓아야 한다.

이때 어떤 방식으로 상태를 관리하는지는 사람마다 조금씩 다를 수 있지만 이렇게 쌍으로 열렸다 닫히는 괄호를 검증할 때의 정석은 스택(Stack)을 사용하는 방법이다.

이렇게 여는 태그를 만났을 때 스택에 Push하고
닫는 태그를 만났을 때 Pop하는 동작만 사용해도 허접한 HTML 파서는 구현 가능하다

태그가 아무리 중첩되어도 반드시 안 쪽에 있는 태그가 먼저 닫힐 수 밖에 없는 HTML 구조를 검증하기에는 마지막에 들어온 녀석이 반드시 먼저 나가야 하는 스택이 아주 찰떡궁합이기 때문이다.

하지만 여기서 문제는 바로 스택의 크기이다. 이 스택의 크기를 얼마나 크게 잡아야 어떤 문자열이든 소화할 수 있는 HTML 파서를 만들 수 있을까?

당연히 크면 클수록 좋다. 스택의 크기가 크면 클 수록 더 깊은 깊이의 트리로 이루어진 HTML도 파싱할 수 있기 때문이다. 하지만 결국 이 스택의 크기를 초과하는 트리를 가진 HTML이 파서에 들어오면 프로그램은 터질 수 밖에 없다. 즉, 어떤 문자열이든 소화할 수 있는 HTML 파서를 만드려면 스택의 크기를 무한하게 잡아야한다.

정규 표현식은 결국 유한 오토마타이다

이처럼 어떠한 기계가 HTML이 올바른지 아닌지를 검증하기 위해서는 무한 개의 상태가 필요하다. 하지만 정규 표현식은 단 한 개의 상태만을 가지는 유한 오토마타를 표현한 것이기 때문에 당연히 무한 개의 상태를 가져야 파싱할 수 있는 HTML을 절대 인지할 수가 없는 것이다.

결국 핵심은 정규 표현식이 상태를 하나 밖에 가질 수 없는 유한 오토마타를 표현하고 있다는 것이며, 상태를 하나 밖에 가질 수 없는 기계로는 절대 해결할 수 없는 문제가 존재한다는 것이다.

그러니 어떤 문자열을 보면 바로 정규 표현식으로 해결하려고 덤비기보다는 내가 이 문자열을 파싱하는 프로그램을 만든다고 생각해보았을때 “몇 개의 상태”가 필요한 지를 먼저 고민해보는 연습이 필요하다. 만약 두 개 이상의 상태가 필요하다면 일단 정규 표현식만으로 해결하기는 쉽지 않은 문제라고 판단할 수 있는 것이다.

물론 이런 상상 알고리즘은 익숙한 사람과 익숙하지 않은 사람의 문제 풀이의 차이가 존재하기 때문에 하나의 상태만으로 해결할 수 있는 문제를 여러 개의 상태가 필요하다고 생각할 수도 있지만, 그래도 알고리즘은 재능의 영역이 아니라 연습의 영역이므로 1년, 2년 꾸준히 하다보면 조금씩 감을 잡는 시간이 짧아질 것이다.

마치며

사실 정규 표현식의 한계는 그냥 “괄호의 깊이에 제한이 없는 문자열은 인지할 수 없다”처럼 간단한 말로도 설명할 수 있는 부분이다.

하지만 그냥 이렇게 설명하고 외우는 것 보다는 정규 표현식이 어떤 문제를 해결하기 위해 탄생한 도구인지, 어떤 컨셉을 가지고 있는지를 함께 이야기하면 조금 더 이해하기가 쉬울 것이라고 생각했다.

정규 표현식에 이런 한계가 존재한다는 사실을 모른다면 ”<ul> 태그 안에 <li> 태그가 존재하니?” 같은 제한적인 상황을 정규 표현식으로 해결했던 경험을 바탕으로, 해결이 불가능한 문제를 해결하려고 도전하게 될 수도 있다.

물론 정규 표현식이 문자열을 다룰 때 많은 편리함을 주는 것은 사실이다. 하지만 앞서 이야기 했듯 정규 표현식의 백트래킹 알고리즘은 예상하지 못 했던 퍼포먼스 이슈를 가져다 줄 수도 있고, 정규 표현식으로는 결코 풀지 못하는 문제도 존재하기 때문에 항상 정규 표현식이라는 도구를 사용한다고 선택하기 전에는 “이게 정말 효율적인 선택인지”에 대한 고민을 해보는 연습이 필요하다.

이상으로 HTML을 정규 표현식만으로 파싱할 수 있을까? 포스팅을 마친다.

• 잘못된 정규 표현식이 만드는 야근 상황

  • 영원히 끝나지 않는 정규 표현식
  • 정규 표현식으로는 해결할 수 없는 문제

• 정규 표현식은 왜 만들어진 것일까?

  • 기계가 알아들을 수 있는 언어를 표현해보자
  • 정규 표현식이 구동되는 환경, 유한 오토마타

• 정규 표현식의 한계

  • 정규 표현식이 HTML을 이해하지 못 하는 이유
  • 정규 표현식은 결국 유한 오토마타이다
• 마치며