Análisis Léxico
Ing. de Computación y
Sistemas
Autómatas y Compiladores
Ing. Carlos Gaytán Toledo
Descripción Funcional
El analizador léxico o scanner lee los caracteres
del programa fuente para agruparlos en
palabras o lexemas y luego clasificarlos en
componentes léxicos o tokens que son
entregados al analizador sintáctico.
08/10/09 2
Descripción Funcional
La compilación empieza con el analizador
sintáctico quien solicita un token para realizar su
trabajo; el analizador léxico lee símbolos y envía el
token correspondiente a la unidad léxico que
requiere el analizador sintáctico y espera una
nueva solicitud de token.
El analizador léxico está supeditado por el
analizador sintáctico.
Durante estas etapas se tiene comunicación con la
tabla de símbolos que concentra información de
las entidades empleadas en el programa.
08/10/09 3
Descripción Funcional
Componentes Léxicos o tokens
palabras reservadas: if, while, do, break
identificadores: asociados a variables, nombres de
funciones, tipos definidos por el usuario, etiquetas,...
Por ejemplo: velocidad, y11, suma, _100
operadores: = * + - / ==
símbolos especiales: ; [ ] ( ) { } ,
constantes numéricas: valores enteros, valores en
coma flotante, etc.: 982, 0xF678, -83.2E+2,...
constantes de caracteres: cadenas de caracteres,
“hola mundo”,...
Comentarios: /** abcde **/
08/10/09 4
Descripción Funcional
Otras funciones del Analizador Léxico
Administrar el archivo del programa fuente: abrirlo,
leerlo, cerrarlo y gestionar posibles errores de lectura.
“Eliminar” comentarios, espacios en blanco, tabuladores
y saltos de línea (caracteres no validos para formar un
token).
Incluir archivos: # include ...
Expandir macros y funciones inline: # define ...
Contabilizar líneas y columnas para emitir mensajes de
error.
Reconocer las marcas de fin de archivo.
Insertar los identificadores en la Tabla de Símbolos.
Reconocer errores léxicos.
08/10/09 5
Token, patrones y
lexemas
Token: elemento léxico o categoría sintáctica del lenguaje fuente.
En Español: Nombres, verbos, adjetivos, …
En un lenguaje de programación: Identificadores, Enteros,
palabras reservadas, espacios en blanco, …
Patrón: regla que describe cómo se forma un token. Los patrones
se especifican mediante expresiones regulares
Lexema: Secuencia de caracteres del programa fuente que
concuerda con un patrón.
Atributos: Información adicional asociada a un token y que será
utilizada en el análisis semántico y/o en la etapa de síntesis
08/10/09 6
Token, patrones y
lexemas
Ejemplos
Token Lexema Patrón
identificador total, b52, i Letra seguida de letras o dígitos
cte_entera 1492, 1, 512 Digito seguido de mas dígitos
pr_if if Letra i seguida de letra f
pr_do do Letra d seguida de letra o
op_div / Símbolo /
op_mayig >= Símbolo > seguido de =
cte_cadena “hola…!!!” Símbolos entre comillas
08/10/09 7
Funcionamiento del
Scanner
08/10/09 8
Funcionamiento del
Scanner
08/10/09 9
Funcionamiento del
Scanner
Ejemplos:
08/10/09 10
Funcionamiento del
Scanner
Ejemplo: La siguiente
entrada del analizador
léxico:
n1 "hola" "hño l!'a" "\\as"
"ac\\as\"11\"22\"dd fas" c2
fin
variable 3 * a verdadero Y
fas"dfas "as"asf"
"a\aas" 1234.34
c3 c3 "AAAA BB
CC"
"fasdfs\"
numerica 3 / 456 <> != 3 O
fadvariable c3
si
falso
cadena
(,3)
produce la siguiente salida:
08/10/09 11
Funcionamiento del
Scanner
Ejercicio: dado la siguiente porción de código fuente
\tif(i==j)\n\t\tz=0; \n\telse\n\t\tz=1
determinar el par Token-lexema que regresa el analizador
léxico
if pr_if = op_asig
( par_izq 0 cte_entera
i ident ; pyc
== op_igualdad else pr_else
j ident z ident
) par_der = op_asig
z ident 1 cte_entera
08/10/09 12
Diseño del Analizador
Léxico
Definir el conjunto de elementos léxicos (tokens)
Elaborar la tabla de tokens, detallando: token, código
asignado al token y patrón (ER)
Construir un AFD para cada ER asociada a cada token.
Combinar todos los AFDs en un único AFD mínimo
equivalente cuyo DT tiene las siguientes diferencias:
El DT debe leer caracteres hasta reconocer un
token, y luego retornar el token que ha reconocido
El DT no puede tener estados de absorción ni de
error.
08/10/09 13
Diseño del Analizador
Léxico
De los estados finales no deben salir
transiciones.
En el caso de las cadenas no específicas, se
debe leer hasta hallar un carácter que no
forma parte del patrón. En este último
estado se debe devolver al buffer de
entrada el[0-9]
carácter leído[0-9]
(que puede ser
parte
[0-9]
del siguiente[0-9]
token), otro
marcando el
* Entero
0estado con 1 un asterisco.
0 1 2
AFD DT
08/10/09 14
Diseño del Analizador
Léxico
Ejemplo: AFD para reconocer números enteros
con signo negativo o sin signo y los operadores
suma y doble incremento.
Notación: d = [0-9], t = otro
Componentes léxicos: Entero (-?d+), Suma (+),
2incremento (+++)
08/10/09 15
Diseño del Analizador
Léxico
Componentes léxicos:
Entero d+
Real d+.d+
Identificador l(l|d)*
Opsuma +
Opresta -
Opmul *
Opdiv /
Parder )
Parizq (
Notación:
d = [0-9]
l = [a-zA-Z]
a = [0-9a-zA-Z]
t = otro
08/10/09 16
Implementación del
Analizador Léxico
Aspectos que se deben tomar en cuenta:
Estrategias de implementación
Prioridad de los tokens
Reconocimiento de palabras reservadas
Gestión de errores
Estrategias de implementación
Programa simulador de la Tabla de Transiciones.
Programa simulador del Diagrama de Transiciones.
Utilización de un constructor de analizadores léxicos.
08/10/09 17
Implementación del
Analizador Léxico
Programa simulador de la Tabla se
transiciones
Inicializa una variable con el estado inicial y
actualiza esta variable con la información de la
tabla cada vez que se lee un símbolo de
entrada, hasta que se lee el ultimo carácter del
lexema que está siendo analizado.
08/10/09 18
Implementación del
Analizador Léxico
Programa simulador de la Tabla se transiciones
08/10/09 19
Implementación del
Analizador Léxico
Programa simulador del Diagrama de
Transiciones
Traducción del DT a pseudo código (los estados del
AFD están implícitos en el algoritmo).
Utiliza una variable para almacenar el estado actual
y una estructura tipo case doble anidada.
El primer case comprueba el estado actual y el
siguiente el carácter en la entrada.
Las transiciones asocian un nuevo valor a la variable
estado y avanza en la entrada.
El código es largo y difícil de mantener si se
introducen nuevos caracteres en el alfabeto o
nuevos estados.
08/10/09 20
Implementación del
Analizador Léxico
Estado = 0;
Repite
Leer siguiente símbolo de la palabra;
Case estado is
1 : if símbolo == ´´+´ then estado = 3;
elsif símbolo = ´-´ then estado = 2;
elsif símbolo = digito then estado = 2;
else rutine _ error;
2 : devolver simbolo;
retornar SUMA;
3 : if símbolo == ´´+´ then estado = 5;
elsif símbolo = ´-´ then estado = 4;
elsif símbolo = digito then estado = 4;
else rutine _ error;
…
fin del case;
hasta fin de cadena;
08/10/09 21
Implementación del
Analizador Léxico
Utilización de un constructor de analizadores
léxicos
Solo necesitamos especificar:
Las expresiones regulares para los tokens.
Reglas de prioridad para los tokens que
coincidan.
Acciones asociadas para cada expresión
regular.
08/10/09 22
Implementación del
Analizador Léxico
Herramientas para la construcción de
compiladores
flex + bison (lenguaje C)
TP lex&yacc (lenguaje Pascal)
JLex + CUP (lenguaje Java)
08/10/09 23
Implementación del
Analizador Léxico
Prioridad de los tokens
Reconocer el token asociado al lexema más largo.
Por ejemplo: DO / DOT, el generador se quedaría con el más
largo (DOT) como identificador.
Si el lexema puede asociar a dos tokens, sus patrones estarán
definidos en un orden, así se asociará al que esté primero.
Por ejemplo: la especificación léxica aparecen las ER:
while Palabra reservada while
letra[letra|digito]* Identificador
08/10/09 24
Implementación del
Analizador Léxico
Reconocimiento de Palabras Reservadas
Incluir todas las PR en una tabla, y cuando el
analizador léxico reconozca un identificador,
comprobar si es una PR:
Si lo es, pasar al analizador sintáctico el código
asociado a la palabra reservada.
Si no lo es, es un identificador, luego insertar
en la TS en caso de que no esté en ella,
pasando al analizador sintáctico el token
identificador y como atributo su dirección en la
TS.
08/10/09 25
Implementación del
Analizador Léxico
Otra opción es inicializar la TS con todas las PR
[por orden alfabético para facilitar la posterior
búsqueda y acceso].
Cuando se encuentre un identificador se
busca en la TS.
SI lo encuentra en la zona reservada para
ellas ENTONCES es una palabra reservada; SI
NO, será un identificador, que, como tal, será
añadido a la TS.
08/10/09 26
Implementación del
Analizador Léxico
Gestión de errores léxicos
Un error léxico se detecta cuando una cadena de
caracteres no concuerda con ningún patrón.
Errores típicos:
Utilizar caracteres que no pertenecen al
alfabeto del lenguaje.
Escribir mal una palabra.
Acciones de recuperación:
Rechazar los caracteres leídos (lexema) y
volver al estado inicial o al estado final anterior
si existe.
08/10/09 27
Implementación del
Analizador Léxico
Modo Pánico: ignorar los caracteres siguientes
hasta leer uno que permita una transición desde
el estado actual.
Acciones de recuperación inteligente:
Borrar un carácter extraño.
Insertar un carácter que falta.
Reemplazar un carácter incorrecto.
Intercambiar dos caracteres adyacentes.
08/10/09 28
