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

 (github.com/c0stya)
1P by GN⁺ | ★ favorite | 댓글 1개
  • TRRE는 정규 표현식에 텍스트 변환을 직접 표현하는 : 연산자를 추가한 언어 확장이며, 이를 실험하는 grep -E 유사 CLI 도구 trre로 제공됨
  • 기본 형태는 a:b처럼 입력 패턴을 출력 패턴으로 바꾸는 transductive pair이며, 삭제는 x:, 삽입은 :x처럼 빈 문자열과의 변환으로 표현함
  • 일반 정규 표현식처럼 대안 선택, 반복, 문자 범위 변환을 사용할 수 있고, cat:dog, [a:A-z:Z], Caesar cipher 같은 예제가 포함됨
  • 내부 구현은 일반 정규 표현식의 FSA 대신 입력-출력 쌍을 다루는 Finite State Transducer(FST) 를 구성하며, 실험적인 on-the-fly 결정화도 지원함
  • 현재는 사전 빌드 바이너리가 없고 직접 빌드해야 하며, DFT 안정화, Unicode 전체 지원, ERE 기능 완성, 효율적인 범위 처리 등이 TODO로 남아 있음

TRRE가 해결하려는 문제

  • 일반 정규 표현식은 텍스트에서 패턴을 찾는 데 유용하지만, 텍스트 편집에서는 그룹 처리 로직이 후처리처럼 동작해 복잡해질 수 있음
  • TRRE는 패턴 매칭과 텍스트 수정을 같은 표현식 안에 넣기 위해 정규 표현식 언어를 확장함
  • 핵심 문법은 pattern-to-match:pattern-to-generate 형태이며, 가장 단순한 예시는 a:b로 a를 b로 바꿈
  • CLI 도구 trre 는 이 개념을 보여주는 구현체이며 grep -E와 비슷한 느낌으로 동작함

기본 변환 문법

  • 문자열 치환은 cat:dog처럼 작성함
    • echo 'cat' | ./trre 'cat:dog'는 dog를 출력함
    • (c:d)(a:o)(t:g)처럼 문자 단위 변환으로도 같은 결과를 만들 수 있음
  • sed처럼 문자열 안의 모든 매치를 바꾸는 데 사용할 수 있음
    • Mary had a little lamb.에서 lamb:cat을 적용하면 Mary had a little cat.이 됨
  • 삭제는 오른쪽을 비워 string_to_delete: 형태로 표현함
    • (x:)or는 xor에서 x를 제거해 or를 만듦
    • a:는 기본 scan mode에서 모든 a를 빈 심볼로 바꿔 제거함
    • [aie]:처럼 대괄호 표현을 써 여러 문자를 제거할 수 있음
  • 삽입은 왼쪽을 비워 :string_to_insert 형태로 표현함
    • (:x)or는 or 앞에 x를 넣어 xor를 만듦
    • had a (:little )lamb는 문맥 안에서 little 을 삽입함

정규 표현식 위의 변환

  • TRRE는 일반 정규 표현식처럼 |를 이용한 대안 선택을 지원함
    • (c:b)at|(d:h)og는 cat dog를 bat hog로 바꿈
  • 반복 연산자도 변환에 적용할 수 있음
    • (cat:dog)*는 catcatcat을 dogdogdog로 바꿈
    • 기본 scan mode에서는 cat:dog만으로도 반복 적용되어 같은 결과를 만들 수 있음
  • 왼쪽 패턴에서 반복을 사용하면 여러 입력을 소비하고 하나의 출력으로 바꿀 수 있음
    • (cat)*:dog는 catcatcat을 dog로 바꿈
  • 오른쪽 패턴에서 *나 +를 쓰면 무한 루프가 발생할 수 있음
    • :a* 같은 표현식은 피해야 함
    • 유한 반복이 필요하면 :(repeat-10-times){10}처럼 횟수를 지정함

