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).
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.
Respuestas:
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).fuente
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.
fuente