Riconoscere il potere di “moderno” espressioni regolari

Question

Che classe di lingue moderne espressioni regolari in realtà riconoscere?

Ogni volta che c'è una sovrabbondanza di lunghezza acquisizione di gruppo con un colpo di riferimento (ad es. (.*)_\1) una regex è ora di corrispondenza non regolari lingua.Ma questo, di per sé, non è sufficiente per abbinare qualcosa di simile S ::= '(' S ')' | ε — il contesto di lingua gratuiti di coppie di parentesi.

Ricorsiva espressioni regolari (che sono nuovi per me, ma mi hanno assicurato esistono in Perl e PCRE) sembrano riconoscere almeno la maggior parte delle lampade a risparmio energetico.

Qualcuno ha fatto o leggere qualsiasi ricerca in questo settore?Quali sono i limiti di questi "moderni" espressioni regolari?Non riconoscono strettamente più o strettamente minore di CFGs, di LL o grammatiche LR?O non esistono entrambe le lingue che possono essere riconosciuti da una regex, ma non è un CFG e l'opposto?

Link a documenti rilevanti, sarebbe molto apprezzato.

Answer 1

Schema Di Ricorsione

Con ricorsiva modelli, si dispone di un modulo di discesa ricorsiva corrispondenza.

Questo è bene per una varietà di problemi, ma una volta che si vuole realmente fare discesa ricorsiva l'analisi, è necessario inserire la cattura di gruppi di qua e di là, ed è imbarazzante per recuperare la piena analizzare la struttura in questo modo.Damian Conway Regexp::Grammatiche modulo per il Perl trasforma il semplice modello in una equivalente che fa automaticamente tutto ciò che di nome cattura in una struttura dati ricorsiva, rendendo molto più facile il recupero della struttura analizzata.Ho un esempio di confronto tra questi due approcci alla fine di questo intervento.

Restrizioni sulla Ricorsione

La domanda era quali tipi di grammatiche che ricorsive modelli possono abbinare.Beh, non sono certo discesa ricorsiva tipo matcher.L'unica cosa che mi viene in mente è che ricorsiva modelli non può gestire a sinistra la ricorsione. Questo pone un vincolo sui tipi di grammatiche che si possono applicare per.A volte è possibile riordinare le produzioni per eliminare la ricorsione sinistra.

BTW, PCRE e Perl differire leggermente su come si è permesso di frase la ricorsione.Si vedano le sezioni “RICORSIVA MODELLI” e “Ricorsione differenza da Perl” in pcrepattern pagina di manuale.ad esempio:Perl in grado di gestire ^(.|(.)(?1)\2)$ dove PCRE richiede ^((.)(?1)\2|.)$ invece.

Ricorsione Demo

La necessità per ricorsiva modelli si pone sorprendentemente frequente.Uno visitati esempio è quando è necessario associare qualcosa che può nidificare, come la balanced parentesi, virgolette, o anche HTML/XML.Ecco la partita per balenced parentesi:

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

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

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

Poi di nuovo, dal momento che stiamo usando una parentesi per il nostro ricorsione, un chiaro esempio potrebbe essere corrispondenti nidificati apici:

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

Un altro modo ricorsivo definito cosa si può desiderare un match sarebbe un palindromo.Questo semplice modello funziona in Perl:

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

cui è possibile testare la maggior parte dei sistemi utilizza qualcosa di simile a questo:

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

Nota che PCRE di attuazione della ricorsione richiede più elaborato

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

Questo è a causa di restrizioni su come PCRE ricorsione opere.

L'Analisi Corretta

Per me, gli esempi di cui sopra sono per lo più giocattoli partite, non tutte che interessante, davvero.Quando diventa interessante è quando si dispone di un vero e proprio grammatica si sta cercando di analizzare.Per esempio, RFC 5322 definisce un indirizzo e-mail piuttosto elaborato.Qui c'è un “grammaticali” modello per corrispondenza:

$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 vedete, è molto BNF-come.Il problema è che è solo una partita, non una cattura.E davvero non si desidera circondano l'intera cosa con l'acquisizione di una parentesi perché non dire che la produzione abbinati parte.In precedenza menzionato Regexp::Grammatiche modulo, si può.

#!/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 può vedere, utilizzando un molto leggermente diversa notazione nel modello, è ora ottenere qualcosa che memorizza l'intero albero sintattico di distanza per voi in %/ variabile, con tutto ben etichettati.Il risultato della trasformazione è ancora un modello, come si può vedere dal =~ operatore.E 'solo un po' magico.