análisis léxico

8/31/2014

Análisis Léxico
Eduardo Aguilar Torres
Agosto,2014.

Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar Torres

Agenda






Información de contacto.
Definición general.
Autómatas finitos.
Desde ER hasta los DFA.
Analizador léxico para el lenguaje TINY.

Departamento de Ingeniería de Sistemas y Computación –Compiladores CCA71

Eduardo Andrés Aguilar Torres

1

8/31/2014

Agenda






Información de contacto.
Definición general.
Autómatas finitos.
Desde ER hasta los DFA.
Analizador léxico para el lenguaje TINY.

Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar Torres

Información de Contacto
 Eduardo Aguilar Torres
Email: eaguilar02@ucn.cl
 Horario de atención: Martes y Jueves 18:00 –
19:30.
 Oficina: Y1-115 (Laboratorio de Inteligencia
Artificial).

Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar Torres

2

8/31/2014

Agenda






Información de contacto.
Definición general.
Autómatas finitos.
Desde ER hasta los DFA.
Analizadorléxico para el lenguaje TINY.

Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar Torres

Definición general
Source Code

Scanner
Tokens

•
•
•
•
•
•

Palabras reservadas
Identificadores
Números
Operadores
Símbolos
Comentarios

Parser
Syntax Tree
Semantic
Analyzer
Annotated
Tree
Source Code
Optimizer

Literal
TableSymbol
Table
Error
Handler

Intermediate
Code
Code
Generator
Target
Code
Target Code
Optimizer

Target
Code

Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar Torres

3

8/31/2014

Clase 20-08 (Ejercicio 3)
•

Considerar el alfabeto simple ∑ = {a, b, c}, determinar
una expresión regular que defina el conjunto de todas
lascadenas que no contengan dos b consecutivas.

• (a|c)*(b(a|c)(b(a|c))*)*(a|c)*|b
• (a|c)*(b(a|c))*(a|c)*(b|e)
• (a|c|ba|bc)*(b|e)

Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar Torres

Clase 20-08 (Ejercicio 4)
Construya la expresión regular correspondiente
al siguiente autómata finito determinístico.((11|00)|((10|01)(00|11)*(01|10)))*
Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar Torres

4

8/31/2014

Agenda






Información de contacto.
Definición general.
Autómatas finitos.
Desde ER hasta los DFA.
Analizador léxico para el lenguaje TINY.

Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés AguilarTorres

Autómatas Finitos
•
•
•
•

•

Un DFA debe tener una transición para cada estado y
carácter.
Aquellas transiciones que dan errores como resultado
se dejan fuera del diagrama del DFA.
Al hacer una transición, los caracteres de entrada son
acumulados hasta convertirse en un token.
Al alcanzar un estado de aceptación, se devuelve el
token que se acaba de reconocer, junto concualquier
atributo asociado.
Al alcanzar un estado de error, se debe retroceder
hacia la entrada (retro-seguimiento) o generar un
token de error.

Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar Torres

5

8/31/2014

Autómatas Finitos

• La transición [otro] indica que el carácter delimitador se
debería considerar como búsqueda haciaadelante, es
decir, que debería ser devuelto a la cadena de entrada
y no consumido.
• El estado de error se ha convertido en estado de
aceptación sin transiciones fuera del estado.
• El AF debe reconocer un token a la vez y comenzar en
su estado de inicio después de reconocer cada token.
Departamento de Ingeniería de Sistemas y Computación – Compiladores CCA71

Eduardo Andrés Aguilar...