정규표현식 - 02. 정규표현식의 역사

다양한 언어로 배우는 정규표현식을 보고 제 나름대로 정리한 내용입니다.

정규표현시의 기원

• 정규표현식으로 대두되는 사람은 연구자 클레이니이다.
• 정규표현식이 만들어내기 전까지는 계산이란 무엇인가? 라는 근원적인 연구가 진행되어 있었고, 계산이라는 행위 자체에 대한 부분을 수학적으로 정형화 한것이 "계산 모델"이다.
• 계산 모델에 대한 기념비 적인 두 연구는 튜링머신과 형식적 뉴런이 있다.

튜링 머신과 알고리즘

• 과학자 튜링이 발명한 튜링머신은 계산기 모델이지만 실질적으로 계산할 수 있는 모든 것들을 머신이 계산할 수 있도록 하는게 목적이였음
• 계산할 수 있다는 것은 결과가 정성적인게 아닌 정량적인 것
  • 인생이란 무엇인가? X
  • 주어진 수가 소수인가? O
• 대부분 알고리즘을 "계산기가 계산하기 위한 순서"로 알고 있지만 "튜링 머신으로 실행할 수 있는 것"이 알고리즘이다.

뇌의 계산 모델과 형식적 뉴런

• 1943년에 연구된 형식적 뉴런 계산 모델은 튜링 머신과 다르게 뇌과학적/신경생리학적 접근으로 만들어 졌다.
• 노드 사이가 연결되어 있고 각자 입력에 가중치가 부여되 있다.
• 형식적 뉴런이 확립되고 난 후부터 뉴럴 네트워크 연구가 활발해졌다. (이게 정규식이랑 뭔 관련이 있는지는 모르겠다)

클레이니에 의한 통일

기억 영역의 유무: 형식적 뉴런과 튜링 머신의 결정적 차이

• 형식적 뉴런과 튜링머신에는 기억 영역의 유무의 차이게 있기에, 튜링머신 즉, 알고리즘은 세상에 존재하는 모든 문제를 계산할 수 없다.
  • 기억 영역 : 메모리나 하드 디스크로써 계산시 사용될 수 있는 외부 작업영역
• 1951년 클레이니는 형식적 뉴런이 정규표현식과 같은 것임을 밝혀냈다.

정규표현식의 탄생

• 클레이니는 과거 눈문에서 정규표현식 (regular expression)을 제안했다.
  • 형식적 뉴런으로 계산할 수 있는 것은 정규표현식으로도 표현할 수 있다는 내용으로 regular expression 명칭도 논문에서 제안했다
  • 아래는 클레이니 논문에 기재된 등식을 최근 정규표현식 구문으로 바꾼것이다
    • E|E = E
    • E|F = F|E
    • (E|F) G = E|(F|G)
    • (EF)G = E(FG)
    • (E*F)G = E*(FG)
    • (E|F)G = EG|FG
    • E(F|G) = EF|EG
    • E*(F|G) = E*F|E*G
    • E*F = F|E*EF
    • E*F = F|EE*F
    • E*F = E^s*(F|EF|E^2... E^(s-1)) (s>=1)

유한 오토마타 도입

• 위의 논문에서 정규표현식 바로뒤에 유한 오토마타라는 계산 모델을 도입했다.
  • 유한 오토마타
    • 기억 영역이 없는 계산 모델
    • 형식적 뉴런보다 단순하게 표현한 계산모델
    • 유한 오토마타가 계산할 수 있는 것 === 정규표현식으로 표현할 수 있는 것
      • 메모리를 일절 소비하지 않는 프로그램으로 계산할 수 있는 것
    • 오토마타라는 단어는 중세 유럽에서는 태엽으로 움직이는 인형이라는 뜻을 가졌음.

유한 오토마타 이론의 발전

• 지금 까지도 오토마타 이론이라는 분야는 활발히 연구되고 있다.
• 오토마타와 정규표현식은 뗄 수 없는 관계이다.
• 오토마타를 사용하면 다음 두 개의 문제를 쉽게해결할 수 있다.
  • 2개의 정규표현식이 같은지 판정
  • 정규표현식을 부정 정규표현으로 만들기

[적응편] 프로그래머의 친구

학문적 세계에서 탄생한 정규표현식이 대중들에게 알려지게된 계기는 유닉스였다.

최초의 정규표현식 엔진

• 클레이니의 논문 이후 17년이 지나고 케네스 톰슨은 정규표현식을 다룬 첫 논문을 발표했다. 해당 논문에는 다음과 같은 내용을 담고있다.
  • 정규표현식으로 NFA를 구성하는 방법
    • 톰슨 구성법이라고도 불린다.
  • NFA 를 효율적으로 시뮬레이션 하는 방법
    • NFA? regex_01
    • NFA를 효율적으로 시뮬레이션 하는 방법은 톰슨 NFA라고 부른다.
  • 시뮬레이션을 실행하는 IBM 7094 코드를 직접 생성하는 방법
    • 정규표현식의 JIT컴파일러를 만들어냈음을 의미한다.

QED: 정규표현식을 이용한 검색 가능한 텍스트 편집기 등장

• 1960년 후반 C언어도 없던 시대에 메인프레임상에서 동작하는 버클리 시분할 시슽메은 QED라는 편집기를 사용하고 있었다. 톰은은 QED를 IBM 7094로 이식하는 작업을 맡았다.
• 이 때 추가된 기능중 하나는 정규표현식을 사용한 검색 기능이다.

ed 에디터부터 grep까지

