¿Qué clase de lenguajes reconocen realmente las expresiones regulares modernas reales?

Siempre que haya un grupo de captura de longitud ilimitada con una referencia (.*)_\1inversa (por ejemplo ), una expresión regular ahora coincide con un idioma no regular. Pero esto, por sí solo, no es suficiente para coincidir con algo como S ::= '(' S ')' | ε: el lenguaje sin contexto de pares de parens coincidentes.

Las expresiones regulares recursivas (que son nuevas para mí, pero estoy seguro de que existen en Perl y PCRE) parecen reconocer al menos la mayoría de las CFL.

¿Alguien ha hecho o leído alguna investigación en esta área? ¿Cuáles son las limitaciones de estas expresiones regulares "modernas"? ¿Reconocen estrictamente más o estrictamente menos que los CFG, de las gramáticas LL o LR? ¿O existen ambos lenguajes que pueden ser reconocidos por una expresión regular pero no por un CFG y lo contrario?

Se agradecerían mucho los enlaces a artículos relevantes.

Recurrencia de patrón

Con patrones recursivos, tiene una forma de coincidencia de descendencia recursiva .

Esto está bien para una variedad de problemas, pero una vez que desee realizar un análisis de descenso recursivo , debe insertar grupos de captura aquí y allá, y es incómodo recuperar la estructura de análisis completa de esta manera. El módulo Regexp :: Grammars de Damian Conway para Perl transforma el patrón simple en uno equivalente que automáticamente hace toda esa captura con nombre en una estructura de datos recursiva, lo que facilita la recuperación de la estructura analizada. Tengo una muestra que compara estos dos enfoques al final de esta publicación.

Restricciones de recursividad

La pregunta era qué tipos de gramáticas pueden coincidir con los patrones recursivos. Bueno, ciertamente son comparadores de tipo descendencia recursiva . Lo único que me viene a la mente es que los patrones recursivos no pueden manejar la recursividad por la izquierda . Esto impone una restricción al tipo de gramáticas a las que puede aplicarlas. A veces puede reordenar sus producciones para eliminar la recursividad por la izquierda.

Por cierto, PCRE y Perl difieren ligeramente en cómo se le permite expresar la recursividad. Consulte las secciones sobre "PATRONES RECURSIVOS" y "Diferencia de recursividad de Perl" en la página de manual de pcrepattern . Por ejemplo: Perl puede manejar ^(.|(.)(?1)\2)$donde lo requiera PCRE ^((.)(?1)\2|.)$.

Demos de recursividad

La necesidad de patrones recursivos surge con una frecuencia sorprendente. Un ejemplo muy visitado es cuando necesita hacer coincidir algo que pueda anidar, como paréntesis equilibrados, comillas o incluso etiquetas HTML / XML. Aquí está la coincidencia para los parens equilibrados:

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

Encuentro eso más complicado de leer debido a su naturaleza compacta. Esto se puede curar fácilmente con el /xmodo para hacer que los espacios en blanco ya no sean significativos:

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

Por otra parte, dado que estamos usando parens para nuestra recursividad, un ejemplo más claro sería la coincidencia de comillas simples anidadas:

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

Otra cosa definida de forma recursiva que tal vez desee hacer coincidir sería un palíndromo. Este patrón simple funciona en Perl:

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

que puede probar en la mayoría de los sistemas usando algo como esto:

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

Tenga en cuenta que la implementación de la recursividad de PCRE requiere el más elaborado

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

Esto se debe a las restricciones sobre cómo funciona la recursividad PCRE.

Análisis adecuado

Para mí, los ejemplos anteriores son en su mayoría partidos de juguete, no tan interesantes, en realidad. Cuando se vuelve interesante es cuando tienes una gramática real que estás tratando de analizar. Por ejemplo, RFC 5322 define una dirección de correo de forma bastante elaborada. Aquí hay un patrón "gramatical" para que coincida:

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

Como ve, eso es muy parecido a BNF. El problema es que es solo una coincidencia, no una captura. Y realmente no quieres rodear todo el asunto con la captura de parens porque eso no te dice qué producción coincidió con qué parte. Usando el módulo Regexp :: Grammars mencionado anteriormente, podemos.

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

Como puede ver, al usar una notación ligeramente diferente en el patrón, ahora obtiene algo que almacena todo el árbol de análisis en la %/variable, con todo claramente etiquetado. El resultado de la transformación sigue siendo un patrón, como puede ver el =~operador. Es un poco mágico.