Scrittura di un parser per le espressioni regolari

Question

Anche dopo anni di programmazione, mi vergogno di dire che non ho mai veramente compreso le espressioni regolari. In generale, quando un problema richiede una regex, di solito riesco (dopo un po 'di riferimenti alla sintassi) a trovare uno appropriato, ma è una tecnica che mi ritrovo ad usare sempre più spesso.

Quindi, per insegnare a me stesso e comprendere le espressioni regolari correttamente, ho deciso di fare ciò che faccio sempre quando cerco di imparare qualcosa; Ad esempio, prova a scrivere qualcosa di ambizioso che probabilmente abbandonerò non appena avrò appreso che ho imparato abbastanza.

A tal fine, voglio scrivere un parser di espressioni regolari in Python. In questo caso, "learn enough" significa che voglio implementare un parser in grado di comprendere completamente la sintassi regex estesa di Perl. Tuttavia, non deve essere il parser più efficiente o anche necessariamente utilizzabile nel mondo reale. Semplicemente deve corrispondere o non riuscire a far corrispondere un modello in una stringa.

La domanda è: da dove iniziare? Non so quasi nulla su come le espressioni regex siano analizzate e interpretate a prescindere dal fatto che coinvolge in qualche modo un automa a stati finiti. Qualche suggerimento su come affrontare questo problema piuttosto scoraggiante sarebbe molto apprezzato.

EDIT:. vorrei chiarire che, mentre ho intenzione di implementare il parser regex in Python, io non sono eccessivamente coccolato su ciò che il linguaggio di programmazione gli esempi o articoli sono scritti in Finché non è in Brainfuck, probabilmente ne capirò abbastanza per renderlo degno di nota.

Answer 1

Scrivere un'implementazione di un motore di espressioni regolari è davvero un compito piuttosto complesso.

Ma se siete interessati a come farlo, anche se non si può capire abbastanza dei dettagli realmente realizzarlo, mi sento di raccomandare che almeno un'occhiata a questo articolo:

Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)

Spiega quanti dei linguaggi di programmazione popolari implementano le espressioni regolari in un modo che può essere molto lento per alcune espressioni regolari e spiega un metodo leggermente diverso che è più veloce. L'articolo include alcuni dettagli su come funziona l'implementazione proposta, incluso un certo codice sorgente in C. Potrebbe essere una lettura un po 'pesante se stai appena iniziando ad apprendere le espressioni regolari, ma penso che valga la pena conoscere la differenza tra i due approcci.

Answer 2

C'è un capitolo interessante (anche se breve) in Beautiful Code di Brian Kernighan, opportunamente chiamato "A Regular Expression Matcher". In essa discute un semplice matcher che può corrispondere a caratteri letterali e ai simboli .^$*.

Answer 3

This paper richiede un approccio interessante. L'implementazione è data in Haskell, ma è stata reimplemented in Python almeno una volta.

Answer 4

Ho già assegnato un +1 a Mark Byers, ma per quanto mi ricordo il documento non dice molto su come l'abbinamento di espressioni regolari funzioni oltre a spiegare perché un algoritmo è cattivo e un altro molto meglio. Forse qualcosa nei link?

Mi concentrerò sull'ottimale approccio: la creazione di automi finiti. Se ti limiti ad automi deterministici senza minimizzazione, questo non è davvero troppo difficile.

Quello che descriverò (molto rapidamente) è l'approccio adottato in Modern Compiler Design.

Immaginate di avere la seguente espressione regolare ...

a (b c)* d 

Le lettere rappresentano caratteri letterali da abbinare. La * è la solita corrispondenza a zero o più ripetizioni. L'idea di base è derivare gli stati in base a regole tratteggiate. Stato zero ci prenderemo come lo stato in cui nulla è stato ancora abbinato, quindi il punto va al fronte ...

0 : .a (b c)* d 

L'unica partita possibile è 'a', in modo che il prossimo stato deriviamo è. ..

1 : a.(b c)* d 

