UNIDAD 2: ANÁLISIS LÉXICO

ENTRANDO EN MATERIA, EN ESTA UNIDAD SE HABLA ACERCA DE LO QUE ES EL ANÁLISIS LÉXICO, LO QUE SON LOS LEXEMAS, UN PATRON,EL MANEJO DEL BUFFERS DE ENTRADA...

FUNCIÓN DEL ANÁLISIS LÉXICO-GRÁFICO
LEXEMAS, PATRONES Y TOKENS
MANEJO DE BUFFERS DE ENTRADA
ESPECIFICACIÓN DE LOS COMPONENTES LÉXICOS
RECONOCIMIENTO DE COMPONENTES LÉXICOS

FUNCIÓN DEL ANÁLISIS LÉXICO-GRÁFICO

El analizador lexicográfico, o explorador, es la parte del compilador que lee el programa fuente, carácter a carácter, y construye a partir de éste unas entidades primarias llamadas tokens. Es decir, el analizador lexicográfico transforma el programa fuente en tiras de tokens.
Función principal del analizador léxico
Leer los caracteres de entrada y elaborar como salida una secuencia de componentes léxicos que utiliza el analizador sintáctico para hacer el análisis.

Funciones secundarias.
• Eliminar del programa fuente comentarios y espacios en blanco (caracteres de espacio en blanco, caracteres TAB, caracteres de nueva línea).

• Relacionar los mensajes de error con el lenguaje fuente.

LEXEMAS, PATRONES Y TOKENS

Componente léxico (token): Son las unidades lógicas que genera el analizador léxico. Es el conjunto de cadenas de entrada que produce como salida el mismo componente léxico. Cada token es una secuencia de caracteres que representa una unidad de información en el programa fuente.

Los componentes léxicos más comunes son los siguientes:
 palabras clave o reservadas
 operadores aritméticos
 operadores relacionales
 operadores lógicos
 operador de asignación
 identificadores
 constantes
 cadenas
 literales
 signos de puntuación
 librerías

Lexema: Representan cadenas de caracteres en el programa fuente que se pueden tratar juntos como una unidad léxica. Un lexema es una secuencia de caracteres en el programa fuente con la que concuerda el patrón para un componente léxico.

Patrón: Regla que describe el conjunto de lexemas que pueden representar a un determinado componente léxico en los programas fuente.

Atributos de los componentes léxicos: 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.

MANEJO DE BUFFERS DE ENTRADA

Buffer: Área del almacenamiento primario destinada a contener datos durante transferencia de entrada salida. Durante la entrada los datos son cargados en el buffer, al terminar la transferencia ya se puede trabajar con ellos.

Técnica de “Pareja de buffers”
En la técnica de pareja de buffers se utiliza un buffer dividido en dos mitades de N caracteres cada uno:

Donde:
N  número de caracteres en un bloque de disco
eof  marca el final del archivo fuente

Al principio, los dos apuntadores apuntan al primer carácter del próximo lexema que hay que encontrar:
1. El 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.
2. El APUNTADOR DE LEXEMA se queda al inicio del lexema y lo procesa.
Después de haber procesado el lexema, ambos apuntadores se colocan en el carácter situado inmediatamente después del lexema.

Técnica de “Centinelas”
Si se utiliza la pareja de buffers, cada vez que se mueva el apuntador delantero se debe comprobar si se ha salido de una mitad del buffer, si así ocurriera se deberá cargar la segunda mitad. Es decir, para hacer avanzar el apuntador se realizan dos pruebas.
Se pueden reducir estas dos pruebas a una si se amplía cada mitad del buffer para admitir un carácter centinela (carácter especial que no puede ser parte del programa fuente – eof) al final.

ESPECIFICACIÓN DE LOS COMPONENTES LÉXICOS

Expresiones regulares
Notación o representación para especificar patrones para un componente léxico. Cada patrón concuerda con una serie de cadenas, de modo que las expresiones regulares servirán como nombres para conjuntos de cadenas.

Cadenas y lenguajes
Alfabeto o clase de carácter: Denota cualquier conjunto finito de símbolos (letras o caracteres).
Conjunto {0,1} alfabeto binario
a, b, c, d, e, ... , z alfabeto
Código ASCII, EBCDIC alfabetos del computador
Cadena (frase o palabra): Es una secuencia finita de símbolos tomadas de un alfabeto.
Lenguaje: Se refiere a cualquier conjunto de cadenas de un alfabeto fijo.

También se puede extender el operador de “exponenciación” a los lenguajes definiendo L° como { }

Sea L el conjunto {A, B, C, D, ...,Z, a, b, c, d,...,z} y D el conjunto {0, 1, 2, ..., 9}. Algunos ejemplos de nuevos lenguajes creados a partir de L y D:
1. LUD es el conjunto de letras y dígitos.
2. LD es el conjunto de cadenas que consta de una letra seguida de un dígito.
3. L4 es el conjunto de todas las cadenas de cuatro letras.
4. L* es el conjunto de todas las cadenas de letras, incluyendo la cadena vacía ( ).
5. L(LUD)* es el conjunto de todas las cadenas de letras y dígitos que comienzan con una letra.
6. D+ es el conjunto de todas las cadenas de uno o más dígitos.

Las expresiones regulares se utilizan para describir los componentes léxicos de un lenguaje o tokens. Las expresiones regulares utilizan varios tipos de operadores para definir los componentes léxicos:
• Paréntesis. Para agrupar símbolos
• Operación concatenación. Se permite la concatenación de cadenas.
• Operación alternativa. Se representa por |, y permite la elección entre dos o más alternativas.

Componentes léxicos:

a) Identificador: (Letra seguida de letras y dígitos). Se puede definir a partir de dos símbolos: letra y dígito.
letra (letra|dígito)*

b) Constante entera
(sin signo) digito+
(con signo) (+|-) digito+

c) Constante de punto flotante sin exponente
(+|-) digito+.digito+

Abreviaturas en la notación

1. Uno o más casos de. +

2. Cero o un caso. ?

Conjuntos no regulares
Aquellos lenguajes que no se pueden describir con ninguna expresión regular.

RECONOCIMIENTO DE COMPONENTES LÉXICOS

Consideremos el siguiente formato gramatical:
Prop  if expr prop
| if expr prop else prop
| €

expr  termino op_rel termino
| termino

termino  id | num

*Donde if, else, opr_rel, id, num, generan conjuntos de cadenas dadas por la siguiente definición regular:


If  if
else  else
op_rel < | <= | == | >= | > | < >
id  letra (letra|digito)*
num  digitos fraccion_optativa exponente_optativo
letra  a|b|c|d| ... |z|A|B|C|...|Z
digito  0|1|2|3|...|9
digitos  digito digito*
fraccion_optativa  .digitos|€
exponente_optativo  (E(+|-|€) digitos)|€

* El analizador léxico reconoce las palabras clave del lenguaje (if, else)
* op_rel, id, num, los representa por su expresión regular.