범위 변환과 생성기

  • 문자 범위 변환은 [a:A-z:Z]처럼 작성함
    • regular expressions를 REGULAR EXPRESSIONS로 바꿀 수 있음
  • Caesar cipher 예제가 포함됨
    • [a:b-y:zz:a]는 caesar cipher를 dbftbs djqifs로 바꿈
    • [a:zb:a-z:y]는 이를 다시 caesar cipher로 되돌림
  • generator처럼 하나의 입력에서 여러 출력을 만들 수도 있음
    • 기본값은 가능한 첫 번째 매치를 사용함
    • -a 옵션을 쓰면 가능한 모든 출력을 생성함
  • 예시로 빈 입력에 :(0|1){3}을 적용하면 000부터 111까지 3비트 이진 시퀀스를 만들 수 있음
  • :(0|1){,3}?와 -ma를 함께 쓰면 길이 3 이하의 부분 집합 형태 출력들을 생성함

언어 사양과 연산자 우선순위

  • 비공식적으로 TRRE는 pattern-to-match:pattern-to-generate 쌍으로 정의됨
  • 왼쪽 pattern-to-match는 문자열 또는 정규 표현식일 수 있음
  • 오른쪽 pattern-to-generate는 보통 문자열이지만 정규 표현식도 가능함
  • : 연산자는 현재 비결합적으로 취급되며, TRRE:TRRE 형태는 문법적으로 허용되지 않음
    • 이 형태는 TRRE가 정의하는 관계의 합성이라는 자연스러운 의미가 있지만, 복잡도가 커질 수 있어 아직 제외됨
  • 연산자 우선순위는 높은 순서부터 다음과 같음
    • 이스케이프 문자 \
    • 대괄호 표현 []
    • 그룹화 ()
    • 반복 * + ? {m,n}
    • 연결
    • Transduction :
    • 대안 선택 |

모드와 탐욕성

  • trre는 두 가지 모드를 지원함
    • Scan Mode: 기본 모드이며 변환을 순차적으로 적용함
    • Match Mode: -m 플래그를 사용하며 전체 문자열이 표현식과 맞는지 확인함
  • -a 옵션은 가능한 모든 출력을 생성함
  • ? 수정자는 *, +, {,} 연산자를 non-greedy로 만듦
    • <(.:)*>는 <cat><dog>에서 <>를 출력함
    • <(.:)*?>는 같은 입력에서 <><>를 출력함
  • 태그나 괄호 안의 내용을 바꾸는 예시도 포함됨
    • <(.*?:cat)>는 <dog> <mouse>를 <cat> <cat>으로 바꿈

FST 기반 구현과 결정화

  • TRRE는 내부적으로 Finite State Transducer(FST) 를 구성함
  • FST는 일반 정규 표현식에서 쓰는 Finite State Automaton(FSA) 와 유사하지만, 단순 문자열 대신 입력-출력 쌍을 다룸
  • TRRE의 핵심 차이는 다음과 같음
    • 두 정규 언어 사이의 이항 관계를 정의함
    • 추론에 FSA 대신 FST를 사용함
    • 성능을 위해 실험적인 on-the-fly 결정화를 지원함
  • 일반 정규식 엔진에서 결정화는 비결정 오토마타를 결정 오토마타로 바꿔 입력 문자열 길이에 대해 선형 시간 추론을 가능하게 함
  • TRRE에서도 비슷한 접근이 가능하지만, 모든 비결정 변환기 NFT를 결정 변환기 DFT로 바꿀 수는 없음
    • 같은 입력 라벨을 가진 두 개의 “bad” cycle이 있으면 상태 생성이 무한 루프에 빠질 수 있음
    • 이런 루프를 감지하는 방법은 있지만 비용이 큼

