¿Qué idiomas reconocen las expresiones regulares compatibles con Perl?

23

Como dice el título, pasé un par de horas el fin de semana pasado tratando de aclarar mi mente sobre la clase de idiomas que coinciden con las expresiones regulares compatibles con Perl, excluyendo cualquier operador coincidente que permita ejecutar código arbitrario dentro del patrón .

Si no sabe qué son los PCRE, lea esto y esto .

El problema es que los recursos disponibles en Internet prácticamente se detienen en lenguajes libres de contexto, y los PCRE pueden coincidir más que esos (ver más abajo); pero realmente no sé dónde encontrar más teoremas o documentos sobre este tipo de cosas.

En particular: los PCRE son obviamente un superconjunto de lenguajes regulares (ya que la sintaxis PCRE tiene todos los operadores de lenguaje regular).

Cualquier CFG se puede poner en forma normal de Greibach, lo que elimina la recursión izquierda. Creo que esto se puede usar por medio de (?(DEFINE)...)grupos para "traducir" la gramática en subrutinas coincidentes, evitando ahogarse en la recursión izquierda, traduciendo:

  • el no terminal a la cabeza de cada producción se convierte en una subrutina (?<HEAD>...)
  • el cuerpo de cada producción se coloca en la subrutina; los terminales se dejan como están, los no terminales se convierten en invocaciones de procedimiento (es decir (?&NONTERMINAL));
  • todas las producciones con el mismo no terminal que la cabeza se agrupan por medio del |operador (más la agrupación adicional con (?:...), si es necesario)
  • el patrón se convierte en un (?(DEFINE)...)grupo que contiene todas las producciones "traducidas", y una invocación para el procedimiento del símbolo de inicio, para que coincida con la cadena completa, es decir^(?(DEFINE)...)(?&START)$

Esto debería tratar con cualquier CFG. Por lo tanto, los PCRE deberían poder coincidir con cualquier CFL.

Hay más: tomemos el lenguaje simple es decir, el lenguaje de las cadenas se repite dos veces. Este lenguaje no es una CFL: el lema de bombeo para las CFL falla. (Preste especial atención a que | v x w |p debe mantenerse, por lo tanto, no puede simplemente bombear el principio o el final de las dos cadenas repetidas).

L={wwEl |wΛ}
El |vXwEl |pags

Sin embargo, este lenguaje es fácilmente igualada por un PCRE: ^(.*)\1$. Por lo tanto, estamos estrictamente por encima de las CFL.

¿Cuánto más arriba? Bueno, como dije, no tengo idea. No pude encontrar ningún recurso sobre CSL o todas las otras clases intermedias para decidirme. ¿Algún experto dispuesto a discutir esto?

Anexo: Me pidieron que especificara exactamente qué subconjunto de la sintaxis PCRE debe permitirse. Como escribí al comienzo de la publicación, quería excluir cualquier operador que permita ejecutar código arbitrario dentro del patrón, como ??{}.

Por el bien del argumento, creo que podemos seguir con la sintaxis definida por la página del comando man pcresyntax (3) , que es un subconjunto razonable de lo que ofrece Perl 5.10-5.12, menos las llamadas (ya que no están dentro del patrón). No estoy seguro de que agregar o quitar verbos de control de retroceso cambie el idioma que podemos reconocer; Si es así, sería bueno averiguar con qué clases tenemos y sin ellas.

Peppe
fuente
2
Incluya su definición elegida de PCRE en su pregunta, ya que ha cambiado entre versiones. Las expresiones regulares reales de Perl pueden contener código arbitrario de Perl, lo que las hace completas para Turing.
Gilles 'SO- deja de ser malvado'
Agregué una nota al final, espero que aclare este punto.
Peppe

Respuestas:

7

También he encontrado esta publicación de blog extremadamente interesante http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html . Proporciona la misma prueba que di antes sobre el hecho de que regexps reconoce las CFL (reescribiendo la gramática a través de DEFINEbloques) e incluso algunas CSL (como el lenguaje de cadenas repetidas); se basa en eso y continúa, dando una prueba de que las expresiones regulares con referencias posteriores son NP-hard (reduciendo 3-SAT a una expresión regular).

Peppe
fuente
2
Cuando el autor dice "NP-complete" deberían decir "NP-hard". No proporcionan pruebas de que la clase de lenguajes PCRE esté contenida en NP.
András Salamon
Es cierto, también se observa en los comentarios.
Peppe
5

Deciden como máximo los lenguajes sensibles al contexto (que, como usted señala, es un superconjunto de los lenguajes libres de contexto). Ver esta publicación de monjes perl .

La idea básica es que la "memoria" de la máquina es el número de grupos de captura, que está limitado linealmente.

Xodarap
fuente
55
El argumento que da en el segundo párrafo explica por qué PCRE no puede aceptar más que CS, pero no por qué esta inclusión es exacta (lo que sugiere en su primer párrafo). Tampoco parece que el artículo vinculado haya dado prueba de ello.
Raphael
Bueno, no puede agrupar más de lo que hay en la cadena de entrada, y el número de grupos se fija en un patrón determinado, por lo que tiene un límite superior (lineal) para la memoria que utiliza un patrón. Aún así, echo de menos una prueba formal de una PCRE -> transformación de autómata acotada lineal ...
peppe
Sí, ustedes dos tienen razón. He modificado la respuesta.
Xodarap
Vea también perlmonks.org/?node_id=406253 para una discusión anterior.
András Salamon