Expresiones Regulares

1. Expresión Regular

Las expresiones regulares representan patrones de cadena de caracteres. Una expresión regular (r) se encuentra completamente definida mediante el conjunto de cadenas con las que concuerda. A este conjunto se denomina lenguaje generado por la expresión regular y se escribe como L (r). La palabra lenguaje se usa para definir “conjunto de cadenas”. Una expresión regular también contendrá caracteres del alfabeto, pero los caracteres tendrán un significado diferente: en una expresión regular todos los símbolos indican patrones.

1.2. Expresiones Regulares Básicas

Expresiones regulares básicas: Son precisamente los caracteres simples del alfabeto, los cuales se corresponden a sí mismos. Dado cualquier carácter a del alfabeto ∑, indicamos que la expresión regular le corresponde al carácter a escribiendo L(a) = {a}. Para una cadena vacía, es decir, la cadena que no contiene ningún carácter. Utilizaremos el símbolo є (épsilon) para denotar la cadena vacía y se definirá el metasímbolo є (en negritas) estableciendo que L(є) = { є} . Cuando no hay una cadena, es decir cuyo lenguaje sea el conjunto vacío, el cual lo escribiremos { }. Emplearemos para esto el símbolo ф y escribiremos L(ф) = { }. Ahora observemos la diferencia entre { } y {є}: el conjunto { } no contiene ninguna cadena, mientras que el conjunto {є} contiene la cadena simple que no se compone de ningún carácter.

1.3. Operaciones de Expresiones Regulares

Existen tres operaciones básicas en las expresiones regulares: 1) selección entre alternativas, la cual se indica mediante el metacarácter | (barra vertical); 2) concatenación que se indica mediante yuxtaposición (sin un carácter), y 3) repetición o “cerradura” la cual se indica mediante el metacarácter *.

1.4. Selección entre alternativas

Si r y s son expresiones regulares, entonces r I s es una expresión regular que define cualquier cadena que concuerda con r o con s. En términos de lenguajes, el lenguaje de r|s es la unión de los lenguajes de r y s, o L(r|s) = L(r) ᴗ L(s).

Como un ejemplo simple, considere la expresión regular a|b: ésta corresponde tanto al carácter a como al carácter b, es decir, L(a | b) = L(a) ᴗ L(b) = { a ) ᴗ ( b ) = {a, b). Como segundo ejemplo, la expresión regular a | є corresponde tanto al carácter simple a como a la cadena vacía (que no está compuesta por ningún carácter). En otras palabras, L(a | є) = {a, є). La selección se puede extender a más de una alternativa, de manera que, por ejemplo,

L(a | b | c | d) = {a, b, c d). En ocasiones también escribiremos largas secuencias de selecciones con puntos, como en a | b |. . . | z, que corresponde a cualquiera de las letras minúsculas de la a hasta la z.

1.5. Concatenación

La concatenación de dos expresiones regulares r y s se escribe como rs, y corresponde a cualquier cadena que sea la concatenación de dos cadenas, con la primera de ellas correspondiendo a r y la segunda correspondiendo a s. Por ejemplo, la expresión regular ab corresponde sólo a la cadena ab, mientras que la expresión regular (a | b) c corresponde a las cadenas ac y bc. (El uso de los paréntesis como metacaracteres en esta expresión regular se explicará en breve.)

Podemos describir el efecto de la concatenación en términos de lenguajes generados al definir la concatenación de dos conjuntos de cadenas. Dados dos conjuntos de cadenas S1 y S2, el conjunto concatenado de cadenas SlS2 es el conjunto de cadenas de SI complementado con todas las cadenas de S2. Por ejemplo, si S1 = {aa, b) y S2 = {a, bb), entonces S1S2 = {aaa, aabb, ba, bbb). Ahora la operación de concatenación para expresiones regulares se puede definir como sigue: L(rs) = L(r)L(s). De esta manera (utilizando el ejemplo anterior), L((a|b) c) = L(a | b)L(c) = (a, b} {c) = {ac, bc}.

La concatenación también se puede extender a más de dos expresiones regulares: L(r1 r2 . . . rn) = L(r1)L(r2) . . . L(rn) = el conjunto de cadenas formado al concatenar todas las cadenas de cada una de las L(r1), . . . , L(rn).

1.6. Repetición

La operación de repetición de una expresión regular, denominada también en ocasiones cerradura (de Kleene), se escribe r*, donde r es una expresión regular. La expresión

...