성능과 설치 상태

  • 기본 비결정 버전은 단순 치환에서 sed보다 약간 느린 예시가 제시됨
    • ./trre '(vodka):(VODKA)': real 0m0.046s
    • sed 's/vodka/VODKA/': real 0m0.024s
  • 복잡한 작업에서는 결정 버전 trre_dft 가 sed보다 빠른 예시가 있음
    • sed -e 's/\(.*\)/\U\1/': real 0m0.508s
    • ./trre_dft '[a:A-z:Z]': real 0m0.131s
  • 사전 빌드 바이너리는 아직 제공되지 않음
  • 설치는 저장소를 클론한 뒤 make && sh test.sh로 빌드하고 테스트하는 방식임
  • TODO에는 다음 항목이 남아 있음
    • 안정적인 DFT 버전
    • 전체 Unicode 지원
    • ERE 기능 완성
      • [] 안의 부정 ^
      • 문자 클래스
      • $^ 앵커 심볼
    • 효율적인 범위 처리

참고한 접근

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 이 프로젝트가 어디로 갈지 흥미롭다. 다만 연산자 우선순위가 부자연스럽고, 이 스레드의 다른 사람들도 비슷하게 느낀 듯함
    cat:dog는 자연스럽게 ca(t:d)og가 아니라 (cat):(dog)와 같다고 예상하게 됨

    • 여러 면에서 흥미로운 아이디어임
      cat:dog가 (cat):(dog)가 아니라 ca(t:d)og처럼 해석된다는 점이 나도 헷갈렸는데, 정규식을 모두가 조금 잘못 쓰고 있다는 걸 떠올리니 이해가 됐음. 정규식은 “원래” 매처가 아니라 문자열 생성기로 보는 게 맞고, 그래서 cat|dog는 형식적으로 {catog,cadog} 같은 집합으로 확장된다고 볼 수 있음
      매칭에서는 이 문자열 집합을 더 큰 텍스트에 대해 부분 문자열 매칭하면 됨. 문제는 실제 정규식 엔진 대부분이 이렇게 동작하지 않고, 기대에 맞추거나 효율을 위해 여러 이상한 동작을 한다는 것임
      여러 정규식 도구를 시험해 보면 (cat)|(dog) 또는 (cat)|(dog)|(ca[td]og) 같은 변형이 나옴. 그래서 더 형식적인 관점에서는 cat:dog가 (cat):(dog)가 아니라 ca(t:d)og를 만드는 게 맞다고 봄. 하지만 수십 년 동안 정규식을 사용자 기대에 맞춘 매칭 도구로 남용해 온 경험 때문에 이제는 모두가 교체하고 싶은 표현식에 괄호를 둘러씀
      이 제안은 흥미롭고 잘 설계됐지만, 결국 정규식을 본래의 생성기 모델로 되돌리려는 느낌이 있음. 문제는 문법이 아니라 도구 쪽에 가까움
      예전에 이 분야와 가까운 일을 했고, 정규식을 문자열 집합 생성기로 생각해 본 적이 없다면 여기서 가지고 놀아볼 수 있음: https://onlinestringtools.com/generate-string-from-regex
      다만 이런 생성 도구의 동작도 매우 특정적임. 내가 쓰던 도구들은 클로저 등에 제약을 지정해서 생성기를 제한하는 여러 방법이 있었음
    • 피드백 고맙고, 우선순위는 나도 고민 중이라 바꿀 수도 있음
      연결 뒤로 미루면 또 다른 문제가 생길 수 있음. 예를 들어 비결합적인 :에서는 cat:dog:mouse가 불법이어야 할 수도 있는데, 어떻게 다룰지 확신이 없음
      현재 버전에서는 엡실론, 즉 빈 문자열을 삽입함. 예를 들어 한 글자씩 건너뛰며 제거하려면 기술적으로 .(.:eps)인 ..:를 실행할 수 있음
      echo 'abcde' | ./trre '..:'의 결과는 'ace'임
      사실 : 결합은 정규 관계의 합성이라는 의미를 가질 수도 있지만, 지금은 너무 복잡하다고 봤음
    • 범위 변환도 비슷함. [a:A-z:Z] 대신 [a-z:A-Z]가 낫고, [a:b-y:zz:a] 대신 [a-y:b-z;z:a] 같은 형태를 제안하고 싶음

  • 유한 상태 변환기와 관련 도구에 관심 있다면 XFST(Xerox Finite-State Transducer)를 볼 만함. 계산언어학 응용에서 20년 넘게 쓰여 왔음
    PARC의 핀란드 연구자가 UT 수업에 와서 FST로 핀란드어 형태론을 처리하는 방법을 보여준 적이 있는데, 겉보기에도 꽤 대단한 일이었음

    • 나도 이걸 언급하려 했음. Kaplan 논문 링크: https://aclanthology.org/J94-3001.pdf
      PARC에서 했던 작업을 설명함
    • http://hfst.github.io/가 XFST의 현대적인 오픈소스 버전임. foma와 OpenFst를 포괄하고, trre가 하는 일과 그 이상을 거의 다 할 수 있을 것임
    • Pynini에도 관심을 가질 만함. OpenFst의 Python 래퍼이자 사용 편의 기능이 많이 추가된 도구임
      OpenFst는 변환기용으로 정말 훌륭한 라이브러리임. Johns Hopkins 등에서 과제 형태로 만든 Pynini 사용 사례 튜토리얼도 괜찮음
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • 표준 정규식의 대안을 찾고 있고, 특히 그룹 논리가 어렵거나 유지보수 가능한 표현을 원한다면 Rosie Pattern Language가 맞을 수도 있음
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • 멋지다. 1997년쯤 전산학 Diplom 논문을 유한 상태 변환기로 썼는데, 생각보다 훨씬 덜 사소했음
    과제는 가능한 경우 합성과 DFA를 구현하는 것이었고, 합성된 변환기도 포함됐음. “유한 상태 변환기의 대수”였고 사용 사례는 형태론이었음. 주제가 크게 과소평가돼 있어서 중간쯤에서 끝내야 했음. 그러니 경의를 표함
    문법과 관련해서, 정말 :가 연결 ab보다 더 강하게 결합하길 원하는지 궁금함

    • 2000년대 초반에 생물정보학에서 OpenFST를 썼음. 가지고 놀기엔 재미있었지만, 내가 하던 작업에는 결국 유용하지 않았음
      20년이 지난 지금도 프로젝트가 계속되고 있다니 보기 좋음: https://www.openfst.org/twiki/bin/view/FST/WebHome
    • 졸업 여부를 사실상 “정규식을 충분히 세게 다룰 수 있느냐”에 거는 건 엄청 대담한 선택임
    • 맞음. 변환기는 아주 오래된 주제임. 어떤 이유에서인지 정규식처럼 특정 언어와 강하게 연결되지는 않았음
      :가 연결보다 강하게 결합해야 하는지는 아직 확신이 없음. 예제 100개 정도를 보고 지금 방식, 즉 :가 .보다 낮은 쪽이 더 자연스럽다고 봤지만, 코드에서는 말 그대로 숫자 하나만 바꾸면 변경 가능함. 그래서 여기 올린 것이고, 실제 피드백이 필요함

  • 어떤 종류의 구조적 치환을 하려는 순간 이 방식은 충분해 보이지 않음. 예를 들어 s/"([^"]*)"/'$1'/ 같은 것을 하고 싶을 때가 있음
    거기에 더해 [^"] 중 [']와 매칭되는 것을 \'로 바꿀 수 있다면 더 유용해 보임
    더 일반적으로는 정규식이 매칭 결과에 대해 사실상 파스 트리를 정의하므로, 그 트리에 더 일반적인 변환을 수행할 수 있으면 유용함

    • 내가 제대로 이해했다면 다음 ttre 표현식이 원하는 일을 함:
      ":'(':(\\')|[^"'])*":'
    • 제대로 이해했다면 "..." 블록 안의 내용을 바꾸고 따옴표를 작은따옴표 '로 바꾸고 싶은 것임
      이 표현식으로 가능함:
      echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"
      결과는 '-' '-'임
      즉 ".+?:-" 표현식으로 "" 안의 텍스트를 - 기호로 치환하면서 동시에 주변 따옴표도 바꿈. 물음표는 비탐욕 모드를 뜻함

  • “정규식은 텍스트에서 패턴을 찾는 훌륭한 도구지만, 텍스트 편집에는 항상 부자연스럽게 느껴졌다”는 주장에 프로젝트 전체가 걸려 있는 듯한데, 정작 예제가 하나도 없음
    정규식이 편집에 왜 부자연스러운지 이해가 안 됨. 여기서 편집이 무엇을 뜻하는지도 모르겠고, 사람들이 왜 그룹에서 어려움을 겪는지도 모르겠음
    이 프로젝트 문법 예제는 많지만, 왜 일반 정규식보다 나은지 모르겠음. “기본 정규식 버전은 이렇고, 내 버전은 이렇고, 그래서 더 쉬워진다”는 예제가 몇 개 있으면 프로젝트를 이해할 수 있을 것 같음

    • 정규식은 보통 한 번 쓰고 다시 고치지 않는 성격이 강하다고 봄. 그 너머를 보려는 프로토타입을 만드는 건 이 분야의 더 나은 미래를 탐색하는 좋은 방법임
    • 타당한 지적임. 가장 명확한 예는 문맥 안에서만 바꾸기가 필요할 때임
      예를 들어 x와 z 사이에 있는 y만 Y로 바꾸려면 Python에서는 대략 이렇게 함:
      pattern = r'(x)y(z)'
      replacement = r'\1Y\2'
      result = re.sub(pattern, replacement, text)
      나는 이를 xy:Yz 패턴으로 대체하고 싶음:
      result = re.trre('xy:Yz', text)
      x, z가 더 복잡한 패턴이거나 정규식 자체라면 이 접근이 더 편할 수 있음
    • 정규식만으로는 편집 기능을 제공하지 않는다고 보는 게 맞음. 그룹은 있지만, 그 그룹을 조합하려면 sed 같은 다른 언어를 써야 함
    • 치환 얘기임. 작성자의 문법으로는 치환을 표현하기가, 말 그대로 타이핑하기가 더 쉬움
      좋은 프로젝트임

  • C 코드가 읽기 정말 즐거움. 아주 좋고, 지금 읽는 중임
    간단한 코멘트 하나만 하자면 README의 theory.pdf 링크가 깨져 있음. PDF가 docs/ 디렉터리에 있으니 URL에 docs/만 포함하면 됨

    • 피드백과 오타 지적 고마움. 고쳤음. 사실 내 C 실력은 꽤 녹슬어서 조금 불안함

  • 오른쪽 부분에 *나 +를 쓰면 무한 루프가 날 수 있으니 피하라고 되어 있는데, 그냥 금지하면 안 되나?
    문법 명세가 더 어려워진다는 건 이해하지만, 유지할 좋은 이유는 없어 보임

    • 타당한 지적이고 동의함. 지금은 비활성화하는 편이 낫겠음
      원래 이유는 변환기 합성이라는 재미있는 연산을 구현하려던 것이었음. 문자열에 간단한 연산을 하고 trre를 필터처럼 합성할 수 있지만, 아직 완성하지 못했음. 그래서 역시 타당한 지적임

  • 멋진 탐구지만, 실제로 왜 더 나은지에 대한 예제가 부족함. 물론 내가 정규식에 너무 오래 익숙해져서 그럴 수도 있음
    예를 들어 trre의 (cat):(dog)가 s/cat/dog보다 왜 나은지, (x:)or가 s/xor/or보다 무엇이 나은지 모르겠음. 거의 모든 예제가 머릿속에서는 비교적 쉬운 정규식으로 대응됨
    핵심 장점이 있다면 그룹 논리 쪽일 것 같으니, 예제도 그쪽에 집중하면 좋겠음. 기본 문법을 설명하기 전부터 왜 더 나은 선택인지 먼저 설명하는 편이 나아 보임
    시저 암호 예제는 “이걸 역방향으로 적용” 기능이 너무 필요해 보임. 많은 텍스트 치환에서 흔한 요청이고, 이 예제에서는 특히 명확함. 프로그래머 머리는 즉시 “왜 같은 논리를 두 번 표현해야 하지?”라고 외치게 됨
    아직 유용한지는 모르겠지만, 오래 자리 잡은 현상 유지에 대한 대안을 탐색하는 건 훌륭함. 보통 그런 시도는 성공하지 못할 가능성도 크지만, 그래도 탐구 자체는 보기 좋음

  • 명세가 꽤 부족해 보임. 첫 예제부터 이상함:
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    여기서 무슨 일이 일어나는지 모르겠음. 문법은 다음처럼 되어 있음:
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    여기서 파스 트리는 무엇인가? 왜 c가 da로 바뀌지 않는가? 또는 왜 c가 제거되고 da가 ot로 바뀌지 않는가?
    그룹 연산자보다 직관적인 검색/치환 의미를 갖는다는 아이디어는 좋음. MS-DOS 시절에는 ren .log .txt 같은 걸 할 수 있었고 동작했는데, 현대의 bash식 사고로는 말도 안 되지만 딱 보면 의도는 매우 분명했음

    • 이건 연산자 우선순위와 토큰화의 문제임. 이 언어에서 토큰은 단일 문자이고, 문자 사이에는 보이지 않는 연산자가 있음
      그 연산자를 명시적으로 ~라고 부르면 예제는 이렇게 보임:
      $ echo 'cat' | trre 'c:d~a:o~t:g'
      dog
      불필요한 괄호를 넣으면 이렇게 됨:
      $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
      dog
    • 문법은 명세가 부족함. 전체 문법은 더 복잡함. 현재 버전은 문서에서 제거해야 할 것 같고, 지금은 실제로 혼란스럽게 만듦
      왜 c가 da로 바뀌지 않느냐는 건 전부 우선순위 때문임. 이 토론을 보면 내가 잘못된 우선순위를 고른 것 같고, 그게 혼란을 일으킴
      현재 우선순위 표는 다음과 같음:
      | 1 | 이스케이프 문자 | \ |
      | 2 | 대괄호 표현식 | [] |
      | 3 | 그룹화 | () |
      | 4 | 단일 문자 ERE 반복 | * + ? {m,n} |
      | 5 | 변환 | : |
      | 6 | 연결 | . (암시적) |
      | 8 | 선택 | | |
      그래서 :가 . 즉 암시적 연결보다 강하게 결합함
    • 맞음, 명세가 부족함. 삭제 예제는 빈 문자열도 REGEX일 수 있음을 보여줌. 그러면 사실상 어떤 위치든 원하는 만큼 많은 빈 문자열 정규식을 포함한다고 볼 수 있어서 파스가 무한히 많아짐
      대신 정규식이 비어 있으면 안 된다고 요구하면 삭제 예제는 깨지지만, 모호성은 연결 쪽으로 넘어감. 즉 (((c:d)(a:o))(t:g))인지 ((c:d)((a:o)(d:g)))인지가 모호해짐. 결합성을 가정하면 이 차이는 중요하지 않을 것임
    • 동작 느낌으로는 c:d, a: 즉 없음, 그리고 ot:g처럼 보임
      하지만 다시 읽어 보니 확실히 혼란스럽고, 이론적으로는 지적이 타당함. 저장소를 읽은 뒤에는 나도 c가 da로 바뀌어야 한다고 믿게 됐지만 확신은 없음
답변달기