Expresiones regulares y lenguajes de programación, definición formal de las expresiones regulares, equivalencias útiles entre expresiones regulares.
Expresiones regulares y lenguajes de programación
Los componentes básicos de un LP –los identificadores, las palabras reservadas, las constantes, los operadores, los símbolos de puntuación– constituyen diferentes LRs. Como tales, los podremos representar mediante ERs.
Ejemplo 48
Sea un LP 1 en el que identificador es una secuencia de letras y dígitos que comienza con letra.
Supongamos que L representa a cualquiera de las letras y D representa a cualquiera de los dígitos.
Entonces, el LR infinito identificador puede representarse mediante la ER L (L+D)*.
Ejemplo 49
Sea un LP 2 en el que constante real es una secuencia de dígitos (por lo menos uno), seguido de un punto, seguido, no obligatoriamente, de una secuencia de dígitos.
Entonces, el LR infinito constante real puede representarse mediante la ER D+ . D*.
Ejemplo 50
Sea un LP 3 que solo tiene tres PALABRAS RESERVADAS: if, else y while.
Entonces, este LR finito puede representarse mediante la ER if+else+while.
Definición formal de las expresiones regulares
Las ERs se construyen utilizando los operadores básicos unión (+), concatenación (·) y clausura de Kleene (*), y se definen formalmente de la siguiente manera recursiva:
Ø es una ER que representa al LR vacío (sin palabras)
ε es una ER que representa al LR que solo contiene la palabra vacía: {ε}
Todo símbolo x de un alfabeto corresponde a una ER x que representa a un LR que solo tiene una palabra con ese símbolo x. Ejemplo: Si ∑ = {a, b}, entonces a es una ER que representa al LR {a} y b es una ER que representa al LR {b}.
Una cadena s es una ER s que representa a un LR que solo contiene la palabra s. Ejemplo: dada la cadena abc, la ER abc representa al LR {abc}.
Si R1 y R2 son ERs, entonces R1 + R2 es una ER. Ejemplo: si R1 = a y R2 = ε, entonces a+ε es una ER
Si R1 y R2 son ERs, entonces R1 • R2 (o, simplemente, R1R2) es una ER. Ejemplo: si R1 = a y R2 = b, entonces ab es una ER.
Si R1 es una ER, entonces R1* es una ER. Ejemplo: si R1 = a, entonces a* es una ER.
Si R1 es una ER, entonces (R1) es una ER. Ejemplo: si R1 = a, entonces (a) es una ER. A los tres operadores básicos descriptos para construir ERs, agregamos, como ya hemos visto, dos operadores que simplifican sensiblemente la escritura de algunas ERs. Ellos son: el operador clausura positiva y el operador potencia, los cuales ya hemos definido oportunamente. En consecuencia:
Si R1 es una ER, entonces R1+ es una ER. Ejemplo: si R1 = a, entonces a+ es una ER.
Si R1 es una ER, entonces R1n (con n ≥ 0 y entero) es una ER. Ejemplo: si R1 = a, entonces a216 es una ER.
Con respecto a la precedencia de los operadores, ya se ha informado que:
Los operadores “clausura de Kleene”, “clausura positiva” y “potencia” tienen prioridad máxima
El operador “concatenación” tiene prioridad media
El operador “unión” tiene prioridad mínima
Equivalencias útiles entre expresiones regulares
En esta sección se conocerán algunas equivalencias que existen entre diferentes ERs y que pueden ser empleadas para simplificar la escritura de ciertas expresiones complejas. Esta es una sección ardua de leer, pero puede resultar de mucha utilidad en más de una ocasión.
Sugerencia: recorra las equivalencias presentadas, siguiendo su lectura con algunos ejemplos propios y sencillos, y luego utilice esta sección como “material de referencia”.
Sean R1, R2 y R3 Expresiones Regulares; entonces:
R1 + R2 = R2 + R1, porque el operador “unión” es conmutativo
(R1 + R2) + R3 = R1 + (R2 + R3) = R1 + R2 + R3
(R1 R2) R3 = R1 (R2 R3) = R1 R2 R3
R1 R2 + R1 R3 = R1 (R2 + R3) (simplificación por ”concatenación” a izquierda)
R1 R3 + R2 R3 = (R1 + R2) R3 (simplificación por ”concatenación” a derecha)
A continuación se agregan algunas equivalencias que corresponden a las ERUs, las que serán ejemplificadas sobre un alfabeto particular. Sea el alfabeto ∑ = {a, b}; entonces, el LU sobre este alfabeto está representado por la ER (a+b)*,y se verifican las siguientes equivalencias:
