두 정규식의 차이와 교집합 계산

 (phylactery.org)
2P by GN⁺ | ★ favorite | 댓글 1개
  • 정규식을 문자열 집합처럼 비교해야 할 때, antimirov는 두 식 α와 β의 포함 관계와 동등성, 교집합·차집합을 한 화면에서 계산해 줌
  • 결과 영역은 보수와 관계식을 함께 보여주며, ~α, α < β, α = β, α & β, α ^ β, α - β 같은 연산을 확인할 수 있음
  • 별도 문자열 s를 넣으면 s ∈ α, s ∈ β로 각 정규식의 매칭 여부를 바로 검증 가능함
  • 문법은 ., 연결, 선택 |, 반복 *·+·?·{n}·{m,n}, 문자 그룹, 부정 문자 그룹, 이스케이프, UTF-16 유니코드 이스케이프를 지원함
  • 앵커, 영폭 단언, 역참조, 하위 그룹 추출, 검색·부분 매칭, 대소문자 무시 같은 동작 변경 기능은 지원하지 않음

정규식 비교와 집합 연산

  • 입력 영역은 두 정규식 α와 β를 받음
  • 출력은 두 정규식의 보수와 관계·집합 연산을 함께 보여줌
    • ~α, ~β: 각 정규식의 보수
    • α < β, α = β, α > β: 두 정규식의 포함 관계와 동등성
    • α & β: 교집합
    • α ^ β: 대칭차
    • α - β: 차집합
  • 문자열 s를 입력하면 s ∈ α, s ∈ β 형태로 각 정규식에 속하는지 확인 가능함
  • 각 정규식의 크기와 DFA 상태 수도 표시함
    • 예시 화면에서는 |α| = 1, |β| = 1
    • 예시 화면에서는 dfa(α)와 dfa(β)가 각각 1개 상태를 가짐

지원하는 정규식 문법

  • 기본 연산자는 단일 문자, 연결, 선택, 반복을 다룸
    • .: 임의의 단일 문자 매칭
    • xy: x 다음에 y를 매칭하는 연결
    • x|y: x 또는 y 매칭
    • x*: 0회 이상 반복
    • (xyz): 그룹화
    • (): 빈 문자열을 매칭하는 빈 정규식
  • 자주 쓰는 반복 축약 문법도 지원함
    • x+: 1회 이상 반복, xx*와 동등함
    • x?: 선택적 매칭, (x|)와 동등함
    • x{n}: x를 n번 연결
    • x{m,n}: x를 m번 이상 n번 이하 연결
  • 문자 집합과 이스케이프는 다음 형태를 사용할 수 있음
    • [a-z0-9]: 그룹 안의 단일 문자 매칭
    • [^a-z0-9]: 그룹에 없는 단일 문자 매칭
    • \c: 특수 문자 c 이스케이프
    • \u001a: 대응하는 UTF-16 문자 매칭
    • 그 외 a, b, c 같은 문자는 자기 자신을 매칭함

