Automatas y compiladores clase2

1. Germania Rodríguez
[email protected]
Teoría de Autómatas y
Compiladores

2. Análisis Léxico

3. Programa Análisis Tokens
Fuente Léxico

4. Función principal leer el programa fuente como
un archivo de caracteres y dividirlo en tokens
Caso especial de coincidencia de patrones, que
necesita métodos de reconocimiento de
patrones que son principalmente expresiones
regulares y autómatas finitos.
Análisis Léxico

5. Patrón: Regla que describe los lexemas que
producirán los tokens.
Tokens: Secuencia de caracteres que
representa una unidad de información en el
programa fuente. Categorías: palabras
reservadas, identificadores, símbolos
especiale
Lexema: cadena de caracteres que se ajustan a
un patrón, representada por un token. Ejm: IF,
WHILE, a1, *, +
El proceso de análisis léxico

6. Atributo: Valor asociado al token. Ejm:
Registro de token: Recolección de atributos
datos estructurados.
El analizador léxico funciona bajo el control
de analizador sintáctico.
El proceso de análisis léxico

7. • Eliminar comentarios
• Elimina aquellos caracteres o sentencias que
carecen de sentido para el Lenguaje
• Reconoce identificadores de usuario,
números, palabras reservadas.
• Reporta errores léxicos
• Lleva la cuenta del número de líneas
analizadas para reportar los errores.
Otras funciones de análisis léxico

8. Ejemplo:
• getToken
a[index] = 4 + 2

9. Componentes Léxicos
Alfabetos
• Conjunto finito no vacío de símbolos sobre
el que se puede generar cadenas y
posteriormente Lenguajes
Latino = {a, b, c, d, e, f, …….z}
Binario = {0,1}

10. Cadenas
Combinación, secuencia, concatenación de
símbolos basados de un alfabeto; cadena
nula, prefijos, sufijos.
EJM: casa, 01001
Operaciones:
– Longitud
– Concatenación

11. Lenguaje
• Conjunto de palabras formadas sobre un
alfabeto
– Castellano
• Restricciones: palabras que no forman
parte del Lenguaje, que no están
conceptualizadas.
– Ejm: abcam

12. Operaciones Lenguaje
• Dado que un Lenguaje es un conjunto, es
aplicable todas las operaciones entre
conjuntos
– Unión
– Intersección
– Diferencia
– Complemento
– Potencia o partes
Cada una con sus propiedades de las
operaciones

13. Operaciones Lenguaje
• Y algunas propias
– Concatenación
L
1
L
2
– Estrella Kleene *
L* = { } U L U LL U LLL
–  Cierre transitivo +
L
+
= L U LL U LLL
Técnicas de Demostración
– Demostración por inducción

14. Gramática
• Mecanismo para generar las cadenas que
pertenecen a un lenguaje, a la vez define
un conjunto finito de reglas que aplicadas a
un estado inicial, son capaces de generar
todas sus cadenas.
G={ A, T, P, S}
A = símbolos auxiliares
T= símbolos terminales
P= producciones - pares (antecedente,
consecuente)
S= símbolo inicial de la gramática

15. Expresión Regular
• Notación que representan de forma abreviada
y precisa las cadenas que pertenecen a un
lenguaje, denominadas token.
• Esta formada por los caracteres del alfabeto y
metacaracteres que denotan operaciones
definidas.
• Al conjunto de cadenas con las que
concuerdan con la expresión regular r se
denominado Lenguaje L(r)

16. Expresiones Regulares
• Básicas: Representan caracteres simples del
alfabeto que corresponden a si mismos
Ejm: L(a) = {a}
• Vacía: La cadena que no corresponde a
ningun carácter
L(E) = E
• Conjunto vacío: No contiene ninguna
cadena.
L(o) = { }

17. Operaciones Expresiones Regulares
• Selección:
Si r y s son expresiones regulares, la selección
se denota r|s y se define por cualquier cadena
que concuerda con r o s
En términos de lenguaje L(r|s) = L(r) U L(s)
La selección se puede extender a más de
dos alternativas L(a|b|c|d) = {a,b,c,d}

18. Operaciones Expresiones Regulares
• Concatenación:
Consiste en la yuxtaposición de los caracteres
sin un carácter intermedio.
La concatenación de las expresiones regulares
r y s se denota rs
En términos de lenguaje L(rs) = L(r)L(s)
La concatenación tambien se puede
extender a más de dos expresiones
regulares.

19. Operaciones Expresiones Regulares
• Repetición:
Denominada tambien cerradura de Kleene, se
denota r* donde r es una expresión regular y
corresponde a cualquier concatenación finita
de las cadenas r así
r* = { } U r U rr U rrr U ….

20. Precedencia de operaciones
1. Repetición
2. Concatenación
3. Selección de alternativas
Cuando la precedencia es diferente, debemos
usar paréntesis para denotarlo.

21. Extensiones expresiones regulares
• Una o más repeticiones:
Tambien conocida como cerradura positiva es una
variante de la cerradura Kleene que indica cero o más
repeticiones, se denota con + y equivale una o más
repeticiones
Ejm: (0|1)
+

• Cualquier carácter:
Se denota con el metacaracter . y equivale a que puede
ser reemplazado con cuanquier carácter del alfabeto
Ejm: .*1.* (todas las cadenas que contengan al menos un 1)
• Intervalo:
Se denota con corchetes y un guión Ejm: [a-z]

22. Extensiones expresiones regulares
• Cualquier carácter que no este en el
conjunto
Se denota con la el metacaracter -, significa que
no incluya el o las expresiones regulares
afectadas.
Ejm: - (a|c)
• Subexpresión opcional
Metacaracter ? Indica la opcionalida de cadenas
que pueden o no aparecer
Ejm: (+|-)? dígito

23. • Kenneth C. Louden, Construccion de Compiladores
Principios Y Práctica
• Universidad Jaume, Open Course Ware –II20 Teoría de
autómatas y lenguajes formales en: http://e-ujier.uji.es/pls/
www/!gri_www.euji22101?
p_id=7&p_tipo=A&p_curso=II20&p_idioma=ES
• http://www.slideshare.net/perlallamas/analisis-lexico-2
• http://www.slideshare.net/felipeiluminati/expresiones-regulares
Bibliografía