regex - El poder de reconocimiento de las expresiones regulares "modernas"

perl theory

Question

¿Qué clase de idiomas reconocen realmente las expresiones reales reales?

Siempre que haya un grupo de captura de longitud ilimitada con una referencia retrospectiva (p (.*)_/1 Ej (.*)_/1 ) una expresión regular ahora se corresponde con un idioma no habitual. Pero esto, por sí solo, no es suficiente para que coincida con algo como S ::= ''('' S '')'' | ε S ::= ''('' S '')'' | ε - el lenguaje libre de contexto de emparejar pares de parens.

Las expresiones regulares recursivas (que son nuevas para mí, pero estoy seguro 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 estos regex "modernos"? ¿Reconocen estrictamente más o estrictamente menos que los CFG, de las gramáticas LL o LR? ¿O existen ambos idiomas que pueden ser reconocidos por una expresión regular pero no un CFG y todo lo contrario?

Los enlaces a documentos relevantes serían muy apreciados.

Answer 1

Recursión de patrón

Con patrones recursivos, tiene una forma de coincidencia de descenso recursivo.

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 difícil recuperar la estructura de análisis completo de esta manera. El módulo Regexp::Grammars Damian Conway para Perl transforma el patrón simple en uno equivalente que automáticamente hace que todo eso se llame capturar en una estructura recursiva de datos, facilitando la recuperación de la estructura analizada. Tengo una muestra que compara estos dos enfoques al final de esta publicación.

Restricciones a la recursión

La pregunta era qué tipo de gramáticas pueden coincidir con los patrones recursivos. Bueno, ciertamente son emparejamientos de tipo descendiente recursivo . Lo único que se me ocurre es que los patrones recursivos no pueden manejar la recursividad a la izquierda . Esto pone una restricción en el tipo de gramáticas a las que puedes aplicarlas. A veces puede reordenar sus producciones para eliminar la recursividad a la izquierda.

Por cierto, PCRE y Perl difieren ligeramente en cómo se le permite expresar la recursión. 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 PCRE requiere ^((.)(?1)/2|.)$ lugar.

Demostraciones de recursión

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

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

Me parece más complicado de leer debido a su naturaleza compacta. Esto es fácilmente curable con el modo /x para hacer que el espacio en blanco ya no sea significativo:

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

Por otra parte, dado que estamos utilizando parens para nuestra recursión, un ejemplo más claro sería hacer coincidir las comillas simples anidadas:

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

Otra cosa recursivamente definida que puede desear emparejar 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 recursión de PCRE requiere los más elaborados

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

Esto se debe a las restricciones sobre cómo funciona la recursión de PCRE.

Análisis correcto

Para mí, los ejemplos anteriores son en su mayoría partidos de juguete, realmente no todos interesantes. 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 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 coincide 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 muy diferente en el patrón, ahora obtiene algo que almacena todo el árbol de análisis para usted en %/ variable, con todo claramente etiquetado. El resultado de la transformación sigue siendo un patrón, como puede ver con el operador =~ . Es solo un poco mágico.