[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
正規表現式 / Regular Expression프로그래밍에서 문자열을 다룰 때, 문자열의 일정한 패턴을 표현하는 일종의 형식 언어를 말한다. 정규식이라고도 부르며, 보통 RegEx 혹은 RegExp라 많이 쓴다.
2. 설명
프로그램을 작성할 때는 특성상 일정한 규칙을 가진 텍스트 문자열을 사용하는 경우가 많은데, 이럴 때 정규 표현식을 사용한다. 특히 컴파일러의 파서 부분은 이 정규 표현식이 반드시 들어간다. 유닉스 계열 운영 체제에서 CLI 환경을 주로 사용하는 경우 grep, sed, awk 등으로 인해 거의 필수적으로 알게 될 수밖에 없는 언어.[1] 웹 프로그래밍도 문자열을 다루는 빈도가 특히 높기 때문에 사용하는 게 거의 필수적. 예를 들면 위키위키만 해도 DB에 저장된 텍스트에 있는 위키 문법을 엔진에서 해석해서 출력해 주는 작업이 필요한데, 위키 문법도 일정한 규칙이 있는 문자열이니만큼 이 작업에서 정규 표현식은 반드시 들어간다. 비단 프로그래머가 아니더라도 텍스트 가공을 해야 할 일이 있는 사람이라면 정규 표현식을 아느냐 모르느냐에 따라 컴퓨터를 바라보는 시각과 그 활용도가 현격하게 차이가 난다.나무위키의 편집기에서도 정규 표현식을 사용해 문자열을 치환하는 등의 작업이 가능하다. 바꾸기 모드에서 .* 모양 버튼을 클릭하면 정규식 입력 모드가 된다.
입문 자체는 생각외로 간단하지만 조금이라도 본격적으로 써보려면 생각한 것처럼 원하는 결과를 이끌어내기가 상당히 어렵다. 전화번호, http 주소, 이메일 주소 등을 따는 레시피는 수도 없이 널려있지만 정작 내가 필요로 하는 부분에서는 제대로 레시피를 썼다고 생각하는데도 원하는 것 이상의 결과를 돌려주는 경우가 상당히 많은데 이를 극복하기 위해서는 정규식 규칙을 꼼꼼하게 읽어보고 직접 다 쳐보고 적용해서 확인해보는 것이 좋다. 멀리 가는 것이 제일 빠르게 가는 길이다. 그나마 요즘은 이런 유용한 사이트들이 많이 있으므로 적극적으로 활용해 보자. 근래에는 대화식으로 레시피를 입력해 볼 수 있는 도구도 생겨났다. #
정규식에 흥미가 생겼다면 컴파일러, 오토마타, 형식 언어 같은 것을 공부해도 좋다.
정규 표현식은 사용되는 언어마다 문법이 조금씩 다를 수도 있다. 정규 표현식을 구현한 엔진들끼리도 조금씩 다른 경우가 있으므로 자신이 익숙한 환경이 아니라면 미리 확인을 해보는 것이 중요하다. 크게 나누면 표준으로 인정된 POSIX의 정규 표현식과 그것에서 문법을 매우 확장한 Perl 방식의 PCRE[2] 이 둘로 나뉘어지며, POSIX 표준의 경우 다시 Basic과 Extended로 나뉜다. 이 외에도 Emacs와 Vim 모두 자체적인 정규 표현식을 지원한다. 문제는, 이 정규 표현식들이 완전히 다르면 모르겠지만, 비슷하면서도 살짝살짝 다르기 때문에 그 차이들을 다 외우고 있을 수도 없는 노릇이며, 정규 표현식 자체가 다량의 텍스트를 다루는 명령이니만큼 작은 실수가 커다란 차이를 불러올 수 있다는 점이다. 즉, 셸에서 쓰기 작업에 정규 표현식을 동반할 경우 매우 주의를 요할 필요가 있다. 또 다른 문제는, 자신이 뭘 원한다고 해서 그것만 배우고 쓰면 되는 게 아니라 프로그램마다 지원하는 정규 표현식이 다르기 때문에 그에 맞춰 배우고 써줘야 한다.[3] PCRE의 경우 이미 정규 표현식이라고 부를 수 없을 정도로 기능이 확장되어 있는데[4], 덕분에 이런 이상한 짓[5]도 가능하다. (...)
3. 문법
자바스크립트의 문자열에서 URL을 찾는 정규 표현식의 예제는 다음과 같다./(http|https|ftp|telnet|news|mms):\/\/[^\"'\s()]+/i위 정규식은 아래와 같이 구분이 된다.
/ | (http|https|ftp|telnet|news|mms):\/\/[^\"'\s()]+ | / | i |
| 패턴 구분자 시작 | 찾을 문자열의 패턴 | 패턴 구분자 끝 | 패턴 변경자 |
패턴 구분자는 정규식의 패턴이 달라질 경우 그것을 구분하는 문자로, 정규식 패턴이 하나만 있을 경우에는 굳이 쓸 필요가 없지만 대부분 붙인다. 난해하게 만드는 주범이다. 왜냐하면, 이 패턴 구분자는 특수 문자 중 역슬래시(\\)를 제외하고 아무거나 쓸 수 있기 때문이다. 심지어 아래 등장하는 의미를 가진 문자(메타 문자라고 부른다)도 패턴 구분자로 쓸 수 있다. 보통 슬래시(/)를 많이 사용하지만 규칙이 있는 것이 아니라서 정말로 프로그래밍하는 사람 마음대로다. 이래저래 헷갈리는 주범 중 하나.
3.1. 메타 문자
다른 언어에서 연산자나 예약어로 쓰이는 문자를 정규 표현식에서는 메타 문자라고 부른다. 메타 문자로 된 자원을 찾아야 하는 경우에는 다른 언어와 마찬가지로 앞에 역슬래시 \\를 붙여 이스케이프해 주면 된다.\\ ^ $ . | [ ] ( ) * + ? { } 마찬가지로 이스케이프 뒤에 문자를 붙이는 표현이 있다. 프로그래밍을 해봤다면 익숙할
\\n은 개행 문자, \\t는 탭 문자 이외에도 \\w는 문자(word character), \\W}는 문자가 아닌 글자(non-word character) 같은 기능들이 존재한다. 문자열의 시작과 끝을 표시하는 메타 문자는 옵션에 따라 줄 단위나 문서 전체를 의미할 수 있다.
^: 문자열의 시작$: 문자열의 종료
모든 아무 문자 하나와 일치하는 메타 문자로
.이 사용된다. 개행 문자는 포함되지 않는 경우가 많다. |는 왼쪽과 오른쪽 패턴 중에 아무 패턴이나 일치한다. 여러 개가 연결되면 그중에서 단 하나의 패턴만 일치한다.3.2. 문자 집합과 특수 문자
찾으려고 하는 문자열에 특정 문자 여럿이 포함되어 있을 경우 문자 집합을 사용하여 여러 문자를 동시에 찾을 수 있다.문자 집합은 대괄호 한 쌍으로 정의되는 문장이며 그 안에는 찾아야 할 문자들이 포함된다. 이때 문자 집합 내부에서 전용으로 사용되는 메타 문자가 있는데
^는 해당 집합에 포함된 문자들을 검색에서 제외하고, 문자와 문자 사이에 -가 있을 경우 해당하는 문자 코드 범위 내의 모든 문자를 포함한다. 단 문자 범위 지정은 역순이 되면 안 되고, A에서 z는 알파벳 대소문자 전체를 찾기도 하지만 그 사이에 존재하는 다른 문자 코드도 찾기 때문에 사용에 주의를 필요로 한다. 만약 문자 범위 지정이 아닌 문자로서의 -를 찾고 싶다면 문자 집합 제일 앞이나 뒷부분에 위치하여야 한다. 그래서 -는 일반적으로 메타 문자가 아니며 문자 집합 안에서만 의미를 가진다.이 외에도 기본적으로 정의된 문자 집합과 특수 문자를 나타내는 몇가지 이스케이프 문자가 있다. 대문자를 쓰면 해당 문자 집합을 제외하는 ^ 문자와 동일하다.
\b: 문자와 공백 사이 또는 문자의 시작 및 끝 지점을 의미한다.\c: 제어 문자를 의미한다.\d: 숫자에 해당하는 유니코드에 대응. [0-9]와 달리 아랍 문자, 페르시아 문자 등 다양한 숫자를 포괄한다.#\f: 폼 피드\n: 개행 문자\s: 공백 문자\t: 탭 문자\v: 수직 탭\w: 단어 영문자+숫자+_(밑줄) [0-9a-zA-Z_]\x: 16진숫값\0: 8진숫값
백스페이스는 반드시
[\b]를 입력해야 한다.3.3. 하위 표현식
패턴을 소괄호 한 쌍으로 둘러싸면 범위를 명시하는 것뿐만 아니라 수량자의 오작동을 막거나, 여러 가지 확장 문법을 사용하는 데 쓰인다.3.4. 수량자
패턴이 반복함을 나타내는 문법으로 패턴 뒤에 중괄호 또는 메타 문자가 붙는다.{n}: 정확히 n번 반복할 때 일치한다.{n,}: n번 이상 반복할 때 일치한다.{n,m}: n번에서 m번 안으로 반복할 때 일치한다.
또는 미리 정의된 반복 회수를 메타 문자로 지정 가능하다.
*: 패턴이 일치하지 않거나 한 번 이상 반복할 때 일치한다.{0,}과 같다.+: 패턴이 한 번 이상 반복할 때 일치한다.{1,}과 같다.?: 패턴이 일치하지 않거나 한 번만 반복할 때 일치한다.{0,1}과 같다.
특정 범위가 지정되지 않은 수량자의 기본 동작은 '패턴과 일치하는 모든 문자열을 찾는다.'이다. 그래서 과도하게 패턴을 일치시키려고 하는데 이 과정에서 필요 이상의 문자열을 찾는 경우가 발생한다. 이는 메타 문자
?를 수량자 뒤에 붙혀서 게으른 수량자로 만들어 해결할 수 있다. 반대로 일반적인 범위가 제한되지 않은 수량자는 탐욕적인 수량자라고 부른다.VIM Editor에서는 - 사용해, 게으른 수량자로 사용 가능하다.
{-n,m}: n번에서 m번 안으로 반복할 때 일치한다.
또한, 문자 하나도 패턴의 일종이기 때문에 평문 뒤에 바로 수량자를 입력하면 문자열 반복을 찾는 게 아니라 수량자 바로 앞에 붙은 패턴인 문자 반복을 찾게 된다. 이 문제를 해결하려면 찾을 문자열을 하위 표현식으로 감싸야 비로소 문자열 반복으로 인식한다.
3.5. 패턴 변경자
패턴 구분자가 끝나면 그 뒤에 쓰는 것으로, 패턴에 일괄적으로 변경을 가할 때 사용한다. 정규식 엔진에 따라 변경자의 적용 방식이 상이하므로 해당 구현의 매뉴얼을 읽어야 한다. 예를 들어 대소문자 무시 플래그의 경우자바스크립트는
/패턴/i 로 쓰지만 파이썬에서는 re.compile(패턴, flags=re.I) 로, Java나 Go에서는 (?i)패턴으로, C#에서는 new Regex(패턴, RegexOptions.IgnoreCase)라고 쓴다.i: 패턴을 대소문자 구분 없이 검사한다. 이 변경자를 사용할 경우 [a-z]로만 검사해도 자동으로 [a-zA-Z]와 같은 기능을 하게 된다. 영어가 아닌 언어(독일어, 프랑스어 등)를 다룰 때에는 버그 가능성이 있으므로 쓰지 않는 게 좋다. 대소문자라는 개념이 없는 한글, 한자, 가나 문자는 이 패턴 변경자가 아무 역할도 하지 않는다.s: 임의의 한 문자를 가리키는.메타 문자에 개행 문자(\\n)도 포함시키도록 한다. 이 변경자를 사용하면.이 줄 바꿈도 임의의 한 문자로 취급하여 찾는다.g:^문자가 문장이 아닌 문서의 처음에,$문자가 문장의 끝(라인 피드 \\n)이 아닌 주어진 문자열의 끝에 매치되게 변경한다.m: 주어진 문자열에 줄 바꿈이 있을 경우, 여러 줄로 취급하여 검사한다(줄 바꿈이 없다면 써도 의미가 없다.). 원래 정규 표현식을 쓸 때 줄 바꿈은 무시되는데, 이걸 사용하면 줄 바꿈을 적용해서 검사한다. 그리고^은 한 줄의 시작,$는 한 줄의 끝으로 의미가 달라진다.x: 공백 문자를 무시한다. 단, 이스케이프(역슬래시하고 같이 쓸 경우)하거나 문자 클래스 안에 있을 경우에는 예외. 정규식을 조금 더 읽기 편하게 만들어준다. 그러나 이 변경자를 지원하지 않는 엔진이 많은 게 단점이다.
3.6. 예제
기본적인 정규식^[0-9]*$: 숫자^[a-zA-Z]*$: 영문자. 패턴 변경자를 써서/^[a-z]*$/i같이 쓸 수 있다.^[가-힣]*$: 현대 한글(유니코드를 지원하는 정규식 엔진에 한정)^[ㄱ-ㅎㅏ-ㅣ가-힣]*$: 한글 자모 낱자를 포함한 모든 현대 한글- 굳이 유니코드 환경에서도 KS X 1001 완성형의 현대 한글 2350자만 선택하고 싶다면 완성형/한글 목록/KS X 1001 문서의 끝부분을 참고할 것.
^[a-zA-Z0-9]*$: 영문/숫자
3.7. 탐욕적 및 게으른 수량자
정규 표현식에서는 일치하는 패턴을 찾는 횟수 제한이 없어 필요 이상의 상황을 연출하기도 하는데 이것은 의도적으로 수량자를 탐욕적으로 만들었기 때문이다. 문법에서 말하는 탐욕적 수량자(Greedy Quantifier)란 가능하면 가장 큰 덩어리를 찾는다는 뜻이다. 반대의 개념인 게으른 수량자(Lazy Quantifier)는 패턴에 근접하는 최소한의 덩어리를 찾는다.- 탐욕적 수량자:
*,+,{n,} - 게으른 수량자:
*?,+?,{n,}?
사용례(Python) :
#!syntax python
>>> data = "<div> <p>First</p> <p>Second</p></div>"
>>> import re
>>> re.findall(r"<p>(.+)</p>", data) # 기본적으로 탐욕적인 매칭
['First</p> <p>Second']
>>> re.findall(r"<p>(.+?)</p>", data) # 게으른 수량자 사용
['First', 'Second']
사실 제대로 구현한 HTML 파서(Parser)는 정규식에 유한 상태 기계를 결합한 오토마타를 사용하지 게으른 수량자를 사용하지 않는다. 물론 언어별로 HTML 파서는 거의 만들어져 있으므로 HTML 파서를 또 구현할 필요는 전혀 없다.
그리고 수량자를 사용해도 정규식으로는 괄호 매치를 못 한다. 무슨 얘기냐면, 지금 매치한 닫힌 괄호에 대응하는 열린 괄호를 찾는 문제는 정규식만으로는 안 된다. 고정 갯수의 괄호는 매치할 수 있지만 임의의 괄호는 매치할 수 없다. 이는 정규식이 정규 언어이기 때문에 발생하는 한계이다.[6] 괄호 매치를 하려면 최소 푸시다운 오토마타(문맥 자유 언어)가 필요하다.
4. 학습 관련 사이트
- RegexOne
step-by-step 방식으로 빠르게 배울 수 있는 사이트. - regex101
간편하게 정규식을 연습하고 디버깅할 수 있는 사이트. 여러 색상으로 그룹을 표시해 주기 때문에 구분이 원활하다.
PCRE, 자바스크립트, 파이썬, Go를 지원한다. - RegExr
PCRE, 자바스크립트를 지원한다. - Regexper, Debuggex, ExtendsClass
정규식을 시각화해 주는 사이트. 작성한 정규식을 선로도(Railroad Diagram)로 변환하여 보여준다. 남이 만든 정규식이 도저히 읽히질 않으면 여기에 그 코드를 복붙해 보자. regexper.com은 정규식을 그림 파일로 다운로드하는 기능을 제공하고 debuggex.com은 실시간 정규식 시각화 및 매치 테스트를 제공한다. - Mozilla JavaScript RegExp Guide
모질라 재단에서 제공하는 개발자 문서로 자바스크립트의 정규 표현식 문법에 대해서 설명한다.
프로그래밍 언어에서 배우고 싶으면 자바스크립트의 정규식 엔진[7]을, 쉽게 배우고 싶으면 Ruby를 추천한다. 원조는 Perl이지만 언어의 문법 자체가 난해하므로 펄 언어 자체를 공부하는 부담이 Ruby보다 크기 때문이다.
Webhacking.kr에서 정규 표현식을 다루는 문제가 하나 있다.
5. 주의점
정규식이라고 해도 각 언어에서 지원하는 정규식 엔진은 그 구현이 제각각 다르기 때문에 항상 정규식을 검증한 다음 사용해야 한다.전후방 일치 같은 유용한 기능도 아예 지원하지 않는 엔진이 많으므로 주의해야 한다.
보통 일반적인 언어에서 지원하는 정규식 엔진은 백트래킹을 일치 여부를 판단하도록 구현되어 있다. 이유는 유한 오토마타보다 구현하기 쉽고, 또 역참조(back reference) 같은 편리한 기능을 지원하기 때문이다. 그러나 백트랙 특성상 최악의 경우 [math(O(2^n))]의 시간 복잡도를 가지므로 문제가 발생할 여지가 있는데, 이런 취약점을 공격하는 방식을 ReDos(regular expression denial of service)라고 한다.[8] 고의든 아니든간에 ReDos 공격을 받으면 서버 자원이 고갈되게 되며, 이는 서비스 장애로 이어질 수 있으므로, 작성한 정규식을 프로덕션에 반영하기 전에 반드시 정규식 테스트 사이트에서 다양한 케이스를 통해 검증하도록 하자.
6. 기타
[1] 모르고 CLI 환경에서 컴퓨터를 사용할 수도 있긴 하지만, 그럴 경우 그냥 GUI 환경을 사용하는 것에 비해 노가다가 현저하게 늘어나고 생산성이 매우 떨어진다.[2] Perl Compatible Regular Expressions. 이름에서 보이듯이 Perl 호환 정규 표현식이지만 완전한 호환은 아니다.[3] 물론, 오늘날에는 전부는 아니더라도 다른 정규 표현식에 대응되는 명령들도 기본으로 포함하고 있는 유닉스나 리눅스 배포판들이 많다. 예를들어, grep 대신 Extended 정규 표현식을 사용하는 egrep, sed 대신 PCRE 정규 표현식을 사용하는 psed 등이 그것이다.[4] 원래 정규 표현식은 놈 촘스키가 만든 촘스키 위계 3유형에 속하는 정규 문법에 대응되는데, PCRE에는 정규 문법에서 허용되지 않는 역참조(이전에 매칭된 부분 문자열과 같은 패턴을 다시 매칭)와 같은 기능을 추가로 제공한다.[5] 합성수에만 매치되고 소수에는 매치되지 않는 합성수 판별기다.[6] 이는 펌핑 보조정리(pumping lemma)를 통해 증명 가능하다.[7] 브라우저에서 F12만 누르면 즉시 사용 가능.[8] RE2나 GNU grep 같은 경우는 톰슨 NFA 기반의 DFA로 구현되어 있어 ReDos 공격에서 어느 정도 자유롭다.[9] 이동식 디스크의 이동식과 주로 엮인다.