El poder reconocer de expresiones regulares “modernos”

Question

¿Qué clase de lenguajes do expresiones regulares modernos reales en realidad reconocen?

Cada vez que hay un grupo de talla de captura sin límites con un back-referencia (por ejemplo (.*)_\1) una expresión regular está ahora que coincidan con un lenguaje no regular. Pero esto, por sí solo, no es suficiente para que coincida con algo así como S ::= '(' S ')' | ε -. El lenguaje libre de contexto de pares coincidentes de parens

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

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

Los enlaces a documentos relevantes sería muy apreciada.

Answer 1

Pattern recursión

Con los 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 completa De este modo. Damian Conway Regexp :: gramáticas módulo para Perl transforma el patrón simple en una equivalente que automáticamente hace todo lo que denomina captura en una estructura de datos recursiva, para hacer mucho más fácil la recuperación de la estructura analizada. Tengo una muestra de la comparación de estos dos enfoques al final de esta publicación.

Restricciones de recursión

La pregunta era qué tipo de gramáticas recursivas que los patrones pueden igualar. Bueno, son sin duda recursiva descenso tipo comparadores. La única cosa que viene a la mente es que patrones recurrentes no pueden manejar recursión por la izquierda . Esto pone una restricción sobre el tipo de gramáticas que se pueden aplicar a ellos. A veces se puede cambiar el orden de sus producciones para eliminar la recursión por la izquierda.

Por cierto, PCRE y Perl difieren ligeramente de lo que está permitido formular la recursividad. Ver las secciones sobre “Patrones recursivos” y “diferencia recursividad de Perl” en el pcrepattern página de manual. por ejemplo:. Perl puede manejar ^(.|(.)(?1)\2)$ donde PCRE requiere ^((.)(?1)\2|.)$ lugar

recursión Demos

La necesidad de patrones recursivos surge sorprendentemente frecuencia. Un ejemplo muy visitado es cuando se necesita para que coincida con algo que anidan lata, como paréntesis equilibrados, citas, o incluso HTML / etiquetas XML. Aquí está el partido por parens balenced:

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

Me parece que la más difícil de leer debido a su naturaleza compacta. Esto es fácilmente curable con el modo /x para 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 recursiva definida puede que desee partido 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

Tenga en cuenta que la aplicación de la recursión de PCRE requiere la más elaborada

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

Esto es debido a las restricciones sobre cómo funciona la recursividad PCRE.

adecuada de análisis

Para mí, los ejemplos anteriores son en su mayoría partidos de juguete, no todos los que interesante, la verdad. Cuando se vuelve interesante es cuando se tiene una verdadera gramática que está tratando de analizar. Por ejemplo, RFC 5322 define una dirección de correo en lugar elaboradamente. Aquí hay un patrón “gramatical” para que coincida con él:

$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 se ve, que es muy similar a la BNF. El problema es que es sólo un partido, no una captura. Y que realmente no quiere simplemente rodear todo el asunto con parens captura porque eso no te dice lo que la producción coincide con la que parte. Con el módulo de Regexp :: gramáticas se ha 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, que ahora recibe 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 se puede ver por el operador =~. Es sólo un poco mágico.