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

> Clean Markdown view of GeekNews topic #19132. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=19132](https://news.hada.io/topic?id=19132)
- GeekNews Markdown: [https://news.hada.io/topic/19132.md](https://news.hada.io/topic/19132.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-02-09T09:46:10+09:00
- Updated: 2025-02-09T09:46:10+09:00
- Original source: [github.com/c0stya](https://github.com/c0stya/trre)
- Points: 1
- Comments: 1

## Topic Body

- # TRRE: 전환 정규 표현식

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

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

- ## 예제

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

  - ### 전환을 통한 정규 표현식
    - **교대** 사용:
      ```bash
      $ echo 'cat dog' | trre 'c:bat|d:hog'
      bat hog
      ```
    - **스타**를 사용하여 변환 반복:
      ```bash
      $ echo 'catcatcat' | trre '((cat):(dog))*'
      dogdogdog
      ```

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

  - ### 생성기
    - **`trre`**는 단일 입력에 대해 여러 출력 문자열을 생성할 수 있음.
    - **이진 시퀀스:**
      ```bash
      $ 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의 논문에서 영감을 받음.

## Comments



### Comment 34335

- Author: neo
- Created: 2025-02-09T09:46:10+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=42974378) 
* Cool, 이 프로젝트의 발전이 기대됨
  - 연산자 우선순위가 자연스럽지 않다고 느낌
  - `cat:dog`이 `(cat):(dog)`보다 `ca(t:d)og`로 해석되는 것이 이상함

* XFST (Xerox Finite-State Transducer)를 추천함
  - 20년 이상 컴퓨터 언어학에 사용된 도구임
  - 핀란드어 형태소 분석에 FST를 사용하는 사례를 들음

* 표준 정규 표현식의 대안으로 Rosie Pattern Language를 추천함
  - 그룹 논리에서 어려움을 겪는 사람들에게 유지보수 가능한 대안이 될 수 있음
  - 관련 링크 제공: [GitLab](https://gitlab.com/rosie-pattern-language/rosie/-/blob/master/doc/i-know-regex.md), [Rosie 공식 사이트](https://rosie-lang.org/about/)

* 1997년에 유한 상태 변환기에 대한 논문을 작성한 경험을 공유함
  - 주제는 형태소 분석이었으며, 과소평가된 주제였음
  - 구문에 대해 `:`가 `ab`보다 강하게 결합되도록 설정하는 것이 맞는지 질문함

* 구조적 치환을 수행할 때 충분하지 않다고 느낌
  - 정규 표현식이 매치된 부분에 대해 구문 트리를 정의하므로, 트리의 일반적인 변환을 수행할 수 있으면 유용할 것임

* 정규 표현식이 텍스트 편집에 부자연스럽다는 주장에 의문을 가짐
  - 프로젝트의 목적이 이 주장에 달려 있지만, 예시가 없음
  - 그룹 사용에 어려움을 겪는 이유를 이해하지 못함
  - 정규 표현식보다 이 프로젝트의 문법이 더 나은 이유를 설명하는 예시가 필요함

* C 코드가 매우 깔끔하다고 칭찬함
  - README의 `theory.pdf` 링크가 잘못되어 수정이 필요함

* `*`나 `+`를 사용하지 말라는 조언에 대해 의문을 가짐
  - 문법을 더 복잡하게 만들겠지만, 이를 허용하지 않는 것이 더 나을 것임

* 첫 번째 예시가 이상하다고 느낌
  - `echo 'cat' | trre 'c:da:ot:g'`의 결과가 이상함
  - 구문 트리가 어떻게 구성되는지 이해하기 어려움
  - MS-DOS 시절의 검색/치환 방식이 더 직관적이라고 느낌

* 예시들이 실제 프로그램의 출력인지 의문을 가짐
  - 문법에 대한 이해가 부족할 수 있지만, 예시들이 잘못된 것처럼 보임
  - `echo 'cat dog' | trre 'c:bat|d:hog'`의 결과가 이상함