• 1971년 톰슨은 유닉스에 탑재하기 위한 에디터로 ed를 개발했는데 이는 최초의 유닉스 정규표현식 툴이다.
  • ed의 정규표현식 엔진에서는 선택기능을 사용할 수 없었다.
  • Ken|Thompson 이런게 불가능
  • 작동방법이 매우 불편하다. man ed를 통해 설명을 확인할 수 있다.
    • 파일명을 입력 -> 명령어 실행 -> 내용 표시 -> 커서를 통해 원하는 곳 수정
• ed는 vim과 마찬가지로 입력/명령어모드로 나누어져 있다.
• ed는 line editor이고 vim은 screen editor이다.
  • ed는 행을 지향한다.
    • 과거에는 출력물이 디바이스의 화면이 아니라 텔레타이프라는 기계를 통해 종이에 표현됐었다. vim처럼 전체화면을 안보여준 이유가 다 있다.
    • 오늘날에는 editor를 떠올리면 screen editor를 떠올리는게 당연하기 때문에 앞에 line, screen따위는 붙이지 않는다.
• 정규표현식이 일치하는 행을 찾는 기능도 편했지만, 검색을 위해 편집기를 켜야하는 점과 실수로 파일내용을 건드릴 위험이 있다는 단점 때문에 grep이라는 도구가 탄생했다
  • 참고로 ed에서 RE라는 정규표현식에 일치하는 행을 모두 표시하는 명령은 g/RE/p이다. (grep의 이름 유래)

유닉스와 정규표현식

• grep이후 AWK, sed, find 등 다양한 정규표현식을 활용한 툴이 등장했다. 현재에도 정규표현식을 사용하는 툴을 열거하면 끝이없을 정도로 많다

프로그래밍 언어와 정규표현식의 만남

• 정규표현식은 문자열 검색을 위해 만들어졌지만, 프로그래밍이란 더 큰 영역으로 진출하게 됐다.

범용 프로그래밍 언어로서 진출: AWK

• AWK는 가장 빠른 시기에 정규표현식을 도입한 범용 프로그래밍언어이다.
  • (cli에서 사용가능한 단순한 프로그램인줄 알앗는데 언어였다..)
• 1985년에 업데이트를 통해 패턴 일치 기능을 도입했다.

POSIX를 이용한 표준화

• 1980년에는 구현 호환성을 확보하기 위해 POSIX(Portalbe Operatiing System Interface)라는 운영체제 전반에 관련된 규격이 생겼다.
• 정규표현식에도 POSIX 표준사양이 정해졌고, 그 당시 C언어와 PHP에서 사용하는 정규표현식이 POSIX.2를 기준으로 하고 있었다.
• POSIX 정규표현식
  • BRE (표준 정규표현식)
    • GNU grep
    • 선택연산, +,? 수량자 사용불가
  • ERE (확장 정규표현식)
    • grep의 -e 옵션, egrep

헨리 스펜서의 정규표현식 라이브러리

• 헨리스펜서는 최초의 C 언어용 정규표현식 라이브러리를 만들어 배포했다. 이 덕분에 개별적으로 엔진을 만들필요가 없이 패턴 일치 기능을 사용할 수 있게되었다.

최근의 정규표현식 엔진 현황

• regex_01 에서 보앗듯 정규표현식의 대부분은 VM형과 DFA형 엔진으로 구분된다.
• DFA
  • GNU grep
  • Google RE2
• VM
  • 펄, 자바스크립트, 루비에 탑재된 엔진

GNU grep

• grep은 ed의 정규표현식 검색 기능을 개별로 빼낸것이다.
• tail -n 100 log.txt | grep 'error'
  • 위 명령어는 log.txt란 파일에서 error라고 적힌 행을 뒤부터 100줄까지만 검색하여 출력하는 명렁어이다.
  • | 는 파이프라고 부르며 맥클로이라는 사람이 처음 고안한 아이디어이다.
• 파이프는 매우 편리한 도구였고 여러곳에 영향을 끼치게된다.
• GNU grep은 본적으로 DFA형이지만, 역참조 대응을 위해 부분적으로는 VM형 접근법도 사용한다.
• DFA형의 중요한 부분은 성능이다.

Google RE2

• 러스 콕스가 C++로 만든 정규식 라이브러리로 2013년에 출시된 가장 새로운 부류이다.
• 구글에서 전 세계 오픈소스를 검색하기위해 만들었다.
• GNU grep가 비교해도 손색이 없는 성능이지만 역참조나 재귀 기능을 제공하지 않는다. (오토마타 이론에서는 이런 방침이 옳다고 할 수 있다.)

Perl

• 래리 월이 실무에서 필요에 의해 만든 실천 지향 언어이다.
• rn이라는 툴의 정규표현식을 빌려와 만들었을 땐 빈약한 기능을 가졌지만 차차 개선됐다.

PCRE

• 여러 언어에서 Perl 정규표현식을 도입하는데 도움을 준 호환성이 높은 정규표현식 패키지이다.
• 나중에는 펄의 정규표현식에는 없는 JIT을 도입해 고속화를 실현했다.

자바스크립트

• 자바스크립트에 사용되는 정규표현식은 ECMAScript에 엄격하게 정해져 있다.
• 브라우저의 자바스크립트 엔진에서는 속도향상을 정규표현식을 최적화한다.
  • 대부분의 컨턴츠를 텍스트로 주고 받기 때문
• JIT 컴파일이라는 기법이 정규표현식 엔진에 적용되었다.