Esta sección trata algunos aspectos de la eficiencia relacionados con el manejo de los buffers de entrada, esto toma importancia cuando se busca un esquema de un pre análisis en la entrada para identificar los componentes léxicos, la finalidad de esto es utilizar técnicas que aumenten la velocidad de analizador léxico.
1. DEFINICION DE TERMINOS
Analizador léxico
Lee la secuencia de caracteres del programa fuente, carácter a carácter, y los agrupa para formar unidades con significado propio, ósea componentes léxicos o tokens en ingles. Estos componentes léxicos representan: palabras reservadas: if, while, do, identificadores asociados a variables, nombres de funciones, operadores: = * + - / == > < & ! =. . ., etc.
Buffer de datos
Un buffer en informática es un espacio de memoria, en el que se almacenan datos para evitar que el programa o recurso que los requiere, ya sea hardware o software, se quede sin datos durante una transferencia.
Un ejemplo de esto último ocurre en una comunicación telefónica, en la que al realizar una llamada esta se almacena, se disminuye su calidad y el numero de bytes a transferidos, y luego se envían estos datos modificados al receptor.
Pueden ser implementados por software o hardware, aunque la gran mayoría son del primer tipo. Normalmente se usan cuando la frecuencia de transferencia de datos es distinta a la de procesado. Estas diferencias temporales de transmisión son normalmente ajustadas mediante la implementación de un algoritmo con cola (o estructura de tipo FIFO) en memoria, para así escribir datos en la cola a una frecuencia y leerlos a otra.
Se puede ejemplificar la función de un buffer utilizando ésta metáfora: Un buffer es como tener dinero en el banco (buffer), un trabajo (entrada) y unos gastos fijos (salida). Si tienes un trabajo inestable, mientras tengas ciertos ahorros, puedes mantener tus gastos fijos sin problemas, e ir ingresando dinero cuando puedas según vas trabajando. Si los ahorros son pequeños, en seguida que no tengas trabajo, no vas a poder acometer los gastos fijos.
Diferencias con la caché:
Una caché puede ser usada a veces como un buffer, y viceversa. Sin embargo, una caché opera con el supuesto de que los mismos datos van a ser utilizados múltiples veces, que los datos escritos serán leídos en un periodo corto de tiempo, o teniendo en cuenta la posibilidad de múltiples lecturas o escrituras para formar un único bloque más grande. Su premisa básica es reducir los accesos a los almacenamientos de nivel más bajo, los cuales son bastante lentos.
Una caché de disco o archivo de caché guarda las estadísticas de los datos almacenados en él y proporciona datos con un tiempo máximo de espera en modos de escritura en diferido. Un buffer, por el contrario, no hace nada de esto, sino que es utilizado normalmente en entrada, salida y a veces, almacenamiento temporal de datos que se enrutan entre distintos dispositivos o que van a ser modificados de manera no secuencial antes de ser escritos o leídos de manera secuencial.
2. MANEJO DE LOS BUFFERS DE ENTRADA
Hay tres métodos generales de implantación de un analizador léxico:
1. Utilizar un generador de analizadores léxicos, como el compilador LEX, para producir el analizador léxico a partir de una especificación basada en expresiones regulares. En este caso, el generador proporciona rutinas para leer la entrada y manejarla con buffers.
Nota Personal:
LEX y FLEX no son lo mismo LEX es un software utilizado para generar componentes léxicos para UNIX y como sobran UNIX es un sistema operativo no libre por lo tanto este LEX se convierte en un programa licenciado, FLEX es la versión libre de este sistema , FLEX estas desarrollado bajo licencia GNU la cual lo hace un software libre pero con restricciones, GNU es una licencia orientada a proteger la libre distribución modificación y uso del software pero a su vez lo protege de intentos de apropiación que lleguen a quitar libertades. GNU es juego de palabras que al final significa IS NOT UNIX su creador recomienda pronunciarlo como ÑU igual que el animal por eso el logo es la cabeza de este animal los que usaron FLEX la pudieron ver, pero al final todos lo pronunciamos como queramos.
2. Escribir el analizador léxico en un lenguaje convencional de programación de sistemas, utilizando las posibilidades de entrada y salida para leer la entrada.
3. Escribir el analizador léxico en lenguaje ensamblador y manejar explícitamente la lectura de la entrada.
Estas tres opciones se relacionan en orden de dificultad reciente para el encargado de la implantación. Aunque los enfoques más difíciles de implementar se convierten en los más rápidos y ya que el analizador léxico no es la más complicada pero si es la única etapa que lee el código fuente esto se puede traducir en tiempo.
3. PAREJAS DE BUFFERS
Como se puede consumir mucho tiempo moviendo caracteres, se han desarrollado técnicas especializadas en el manejo de buffers para reducir el número de operaciones necesarias para procesar un carácter de entrada.
Se utiliza un buffer dividido en dos mitades de N caracteres cada una (por lo general N es el número de caracteres en un bloque de disco, por ejemplo, 1024 ó 4096). Se leen N caracteres de entrada en cada mitad del buffer con una orden de lectura, en vez de invocar una instrucción de lectura para cada carácter de entrada. Si quedan menos de N caracteres en la entrada, entonces se lee un carácter especial eof, que marca el final del archivo fuente.
Se mantienen dos apuntadores al buffer de entrada. La cadena de caracteres entre los dos apuntadores es el lexema en curso.
Al principio, los dos apuntadores apuntan al primer carácter del próximo lexema que hay que encontrar.
Uno de ellos, llamado apuntador delantero, examina hacia delante hasta encontrar una concordancia con un patrón. Una vez determinado el siguiente lexema, el apuntador delantero se coloca en el carácter de su extremo derecho. Después de haber procesado el lexema, ambos apuntadores se colocan en el carácter situado inmediatamente después del lexema.
Cuando el apuntador delantero está a punto de sobrepasar por la marca intermedia del buffer, se llena la mitad derecha con N nuevos caracteres de entrada.
Cuando el apuntador delantero está a punto de sobrepasar el extremo derecho del buffer, se llena la mitad izquierda con N nuevos caracteres de entrada y el apuntador delantero se regresa al principio del buffer.
(Este y el siguiente algoritmo lo escribí interpretando la información que encontré no se puede tomar como base porque no está probado y creo que hasta se puede mejorar en mucho)
If (delantero = final de la primera mitad){
Recargar la segunda mitad;
Delantero = delantero + 1;
}
If (delantero = final de la segunda mitad){
Recargar la primera mitad;
Pasar delantero al principio de la primera mitad;
}
If(delantero!= final de la primera mitad && delantero!=final de la segunda mitad){
Delantero=delantero+1;
}
4. CENTINELAS
El centinela se define como un carácter especial que no puede ser parte del programa fuente. una elección natrual es eof (fin de archivo en ingles), lo que se hace es poner un carácter eof al final de cada mitad para evitar estar haciendo la comprobación con cada lexema, como se encuentran N caracteres de entrada entre los simbolos eof, el promedio de pruebas por cada carácter de entrada es próximo a 1
Delantero=delantero +1;
If (delantero = eof){
If (delantero = final de la primer mitad){
Recargar la segunda mitad;
Delantero=delantero+1;
}
If(delantero=final de la segunda mitad){
Recargar la segunda mitad;
Delantero=delantero+1;
}
If(delantero!= final de la primera mitad && delantero!=final de la segunda mitad){
//eof;
Terminar el análisis léxico
}
}
Fuente de informacion: Wikipedia y Libro Compiladores Principios Tecnicas Y Herramientas - Aho Sethi Ullman Pearson
No hay comentarios:
Publicar un comentario