Il potere riconoscimento di "moderno" regex

Question

Che classe dei linguaggi fanno reali espressioni regolari moderni in realtà riconoscono?

Ogniqualvolta vi è un gruppo che cattura la lunghezza illimitata con un riferimento all'indietro (ad esempio (.*)_\1), un'espressione regolare corrisponde ora a una lingua non regolare. Ma questo, di per sé, non è sufficiente per corrispondere a qualcosa come S ::= '(' S ')' | ε - il linguaggio privo di contesto di coppie di parenti corrispondenti. (esistono, che sono nuove per me, ma mi è stato assicurato in Perl e PCRE)

regex ricorsive sembrano riconoscere almeno la maggior parte delle lampadine fluorescenti compatte.

Qualcuno ha fatto o leggere qualsiasi ricerca in questo settore? Quali sono i limiti di queste regex "moderne"? Riconoscono strettamente più o meno meno dei CFG, delle grammatiche LL o LR? O esistono entrambi i linguaggi che possono essere riconosciuti da un'espressione regolare ma non un CFG e l'opposto?

collegamenti a documenti rilevanti sarebbe molto apprezzato.

Answer 1

modello ricorsione

Con i modelli ricorsive, si dispone di una forma di discesa ricorsiva corrispondenza.

Questo va bene per una varietà di problemi, ma una volta che si vuole fare davvero discesa ricorsiva parsing, è necessario inserire i gruppi di cattura qua e là, ed è scomodo per recuperare la struttura completa di analisi in questo modo. Il modulo Regexp::Grammars di Damian Conway per Perl trasforma il modello semplice in uno equivalente che fa automaticamente tutto ciò che viene chiamato catturare in una struttura dati ricorsiva, rendendo molto più facile il recupero della struttura analizzata. Ho un campione che confronta questi due approcci alla fine di questo post.

Restrizioni ricorsione

la domanda era che tipo di grammatiche che i modelli ricorsivi possono eguagliare. Bene, sono certamente gli abbinamenti di tipo recursive descent. L'unica cosa che viene in mente è che i pattern ricorsivi non possono gestire left recursion. Questo pone un vincolo sul tipo di grammatiche a cui è possibile applicarle. A volte puoi riordinare le tue produzioni per eliminare la ricorsione a sinistra.

BTW, PCRE e Perl differiscono leggermente da quanto si è permesso di frase la ricorsione. Vedere le sezioni sui “modelli RICORSIVI” e “differenza ricorsione da Perl” nel pcrepattern pagina di manuale. Ad esempio: Perl può gestire ^(.|(.)(?1)\2)$ dove PCRE richiede invece ^((.)(?1)\2|.)$.

ricorsione Grandi

La necessità di modelli ricorsivi pone sorprendentemente frequentemente. Un esempio ben visto è quando devi abbinare qualcosa che può annidare, come parentesi, virgolette o anche tag HTML/XML bilanciati. Ecco la partita per parental balenata:

\((?:[^()]*+|(?0))*\) 

Trovo più difficile da leggere a causa della sua natura compatta.Questo è facilmente curabile con modalità /x per rendere gli spazi più significativi:

\((?: [^()] *+ | (?0))* \) 

Poi di nuovo, dal momento che stiamo usando parentesi per la nostra ricorsione, un esempio più chiaro sarebbe corrispondenza apici annidati:

‘ (?: [^‘’] *+ | (?0))* ’ 

Un'altra cosa ricorsivamente definita che potresti voler abbinare sarebbe un palindromo. Questo semplice modello funziona in Perl:

^((.)(?1)\2|.?)$ 

che è possibile testare sulla maggior parte dei sistemi che utilizzano qualcosa come questo:

$ perl -nle 'print if /^((.)(?1)\2|.?)$/i' /usr/share/dict/words 

nota che l'attuazione di PCRE della ricorsione richiede più elaborata

^(?:((.)(?1)\2|)|((.)(?3)\4|.)) 

