¿Son las expresiones regulares un lenguaje de programación?

27

En el sentido académico, ¿las expresiones regulares califican como lenguaje de programación?

La motivación para mi curiosidad es una pregunta SO que acabo de mirar y que preguntó "¿puede regex hacer X?" y me hizo preguntarme qué se puede decir en sentido genérico sobre las posibles soluciones que los utilizan.

Básicamente estoy preguntando, "¿son completas las expresiones regulares de Turing"?

Anodide Aaron
fuente
99
Básicamente, ¿estás preguntando "son expresiones regulares Turing completas"?
FrustratedWithFormsDesigner
Sería genial si alguien elaborara además, pero sí
Aaron Anodide
44
La "son expresiones regulares Turing completa" requiere una comprensión de los tipos de lenguaje y el hierchary Chomsky
55
(1 minuto más tarde que una edición) y si desea seguir ese camino de preguntas y explicaciones, es posible que desee ver el intercambio de teoría cs . El lema de bombeo es la prueba más simple para "un lenguaje normal puede coincidir con ^ nb ^ n" (que es compatible con una máquina de Turing).
1
Creo que está preguntando si puede incluirlo en su currículum en la sección "Lenguajes de programación". La respuesta en ese caso es no. Eso va en la sección "Tecnologías".
Neil

Respuestas:

46

Las expresiones regulares son un tipo particular de gramática formal utilizada para analizar cadenas y otra información textual que se conoce como "lenguas regulares" en la teoría del lenguaje formal. No son un lenguaje de programación como tal. Son más una abreviatura para la codificación que de otro modo sería extremadamente tediosa de implementar e incluso más confusa que la Regex a veces arcana.

Los lenguajes de programación generalmente se definen como lenguajes que están completos en Turing . Dichos lenguajes deben poder procesar cualquier función computable . Regex no encaja en esta categoría.

Si quieres un lenguaje que se parezca a Regex, prueba J.

Ingeniero mundial
fuente
1
+1, busqué pero no pude encontrar una buena discusión / prueba de la integridad de las expresiones regulares de Turing.
FrustratedWithFormsDesigner
1
@ davidk01: los autómatas celulares pueden estar completos (aunque los compiladores buenos son difíciles de encontrar), las expresiones regulares no. Puede hacer cálculos no triviales, sí, pero hay cosas bastante triviales que no puede hacer también. Turing autómatas celulares completos podría considerarse como un lenguaje de programación, ya que, en principio, puede escribir cualquier programa con ellos que podría con cualquier otro lenguaje.
psr
1
También es importante tener en cuenta que la expresión regular que realiza la prueba de primalidad ( montreal.pm.org/tech/neil_kandalgaonkar.shtml#primality_regex ) usa características de expresiones regulares perl que son más poderosas que las "Expresiones regulares" en el sentido académico, es decir, grupos almacenados . Los lenguajes regulares no pueden requerir memoria arbitraria.
Eric W.
55
@WorldEngineer: Hay lenguajes de programación interesantes y útiles que no están completos en Turing. Datalog, SQL y ACL2 son algunos ejemplos que vienen a la mente, así como cualquier número de cálculos lambda fuertemente normalizados utilizados en cosas como los comprobadores de teoremas basados ​​en la teoría de tipos.
Ryan Culpepper
1
No todos los lenguajes de programación están completos. Por ejemplo, los lenguajes declarativos puramente libres de contexto como XML que no se completan sin estar emparejados con un intérprete podrían considerarse lenguajes de programación. Todo depende de su definición de 'lenguaje de programación'. Todo lo que necesita para transformar un lenguaje 'normal' en un lenguaje 'libre de contexto' es una pila pushdown. Entonces son tortugas hasta el fondo.
Evan Plaice
14

Es difícil responder a preguntas del tipo "es X una Y ", si los participantes en el debate del uso de diferentes definiciones de X e Y . Podría ser que para algunas definiciones, la respuesta es "sí", y para algunas definiciones la respuesta es "no". Especialmente si la respuesta depende de detalles técnicos donde las diferentes definiciones difieren. Además, esta discusión contiene información errónea, así que tenga paciencia con una respuesta más larga.

¿Qué queremos decir con " lenguaje de programación "?

Una respuesta simple podría ser "un lenguaje utilizado para crear programas". Claro, pero: ¿qué tipo de programas? ¿Qué pasa con un lenguaje que podría usarse para crear algunos tipos de programas, pero no otros tipos de programas? Aquí hay dos ejemplos específicos para ilustrar los casos extremos:

1) Un lenguaje imaginario llamado M funciona así: si el programa contiene la letra única "m", crea un juego de Buscaminas. Todo lo demás es un error de sintaxis.

