El poder de reconocimiento de las expresiones regulares "modernas"

Question

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

Siempre que exista un grupo de captura de longitud ilimitada con una referencia retrospectiva (por ejemplo, (.*)_\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 ')' | ε - el lenguaje libre de contexto de emparejar pares de parens.

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

¿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 al revés?

Los enlaces a documentos relevantes serían muy apreciados.

Answer 1

Patrón recursividad

Con patrones recurrentes, que tiene una forma de descenso recursivo a juego.

Esto está bien para una variedad de problemas, pero una vez que quiere hacer realmente descendente recursivo análisis, es necesario insertar grupos de captura de aquí para allá, y es difícil de recuperar la estructura de análisis completo de esta manera. El módulo Regexp::Grammars de Damian Conway transforma el patrón simple en uno equivalente que automáticamente hace que todo eso se llame capturar en una estructura recursiva de datos, 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 a la recursividad

La pregunta era qué tipo de gramáticas recursivas que los patrones pueden igualar. Bueno, ciertamente son recursive descent tipo matchers. Lo único que se me ocurre es que los patrones recursivos no pueden manejar left recursion. Esto pone una restricción en los géneros a los que puedes aplicarlos. A veces puede reordenar sus producciones para eliminar la recursividad a la izquierda.

BTW, PCRE y Perl difieren ligeramente en cómo se puede 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|.)$ en su lugar.

recursión Demos

La necesidad de patrones recursivos surge sorprendentemente 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 equilibrados:

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

Me resulta algo truculento de leer debido a su naturaleza compacta.Esto es fácilmente curable con /x modo de hacer espacio en blanco ya no es significativa:

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

Por otra parte, ya que estamos utilizando para nuestro parens recursividad, un ejemplo más claro sería juego comillas simples anidados:

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

Otra cosa definida recursivamente con la que desearía coincidir sería un palíndromo. Este patrón simple funciona en Perl:

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

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

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

Nota que la aplicación de la recursión de PCRE requiere la más elaborada

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

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

de análisis apropiado

Para mí, los ejemplos anteriores son en su mayoría partidos de juguete, que no todos interesante, la verdad. 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 se ve, mediante el uso de una notación ligeramente diferente en el patrón, ahora se consigue algo que almacena todo el árbol de análisis sintáctico de distancia para usted en la variable %/, con todo perfectamente etiquetados. El resultado de la transformación sigue siendo un patrón, como puede ver en el operador =~. Es solo un poco mágico.