Regular Expressions
Typen für reguläre Ausdrücke

NFA

Ein NFA-Motor (Nondeterministic Finite Automaton) wird vom Muster gesteuert .

Prinzip

Das Regex-Muster wird in einen Baum geparst.

Der aktuelle Positionszeiger wird auf den Anfang der Eingabezeichenfolge gesetzt, und es wird an dieser Position eine Übereinstimmung versucht. Wenn die Übereinstimmung fais ist, wird die Position auf das nächste Zeichen in der Zeichenfolge erhöht und von dieser Position aus wird eine weitere Übereinstimmung versucht. Dieser Vorgang wird wiederholt, bis eine Übereinstimmung gefunden wird oder das Ende der Eingabezeichenfolge erreicht ist.

Für jeden Spielversuch

Der Algorithmus arbeitet durch Durchlaufen des Musterbaums für eine gegebene Startposition. Beim Durchlaufen des Baums wird die aktuelle Eingabeposition aktualisiert, indem übereinstimmende Zeichen verwendet werden.

Wenn der Algorithmus auf einen Baumknoten trifft, der an der aktuellen Position nicht mit der Eingabezeichenfolge übereinstimmt, muss er zurückverfolgt werden . Dies geschieht, indem Sie zum übergeordneten Knoten in der Baumstruktur zurückkehren, die aktuelle Eingabeposition auf den Wert zurücksetzen, den sie bei der Eingabe des übergeordneten Knotens hatte, und den nächsten alternativen Zweig versuchen.

Wenn es dem Algorithmus gelingt, den Baum zu verlassen, meldet er eine erfolgreiche Übereinstimmung. Andernfalls schlägt das Match fehl, wenn alle Möglichkeiten ausprobiert wurden.

Optimierungen

Regex-Engines wenden normalerweise einige Optimierungen an, um die Leistung zu verbessern. Wenn sie zum Beispiel feststellen, dass eine Übereinstimmung mit einem bestimmten Zeichen beginnen muss, versuchen sie eine Übereinstimmung nur an den Positionen in der Eingabezeichenfolge, an denen das Zeichen erscheint.

Beispiel

abeacab a(b|c)a an den Eingabestring abeacab :

Der Musterbaum könnte ungefähr so ​​aussehen:

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

Der Spielvorgang läuft wie folgt ab:

a(b|c)a      abeacab
^            ^

a wird in der Eingabezeichenfolge gefunden, verbraucht sie und fährt mit dem nächsten Element im Musterbaum fort: der Änderung. Versuchen Sie die erste Möglichkeit: eine genaue b .

a(b|c)a      abeacab
  ^           ^

b gefunden wird, damit der Wechsel erfolgreich ist, verbrauchen Sie ihn und fahren Sie mit dem nächsten Element in der Verkettung fort: ein genaues a :

a(b|c)a      abeacab
      ^        ^

a wird nicht an der erwarteten Position gefunden. Kehren Sie zur Änderung zurück, setzen Sie die Eingabeposition auf den Wert zurück, den sie bei der ersten Eingabe der Änderung hatte, und versuchen Sie die zweite Alternative:

a(b|c)a      abeacab
    ^         ^

c wird an dieser Position nicht gefunden. Zurück zur Verkettung. An diesem Punkt gibt es keine weiteren Möglichkeiten, es gibt also keine Übereinstimmung am Anfang der Zeichenfolge.

Versuchen Sie ein zweites Spiel an der nächsten Eingabeposition:

a(b|c)a      abeacab
^             ^

a passt da nicht zusammen. Versuchen Sie ein anderes Spiel an der nächsten Position:

a(b|c)a      abeacab
^              ^

Auch kein Glück. Weiter zur nächsten Position.

a(b|c)a      abeacab
^               ^

a Streichholz, also verbrauchen Sie es und geben Sie die Alternative ein:

a(b|c)a      abeacab
  ^              ^

b passt nicht zusammen. Versuchen Sie die zweite Alternative:

a(b|c)a      abeacab
    ^            ^

c passt, also verbrauchen Sie es und fahren Sie mit dem nächsten Element in der Verkettung fort:

a(b|c)a      abeacab
      ^           ^

a stimmt überein und das Ende des Baums wurde erreicht. Bericht über ein erfolgreiches Spiel:

a(b|c)a      abeacab
                \_/

DFA

Eine DFA-Engine (Deterministic Finite Automaton) wird von der Eingabe gesteuert .

Prinzip

Der Algorithmus durchsucht die Eingabezeichenfolge einmal und speichert alle möglichen Pfade in der Regex, die übereinstimmen könnten. Wenn zum Beispiel im Muster eine Änderung auftritt, werden zwei neue Pfade erstellt und unabhängig voneinander versucht. Wenn ein bestimmter Pfad nicht übereinstimmt, wird er aus den festgelegten Möglichkeiten entfernt.

Implikationen

Die Übereinstimmungszeit ist durch die Größe des Eingabestrings begrenzt. Es gibt kein Backtracking, und die Engine kann mehrere Übereinstimmungen gleichzeitig finden, sogar überlappende Übereinstimmungen.

Der Hauptnachteil dieser Methode ist der reduzierte Funktionsumfang, der von der Engine im Vergleich zum NFA-Engine-Typ unterstützt werden kann.

Beispiel

Match a(b|c)a gegen 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