UNIDAD II.-Analizador léxico.

2.1.-Funciones del analizador léxico

El analizador léxico constituye la primera fase del compilador.

La función principal del  analizador es leer los caracteres de entrada del programa fuente y verificar a qué tipo de componentes léxicos pertenecen, esta información es utilizada después por el analizador sintáctico. 

Funciona de la siguiente manera: lee un  carácter de izquierda a derecha hasta encontrar una coincidencia con un patrón, una vez que ya encontró el patrón guarda este elemento en la tabla de símbolos y regresa por otro componente léxico.

Además de lo anterior, el analizador léxico, identifica y elimina todos los espacios  en blanco y comentarios que haya en el programa fuente así como también relacionar todos los errores que se den durante el análisis con los elementos del programa fuente.

2.2.-Lexemas, patrones y tokens (componentes léxicos)

Lexema: también identificadas como cadenas de caracteres, son todas las cadenas del programa fuente que tiene un significado en de acuerdo con un patrón definido por la sintaxis del lenguaje para un componente léxico.

Patrón: conjunto de reglas que describen a cada uno de los componentes léxicos de acuerdo a ciertas características específicas que lo identifiquen.

Token (componente léxico): unidad lógica generada por el analizador léxico, representa una información determinada, puede ser un operando, un operador, una función, etc., y corresponden a un lexema.

Ejemplos de componentes léxicos o tokens son: palabras reservadas, operadores de relación, comparación, lógicos, etc.

Ejemplos:

Componente léxico	Lexemas	Descripción informal
Main	Main	Programa principal/Main
If	If	Sentencia de bifurcación selectiva
For	For	Estructura de selección repetitiva en la cual se conoce el numero de iteraciones
Int	Int	Conjunto de números enteros
Char	Char	Tipo de dato que representa un carácter cualquiera  de la A-Z, a-z o números
Librerías	Iostream.h, conio.h,stdio.h	Conjunto de paquetes o programas con funciones predefinidas
Operadores aritméticos	+,-,*,/	Conjunto de operadores que permiten realizar operaciones matemáticas

2.3.-Manejo de buffers de entrada

Un buffer es un espacio de almacenamiento temporal de entrada o salida de datos cuando esta está en transferencia. En el análisis léxico se utiliza un buffer para realizar la compilación en menos tiempo y además para no consumir toda la memoria durante las comparaciones. Existen 2 técnicas de comparación del análisis léxico cuando usa el buffer, y son:

Técnica de pareja de buffer.

Aquí se divide al buffer en 2 partes iguales, se tienen además 2 apuntadores que recorren el buffer, uno de ellos denominado delantero que va recorriendo el buffer posición por posición hasta encontrar una coincidencia con un patrón y otro llamado lexema que recorre el buffer procesando la información de los lexemas.

La técnica consiste en que primero se llena una mitad del buffer, el apuntador delantero comienza a recorrer el buffer  seguido por el apuntador lexema, hasta encontrar coincidencias con un patrón  y así hasta llegar al final de la primera mitad, cuando se termina la primera mitad, se llena la segunda mitad del buffer y los apuntador es delantero y lexema se posicionan al inicio de la segunda mitad y realizan el mismo proceso que se describió anteriormente.

Cuando se llega al final de la segunda mitad,  se llena de nuevo la primera mitad y los apuntadores pasan al inicio de esta, este proceso se repite hasta encontrar el fin de archivo (eof).

Técnica del centinela.

El buffer se divide en 2 mitades, se usan 2 apuntadores a igual que en la técnica anterior. Funciona de manera similar al de pareja de buffer pero con una pequeña diferencia, aquí cada que el apuntador delantero avanza se verifica que el buffer aun no termina, esto es si ha encontrado la señal de fin del buffer (eob), de ser así se llena la segunda mitad del buffer y los apuntadores pasan a la segunda mitad, con esta señal se reduce tiempo de verificar si se ha llegado al límite del buffer, utilizando 2 señales de terminación, una para cada buffer.

