Lenguajes y Autómatas L Unidad V

TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE CHIHUAHUA II
LENGUAJES Y AUTÓMATAS I
DESARROLLO UNIDAD V
ROBERTO PEDROZA
ÍNDICE
Contents
5.1 Función del analizador léxico.................................3
5.2 Componentes léxicos, patrones y lexemas............3
5.3 Creación de Tabla de tokens..................................4
5.4 Errores léxicos........................................................5
5.5 Generadores de analizadores léxicos....................6
5.6 Aplicaciones............................................................7
Referencias...................................................................8
5.1 Función del analizador léxico
Un analizador léxico aísla al analizador sintáctico de la representación en lexemas
de los componentes léxicos.
Tiene como funciones:
–Eliminación de espacios en blanco y comentarios. Si el analizador léxico elimina
los espacios en blanco, el analizador sintáctico nunca tendrá que considerarlos. La
alternativa de modificar la gramática para incorporar los espacios en blanco dentro
de la situación no es tan fácil de implantar.
–Reconocimiento de identificadores y palabras clave. Es el encargado de construir
los lexemas que constituyen los identificadores de los lenguajes de programación.
–Reconocimiento de constantes. La tarea de agrupar dígitos para formar enteros
se le asigna, por lo general, a un analizador léxico, porque los números se pueden
tratar como unidades simples durante la traducción
Es habitual que el analizador léxico y el sintáctico formen un par productor-
consumidor. El analizador léxico produce componentes léxicos y el analizador
sintáctico los consume.
Hay varias razones para dividir la fase de análisis de la compilación en análisis
léxico y análisis sintáctico.
1. Separar el análisis léxico del análisis sintáctico a menudo permite simplificar
una u otra de dichas fases.
2. Se mejora la eficiencia del compilador.
3. Se mejora la transportabilidad del compilador
5.2 Componentes léxicos, patrones y lexemas

Componente léxicos (token): unidad mínima de información que significa algo a
la hora de compilar; concepto de palabra; las frases de un lenguaje constan de
cadenas de componentes léxicos.
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.
El analizador léxico recoge información sobre los componentes léxicos en sus
atributos asociados. Los componentes léxicos influyen en las decisiones del
análisis sintáctico, y los atributos, en la traducción de los componentes léxicos. En
la práctica, los componentes.
En la práctica, los componentes léxicos suelen tener un solo atributo –un
apuntador a la entrada de la tabla de símbolos donde se guarda la información
sobre el componente léxico
Lexemas: Una secuencia de caracteres de entrada que comprenda un solo

componente léxico se llama lexema; cadenas de caracteres de las que extraigo el
concepto abstracto de componente léxico.
Patrón: Descripción de la forma que han de tomar los lexemas para ajustarse a un
componente léxico
Atributos de los componentes léxicos
Cuando concuerda con un patrón más de un lexema, el analizador léxico debe
proporcionar información adicional sobre el lexema concreto que concordó a las
siguientes fases del compilador.
5.3 Creación de Tabla de tokens.

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.
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. Máxima: 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
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: Puntero a la posición de memoria asignada. La clave
puede sustituirse por un puntero. Los identificadores pueden estar empaquetados.
La longitud del identificador puede especificarse en la tabla o delante del nombre,
o ser implícita.
Tablas consecutivas: Todos los elementos ocupan posiciones de memoria
adyacentes. Tablas ligadas: cada elemento apunta al siguiente. Tablas
doblemente ligadas: cada elemento apunta al siguiente y al anterior. Tablas no
ordenadas Inserción: en el primer lugar vacío.
5.4 Errores léxicos

Son pocos los errores léxicos que se pueden detectar simplemente a nivel léxico
porque un analizador léxico tiene una visión muy restringida del programa fuente.
La estrategia de recuperación más sencilla es el “modo pánico”. Se borran
caracteres sucesivos de la entrada hasta que el analizador léxico pueda encontrar
un componente léxico bien formado.
Otras posibles acciones de recuperación son:
1.Borrar un carácter extraño
2.Insertar un carácter que falta
3.Reemplazar un carácter incorrecto por otro correcto
4.Intercambiar dos caracteres adyacentes.
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.
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.
Como la tarea que realiza el analizador léxico es un caso especial de coincidencia
de patrones, se necesitan los métodos de especificación y reconocimiento de
patrones, y estos métodos son principalmente las expresiones regulares y los
autómatas finitos. Sin embargo, 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.
5.5 Generadores de analizadores léxicos

