O poder reconhecer de expressões regulares “modernos”

Question

O que classe de linguagens que regexes modernos reais realmente reconhecer?

Sempre que há um grupo de comprimento captura ilimitada com uma referência para trás (por exemplo (.*)_\1) um regex agora está combinando uma linguagem não-regular. Mas isso, por si só, não é suficiente para combinar algo como S ::= '(' S ')' | ε -. A linguagem livre de contexto de pares de parênteses

regexes Recursivos (que são novos para mim, mas estou exist assegurada em Perl e PCRE) parecem reconhecer, pelo menos, a maioria das lâmpadas fluorescentes compactas.

Alguém já fez ou ler qualquer pesquisa nesta área? Quais são as limitações dessas expressões regulares "modernos"? Será que eles reconhecem estritamente mais ou estritamente menor que CFGs, de LL ou LR gramáticas? Ou existem ambas as línguas que podem ser reconhecidos por um regex, mas não uma CFG e o contrário?

Os links para documentos relevantes seria muito apreciado.

Answer 1

Pattern recursão

Com padrões recursiva, você tem uma forma de descida recursiva harmonização .

Isso é bom para uma variedade de problemas, mas uma vez que você quer realmente fazer a descida recursiva parsing , você precisa inserir grupos de captura aqui e ali, e é difícil de recuperar a estrutura de análise completa nesse caminho. Damian Conway Regexp :: Gramáticas módulo para Perl transforma o padrão simples em uma equivalente que faz automaticamente tudo o que chamado captura em uma estrutura de dados recursiva, para fazer a recuperação muito mais fácil da estrutura analisada. Eu tenho uma amostra comparando estas duas abordagens no final desta postagem.

Restrições à recursão

A questão era que tipos de gramáticas que os padrões recursiva pode igualar. Bem, eles são certamente recursiva descida tipo matchers. A única coisa que vem à mente é que padrões recursiva não pode lidar com esquerda recursão. Isto coloca uma restrição na tipos de gramáticas que você pode aplicar para eles. Às vezes você pode reorganizar suas produções para eliminar recursão esquerdo.

BTW, PCRE e Perl ligeiramente diferente de como você está autorizado a frase a recursão. Consulte as seções sobre “padrões recursiva” e “diferença recursão de Perl” no pcrepattern manpage. por exemplo:. Perl pode manipular ^(.|(.)(?1)\2)$ onde PCRE requer ^((.)(?1)\2|.)$ vez

recursão Demos

A necessidade de padrões recursiva surge surpreendentemente freqüentemente. Um exemplo bem visitado é quando você precisa combinar algo que pode ninho, tais como parênteses balanceados, citações, ou até mesmo HTML / tags XML. Aqui está o jogo para parens balenced:

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

Eu acho que mais difícil de ler por causa de sua natureza compacta. Isso é facilmente curável com modo /x para fazer espaços em branco não está mais significativa:

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

Então, novamente, uma vez que estamos usando parênteses para o nosso recursão, um exemplo mais claro seria combinar aspas simples aninhados:

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

Outra coisa definida recursivamente você pode querer jogo seria um palíndromo. Esse padrão simples funciona em Perl:

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

que você pode testar na maioria dos sistemas usando algo parecido com isto:

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

Note que a implementação de recursão de PCRE requer a mais elaborada

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

Este é por causa de restrições sobre como funciona a recursão PCRE.

adequada de análise

Para mim, os exemplos acima são principalmente partidas brinquedo, nem todos os que interessante, realmente. Quando se torna interessante é quando você tem uma gramática real, você está tentando analisar. Por exemplo, RFC 5322 define um endereço de e-mail em vez elaborada. Aqui está um padrão de “gramatical” para combiná-lo:

$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 você pode ver, isso é muito BNF-like. O problema é que é apenas um jogo, não uma captura. E você realmente não quer apenas cercar a coisa toda com parens capturando porque isso não lhe diz que a produção combinada que parte. Usando o módulo Regexp :: Gramáticas mencionado anteriormente, nós 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 você pode ver, usando uma notação ligeiramente diferente do padrão, agora você pode obter algo que armazena toda a árvore de análise afastado para você na variável %/, com tudo cuidadosamente etiquetado. O resultado da transformação ainda é um padrão, como você pode ver pelo operador =~. É apenas um pouco mágico.