지원하지 않는 기능

  • antimirov는 정규식을 집합 연산 대상으로 다루는 데 초점을 두며, 다음 기능은 제외됨
    • 앵커 ^, $
      • 단, ^와 $는 여전히 이스케이프해야 함
    • 영폭 단언 예: (?=...), (?<=...)
    • 역참조 예: \1, \2
    • 하위 그룹 추출
    • 검색 또는 부분 매칭
    • 대소문자 무시처럼 동작을 바꾸는 다른 플래그
  • 자세한 정보는 non/antimirov에서 확인할 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 정규식이 파싱 → NFA → DFA → 최소 DFA로 바뀌는 과정을 보여주고, 최소 DFA에서 LLVM IR/Javascript/WebAssembly까지 출력하는 비슷한 웹 데모를 만들었음
    http://compiler.org/reason-re-nfa/src/index.html

  • 이 라이브러리는 문자열 클래스 계층을 만드는 데 쓸 수 있고, 그 결과 타입이 있는 문자열을 더 적극적으로 활용할 수 있음
    예를 들어 이메일과 URL은 특수한 문법을 가지며, 그 값의 공간은 모든 비어 있지 않은 문자열의 부분집합이고, 비어 있지 않은 문자열은 모든 문자열의 부분집합임
    타입 시스템이 이메일 문자열이 비어 있지 않은 문자열의 하위 타입이라는 걸 알면, 이메일 주소를 비어 있지 않은 문자열을 요구하는 함수에 넘겨도 유효하다고 판단할 수 있음
    이 라이브러리는 그런 문자열 타입의 정의와 계층을 검증하는 데 쓸 수 있고, 계층 구현은 언어마다 서브클래싱, 트레이트 경계 등으로 달라짐

    • 태그 붙은 합집합 타입이 있는 언어에서는 이런 방식을 자주 씀. Haskell풍 의사코드는 대략 이런 느낌임
      Address 생성자는 내보내지 않고 타입만 내보내며, fromString :: Text -> Maybe Address 안에서 검증하고 잘못된 주소면 Nothing을 반환함
      유효성은 데이터 안에 섞지 말고 별도 경로로 신호를 보내고, 출력이 필요할 때는 toText :: Address -> Text로 감싼 값을 다시 꺼냄
    • 이메일 주소 검증에 정규식을 쓰지 않는 게 좋음
      https://news.ycombinator.com/item?id=31092912
    • 늦여름 아침에 @ 왼쪽에 이메일 주소로 무엇이 허용되고 안 되는지 파고드는 것만큼 묘한 일도 없음
      “유효한 이메일 주소”를 표현하려는 모든 정규식은 틀렸다고 보는 단순한 휴리스틱은 꽤 안전하지만, 재미는 다 망쳐버림
    • “값의 공간”이 무슨 뜻인지 궁금함

  • 정규식은 꽤 멋지고 복잡한 수학 이론을 가치 있는 인터페이스로 묶어낸 좋은 예임
    선형대수도 비슷하게 느껴짐

    • 적절한 체가 주어지면 정말 많은 수학이 선형대수로 바뀔 수 있다는 게 늘 놀라움
      복소평면의 Möbius 변환 w=(az+b)/(cz+d)조차 선형대수로 바꿀 수 있음
    • 보통 그런 경우 표현이 진실에 가까워지고 있다는 뜻임
      좋은 인터페이스에는 본질적인 가치가 있는데, 결과 중심적인 많은 사람들이 그걸 잘 인정하지 않음
    • 기억이 맞다면 Conway의 https://store.doverpublications.com/0486485838.html에서 선형대수와의 연결이 나왔던 것 같음. 대충 훑어보기만 했음

  • 이 멋진 페이지는 정규식 쌍 사이의 이항 관계를 계산하고 DFA를 그래프로 보여줌
    정규식 위에서 수행하는 꽤 비자명한 연산들을 정말 인상적으로 시연함

    • 아주 멋지지만, 엄밀히 말해 더 이상 정규식이 아니게 만드는 기능들을 지원하지 않는 것도 놀랍진 않음
      그래도 ^와 $ 앵커는 문제가 없을 줄 알았음

  • “regex filter numbers divisible by 3”를 붙여넣어 보니 페이지가 완전히 멈췄음: https://stackoverflow.com/q/10992279/41948
    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$
    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
    더 짧은 표현이 있는지 궁금함

    • 이 웹페이지는 상태가 많은 DFA를 만드는 정규식에서 멈춤
      예를 들면 (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog 같은 것들임
    • 어차피 페이지 설명상 앵커는 지원하지 않는다고 되어 있음

  • 문법적으로 유효한 URL과 이메일 주소의 교집합을 보고 싶었는데, 아래 URL 정규식만 입력해도 페이지가 처리하는 데 너무 오래 걸림
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    출처: https://stackoverflow.com/a/3809435/623763

    • (...){1,256} 같은 표현은 매우 무겁고, Scala JS 코드가 결국 시간 초과가 나거나 브라우저를 죽이게 됨
      그걸 (...)+로 바꾸면 적어도 내 환경에서는 동작함. (...){1,6}처럼 작은 표현은 괜찮을 것 같음

  • 합집합과 교집합으로 생성되는 정규식이 특별히 간결하지 않다는 점에 놀랐다가 곧 납득했음
    예를 들어 "y.+"와 ".+z"의 교집합은 "y.*z"라는 아주 단순한 표현으로 쓸 수 있고, 페이지로도 동등성이 확인됨. 하지만 도구는 yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz*를 내놓음
    이런 결과가 나오는 이유는 있겠지만, 문자 수 같은 기준에서 최소 정규식을 내는 건 훨씬 어려울 가능성이 큼

    • 이유 중 하나는 ".+z"가 결정적 오토마톤으로 변환된 뒤 더 크고 지저분해지기 때문일 듯함

  • 예전에 이 개념을 써서 “IP RegEx filter” 설정의 검증 로직을 작성한 적이 있음
    목표는 사용자가 정규식으로 IP 필터를 설정하게 하는 것이었음. 마케팅 쪽은 CIDR을 이해하지 못했고, Google Analytics 때문에 정규식은 알고 있었음
    유효한 정규식을 어떻게 정의할 수 있을까? “모든 IPv4 주소” 정규식과의 교집합이 비어 있지 않고, 동시에 “모든 IPv4 주소” 정규식과 같지도 않아야 했음
    필터가 아무 일도 안 한다는 불만은 많이 막았지만, 잘못된 필터 입력 자체를 막지는 못했음

    • 더 단순한 해법도 가능하지 않았을까? 필터 정규식을 검증하려 하기보다, 샘플 IP 주소를 보여주거나 사용자가 주소 묶음을 넣게 한 뒤 어떤 주소가 매칭되고 어떤 주소가 매칭되지 않는지 보여주면 됨
      잘못된 필터 문제를 다루는 데도 도움이 됨

  • 모바일에서 더 쓰기 좋게 하려면 정규식 입력 필드의 자동 추천을 끄는 게 좋겠음
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • 비슷한 3으로 나누어떨어지는 수 정규식 2개로 페이지를 테스트했는데, 양끝의 ^와 $를 제거해도 멈췄음
    Regex 1: ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))*
    Regex 2: ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))*
    마지막 * 직전까지는 모두 파싱되지만, *를 붙이는 순간 전체 페이지가 멈춤
    *가 없으면 자릿수 합이 3으로 나누어떨어지는 숫자 조각을 파싱하는 유효한 검증기를 만들어냈음

답변달기