정규 표현 식 일치 분석 과정 분석(정규 표현 식 일치 원리)

정규 표현 식 에 대한 소개 글 이 여러 편 있 습 니 다.정규 표현 식 을 점점 더 많이 사용 하면 서 성능 을 최적화 시 키 고 정규 표현 식 의 쓰기 가 Bug 와 일치 하 는 것 을 줄 이려 고 합 니 다.우 리 는 정규 표현 식 의 집행 과정 을 더욱 깊이 이해 해 야 한다.다음은 정규 표현 식 의 실행 과정 을 함께 학습 하고 분석 합 니 다.우 리 는 regexbuddy 테스트 도구 로 실행 과정 을 분해 하고 구체 적 인 도 구 를 사용 할 것 입 니 다.정규 표현 식 성능 테스트 도구 추천,최적화 도구 추천(regexbuddy 추천)을 볼 수 있 습 니 다.정규 표현 식 해석 과정 을 이해 하기 전에 우 리 는 먼저 몇 가지 개념 을 익 혀 야 한다.
일반 정규 표현 식 엔진
엔진 은 정규 표현 식 일치 방법 과 내부 검색 과정 을 결정 하여 중요 한 것 을 알 게 되 었 습 니 다.현재 주요 유행 엔진 은 DFA,NFA 두 가지 엔진 이 있 는데 우 리 는 비교적 구분한다.
엔진.
차이 점
DFA
Deterministic finite automaton
확정 형 은 가난 한 자동 동기 가 있다.
DFA 엔진 은 역 추적 을 요구 하지 않 습 니 다.(따라서 똑 같은 문 자 를 두 번 테스트 하지 않 습 니 다)그래서 일치 속도 가 빠 릅 니 다!DFA 엔진 은 가장 긴 가능 한 문자열 과 일치 할 수 있 습 니 다.그러나 DFA 엔진 은 제 한 된 상태 만 포함 하기 때문에 역방향 참조 모드 와 일치 하지 않 고 하위 표현 식 을 캡 처 할 수 없습니다.대표 적 으로 awk,egrep,flex,lex,MySQL,Procmail
NFA
Non-deterministic finite automation 비 확정 형 은 가난 한 자동 동기 가 있 고 전통 적 인 NFA,Posix NFA 로 나 뉜 다.
전통 적 인 NFA 엔진 은 이른바'탐 욕 스 러 운'일치 추적 알고리즘(longest-leftmost)을 실행 하여 정규 표현 식 의 모든 가능 한 확장 을 지정 한 순서 로 테스트 하고 첫 번 째 일치 항목 을 받 아들 입 니 다.전통 적 인 NFA 역 추적 은 똑 같은 상태 에 여러 번 접근 할 수 있 으 며,최 악의 경우 에는 실행 속도 가 매우 느 릴 수 있 지만,하위 매 칭 을 지원 합 니 다.대표 적 으로 GNU Emacs,Java,ergp,less,more,.NET 언어,
PCRE library,Perl,PHP,Python,Ruby,sed,vi 등 일반 고급 언어 는 모두 이 모델 을 사용한다.
DFA 는 정규 표현 식 과 일치 하 는 문자열 문 자 를 찾 고 NFA 는 정규 표현 식 을 위주 로 문자열 에서 하나씩 찾 습 니 다.속도 가 느 리 지만 조작 자 에 게 는 더 간단 하기 때문에 응용 이 더욱 광범 위 합 니 다!다음은 NFA 엔진 의 예 를 들 어 분석 과정 을 설명 합 니 다!
엔진 에 보 이 는 문자열 구성 분석
문자열"DEF"의 경우 D,E,F 세 글자 와 0,1,2,3 네 개의 숫자 위치:0D1E2F 3 를 포함 하고 정규 표현 식 에 있어 모든 소스 문자열 은 문자 와 위치 가 있 습 니 다.정규 표현 식 은 0 번 위치 에서 하나씩 일치 합 니 다.
문자 와 0 너비 차지
정규 표현 식 이 일치 하 는 과정 에서 하위 표현 식 이 위치 가 아 닌 문자 내용 에 일치 하고 최종 일치 결과 에 저장 된다 면 이 하위 표현 식 은 문 자 를 차지 하고 있다 고 생각 합 니 다.하위 표현 식 이 일치 하 는 위치 나 일치 하 는 내용 이 최종 일치 결과 에 저장 되 지 않 는 다 면 이 하위 표현 식 은 0 너비 라 고 생각 합 니 다.점유 문 자 는 서로 배척 하 는 것 이 고,0 폭 은 서로 배척 하 는 것 이 아니다.즉,하나의 문자 입 니 다.같은 시간 에 하나의 표현 식 만 일치 할 수 있 고 한 위 치 는 여러 개의 0 너비 의 하위 표현 식 으로 일치 할 수 있 습 니 다.흔히 볼 수 있 는 0 너비 문 자 는:^,(?=)이다.기다리다
정규 표현 식 일치 프로 세 스 상세 설명 인 스 턴 스
우 리 는 위의 몇 가지 개념 을 파악 하고 다음 에 몇 가지 흔히 볼 수 있 는 해석 과정 을 분석 했다.소프트웨어 regexBuddy 를 결합 하여 분석 합 니 다.
데모 1:원본 문자 DEF,대응 하 는 표 시 는:0D1E2F 3,정규 표현 식 과 일치 하 는 것 은:/DEF/

