Mangiare ciliegie rosse ti dà la possibilità di mangiare fantasmi blu. L'idea che i derivati ​​possano essere usati per creare un algoritmo di corrispondenza di espressioni regolari è quasi altrettanto ridicola. Lascia che ti spieghi come funziona questo algoritmo e come si collega a Pac-Man.

Nel 1964 Brzozowski pubblicò il primo articolo sui derivati ​​delle espressioni regolari . Questo è di gran lunga uno dei miei algoritmi preferiti. Usando le derivate delle espressioni regolari, possiamo implementare un algoritmo per eseguire la corrispondenza delle espressioni regolari. Questo algoritmo è molto:

• semplice
• funzionale
• facilmente estendibile con i propri operatori

In questo articolo, ti mostrerò come possiamo abbinare una stringa con un'espressione regolare usando solo due funzioni pure e alcune analogie con Pac-Man. Se preferisci, puoi guardare il seguente video invece di leggere l'articolo in quanto copre lo stesso materiale:

Riepilogo delle espressioni regolari

Per prima cosa, facciamo una rapida revisione delle espressioni regolari per assicurarci di essere sulla stessa pagina. L'espressione a(a|b)*corrisponde a una stringa che inizia con un a, seguito da un numero qualsiasi di a' e b'.

• La stringa abcorrisponderà a(a|b)*. Lo indicheremo con un fantasma blu commestibile.
• Anche la stringa aabbbacorrisponde a(a|b)*poiché inizia con an aed è seguita da diversi a' e b'.
• Successivamente, la stringa acnon corrisponde a(a|b)*, poiché la regex non corrisponde a nessuna ce la nostra regex non esegue alcuna corrispondenza di sottostringa. Lo indicheremo usando un fantasma rosso che insegue Pac-Man.
• Infine, anche la stringa banon corrisponde a(a|b)*perché non inizia con un a.

Panoramica dell'algoritmo

Prima di entrare nei dettagli, diamo una panoramica di come funziona questo algoritmo. Ho ideato uno strano gioco di Pac-Man in cui puoi mangiare i fantasmi solo se mangi il frutto in una sequenza che corrisponde alla regex. Il nostro Pac-Man rappresenta la regex aba*. Ha la seguente stringa di frutta da mangiare: una mela, poi una banana e poi una mela: aba.

1. Quando iniziamo, il fantasma ci sta inseguendo e l'espressione regolare che ci resta da confrontare è aba*.
2. Mangiamo la prima mela e l'espressione regolare che ci resta da confrontare è ba*. Il fantasma ci sta ancora inseguendo poiché il frutto che abbiamo mangiato finora, la mela, non corrisponde alla regex.
3. Successivamente, mangiamo la banana. La regex che ci resta da abbinare è a*. Ora il fantasma inizia a scappare perché, tecnicamente, abcorrisponde già aba*.
4. Possiamo provare a mangiare il fantasma oa mangiare un'altra mela, nel qual caso l'espressione regolare che ci resta da abbinare è ancora a*. Il fantasma sta ancora scappando poiché abacorrisponde anche all'espressione regolare aba*.

C'è un'altra funzione al lavoro qui. La funzione controlla se il fantasma sta inseguendo il Pac-Man o se il Pac-Man ha già abbinato l'espressione regolare e sta inseguendo il fantasma. Questa funzione è chiamata funzione nullable; controlla se l'espressione regolare lasciata per la corrispondenza corrisponde alla stringa vuota. Può farlo perché se la regex lasciata corrispondere alla stringa vuota, il frutto che ha mangiato deve essere già stato sufficiente per soddisfare la regex.

Algoritmo di corrispondenza derivata

Ciò significa che abbiamo solo bisogno di due funzioni per scrivere l'algoritmo di corrispondenza derivata:

1. la funzione derivata
2. la funzione nullable

Uno in Golang per i programmatori imperativi:

e un altro in Haskell per programmatori funzionali:

Queste due funzioni sono equivalenti e scritte solo in diversi stili di programmazione. Nel codice Haskell, foldlchiamato anche piega a sinistra o ridotto in altre lingue, fa il lavoro del ciclo for per te. Inoltre, in Haskell, non abbiamo bisogno delle virgole per passare i parametri alle funzioni; poiché l'applicazione della funzione è l'operazione più comune in un linguaggio di programmazione funzionale, usiamo lo spazio per delimitare i parametri.

Ora, approfondiamo come implementare le funzioni nullable e derivate.

Digressione sulla storia delle origini di Pac-Man

Ma prima di farlo, non so se ti sei mai chiesto quale sia la storia delle origini di Pac-Man. Sostengo che non c'era un barile di scorie nucleari in cui è caduto Pac-Man, con il risultato che Pac-Man ha ottenuto il potere di mangiare i fantasmi. La logica è molto più semplice.

