1P by neo 1달전 | ★ favorite | 댓글 1개
  • TRRE: 전환 정규 표현식

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

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

    • 기본

      • catdog로 변경:
        $ 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의 논문에서 영감을 받음.
Hacker News 의견
  • Cool, 이 프로젝트의 발전이 기대됨

    • 연산자 우선순위가 자연스럽지 않다고 느낌
    • cat:dog(cat):(dog)보다 ca(t:d)og로 해석되는 것이 이상함
  • XFST (Xerox Finite-State Transducer)를 추천함

    • 20년 이상 컴퓨터 언어학에 사용된 도구임
    • 핀란드어 형태소 분석에 FST를 사용하는 사례를 들음
  • 표준 정규 표현식의 대안으로 Rosie Pattern Language를 추천함

    • 그룹 논리에서 어려움을 겪는 사람들에게 유지보수 가능한 대안이 될 수 있음
    • 관련 링크 제공: GitLab, Rosie 공식 사이트
  • 1997년에 유한 상태 변환기에 대한 논문을 작성한 경험을 공유함

    • 주제는 형태소 분석이었으며, 과소평가된 주제였음
    • 구문에 대해 :ab보다 강하게 결합되도록 설정하는 것이 맞는지 질문함
  • 구조적 치환을 수행할 때 충분하지 않다고 느낌

    • 정규 표현식이 매치된 부분에 대해 구문 트리를 정의하므로, 트리의 일반적인 변환을 수행할 수 있으면 유용할 것임
  • 정규 표현식이 텍스트 편집에 부자연스럽다는 주장에 의문을 가짐

    • 프로젝트의 목적이 이 주장에 달려 있지만, 예시가 없음
    • 그룹 사용에 어려움을 겪는 이유를 이해하지 못함
    • 정규 표현식보다 이 프로젝트의 문법이 더 나은 이유를 설명하는 예시가 필요함
  • C 코드가 매우 깔끔하다고 칭찬함

    • README의 theory.pdf 링크가 잘못되어 수정이 필요함
  • *+를 사용하지 말라는 조언에 대해 의문을 가짐

    • 문법을 더 복잡하게 만들겠지만, 이를 허용하지 않는 것이 더 나을 것임
  • 첫 번째 예시가 이상하다고 느낌

    • echo 'cat' | trre 'c:da:ot:g'의 결과가 이상함
    • 구문 트리가 어떻게 구성되는지 이해하기 어려움
    • MS-DOS 시절의 검색/치환 방식이 더 직관적이라고 느낌
  • 예시들이 실제 프로그램의 출력인지 의문을 가짐

    • 문법에 대한 이해가 부족할 수 있지만, 예시들이 잘못된 것처럼 보임
    • echo 'cat dog' | trre 'c:bat|d:hog'의 결과가 이상함