Expresiones Regulares
Curso de Compiladores
Preparado por
Manuel E. Bermúdez, Ph.D.
Associate Professor
University of Florida
Expresiones Regulares
• Una descripción compacta y fácil de leer de un
lenguaje regular.
• Usamos operadores para denotar constructores
de lenguajes, y construir lenguajes complejos a
partir de lenguajes “atómicos” sencillos.
Expresiones Regulares
Definición: Una expresión regular sobre un alfabeto Σ se
define recursivamente:
1.
2.
3.
4.
5.
6.
ø denota el lenguaje ø
ε denota el lenguaje {ε}
a denota el lenguaje {a}, para todo a  Σ.
(P + Q) denota L(P) U L(Q), donde P, Q son e.r.’s.
(PQ) denota L(P)·L(Q), donde P, Q son e.r.’s.
P* denota L(P)*, donde P is una e.r.
Para evitar paréntesis excesivos, asumimos asociatividad
izquierda, con la siguiente precedencia (de mayor
prioridad a menor prioridad): *, ·, +
Expresiones Regulares
Ejemplos:
(O + 1)*: una hilera de O’s y 1’s.
(O + 1)*1: una hilera de O’s y 1’s, que termina en 1.
1*O1*: una hilera de 1’s con un O insertado.
Letter (Letter + Digit)*: un identificador.
Digit Digit*: un entero.
Quote Char* Quote: una hilera. †
# Char* Eoln: un comentario. †
{Char*}: otro comentario. †
† Assumiendo que Char no contiene ‘Quote’,
eoln, o ‘}’ .
Expresiones Regulares
Conversión de gramática lineal derecha a expresión
regular
Ejemplo:
S → aS
→ bR
→ε
R → aS
¿ Qué significa S → aS ?
L(S)  {a}·L(S)
S → bR significa L(S)  {b}·L(R)
S → ε significa L(S) {ε}
Expresiones Regulares
Juntas (las tres opciones de S) significan que
L(S) = {a}·L(S) + {b}·L(R) + {ε}
o bien, S = aS + bR + ε
Similarmente, R → aS significa que R = aS.
Entonces, S = aS + bR + ε
R = aS
Sistema de ecuaciones simultáneas, en la cual las
variables son los no-terminals.
Expresiones Regulares
Solución del sistema de ecuaciones simultáneas.
S = aS + bR + ε
R = aS
Sustituimos R = aS:
S = aS + baS + ε
= (a + ba) S + ε
Pregunta: ¿ Qué hacemos con ecuaciones de la
forma
X = X + β ?
Expresiones Regulares
Respuesta: β  L(x), así que
αβ  L(x),
ααβ  L(x),
αααβ  L(x), …
y entonces, α*β = L(x).
En nuestro caso,
S = (a + ba) S + ε
= (a + ba)* ε
= (a + ba)*
Expresiones Regulares
Algoritmo 5:
Gramática Lineal Derecha → Expresión Regular
1. A = α1 + α2 + … + αn
si A → α1
→ α2
.
.
.
→ αn
Expresiones Regulares
2. Si la ecuación es de la forma X = α, donde X no
aparece in α, se reemplaza toda ocurrencia de X
con α en todas las demás ecuaciones, y se
elimina la ecuación X = α.
Si la ecuación es de la forma X = αX + β, donde
X no occurre en α o en β, se reemplaza la
ecuación con X = α*β.
Nota: Se puede necesitar manipulación algebraica
para obtener la forma X = αX + β.
Importante: La concatenación no es conmutativa!!
Expresiones Regulares
Ejemplo:
S→a
→ bU
→ bR
R → abaU
→U
U → aS
→b
S = a + bU + bR
R = abaU + U = (aba + ε) U
U = aS + b
Sustituimos R:
S = a + bU + b(aba + ε) U
U = aS + b
Expresiones Regulares
Sustituimos U:
S = a + b(aS + b) + b(aba + ε)(aS + b)
= a + baS + bb + babaaS + babab + baS + bb
repetidas
= (ba + babaa)S + (a + bb + babab)
Y entonces,
S = (ba + babaa)*(a + bb + babab)
Lenguajes Regulares
Resumiendo:
Listo
RGR
RGL
Algoritmos 1,2 Algoritmos 3,4
Pronto
DFA
Mínimo
Algoritmo 5
RE
NFA
DFA
Expresiones Regulares
Algoritmo 6 (Versión 1):
Expresión Regular → FSA (Autómata Finito
no-determinístico)
Se construye el FSA recursivamente, según la
estructura de la expresión regular. Cada FSA
tiene un estado inicial, y uno final.
Conversiones:

