Rekurencja Wzorca

Z rekurencyjnymi wzorami, masz postać rekurencyjnego zejścia dopasowania.

Jest to w porządku dla różnych problemów, ale gdy chcesz wykonać rekurencyjne parsowanie , musisz wstawić grupy przechwytywania tu i tam, a odzyskanie pełnej struktury parsowania w ten sposób jest niezręczne. Damian Conway ' s Regexp:: Grammars moduł dla Perla przekształca prosty wzór w równoważny, który automatycznie robi wszystko, co nazwane przechwytywanie w rekurencyjną strukturę danych, co znacznie ułatwia pobieranie analizowanej struktury. Mam próbkę porównującą te dwa podejścia na końcu tego postu.

Ograniczenia rekurencji

Pytanie brzmiało, jakie rodzaje gramatyk mogą pasować do wzorców rekurencyjnych. Cóż, z pewnością są to rekurencyjne spadki typu matchers. Jedyne co przychodzi mi na myśl to to, że rekurencyjne wzorce nie mogą obsłużyć rekurencja . to nakłada ograniczenie na rodzaje gramatyk, do których można je zastosować. Czasami można zmienić kolejność produkcji, aby wyeliminować lewe rekurencje.

BTW, PCRE i Perl różnią się nieco sposobem wyrażenia rekursji. Zobacz sekcje "recursive PATTERNS" i "Recursion difference from Perl" na stronie podręcznika pcrepattern. na przykład: Perl potrafi obsłużyć ^(.|(.)(?1)\2)$, gdzie PCRE wymaga ^((.)(?1)\2|.)$.

Recursion Demos

Potrzeba dla rekurencyjnych wzorców powstaje zaskakująco często. Jednym z dobrze odwiedzanych przykładów jest dopasowanie czegoś, co może się zagnieżdżać, takiego jak zrównoważone nawiasy, cudzysłowy, a nawet znaczniki HTML / XML. Oto mecz dla balancerów:

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

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

Z drugiej strony, ponieważ używamy parens dla naszej rekurencji, jaśniejszym przykładem może być dopasowanie zagnieżdżonych pojedynczych cudzysłowów:

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

Inną rekurencyjnie zdefiniowaną rzeczą, którą możesz chcieć dopasować, będzie palindrom. Ten prosty wzorzec działa w Perlu:

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

Które możesz przetestować na większości systemów używając czegoś takiego:

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

Zauważ, że implementacja rekurencji PCRE wymaga bardziej rozbudowanego

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

Jest to spowodowane ograniczeniami w sposobie działania rekurencji PCRE.

Właściwe Parsowanie

Dla mnie powyższe przykłady to głównie zabawkowe mecze, nie wszystkie , które są naprawdę interesujące. Kiedy staje się to interesujące, gdy masz prawdziwą gramatykę, którą próbujesz przeanalizować. Na przykład, RFC 5322 definiuje adres pocztowy dość szczegółowo. Oto wzór "gramatyczny"pasujący do niego:

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

Jak widzisz, to bardzo podobne do BNF. Problem w tym, że to tylko dopasowanie, a nie schwytanie. I naprawdę nie chcesz otaczać całej sprawy przechwytywaniem parenów, bo to nie mówi ci, która produkcja pasuje do której części. Używając wcześniej wspomnianego modułu regexp:: Grammars, możemy.

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

Jak widzisz, używając nieco innej notacji we wzorze, otrzymujesz teraz coś, co przechowuje całe drzewo parse dla ciebie w zmiennej %/, ze wszystkim starannie oznaczonym. Wynik transformacji jest nadal wzorcem, co widać po operatorze =~. To trochę magiczne.