Comer cerezas rojas te da la posibilidad de comer fantasmas azules. La idea de que las derivadas se pueden usar para crear un algoritmo de comparación de expresiones regulares es casi igual de ridícula. Permítanme explicar cómo funciona este algoritmo y cómo se relaciona con Pac-Man.

En 1964, Brzozowski publicó el primer artículo sobre Derivadas de expresiones regulares . Este es, con mucho, uno de mis algoritmos favoritos. Usando derivados de expresiones regulares, podemos implementar un algoritmo para hacer coincidencias de expresiones regulares. Este algoritmo es muy:

• simple
• funcional
• fácilmente extensible con sus propios operadores

En este artículo, le mostraré cómo podemos hacer coincidir una cadena con una expresión regular usando solo dos funciones puras y algunas analogías de Pac-Man. Si lo prefiere, puede ver el siguiente video en lugar de leer el artículo, ya que cubre el mismo material:

Resumen de expresiones regulares

Primero, hagamos una revisión rápida de las expresiones regulares para asegurarnos de que estamos en la misma página. La expresión a(a|b)*coincide con una cadena que comienza con a, seguida de cualquier número de a's y b's.

• La cadena abcoincidirá a(a|b)*. Indicaremos esto con un fantasma azul comestible.
• La cadena aabbbatambién coincide a(a|b)*, ya que comienza con un ay seguido de varios a's y b's.
• A continuación, la cadena acno coincide a(a|b)*, ya que la expresión regular no coincide con ninguna cy nuestra expresión regular no coincide con ninguna subcadena. Lo indicaremos con un fantasma rojo que persigue al Pac-Man.
• Finalmente, la cadena batampoco coincide a(a|b)*porque no comienza con un a.

Descripción general del algoritmo

Antes de profundizar en los detalles, veamos una descripción general de cómo funciona este algoritmo. He ideado un extraño juego de Pac-Man en el que solo puedes comer los fantasmas si comes la fruta en una secuencia que coincida con la expresión regular. Nuestro Pac-Man representa la expresión regular aba*. Tiene la siguiente cadena de frutas para comer: una manzana, luego un plátano y luego una manzana: aba.

1. Cuando empezamos, el fantasma nos persigue, y la expresión regular que nos queda por emparejar es aba*.
2. Nos comemos la primera manzana, y la expresión regular que ahora nos queda por emparejar es ba*. El fantasma todavía nos persigue ya que la fruta que hemos comido hasta ahora, la manzana, no coincide con la expresión regular.
3. A continuación, comemos el plátano. La expresión regular que nos queda para hacer coincidir es a*. Ahora el fantasma empieza a salir corriendo porque, técnicamente, abya coincide aba*.
4. Podemos intentar comernos el fantasma o comernos otra manzana, en cuyo caso la expresión regular que nos queda por igualar es todavía a*. El fantasma sigue huyendo ya que abatambién coincide con la expresión regular aba*.

Hay una función más en el trabajo aquí. La función verifica si el fantasma está persiguiendo al Pac-Man o si el Pac-Man ya ha coincidido con la expresión regular y está persiguiendo al fantasma. Esta función se denomina función anulable; comprueba si la expresión regular que queda para coincidir coincide con la cadena vacía. Puede hacerlo porque si la expresión regular que queda para coincidir coincide con la cadena vacía, la fruta que ha comido ya debe haber sido suficiente para satisfacer la expresión regular.

Algoritmo de coincidencia de derivadas

Eso significa que solo necesitamos dos funciones para escribir el algoritmo de coincidencia derivada:

1. la función derivada
2. la función anulable

Uno en Golang para los programadores imperativos:

y otro en Haskell para programadores funcionales:

Estas dos funciones son equivalentes y solo están escritas en diferentes estilos de programación. En el código de Haskell, el foldltambién llamado doblar a la izquierda o reducir en otros lenguajes, hace el trabajo del bucle for por ti. Además, en Haskell, no necesitamos comas para pasar parámetros a funciones; Dado que la aplicación de funciones es la operación más común en un lenguaje de programación funcional, usamos espacios para delimitar parámetros.

Ahora, profundicemos en cómo implementar las funciones anulables y derivadas.

Digresión de la historia de Pac-Man Origin

Pero antes de hacer eso, no sé si alguna vez te has preguntado sobre la historia del origen de Pac-Man. Sostengo que no hubo un barril de desechos nucleares en el que cayó Pac-Man, lo que resultó en que Pac-Man obtuviera el poder de comer fantasmas. La lógica es mucho más simple.

