| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III Introducción 3.1 Token y Lexemas 3.2 Algoritmo de los dos Buffers 3.3 Expresiones regulares

3.4 Definición y ejemplos de AFN

3.5 Definición y ejemplos de AFD

3.6 Construcción de un AFN a partir de una expresión regular

3.7 Conversión de un AFN a AFD (Construcción de subconjuntos)

3.8 Lenguaje LEX

3.9 Escritura de Programas LEX

UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

3.2 Algoritmo de los dos Buffers

> El analizador léxico es la única fase del compilador que lee el programa fuente carácter a carácter, lo que lo hace ser lo más fácil y lento del compilador.
> Una forma de hacer más eficiente este proceso es utilizar el algoritmo de los dos buffers que resulta útil cuando es necesario un pre-análisis en la entrada para identificar los componentes léxicos.

> El algoritmo de los dos buffers utiliza un buffer para la lectura de los caracteres dividido en dos mitades de N caracteres cada una, donde N es el número de caracteres en un bloque de disco. Se mantienen dos apuntadores al buffer de entrada, uno es llamado delantero y el otro comienzo del lexema.

> Esquema del buffer de entrada con el algoritmo de los dos buffers:

> Si quedan menos de N caracteres de entrada se utiliza el carácter especial “eof” para marcar el final del archivo fuente como se muestra en la siguiente figura:

> La cadena de caracteres entre los dos apuntadores es el lexema en curso. Al principio los dos apuntadores apuntan al primer carácter, donde el apuntador delantero examina hacia delante hasta encontrar una concordancia con un patrón. Una vez determinado el lexema, el apuntador delantero se coloca en el carácter de su extremo derecho.

> Después se procesa el lexema y ambos apuntadores se colocan en el carácter situado inmediatamente después del lexema. Con este esquema se pueden considerar los comentarios y espacios en blanco como patrones que no producen componentes léxicos.

> 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.

> El algoritmo para avanzar el apuntador delantero es el siguiente:

> if delantero está al final de la primera mitad
> then begin recargar la segunda mitad;
> delantero: = delantero + 1
> end
> else if delantero está al final de la segunda mitad
> then begin recargar la primera mitad;
> pasar delantero al principio de la 1ª mitad
> end
> else delantero := delantero + 1;

> Este esquema limita la cantidad de caracteres de preanálisis, lo que puede imposibilitar el reconocimiento de los componentes léxicos cuando la distancia recorrida por el apuntador delantero sea mayor que el tamaño del buffer. Como por ejemplo la siguiente declaración:

Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello