presentación de powerpoint -...
TRANSCRIPT
![Page 1: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/1.jpg)
![Page 2: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/2.jpg)
Contenido
• Clasificación de los autómatas finitos
• Autómata finito no determinista (AFND)
• Autómata finito determinista (AFD)
• Teorema sobre la transformación de AFND en AFD
• Transformación de una expresión regular en un autómata
finito
• Construcción de Thompson de un AFND a partir de una
expresión regular
• Nomenclatura de Thompson
• Ejemplos
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
2
![Page 3: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/3.jpg)
Clasificación de los autómatas finitos
• Cuando se definió autómata finito, la función ,es en
general no determinista. Así en función de f, se hablará de autómatas
finitos deterministas AFD y autómatas finitos no deterministas
AFND.
• Un autómata finito no determinista AFND se caracteriza por la posibilidad de
que dada una entrada e en un estado qi, se pueda pasar a un estado qj, qk,...,qn
sin saber a ciencia cierta, a cual de esos estados pasará. Existiendo la misma
probabilidad de que pase a cualquiera de dichos estados.
• Un autómata finito determinista AFD es un caso particular de los autómatas
finitos, en el que la función de transición no presenta ninguna ambigüedad en las
transiciones de estados para una entrada dada.
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
3
![Page 4: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/4.jpg)
Autómatas finitos no deterministas
(AFND) • La definición de autómata finito no determinista AFND coincide con
la de autómata finito :
• Con la salvedad de que es no determinista, i.e. es aquel que
presenta cero, una o más transiciones por el mismo carácter del alfabeto.
• Un autómata finito no determinista también puede o no tener más de
un nodo inicial.
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
4
![Page 5: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/5.jpg)
AFND Ejemplo • Resolver:
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
5
![Page 6: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/6.jpg)
AFND Ejemplo • Solución:
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
6
![Page 7: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/7.jpg)
Autómatas finitos deterministas
(AFD) • Un autómata finito determinista AFD es un caso particular
de los autómatas finitos, en el que la función de transición
no presenta ninguna ambigüedad en las transiciones de
estados para una entrada dada.
• Un autómata finito determinista es una quíntupla AFD=(E,
Q, f, q1, F) donde la función es
determinista.
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
7
![Page 8: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/8.jpg)
Teorema sobre la transformación de
AFND en AFD
• "Para todo autómata finito no determinista AFND=(E, Q,
f, q1,F) se puede construir un autómata finito
determinista AFD=(E, Q’, f’, q’1, F’) tal que el lenguaje
reconocido por el autómata finito determinista AFD
coincida con el lenguaje reconocido por el autómata finito
no determinista AFND, es decir L(AFD) = L(AFND)".
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
8
![Page 9: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/9.jpg)
Transformación de AFND en AFD
a b Expresión: ab|ac*
a
2
1
c
3
4
AFND
INICIO
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
9
![Page 10: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/10.jpg)
Transformación de AFND en AFD
b a
1
c
3
4
2,4
c
AFD
Expresión: ab|ac*
INICIO
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
10
![Page 11: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/11.jpg)
AFND -> AFD (Ejemplo) • Resolver:
• Sea el autómata finito no determinista del ejemplo anterior, determinar un
autómata finito determinista equivalente.
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
11
![Page 12: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/12.jpg)
AFND -> AFD (Ejemplo) • Solución:
• El AFD tendrá en un principio 24 estados,
i.e. Q’ conjunto de las partes de Q (16
estados).
• También se define el estado inicial y el
conjunto de estados finales F’.
• Q’={
,[q1],[q2],[q3],[q4],[q1q2],...,[q1q2q3q4]
}
• q’1=[q1]
• F’={[q4],[q1q4],[q2q4],[q3q4],[q1q2q4],.
..,[q1q2q3q4]}
• f ’ se construye a partir de f resultando la
siguiente tabla
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
12
![Page 13: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/13.jpg)
AFND -> AFD (Ejemplo) • Solución:
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
13
![Page 14: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/14.jpg)
AFND -> AFD (Ejemplo) • Solución:
• Ahora bien, en un AF los estados
que no son accesibles desde el
inicial pueden eliminarse, así se
eliminan los marcados en la tabla
con flechas.
• Entonces f’ puede resumirse según
la tabla:
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
14
![Page 15: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/15.jpg)
AFND -> AFD (Ejemplo) • Solución
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
15
![Page 16: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/16.jpg)
Transformación de una expresión regular
en un autómata finito • Dada una expresión regular existe un autómata finito
capaz de reconocer el lenguaje que ésta define.
• Recíprocamente, dado un autómata finito, se puede
expresar mediante una expresión regular del lenguaje
que reconoce.
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
16
![Page 17: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/17.jpg)
Transformación de una expresión regular
en un autómata finito
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
17
![Page 18: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/18.jpg)
Transformación de una expresión regular
en un autómata finito
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
18
![Page 19: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/19.jpg)
Transformación de una expresión regular
en un autómata finito
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
19
![Page 20: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/20.jpg)
Construcción de Thompson de un AFND a
partir de una expresión regular
• La construcción de Thompson construye un AFND a partir
de cualquier expresión regular.
• El algoritmo construye a partir de expresiones regulares un
diagrama de AFND, para luego poder generar un AFD
mínimo equivalente.
• Utiliza una notación estándar para generar el AFND
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
20
![Page 21: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/21.jpg)
• Para la representación de una cadena vacía se utiliza el símbolo
ε.
Nomenclatura de Thompson
Cadena Vacía
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
21
![Page 22: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/22.jpg)
Nomenclatura de Thompson
• Para representar un símbolo, se utilizan dos estados y una
transición para el movimiento con el símbolo.
r
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
22
![Page 23: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/23.jpg)
Nomenclatura de Thompson
• Para la concatenación de dos símbolos únicamente se unen cada
uno de los símbolos por
rs
Concatenación de símbolo
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
23
![Page 24: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/24.jpg)
• Para la elección de alternativas, crear transiciones ε para la
unión de las transiciones.
Nomenclatura de Thompson
r | s
Elección de alternativas
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
24
![Page 25: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/25.jpg)
• Para la cerradura Positiva, se agregan transiciones ε para retornar
al estado previo, permitiendo agregar 1 o mas veces el símbolo
Nomenclatura de Thompson
r +
Cerradura positiva
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
25
![Page 26: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/26.jpg)
Nomenclatura de Thompson
• Para la cerradura de Kleene, se agregan transiciones ε para
retornar a estado previo. Y otra transición ε para saltar la
transición con r.
r *
Cerradura de Kleene
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
26
![Page 27: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/27.jpg)
Diagrama del NFA que representa la ER a*b.
1. Parte de la cerradura de Kleene.
Ejemplo 01 Método de Thompson
a*b
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
27
![Page 28: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/28.jpg)
2. Para continuar se generan la concatenación del símbolo
b
Ejemplo 01 Método de Thompson
a*b
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
28
![Page 29: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/29.jpg)
3. Para finalizar se numeran los estados y se indica el
estado inicial y final
Ejemplo 01 Método de Thompson
a*b
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
29
![Page 30: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/30.jpg)
A partir de la ER (b|(b*a)*)a
1. Parte de la cerradura de Kleene que se encuentra dentro
de paréntesis.
Ejemplo 02 Método de Thompson
(b|(b*a)*)a
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
30
![Page 31: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/31.jpg)
A partir de la ER (b|(b*a)*)a
2. Completamos dicho paréntesis concatenando el símbolo
a
Ejemplo 02 Método de Thompson
(b|(b*a)*)a
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
31
![Page 32: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/32.jpg)
A partir de la ER (b|(b*a)*)a
3. Aplicar la Cerradura de Kleene al paréntesis
Ejemplo 02 Método de Thompson
(b|(b*a)*)a ε
ε
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
32
![Page 33: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/33.jpg)
A partir de la ER (b|(b*a)*)a
4. La elección de alternativas del b y el diagrama anterior.
Ejemplo 02 Método de Thompson
(b|(b*a)*)a ε
ε
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
33
![Page 34: Presentación de PowerPoint - eafranco.comeafranco.com/docencia/compiladores/files/10_Analisis_Lexico_VI.pdf · •Transformación de una expresión regular en un autómata finito](https://reader031.vdocumento.com/reader031/viewer/2022021712/5ba2aff209d3f2a1708c4b87/html5/thumbnails/34.jpg)
5. Concatenamos el último símbolo, enumerando e
indicando el estado inicial y el final
Ejemplo 02 Método de Thompson
(b|(b*a)*)a ε
ε
10 Análisis léxico VI Compiladores - Profr. Edgardo Adrián Franco Martínez
34