Expresiones regulares PDF

Preview

Summary

Download Expresiones regulares PDF

Description

Expresiones regulares

Lenguajes Formales y Computabilidad

Expresiones regulares Hemos visto que los lenguajes son un conjunto finito o infinito de sentencias. Los lenguajes de programación con un número de sentencias finitos se pueden especificar exhaustivamente enumerando todas sus sentencias. No obstante, para los lenguajes con un número de sentencias infinito, esta tarea se hace imposible, pues los medios para describirlos son limitados. La manera habitual de describir un lenguaje es mediante su gramática, pero debemos considerar que las gramáticas que se utilizan en los lenguajes de programación necesitan de una modelización matemática que haga factible su implementación en los compiladores. Noam Chomsky (ver el apartado “Gramáticas de Chomsky” de la Lectura 2 de este módulo) logró grandes avances en la concepción de un modelo matemático de las gramáticas al conectarlos con los lenguajes naturales. Esto permitió descubrir una relación entre la teoría de las máquinas abstractas y la de los lenguajes formales, facilitando no solo la comprensión y la descripción formal de los lenguajes, sino también el desarrollo de los correspondientes compiladores para la programación de computadoras que por ese tiempo estaban surgiendo. Se originan así los metalenguajes, que son herramientas que sirven para describir formalmente a los lenguajes y no solo facilitan la comprensión de estos, sino también el desarrollo del compilador correspondiente. Un ejemplo de metalenguaje son las expresiones regulares que describen los componentes léxicos (o tokens) de un lenguaje. Estas expresiones son utilizadas en los sistemas que tienen que ver con el procesamiento y con el reconocimiento de cadenas, por ejemplo: 1. Muchos comandos de búsqueda, como sed o grep de Unix (Linux) y sus equivalentes para la búsqueda de cadena (tokens) que se ven en los navegadores web o en los sistemas de formato de texto. Estos utilizan una notación de expresión regular, como patrones que describen lo que el usuario desea encontrar en un archivo de texto. 2. Las expresiones o descripciones regulares definen, casi siempre, la forma de especificar los tokens de modo que sean reconocidos por los analizadores léxicos de los compiladores en los lenguajes de 2

programación. Tomando estas expresiones regulares como entrada, los analizadores léxicos pueden ser programados a mano o generados automáticamente, realizando tareas muy concretas de la gestión de símbolos. El módulo de lectura de un programa y el analizador léxico son los únicos elementos de un compilador que necesitan trabajar con el texto del programa al completo (ver Grune, Bal, Jacob y Langendoen, 2007). En la Figura 1 se muestra la estructura conceptual de un compilador.

Figura 1: Estructura conceptual de un compilador

Fuente: Grune et al., 2007, p. 11.

Una expresión regular es una fórmula que describe un posible conjunto infinito de cadenas. Estas pueden ser entendidas como un patrón para seleccionar o buscar cadenas dentro de un lenguaje1 o también como una forma de describir un lenguaje.

1

Habitualmente, a las expresiones regulares las utilizamos cuando buscamos ciertas ocurrencias en los editores de texto más comunes.

3

Por ejemplo: la expresión 𝑎𝑏∗ puede emplearse para buscar un texto que consiste en un carácter 𝑎 seguido por cero o más caracteres 𝑏. Esta expresión genera un conjunto infinito {𝑎, 𝑎𝑏, 𝑎𝑏𝑏, 𝑎𝑏𝑏𝑏…}. Cuando se tiene una cadena que puede ser generada por una expresión regular dada decimos que la expresión regular selecciona produce una coincidencia para la cadena.

Operadores de expresiones regulares Las expresiones regulares denotan lenguajes. Por ejemplo, la expresión regular 01∗+ 10∗ indica que el lenguaje consiste en todas las cadenas formadas por un solo 0 seguido por cualquier número de 1 o de un solo 1 seguido de cualquier número de 0. Por el momento es imposible interpretar completamente las expresiones regulares y, antes de describir su notación, es oportuno recordar tres operaciones posibles de realizar con los lenguajes, dos de ellas ya han sido vistas: 1. La unión de los lenguajes A y B, definida como 𝐴 ∪ 𝐵 = {𝑥|𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵}. 2. La concatenación de los lenguajes A y B, definida como AB = {ab|a ∈ A ∧ b ∈ B}. 3. El cierre de Kleene2 de un lenguaje L, denotado como 𝐿∗ , representa el conjunto de las cadenas que se pueden formar mediante la adopción de cualquier número de estas a partir de L, posiblemente con repeticiones y concatenaciones. Por ejemplo, si L = {0, 1}, entonces 𝐿∗ son todas las cadenas de 0 y 1. Formalmente, 𝐿∗ es la unión infinita ∪i≥0 Li, donde 𝐿0 = {ϵ}, L1 = L. Asimismo, Li para i > 1 es LLL…L (es decir, la concatenación de i copias de L). Otros autores representan el cierre de Kleene de un lenguaje L como 𝐿∗ = {ϵ} ∪ L ∪ L ∪ L ∪ L… El Kleene star (operador de Kleene o cierre de Kleene) es una operación unaria en un conjunto de símbolos o caracteres. La aplicación del operador a un conjunto V se escribe como 𝑉 ∗. Este es ampliamente utilizado para las

2

El cierre de Kleene (closure, star or Kleene closure, operador) fue introducido por Stephen Cole Kleene, quien originó la notación de expresiones regulares y el operador de este (Stephen Cole Kleene, s. f.).

4

