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
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.
Respostas:
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).fonte
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.
fonte