ANALIZADOR
LEXICO
J OSTI N GON Z ALEZ BR AVO
I NG. SI STEMAS C OMPUT AC ION ALES 5 B
DOCENTE: C ER EC ED O GAR C IA M AN U EL.
TEMAS: 4. 3 C R EAC I ÓN D E T ABLAS D E T OKEN
4. 4 E RRORES LÉXI C OS
5. 5 GENERA D OR ES D E AN ALIZ AD OR ES LÉXICOS
INTRODUCCIÓN
N ANALIZADOR LÉXICO O
U
ANALIZADOR LEXICOGRÁFICO ES
LA PRIMERA FASE DE UN
COMPILADOR, CONSISTENTE EN
UN PROGRAMA QUE RECIBE
COMO ENTRADA EL CÓDIGO
FUENTE DE OTRO PROGRAMA Y
PRODUCE UNA SALIDA
COMPUESTA DE TOKENS O
SÍMBOLOS.
4.3 CREACIÓN DE
TABLAS DE TOKENS
TABLA CONJUNTO DE PARES CLAVE-VALOR, LLAMADOS ELEMENTOS
DE LA TABLA. LA TABLA DE SÍMBOLOS ES UNA COMPONENTE
NECESARIA DE UN COMPILADOR. AL DECLARAR UN IDENTIFICADOR
(NORMALMENTE UNA SOLA VEZ), ÉSTE ES INSERTADO EN LA TABLA.
CADA VEZ QUE SE UTILICE EL IDENTIFICADOR SE REALIZARÁ UNA
BÚSQUEDA EN LA TABLA PARA OBTENER LA INFORMACIÓN ASOCIADA
(EL VALOR).
BÚSQUEDA DADA LA CLAVE DE UN ELEMENTO, ENCONTRAR SU
VALOR.
INSERCIÓN DADO UN PAR CLAVE-VALOR, AÑADIR UN ELEMENTO
NUEVO A LA TABLA.
CAMBIO DE VALOR BUSCAR EL ELEMENTO Y CAMBIAR SU VALOR.
BORRADO ELIMINAR UN ELEMENTO DE LA TABLA. LONGITUD DE
BÚSQUEDA (O TIEMPO DE ACCESO)
DE UNA CLAVE LI = NÚMERO DE COMPARACIONES CON ELEMENTOS
DE LA TABLA PARA ENCONTRAR ESA CLAVE.
MAXIMA LM = NÚMERO MÁXIMO DE COMPARACIONES PARA ENCONTRAR
CUALQUIER CLAVE.
MEDIA (ESPERADA) LM = NÚMERO MEDIO DE COMPARACIONES PARA ENCONTRAR
UN VALOR. SI LA FRECUENCIA DE TODAS LAS CLAVES ES LA MISMA: LM = (S LI)/N
SI LA FRECUENCIA DE TODAS LAS CLAVES NO ES LA MISMA: LM = S PI.LI
GRADO DE OCUPACIÓN S = N/N DONDE N=NÚMERO DE ELEMENTOS EN LA TABLA Y
→
N=CAPACIDAD MÁXIMA DE LA TABLA. FUNCIÓN DE BÚSQUEDA: B : K E ASOCIA A
CADA CLAVE K UN ELEMENTO B(K). VALOR ASOCIADO A UNA CLAVE K: V(B(K)).
PUEDE SER MÚLTIPLE, EN CUYO CASO NORMALMENTE SE CONVIERTE EN UN
PUNTERO. SI ESTÁ EN LA TABLA PUEDE ALMACENARSE CONSECUTIVAMENTE O EN
SUBTABLAS PARALELAS. TABLAS DE SÍMBOLOS (IDENTIFICADORES) LA CLAVE ES
EL IDENTIFICADOR. EL VALOR ESTÁ FORMADO POR:
ATRIBUTOS DEL IDENTIFICADOR
LA LONGITUD DEL IDENTIFICADOR PUEDE ESPECIFICARSE EN LA TABLA O
DELANTE DEL NOMBRE, O SER IMPLÍCITA. O TABLAS CONSECUTIVAS: TODOS LOS
ELEMENTOS OCUPAN POSICIONES DE MEMORIA ADYACENTES. O TABLAS LIGADAS:
CADA ELEMENTO APUNTA AL SIGUIENTE. O TABLAS DOBLEMENTE LIGADAS: CADA
ELEMENTO APUNTA AL SIGUIENTE Y AL ANTERIOR. O TABLAS NO ORDENADAS
INSERCIÓN: EN EL PRIMER LUGAR VACÍO.
4.4 ERRORES LÉXICOS
EL ANÁLISIS LÉXICO CONSTITUYE LA PRIMERA FASE, AQUÍ SE LEE EL
PROGRAMA FUENTE DE IZQUIERDA A DERECHA Y SE AGRUPA EN
COMPONENTES LÉXICOS (TOKENS), QUE SON SECUENCIAS DE CARACTERES
QUE TIENEN UN SIGNIFICADO. ADEMÁS, TODOS LOS ESPACIOS EN BLANCO,
LÍNEAS EN BLANCO, COMENTARIOS Y DEMÁS INFORMACIÓN INNECESARIA
SE ELIMINA DEL PROGRAMA FUENTE. TAMBIÉN SE COMPRUEBA QUE LOS
SÍMBOLOS DEL LENGUAJE (PALABRAS CLAVE, OPERADORES,...) SE HAN
ESCRITO CORRECTAMENTE.
UN ANALIZADOR LÉXICO TAMBIÉN ES LA PARTE DEL TRADUCTOR QUE
MANEJA LA ENTRADA DEL CÓDIGO FUENTE, Y PUESTO QUE ESTA ENTRADA
A MENUDO INVOLUCRA UN IMPORTANTE GASTO DE TIEMPO, EL ANALIZADOR
LÉXICO DEBE FUNCIONAR DE MANERA TAN EFICIENTE COMO SEA POSIBLE.
SON POCOS LOS ERRORES SIMPLEMENTE EN EL NIVEL LÉXICO YA QUE
TIENE UNA VISIÓN MUY RESTRINGIDA DE UN PROGRAMA FUENTE. EL
ANALIZADOR LÉXICO DEBE DEVOLVER EL COMPONENTE LÉXICO DE UN
IDENTIFICADOR Y DEJAR A OTRA FASE SE OCUPE DE LOS ERRORES.
EJEMPLO
SUPONGA QUE UNA SITUACIÓN EN LA CUAL EL ANALIZADOR LÉXICO NO PUEDE
CONTINUAR PORQUE NINGUNO DE LOS PATRONES CONCUERDA CON UN PREFIJO DE
LA ENTRADA. TAL VEZ LA ESTRATEGIA DE RECUPERACIÓN MÁS SENCILLA SEA
RECUPERACIÓN “EN MODO PANICO” (ESTE MÉTODO DE RECUPERACIÓN ES DONDE SE
BORRA CARACTERES SUCESIVOS DE LA ENTRADA HASTA QUE EL ANALIZADOR LÉXICO
PUEDA ENCONTRAR UN COMPONENTE LÉXICO BIEN FORMADO). ¡¡LOS PROGRAMAS NO
SIEMPRE SON CORRECTOS!!
EL COMPILADOR TIENE QUE: REPORTAR CLARA Y EXACTAMENTE LA PRESENCIA DE
ERRORES RECUPERARSE DE CADA ERROR LO SUFICIENTEMENTE RÁPIDO PARA PODER
DETECTAR ERRORES SUBSIGUIENTES: TRATAR DE EVITAR MENSAJES FALSOS DE
ERROR UN ERROR QUE PRODUCE UN TOKEN ERRÓNEO ERRORES LÉXICOS
POSIBLES UN TOKEN O COMPONENTE LÉXICO ES UNA CADENA DE CARACTERES QUE
TIENE UN SIGNIFICADO COHERENTE EN CIERTO LENGUAJE DE PROGRAMACIÓN.
EJEMPLOS DE TOKENS, PODRÍAN SER PALABRAS CLAVE (IF, WHILE, INT),
IDENTIFICADORES, NÚMEROS, SIGNOS, O UN OPERADOR DE VARIOS CARACTERES.
SON LOS ELEMENTOS MÁS BÁSICOS SOBRE LOS CUALES SE DESARROLLA TODA
TRADUCCIÓN DE UN PROGRAMA, SURGEN EN LA PRIMERA FASE, LLAMADA ANÁLISIS
LÉXICO.
4.5 GENERADORES DE
ANALIZADORES LÉXICOS
SE PUEDEN USAR VARIAS TÉCNICAS PARA ACELERAR
EL ALGORITMO Y AHORRAR ESPACIO LAS ETIQUETAS
PUEDEN GUARDARSE MEDIANTE DISPERSIÓN PARA
PRODUCIR UN SISTEMA DE FIRMAS QUE ACELERE SUS
BÚSQUEDAS COMO LAS TABLAS DE TRANSICIONES
SON MUY ESCASAS, SE PUEDEN GUARDAR EN UNA
LISTA CORTA QUE SE CONSULTE CADA VEZ QUE SE
NECESITE HACER UNA TRANSICIÓN A PARTIR DE UN
ESTADO ESTAS LISTAS NO SUELEN TENER MÁS DE
TRES O CUATRO ELEMENTOS, ASÍ QUE SU BÚSQUEDA
SERÁ RAZONABLEMENTE RÁPIDA.
