NFA 영혼 - 역 추적

역 추적 원리: 가능 한 모든 표현 식 가 지 를 기록 하고 일치 시 키 려 고 시도 합 니 다. 실패 하면 되 돌아 갑 니 다. 마지막 정확 한 태그 에서 새로운 표현 식 (예비 상태) 으로 새로운 시 도 를 시작 하 십시오.
특성 으로 거 슬러 올 라 갈 수 있 습 니 다: 우선 일치, 우선 일치 무시, 다 중 선택 구조, 환시, 조건 판단, 역방향 참조, 경화 그룹
거 슬러 올 라 가 는 두 가지 원칙:
1. 시도: 우선 양사 (?, *, +, {m, n}) 와 일치 합 니 다.
2. 시도 건 너 뛰 기: 우선 양사 무시 (?, *?)
강제 적 으로 거 슬러 올 라 갈 때 '후진 선 출' 원칙 을 집행 한다. 즉, 오른쪽 에서 왼쪽으로 거 슬러 올 라 가 는 것 이다.
1. 일치 하 는 우선 양사 가 '?'시대 의 흐름 을 되돌아보다
일치 우선 순위
돌 이 켜 보다
돌 이 켜 보지 않다
성공 일치
"ab? c" 가 "ac" 와 일치 합 니 다.
"ab? c" 가 "abc" 와 일치 합 니 다.
일치 하지 않 음
"ab? c" 가 "abx" 와 일치 합 니 다.
"ab? c" 가 "ax" 와 일치 합 니 다.
1、?우선 일치 하 는 양사, 0 번 또는 1 번 을 표시 합 니 다. 일치 하려 고 시도 합 니 다.
2. 역 추적 - 성공 일치:
초기 상태: "a" 와 "
a "매 칭 성공
예비 상태: "ab?, c" + "a, c" – "b?" 와 "
c "일치 하지 않 음, 거 슬러 올 라 가기
역 추적 상태: "ab?, c" + "a, c" – "c" 와 "
c "일치 성공
3. 역 추적 - 일치 하지 않 음:
초기 상태: "a, b? c" + "a, bx" – "a" 와 "
a "매 칭 성공
예비 상태: "ab?, c" + "a, bx" – "b?" 와 "
b "부분 일치 성공
예비 상태: "ab?, c" + "ab, x" – "c" 와 "
x "부분 일치 가 성공 하지 못 했 습 니 다. 거 슬러 올 라 갑 니 다.
역 추적 상태: "ab?, c" + "a, bx" – "c" 와 "
b "전역 일치 가 성공 하지 못 했 습 니 다. 거 슬러 올 라 갑 니 다.
위 역 추적 1:
초기 상태: "ab? c" + "a, bx" – "a" 와 "
b "일치 하지 않 음, 거 슬러 올 라 가기...
우선 [예] 'ab??? c' 가 'abc' 와 일치 하 는 초기 상 태 를 무시 합 니 다. 'a, b?? c' + 'a, bc' – 'a' 가 'a' 와 일치 하 는 예비 상태: 'ab???, c' + 'a, bc' - 'c' 가 'b' 부분 과 일치 하지 않 습 니 다. 역 추적 상태: 'a, b? c' + 'a, bc' - 'b' 가 'b' 와 일치 하 는 예비 상태: 'ab????, c' + 'ab, c' - 'c' 와 'c'일치 성공
우선 순위시, 예비 상 태 를 설정 한 다음 일치 합 니 다. [예비 상 태 를 설정 할 때] 항상 이전 상태 에서 표현 식 제어 권 을 뒤로 이동 합 니 다. (건 너 뛸 수 있 습 니 다. 제어 하 는 문자) 이전 상태의 텍스트 위 치 는 변 하지 않 습 니 다. 그리고 표현 식 으로 텍스트 가 일치 하 는 지 확인 합 니 다. 2 가지 상황 으로 나 누 어 우선 일치 하거나 우선 무시 합 니 다. 1 -[우선 일치 시] [일치 하지 않 으 면] 예비 상태 에 있 는 텍스트 의 위 치 를 검사 한 후 추진 합 니 다. [일치 하지 않 으 면] 예비 상태 로 거 슬러 올 라 갑 니 다.
2 - [우선 일치 무시 시] [일치 하면] 표현 식 과 텍스트 가 계속 정상적으로 일치 합 니 다. [일치 하지 않 으 면] 예비 상태 로 거 슬러 올 라 가면 무시 하 는 표현 식 과 일치 합 니 다.
2. 우선 순위 단어 가 '*' 또는 '+' 일 때 거 슬러 올 라 갑 니 다.
1. * 는 임 의 일치 로 인해 예비 상 태 를 계속 저장 하고 모든 규정 문 자 를 취 소 했 는 지 지도 해 야 합 니 다. 2. '+' 는 최소 1 번 을 표시 하기 때문에 먼저 성공 적 으로 일치 하 는 문 자 를 찾 아야 합 니 다. 이 를 통 해 예비 상 태 를 구축 해 야 합 니 다.
세 가지
앞쪽 위치 에 있 는 분기 가 일치 하 는 데 성공 하면 뒤쪽 의 가 지 는 무시 되 기 때문에 순서대로 배열 해 야 합 니 다. 각 분기 의 선후 순 서 를 명확 하 게 지도 해 야 합 니 다 [예] 일치 날짜: Jan 31 과 유사 합 니 다.
[해석] 1. 존재 할 수 있 는 형식: Jan 01, Jan 1, Jan 23 2. 숫자 부분 은 여러 가지 로 해결 해 야 합 니 다. Jan (0? [1 - 9] | [12] [0 - 9] | 3 [01])
4. 점유 우선 양사 와 경화 그룹
[목적] 특정한 문자 가 일치 하 는 데 성공 한 상황 에서 역 추적 을 포기 합 니 다. 즉, 이전의 예비 상 태 를 포기 하고 뒤로 물 러 서지 않 습 니 다. 방법 은 두 가지 가 있 습 니 다. 경화 그룹 과 점유 우선 양사 1, 경화 그룹 - (? >...)
이 구조 체 가 끝 난 후에 이 구조 체 의 예비 상 태 를 포기 하고 그 전에 일치 하 는 내용 을 하나의 단원 으로 경화 시 켜 전체적으로 보류 하거나 포기 하 는 '잠 금' 상태 이다.
일치 하 는 우선 순위 나 무시 하 는 '차이 점' 은 경화 그룹 이 표현 식 에서 가능 한 그룹 을 포기 하고 거 슬러 올 라 가지 않 아 일부 결 과 를 초래 하 는 것 입 니 다.
(1) 영향 없 음 (2) 매 칭 실패 (3) 매 칭 결 과 를 바 꾸 기 (4) 매 칭 실패 속 도 를 빠르게 합 니 다. 예 를 들 어 '\ w +:' 로 'Number' 를 매 칭 하면 성공 할 수 없 지만 표현 식 은 역 추적 을 해서 속도 에 영향 을 줄 수 있 습 니 다. 따라서 '(? > \ w +)' 는 역 추적 을 포기 하고 실 패 를 빨리 매 칭 할 수 있 습 니 다.
2. 점유 우선 양사 점유 우선 양사:? +, * +, + 와 {m, n} + 점유 우선 양사 가 일치 할 때 예비 상태 가 발생 하지 않 습 니 다. 경화 그룹 과 유사 하지만 간단하게 쓸 수 있 습 니 다. (? > \ w +:) 과 \ w +: 같은 의 미 를 표현 합 니 다.
5. '*' 가 일 으 킨 예
【 예 1 】 ". * ([0 - 9] [0 - 9] [0 - 9]]" 로 텍스트 일치 "I have 12345 dollors"

    ：I have 12345，  45