Intuitivamente, esto no es lo que queremos decir con "un lenguaje de programación". Pero el departamento de marketing de M podría argumentar que técnicamente cumple con la definición, porque puede usarse para crear un programa. Claro, el compilador hace algunas partes críticas para usted, pero eso es lo que hacen los compiladores, ¿no? Un compilador del lenguaje C también traduce algunas palabras simples en docenas de instrucciones del procesador. El compilador M simplemente va más allá y simplifica aún más su trabajo.

2) Si instala la versión original del famoso Turbo Pascal, puede escribir muchos tipos de programas. Pero no puede escribir un juego que se ejecute en el navegador web, porque la API necesaria simplemente no está allí.

Entonces, ¿qué es exactamente lo que hace de Turbo Pascal un lenguaje de programación, pero M no lo tiene? Simplemente hablando, puedes hacer más en Pascal que en M. Pero imagina que tenemos un M.NET, que crea un juego de Buscaminas que se ejecuta en un navegador web. Así que ahora tenemos algo que Pascal puede hacer y M.NET no, pero también tenemos algo que M.NET puede hacer y Pascal no. ¿Por qué deberíamos considerar importantes las ventajas de Pascal y las ventajas de M.NET irrelevantes?

La respuesta es que puede escribir todo tipo de algoritmos en Pascal, pero no puede escribir algoritmos en M o M.NET. Claro, M compila su comando "m", y C compila su comando "strcmp". Pero puede poner "strcmp" en un contexto más amplio, por ejemplo, comparar dos archivos línea por línea, o leer miles de cadenas y ordenarlas alfabéticamente, o ... bueno, millones de otras cosas. Y es precisamente esta capacidad de usar comandos dados en cualquier algoritmo lo que hace la esencia de un lenguaje de programación.

¿Qué es exactamente un algoritmo y, lo que es más importante, qué es "cualquier algoritmo"? En informática utilizamos las palabras Turing-complete . La idea es que hay un conjunto de lenguajes de computadora, donde cada uno de ellos puede simularlos a todos. Uno de esos idiomas es la máquina de Turing, por eso se les llama así. Pascal está allí, C está allí, Java está allí, Python está allí, Lisp está allí, Smalltalk está allí, incluso XSLT está allí. Nuestros hipotéticos M y M.NET no están allí. Puedes aprender más sobre esto en cualquier universidad que ofrezca un curso de computación decente, pero la idea es que un lenguaje completo de Turing pueda hacer cualquier cosaque otro lenguaje completo de Turing puede hacer, si les das la API mínima necesaria. (Si le das alguna API de navegador web a Pascal, puedes crear todo tipo de juegos en el navegador web. Si le das API de navegador web a M, todavía solo puedes crear Buscaminas.) Podríamos decir metafóricamente que si Si elimina todas las API de un lenguaje de programación, lo importante es lo que queda.

¿Qué queremos decir con " expresiones regulares "?

Diferentes lenguajes de programación los implementan de manera ligeramente diferente. Pero la idea original era que las expresiones regulares expresan los llamados lenguajes regulares . Tenga en cuenta que aquí no hablamos sobre lenguajes de programación, sino sobre lenguajes (pseudo) humanos. Imagine que encuentra una tribu exótica que habla un idioma que consiste solo en palabras "ba", "baba", "bababa", etc. Podría describir este lenguaje verbalmente como "una sílaba 'ba' repetida una o más veces" o utilizando una expresión regular como "(ba) +".

