Quais idiomas as expressões regulares compatíveis com Perl reconhecem?

23

Como o título diz, passei algumas horas no final de semana passado tentando me convencer sobre a classe de idiomas correspondida por expressões regulares compatíveis com Perl, excluindo qualquer operador correspondente que permita executar código arbitrário dentro do padrão .

Se você não sabe o que são PCREs, leia isto e isto .

O problema é que os recursos disponíveis na Internet praticamente param em linguagens livres de contexto, e os PCREs podem corresponder mais do que aqueles (veja abaixo); mas realmente não sei onde encontrar mais teoremas ou trabalhos sobre esse tipo de coisa.

Em particular: PCREs são obviamente um superconjunto de idiomas regulares (como a sintaxe do PCRE possui todos os operadores de idiomas regulares).

Qualquer CFG pode ser colocado na forma normal de Greibach, o que remove a recursão esquerda. Eu acho que isso pode ser usado por meio de (?(DEFINE)...)grupos para "traduzir" a gramática em sub-rotinas correspondentes, evitando engasgar com a recursão esquerda, traduzindo:

  • o não terminal na cabeça de cada produção se torna uma sub-rotina (?<HEAD>...)
  • o corpo de cada produção é colocado na sub-rotina; os terminais são deixados como estão, os não terminais se tornam invocações de procedimentos (ie (?&NONTERMINAL));
  • todas as produções com o mesmo não-terminal que a cabeça são organizadas por meio do |operador (além de agrupamentos adicionais (?:...), se necessário)
  • o padrão se torna um (?(DEFINE)...)grupo que contém todas as produções "traduzidas" e uma invocação para o procedimento do símbolo inicial, para coincidir com a sequência inteira, ou seja,^(?(DEFINE)...)(?&START)$

Isso deve lidar com qualquer CFG. Portanto, os PCREs devem poder corresponder a qualquer CFL.

Há mais: vamos usar a linguagem simples ou seja, o idioma das strings repetidas duas vezes. Esse idioma não é uma CFL - o lema de bombeamento das CFLs falha. (Preste muita atenção que deve manter, portanto você não pode simplesmente bombear o início ou o fim das duas seqüências repetidas.)| v x w | p

L={ww|wΛ}
|vxw|p

No entanto, esta língua é facilmente compensada por um PCRE: ^(.*)\1$. Portanto, estamos estritamente acima das CFLs.

Quanto acima? Bem, como eu disse, não faço ideia. Não consegui encontrar nenhum recurso sobre CSLs ou todas as outras classes no meio para me decidir. Algum especialista disposto a discutir isso?

Adendo: Me pediram para especificar exatamente qual subconjunto da sintaxe PCRE deve ser permitido. Como escrevi no começo do post, queria excluir qualquer operador que permita executar código arbitrário dentro do padrão, como ??{}.

Pelo bem do argumento, acho que podemos manter a sintaxe definida na página do manual pcresyntax (3) , que é um subconjunto razoável do que o Perl 5.10-5.12 oferece, menos as frases de destaque (pois elas não estão dentro do padrão). Não tenho certeza de que adicionar ou remover verbos de controle de retorno retorne alterar o idioma que podemos reconhecer; se assim for, seria bom descobrir com quais classes temos e sem essas.

peppe
fonte
2
Inclua sua definição escolhida de PCRE na sua pergunta, pois ela mudou entre as versões. As regexes Perl reais podem conter código Perl arbitrário, tornando-as completas em Turing.
Gilles 'SO- stop be evil'
Eu adicionei uma nota no final, espero que deixe esse ponto mais claro.
peppe

Respostas:

7

Eu também achei esta postagem no blog extremamente interessante http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html . Ele fornece a mesma prova que eu dei antes sobre o fato de o regexps reconhecer as CFLs (reescrevendo a gramática através de DEFINEblocos) e até mesmo algumas CSLs (como o idioma das seqüências repetidas); ele se baseia nisso e continua, fornecendo uma prova de que os regexps com referências anteriores são difíceis de NP (reduzindo 3-SAT a um regexp).

peppe
fonte
2
Quando o autor diz "NP-complete", deveria estar dizendo "NP-hard". Eles não fornecem prova de que a classe de idiomas PCRE esteja contida no NP.
András Salamon
É verdade, também é observado nos comentários.
peppe
5

Eles decidem no máximo as linguagens sensíveis ao contexto (que, como você aponta, são um superconjunto das linguagens livres de contexto). Veja este post sobre monges perl .

O insight básico é que a "memória" da máquina é o número de grupos de captura, que é linearmente delimitado.

Xodarap
fonte
5
O argumento apresentado no segundo parágrafo explica por que o PCRE não pode aceitar mais do que o CS, mas não o porquê dessa inclusão ser exata (o que você sugere no seu primeiro parágrafo). Também não parece que o artigo vinculado tenha uma prova disso.
Raphael
Bem, você não pode agrupar mais do que o que está na sequência de entrada, e o número de grupos é fixo em um determinado padrão; portanto, você tem um limite superior (linear) para a memória que um padrão usa. Ainda assim, eu sinto falta de uma prova formal de um PCRE -> linear transformação autômato limitada ...
peppe
Sim, vocês dois estão certos. Eu modifiquei a resposta.
Xodarap 04/04
Veja também perlmonks.org/?node_id=406253 para uma discussão anterior.
András Salamon