Pac-Man è un frutto! Quando Pac-Man mangia altra frutta, Pac-Man è un cannibale. Quindi, se mai vieni inseguito da un fantasma, devi mangiare della carne umana e il fantasma dovrebbe, almeno temporaneamente, iniziare a scappare da te. Ora, non l'ho provato da solo, ma la logica sembra valida.

Questo spiega perché gli zombi inseguono sempre gli umani. Come disse una volta David Attenborough:

“Gli zombi che ci inseguono, sono essi stessi inseguiti da fantasmi che non possiamo vedere. Dopo che gli zombi hanno mangiato parte della nostra carne umana, li vedrai esibire lo strano comportamento di masticare l'aria, questo è lo zombi che mangia il fantasma che lo inseguiva prima.

Operatori di base

L'implementazione delle funzioni nullable e derivate ci richiede innanzitutto di definire gli operatori di base disponibili nelle nostre espressioni regolari.

Possiamo pensare a un'espressione regolare come a descrivere un insieme di stringhe.

• Ciò significa che l'insieme vuoto rappresenta un operatore che non corrisponde a stringhe.
• La stringa vuota rappresenta un set singleton di una singola stringa che corrisponde solo alla stringa vuota.
• Il carattere rappresenta anche un set singleton che corrisponde solo al singolo carattere a.
• Possiamo quindi combinare queste espressioni regolari di base utilizzando operatori come: or, concatenatione Kleene star, dove re srappresenta le due espressioni di espressioni regolari che stiamo combinando.

Funzione annullabile

Possiamo iniziare con la funzione nullable. Diamo un'occhiata ad alcuni esempi e scopriamo quale di queste espressioni regolari corrisponde alla stringa vuota per ottenere informazioni su come viene implementata questa funzione.

• a*corrisponde alla stringa vuota poiché zero o più include zero.
• (a*|b)corrisponde alla stringa vuota poiché il lato sinistro di o corrisponde alla stringa vuota.
• abnon corrisponde alla stringa vuota, poiché corrisponde solo alla stringaab
• ab*inoltre non corrisponde alla stringa vuota, poiché ab*richiede una stringa che inizi con ana
• (a|b)non corrisponde alla stringa vuota, poiché né il lato sinistro né quello destro della orcorrisponde alla stringa vuota.

Ecco l'implementazione della funzione nullable. Il lato sinistro rappresenta i valori che vengono passati alla funzione e il lato destro rappresenta l'implementazione della funzione in quel caso. I fantasmi rossi rappresentano il falso e i fantasmi blu rappresentano il vero:

• Il set vuoto non corrisponde alla stringa vuota poiché non corrisponde a nessuna stringa.
• La stringa vuota corrisponde alla stringa vuota perché corrisponde solo alla stringa vuota.
• Il carattere anon corrisponde alla stringa vuota perché corrisponde solo al carattere a.
• Se abbiamo un logico or, dobbiamo controllare entrambi i lati. Se uno dei due corrisponde alla stringa vuota, allora il logico orcorrisponde alla stringa vuota.
• Affinché concatenationdue espressioni regolari corrispondano alla stringa vuota, entrambe devono corrispondere alla stringa vuota.
• E infine, se abbiamo zero or morequalcosa, questo include zero, il che significa che corrisponde sempre alla stringa vuota.

1. Il nostro operatore principale è orquesto significa che dobbiamo verificare la nullità dei lati sinistro e destro: be a*.
2. Controlliamo e vediamo che il carattere bsul lato sinistro non è annullabile: false.
3. Quindi controlliamo e vediamo che a*sul lato destro è nullable: true.
4. Ora siamo tornati falsee truepossiamo orfarli ottenere true.

Esercizi annullabili

Prova a esaminare l'implementazione e controlla se le seguenti espressioni regolari sono nullable. Puoi fare clic su di essi per verificare la tua risposta:

1. un
2. a*(b*|∅)
3. ea
4. ∅*
5. (∅|b)*(abc|ε)

Prima di esaminare l'implementazione della funzione, diamo un'occhiata agli esempi di una derivata. Qui prenderemo la derivata di alcune espressioni regolari, tutte rispetto al carattere a:

• L'espressione regolare che resta da confrontare dopo a*aver mangiato una amela è ancora a*.
• La derivata di ab*rispetto a aè b*, dato che abbiamo già abbinato il prefisso a.
• La derivata di (a|b)brispetto a aè b.
• La derivata di b|(a*b)rispetto a aè a*b. La sinistra bnon corrispondeva, quindi potevamo buttarla via e la 's sulla destra aveniva consumata .zero or more a
• Successivamente, abbiamo ab*, questo è leggermente complicato. Dopo che ha mangiato la mela, l'espressione regolare rimasta per la corrispondenza è b(ab)*. Dal momento che abbiamo trovato solo il a, ci aspettiamo di vederne almeno un altro b.

