La reconnaissance de la puissance de "moderne" regexes

Question

Quelle classe de langues moderne réel regexes vraiment le reconnaître?

Chaque fois qu'il ya une surabondance de la longueur de la capture d'un groupe avec une référence (par exemple, (.*)_\1) d'une expression régulière est maintenant identique à un non-langage régulier. Mais cela, en soi, n'est pas suffisant pour correspondre à quelque chose comme S ::= '(' S ')' | ε - le contexte du langage de l'appariement des paires de parenthèses.

Récursive regexes (qui sont nouveaux pour moi, mais je suis assuré existe en Perl et PCRE) semblent reconnaître au moins la plupart des ampoules fluorescentes compactes.

Quelqu'un a fait ou lu toute la recherche dans ce domaine? Quelles sont les limites de ces "modernes" regexes? Ils ne reconnaissent strictement plus ou strictement moins de CFGs, de LL ou grammaires LR? Ou existe-t-il les deux langues qui peuvent être reconnus par une regex mais pas un CFG et le contraire?

Des liens vers les documents pertinents seront très appréciés.

Answer 1

Schéma De Récursion

Avec récursive modèles, vous disposez d'un formulaire de descente récursive de correspondance.

C'est très bien pour une variété de problèmes, mais une fois que vous voulez réellement faire récursive descente d'analyse, vous devez insérer la capture des groupes ici et là, et il est difficile de récupérer la totalité analyser la structure de cette façon. Damian Conway Regexp::Grammaires module Perl transforme le simple motif dans l'équivalent d'une automatiquement toutes les nommés de la capture dans une structure de données récursive, ce qui pour beaucoup plus facile la récupération de l'analyse de la structure. J'ai un échantillon de la comparaison de ces deux approches à la fin de cette publication.

Les Restrictions sur la Récursivité

La question était de savoir quels types de grammaires que récursive modèles peuvent correspondre. Eh bien, ils sont certainement descente récursive type de rapprochement. La seule chose qui vient à l'esprit est que récursive modèles ne peuvent pas gérer la récursion à gauche. Cette situation exerce une contrainte sur les types de grammaires que vous pouvez appliquer à. Parfois, vous pouvez réorganiser vos productions afin d'éliminer la récursivité à gauche.

BTW, PCRE et Perl diffèrent légèrement sur la façon dont vous êtes autorisé à l'expression de la récursivité. Voir les sections "RÉCURSIVE MODÈLES" et de "Récursivité différence de Perl" dans le pcrepattern page de manuel. par exemple: Perl peut manipuler ^(.|(.)(?1)\2)$ où PCRE exige ^((.)(?1)\2|.)$ à la place.

La Récursivité Des Démos

La nécessité pour les motifs se pose très fréquemment. Un bien visité, par exemple, lorsque vous avez besoin pour correspondre à quelque chose qui peut nid, tels que l'équilibre entre parenthèses, guillemets, ou même HTML/balises XML. Voici le match pour équilibrée parens:

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

Je trouve que le plus difficile à lire en raison de sa nature compacte. Ceci est facilement curable avec /x mode pour rendre les espaces plus importants:

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

Puis de nouveau, puisque nous l'utilisons des parens de nos récursivité, une meilleure exemple serait de correspondance imbriquée entre guillemets simples:

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

Une autre manière récursive défini chose que vous pouvez souhaiter match allait être un palindrome. Ce simple modèle fonctionne en Perl:

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

que vous pouvez tester sur la plupart des systèmes utilisant quelque chose comme ceci:

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

Notez que PCRE de la mise en œuvre de la récursivité exige la plus élaborée

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

C'est en raison de restrictions sur la façon dont PCRE de la récursivité des œuvres.

Analyse Correcte

Pour moi, les exemples ci-dessus sont pour la plupart jouet correspond, pas tous qui intéressant, vraiment. Quand il devient intéressant, c'est lorsque vous avez une véritable grammaire que vous essayez de l'analyser. Par exemple, le RFC 5322 définit une adresse e-mail plutôt minutieusement. Voici une "grammaire" de modèle pour le match:

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

Comme vous le voyez, c'est très BNF. Le problème est qu'il est juste un match, pas une capture. Et vous ne voulez vraiment pas juste entourer le tout avec capture parens parce que cela ne vous dirai pas lesquels la production appariés qui partie. À l'aide de la mentionné précédemment Regexp::Grammaires module, nous le pouvons.

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

Comme vous le voyez, à l'aide d'un très légèrement différente de la notation dans le modèle, vous pouvez maintenant obtenir quelque chose qui stocke l'ensemble de l'arbre d'analyse, par vous dans l' %/ variable, le tout soigneusement étiquetés. Le résultat de la transformation est encore un modèle, comme vous pouvez le voir par l' =~ de l'opérateur. C'est juste un peu magique.