Upload
noamirodriguez
View
237
Download
1
Embed Size (px)
Citation preview
8/19/2019 Clase Compiladores
1/48
EXPRESIONES REGULARES
1
8/19/2019 Clase Compiladores
2/48
DEFINICIONES BÁSICAS
Alfabeto: conjunto no vacío de símbolos. Es usualutilizar Σ para denotar un alfabeto.Ejemplos:
Palabra o cadena: es una secuencia de símbolos delalfabeto, es decir, s = a1a2...an, donde ai ∈ Σ.
Por lo general se utilizan las primeras letras del
alfabeto, a, b, c, d , e, para denotar símbolos delalfabeto las !ltimas letras, s, t, u, v , w , x , y , z , paradenotar palabras.
2
8/19/2019 Clase Compiladores
3/48
DEFINICIONES BÁSICAS
"ongitud de una palabra: es el n!mero desímbolos en s. #e denota por $s$.
Palabra nula o vacía λ: es la palabra de longitudcero. Algunos autores utilizan ε para denotarla.
%oncatenaci&n: si s = a1a2...an t = b1b2...bn,entoncesst = a1a2...anb1b2...bn' s2 = ss' s( = sss. "a
concatenaci&n es asociativa, es decir, s)tu* = )st*u,pero no es conmutativa.
3
8/19/2019 Clase Compiladores
4/48
EJEMPLO #ean dos palabras + e tales ue + - )/*,
- )/*
4
#e llama concatenaci&n de las palabras + e a otra palabra z
z= + = a10.aib10.bj
8/19/2019 Clase Compiladores
5/48
EJEMPLO "a concatenaci&n debe cumplir:
5
E+istencia de elemento neutro
+ = +λ = x
#e comprueba ue es un monoide )semigrupo conelemento neutro*
8/19/2019 Clase Compiladores
6/48
EJEMPLO o es conmutativa: si +=abc, =ad, se
verifica ue:+ = abcad
+= adabc
6
"ongitud de la palabra
+ = + 3
8/19/2019 Clase Compiladores
7/48
...DEFINICIONES BÁSICAS
4ado un alfabeto Σ, definimos: Σ5 = 6 x $ x es una palabra sobre Σ $ x $ = 57
Ejemplo: Σ = 68, 17Σ8 =6λ7Σ1 =68, 17Σ2 =688, 81, 18, 117Σ( =6888, 881, 818, 811, 188, 181, 118, 1117...
Σ9 = Σ8∪ Σ1∪ Σ2∪ Σ(∪... es el conjunto de todas laspalabras ue pueden ser formadas con letras del alfabetoΣ, incluendo a λ. A Σ9 se le llama la Cerradura de Kleenede Σ.
Σ3 = Σ1∪ Σ2∪ Σ(∪... es el conjunto de todas las palabrasno-vacías ue pueden ser formadas con letras de Σ, esdecir, Σ3 = Σ9 − 6λ7.
Ejercicio en clase: #ea Σ = 6a, b, c7. btener Σ8, Σ1, Σ2
Σ(. 7
8/19/2019 Clase Compiladores
8/48
DEFINICIÓN RECURSIVA DE *
;ase: λ ∈ Σ9
Paso recursivo: si w ∈ Σ9 a ∈ Σ, entonceswa ∈ Σ9.
%erradura: w pertenece a Σ9
s&lo si puede serobtenida a partir de λ mediante un n!merofinito de aplicaciones del paso recursivo.
ota: definiciones recursivas son una buena
8/19/2019 Clase Compiladores
9/48
LENGUAJES
"enguaje sobre un alfabeto Σ es un conjunto finito o infinitode palabras sobre Σ, es decir, es un subconjunto de Σ9.
"enguajes interesantes no consisten de conjuntosarbitrarios de cadenas sino de cadenas ue cumplenciertas condiciones las cuales definen la sinta+is dellenguaje.
n lenguaje finito puede ser definido por e+tensi&n, amenos ue sea >demasiado e+tenso?.
"enguajes infinitos con reuerimientos sint@cticos simples
pueden definirse recursivamente.
9
8/19/2019 Clase Compiladores
10/48
EJEMPLOS
"enguaje L sobre Σ =68, 17 ue consta de cadenas ue terminan en 1;ase: 1 ∈ LPaso recursivo: si u ∈ L a ∈ Σ, entonces au ∈ L.%erradura: una cadena u pertenece a L s&lo si puede ser obtenida a partir del
elemento base mediante un n!mero finito de aplicaciones del paso recursivo.
"enguaje L sobre Σ =6a, b7 ue consta de cadenas ue inician con a tienen longitud par;ase: aa, ab ∈ LPaso recursivo: si u ∈ L, entonces uaa, uab, uba, ubb ∈ L.%erradura: una cadena u pertenece a L s&lo si puede ser obtenida a partir de
los elementos base mediante un n!mero finito de aplicaciones del pasorecursivo.
10
8/19/2019 Clase Compiladores
11/48
... EJEMPLOS "enguaje L sobre Σ =6a, b7 ue consta de
cadenas en las ue cada ocurrencia de b es inmediatamente precedida por una a.
Por ejemploλ
, a, abaab est@n en " perono así bb, bab, abb.;ase: λ ∈ LPaso recursivo: si u ∈ L, entonces ua uab ∈
".%erradura: una cadena u pertenece a L s&lo si
puede ser obtenida a partir de los elementosbase mediante un n!mero finito deaplicaciones del paso recursivo.
11
8/19/2019 Clase Compiladores
12/48
…EJEMPLOS
#ea L el lenguaje sobre el alfabeto Σ = 68, 17definido recursivamente por
1. λ ∈ L
2. #i u ∈ L entonces 8u 8u1 ∈ L.
(. %ualuier elemento en L puede ser obtenido apartir de la regla 1. utilizando la regla 2. unn!mero finito de veces.
4efina L por intenci&n.
12
L = {0m 1n | m n 0
8/19/2019 Clase Compiladores
13/48
8/19/2019 Clase Compiladores
14/48
…EJEMPLOS
4efina recursivamente al lenguaje L sobre elalfabeto Σ = 6a, b7 ue consiste de las palabrasue tienen m@s as ue bs.
1. a ∈ L
2. #i u ∈ L entonces au ∈ P .
(. #i u v ∈ L entonces buv , ubv uvb ∈ P .
. %ualuier palabra en L puede ser obtenido apartir de la regla 1. utilizando las reglas 2. (.
un n!mero finito de veces.
14
8/19/2019 Clase Compiladores
15/48
¿ES SUFICIENTE LARECURSIVIDAD?
Ba muc
8/19/2019 Clase Compiladores
16/48
CONCATENACIÓN DE LENGUAJES
L1L2 = 6w $ w = xy , x ∈ L1 y ∈ L27 Para un lenguaje L:
L8 = 6λ7
L1
= LL2 = L LL( = L L L ...
L*
= L8
∪ L1
∪ L2
∪ L(
∪... )%erradura de Cleene*L+ = L1 ∪ L2 ∪ L( ∪... = LL*
16
8/19/2019 Clase Compiladores
17/48
EJEMPLO DE CONCATENACIÓN = 6a, b, c7' ! = 6abb, ba7
! =6aabb, aba, babb, bba, cabb, cba7 8 = 6λ7 1 = 6a, b, c7 2 = = 6aa, ab, ac, ba, bb, bc, ca, cb, cc7 ( = 2 = 6aaa, aab" aac" aba, abb" abc" aca,
acb" acc" baa, bab" bac" bba, bbb" bbc" bca, bcb"bcc" caa, cab" cac" cba" cbb, cbc" cca" ccb" ccc7
17
8/19/2019 Clase Compiladores
18/48
EJEMPLOS DE CERRADURA DE KLEENE
L = 68, 117L8 = 6λ7L1 = 68, 117L2 = 688, 811, 118, 11117L( = 6888, 8811, 8118, 81111, 1188, 11811, 11118, 1111117L = 68888, 88811, 88118, 881111, 81188, 811811, 811118,
8111111, 11888, 118811, 118118, 1181111, 111188,1111811, 1111118, 111111117
L9 son todas las ue se pueden formar concatenandocualuier n!mero de veces )e+cepto ∞* palabras de L. "aspalabras pueden ser iguales o distintas.
D%u@ntos elementos tiene Ln7: 2n
ndependientemente del lenguaje, DLn tiene siempre 2n elementosF
18
8/19/2019 Clase Compiladores
19/48
MÁS EJEMPLOS L = 6a, b796bb7 6a, b79
%onsiste de las cadenas sobre 6a, b7 ue contienen la
subcadena bb. "enguaje ue consiste de todas las cadenas ue
empiezan con aa o terminan con bb.L = 6aa76a, b79∪ 6a, b796bb7
L1 = 6bb7 L2 = 6λ, bb, bbbb7. L19 = DF, L29 = DFGanto L19 como L29 consisten de cadenas ue tienen un
n!mero par de bHs.
6aa, bb, ab, ba79%onsiste de todas las cadenas sobre 6a, b7 de longitud par.
6a, b79I 6aa, bb, ab, ba79Es el lenguaje ue consiste de las cadenas de longitud non.DEs regular este lenguajeFEste lenguaje tambiJn est@ dado por 6a, b76aa, bb, ab,
ba79,por lo tanto el lenguaje sí es regular.
19
8/19/2019 Clase Compiladores
20/48
CONJUNTOS REGULARES
n conjunto es regular si1. Es el conjunto vacío, ∅, & el conjunto cuo elemento es la
palabra vacía, 6λ7, & es un subconjunto simple )s&lo unelemento* del alfabeto.er generado a partir
2. Puede ser generado a partir de ∅ & de 6λ7 & de un subconjuntosimple utilizando las operaciones de uni&n, concatenaci&n cerradura de Cleene.
ota: no se puede utilizar la diferencia de conjuntos. 4efinici&n recursiva de conjunto regular.
#ea Σ un alfabeto. "os conjuntos regulares sobre Σ sedefinen recursivamente de la siguiente manera:
;ase: ∅, 6λ7 6a7, para toda a ∈ Σ, son conjuntos regulares
sobre Σ. Paso recursivo: #i ! son conjuntos regulares sobre Σ,
entonces los conjuntos ∪ ! , ! 9 tambiJn lo son. %erradura: es un conjunto regular sobre Σ s&lo si puede ser
obtenido a partir de los elementos base mediante un n!mero
finito de aplicaciones del paso recursivo. 20
8/19/2019 Clase Compiladores
21/48
EJEMPLOS DE CONJUNTOSREGULARES 6a, b796bb76a, b79 es regular sobre 6a, b7
%onsiste del conjunto de cadenas ue contienena la subcadena bb.
El conjunto de cadenas ue empiezan terminan con una a contienen al menos unab es regular sobre 6a, b7. 6a76a, b796b76a, b796a7
21
EXPRESIONES REGULARES
8/19/2019 Clase Compiladores
22/48
EXPRESIONES REGULARES
"as e+presiones regulares se utilizan para abreviar ladescripci&n de conjuntos regulares. El conjunto regular 6a7 es representado por a. "as operaciones de uni&n, concatenaci&n cerradura de Cleene son
denotadas por 3, u+taposici&n 9, respectivamente.
4efinici&n recursiva de una e+presi&n regular.#ea Σ un alfabeto. "as e+presiones regulares sobre Σ se definenrecursivamente de la siguiente manera:
;ase:∅
,λ a, para toda a
∈ Σ, son e+presiones regulares sobre
Σ.
Paso recursivo: #i u v son e+presiones regulares sobre Σ, entonces lase+presiones )u3v *, )uv * )u9* tambiJn lo son representan a los conjuntos6u7 ∪ 6v 7, 6u76v 7 6u79, respectivamente.
%erradura: u es una e+presi&n regular sobre Σ s&lo si puede ser obtenido apartir de los elementos base mediante un n!mero finito de aplicacionesdel paso recursivo.
22
8/19/2019 Clase Compiladores
23/48
EJEMPLOS
"enguaje E+presi&n regular
6λ7 λ687 868817 = 687687617 88168, 17 = 687∪617 8 3 1
68, 187 = 687∪6187 8 3 1861, λ768817 )1 3 λ*88161187968, 17 )118*9)8 3 1*61796187 1918
618, 111, 1181879 )18 3 111 3 11818*9
68, 1879)61179∪6881, λ7* )8 3 18*9))11*9 3 881 3 λ*)88 3 81 3 18 3 11*9 ))8 3 1*)8 3 1**9
23
8/19/2019 Clase Compiladores
24/48
...EXPRESIONES REGULARES
Gomando en cuenta ue la uni&n la concatenaci&n son asociativas,adem@s conviniendo en ue la precedencia u orden de ejecuci&n de lasoperaciones est@ dada por:ParJntesis%erradura de Cleene%oncatenaci&nni&n
las e+presiones se pueden simplificar a!n m@s reduciendo el n!mero deparJntesis. 6a, b796bb76a, b79 = )a 3 b*9bb)a 3 b*9
6a76a, b796b76a, b796a7 = a)a 3 b*9b)a 3 b*9a
otaci&nu3 = uu* u2 = uu" u( = u2u" ...
24
8/19/2019 Clase Compiladores
25/48
EJEMPLO
El conjunto 6bawab $ w ∈ 6a, b797 es regular sobre6a, b74emostraci&n:%onjunto E+presi&n Kustificaci&n
1. 6a7 a ;ase2. 6b7 b ;ase(. 6a76b7=6ab7 ab %oncatenaci&n de 1 2. 6a7 ∪ 6b7=6a,b7 a3b ni&n de 1 2L. 6b76a7=6ba7 ba %oncatenaci&n de 2 1M. 6a,b79 )a3b*9 %erradura Cleene de N. 6ba76a,b79 ba)a3b*9 %oncatenaci&n de L MO. 6ba76a,b796ab7 ba)a3b*9ab %oncatenaci&n de N (
25
8/19/2019 Clase Compiladores
26/48
LENGUAJES REGULARES 4efinici&n: n lenguaje es regular si se
puede representar por una e+presi&n regularo conjunto regular.
26
8/19/2019 Clase Compiladores
27/48
...MÁS EJEMPLOS )a3b*9aa)a3b*93)a3b*9bb)a3b*9:
epresenta al conjunto de cadenas sobre 6a, b7 ue contienen a la subcadena aa o a la subcadena bb oa ambas subcadenas.
E+presi&n regular ue represente al conjunto de cadenas sobre 6a, b7 ue contienene+actamente dos bHs: a9ba9ba9
a9ba9b#a3b*9, )a3b*9ba9ba9, )a3b*9b)a3b*9b)a3b*9 representan al conjunto de cadenas sobre 6a, b7 ue contienen dos o m@s bHs.
a9)a9ba9ba9*9 a9)ba9ba9*9 epresentan cadenas con un n!mero par de bHs.
E+presi&n regular para el lenguaje sobre 6a, b7 en cuas palabras inmediatamenteantes de toda b aparece una a: )a3ab*9.
E+presi&n regular ue representa a las palabras ue contienen e+actamente una vezdos bHs contiguas: )ba3bc3a3c*9bb)a3c3ab3cb*9
27
8/19/2019 Clase Compiladores
28/48
EJERCICIO EN CLASE Escriba una e+presi&n regular para el
lenguaje sobre 68 ,17 ue consiste de laspalabras en las ue no
8/19/2019 Clase Compiladores
29/48
EUIVALENCIAS
na e+presi&n regular define un patr&n' unapalabra pertenece al lenguaje definido por
esa e+presi&n regular si s&lo si sigue elpatr&n.
na e+presi&n regular ue represente un
lenguaje debe cumplir dos condiciones:%orrecta: todas las palabras representadas por lae+presi&n regular deben ser parte del lenguaje.
%ompleta: toda palabra del lenguaje debe serrepresentada por la e+presi&n regular.
%oncatenaci&n indica orden de los símbolos,la cerradura de Cleene permite repeticiones 3 indica selecci&n.
4os e+presiones ue representan al mismoconjunto son llamadas euivalentes.
29
IDENTIDADES
8/19/2019 Clase Compiladores
30/48
IDENTIDADES ∅u = u∅ = ∅ λu = uλ = u
∅9
= λ λ9 = λ u3v = v 3u u3∅ = u u3u = u u9 = u9 u9 = )u9*9 u)v 3w * = uv 3 uw )u3v *w = uw 3vw )uv *9u = u)vu*9
)u3v *
9
= )u9
3v *
9
= u9
)u3v *
9
= )u3vu9
*
9
= )u9
v
9
*
9
= u9
)vu9
*
9
=)u9v *9u9
u9)u + λ* = u9
u9u9 = u9 u9 3 v 9 = v 9 3 u9
)u9
v 9
*9
= )u 3 v *9
= )u 3 v *9
uv )u 3 v *9
3 v 9
u9
30
EJEMPLOS
8/19/2019 Clase Compiladores
31/48
EJEMPLOS E+presi&n ue representa las cadenas sobre 6a, b7 ue no
contienen la subcadena aa: b9)ab3*93b9)ab3*9a =
b9)ab3*9)λ3a* =b9)abb9*9)λ3a* =)b3ab*9)λ3a*
E+presi&n regular ue representa las cadenas sobre 6a, b,c7 ue contienen la subcadena bc: )a3b3c*9bc)a3b3c*9
c9)b3ac9*9
epresenta las cadenas ue no contienen la subcadena bc.
%adenas sobre 68, 17 de longitud igual a M:
)8 3 1*)8 3 1*)8 3 1*)8 3 1*)8 3 1*)8 3 1* = )8 3 1*M
%adenas sobre 68, 17 de longitud maor o igual a M: )8 3 1*)8 3 1*)8 3 1*)8 3 1*)8 3 1*)8 3 1*)8 3 1* 9 = )8 3 1*M)8 3 1*9
%adenas sobre 68, 17 de longitud menor o igual a M: )8 3 1 3 λ*)8 3 1 3 λ*)8 3 1 3 λ*)8 3 1 3 λ*)8 3 1 3 λ*)8 3 1 3 λ*
= )8 3 1 3 λ*M 31
8/19/2019 Clase Compiladores
32/48
EJERCICIOS EN CLASE
btenga una e+presi&n regular para el conjunto depalabras sobre 6a, b, c7 ue tienen al menos una a al menos una b.
c9a)a 3 c*9b)a 3 b 3 c*9 3 c9b)b 3 c*9a)a 3 b 3 c*9
btenga una e+presi&n regular para el lenguaje sobre68 , 17 ue consiste de las palabras cuo dJcimosímbolo contado de la derec
8/19/2019 Clase Compiladores
33/48
CLAUSURA POSITIVA DE UNLENGUAJE #e define
Es decir, el lenguaje obtenido uniendo el
lenguaje " con todas sus potencias posibles,e+cepto "8.
Puesto ue el alfabeto / es tambiJn unlenguaje sobre /, puede aplic@rsele esta
operaci&n. #e ver@ entonces ue
/3 = R)/*I67
33
8/19/2019 Clase Compiladores
34/48
ITERACIÓN! CIERRE OCLAUSURA DE UN LENGUAJE #e define:
#on evidentes las siguientes identidades:"9 = "3 67∪
"3 = ""9 = "9" Puesto ue el alfabeto / es tambiJn un lenguaje
sobre /, puede aplic@rsele esta operaci&n. #e ver@entonces ue /9 = R)/*
A partir de este momento, representaremos allenguaje universal sobre el alfabeto / con elsímbolo /9.
34
8/19/2019 Clase Compiladores
35/48
8/19/2019 Clase Compiladores
36/48
EJERCICIOS #ea / =68,1,27, +=88, =1, z=218. 4efinir las
siguientes palabras: +, +z,z, +z, +(, +22,)+*2, )z++*(. D%u@les son sus longitudes,cabezas colasF
#ea / =68,1,27. Escribir seis de las cadenasm@s cortas de /3 de /9.
36
8/19/2019 Clase Compiladores
37/48
GRAMATICA na gram@tica describe la estructura de las
frases de las palabras de un lenguaje.
#e llama $ra)ática &or)al a la cuádru'la
donde G es el alfabeto de sí)boloster)inales" y es el al&abeto de sí)bolos noter)inales. e verifica ue
37
8/19/2019 Clase Compiladores
38/48
P es un conjunto finito de reglas de producci&n dela forma u ::= v, donde se verifica ue:
Es decir, u es una palabra no vacía del lenguajeuniversal del alfabeto ue contiene al menos unsímbolo no terminal v es una palabra,posiblemente vacía, del mismo lenguaje universal.
38
8/19/2019 Clase Compiladores
39/48
EJEMPLO
39
8/19/2019 Clase Compiladores
40/48
NOTACION DE BACKUS otaci&n abreviada: si el conjunto de
producciones contiene dos reglas de la forma
u ::= v
u ::= pueden representarse abreviadamente con lanotaci&n u ::= v $
"a notaci&n u::=v de las reglas de
producci&n, junto con la regla de abreviaci&nindicada, se denomina ,or)a or)al deacus" o ,.
40
8/19/2019 Clase Compiladores
41/48
41
8/19/2019 Clase Compiladores
42/48
DERIVACION DIRECTA #ea / un alfabeto +::= una producci&n
sobre las palabras de ese alfabeto. #ean v dos palabras del mismo alfabeto )v, /9*.∈#e dice ue w es derivaci/n directa de v" o0ue v 'roduce directa)ente w" o 0ue w sereduce directa)ente a v" si existen dos 'alabras z"u *"∈ tales ue:
v=z+u=zu
ndicamos esta relaci&n con el símbolo v .→
42
8/19/2019 Clase Compiladores
43/48
DERIVACION DIRECTA %"A: #i +::= es una producci&n sobre /, se
sigue ue + .→
#ea el alfabeto /=68,1,2,,%7, el conjunto deproducciones
::= %
::= %
% ::= 8
% ::= 1
% ::= 2
Pueden demostrarse f@cilmente las siguientesderivaciones directas:
% %% %%% 2%% 21% 218→ → → → → →
43
8/19/2019 Clase Compiladores
44/48
DERIVACION #ea / un alfabeto P un conjunto de
producciones sobre las palabras de esealfabeto. #ean v dos palabras del mismoalfabeto )v, /9*. #e dice ue∈ w esderivaci/n de v" o 0ue v 'roduce w" o 0ue wse reduce a v" si existe una secuencia &initade 'alabras u2" u1" ..." un #n324" 5 ales ue
v = u8 u1 u2 ... unI1 un = → → →
ndicamos esta relaci&n con el símbolo v 3→. "a secuencia anterior se llama derivaci/nde lon$itud n.
44
8/19/2019 Clase Compiladores
45/48
ndicamos esta relaci&n con el símbolo v 3→. "a secuencia anterior se llama derivaci/nde lon$itud n.
En el ejemplo anterior, puede verse ue 3 218 mediante una secuencia de longitud→M.
%"A: #i v , entonces v 3 → →mediante una secuencia de longitud 1.
45
8/19/2019 Clase Compiladores
46/48
46
8/19/2019 Clase Compiladores
47/48
PREGUNTADBa lenguajes para los ueno e+iste una e+presi&n
regular ue losrepresenteF
47
Sí !!
8/19/2019 Clase Compiladores
48/48
EJEMPLO DE UN LENGUAJE NOREGULAR
6anbn $ n ≥ 87