• La derivata dell'insieme vuoto è sempre l'insieme vuoto. Non c'è modo di recuperare poiché l'insieme vuoto non corrisponde a nulla.
• La derivata della stringa vuota relativa a qualsiasi carattere è l'insieme vuoto. Non si aspettava di corrispondere a un personaggio. Corrisponderà solo alla stringa vuota.
• La derivata di un singolo carattere a un carattere simile (in questo caso, il apple) è la stringa vuota poiché dopo che si è confrontata con se stessa, tutto ciò che resta da confrontare è la stringa vuota.
• La derivata di un carattere rispetto a un carattere diverso che non è uguale, in questo caso l' banana, è l'insieme vuoto poiché non abbiamo abbinato il carattere specifico.
• La derivata di orun'espressione è la ordelle derivate. Spinge semplicemente il problema ai suoi figli.
• La derivata concatdell'espressione deve considerare se può saltare la prima espressione. Può saltare la prima espressione solo se la prima espressione corrisponde alla stringa vuota ed è nullable. Quindi la prima cosa che facciamo è controllare questo. Pensiamo al caso in cui non può ignorare la prima espressione quando l'espressione rnon ammette valori Null. Quindi la derivata è la derivata della prima espressione concatenatedcon la seconda espressione s. Se possiamo saltare la prima espressione regolare, dobbiamo considerare un'alternativa che è solo la derivata della seconda espressione. Possiamo quindi orle due alternative di saltare re non saltare re restituirle come risultato.
• Infine, abbiamo l' staroperatore. Corrisponde a un'espressione zero o più volte. Poiché ci viene passato un carattere, questo non è il caso zero. Quindi dobbiamo considerare il one or morecaso. Ciò significa che dobbiamo prendere la derivata dell'espressione all'interno di stare concatenatedi nuovo con l' zero or moreespressione.

Esempio derivato 1

Prendiamo la derivata di (ab)*rispetto a a.

(ab)*è zero or moreun'espressione, quindi guardiamo alla zero or moreregola. Vediamo che questo richiede di prendere la derivata dell'espressione all'interno del file star.

Questo è il concatenationdi ae b. Quindi controlliamo se il lato sinistro è nullable e il carattere anon è nullable. Ciò significa che non possiamo saltarlo. Dobbiamo prendere la derivata di arispetto a a. Ma quella è la stringa vuota, quindi se usiamo concatenatela stringa vuota con il lato destro, che era b, otteniamo b.

Ora, torniamo indietro a zero or more, ricordiamo che abbiamo preso la derivata di abrispetto a ae ottenuto di nuovo a b. Ora possiamo concatenarlo con di (ab)*nuovo e otteniamo b(ab)*.

Esempio derivato 2

Prendiamo la derivata di (a*ba)rispetto a b.

• a*è concatenato con baquindi diamo un'occhiata alla regola di concatenazione.
• Controlliamo se il lato sinistro a*è nullable, il che è. Ciò significa che possiamo saltarlo, il che significa anche che dobbiamo creare uno ordei due derivati.
• Il lato sinistro finisce per non corrispondere, poiché a*non corrisponde b.
• Fortunatamente abbiamo un'alternativa ba. La derivata di barispetto a bè e a.

Ho saltato alcuni dettagli qui. Consideralo un esercizio per controllare il mio lavoro esaminando tu stesso la funzione.

Esercizi derivativi

Prova a esaminare l'implementazione e controlla quali sono le derivate delle seguenti espressioni regolari rispetto a b. Puoi fare clic su di essi per verificare la tua risposta:

1. εb
2. b*(b|c)
3. a*(b|c)
4. bεb
5. ∅*b

Spero che tu ora capisca perché mangiare ciliegie rosse ti dà la possibilità di mangiare fantasmi blu e come implementare un matcher di espressioni regolari usando l'algoritmo derivato.

Abbiamo coperto l'algoritmo di lavoro di base qui, ma ci sono molti modi per rendere questo algoritmo ancora migliore con modifiche molto piccole. In questo post abbiamo imbrogliato e sorvolato sulle regole di semplificazione, usandole senza spiegarle, cosa che diventerà particolarmente ovvia se seguirai gli esercizi. Inoltre, non abbiamo discusso di come utilizzare la memoizzazione per costruire pigramente un automa efficiente.

Possiamo anche facilmente estendere l'algoritmo per includere nuovi operatori come, note interleavepersino supportare grammatiche senza contesto. Tratterò alcuni di questi argomenti nel prossimo articolo .

Nel frattempo, mi piacerebbe vedere la tua implementazione di questo algoritmo in un linguaggio di programmazione con cui ti senti più a tuo agio. Vi prego di inviarmi un link nei commenti.

Grazie

• Brink van der Merwe per aver dedicato del tempo a spiegarmi questo algoritmo.

• Brzozowski, Janusz A. "Derivati ​​di espressioni regolari". Giornale dell'ACM (JACM) 11.4 (1964): 481–494.
• Owens, Scott, John Reppy e Aaron Turon. "Derivati ​​​​di espressioni regolari riesaminati". Giornale di programmazione funzionale 19.2 (2009): 173–190.