Regular Expressions
Typy silników wyrażeń regularnych

NFA

Silnik NFA (niedeterministyczny automat skończony) jest napędzany przez wzorzec .

Zasada

Wzór wyrażenia regularnego jest przetwarzany na drzewo.

Wskaźnik bieżącej pozycji jest ustawiony na początek ciągu wejściowego i w tej pozycji próbuje się dopasować. Jeśli dopasowanie fais, pozycja jest zwiększana do następnego znaku w ciągu i następuje próba ponownego dopasowania z tej pozycji. Proces ten powtarza się, dopóki nie zostanie znalezione dopasowanie lub nie zostanie osiągnięty koniec ciągu wejściowego.

Dla każdej próby dopasowania

Algorytm działa poprzez wykonanie przejścia drzewa wzorów dla danej pozycji początkowej. W miarę przechodzenia przez drzewo aktualizuje bieżącą pozycję wejściową , zużywając pasujące znaki.

Jeśli algorytm napotka węzeł drzewa, który nie pasuje do ciągu wejściowego w bieżącej pozycji, będzie musiał wykonać powrót . Odbywa się to poprzez powrót do węzła nadrzędnego w drzewie, zresetowanie bieżącej pozycji wejściowej do wartości, którą posiadał po wejściu do węzła nadrzędnego i wypróbowanie kolejnej gałęzi alternatywnej.

Jeśli algorytmowi uda się wyjść z drzewa, zgłasza pomyślne dopasowanie. W przeciwnym razie, po wypróbowaniu wszystkich możliwości, dopasowanie nie powiedzie się.

Optymalizacje

Silniki Regex zwykle stosują pewne optymalizacje dla lepszej wydajności. Na przykład, jeśli ustalą, że dopasowanie musi rozpoczynać się od danego znaku, podejmą próbę dopasowania tylko w tych pozycjach ciągu wejściowego, w których pojawia się ten znak.

Przykład

Dopasuj a(b|c)a do wejściowego ciągu abeacab :

Drzewo wzorów może wyglądać mniej więcej tak:

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

Dopasowanie przebiega następująco:

a(b|c)a      abeacab
^            ^

a znajduje się w ciągu wejściowym, zużyj go i przejdź do następnego elementu w drzewie wzorów: alternacji. Wypróbuj pierwszą możliwość: dokładny b .

a(b|c)a      abeacab
  ^           ^

b zostanie znalezione, więc przemiana się powiedzie, skonsumuj ją i przejdź do następnego elementu w konkatenacji: dokładna a :

a(b|c)a      abeacab
      ^        ^

a nie znajduje się w oczekiwanej pozycji. Wróć do alternacji, zresetuj pozycję wejściową do wartości, którą miała po wprowadzeniu alternacji po raz pierwszy, i wypróbuj drugą alternatywę:

a(b|c)a      abeacab
    ^         ^

c nie znajduje się w tej pozycji. Powrót do konkatenacji. W tym momencie nie ma innych możliwości wypróbowania, więc nie ma dopasowania na początku łańcucha.

Próba drugiego dopasowania na następnej pozycji wejściowej:

a(b|c)a      abeacab
^             ^

się nie zgadza. Spróbuj kolejnego meczu na następnej pozycji:

a(b|c)a      abeacab
^              ^

Nie ma też szczęścia. Przejść do następnej pozycji.

a(b|c)a      abeacab
^               ^

a meczów, więc spożywać ją i wprowadź przemienności:

a(b|c)a      abeacab
  ^              ^

b nie pasuje. Spróbuj drugiej alternatywy:

a(b|c)a      abeacab
    ^            ^

c pasuje, więc zużyj go i przejdź do następnego elementu w konkatenacji:

a(b|c)a      abeacab
      ^           ^

a meczów, a koniec z drzewa został osiągnięty. Zgłoś udany mecz:

a(b|c)a      abeacab
                \_/

DFA

Silnik DFA (Deterministic Finite Automaton) jest napędzany przez dane wejściowe .

Zasada

Algorytm skanuje przez ciągu wejściowego raz, i pamięta wszystkie możliwe ścieżki w regex, który mógłby się równać. Na przykład, gdy napotkamy naprzemienność we wzorcu, dwie nowe ścieżki są tworzone i próbowane niezależnie. Gdy dana ścieżka nie pasuje, jest usuwana z zestawu możliwości.

Implikacje

Czas dopasowania jest ograniczony przez rozmiar ciągu wejściowego. Nie ma cofania się, a silnik może znaleźć wiele dopasowań jednocześnie, nawet pokrywające się dopasowania.

Główną wadą tej metody jest ograniczony zestaw funkcji, który może być obsługiwany przez silnik w porównaniu z typem silnika NFA.

Przykład

Dopasuj a(b|c)a do 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