Se supone que las expresiones regulares expresan: "nada", "esta letra", "esto, seguido de eso", "esto o aquello", "esto, repetido una o más veces", y "no esto". - Esa es la definición matemática . Cualquier otra cosa es solo un conveniente acceso directo creado a partir de los componentes anteriores. Por ejemplo, "esto, repetido dos o tres veces" puede traducirse como "esto, seguido de esto, seguido de (esto o nada)", pero podría ser más conveniente escribir "ba {2,3}" que "baba (licenciado en Letras)?".

En la vida real, una implementación típica de "expresiones regulares" implementa más que esto. Por ejemplo, usando la definición matemática, un lenguaje de "aba", "aabaa", "aaabaaa", etc., cualquier número de "a" s, seguido de una "b", seguido del mismo número de "a "s - no es un lenguaje normal. Sin embargo, muchas "expresiones regulares" utilizadas hoy podrían detectarlo, utilizando el concepto adicional de "lo mismo que encontramos antes", escrito como "(a +) b \ 1". Usando este concepto adicional, podemos hacer algunas cosas interesantes, por ejemplo, detectar palabras que consisten en un número primo de letras. Aún así, no podemos hacer ningún algoritmo ... para una explicación de por qué,

Entonces, volviendo al tema original: ¿son las expresiones regulares (definidas como: expresiones que describen lenguajes regulares en la jerarquía de Chomsky; o como: el primero, más la operación \ 1) un lenguaje de programación (definido como: Turing-complete)? La respuesta es no . No, no puede implementar ningún algoritmo utilizando expresiones regulares, y la capacidad de implementar cualquier algoritmo es lo que las personas que estudian informática generalmente entienden como la esencia del lenguaje de programación.

Por supuesto, cualquiera puede cambiar la respuesta insistiendo en una definición diferente . Como escribí al principio, los detalles técnicos son importantes aquí. Si te equivocas, obtienes una respuesta incorrecta.

Y si usted está no interesado en los detalles técnicos, la respuesta podría ser: ¿Se puede utilizar expresiones regulares (y nada más) para hacer un programa? No. Entonces, ¿por qué llamarlo un lenguaje de programación? (Sin embargo, una respuesta como esta se descargó y eliminó aquí, por eso escribí esta versión más larga).

EDITAR: Además, cualquiera puede crear una biblioteca implementando su propia nueva variante de "expresiones regulares" con algunas características nuevas agregadas. En algún momento, las nuevas características pueden ser suficientes para que todo el sistema se complete en Turing. Un ejemplo trivial sería incorporar un lenguaje completo de Turing usando alguna nueva sintaxis; pero también puede suceder menos obviamente. Quizás ya sucedió.

Viliam Búr
fuente
0

En .Net, Regex no solo puede manejar múltiples formas de condicionales, usando diferentes combinaciones de alternancia y lookarounds, sino que también puede manipular su propia pila.

(?xm)
    (?>
        <(?<Tagname>table)[^>]*>
    )
(?(Tagname)
    (
        </(?(?!\k'Tagname')(?<-Tagname>))*\k'Tagname'>(?<-Tagname>)
    |
        (?>
            <(?<Tagname>[a-z][^\s>]*)[^>]*>
        )
    |
        [^<]+
    )+?
    (?(Tagname)(?!))
)

Esto, por ejemplo, es un pequeño fragmento que escribí para recuperar una tabla HTML. A diferencia de otros motores de expresiones regulares, controla la pila de colecciones de captura (push, peek y pop) y puede manejar objetos anidados. Tengo uno más complejo, pero es más bien propietario.

Creo que en este ejemplo, se puede considerar que Regex tiene todos los requisitos básicos de un lenguaje de programación. Tiene variables, memoria en línea, condicionales, entrada y salida, se compila utilizando uno de los múltiples motores de compilación de expresiones regulares (.Net en este caso).

En respuesta al graznido sobreutilizado para (NUNCA) analizar HTML con expresiones regulares, seguí adelante y publiqué una respuesta preescrita que puedo publicar: Análisis HTML

Otro ejemplo (solo una demostración) es el siguiente:

Function Regex("<(td>)((?:[^<]*(?(?!</\1)<))*)</\1")
    Group(0) = "<"
    Group(1) = "td>"
    Group(0) += Group(1)
    Group(2) = LoopMethod()
    Group(0) += Group(2)
    Group(0) += "</" & Group(1)
    Return Group()
