☰

교대로 가장 짧은 일치 항목을 선택하는 방법이 있습니까?

tag-icon • tag-icon awk grep regular-expression
교대로 가장 짧은 일치 항목을 선택하는 방법이 있습니까?

나는 grep과 awk가 NFA(Non-Deterministic) 정규식 기계를 사용한다는 인상을 받았습니다.
이 페이지 중간에 있는 이미지정규식 일치는 간단하고 빠를 수 있습니다.그 사실을 확인합니다.

첫 번째 교체가 일치하면 NFA 구현이 중지될 수 있는 것으로 알려져 있습니다. 예를 들어 링크된 기사의 NFA 머신은 다음과 같습니다.예를 들어, abab|abbb에 대한 NFA를 고려해보세요.:

여기에 이미지 설명을 입력하세요

정규식에 해당하는 것은 첫 번째 와 일치할 때 abab|abbb문자열과 오른쪽의 일치 상태에 도달합니다 . 그 시점에서는 끝까지 도달하여 매칭 상태로 정지하게 된다(S10). 또 다른 일치가 가능 하더라도 더 많은 입력을 테스트할 필요가 없습니다 .ababbbbabababbb

즉, 이 코드에서는 다음과 같습니다.

echo 'catfish' | grep -Eo 'cat|catfish'

결과는 이어야 cat하지만 입니다 catfish. 교대를 바꿔도 결과는 동일합니다.

grep 정규식 엔진이 항상 가장 긴 일치 항목을 찾는 이유는 무엇입니까?

그리고 그 기본값을 변경할 수 있나요?

답변1

표준에서는 실제로 가장 긴 일치를 요구하기 때문에 POSIX 호환 grep또는 으로 이를 수행할 수 있는 방법이 없다고 생각합니다 (예를 들어 맨페이지 참조).awkregex(7)

예를 들어 프로그램과 정규 표현식을 awk수정하여 원하는 출력을 얻을 수 있습니다.awk

echo 'SetValue' | awk '{ if (match($0, /Set(Value)?/)) { print substr($0, RSTART, 3); }

pcregrep이 상황에서는 다음을 사용하여 번호가 매겨진 하위 그룹을 지정할 수 있는 (pcre perl 호환 정규 표현식 라이브러리의 일부) 에 도달합니다 -o.

echo SetValue | pcregrep -o1 '(Set)(Value)?'

또는 pcre에는 탐욕스럽지 않은 일치를 위한 구문이 있기 때문에

echo SetValue | pcregrep -o0 'Set(Value)??'

답변2

내가 이해할 수 있는 한, 실제로 다음과 같은 것들이 있다는 것이 밝혀졌습니다.두 개의 NFA 머신:

  • 기존 NFA 엔진
    역추적 및 다음을 수행하는 NFA 머신입니다.가장 긴 왼쪽 일치 항목이 항상 존중될 수는 없습니다..

  • POSIX NFA 엔진
    모든 상태를 병렬로 처리하고 입력 문자열에서 일치하는 항목을 선택할 수 있는 비역추적 NFA 엔진입니다. 가장 왼쪽에서 가장 긴 일치 항목을 선택하는 것은 POSIX 요구 사항입니다.

그러나 DFA 역추적 시스템(Perl)은기하급수적으로 폭발하다(2^n)정규식이 아닌 텍스트에 의해 구동되며 첫 번째 대체 항목을 선택할 수도 있고 선택하지 않을 수도 있습니다.

또한DFA는 가능한 모든 일치 항목을 동시에 인식합니다..

그리고 질문에 링크된 기사의 저자는re2 구현은 대체를 다음과 같이 정의합니다: x|y ==> x 또는 y(x 선호)즉, 첫 번째 교대를 선호합니다.

따라서 결론적으로 특정 구현에 따라 대체 부분이 선택될 NFA 또는 DFA를 실제로 연관시킬 수 있는 방법이 없습니다.

그리고 아니요. 특정 구현에 기본값을 변경하도록 지시하는 방법을 찾지 못했습니다.

관련된:

관련 정보