Libreria Python per analizzare la regex in AST?

Question

Per enfatizzare, non voglio "analizzare usando un'espressione regolare" - Voglio "analizzare un'espressione regolare in un albero simbolico". (La ricerca ha solo richiamato il primo ...)

Il mio caso d'uso: per velocizzare una ricerca regolare su un database, vorrei analizzare una espressione regolare come (foo|bar)baz+(bat)* ed estrarre tutte le sottostringhe che DEVONO apparire in un incontro. (In questo caso, è solo baz perché foo/bar sono alternanze e bat può apparire 0 volte.)

Per fare ciò, ho bisogno di una certa comprensione degli operatori regex/semantica. re.DEBUG è più vicina:

In [7]: re.compile('(foo|bar)baz+(bat)', re.DEBUG) 
subpattern 1 
    branch 
    literal 102 
    literal 111 
    literal 111 
    or 
    literal 98 
    literal 97 
    literal 114 
literal 98 
literal 97 
max_repeat 1 4294967295 
    literal 122 
subpattern 2 
    literal 98 
    literal 97 
    literal 116 

Tuttavia, è solo la stampa, e la c-implementazione non preserva la struttura in seguito, per quanto posso dire. Qualche idea su come posso analizzarla senza scrivere il parser del mio proprietario?

Answer 1

È possibile specificare solo un (classico) regex usando un contesto grammatica libera:

regex = { alternatives }; 
alternatives = primitive { '|' alternatives } ; 
primitive = '(' regex ')' | '[' character_set ']' | ... 

Questo significa che non è possibile analizzare una regex usando una regex (Perl è un'eccezione, ma poi le sue "espressioni regolari "sono estesi ben oltre il" classico ").

Quindi, per analizzare un'espressione regolare, è necessario creare il proprio parser e costruire un qualche tipo di albero (re.Debug viene abbastanza vicino) o quella libreria magica che si spera.

Sospetto che questa sia la parte facile. Questo non è terribilmente difficile da fare da soli; vedi Is there an alternative for flex/bison that is usable on 8-bit embedded systems? per uno schema semplice per la costruzione di tali parser.

per capire il semantica della regex (ad esempio, per capire "sottostringhe necessari"), si potrebbe essere in grado di cavarsela con la costruzione di un analizzatore le passeggiate sopra l'albero di analisi, e per ogni sottostruttura (in basso su), calcola la stringa comune. In caso contrario, potrebbe essere necessario implementare la classica costruzione NDFA e quindi passarci sopra, oppure implementare l'NDFA nella costruzione di DFA e passare sopra a DFA. Le regex reali tendono a contenere molte complicazioni disordinate come set di caratteri incorporati, gruppi di cattura, ecc.

La "stringa comune" potrebbe non essere solo una sequenza contigua di caratteri sebbene sia possibile definirla in modo limitato. Si potrebbe includere diverse sottostringhe costanti separati da intervalli di lunghezza fissa o variabile di caratteri, per esempio il sottostringhe necessario potrebbe sempre essere esso stesso esprimibili come "semplice regex" del modulo:

(<character>+ ?+) <character>+