Regular Expressions
정규 표현식 엔진 유형

NFA

NFA (Nondeterministic Finite Automaton) 엔진은 패턴에 의해 구동됩니다 .

원리

정규식 패턴은 트리로 파싱됩니다.

현재 위치 포인터가 입력 문자열의 시작으로 설정되고이 위치에서 일치가 시도됩니다. 성냥이 성사되면, 위치는 문자열의 다음 문자로 증가하고이 위치에서 다른 성냥이 시도됩니다. 이 프로세스는 일치하는 항목이 발견되거나 입력 문자열의 끝에 도달 할 때까지 반복됩니다.

매치 시도마다

알고리즘은 주어진 시작 위치에 대한 패턴 트리를 탐색하여 작동합니다. 트리를 진행하면서 일치하는 문자를 사용하여 현재 입력 위치 를 업데이트합니다.

알고리즘이 현재 위치의 입력 문자열과 일치하지 않는 트리 노드를 발견하면 역 추적 해야합니다. 이 작업은 트리의 부모 노드로 돌아가서 현재 입력 위치를 부모 노드를 입력 할 때의 값으로 재설정하고 다음 대체 분기를 시도하여 수행됩니다.

알고리즘이 트리를 종료하도록 관리하면 성공한 일치를보고합니다. 그렇지 않으면 모든 가능성이 시도되면 일치가 실패합니다.

최적화

Regex 엔진은 대개 더 나은 성능을 위해 몇 가지 최적화를 적용합니다. 예를 들어 일치 항목이 주어진 문자로 시작되어야한다고 판단한 경우 해당 문자가 나타나는 입력 문자열의 해당 위치에서만 일치를 시도합니다.

예

a(b|c)a 를 입력 문자열 abeacab 과 abeacab .

패턴 트리는 다음과 유사 할 수 있습니다.

CONCATENATION
    EXACT: a
    ALTERNATION
        EXACT: b
        EXACT: c
    EXACT: a

경기는 다음과 같이 진행됩니다.

a(b|c)a      abeacab
^            ^

a 가 입력 문자열에서 발견되면이를 소비하고 패턴 트리의 다음 항목 인 alternation으로 진행합니다. 첫 번째 가능성을 시도하십시오 : 정확한 b .

a(b|c)a      abeacab
  ^           ^

b 가 발견되면 교대가 성공하고, 그것을 소비하고 연결의 다음 항목으로 진행합니다. 정확한 a :

a(b|c)a      abeacab
      ^        ^

a 가 예상 위치에서 발견 되지 않습니다 . 교대로 역 추적하고 교대로 처음 입력했을 때의 값으로 입력 위치를 재설정하고 두 번째 대안을 시도하십시오.

a(b|c)a      abeacab
    ^         ^

c 는이 위치에 없습니다 . 연결을 역 추적하십시오. 이 시점에서 시도 할 수있는 다른 방법은 없으므로 문자열 시작 부분에 일치 항목이 없습니다.

다음 입력 위치에서 두 번째 일치 시도 :

a(b|c)a      abeacab
^             ^

a 이 일치하지 않습니다. 다른 위치에서 다음 경기를 시도하십시오 :

a(b|c)a      abeacab
^              ^

행운도 없습니다. 다음 위치로 이동하십시오.

a(b|c)a      abeacab
^               ^

일치하는, 그래서 소비와 교대를 입력 :

a(b|c)a      abeacab
  ^              ^

b 가 일치하지 않습니다. 두 번째 대안을 시도하십시오 :

a(b|c)a      abeacab
    ^            ^

c 일치하므로 소비하고 연결의 다음 항목으로 넘어갑니다.

a(b|c)a      abeacab
      ^           ^

일치, 그리고 나무의 끝에 도달했습니다. 일치하는 항목 신고 :

a(b|c)a      abeacab
                \_/

DFA

DFA (Deterministic Finite Automaton) 엔진은 입력에 의해 구동됩니다 .

원리

이 알고리즘은 입력 문자열을 한 번 검사하고 일치 할 수있는 정규식의 가능한 모든 경로를 기억합니다. 예를 들어 패턴에서 교번이 발생하면 두 개의 새로운 경로가 만들어지고 독립적으로 시도됩니다. 주어진 경로가 일치하지 않으면 설정된 경로에서 삭제됩니다.

시사점

일치하는 시간은 입력 문자열 크기로 제한됩니다. 역 추적은 없으며 엔진은 여러 개의 일치 항목을 동시에 찾을 수 있습니다.

이 방법의 주된 단점은 NFA 엔진 유형과 비교하여 엔진이 지원할 수있는 감소 된 기능 세트입니다.

예

abadaca 와 a(b|c)a 를 abadaca .

abadaca      a(b|c)a
^            ^        Attempt 1      ==> CONTINUE

abadaca      a(b|c)a
 ^           ^        Attempt 2      ==> FAIL
               ^      Attempt 1.1    ==> CONTINUE
                 ^    Attempt 1.2    ==> FAIL

abadaca      a(b|c)a
  ^          ^        Attempt 3      ==> CONTINUE
                   ^  Attempt 1.1    ==> MATCH

abadaca      a(b|c)a
   ^         ^        Attempt 4      ==> FAIL
               ^      Attempt 3.1    ==> FAIL
                 ^    Attempt 3.2    ==> FAIL

abadaca      a(b|c)a
    ^        ^        Attempt 5      ==> CONTINUE

abadaca      a(b|c)a
     ^       ^        Attempt 6      ==> FAIL
               ^      Attempt 5.1    ==> FAIL
                 ^    Attempt 5.2    ==> CONTINUE

abadaca      a(b|c)a
      ^      ^        Attempt 7      ==> CONTINUE
                   ^  Attempt 5.2    ==> MATCH

abadaca      a(b|c)a
       ^       ^      Attempt 7.1    ==> FAIL
                 ^    Attempt 7.2    ==> FAIL