El paso de una expresión regular a un AF se puede hacer de manera
automatizada. Existen varias herramientas que realizan dicho trabajo
Generadores de analizadores léxicos:
– AT&T Lex (más común en UNIX)
– MKS Lex (MS-Dos)
– Flex
– Abraxas Lex
– Posix Lex
– ScanGen–JLex
– ...
FLEX sigue el esquema:
patrón1 {acción 1}
patrón2 {acción 2}
.......
Patrón k {acción k}
donde:
–patrón: expresión regular
–acción: fuente C con las acciones a realizar cuando el patrón concuerde con un
lexema•
Funcionamiento:
– FLEX recorre entrada estándar hasta que encuentra una concordancia» un
lexema correspondiente al lenguaje de algunas de las e.r. representadas por los
patrones
– entonces, ejecuta el código asociado (acción)
– permite acceder a la información asociada al lexema (string, longitud del mismo,
nº de línea en el código fuente, ...)
5.6 Aplicaciones
Algunas aplicaciones de los analizadores léxicos son:
El analizador léxico divide la entrada en componentes léxicos.
Los componentes se agrupan en categorías léxicas.
Asociamos atributos a las categorías léxicas.
Especificamos las categorías mediante expresiones regulares.
Para reconocer los lenguajes asociados a las expresiones regulares empleamos
autómatas de estados finitos(AFD).
Se pueden crear los AFD directamente a partir de la expresión regular.
El analizador léxico utiliza la maquina discriminadora determinista.
El tratamiento de errores en nivel léxico es muy simple.
Se pueden emplear las ideas de los analizadores léxicos para facilitar el
tratamiento de ficheros de texto.
Ejemplo: implementar en LEX, un analizador léxico para:
Menor→ <
Mayor→ >
Menor Igual → <=
Mayor Igual → >=
Igual → =
Distinto → <>
Letra → a|b|...|z|A|B|....|Z digito→0|1|...|9
Identificador → letra(letra|digito)*
ConstEntera → digito digito*
Comportamiento Deseado:
Antes del analizador léxico -> v0<>27 segundos = 1000
Después del analizador léxico:
(IDENTIFICADOR, v0)
(DISTINTO,)
(CONSTENTERA,27)
(IDENTIFICADOR, segundos)
(IGUAL,)
(CONSTENTERA ,1000)
Referencias
(s.f.). Obtenido de https://www.clubensayos.com/Ciencia/Tabla-De-

Tokens/2619832.html
(s.f.). Obtenido de
https://lenguajesyautomatasblog.wordpress.com/2017/05/15/unidad-5-
analisis-lexico/
(s.f.). Obtenido de http://cgosorio.es/Docencia/PLFolder/UD2/AnaLex.pdf
(s.f.). Obtenido de http://webdiis.unizar.es/~ezpeleta/lib/exe/fetch.php?
media=misdatos:compi:2bis.introflex.pdf
(s.f.). Obtenido de https://jazieljosuecelis.wordpress.com/2015/05/25/aplicaciones-
de-un-analizador-lexico/

Lenguajes y Autómatas L Unidad V

Cargado por

Copyright:

Formatos disponibles

Lenguajes y Autómatas L Unidad V

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Lenguajes y Autómatas L Unidad V

Cargado por

Copyright:

Formatos disponibles

TECNOLÓGICO NACIONAL DE MÉXICO

INSTITUTO TECNOLÓGICO DE CHIHUAHUA II

5.2 Componentes léxicos, patrones y lexemas

Lexemas: Una secuencia de caracteres de entrada que comprenda un solo

5.3 Creación de Tabla de tokens.

5.4 Errores léxicos

5.5 Generadores de analizadores léxicos

(s.f.). Obtenido de https://www.clubensayos.com/Ciencia/Tabla-De-

También podría gustarte