[해석] '. *' 는 임의의 텍스트 나 공백, 즉 텍스트 가 모두 일치 하 는 것 을 나타 낸다. 그러나 정규 표현 식 이 ([0 - 9] [0 - 9]) 의 통제 권 을 얻 은 후에 's' 는 첫 번 째 [0 - 9] 와 일치 하지 않 고 거 슬러 올 라 가 야 한다. 텍스트 는' r '로 거 슬러 올 라 가 일치 하지 않 고' 5 '로 거 슬러 올 라 가 첫 번 째 [0 - 9] 를 만족 시 키 고 두 번 째 는 일치 하지 않 으 며' 45 '로 거 슬러 올 라 가 야 한다.일치 성공.
[예 2] 따옴표 사이 의 텍스트 와 일치 합 니 다.
My dog’s name is “John”, its brother’s name is “Jack”.
[해석] 1. '. *' 로 일치 하면 'John', its brother 's name is' Jack' 을 얻 을 수 있 습 니 다. 요구 에 부합 되 지 않 기 때문에 중간 에 있 는 작은 따옴표 를 찾 아야 합 니 다. 작은 따옴표 가 아 닌 텍스트 를 얻 을 수 있 습 니 다. '[^'] * '3. 이 법 은' 배제 형 문자 그룹 '이 라 고 부 르 고 우선 순위 단 어 를 무시 할 수도 있 습 니 다.
【 예 3 】 "다 중 문자" 가 HTML 과 일치 하 는 tag 를 가 져 올 때 < p > I have 12345 dollors < / p > and < p > you are 12 < / p > 중 < p > 와 < / p > 사이 의 내용 을 가 져 옵 니 다.
【 해 석 】 1. 이전 예 와 유사 한 더 블 따옴표 입 니 다. 여 기 는 < p > 와 < / p > 2 입 니 다. 우선 일치 하 는 양 어 를 무시 합 니 다 *? 3. "p >. *? < / p >"