Unidad II. Expresiones Regulares

2.1 DEFINICIÓN FORMAL DE UNA ER

Una expresión regular es una forma abreviada de representar cadenas de caracteres que se ajustan a un determinado patrón. Al conjunto de cadenas representado por la expresión r se lo llama lenguaje generado por la expresión regular r y se escribe L (r).

Una expresión regular se define sobre un alfabeto Σ y es una cadena formada por caracteres de dicho alfabeto y por una serie de operadores también llamados metacaracteres.

Las expresiones regulares básicas se definen de la siguiente forma:

1. El símbolo Φ (conjunto vacío) es una expresión regular y L (Φ) = {}

2. El símbolo λ (palabra vacía) es una expresión regular y L (λ) = {λ}

3. Cualquier símbolo a ∈  Σ es una expresión regular y L (a) = {a}

A partir de estas expresiones regulares básicas pueden construirse expresiones regulares más complejas aplicando las siguientes operaciones:

• Concatenación (se representa con el metacarácter .)

Si r y s son expresiones regulares, entonces r.s también es una expresión regular y L(r.s)=L(r).L(s).
El operador . puede omitirse de modo que rs también representa la concatenación. La concatenación de dos lenguajes L₁ y L₂ se obtiene concatenando cada cadena de L₁ con todas las cadenas de L₂.

Por ejemplo:
si L₁={00,1} y  L₂={11,0,10}
Entonces:
L₁L₂={0011,000,0010,111,10,110}

• Unión (se representa con el metacarácter |)

Si r y s son expresiones regulares, entonces r|stambién es una expresión regular y L(r|s)=L(r)∪ L(s).

Por ejemplo, el lenguaje generado por la expresión regular:

ab|c es L(ab|c)={ab,c}.

• Cierre o Clausura (se representa con el metacarácter *)

Si r es una expresión regular, entonces r* también es una expresión regular y L(r*)=L(r)*. La operación de cierre aplicada a un lenguaje L se define así:

donde Lⁱ es igual a la concatenación de L consigo mismo i veces y L⁰=λ.
Por ejemplo, el lenguaje generado por la expresión regular a*ba* es:
L(a*ba*)={b,ab,ba,aba,aab,...}, es decir, el lenguaje formado por todas las cadenas de a’s y b’s que contienen una única b.

Cuando aparecen varias operaciones en una expresión regular, el orden de precedencia es el siguiente: cierre, concatenación y unión. Este orden puede modificarse mediante el uso de paréntesis. (Alfonseca, 2006)

2.2 DISEÑO DE ER

El analizador léxico debe analizar e identificar sólo un conjunto finito de cadena válida/token/lexeme que pertenecen al lenguaje de la mano. Busca el modelo definido por las normas del lenguaje.

Las expresiones regulares tienen la capacidad de expresar finito idiomas definiendo un modelo finito de cadenas de símbolos. La gramática definida por las expresiones regulares es conocida como gramática regular. El idioma definido por gramática regular se conoce como idioma habitual.

Las diferentes operaciones sobre los idiomas disponibles son:

ANOTACIONES

Si r y s son expresiones regulares denotando las lenguas L(r) y L(s), a continuación:

• Unión: (r)|(s) es una expresión regular que denota L(r) U L(s)
• Concatenación: (r)(s) es una expresión regular que denota L(r)L(s)
• Cierre Kleene: (r)* es una expresión regular que denota (L(r))*
• (r): es una expresión regular que denota L(r)

PRECEDENCIA Y ASOCIATIVIDAD

• *, La concatenación (.), y | (pipe) son asociativo
• * Tiene la mayor prioridad
• La concatenación (.) tiene la segunda mayor prioridad.
• | (Pipe) tiene la menor prioridad de todos.

2.3 APLICACIONES EN PROBLEMAS REALES

Una de las principales aplicaciones de los hermanos Deitel, son las expresiones regulares que facilitan la construcción de un compilador. A menudo se utiliza una expresión regular larga y compleja para validar la sintaxis de un programa. Si el código del programa no concuerda con la expresión regular, el compilador sabe que hay un error de sintaxis dentro del código.

Generalmente convierten la expresión regular a un autómata finito no determinista y después construyen el autómata finito determinista.

Otra aplicación del mismo libro es en los editores de texto. También encontramos a las expresiones regulares en la biología molecular. También hay esfuerzos importantes para tratar de representar cadenas como generadas por expresiones regulares o por lenguajes regulares.

BIBLIOGRAFÌAS

Tema 2.1:
Alfonseca, M. (2006). Compiladores e Intérpretes: Teoría y Práctica. Madrid: Pearson Educación.
Investigado por: Arilenne Hernández Plascencia
Tema 2.2:

AHO, A. V. (2008). COMPILADORES. PRINCIPIOS, TÉCNICAS Y HERRAMIENTAS. Segunda edición. Mexico: Pearson Educación.

Investigado por: Jonathan Hernández Antonio y Araceli Martinez Martinez

Tema 2.3:

AHO, A. V. (2008). COMPILADORES. PRINCIPIOS, TÉCNICAS Y HERRAMIENTAS. Segunda edición. Mexico: Pearson Educación.

Investigado por: Germán David Hernández Gomez y Carlos Martínez Valentin