expresiones regulares, que es el contexto en el que fue introducido por Kleene para caracterizar algunos autómatas. • Si V es un conjunto de cadenas, entonces 𝑉 ∗ se define como el menor superconjunto de V que contiene 𝜆 (cadena vacía) y es cerrado bajo la operación de concatenación de cadenas. Este sistema también se describe como el conjunto de las cadenas que se forman a partir de la concatenación de cero o más cadenas de V. • Si V es un conjunto de símbolos o caracteres, entonces 𝑉 ∗ es el conjunto de todas las cadenas sobre los símbolos (o caracteres) pertenecientes a V, incluyendo 𝜆. Construcción de expresiones regulares Todas las algebras comienzan con expresiones elementales, probablemente con constantes y variables. Luego, mediante la aplicación de un determinado conjunto de operadores (con sus métodos de agrupación y los operandos), podemos construir más expresiones y agregar otras previamente construidas. Por ejemplo, el álgebra aritmética comienza con constantes como números enteros y reales, agrega luego las variables y se basa en expresiones más complejas con operadores aritméticos como la suma y la multiplicación. El álgebra de las expresiones regulares sigue este patrón, con constantes y variables que denotan el lenguaje, y los operadores de las tres operaciones comentadas anteriormente (unión, concatenación y operador de Kleene). Se puede ahora describir la expresión regular recursivamente. Para la expresión regular E, se define el lenguaje que representa y es denotada como L (E)3. Una expresión regular consiste de tres partes: 1. La constante {𝜖} y ∅, respectivamente, o sea, (𝜖) y (∅) = ∅. 2. Si a es cualquier símbolo, entonces a es una expresión regular. Esta

3

Los autores Hopcroft y Ullman (2007) indican que es solo la expresión regular y el lenguaje que ella denota es L(E).

5

expresión denota el lenguaje {a}. Es decir L(a) = {a}. Los autores Hopcroft y Ullman (2007) resaltan la letra en negrita para indicar una expresión que corresponde a un símbolo. 3. Una variable, usualmente en mayúscula e itálica, como L, que denota cualquier lenguaje. Por ejemplo: consideremos la expresión: (0 ∪ 1) 01∗ El lenguaje descripto por esta expresión es el conjunto de todas las cadenas binarias:  que comienzan con 0 o 1 (esto lo indica (0 ∪ 1));  el segundo símbolo es 0 (esto lo indica 0);  finaliza con cero o más 1 (esto lo indica 01∗). Con lo que resulta, el lenguaje descripto por esta expresión es {00, 001, 0011, . . . , 10, 101, … . ,1011, 10111}.

6

Operadores y patrones La Tabla 1 muestra los componentes de las expresiones regulares y se pueden ver los patrones básicos y los operadores. Tabla 1: Componentes de las expresiones regulares []

Fuente: Grune et al., 2007, p. 53.

7

Referencias Bluedorn, H. (s. f.). Two methods of reasoning. Recuperado http://www.triviumpursuit.com/articles/two_methods_of_reasoning.php

de

Chomsky, N. (1959). On certain formal properties of grammars. Information and Control, 2(1), 137-167. Recuperado de https://www.sciencedirect.com/science/article/pii/S0019995859903626 Cubero, E., Moreno, M. y Salomón, R. (2007). Teoría de autómatas y lenguajes formales. Durán Jacobo, M. Lenguaje formal. En Autor, Introducción a los lenguajes formales. Recuperado de http://www.libros.publicaciones.ipn.mx/PDF/1338.pdf Función matemática. (s. f). En Wikipedia. Recuperado http://es.wikipedia.org/wiki/Funci%C3%B3n_matem%C3%A1tica

de

Grune, D., Bal, H. E., Jacob C. J. H. y Langendoen, K. G. (2007). Diseño de compiladores modernos. McGraw Hill. Hopcroft, J. y Ullman, J. (1993). Introducción a la teoría de autómatas, lenguajes y computación (1.a ed.). Hopcroft, J. & Ullman, J. (2001). Introduction to automata theory, languages and computation (2nd ed.). Hopcroft, J. & Ullman, J. (2007). Introduction to automata theory, languages and computation (3rd ed.). Hopcroft, J. y Ullman, J. (2008). Teoría de autómatas, lenguajes y computación (3.a ed.). Lenguaje formal. (s. f.). En Wikipedia. http://es.wikipedia.org/wiki/Lenguaje_formal

Recuperado

de

Lógica proposicional. (s. f.). En Wikipedia. http://es.wikipedia.org/wiki/L%C3%B3gica_proposicional

Recuperado

de

8

Miller, J. (s. f.). Earliest uses of various mathematical symbols. Recuperado de http://jeff560.tripod.com/mathsym.html Moisl, H. Computational linguistics. dehttp://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture1.htm

Recuperado

RapidTables.com. (s. f.). Set theory symbols. Recuperado http://www.rapidtables.com/math/symbols/Set_Symbols.htm

de

Símbolos matemáticos. (s. f.). En Wikipedia. Recuperado http://es.wikipedia.org/wiki/Anexo:S%C3%ADmbolos_matem%C3 %A1ticos Stephen Cole Kleene. (s. f.). En Wikipedia. Recuperado https://en.wikipedia.org/wiki/Stephen_Cole_Kleene

de

Trochim, W. (2006). Deduction & induction. http://www.socialresearchmethods.net/kb/dedind.php

Recuperado

de

de

Uszkoreit, H. (s. f.). What is computational linguistics? Recuperado de http://www.coli.uni-saarland.de/~hansu/what_is_cl.html

9...