UNIDAD 2
EXPRESIONES REGULARES
En esta unidad se describen las expresiones regulares, primero las expresiones regulares con sus operaciones fundamentales: la concatenación, la unión y la cerradura; estas operaciones son suficientes para el estudio de los lenguajes formales y la teoría de máquinas, después las expresiones regulares extendidas que incluyen operaciones adicionales.
2.1 Definición formal.
Las expresiones regulares están formadas por constantes y operadores y denotan conjuntos de palabras llamados conjuntos regulares. Dado un alfabeto finito Σ, se definen las siguientes constantes:
1. (conjunto vacío) ∅ que denota el conjunto ∅
2. (palabra vacía) ε que denota el conjunto {ε}
3. (carácter del alfabeto) a elemento de Σ que denota el conjunto {a}
y las siguientes operaciones:
1. (unión) r|s que denota la unión de R y S, donde R y S son respectivamente los conjuntos denotados por las expresiones r y s.
2. (concatenación) r.s que denota el conjunto { αβ | α en R y β en S }, donde R y S representan respectivamente los conjuntos denotados por las expresiones r y s. Por ejemplo, la expresión "(ab|c)(d|ef)" denota el conjunto {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
3. Cerradura (de Kleene) r* que denota el más pequeño conjunto que extiende a R, contiene ε y está cerrado por concatenación de palabras, donde R es el conjunto denotado por la expresión r. r* es también el conjunto de todas las palabras que pueden construirse por concatenación de cero o más ocurrencias de R. Por ejemplo, "(ab|c)*" contiene las palabras ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", etcétera.
Para reducir al mínimo el número de paréntesis necesarios para escribir una expresión regular, se asume que la cerradura de Kleene es el operador de mayor prioridad, seguido de concatenación y luego la unión de conjuntos. El operador de concatenación suele omitirse. Los paréntesis solo se incluyen para eliminar ambigüedades. Y Por ejemplo, "(ab)c" se escribe igualmente como "abc" y "U(b(c*))" puede escribirse "Ubc*".
Nótese que las expresiones regulares definen lenguajes. Los lenguajes regulares pueden ser usados en la construcción de analizadores léxicos - programas que analizan un texto y extraen los lexemas (o unidades léxicas) que hay en el mismo.
El conjunto de los lenguajes regulares sobre un alfabeto está formado por el lenguaje vacío, los lenguajes unitarios incluido {} y todos los lenguajes obtenidos a partir de la concatenación, unión y cerradura de lenguajes.
Ejemplo de lenguajes regulares:
Expresión Regular Lenguaje Regular
10 L={La cadena de 10}
1 | 0 L={Una cadena de 0 ó una cadena de 1}
1* L={Cualquier cadena de 1’s incluyendo }
(00)* L={Cadenas de 0’s de longitud par, incluyendo }
0*1* L={Cadenas de ninguno o más 0’s concatenadas a cadenas de ninguno o más 1’s}
1(1 | 0)* L={Todas las cadenas sobre el alfabeto {1, 0} que empiecen con 1}
(1 | 0)*00 L={Todas las cadenas sobre el alfabeto {1, 0} que terminen en 00}
(1 | 0)*00(1 | 0)* L={Cualquier combinación de 0’s ó 1’s que contengan al menos dos ceros consecutivos}
Cuando sea necesario distinguir entre una expresión regular r y el lenguaje denotado por la misma, usaremos L(r) para denotar el lenguaje. En cualquier caso, si se afirma que w r, ello equivale a decir que w L(r). Si r y s son expresiones regulares sobre el mismo alfabeto y si L(r)= L(s), entonces se dice que r y s son equivalentes. En el caso de que r y s sean equivalentes se puede escribir r = s. También se puede usar r s en el caso de que L(r) L(s).
2.2 Operaciones.
Para escribir operaciones regulares extendidas, usadas en las aplicaciones, se amplían las operaciones, representadas por símbolos con significado especial (llamados también meta-caracteres). A continuación se listan los principales meta-caracteres y su función en la mayoría de los intérpretes de expresiones regulares.
El Punto "."
El punto es interpretado por el motor de búsqueda como cualquier otro carácter excepto los caracteres que representan un salto de línea, a menos que se le especifique esto al motor de Expresiones Regulares. Por lo tanto si esta opción se deshabilita en el motor de búsqueda que se utilice, el punto le dirá al motor que encuentre cualquier carácter incluyendo los saltos de línea. En la herramienta EditPad Pro esto se hace por medio de la opción "punto corresponde a nueva línea" en las opciones de búsqueda. En .Net Framework se utiliza la opción RegexOptions.Singleline al efectuar la búsqueda o crear la expresión regular.
El punto se utiliza de la siguiente forma: Si se le dice al motor de RegEx que busque "g.t" en la cadena "el gato de piedra en la gótica puerta de getisboro goot" el motor de búsqueda encontrará "gat", "gót" y por último "get". Nótese que el motor de búsqueda no encuentra "goot"; esto es porque el punto representa un solo carácter y únicamente uno. Si es necesario que el motor encuentre también la expresión "goot", será necesario utilizar repeticiones, las cuales se explican más adelante.
Aunque el punto es muy útil para encontrar caracteres que no conocemos, es necesario recordar que corresponde a cualquier carácter y que muchas veces esto no es lo que se requiere. Es muy diferente buscar cualquier carácter que buscar cualquier carácter alfanumérico o cualquier dígito o cualquier no-dígito o cualquier no-alfanumérico. Se debe tomar esto en cuenta antes de utilizar el punto y obtener resultados no deseados.
La barra inversa ""
Se utiliza para "marcar" el siguiente carácter de la expresión de búsqueda de forma que este adquiera un significado especial o deje de tenerlo. O sea, la barra inversa no se utiliza nunca por sí sola, sino en combinación con otros caracteres. Al utilizarlo por ejemplo en combinación con el punto "." este deja de tener su significado normal y empieza a comportarse como un carácter literal.
De la misma forma, cuando se coloca la barra inversa seguida de cualquiera de los caracteres especiales que discutiremos a continuación, estos dejan de tener su significado especial y se convierten en caracteres de búsqueda literal.
Como ya se mencionó con anterioridad, la barra inversa también puede darle significado especial a caracteres que no lo tienen. A continuación hay una lista de algunas de estas combinaciones:
• t - Representa un tabulador.
• r - Representa el "regreso al inicio" o sea el lugar en que la línea vuelve a iniciar.
• n - Representa la "nueva línea" el carácter por medio del cual una línea da inicio. Es necesario recordar que en Windows es necesaria una combinación de rn para comenzar una nueva línea, mientras que en Unix solamente se usa n.
• a - Representa una "campana" o "beep" que se produce al imprimir este carácter.
• e - Representa la tecla "Esc" o "Escape"
• f - Representa un salto de página
• v - Representa un tabulador vertical
• x - Se utiliza para representar caracteres ASCII o ANSI se conoce su código. De esta forma, si se busca el símbolo de derechos de autor y la fuente en la que se busca utiliza el conjunto de caracteres Latin-1 es posible encontrarlo utilizando "xA9".
• u - Se utiliza para representar caracteres Unicode si se conoce su código. "u00A2" representa el símbolo de centavos. No todos los motores de Expresiones Regulares soportan Unicode. El .Net Framework lo hace, pero el EditPad Pro no, por ejemplo.
• d - Representa un dígito del 0 al 9.
• w - Representa cualquier carácter alfanumérico.
• s - Representa un espacio en blanco.
• D - Representa cualquier carácter que no sea un dígito del 0 al 9.
• W - Representa cualquier carácter no alfanumérico.
• S - Representa cualquier carácter que no sea un espacio en blanco.
• A - Representa el inicio de la cadena. No un carácter sino una posición.
• Z - Representa el final de la cadena. No un carácter sino una posición.
• b - Marca el inicio y el final de una palabra.
• B - Marca la posición entre dos caracteres alfanuméricos o dos no-alfanuméricos.
Nota: La utilidad Charmap.exe de Windows permite encontrar los códigos ASCII/ANSI/UNICODE para utilizarlos en Expresiones Regulares.
Los corchetes "[]"
La función de los paréntesis cuadrados en el lenguaje de las expresiones regulares es representar "clases de caracteres", o sea, agrupar caracteres en grupos o clases. Son útiles cuando es necesario buscar uno de un grupo de caracteres. Dentro de los paréntesis cuadrados es posible utilizar el guión "-" para especificar rangos de caracteres. Adicionalmente, los meta-caracteres pierden su significado y se convierten en literales cuando se encuentran dentro de los paréntesis cuadrados. Por ejemplo, "d" nos es útil para buscar cualquier carácter que represente un dígito. Sin embargo esta denominación no incluye el punto "." que divide la parte decimal de un número. Para buscar cualquier carácter que representa un dígito o un punto puede utilizarse la expresión regular "[d.]". Como se hizo notar anteriormente, dentro de los paréntesis cuadrados, el punto representa un carácter literal y no un meta-caracter, por lo que no es necesario antecederlo con la barra inversa. El único carácter que es necesario anteceder con la barra inversa dentro de los paréntesis cuadrados es la propia barra inversa. La expresión regular "[dA-Fa-f]" permite encontrar dígitos hexadecimales. Los paréntesis cuadrados permiten también encontrar palabras aún si están escritas de forma errónea, por ejemplo, la expresión regular "expresi[oó]n" permite encontrar en un texto al palabra "expresión" aunque se haya escrito con o sin acento. Es necesario aclarar que sin importar cuantos caracteres se introduzcan dentro del grupo por medio de los paréntesis cuadrados, el grupo solo le dice al motor de búsqueda que encuentre un solo carácter a la vez, o sea, que "expresi[oó]n" no encontrará "expresioon" o "expresioón".
La barra "|"
Nos sirve para indicar una de varias opciones. Por ejemplo, la expresión regular "a|e" encontrará cualquier "a" o "e" dentro del texto. La expresión regular "este|oeste|norte|sur" permitirá encontrar cualquiera de los nombres de los puntos cardinales. La barra se utiliza comúnmente en conjunto con otros caracteres especiales.
El signo de dólar "$"
Representa el final de la cadena de caracteres o el final de la línea, si se utiliza el modo multi-línea. No representa un caracter en especial sino una posición. Si se utiliza la expresión regular ".$" el motor encontrará todos los lugares donde un punto finalice la línea, lo que es útil para avanzar entre párrafos.
EXPRESIONES REGULARES
En esta unidad se describen las expresiones regulares, primero las expresiones regulares con sus operaciones fundamentales: la concatenación, la unión y la cerradura; estas operaciones son suficientes para el estudio de los lenguajes formales y la teoría de máquinas, después las expresiones regulares extendidas que incluyen operaciones adicionales.
2.1 Definición formal.
Las expresiones regulares están formadas por constantes y operadores y denotan conjuntos de palabras llamados conjuntos regulares. Dado un alfabeto finito Σ, se definen las siguientes constantes:
1. (conjunto vacío) ∅ que denota el conjunto ∅
2. (palabra vacía) ε que denota el conjunto {ε}
3. (carácter del alfabeto) a elemento de Σ que denota el conjunto {a}
y las siguientes operaciones:
1. (unión) r|s que denota la unión de R y S, donde R y S son respectivamente los conjuntos denotados por las expresiones r y s.
2. (concatenación) r.s que denota el conjunto { αβ | α en R y β en S }, donde R y S representan respectivamente los conjuntos denotados por las expresiones r y s. Por ejemplo, la expresión "(ab|c)(d|ef)" denota el conjunto {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
3. Cerradura (de Kleene) r* que denota el más pequeño conjunto que extiende a R, contiene ε y está cerrado por concatenación de palabras, donde R es el conjunto denotado por la expresión r. r* es también el conjunto de todas las palabras que pueden construirse por concatenación de cero o más ocurrencias de R. Por ejemplo, "(ab|c)*" contiene las palabras ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", etcétera.
Para reducir al mínimo el número de paréntesis necesarios para escribir una expresión regular, se asume que la cerradura de Kleene es el operador de mayor prioridad, seguido de concatenación y luego la unión de conjuntos. El operador de concatenación suele omitirse. Los paréntesis solo se incluyen para eliminar ambigüedades. Y Por ejemplo, "(ab)c" se escribe igualmente como "abc" y "U(b(c*))" puede escribirse "Ubc*".
Nótese que las expresiones regulares definen lenguajes. Los lenguajes regulares pueden ser usados en la construcción de analizadores léxicos - programas que analizan un texto y extraen los lexemas (o unidades léxicas) que hay en el mismo.
El conjunto de los lenguajes regulares sobre un alfabeto está formado por el lenguaje vacío, los lenguajes unitarios incluido {} y todos los lenguajes obtenidos a partir de la concatenación, unión y cerradura de lenguajes.
Ejemplo de lenguajes regulares:
Expresión Regular Lenguaje Regular
10 L={La cadena de 10}
1 | 0 L={Una cadena de 0 ó una cadena de 1}
1* L={Cualquier cadena de 1’s incluyendo }
(00)* L={Cadenas de 0’s de longitud par, incluyendo }
0*1* L={Cadenas de ninguno o más 0’s concatenadas a cadenas de ninguno o más 1’s}
1(1 | 0)* L={Todas las cadenas sobre el alfabeto {1, 0} que empiecen con 1}
(1 | 0)*00 L={Todas las cadenas sobre el alfabeto {1, 0} que terminen en 00}
(1 | 0)*00(1 | 0)* L={Cualquier combinación de 0’s ó 1’s que contengan al menos dos ceros consecutivos}
Cuando sea necesario distinguir entre una expresión regular r y el lenguaje denotado por la misma, usaremos L(r) para denotar el lenguaje. En cualquier caso, si se afirma que w r, ello equivale a decir que w L(r). Si r y s son expresiones regulares sobre el mismo alfabeto y si L(r)= L(s), entonces se dice que r y s son equivalentes. En el caso de que r y s sean equivalentes se puede escribir r = s. También se puede usar r s en el caso de que L(r) L(s).
2.2 Operaciones.
Para escribir operaciones regulares extendidas, usadas en las aplicaciones, se amplían las operaciones, representadas por símbolos con significado especial (llamados también meta-caracteres). A continuación se listan los principales meta-caracteres y su función en la mayoría de los intérpretes de expresiones regulares.
El Punto "."
El punto es interpretado por el motor de búsqueda como cualquier otro carácter excepto los caracteres que representan un salto de línea, a menos que se le especifique esto al motor de Expresiones Regulares. Por lo tanto si esta opción se deshabilita en el motor de búsqueda que se utilice, el punto le dirá al motor que encuentre cualquier carácter incluyendo los saltos de línea. En la herramienta EditPad Pro esto se hace por medio de la opción "punto corresponde a nueva línea" en las opciones de búsqueda. En .Net Framework se utiliza la opción RegexOptions.Singleline al efectuar la búsqueda o crear la expresión regular.
El punto se utiliza de la siguiente forma: Si se le dice al motor de RegEx que busque "g.t" en la cadena "el gato de piedra en la gótica puerta de getisboro goot" el motor de búsqueda encontrará "gat", "gót" y por último "get". Nótese que el motor de búsqueda no encuentra "goot"; esto es porque el punto representa un solo carácter y únicamente uno. Si es necesario que el motor encuentre también la expresión "goot", será necesario utilizar repeticiones, las cuales se explican más adelante.
Aunque el punto es muy útil para encontrar caracteres que no conocemos, es necesario recordar que corresponde a cualquier carácter y que muchas veces esto no es lo que se requiere. Es muy diferente buscar cualquier carácter que buscar cualquier carácter alfanumérico o cualquier dígito o cualquier no-dígito o cualquier no-alfanumérico. Se debe tomar esto en cuenta antes de utilizar el punto y obtener resultados no deseados.
La barra inversa ""
Se utiliza para "marcar" el siguiente carácter de la expresión de búsqueda de forma que este adquiera un significado especial o deje de tenerlo. O sea, la barra inversa no se utiliza nunca por sí sola, sino en combinación con otros caracteres. Al utilizarlo por ejemplo en combinación con el punto "." este deja de tener su significado normal y empieza a comportarse como un carácter literal.
De la misma forma, cuando se coloca la barra inversa seguida de cualquiera de los caracteres especiales que discutiremos a continuación, estos dejan de tener su significado especial y se convierten en caracteres de búsqueda literal.
Como ya se mencionó con anterioridad, la barra inversa también puede darle significado especial a caracteres que no lo tienen. A continuación hay una lista de algunas de estas combinaciones:
• t - Representa un tabulador.
• r - Representa el "regreso al inicio" o sea el lugar en que la línea vuelve a iniciar.
• n - Representa la "nueva línea" el carácter por medio del cual una línea da inicio. Es necesario recordar que en Windows es necesaria una combinación de rn para comenzar una nueva línea, mientras que en Unix solamente se usa n.
• a - Representa una "campana" o "beep" que se produce al imprimir este carácter.
• e - Representa la tecla "Esc" o "Escape"
• f - Representa un salto de página
• v - Representa un tabulador vertical
• x - Se utiliza para representar caracteres ASCII o ANSI se conoce su código. De esta forma, si se busca el símbolo de derechos de autor y la fuente en la que se busca utiliza el conjunto de caracteres Latin-1 es posible encontrarlo utilizando "xA9".
• u - Se utiliza para representar caracteres Unicode si se conoce su código. "u00A2" representa el símbolo de centavos. No todos los motores de Expresiones Regulares soportan Unicode. El .Net Framework lo hace, pero el EditPad Pro no, por ejemplo.
• d - Representa un dígito del 0 al 9.
• w - Representa cualquier carácter alfanumérico.
• s - Representa un espacio en blanco.
• D - Representa cualquier carácter que no sea un dígito del 0 al 9.
• W - Representa cualquier carácter no alfanumérico.
• S - Representa cualquier carácter que no sea un espacio en blanco.
• A - Representa el inicio de la cadena. No un carácter sino una posición.
• Z - Representa el final de la cadena. No un carácter sino una posición.
• b - Marca el inicio y el final de una palabra.
• B - Marca la posición entre dos caracteres alfanuméricos o dos no-alfanuméricos.
Nota: La utilidad Charmap.exe de Windows permite encontrar los códigos ASCII/ANSI/UNICODE para utilizarlos en Expresiones Regulares.
Los corchetes "[]"
La función de los paréntesis cuadrados en el lenguaje de las expresiones regulares es representar "clases de caracteres", o sea, agrupar caracteres en grupos o clases. Son útiles cuando es necesario buscar uno de un grupo de caracteres. Dentro de los paréntesis cuadrados es posible utilizar el guión "-" para especificar rangos de caracteres. Adicionalmente, los meta-caracteres pierden su significado y se convierten en literales cuando se encuentran dentro de los paréntesis cuadrados. Por ejemplo, "d" nos es útil para buscar cualquier carácter que represente un dígito. Sin embargo esta denominación no incluye el punto "." que divide la parte decimal de un número. Para buscar cualquier carácter que representa un dígito o un punto puede utilizarse la expresión regular "[d.]". Como se hizo notar anteriormente, dentro de los paréntesis cuadrados, el punto representa un carácter literal y no un meta-caracter, por lo que no es necesario antecederlo con la barra inversa. El único carácter que es necesario anteceder con la barra inversa dentro de los paréntesis cuadrados es la propia barra inversa. La expresión regular "[dA-Fa-f]" permite encontrar dígitos hexadecimales. Los paréntesis cuadrados permiten también encontrar palabras aún si están escritas de forma errónea, por ejemplo, la expresión regular "expresi[oó]n" permite encontrar en un texto al palabra "expresión" aunque se haya escrito con o sin acento. Es necesario aclarar que sin importar cuantos caracteres se introduzcan dentro del grupo por medio de los paréntesis cuadrados, el grupo solo le dice al motor de búsqueda que encuentre un solo carácter a la vez, o sea, que "expresi[oó]n" no encontrará "expresioon" o "expresioón".
La barra "|"
Nos sirve para indicar una de varias opciones. Por ejemplo, la expresión regular "a|e" encontrará cualquier "a" o "e" dentro del texto. La expresión regular "este|oeste|norte|sur" permitirá encontrar cualquiera de los nombres de los puntos cardinales. La barra se utiliza comúnmente en conjunto con otros caracteres especiales.
El signo de dólar "$"
Representa el final de la cadena de caracteres o el final de la línea, si se utiliza el modo multi-línea. No representa un caracter en especial sino una posición. Si se utiliza la expresión regular ".$" el motor encontrará todos los lugares donde un punto finalice la línea, lo que es útil para avanzar entre párrafos.