El poder de reconocimiento de las expresiones regulares "modernas"

Resuelto tobyodavies asked hace 13 años • 1 respuestas

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

Siempre que hay un grupo de captura de longitud ilimitada con una referencia inversa (por ejemplo (.*)_\1), una expresión regular ahora coincide con un idioma no regular. Pero esto, por sí solo, no es suficiente para hacer coincidir algo como S ::= '(' S ')' | εel lenguaje libre de contexto de pares de padres 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 realizado 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, las gramáticas LL o LR? ¿O existen ambos idiomas que pueden ser reconocidos por una expresión regular pero no por un CFG y viceversa?

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

tobyodavies avatar Jan 30 '11 10:01 tobyodavies
Aceptado

Recursión de patrón

Con los patrones recursivos, tienes una forma de coincidencia de descenso recursivo .

Esto está bien para una variedad de problemas, pero una vez que realmente desea realizar un análisis de descenso recursivo , necesita 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 realiza automáticamente toda la captura de nombres en una estructura de datos recursiva, lo que facilita mucho la recuperación de la estructura analizada. Tengo una muestra que compara estos dos enfoques al final de esta publicación.

Restricciones a la recursividad

La pregunta era qué tipos de gramáticas pueden coincidir con los patrones recursivos. Bueno, ciertamente son comparadores de tipo de descenso recursivo . Lo único que me viene a la mente es que los patrones recursivos no pueden manejar la recursividad por la izquierda . Esto impone una limitación a los tipos de gramáticas a las que se pueden aplicar. A veces puedes reordenar tus 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 con respecto a Perl” en la página de manual de pcrepattern . por ejemplo: Perl puede manejar ^(.|(.)(?1)\2)$lo que requiere PCRE ^((.)(?1)\2|.)$.

Demostraciones de recursividad

La necesidad de patrones recursivos surge con sorprendente frecuencia. Un ejemplo muy conocido es cuando necesita hacer coincidir algo que se puede anidar, como paréntesis equilibrados, comillas o incluso etiquetas HTML/XML. Aquí está el partido para padres equilibrados:

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

Me resulta más complicado de leer debido a su naturaleza compacta. Esto se puede solucionar fácilmente con /xel modo para hacer que los espacios en blanco dejen de ser significativos:

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

Por otra parte, dado que usamos pares para nuestra recursividad, un ejemplo más claro sería hacer coincidir comillas simples anidadas:

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

Otra cosa definida recursivamente que quizás desees hacer coincidir sería un palíndromo. Este patrón simple funciona en Perl:

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

que puedes 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 por parte de PCRE requiere métodos más elaborados.

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

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

Análisis adecuado

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

$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 puede ver, eso es muy parecido a BNF. El problema es que se trata sólo de una coincidencia, no de una captura. Y realmente no quieres rodear todo con la captura de padres porque eso no te dice qué producción coincidió con cada 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 cuidadosamente etiquetado. El resultado de la transformación sigue siendo un patrón, como puede ver el =~operador. Es un poco mágico.

tchrist avatar Jan 30 '2011 15:01 tchrist