저는 정규식의 역사와 발전을 연구하고 있습니다. 다음 타임라인을 찾았습니다.
- 1956 - Kleene은 신경망에 관한 논문에서 정규식을 소개합니다.
- 1964 - Brzozowsi는 정규식 파생어의 개념을 도입합니다.
- 1968 - Thompson이 정규식 컴파일러 작성 방법을 설명합니다.
- 1960년대 후반/1970년대 초반
- Thompson은 QED 편집기를 CTSS로 포팅하여 정규식 지원을 추가했습니다.
- Thompson과 Ritchie는 QED를 Multics로 포팅했고 결국 1970년대에는 Unix로 포팅했습니다.
- Thompson은 QED에서 영감을 받아 에드를 썼습니다.
- Unix V1 이후 Thompson은 ed에서 정규식 코드를 추출하여 grep을 만들었습니다.
- Unix V7에서는 egrep과 fgrep이 도입되었습니다.
Kleene과 Brzozowski는 정규 표현식에 대해 동일하지만 다른 정의를 가지고 있으며, Thompson은 그의 논문에서 독자들이 이러한 정의에 익숙하다고 명시적으로 가정합니다.
내가 혼란스러워하는 것은 ed의 교대(두 정규 표현식 중 하나와 일치)에서 무슨 일이 일어나고 있는지입니다. Kleene, Brzozowski 및 Thompson의 논문에는 교대가 포함되어 있습니다. QED에서 Thompson의 정규식 구현에는 대체가 포함되어 있지만 ed는 그렇지 않습니다. 초기 grep도 마찬가지였습니다.
나에게 더 이상한 점은 ed가 정규식에 역참조 지원을 도입했다는 것입니다. 즉, 정규식은 (a.c)\1일치 abcabc하지만 일치하지 않습니다 abcadc. 역참조를 사용하면 ed와 grep이 일부 비전통적인 언어를 인식할 수 있지만 대체가 부족하다는 것은 일부 일반 언어를 인식할 수 없음을 의미합니다.
Thompson이 qed와 ed 교대로 지원을 제거한 이유는 무엇입니까? 역참조는 추가되지만 대체는 추가되지 않는 이유는 무엇입니까?
답변1
Dennis Ritchie는 다음과 같은 짧은 기사를 쓴 적이 있습니다.QED 텍스트 편집기의 불완전한 역사. 본문에서 우리가 읽을 수 있는 것은
"표준 유닉스 편집기"는
ed원래 Ken Thompson이 PDP-7용으로 작성했습니다. 기본 텍스트 줄 방향을 유지하지만 연산자만 포함하도록 정규식을 근본적으로 단순화합니다*. 즉, 교대나 괄호가 없습니다. 내 QED에는 문맥 없는 언어가 많이 포함되어 있지만 이 버전은 모든 일반 언어조차 표현할 수 없습니다. 손실은 크지 않습니다.마찬가지로 Ken의 Unix는
ed다중 버퍼 및 버퍼 실행 개념을 포기했습니다. Unix의 이후 버전ed(현재는 C로 작성됨)에는 약간의 복잡성이 추가되기 시작했습니다(예: "정규" 표현의 역참조는 이제 모든 일반 언어나 문맥 자유 언어를 포괄하지는 않지만 문맥 감지 언어를 침해합니다).
이 짧은 문단에서 Ken의 주요 관심사는 어떻게 ed사용 하는가라는 것을 알 수 있습니다.일을 끝내다, 실제로 사용되지 않는 정규식을 구현하려고 시도하는 대신. 이것"손실은 크지 않습니다."아마도 Ken이 본문에 개인적으로 접근했다는 신호일 것입니다.필요변경 또는 역참조(적어도 절망적이지는 않음).
길스도 그렇고댓글로 지적해, 대체 구현은 느리고 상대적으로 메모리 집약적일 수 있는 반면, 역참조는 비정상적인 상황에서 느려질 수 있으므로 제한된 하드웨어에서 역참조가 구현될 가능성이 더 높습니다.
개발 초기에 유닉스 팀이 사용했던 PDP-7은 8k 단어의 메모리를 가지고 있었고, Ken이 QED 버전을 구현한 Multics 시스템은 64k 단어의 메모리를 가진 시스템에서 실행되었습니다. 이는 ed원래 구현에 매우 기본적인 패턴 일치 기능만 있었던 또 다른 이유 일 가능성이 높습니다 .
요약: 두 가지 이유가 있을 수 있습니다.
- 제한된 하드웨어(PDP-7)로 인해 인터리빙 및 역참조 등을 구현하는 것이 불가능하거나 번거롭습니다.
- 편집기의 목적에는 실제로 전체 정규식 구문이 필요하지 않습니다. 더 강력한 하드웨어(PDP-11)로 이동하면서 역참조가 편집기에 다시 추가되었지만 당시 편집기 사용자 간에는 변경이 전혀 필요하지 않았을 수 있습니다.