Questo a causa delle restrizioni su come funziona la ricorsione PCRE.

corretto parsing

Per me, gli esempi di cui sopra sono per lo più le partite di giocattoli, non tutti che interessante, davvero. Quando diventa interessante è quando hai una grammatica reale che stai cercando di analizzare. Ad esempio, RFC 5322 definisce un indirizzo di posta piuttosto elaborato. Ecco un modello “grammaticale” per abbinarlo:

$rfc5322 = qr{ 

    (?(DEFINE) 

    (?<address>   (?&mailbox) | (?&group)) 
    (?<mailbox>   (?&name_addr) | (?&addr_spec)) 
    (?<name_addr>  (?&display_name)? (?&angle_addr)) 
    (?<angle_addr>  (?&CFWS)? < (?&addr_spec) > (?&CFWS)?) 
    (?<group>   (?&display_name) : (?:(?&mailbox_list) | (?&CFWS))? ; (?&CFWS)?) 
    (?<display_name> (?&phrase)) 
    (?<mailbox_list> (?&mailbox) (?: , (?&mailbox))*) 

    (?<addr_spec>  (?&local_part) \@ (?&domain)) 
    (?<local_part>  (?&dot_atom) | (?&quoted_string)) 
    (?<domain>   (?&dot_atom) | (?&domain_literal)) 
    (?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dcontent))* (?&FWS)? 
            \] (?&CFWS)?) 
    (?<dcontent>  (?&dtext) | (?&quoted_pair)) 
    (?<dtext>   (?&NO_WS_CTL) | [\x21-\x5a\x5e-\x7e]) 

    (?<atext>   (?&ALPHA) | (?&DIGIT) | [!#\$%&'*+-/=?^_`{|}~]) 
    (?<atom>   (?&CFWS)? (?&atext)+ (?&CFWS)?) 
    (?<dot_atom>  (?&CFWS)? (?&dot_atom_text) (?&CFWS)?) 
    (?<dot_atom_text> (?&atext)+ (?: \. (?&atext)+)*) 

    (?<text>   [\x01-\x09\x0b\x0c\x0e-\x7f]) 
    (?<quoted_pair>  \\ (?&text)) 

    (?<qtext>   (?&NO_WS_CTL) | [\x21\x23-\x5b\x5d-\x7e]) 
    (?<qcontent>  (?&qtext) | (?&quoted_pair)) 
    (?<quoted_string> (?&CFWS)? (?&DQUOTE) (?:(?&FWS)? (?&qcontent))* 
          (?&FWS)? (?&DQUOTE) (?&CFWS)?) 

    (?<word>   (?&atom) | (?&quoted_string)) 
    (?<phrase>   (?&word)+) 

    # Folding white space 
    (?<FWS>    (?: (?&WSP)* (?&CRLF))? (?&WSP)+) 
    (?<ctext>   (?&NO_WS_CTL) | [\x21-\x27\x2a-\x5b\x5d-\x7e]) 
    (?<ccontent>  (?&ctext) | (?&quoted_pair) | (?&comment)) 
    (?<comment>   \((?: (?&FWS)? (?&ccontent))* (?&FWS)? \)) 
    (?<CFWS>   (?: (?&FWS)? (?&comment))* 
         (?: (?:(?&FWS)? (?&comment)) | (?&FWS))) 

    # No whitespace control 
    (?<NO_WS_CTL>  [\x01-\x08\x0b\x0c\x0e-\x1f\x7f]) 

    (?<ALPHA>   [A-Za-z]) 
    (?<DIGIT>   [0-9]) 
    (?<CRLF>   \x0d \x0a) 
    (?<DQUOTE>   ") 
    (?<WSP>    [\x20\x09]) 
    ) 

    (?&address) 

}x; 

Come si vede, è molto BNF-like. Il problema è che è solo una partita, non una cattura. E tu davvero non vuoi semplicemente circondare il tutto con l'acquisizione di parenti perché questo non ti dice quale produzione corrisponde a quale parte. Usando il modulo Regexp :: Grammars precedentemente menzionato, possiamo.

#!/usr/bin/env perl 

use strict; 
use warnings; 
use 5.010; 
use Data::Dumper "Dumper"; 

my $rfc5322 = do { 
    use Regexp::Grammars; # ...the magic is lexically scoped 
    qr{ 

    # Keep the big stick handy, just in case... 
    # <debug:on> 

    # Match this... 
    <address> 

    # As defined by these... 
    <token: address>   <mailbox> | <group> 
    <token: mailbox>   <name_addr> | <addr_spec> 
    <token: name_addr>  <display_name>? <angle_addr> 
    <token: angle_addr>  <CFWS>? \< <addr_spec> \> <CFWS>? 
    <token: group>   <display_name> : (?:<mailbox_list> | <CFWS>)? ; <CFWS>? 
    <token: display_name> <phrase> 
    <token: mailbox_list> <[mailbox]> ** (,) 

    <token: addr_spec>  <local_part> \@ <domain> 
    <token: local_part>  <dot_atom> | <quoted_string> 
    <token: domain>   <dot_atom> | <domain_literal> 
    <token: domain_literal> <CFWS>? \[ (?: <FWS>? <[dcontent]>)* <FWS>? 

    <token: dcontent>  <dtext> | <quoted_pair> 
    <token: dtext>   <.NO_WS_CTL> | [\x21-\x5a\x5e-\x7e] 

    <token: atext>   <.ALPHA> | <.DIGIT> | [!#\$%&'*+-/=?^_`{|}~] 
    <token: atom>   <.CFWS>? <.atext>+ <.CFWS>? 
    <token: dot_atom>  <.CFWS>? <.dot_atom_text> <.CFWS>? 
    <token: dot_atom_text> <.atext>+ (?: \. <.atext>+)* 

    <token: text>   [\x01-\x09\x0b\x0c\x0e-\x7f] 
    <token: quoted_pair>  \\ <.text> 

    <token: qtext>   <.NO_WS_CTL> | [\x21\x23-\x5b\x5d-\x7e] 
    <token: qcontent>  <.qtext> | <.quoted_pair> 
    <token: quoted_string> <.CFWS>? <.DQUOTE> (?:<.FWS>? <.qcontent>)* 
          <.FWS>? <.DQUOTE> <.CFWS>? 

    <token: word>   <.atom> | <.quoted_string> 
    <token: phrase>   <.word>+ 

    # Folding white space 
    <token: FWS>    (?: <.WSP>* <.CRLF>)? <.WSP>+ 
    <token: ctext>   <.NO_WS_CTL> | [\x21-\x27\x2a-\x5b\x5d-\x7e] 
    <token: ccontent>  <.ctext> | <.quoted_pair> | <.comment> 
    <token: comment>   \((?: <.FWS>? <.ccontent>)* <.FWS>? \) 
    <token: CFWS>   (?: <.FWS>? <.comment>)* 
          (?: (?:<.FWS>? <.comment>) | <.FWS>) 

    # No whitespace control 
    <token: NO_WS_CTL>  [\x01-\x08\x0b\x0c\x0e-\x1f\x7f] 
    <token: ALPHA>   [A-Za-z] 
    <token: DIGIT>   [0-9] 
    <token: CRLF>   \x0d \x0a 
    <token: DQUOTE>   " 
    <token: WSP>    [\x20\x09] 
    }x; 
}; 

while (my $input = <>) { 
    if ($input =~ $rfc5322) { 
     say Dumper \%/;  # ...the parse tree of any successful match 
           # appears in this punctuation variable 
    } 
} 

Come si vede, utilizzando una notazione molto leggermente diversa nel modello, è ora ottenere qualcosa che memorizza l'intero albero sintattico via per voi nella variabile %/, con tutto ordinatamente etichettati. Il risultato della trasformazione è ancora un modello, come puoi vedere dall'operatore =~. È solo un po 'magico.