¡Pac-Man es una fruta! Cuando Pac-Man come otras frutas, Pac-Man está siendo un caníbal. Entonces, si alguna vez te persigue un fantasma, debes comer algo de carne humana, y el fantasma debería, al menos temporalmente, comenzar a huir de ti. Ahora, no lo he intentado yo mismo, pero la lógica parece sólida.

Esto explica por qué los zombis siempre persiguen a los humanos. Como dijo una vez David Attenborough:

“Los zombis que nos persiguen, ellos mismos están siendo perseguidos por fantasmas que no podemos ver. Después de que los zombis coman algo de nuestra carne humana, los verás exhibiendo el extraño comportamiento de masticar el aire, este es el zombi devorando al fantasma que lo perseguía antes”.

Operadores básicos

La implementación de las funciones anulables y derivadas requiere que primero definamos los operadores básicos disponibles en nuestras expresiones regulares.

Podemos pensar en una expresión regular como una descripción de un conjunto de cadenas.

• Esto significa que el conjunto vacío representa un operador que no coincide con cadenas.
• La cadena vacía representa un conjunto singleton de una sola cadena que solo coincide con la cadena vacía.
• El carácter también representa un conjunto único que solo coincide con el carácter único a.
• Luego podemos combinar estas expresiones regulares base usando operadores como: or, concatenationy Kleene star, donde ry srepresenta las dos expresiones regulares que estamos combinando.

Función anulable

Podemos comenzar con la función anulable. Veamos algunos ejemplos y averigüemos cuál de estas expresiones regulares coincide con la cadena vacía para obtener una idea de cómo se implementa esta función.

• a*coincide con la cadena vacía ya que cero o más incluye cero.
• (a*|b)coincide con la cadena vacía ya que el lado izquierdo de o coincide con la cadena vacía.
• abno coincide con la cadena vacía, ya que solo coincide con la cadenaab
• ab*tampoco coincide con la cadena vacía, ya ab*que requiere una cadena que comience con una
• (a|b)no coincide con la cadena vacía, ya que ni el lado izquierdo ni el derecho orcoinciden con la cadena vacía.

Aquí está la implementación de la función anulable. El lado izquierdo representa los valores que se pasan a la función y el lado derecho representa la implementación de la función en ese caso. Los fantasmas rojos representan lo falso y los fantasmas azules representan lo verdadero:

• El conjunto vacío no coincide con la cadena vacía ya que no coincide con ninguna cadena.
• La cadena vacía coincide con la cadena vacía porque solo coincide con la cadena vacía.
• El carácter ano coincide con la cadena vacía porque solo coincide con el carácter a.
• Si tenemos un lógico or, tenemos que verificar ambos lados. Si alguno coincide con la cadena vacía, entonces el lógico orcoincide con la cadena vacía.
• Para concatenationque dos expresiones regulares coincidan con la cadena vacía, ambas deben coincidir con la cadena vacía.
• Y finalmente, si tenemos zero or morealgo, entonces eso incluye cero, lo que significa que siempre coincide con la cadena vacía.

1. Nuestro operador principal es el oresto significa que tenemos que verificar la nulabilidad de los lados izquierdo y derecho: by a*.
2. Verificamos y vemos que el carácter ben el lado izquierdo no es anulable: false.
3. Luego verificamos y vemos que a*en el lado derecho es anulable: true.
4. Ahora regresamos falsey truepodemos que orellos lo consigan true.

Ejercicios anulables

Intente recorrer la implementación y verifique si las siguientes expresiones regulares son anulables. Puede hacer clic en ellos para comprobar su respuesta:

1. a
2. a*(b*|∅)
3. εa
4. ∅*
5. (∅|b)*(abc|ε)

Antes de ver la implementación de la función, veamos ejemplos de una derivada. Aquí vamos a tomar la derivada de algunas expresiones regulares, todas con respecto al carácter a:

• La expresión regular que queda por emparejar después de a*haber comido una amanzana es todavía a*.
• La derivada de ab*con respecto a aes b*, ya que hemos emparejado el prefijo a.
• La derivada de (a|b)bcon respecto a aes b.
• La derivada de b|(a*b)con respecto a aes a*b. El izquierdo bno coincidía, así que pudimos tirarlo y afue consumido por el zero or more ade la derecha.
• A continuación, tenemos ab*, este es un poco complicado. Después de que se come la manzana, la expresión regular que queda por emparejar es b(ab)*. Dado que solo hemos emparejado el a, esperamos ver al menos uno más b.

