Show HN: 텍스트 편집을 위한 Transductive 정규 표현식

TRRE: 전환 정규 표현식

요약

• 텍스트 편집과 grep과 유사한 명령줄 도구를 위한 정규 표현식의 확장임.
• 프로토타입이므로 실제 환경에서는 사용하지 말 것.

소개

• 정규 표현식은 텍스트에서 패턴을 검색하는 데 유용한 도구임.
• 텍스트 편집에는 자연스럽지 않다고 느껴져서 확장을 제안함.
• 전환 정규 표현식 또는 **trre**라고 부름.
• : 기호를 사용하여 변환을 정의함.
• a:b는 a를 b로 대체하는 가장 간단한 형태임.
• **trre**라는 명령줄 도구를 만들어 개념을 시연함.

예제

• 기본

  • cat을 dog로 변경: $ echo 'cat' | trre 'c:da:ot:g' dog
  • sed처럼 문자열의 모든 일치를 대체: $ echo 'Mary had a little lamb.' | trre '(lamb):(cat)' Mary had a little cat.
  • 삭제: $ echo 'xor' | trre '(x:)or' or
  • 삽입: $ echo 'or' | trre '(:x)or' xor

• 전환을 통한 정규 표현식

  • 교대 사용: $ echo 'cat dog' | trre 'c:bat|d:hog' bat hog
  • 스타를 사용하여 변환 반복: $ echo 'catcatcat' | trre '((cat):(dog))*' dogdogdog

• 범위 변환

  • 문자 범위 변환: $ echo "regular expressions" | trre "[a:A-z:Z]" REGULAR EXPRESSIONS

• 생성기

  • **trre**는 단일 입력에 대해 여러 출력 문자열을 생성할 수 있음.
  • 이진 시퀀스: $ echo '' | trre -ma ':(0|1){3}' 000 001 010 011 100 101 110 111

언어 사양

• **trre**는 패턴-매칭:패턴-생성의 쌍으로 정의됨.
• 패턴-매칭은 문자열이나 정규 표현식일 수 있음.
• 패턴-생성은 일반적으로 문자열이지만 regex일 수도 있음.

왜 작동하는가

• **trre**는 **유한 상태 변환기(FST)**라는 특별한 자동자를 구축함.
• FST는 입력-출력 쌍을 처리함.

설계 선택 및 열린 질문

• :의 결합성, 우선순위, 암시적 엡실론 등 여러 결정이 필요함.

모드 및 탐욕성

• **trre**는 두 가지 모드를 지원함:
  • 스캔 모드(기본): 변환을 순차적으로 적용함.
  • 매치 모드: 표현식에 대해 전체 문자열을 확인함.

결정화

• 비결정적 자동자를 결정적 자동자로 변환하는 과정이 중요함.

성능

• NFT(비결정적) 버전은 sed보다 약간 느림.
• 복잡한 작업에서는 trre_dft(결정적 버전)가 sed보다 성능이 좋을 수 있음.

TODO

• ERE 기능 세트 완성, 전체 유니코드 지원, 효율적인 범위 처리 등.

참고 문헌

• Russ Cox의 기사와 Cyril Allauzen, Mehryar Mohri의 논문에서 영감을 받음.