정규표현식 - 03. 프로그래머를 위한 고급 정규표현식
다양한 언어로 배우는 정규표현식을 보고 제 나름대로 정리한 내용입니다.
3장에서는 접합/선택/반복의 기본 3연산만으로 구성되는 정규표현식으로 기술할 수 있는 패턴이 무엇인지 설명한다. -> 기본부터 잘 알아야한다.
- 기본 3연산만으로 구성되는 정규표현식으로 기술할 수 있는 패턴 -> [[정규 언어]]
- 정규표현식의 패턴은 단어라는 의미이다.
단순한 정규표현식과 정규언어
정규표현식에 일치하는 문자열의 집합 = 정규 언어
집합의 기준
a*b*
라는 정규표현식에 일치하는 문자열- 공백문자열, ab, aab, aabb... 무한히 존재함 ->
a*b*
정규 언어는 무한히 존재한다.
- 공백문자열, ab, aab, aabb... 무한히 존재함 ->
문자 집합
- 집합이란 무언가를 모아놓은 것을 뜻한다.
- 문자 집합
- 심볼 또는 기호들로 이루어진 집합
- 문자 집합
- 우리는 10진수로 숫자를 표현할 때 {1,2,3,4,5,6,7,8,9,0}을 사용하며 이는 아스키 코드 집합에 속해져 있는문자들이다.
- 전세계 문자를 처리하는 표준 규격 유니코드는 113021개의 문자가 등록되어있다.
- 지금까지 열거한 문자 집합들은 모두 문자의 종류가 유한하다는 공통점이 있다.
- 집합론에서는
문자 집합은 유한 집합이다
라고 한다.
- 집합론에서는
문자열 집합
$\sum^*$
- 이 기호는 문자집합 $\sum$을 조합하면 만들어낼 수 있는
모든 문자열
의 집합을 나타낸다. - $\sum^*$는 $\sum$상의 모든 문자열의 집합이다.
- 단, 여기서말하는 문자열은 유한 개수만큼 나열한 것이라고 생각하자.
- $\sum = {0, 1}$의 $\sum^*$은 ${0, 1, 00, 11, 10, 01, 100, ...}$ 이다. 즉, 모든 바이너리 문자열 집합을 의미한다.
- $\sum^*$ 는 공백 문자열을 포함한다.
- 아무것도 없는 문자열도 문자열로 처리한다는 뜻이다. 이 책에서는 공백문자를 입실론($\mathcal{E}$)으로 표기한다.
- $w$를 0회 반복한 문자열은 공백문자열이다.
- $\sum^*$ 는 무한 집합이다.
- 무한한 요소를 가지기 때문에 얼마든지 길어질 수 있다.
- 집합론에서는 무한 집합이라고 한다.
집합의 작성법: 외연적 기법과 내포적 기법
- 외연적 기법
- ${}$안에 모든 요소를 열거
- 내포적 기법
- ${n|n은 0 이상 10 이하의 자연수}$
- 함수와 비슷한 꼴이다.
언어 = 문자열집합
- 형식 언어 이론에서는 문자 집합 $\sum$ 상의 언어란 문자열 집합 $\sum^*$ 의 부분 집합을 가리킨다.
a
는a*
에 포함되듯?
- 이 책에서는
계산적/수리적으로 기술할 수 있는 언어
를 중점으로 다룬다.- 계산적/수리적으로 기술
- 불가한 케이스
- 바른 문법의 한글
- 가능한 케이스
- ${ w | w 는 0^(10^10^*)에 일치하는 문자열}$
- 짝수개의 1을 포함하는 바이너리 문자열을 뜻한다.
- ${ w | w 는 0^(10^10^*)에 일치하는 문자열}$
- 불가한 케이스
- 계산적/수리적으로 기술
단순한 정규 표현식
- 초기 정규표현식에는 기본 3연산인 접합/선택/반복 이 세가지 연산밖에 없었다. 물론 이 연산만으로도 URI처럼 복잡한 패턴을 표현할 수 있다.
- 정규표현식을 집합으로 표현하기
- 임의의 정규표현식
r
, 그r
에 일치하는 문자열 집합L(r)
,L(r)
은r
의 수락 문자열 집합이라고 부르기로 한다. 1(0|1)0
이라는 정규표현식을 예시로 들어보면- $L(1(0|1)0) = {100,110}$
- 일반적으로 반복연산자인
*
(클레이니 연산자)를 포함하는 경우에는r
에 일치하는 문자열 집합은 무한 집합이 된다.
- 임의의 정규표현식
정규표현식으로 표현할 수 있는 언어
- 정규표현식으로 표현할 수 있는 언어 === 정규 언어
- 모든 정규 언어에는 반드시 그것을 표현하는 정규표현식이 존재하며, 정규표현식은 정규 언어를 표현하기 위한 방법중 하나일 뿐이다. 이외에도 유한 오토마타, 유한 모노이드 등이 있다.
현대 정규표현식의 다양한 기능/구문/구현
기본 3연산인 접합/선택/반복외의 다양한 기능을 설명한다.
정규표현식의 다양한 기능 추가 흐름과 다양하 엔진이 존재하는 이유
- 정규표현식의 기능 추가 흐름은 개발 역사와 맞물려 있는데, 개발이 고도화되며 각기 다른 목적의 정규표현식 엔진들이 만들어지게 되었다.
정규표현식 엔진간 기능 구현/구문 차이
- 30종이 넘는 유명한 정규표현식 엔진이 존재하지만, 주요 정규 표현식 엔진들은 다음과 같다.
- 펄
- PCRE
- 루비
- 자바스크립트
- Google RE2
- 참고로 구글의 제프딘이 참여했었다.
- GNU grep 등
- 엔진마다 지원하는 기능들이 각자 다르다.
- 캡쳐 관련 기능/구문
- 참고로 최근 자바스크립트 스펙에서는 이름 지정 캡쳐 기능이 추가되었다.
- 확장 기능인 전방/후방 탐색
- 재귀
- 역참조
- 캡쳐 관련 기능/구문
- 각 정규표현식 엔진들의 구조를 이해하게되면 성능최적화를 하는데 큰 도움이 되기 때문에 어떤 구조로 동작하고 있는지 알아 두는것이 좋다.
- 크게 두 종류로 나누는 엔진 종류
- DFA
- 속도 중심
- VM
- 기능 중심
- DFA
- 크게 두 종류로 나누는 엔진 종류
기본 엔진의 벤치마크
- 자바스크립트 업계에서는 JIT 컴파일을 도입하면서 서로간의 엔진 경쟁이 심해졌다. 이는 webkit을 프로젝트를 시작한 애플이 가장 먼저 도입하면서 시작되었다.
- 엔진의 종류마다 탄생하게된 목적이 다르듯 정규표현식마다 특정 엔진이 우세한 성능을 보인다.
- 특정 정규표현식은 특정 엔진에 엄청난 성능 부하를 일으키기도 한다.
a[^x]{20}b
를 DFA 엔진에서 사용하면 상태 수 폭발로 인해 엄청 느리다.
읽기 쉬운 정규표현식 작성
정규표현식을 깊게 이해해도 결국 읽기 실무에서는 읽기 쉬운 정규표현식을 작성해야한다.
간단히 작성하기
.*hoge.*fuga.*piyo.*|.*hoge.*piyo.*fuga.*|.*fuga.*hoge.*piyo.*|.*fuga.*piyo.*hoge.*|.*piyo.*hoge.*fuga.*|.*piyo.*fuga.*hoge.*|
- 위 정규표현식은 전방 탐색을 통해 AND 연산으로 짧게 대체할 수 있다.
(?=.*hoge.*)(?=.*fuga.*)(?=.*piyo.*)
- 전방탐색후 다음 전방탐색 그룹에게 커서를 넘기고 다시 커서를 되돌리며 검색한다. (루프처럼 동작)
- 위 정규표현식은 전방 탐색을 통해 AND 연산으로 짧게 대체할 수 있다.
- 가독성 좋은 정규표현식 작성하기
- 그룹화, 수량자, 문자 클래스, 이스케이프를 활용하자
02-[0-9][0-9][0-9][0-9]-[0-9][0-9][0-9][0-9]
는02(-\d{4}){2}
로 작성할 수 있다.
- 전방 탐색이나 후방 탐색 기능을 적극 활용하자.
- 단 팀원들이 이 기능을 이해하고 있다는 전제하에 사용해야 한다.
- 정규표현식을 부품화 하자.
- 그룹화, 수량자, 문자 클래스, 이스케이프를 활용하자
설명 형식으로 적기
- 정규표현식도 설명 형식으로 작성가능하다.
- 이름 지정 캡쳐 사용하기
DD/MM/YYYY
(\d{2})\/(\d{2})\/(\d{4})
- 뭐가 뭔지 한눈에 안들어온다.
(?<day>\d{2})\/(?<month>\d{2})\/(?<year>\d{4})
- 아 날짜 문자열이구나~
- 아래와 같은 방법도 가능하다.
/(\d{2}) \/ # 일(\d{2}) \/ # 월(\d{4}) # 년/
- 이름 지정 캡쳐 사용하기
현실적으로 타협하기
이 세상에는 도대체 이런 정규표현식을 누가짠거야? 라는 생각이 들 정도로 복잡한 정규표현식이 많이 존재한다.
엄격한 정규표현식
- 이메일은 작성하는 사람의 입장에서는 간단한 패턴으로 이루어진 문자열이지만, 이를 위한 정규표현식은 매우 복잡하다.
- HTML5에서는 이메일 검증을 위해 다음 정규표현식을 사용한다./^[a-z0-9!#$%&'*+\/=?^_`{|}~.-]+@[a-z0-9](?:[a-z0-9-]{0,61}[a-z0-9])?(?:\.[a-z0-9]([a-z0-9-]{0,61}[a-z0-9])?)*$/iD
- RFC 정의 표준에는 이 정규표현식이 표준 문법을 따르지 않다고 강조하고 있다. 그 이유는 실용성 때문이다. RFC의 사양을 읽고 제대로 해석하는 것부터 어려우며 메일 주소 문법을 제대로 쉽게 설명하는 사이트도 찾기 힘들다. HTML5가 제공하는 이메일 정규표현식이 오히려 메일 주소 정규표현식의 표준을 제공하는게 오히려 도움이 되는 것이다.
- 서울의 전화번호를 엄격하게 제한하려면
02(-\d{4}){2}
로 작성하면 된다. 하지만 모든 번호를 포함하지는 못한다. 시내 국번을 포함하거나 앞자리가 3자리인 경우도 있다. 물론 모든 전화번호를 나열하면 정규표현식을 만드는것이 가능하다. 비슷하게 세상에 존재하는 모든 URI도 정규표현식을 만드려면 모든 URI에 request를 보낸 후 응답이 있는 URI를 나열하여 정규표현식을 만들 수 있다. 그런데 이는 매우 비효율적이다.
절충형 정규표현식
- 어느 정도 복잡성을 가진 패턴을 작성하는 것은 도구의 힘을 빌려야한다. 아니면 절충하여 사용하고 있는 언어의 힘을 빌려야한다.
- 예시) if문으로 먼저 큰 패턴을 제외시킬 수 있다.
- 절충형 정규표현식 작성시 선택해야할 점
- 맞는 문자열에 일치한다 -> false nagative
- 맞지 않는 문자열에는 일치하지 않는다. -> false positive
- false nagative
- 표현하고 싶은 언어에 포함되는 더 작은 언어를 유사하다고 간주한다. -> 더 작은 범주 -> 통과해야할게 통과 못할 수도 있다.
- false positive
- 표현하고 싶은 언어를 포함하는 더 큰 언어를 유사하다고 간주한다. -> 더 큰 범주 -> 통과하면 안되는게 통과할 수도 있다
- 실무에서는 false negative를 사용하는것이 좋다.
Tags
Edit this page
최근 수정 시각 11/6/2022