• La derivada del conjunto vacío es siempre el conjunto vacío. No hay forma de recuperar ya que el conjunto vacío no coincide con nada.
• La derivada de la cadena vacía relativa a cualquier carácter es el conjunto vacío. No esperaba coincidir con un personaje. Solo coincidirá con la cadena vacía.
• La derivada de un solo carácter a un carácter similar (en este caso, el apple) es la cadena vacía, ya que después de que se haya emparejado, todo lo que queda por coincidir es la cadena vacía.
• La derivada de un carácter con respecto a otro carácter diferente que no es igual, en este caso el banana, es el conjunto vacío ya que no hemos emparejado el carácter específico.
• La derivada de una orexpresión es la orde las derivadas. Simplemente empuja el problema a sus hijos.
• La derivada de la concatexpresión tiene que considerar si puede saltarse la primera expresión. Solo puede omitir la primera expresión si la primera expresión coincide con la cadena vacía y admite valores NULL. Así que lo primero que hacemos es comprobar esto. Pensemos en el caso en el que no se puede omitir la primera expresión cuando la expresión rno admite valores NULL. Entonces la derivada es la derivada de la primera expresión concatenatedcon la segunda expresión s. Si podemos omitir la primera expresión regular, debemos considerar una alternativa que sea solo la derivada de la segunda expresión. Entonces podemos orlas dos alternativas de saltear ry no saltar ry devolver eso como resultado.
• Finalmente, tenemos el staroperador. Coincide con una expresión cero o más veces. Dado que se nos está pasando un carácter, este no es el caso cero. Así que tenemos que considerar el one or morecaso. Esto significa que tenemos que tomar la derivada de la expresión dentro de stary concatenatenuevamente con la zero or moreexpresión.

Derivado ejemplo 1

Vamos a sacar la derivada de (ab)*con respecto a a.

(ab)*es una zero or moreexpresión, así que buscamos la zero or moreregla. Vemos que esto requiere tomar la derivada de la expresión dentro de star.

Este es el concatenationde ay b. Entonces verificamos si el lado izquierdo es anulable y el carácter ano es anulable. Esto significa que no podemos pasarlo por alto. Tenemos que sacar la derivada de acon respecto a a. Pero esa es la cadena vacía, así que si tenemos concatenatela cadena vacía con el lado derecho, que era b, obtenemos b.

Ahora, recurrimos a zero or more, recuerde que tomamos la derivada de abcon respecto a ay obtuvimos a b. Ahora podemos concatenar eso con (ab)*otra vez y obtenemos b(ab)*.

Derivada ejemplo 2

Vamos a sacar la derivada de (a*ba)con respecto a b.

• a*se concatena con ba, por lo que echamos un vistazo a la regla de concatenación.
• Verificamos si el lado izquierdo a*es anulable, lo cual es. Esto significa que podemos omitirlo, lo que también significa que tenemos que crear una orde dos derivadas.
• El lado izquierdo termina por no coincidir, ya a*que no coincide b.
• Por suerte tenemos una alternativa el ba. La derivada de bacon respecto a bes y a.

Me he saltado algunos detalles aquí. Considéralo un ejercicio para comprobar mi trabajo recorriendo la función tú mismo.

Ejercicios de derivadas

Intente recorrer la implementación y verifique cuáles son las derivadas de las siguientes expresiones regulares con respecto a b. Puede hacer clic en ellos para comprobar su respuesta:

1. εb
2. b*(b|c)
3. a*(b|c)
4. bεb
5. ∅*b

Espero que ahora entiendas por qué comer cerezas rojas te da la capacidad de comer fantasmas azules y cómo implementar un comparador de expresiones regulares usando el algoritmo derivado.

Hemos cubierto el algoritmo de trabajo básico aquí, pero hay muchas maneras de hacer que este algoritmo sea aún mejor con ajustes muy pequeños. Hicimos trampa y pasamos por alto las reglas de simplificación en esta publicación, usándolas sin explicarlas, lo que se volverá especialmente obvio si recorre los ejercicios. Tampoco hemos discutido cómo puede usar la memoización para construir un autómata eficiente de forma perezosa.

También podemos extender fácilmente el algoritmo para incluir nuevos operadores como, note interleaveincluso admitir gramáticas libres de contexto. Discutiré algunos de estos temas en el próximo artículo .

Mientras tanto, me encantaría ver su implementación de este algoritmo en un lenguaje de programación con el que se sienta más cómodo. Por favor envíeme un enlace en los comentarios.

Gracias

• Brink van der Merwe por tomarse el tiempo de explicarme este algoritmo.

• Brzozowski, Janusz A. "Derivados de expresiones regulares". Revista de la ACM (JACM) 11.4 (1964): 481–494.
• Owens, Scott, John Reppy y Aaron Turon. "Derivados de expresiones regulares reexaminados". Revista de programación funcional 19.2 (2009): 173–190.