1
2
para ø
Expresiones Regulares
1
•
1
•
ε
•
ó
a
2
P
para a
ε
1
para P + Q
2
ε
•
para ε
P
ε
Q
ε
Q
ε
1
P
ε
Q
ε
2
para P· Q
Expresiones Regulares

1
ε
ε
ε
P
2
para P*
ε
Ejemplo: (b (aba + ε) a)*
1
3
5
b
a
b
2
(b (aba + ε) a)*
4
(b (aba + ε) a)*
6
(b (aba + ε) a)*
Expresiones Regulares
7
10
3
a
4
a
a
ε
5
8
8
(b (aba + ε) a)*
9
(b (aba + ε) a)*
11
(b (aba + ε) a)*
b
6
ε
a
7
(b (aba + ε) a)*
Expresiones Regulares
ε
3 a
4
ε
9 ε
13
ε
b
5
6
ε
12
ε
b
2
8
7
a
1
(b (aba + ε) a)*
ε
ε
3
a
9
ε
4
ε
13
ε
5
b
12
ε
(b (aba + ε) a)*
8
a
6
ε
7
Expresiones Regulares
b
2
1
(b (aba + ε) a) *
ε
ε
3
a
9
ε
4
ε
13
ε
5
b
12
ε
11
a
10
ε
8
a
6
ε
7
Expresiones Regulares
(b (aba + ε) a)*
14 ε
b
2
ε
ε
ε
ε
15
1
12 ε
3
a
ε
ε
11
9
a
10
4
ε
ε
13 ε
5
8
a
7
ε
6
Expresiones Regulares
Algoritmo 6 (Versión 2):
Expresión Regular → FSA (Autómata Finito
no-determinístico)
Punto de inicio:
E
Expresiones Regulares
Reglas de conversión:
a
a*
ε
ε
ab
a
b
a
a+b
b
Expresiones Regulares
Algoritmo 6 versión 1:
• Construye FSA de abajo hacia arriba
• Bueno para máquinas
• Malo para seres humanos
Algoritmo 6 versión 2:
• Construye FSA de arriba hacia abajo
• Malo para máquinas
• Bueno para seres humanos
Expresiones Regulares
Ejemplo (Versión 2):
(a + b)* (aa + bb)
(a + b)*
aa + bb
ε
aa
ε
bb
ε
a+b
a
b
ε
a
a
b
b
Expresiones Regulares
Ejemplo (Versión 2):
ba(a + b)* ab
a
b
a
ε
ε
b
a
b
Lenguajes Regulares
Resumiendo:
Listo
RGR
RGL
Algoritmos 1,2 Algoritmos 3,4
Pronto
DFA
Mínimo
Algoritmo 5
RE
Algoritmo 6
NFA
DFA
Autómatas de Estado Finito
Determinísticos (DFA’s)
Definición: Un FSA determinístico se define igual
que uno no-determinístico, excepto que
δ: Q x Σ → Q, en lugar de
δ: Q x Σ U {ε} → 2Q
Así,
ε
y
a
a
son impossibles.
Autómatas de Estado Finito
Determinísticos (DFA’s)
Cada transición de un DFA consume un símbolo.
Afortunadamente, los DFA’s tiene el mismo poder
(de reconocimiento) que los NFA’s.
Teorema: Para cada NFA existe un DFA equivalente
(i.e. que acepta el mismo lenguaje).
Autómatas de Estado Finito
Determinísticos (DFA’s)
Algoritmo 7: Conversión de NFA a DFA:
• Se “simulan” las transiciones del NFA, con el DFA.
• El estado inicial del DFA es el estado inicial del NFA
(digamos, S), junto con todos los estados
alcanzables (con ε) desde S.
• Cada estado del DFA es un subconjunto de los
estados del NFA.
• Estados nuevos en el DFA se construyen calculando
el conjunto de estados alcanzables desde estados
del NFA, para cada símbolo.
• Los estados finales del DFA son los que contienen al
menos un estado final del NFA.
Autómatas de Estado Finito
Determinísticos (DFA’s)
Ejemplo:
ε
a*b + ba*
a
ε
2
3
b
a
1
b
4
ε
5
6
ε
NFA
Autómatas de Estado Finito
Determinísticos (DFA’s) a
Entrada
Estado
123
23
456
6
56
a
23
23
56
--56
DFA:
b
456
6
------a
123 b
ε
ε
4
3 b
a ε 6
5
b
6
2
ε
1 b
a
23
a
456
56
a
Autómatas de Estado Finito
Determinísticos (DFA’s)
En general, si el NFA tiene N estados, el DFA puede
tener hasta 2N estados.
ε
Ejemplo: ba (a + b)* ab
0
b
1
a
2
ε
ε
a
4
5
ε
8
3
ε
6
NFA
ε
7
b
ε
ε
11
b
10
a
9
ε
b
0
ε
a
1
2
NFA
ε
3
4
ε
5
8
ε
6
11
Estado
0
1
234689
34568910
346789
34678911
a
a
--234689
34568910
34568910
34568910
34568910
b
ε
b
7
ε
ε
a
10
9
b
1
--346789
34678911
346789
346789
Autómatas de Estado Finito
Determinísticos (DFA’s)
DFA
0
b
1
a
a
a
34568910
b
a
346789
234689
b
b
a
34678911
b
Lenguajes Regulares
Resumiendo:
Listo
RGR
RGL
Algoritmos 1,2 Algoritmos 3,4
Pronto
DFA
Mínimo
Algoritmo 5
RE
Algoritmo 6
NFA
Algoritmo 7
DFA
Minimización de Estados
Teorema: Dado un DFA M, existe un DFA M’
equivalente que es mínimo, i.e. no existe
ningún otro DFA equivalente con menos estados
que M’.
Definición: Una partición de un conjunto S es un
conjunto de subconjuntos de S, tal que cada
elemento de S aparece en uno (y solo uno) de
esos subconjuntos.
Minimización de Estados
Ejemplo:
S = {1, 2, 3, 4, 5}
Π1 = { {1, 2, 3, 4}, {5} }
Π2 = { {1, 2, 3,}, {4}, {5} }
Π3 = { {1, 3}, {2}, {4}, {5} }
Nota: Π2 es un refinamiento de Π1 , y Π3 es un
refinamiento de Π2.
Minimización de Estados
Algorithmo 8 (Minimización de un DFA):
1. Eliminar las transiciones indefinidas introduciendo
el estado TRAMPA, desde el cual no se llega un
estado final.
2. Particionar los estados en dos grupos (finales y nofinales).
3. Completar la tabla de estados, especificando las
transiciones de cada grupo a otros.
Refinar la partición: se desprenden los grupos con
transiciones distintas.
4. Repetir el paso 3 hasta no haber más
refinamientos.
5. Determinar los estados finales.
Minimización de Estados
a
Ejemplo:
a
1
Π0 = { {1, 2, 3, 4}, {5} }
Estado
1
2
3
4
5
a
1234
1234
1234
1234
1234
b
2
a
a
b
b
1234
1234
1234
5
1234
4
3
b
b
a
5
b
Se desprende {4}
de la partición
{1,2,3,4}
Minimización de Estados
Π1 = { {1, 2, 3}, {4}, {5} }
a
1
Estado
1
2
3
4
5
a
123
123
123
123
123
b
123
4
123
5
123
a
b
2
4
a
a
b
3
Se desprende {2} de la partición {1,2,3}
b
b
a
5
Minimización de Estados
a
2
a
Π2 = { {1, 3}, {2}, {4}, {5} }
1
b
4
a
a
b
Estado
1
3
2
4
5
a
2
2
2
2
2
b
13
13
4
5
13
a
b
3
b
5
b
13
b
5
a
a
b
No más refinamientos
DFA Mínimo
a
2
a
b
4
Lenguajes Regulares
Resumiendo:
RGR
RGL
Algoritmos 1,2 Algoritmos 3,4
Algoritmo 8
Algoritmo 5
RE
DFA
Mínimo
Algoritmo 6
Listo !
NFA
Algoritmo 7
DFA
Resumen de Lenguajes Regulares
• La clase más pequeña de la jerarquía de
Chomsky.
• Apropiada para el análisis léxico.
• Cuatro representaciones: RGR, RGL, ER y FSA.
• Las cuatro son equivalentes (algoritmos de
transformación).
• Diversas ventajas y desventajas entre las
cuatro representaciones, para el diseñador, el
implementador, y el usuario de un lenguaje.
• Los FSA se pueden hacer determinísticos y
mínimos.
Descargar

www.cise.ufl.edu