☰

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

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

내 생각에 grep과 awk는 NFA(비결정적) 정규식 기계를 사용한다는 것입니다.
이 페이지 중앙에 있는 그림은 다음과 같습니다.정규식 일치는 간단하고 빠릅니다.이것이 실제로 사실인지 확인하십시오.

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

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

해당 정규식은 abab|abbb첫 번째 정규식과 일치할 때 문자열의 오른쪽과 일치하는 상태에 도달합니다. 이때 종료점에 도달하여 매칭 상태에 도달하면 정지하게 된다(S10). 또 다른 일치 항목이 있더라도 추가 입력을 테스트할 필요는 없습니다.ababbbbabababbb

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

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

결과는 이어야 cat하지만 입니다 catfish. 교체 여부에 관계없이 결과는 동일합니다.

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

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

답변1

표준에서는 가장 긴 일치를 요구하기 때문에 POSIX 호환 OR로 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 머신 2대:

  • 기존 NFA 엔진
    추적 가능한 NFA 기계가장 긴 왼쪽 일치 항목이 항상 존중되는 것은 아닙니다..

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

그러나 DFA 역추적기(Perl)는지수 폭발(2^n)정규 표현식이 아닌 텍스트로 구동되며 첫 번째 대체 항목을 선택하거나 선택하지 않을 수 있습니다.

또 있다고 하네요DFA는 가능한 모든 일치 항목을 동시에 식별합니다..

그리고, 질문에 링크된 기사의 작성자로 판단하면,re2 구현은 교대를 다음과 같이 정의합니다: x|y ==> x 또는 y (x가 선호됨)즉, 교대로 첫 번째 항목을 선호합니다.

따라서 요약하자면 대체 부분이 선택될 NFA 또는 DFA를 실제로 연관시킬 수 있는 방법은 없으며 구현에 따라 다릅니다.

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

관련된:

관련 정보