Die Anerkennung der macht der "moderne" regexes

Muster Rekursion

Mit rekursiven Muster, Sie haben eine form der rekursiven Abstieg passenden.

Dies ist gut für eine Vielzahl von Problemen, aber wenn Sie wollen, um tatsächlich rekursiven Abstieg Analyse, müssen Sie legen Sie die capture-Gruppen hier und dort, und es ist umständlich, zum wiederherstellen der vollen parse-Struktur in dieser Weise. Damian Conway ist Regexp::Grammars - Modul für Perl verwandelt das einfache Muster in eine äquivalente ein, dass automatisch alle, die benannte Aufnahme in eine rekursive Datenstruktur, so dass für viel einfacher Abruf der analysierten Struktur. Ich habe eine Probe vergleicht man diese beiden Ansätze am Ende dieses Postings.

Einschränkungen der Rekursion

War die Frage, welche Arten von Grammatiken, rekursive Muster zuordnen kann. Nun, Sie sind sicherlich rekursiver Abstieg Typ Matcher. Das einzige, was mir einfällt, ist, dass rekursive Muster nicht in den Griff Links-Rekursion. Dies stellt eine Einschränkung auf die Arten von Grammatiken, die Sie anwenden können, Sie. Manchmal können Sie neu anordnen, Ihre Produktionen zu eliminieren Links-Rekursion.

BTW, PCRE und Perl unterscheiden sich geringfügig, wie Sie sind, erlaubt Satz der Rekursion. Siehe Abschnitt "RECURSIVE PATTERNS" und "Rekursion Unterschied von Perl" in der pcrepattern manpage. zB: Perl verarbeiten kann ^(.|(.)(?1)\2)$ wo PCRE erfordert ^((.)(?1)\2|.)$ statt.

Rekursion Demos

Die Notwendigkeit für rekursive Muster entsteht, überraschend Häufig. Ein gut besuchter Beispiel ist, wenn Sie benötigen, zu entsprechen, etwas, das nest, wie ausgewogene Klammern, Anführungszeichen, oder auch HTML - /XML-tags. Hier ist das match für balenced parens:

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

Ich finde, dass es schwieriger zu Lesen, weil seine kompakte Natur. Dies ist leicht heilbar mit /x - Modus zu machen whitespace nicht mehr signifikant:

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

Dann wieder, da sind wir mit parens für unsere Rekursion, ein deutlicheres Beispiel wäre passender verschachtelte einfache Anführungszeichen:

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

Anderen rekursiv definiert, was Sie wünschen können, zu entsprechen, wäre ein Palindrom. Diese einfachen Muster funktioniert in Perl:

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

dem Sie testen können auf den meisten Systemen mit so etwas wie dieses:

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

Beachten Sie, dass PCRE ist die Implementierung der Rekursion erfordert aufwändigere

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

Dies ist wegen der Beschränkungen auf, wie PCRE Rekursion funktioniert.

Ordnungsgemäße Analyse

Mir, die Beispiele oben sind meist Spielzeug, Spiele, nicht alle , dass interessant, wirklich. Interessant wird es dann, wenn Sie eine echte Grammatik versuchen Sie zu analysieren. Zum Beispiel, RFC 5322 definiert einen E-mail-Adresse und nicht aufwändig. Hier ist eine "grammatische" Muster zu entsprechen:

$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;

Wie Sie sehen, das ist sehr BNF-like. Das problem ist, es ist nur ein Spiel, nicht ein erfassen. Und Sie wirklich nicht wollen, umgeben Sie das ganze mit der Erfassung parens, da wissen Sie noch nicht, die Produktion abgestimmt, welcher Teil. Mit den zuvor genannten Regexp::Grammars-Modul, das können wir.

#!/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
    }
}

Wie Sie sehen, durch die Verwendung leicht unterschiedlicher Schreibweise in das Muster, Sie bekommen jetzt etwas, das speichert die kompletten parse-Baum-Weg für Sie in die %/ variable, mit der alles säuberlich beschriftet. Das Ergebnis der transformation ist immer noch ein Muster, wie man sehen kann, die =~ Betreiber. Es ist nur ein bisschen Magie.