Jaką klasę języków faktycznie rozpoznają współczesne regexy?

Ilekroć istnieje grupa przechwytywania nieograniczonej długości z odwołaniem wstecznym (np. (.*)_\1), Wyrażenie regularne pasuje teraz do nieregularnego języka. Ale to samo w sobie nie wystarczy, aby dopasować coś w rodzaju S ::= '(' S ')' | ε- bezkontekstowego języka dopasowywania par par.

Rekurencyjne wyrażenia regularne (które są dla mnie nowe, ale jestem pewien, że istnieją w Perlu i PCRE) wydają się rozpoznawać przynajmniej większość świetlówek kompaktowych.

Czy ktoś przeprowadził lub przeczytał jakieś badania w tej dziedzinie? Jakie są ograniczenia tych „nowoczesnych” wyrażeń regularnych? Czy rozpoznają bardziej lub ściśle mniej niż CFG, gramatyki LL lub LR? A może istnieją oba języki, które można rozpoznać za pomocą wyrażenia regularnego, ale nie przez CFG i odwrotnie?

Mile widziane byłyby linki do odpowiednich artykułów.

Rekursja wzorców

W przypadku wzorców rekurencyjnych masz postać rekursywnego dopasowywania zejść .

Jest to dobre w przypadku różnych problemów, ale gdy chcesz faktycznie przeprowadzić parsowanie rekursywne , musisz wstawić grupy przechwytywania tu i tam, a odzyskanie pełnej struktury analizy w ten sposób jest niewygodne. Moduł Regexp :: Grammars Damiana Conwaya dla Perla przekształca prosty wzorzec w równoważny, który automatycznie wykonuje wszystkie nazwane przechwytywanie w rekursywną strukturę danych, co znacznie ułatwia pobieranie przeanalizowanej struktury. Mam próbkę porównującą te dwa podejścia na końcu tego posta.

Ograniczenia rekursji

Pytanie brzmiało, jakie rodzaje gramatyki mogą pasować do wzorców rekurencyjnych. Cóż, z pewnością są to dopasowujące rekursywne pochodzenie . Jedyną rzeczą, która przychodzi na myśl, jest to, że wzorce rekurencyjne nie radzą sobie z lewą rekurencją . To nakłada ograniczenia na rodzaje gramatyki, do których możesz je zastosować. Czasami możesz zmienić kolejność swoich produkcji, aby wyeliminować lewostronną rekurencję.

BTW, PCRE i Perl różnią się nieco pod względem tego, jak możesz frazować rekursję. Zobacz sekcje „WZORY REKURSYWNE” i „Różnica rekurencji w stosunku do Perla” na stronie podręcznika pcrepattern . np .: Perl może obsłużyć to, ^(.|(.)(?1)\2)$czego wymaga PCRE ^((.)(?1)\2|.)$.

Dema rekurencji

Potrzeba rekurencyjnych wzorców pojawia się zaskakująco często. Jednym z dobrze odwiedzanych przykładów jest sytuacja, w której musisz dopasować coś, co można zagnieździć, na przykład wyważone nawiasy, cudzysłowy, a nawet tagi HTML / XML. Oto mecz dla zbalansowanych parens:

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

Uważam, że jest to trudniejsze do odczytania ze względu na jego zwarty charakter. Można to łatwo wyleczyć w /xtrybie, aby białe znaki nie były już istotne:

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

Z drugiej strony, ponieważ używamy parens do naszej rekursji, jaśniejszym przykładem byłoby dopasowywanie zagnieżdżonych pojedynczych cudzysłowów:

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

Inną zdefiniowaną rekurencyjnie rzeczą, którą możesz chcieć dopasować, byłby 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 rekurencja w PCRE wymaga bardziej skomplikowanych rozwiązań

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

Dzieje się tak z powodu ograniczeń dotyczących działania rekurencji PCRE.

Prawidłowe analizowanie

Dla mnie powyższe przykłady to głównie zapałki zabawek , naprawdę nie wszystkie są tak interesujące. Kiedy staje się interesujący, kiedy masz prawdziwą gramatykę, którą próbujesz przeanalizować. Na przykład RFC 5322 definiuje adres e-mail dość szczegółowo. Oto „gramatyczny” wzorzec pasujący do tego:

$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 widać, jest to bardzo podobne do BNF. Problem w tym, że to tylko dopasowanie, a nie bicie. I naprawdę nie chcesz po prostu otaczać całości przechwytywaniem parenów, ponieważ to nie mówi ci, która produkcja pasuje do której części. Korzystając ze wspomnianego wcześniej 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 bardzo nieznacznie innej notacji we wzorcu, otrzymujesz teraz coś, co przechowuje całe drzewo parsowania dla ciebie w %/zmiennej, ze wszystkimi starannie oznaczonymi etykietami. Rezultatem transformacji jest nadal wzór, co widać po =~operatorze. To trochę magiczne.