Regular Expressions
Vanliga uttrycksmotortyper

NFA

En NFA-motor (Nondeterministic Finite Automaton) drivs av mönstret .

Princip

Regex-mönstret delas in i ett träd.

Den aktuella positionspekaren är inställd på början av inmatningssträngen, och en matchning försöks i denna position. Om matchning fais ökas positionen till nästa tecken i strängen och en annan matchning försöks från denna position. Denna process upprepas tills en matchning hittas eller slutet på inmatningssträngen nås.

För varje matchförsök

Algoritmen fungerar genom att utföra en genomgång av mönsterträdet för en given startposition. När det går igenom trädet uppdaterar det den aktuella inmatningspositionen genom att konsumera matchande tecken.

Om algoritmen möter en trädnod som inte matchar ingångssträngen vid den aktuella positionen, måste den backtracka . Detta utförs genom att gå tillbaka till överordnade noden i trädet, återställa den aktuella inmatningspositionen till det värde som den hade vid inmatning av överordnade noden och försöka nästa alternativa gren.

Om algoritmen lyckas lämna trädet rapporterar den en lyckad matchning. Annars, när alla möjligheter har testats, misslyckas matchen.

optimeringar

Regex-motorer tillämpar vanligtvis vissa optimeringar för bättre prestanda. Till exempel, om de bestämmer att en matchning måste börja med ett givet tecken, försöker de en matchning endast på de positioner i inmatningssträngen där det tecknet visas.

Exempel

Matcha a(b|c)a mot ingångssträngen abeacab :

Mönsterträdet kan se ut som:

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

Matchningen behandlas enligt följande:

a(b|c)a      abeacab
^            ^

a hittas i inmatningssträngen, konsumerar den och fortsätter till nästa objekt i mönstratreet: växlingen. Prova den första möjligheten: en exakt b .

a(b|c)a      abeacab
  ^           ^

b hittas, så att växlingen lyckas, konsumera den och gå vidare till nästa punkt i sammankopplingen: en exakt a :

a(b|c)a      abeacab
      ^        ^

a inte finns på den förväntade positionen. Backtrack till växlingen, återställ ingångsläget till det värde det hade när du startade växlingen för första gången och prova det andra alternativet:

a(b|c)a      abeacab
    ^         ^

c hittas inte i denna position. Backtrack till samkopplingen. Det finns inga andra möjligheter att prova just nu, så det finns ingen matchning i början av strängen.

Försök en andra match vid nästa inmatningsposition:

a(b|c)a      abeacab
^             ^

a stämmer inte det. Försök ytterligare en match på nästa position:

a(b|c)a      abeacab
^              ^

Ingen tur heller. Gå vidare till nästa position.

a(b|c)a      abeacab
^               ^

a tändstickor, så konsumera den och ange växlingen:

a(b|c)a      abeacab
  ^              ^

b stämmer inte. Försök det andra alternativet:

a(b|c)a      abeacab
    ^            ^

c matchningar, så konsumera det och gå vidare till nästa objekt i sammankopplingen:

a(b|c)a      abeacab
      ^           ^

a tändstickor, och trädets slut har nåtts. Rapportera en framgångsrik match:

a(b|c)a      abeacab
                \_/

DFA

En DFA-motor (Deterministic Finite Automaton) drivs av ingången .

Princip

Algoritmen skannar igenom inmatningssträngen en gång och kommer ihåg alla möjliga banor i regex som kan matcha. Till exempel, när en växling möts i mönstret, skapas två nya vägar och försöks oberoende. När en given väg inte matchar, släpps den från inställda möjligheter.

Implikationer

Matchningstiden begränsas av inmatningssträngstorleken. Det finns ingen backtracking, och motorn kan hitta flera matchningar samtidigt, även överlappande matchningar.

Den största nackdelen med denna metod är den reducerade funktionen som kan stöds av motorn jämfört med NFA-motortyp.

Exempel

Matcha a(b|c)a mot 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