[regex] 정규 엔진 이 DFA 인지 NFA 인지 어떻게 판단 합 니까?

[regex] 정규 엔진 이 DFA 인지 NFA 인지 어떻게 판단 합 니까?
일반적인 정규 엔진 은 NFA, DFA, POSIX NFA 로 나 뉘 는데 구분 하기 위해 전 자 는 NFA, NFA 와 DFA 휘발유 타 는 자동차 와 전 기 를 타 는 것 으로 분류 된다. 전 기 를 타 는 사람 은 일반적으로 고 급 스 러 워 보이 고 휘발 유 를 타 는 사람 은 얼핏 보면 무 겁 지만 무 겁 고 풍부 한 메타 문자 의 지원 이 있다.두 가 지 는 실현 에 있어 서도 각각 천추 가 있다. 정규 엔진 이 DFA 인지 NFA 인지 어떻게 판단 하 는 지 살 펴 보 자.
어떻게 판단 합 니까?
우선 명확 한 것 은 DFA 지원 하지 않 는 다 는 것 이다 . 따라서 현재 정규 엔진 의 지원 여부 를 판단 하면 기본적으로 확정 할 수 있다.다 선 구조 로 판단 할 수 있 는 방법 도 있다.
간단 한 문자열 쓰기

nfa not

정규 (nfa | nfa not) 로 일치 합 니 다.
정규 엔진 이 NFA 이면 'nfa' 와 일치 합 니 다. DFA 이 라면 'nfa not' 와 일치 합 니 다. 이것 은 NFA 와 DFA 의 일치 체제 와 관련 이 있 습 니 다.
정규 엔진 이 NFA 이 라면 NFA 이 일치 하기 시 작 했 을 때 다 중 선택 구조 이기 때문에 NFA 왼쪽 에서 오른쪽으로 순서대로 시도 합 니 다. 일치 에 실패 하면 다 중 선택 구조 로 거 슬러 올 라 간 다음 두 번 째 를 시도 합 니 다. 이 문자열 에 맞 을 때 nfa 가 성공 합 니 다!이어서 뒤로 일치 하지 않 고 결 과 를 되 돌려 주지 않 을 것 이다.
정규 엔진 이 DFA 이 라면 DFA 길이 가 가장 긴 다 중 선택 구조의 옵션 을 항상 선택 한 다 는 것 은 무슨 뜻 입 니까?DFA 정규 컴 파일 을 할 때 먼저 일련의 최적화 조 치 를 취해 뒤의 일치 가 더욱 쉬 워 질 수 있 도록 합 니 다. 그래서 믿 지 않 을 수도 있 습 니 다. DFA 모든 일치 가능성 을 기억 할 것 입 니 다. 그러면 그 일치 과정 은 아마 이 럴 것 입 니 다.처음에 "nfa" 와 일치 하 게 되 었 습 니 다. 일치 하 는 데 성 공 했 지만 앞으로 도 계속 일치 하 는 것 을 발 견 했 습 니 다. 그래서 최종 적 으로 "nfa not" 와 일치 합 니 다.DFA 보다 훨씬 빠 른 이유 다.일반적으로 거 슬러 올 라 가 는 것 은 NFA 의 영혼 이다. NFA 에서 거 슬러 올 라 가지 않 는 다. 왜냐하면 처음부터 정칙 의 모든 결 과 를 알 고 있 기 때문에 정칙 의 좋 고 나 쁨 은 영향 을 주지 않 는 다 DFA. 그러나 영향 을 줄 수 있다 DFA. NFA 는 항상 '황하 가 죽지 않 으 면 마음 이 죽지 않 는 다' 는 느낌 을 준다.일반적으로 NFA 매 칭 에 실패 하면 NFA 거 슬러 올 라 가 려 고 합 니 다. 뒤에 성공 할 수 있 는 지 없 는 지 모 르 기 때 문 입 니 다. 그 는 어리둥절 하지만 NFA 처음부터 모든 매 칭 이 가능 하 다 는 것 을 알 고 있 었 습 니 다.