프로 세 스 는 다음 과 같이 이해 할 수 있 습 니 다.먼저 정규 표현 식 문자/D/에서 제어 권 을 얻 고 위치 0 부터 일치 하 며/D/에서'D'와 일치 합 니 다.일치 하 는 데 성공 하고 제어 권 은 문자/E/에 게 맡 깁 니 다."D"가/D/와 일치 하기 때문에/E/는 위치 1 부터 매 칭 을 시도 합 니 다./E/에서"E"와 일치 합 니 다.매 칭 성공,제어 권 은/F/에 게 맡 깁 니 다./F/에서"F"와 일치 합 니 다.일치 합 니 다.
Demo 2:원본 문자 DEF,대응 하 는 표 시 는 0D1E2F 3 이 고 정규 표현 식 과 일치 하 는 것 은:/D\w+F/입 니 다.

프로 세 스 는 다음 과 같이 이해 할 수 있 습 니 다.먼저 정규 표현 식 문자/D/에서 제어 권 을 얻 고 위치 0 부터 일치 합 니 다./D/에서"D"와 일치 합 니 다.일치 성공,제어 권 은 문자/\w+/에 게 전 달 됩 니 다."D"가/D/와 일치 하기 때문에/\w+/위치 1 부터 일치 하려 고 시도 합 니 다.\w+탐욕 모드 는 예비 상 태 를 기록 합 니 다.기본 값 은 최 장 문자 와 일치 하고 EF 에 직접 일치 하 며 일치 합 니 다.현재 위치 3 입 니 다.그리고 통제 권 을/F/에 게 건네준다./F/매 칭 에 실 패 했 습 니 다.\w+매 칭 은 한 자 리 를 거 슬러 올 라 가 현재 위 치 는 2 가 됩 니 다.그리고 제어 권 을/F/로 건 네 주 고/F/일치 문자 F 에 성공 하 였 습 니 다.따라서\w+여 기 는 E 문자 와 일치 합 니 다.일치 완료!
Demo 3:원본 문자 DEF,대응 하 는 표 시 는:0D1E2F 3 이 고 정규 표현 식 과 일치 하 는 것 은:/^(?=D)[D-F]+$/

프로 세 스 는 다음 과 같이 이해 할 수 있 습 니 다:메타 문자/^/와/$/일치 하 는 것 은 위치,순서 로 둘 러 보기/(?=D)/(현재 위치 와 일치 하고 오른쪽 에 문자'D'문자 가 있 는 지 여부)일치 만 합 니 다.문자 가 없 으 며 일치 하 는 내용 을 최종 일치 결과 에 저장 하지 않 기 때문에 모두 0 너비 입 니 다.먼저 원 문자/^/에서 제어 권 을 얻 고 위치 0 부터 일치 합 니 다./^/일치 하 는 것 은 시작 위치'위치 0'입 니 다.일치 하 는 성공,제어 권 은 순서 로 둘 러 보기/(?=D)/；/(?=D])/위치 오른쪽 에 알파벳'D'가 있어 야 일치 할 수 있 습 니 다.0 너비 의 하위 표현 식 은 서로 배척 하지 않 습 니 다.즉,같은 위 치 는 여러 개의 0 너비 서브 표현 식 으로 동시에 일치 할 수 있 기 때문에 위치 0 에서 일치 하려 고 시도 합 니 다.위치 0 의 오른쪽 은 문자'D'입 니 다.요구 에 부합 되 고 일치 하 며 성공 적 이 며 통제 권 은/[D-F]+/에 게 전달 합 니 다.왜냐하면D)/일치 만 하고 일치 하 는 내용 을 마지막 결과 에 저장 하지 않 습 니 다.그리고/(?=D)/매 칭 에 성공 한 위 치 는 위치 0 이 므 로/[D-F]+/도 위치 0 부터 매 칭 을 시도 합 니 다.이것 은 끝 위치,즉'위치 3'과 일치 합 니 다.일치 합 니 다.이 때 정규 표현 식 이 일치 합 니 다.보고서 가 일치 합 니 다.매 칭 결 과 는"DEF"이 고 시작 위 치 는 0 이 며 끝 위 치 는 3 입 니 다.그 중/^/일치 하 는 위치 0,/(?=D)/일치 하 는 위치 0,/[D-F]+/일치 하 는 문자열"DEF",/$/일치 하 는 위치 3.
후기:위의 이 몇 가지 예 에서 우 리 는 정규 표현 식 의 일반적인 일치,그리고 역 추적 과정 을 분석 한 다음 에 0 너비 문자,일치 과정 을 분석 했다.물론 제 시 된 예 는 비교적 간단 하고 실제 과정 에서 더 길 고 복잡 한 정규 표현 식 을 만 날 수 있다.그러나 사상 은 유사 하 다.우리 가 나 를 원 리 를 해석 하기 만 한다 면 하나하나 분해 할 수 있다.자,여기까지 입 니 다.교 류 를 환영 합 니 다!