Regular Expressions
Tipi di motore di espressioni regolari

NFA

Un motore NFA (Nondeterministic Finite Automaton) è guidato dal modello .

Principio

Il modello regex viene analizzato in un albero.

Il puntatore di posizione corrente viene impostato all'inizio della stringa di input e viene tentata una corrispondenza in questa posizione. Se la partita fais, la posizione viene incrementata al carattere successivo nella stringa e viene tentata un'altra corrispondenza da questa posizione. Questo processo viene ripetuto finché non viene trovata una corrispondenza o viene raggiunta la fine della stringa di input.

Per ogni tentativo di partita

L'algoritmo funziona eseguendo un attraversamento dell'albero del modello per una data posizione di partenza. Man mano che procede attraverso l'albero, aggiorna la posizione di input corrente consumando i caratteri corrispondenti.

Se l'algoritmo incontra un nodo dell'albero che non corrisponde alla stringa di input nella posizione corrente, dovrà tornare indietro . Questo viene eseguito tornando al nodo genitore nell'albero, reimpostando la posizione di input corrente sul valore che aveva al momento dell'ingresso nel nodo genitore e provando il successivo ramo alternativo.

Se l'algoritmo riesce a uscire dall'albero, riporta una corrispondenza corretta. Altrimenti, quando tutte le possibilità sono state provate, la partita fallisce.

ottimizzazioni

I motori Regex di solito applicano alcune ottimizzazioni per prestazioni migliori. Ad esempio, se stabiliscono che una partita deve iniziare con un dato personaggio, tenteranno una corrispondenza solo in corrispondenza di quelle posizioni nella stringa di input in cui appare quel personaggio.

Esempio

Abbina a(b|c)a contro la stringa di input abeacab :

L'albero del modello potrebbe essere simile a qualcosa:

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

La partita si svolge come segue:

a(b|c)a      abeacab
^            ^

a si trova nella stringa di input, la consuma e passa all'elemento successivo nell'albero del modello: l'alternanza. Prova la prima possibilità: un'esatta b .

a(b|c)a      abeacab
  ^           ^

b viene trovato, quindi l'alternanza ha successo, lo consuma e passa all'elemento successivo nella concatenazione: un esatto a :

a(b|c)a      abeacab
      ^        ^

a non si trova nella posizione prevista. Tornando indietro all'alternanza, reimposta la posizione di input sul valore che aveva quando si immette l'alternanza per la prima volta e prova la seconda alternativa:

a(b|c)a      abeacab
    ^         ^

c non si trova in questa posizione. Backtrack alla concatenazione. Non ci sono altre possibilità da provare a questo punto, quindi non c'è corrispondenza all'inizio della stringa.

Tenta una seconda corrispondenza alla successiva posizione di input:

a(b|c)a      abeacab
^             ^

a non corrisponde a lì. Prova un'altra corrispondenza nella prossima posizione:

a(b|c)a      abeacab
^              ^

Nessuna fortuna neanche. Avanzare alla prossima posizione.

a(b|c)a      abeacab
^               ^

a partita, quindi consumala e inserisci l'alternanza:

a(b|c)a      abeacab
  ^              ^

b non corrisponde. Tentare la seconda alternativa:

a(b|c)a      abeacab
    ^            ^

c corrisponde, quindi consumalo e passa all'elemento successivo nella concatenazione:

a(b|c)a      abeacab
      ^           ^

a partita e la fine dell'albero è stata raggiunta. Segnala una corrispondenza riuscita:

a(b|c)a      abeacab
                \_/

DFA

Un motore DFA (Deterministic Finite Automaton) è guidato dall'input .

Principio

L'algoritmo esegue la scansione della stringa di input una sola volta e ricorda tutti i possibili percorsi nella regex che potrebbero corrispondere. Ad esempio, quando si verifica un'alternanza nel motivo, vengono creati e tentati in modo indipendente due nuovi percorsi. Quando un determinato percorso non corrisponde, viene eliminato dal set di possibilità.

implicazioni

Il tempo di abbinamento è limitato dalla dimensione della stringa di input. Non c'è il backtracking e il motore può trovare più corrispondenze contemporaneamente, anche se si sovrappongono partite.

Lo svantaggio principale di questo metodo è il set di funzionalità ridotto che può essere supportato dal motore, rispetto al tipo di motore NFA.

Esempio

Abbina a(b|c)a contro 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