End Function

Function LoopMethod()
    retGroup = ""
    Do
        tmpGroup = Everything that is NOT an Opening HTML Delimeter
        If the Text following tmpGroup Does NOT Equal "</" & Group(1) Then
            tmpGroup += "<"
            retGroup += tmpGroup
        Else
            Exit Do
        End If
    Loop
    Return retGroup
End Function

Nuevamente, para los loros HTML: analizar HTML

Esto muestra una expresión regular más simple que realiza bucles y condicionales (¿algoritmos?). Lo único que falta es el cálculo matemático real. Esta es una expresión regular más detallada que simplemente extrae una célula TD más eficientemente que el método típico "(. *?)".

Pero incluso como entusiasta de Regex y maestro autoproclamado, no iría por ahí diciéndole a nadie que Regex es un lenguaje de programación. Mi propio argumento en mi contra es que no puede estar solo, debe ejecutarse a través de su propio motor mientras es compatible con otro motor de lenguaje de programación.

Suamere
fuente
Si "prueba" esto y no funciona, debe darse cuenta de que la mayoría de los "probadores" de motores de expresiones regulares no manejan .Net Regex (grupos de equilibrio). Tendría que usar esto realmente en un programa .Net.
Suamere
3
Oh Dios, esta es evidencia prima facia de por qué nunca deberías usar expresiones regulares para analizar html . Siempre.
Tacroy
@Tacroy Es bueno ver a alguien intervenir para aconsejar sobre loros sobre el análisis de HTML con expresiones regulares. Si bien no es para los débiles de corazón, la combinación de expresiones regulares como la anterior con una pila es una receta básica (y eficiente) para construir un analizador sin contexto.
Evan Plaice
1
En respuesta al Parrot Squawking. He creado esto: Parsing HTML
Suamere
No es una expresión regular si acepta lenguajes sensibles al contexto. Es otro DSL que es un superconjunto de Regex. El nombre del vendedor no cambia eso
Caleth
0

Si bien encontrar / reemplazar en una expresión regular no es un lenguaje de programación completo de Turing, como se explicó en las respuestas anteriores, si permite usar acciones repetidas de reemplazar con expresiones regulares, entonces sí, puede codificar cualquier máquina de Turing usando una expresión regular:

Buscar / reemplazar repetidamente con expresiones regulares es un lenguaje de programación completo de Turing

Como consecuencia, puede calcular cualquier función computable usando la misma búsqueda y reemplazar la expresión regular de javascript una y otra vez.

Para probar la integridad de Turing, es suficiente codificar una máquina de Turing en búsqueda / reemplazo de expresiones regulares. Suponga que el estado del editor es:

0000#12345:01-5:0#0000000

que se puede leer como una cinta de símbolos con un lector:

[left symbols]#[set of states]:[set of symbols]-[current state]:[current symbol]#[right symbols]

Para la regla que lee 0 en el estado 5, escribe 1 y cambia su estado a 3 y se mueve hacia la izquierda, lo abstraemos usando la siguiente notación:

5:0 => 1, 3:[left]

Codificamos la notación anterior en una expresión regular de búsqueda:

(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#

y su expresión de reemplazo (similar a javascript)

#12345:01-$4:$1#$8

Ok, ¿ahora cómo codificar muchas reglas? Utilizamos la concatenación con el oroperador |para la búsqueda de expresiones regulares, y combinamos los resultados en reemplazo, numerando números de grupo con desplazamientos. Por ejemplo, consideremos el conjunto de cuatro reglas.

5:0 => 1, 3:left
3:0 => 1, 5:right
5:1 => 1, 5:right
3:1 => 1: 3:stop

Los codificamos en una búsqueda y reemplazamos la expresión:

Search:
(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#

Replace by:
$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8

Pruébelo en su motor javascript favorito:

function turingstep(s) {
  return s.replace(/(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#/g,"$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8");
}

var tape = "0000#12345:01-5:0#0000000"
for(var i = 0; i < 6; i++) {
  console.log(tape)
  tape = turingstep(tape)
}
Mikaël Mayer
fuente