2.4.-Especificación de los componentes léxicos.

Los desarrolladores de compiladores para identificar la concordancia entre lexemas y componentes léxicos requieren de un esquema que defina al componente léxico.

Expresión regular.

Notación o representación para especificar patrones para los componentes léxicos.

Cada patrón concuerda con una serie de cadenas (lexema) de modo que la expresión regular sirve como nombre para un conjunto de cadenas.

Cadenas y lenguajes.

Ø  Alfabeto o clase de carácter: cualquier conjunto finito de símbolos.

Ø  Cadena (frase o palabra): secuencia finita de símbolos  formados por elementos del alfabeto.

Ø  Lenguajes: conjunto de cadenas de un alfabeto fijo.

Operaciones aplicadas a los lenguajes.

·         Unión: L UM  (elementos  que están en L y en M).

·         Concatenación: LM (elementos de L seguidos de elementos de M).

·         Cerradura de Klenne: L^* (cero o más concatenaciones de L).

·         Cerradura positiva: L⁺ (1 o más de concatenaciones de L).

Operadores p/definir componentes léxicos.

()àPara agrupar símbolos.

|àPara elegir entre 2 o más alternativas.

?à0 (cero) ó un caso.

Conjuntos no regulares.

Aquellos lenguajes que no se pueden describir con una expresión regular.

Ejemplos:

1.- Componente léxico: Identificador.

Patrón: letra seguida de letras o dígitos.

Ejemplos de lexemas: clave, num1, num2, a123, x, y.

Expresión regular.

                identàletra (letra|dígito) ^*   

                letraàa|b|c|…|z|A|B|C|…|Z

                dígitoà0|1|2|3|4|5|6|7|8|9

Nota: una expresión regular se construya a partir de expresiones regulares más simples, hasta llegar a símbolos del alfabeto.

2.- Componente léxico: números enteros.

Patrón: cualquier número sin punto decimal.

Expresión regular.

num_entàdígito dígito^*

dígitoà0|1|2|3|4|5|6|7|8|9

num_entàdígito ⁺

dígitoà0|1|2|3|4|5|6|7|8|9

  

3.- Componente léxico: número reales positivos y negativos.

Lexemas de ejemplo: -179.12, +12.0, +0.735, -2385.72

Patrón: cualquier número con punto decimal positivo o negativo.

Expresión regular.

num_realà(+|-) dígito⁺.dígito⁺

dígitoà0|1|2|3|4|5|6|7|8|9

4.- Para representar la expresión regular para palabras reservadas del lenguaje, se utiliza la misma palabra reservada.

mainàmain

ifàif

elseàelse

getchàgetch

intàint

floatàfloat

doubleàdouble

clrscràclrscr

whileàwhile

foràfor

El analizador léxico aparte de identificar lexemas que corresponden a un componente léxico, elimina del código fuente:

Espacios en blanco

Comentarios.

Por lo que debe existir una representación (expresión regular) que marque esta concordancia.

Componente léxico: espacios en blanco

Patrón: espacios en blanco entre lexemas que pueden ser: secuencias nulas de espacios en blanco, caracteres TAB (sangría) y caracteres de nueva línea (end).

Expresión regular.

Esp. Blancoàblanco|TAB|línea_nueva

Ebàesp_blanco⁺

Blancoà_

TABà_ _ _ _

Línea_nuevaà”enter”

Componente léxico: comentarios

Patrón: cualquier nota escrita después de los signos // hasta terminar el renglón.

Expresión regular.

Comentarioà//(letra|digito|sign_punt⁺|eb)

LetraàA|B|C|D|…|Z|a|b|c|…|z

Digitoà0|1|2|3|4|5|6|7|8|9|

Sign_puntà$|#|,|;|!|…|&

Ebàesp_blanco

Esp_blancoàblanco|TAB|nueva_linea