ora abbiamo due possibilità - corrispondere al 'b' (se c'è almeno una ripetizione di 'b c') o abbinare la 'd' altro. Nota: stiamo fondamentalmente facendo una ricerca con il digramma qui (prima o dopo la profondità prima o qualsiasi altra cosa) ma stiamo scoprendo il digrafo mentre lo cerchiamo. Supponendo una strategia di ampiezza, avremo bisogno di accodare uno dei nostri casi per una considerazione successiva, ma ignorerò il problema da qui in poi. In ogni caso, abbiamo scoperto due nuovi stati ...

2 : a (b.c)* d 
3 : a (b c)* d. 

Stato 3 è uno stato finale (ci possono essere più di uno). Per lo stato 2, possiamo solo abbinare la "c", ma dobbiamo fare attenzione con la posizione del punto in seguito. Otteniamo "a. (B c) * d" - che è lo stesso di stato 1, quindi non abbiamo bisogno di un nuovo stato.

IIRC, l'approccio in Modern Compiler Design è quello di tradurre una regola quando si colpisce un operatore, al fine di semplificare la gestione del punto. Stato 1 sarebbe stato trasformato da ...

1 : a.b c (b c)* d 
    a.d 

Cioè, la vostra prossima opzione è sia per abbinare la prima ripetizione o per saltare la ripetizione. Gli stati successivi di questo sono equivalenti agli stati 2 e 3. Un vantaggio di questo approccio è che puoi scartare tutte le tue partite passate (tutto prima del ".") Come ti interessa solo le partite future. Questo in genere dà un modello di stato più piccolo (ma non necessariamente uno minimo).

EDIT Se si scartano i dettagli già abbinati, la descrizione dello stato è una rappresentazione dell'insieme di stringhe che possono verificarsi da questo momento in poi.

In termini di algebra astratta, questo è un tipo di chiusura del set. Un'algebra è fondamentalmente un insieme con uno (o più) operatori. Il nostro set è di descrizioni di stato e i nostri operatori sono le nostre transizioni (corrispondenze di personaggi). Un insieme chiuso è uno in cui l'applicazione di qualsiasi operatore a qualsiasi membro nell'insieme produce sempre un altro membro che si trova nell'insieme. La chiusura di un set è il set più grande e mimato che è chiuso. Quindi, fondamentalmente, iniziando con lo stato di partenza ovvio, stiamo costruendo il set minimo di stati che è chiuso rispetto al nostro set di operatori di transizione - il set minimo di stati raggiungibili.

Minimo qui si riferisce al processo di chiusura - potrebbe esserci un automa equivalente più piccolo che viene normalmente definito come minimo.

Con questa idea di base in mente, non è troppo difficile dire "se ho due macchine di stato che rappresentano due serie di stringhe, come posso ricavarne una terza che rappresenta l'unione" (o intersezione, o imposta differenza ...). Invece di regole tratteggiate, le rappresentazioni di stato saranno uno stato corrente (o un insieme di stati correnti) da ciascun automa di input e forse ulteriori dettagli.

Se le tue grammatiche regolari diventano complesse, puoi ridurle al minimo. L'idea di base qui è relativamente semplice. Raggruppate tutti i vostri stati in una classe di equivalenza o "blocco". Quindi verifichi ripetutamente se hai bisogno di dividere i blocchi (gli stati non sono realmente equivalenti) rispetto a un particolare tipo di transizione. Se tutti gli stati di un determinato blocco accettano una corrispondenza dello stesso carattere e, nel farlo, raggiungono lo stesso blocco successivo, sono equivalenti.

L'algoritmo di Hopcrofts è un modo efficace per gestire questa idea di base.

Una cosa particolarmente interessante della minimizzazione è che ogni automa finito deterministico ha precisamente una forma minima. Inoltre, l'algoritmo di Hopcrofts produrrà la stessa rappresentazione di quella forma minimale, indipendentemente dalla rappresentazione di quale caso più ampio ha iniziato. Cioè, questa è una rappresentazione "canonica" che può essere usata per derivare un hash o per ordinamenti arbitrari ma coerenti. Ciò significa che puoi usare gli automi minimi come chiavi nei contenitori.

Quanto sopra è probabilmente una definizione di WRT un po 'sciatta, quindi assicuratevi di cercare da soli i termini prima di usarli voi stessi, ma con un po' di fortuna questo fornisce una rapida introduzione alle idee di base.

BTW - dai uno sguardo al resto di Dick Grunes site - ha un libro in formato PDF gratuito sulle tecniche di analisi. La prima edizione di Modern Compiler Design è abbastanza buona, ma come vedrete, c'è una seconda edizione imminente.

Answer 5

Sono d'accordo sul fatto che scrivere un motore regex migliorerà la comprensione ma hai dato un'occhiata a ANTLR ??. Genera automaticamente i parser per qualsiasi tipo di lingua. Quindi forse puoi provare la tua mano prendendo una delle grammatiche linguistiche elencate allo Grammar examples ed esegui l'AST e il parser che genera. Genera un codice veramente complicato ma avrai una buona comprensione di come funziona un parser.