Regular Expressions
Soorten reguliere expressie-motoren

NFA

Een NFA-motor (Nondeterministic Finite Automaton) wordt aangedreven door het patroon .

Beginsel

Het regex-patroon wordt in een boom geparseerd.

De huidige positie- aanwijzer is ingesteld op het begin van de invoertekenreeks en op deze positie wordt een overeenkomst geprobeerd. Als de match fais, wordt de positie opgehoogd naar het volgende karakter in de string en wordt een andere match geprobeerd vanaf deze positie. Dit proces wordt herhaald totdat een overeenkomst is gevonden of het einde van de invoerreeks is bereikt.

Voor elke matchpoging

Het algoritme werkt door een verplaatsing van de patroonboom uit te voeren voor een gegeven startpositie. Naarmate het door de boom vordert, wordt de huidige invoerpositie bijgewerkt door overeenkomende tekens te gebruiken.

Als het algoritme een boomknooppunt tegenkomt die niet overeenkomt met de invoerreeks op de huidige positie, moet het teruggaan . Dit wordt uitgevoerd door terug te gaan naar het bovenliggende knooppunt in de structuur, de huidige invoerpositie opnieuw in te stellen naar de waarde die het had bij het invoeren van het bovenliggende knooppunt en de volgende alternatieve tak te proberen.

Als het algoritme erin slaagt om de boom te verlaten, meldt het een succesvolle match. Anders mislukt de wedstrijd als alle mogelijkheden zijn geprobeerd.

optimalisaties

Regex-motoren passen meestal enkele optimalisaties toe voor betere prestaties. Als ze bijvoorbeeld bepalen dat een overeenkomst moet beginnen met een bepaald teken, zullen ze een overeenkomst alleen proberen op die posities in de invoertekenreeks waar dat teken verschijnt.

Voorbeeld

abeacab a(b|c)a tegen de invoertekenreeks abeacab :

De patroonboom kan er ongeveer zo uitzien:

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

De match wordt als volgt verwerkt:

a(b|c)a      abeacab
^            ^

a staat in de invoertekenreeks, verbruikt het en gaat door naar het volgende item in de patroonboom: de afwisseling. Probeer de eerste mogelijkheid: een exacte b .

a(b|c)a      abeacab
  ^           ^

b is gevonden, dus de afwisseling slaagt, verbruikt het en gaat door naar het volgende item in de aaneenschakeling: een exacte a :

a(b|c)a      abeacab
      ^        ^

a is niet gevonden op de verwachte positie. Ga terug naar de afwisseling, reset de invoerpositie naar de waarde die hij had bij het invoeren van de afwisseling en probeer het tweede alternatief:

a(b|c)a      abeacab
    ^         ^

c is niet gevonden op deze positie. Terug naar de aaneenschakeling. Er zijn geen andere mogelijkheden om dit te proberen, dus er is geen overeenkomst aan het begin van de string.

Probeer een tweede wedstrijd op de volgende invoerpositie:

a(b|c)a      abeacab
^             ^

a komt daar niet overeen. Probeer een andere wedstrijd op de volgende positie:

a(b|c)a      abeacab
^              ^

Ook geen geluk. Ga naar de volgende positie.

a(b|c)a      abeacab
^               ^

a overeenkomsten, dus consumeer het en voer de afwisseling in:

a(b|c)a      abeacab
  ^              ^

b komt niet overeen. Probeer het tweede alternatief:

a(b|c)a      abeacab
    ^            ^

c wedstrijden, dus consumeer het en ga door naar het volgende item in de aaneenschakeling:

a(b|c)a      abeacab
      ^           ^

a overeen, en het einde van de boom is bereikt. Meld een succesvolle wedstrijd:

a(b|c)a      abeacab
                \_/

DFA

Een DFA-motor (Deterministic Finite Automaton) wordt aangedreven door de invoer .

Beginsel

Het algoritme scant eenmaal door de invoertekenreeks en onthoudt alle mogelijke paden in de regex die kunnen overeenkomen. Wanneer er bijvoorbeeld een afwisseling in het patroon wordt aangetroffen, worden twee nieuwe paden gemaakt en onafhankelijk van elkaar geprobeerd. Wanneer een bepaald pad niet overeenkomt, wordt het verwijderd uit de ingestelde mogelijkheden.

Implicaties

De overeenkomende tijd wordt begrensd door de grootte van de invoertekenreeks. Er is geen backtracking en de motor kan meerdere overeenkomsten tegelijkertijd vinden, zelfs overlappende overeenkomsten.

Het belangrijkste nadeel van deze methode is de verminderde functieset die door de motor kan worden ondersteund in vergelijking met het NFA-motortype.

Voorbeeld

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