Unidad V Análisis Léxico

Instituto Tecnológico SuperiorDe Coatzacoalcos

2015

M.A.S.C. Arturo Iván Grajales Vázquez.

Competencia a desarrollar.

Construir un analizador léxico a partir de un lenguaje de programación o un analizador léxico (p. e. Flex, Lex, JavaCC).

Subtemas.

5.1 Funciones del analizador léxico5.2 Componentes léxicos, patrones y lexemas5.3 Creación de Tabla de tokens5.4 Errores léxicos5.5 Generadores de analizadores Léxicos5.6 Aplicaciones (Caso de estudio)

Introducción al analizador

Léxico

Analizador léxico o Scanner.

La fase del análisis lexicográfico de un compilador agrupa secuencia de caracteres en categorías. Aunque esto se conoce también como rastréo, realmente podemos distinguir dos tareas separadas:

Un rastreador mueve un apuntador a través de la entrada un carácter a la vez para hallar cadenas continuas de caracteres, las cuales constituyen elementos textuales individuales ( palabras), y clasificadas cada una de acuerdo con su tipo.

El filtro descarta algunos de los tokens encontrados por el rastreador ( tal vez espacios y comentarios), determina cuáles otros son símbolos reservados ( quizá palabras clave u operadores), y coloca el texto de los restantes en la tabla de nombre.

El analizador lexicográfico pasa al analizador sintáctico el tipo de token, más el valor real de éste. En ocasiones, el valor es un apuntador a la tabla que contiene el valor. Puede haber tablas separadas para nombres, constantes numéricas, cadenas de caracteres constantes, y operadores, o puede hacer una tabla que incluya todo lo anterior.

Estructura que muestra el sitio que ocupa el analizador léxico dentro del compilador.

Analizador lexicográfico

Analizador Sintáctico

Analizador semántico

Optimización

PreparaciónPara la

Generaciónde código

Generacióndel código

Tokens

Manejo de tablas

•Tabla de símbolo.

• Tabla de literales.

• Tabla de ciclos iterativos

• Tabla de representa- ción intermedia

Manejo de errores E/S

Tokens

Los tokens ( componentes léxicas ) son las unidades léxicas básicas del mismo modo en que las palabras y los signos de puntuación son las unidades básicas de una oración en ingles. Los tokens varían de lenguaje en lenguaje, e incluso de compilador en compilador para el mismo lenguaje. Algunos ejemplos de tokens son:

La palabra clave.

La constantes.

El identificador.

El operador.

Puntuación.

Problema del análisis lexicográfico

Podemos describir el problema del análisis lexicográfico como:

Dada una cadena de caracteres, divídase en una cadena de tokens:

Tokens=( tipo, valor)

Al tipo de un tokens a menudo se llama clase; los carácter reales se conocen como lexema. Existen tres formalismo o modelos comunes para la descripción de los tipos de tokens:

Expresiones regulares:- La expresiones regulares describen los tokens como el conjunto de cadenas permitidas en un lenguaje.

Diagramas de transición :- Los diagramas de transición describen los tokens como cadenas permitidas que toman el diagrama desde un estado inicial hasta un estado final.

Gramáticas lineales:- Las gramáticas lineales describen los tokens como las cadenas generadas por una gramática en una forma especial (Llamadas también gramáticas regulares ).

5.1. Funciones del Analizador Léxico

Funciones principales de los analizadores lexicográfico.

Existen tres funciones principales para un analizador lexicográfico a medida que va hallando tokens:

Utilidades de caracteres y manejo de línea:- Se establece un programa mediante un formato uniforme y compacto, el analizador lexicográfico puede eliminar información innecesaria como los comentarios. También procesa directivas de control del compilador ( como la petición para crear un archivo del listado de un programa ), introduce información preliminar ( como los nombres definidos por el usuario) en tablas y formatos y lista el programa.

Prueba de predicado: - Tiene como finalidad verificar la membresía de un conjunto de caracteres. Para un predicado su objetivo es regresar un valor de verdadero siempre que se cumplan la condición establecida por el. Las implementaciones de estas utilidades dependen del lenguaje en que se haya escrito al analizador lexicográfico. Por ejemplo:

Esletra ( x ) : “A” <= x y x <= “Z”

El predicado Esletra aquí prueba sólo letras mayúsculas ( y presume que todas las mayúsculas están codificadas en forma consecutivas ).

Acciones : - En general, hay una acción para cada tipo de token. En algunos casos, podemos necesitar una acción para cada carácter rastreado. Por ejemplo:

Cuando se rastrean los dígitos en un número, podríamos tener que convertir la secuencia de caracteres a un número.

5.2. Componentes léxico, patrones y lexemas

En la fase de análisis, los términos componentes léxicos (token), patrón y lexema se emplean con significados específicos. Un analizador léxico, inicialmente lee los lexemas y le asigna un significado propio.

Componente léxico es la secuencia lógica y coherente de caracteres relativo a una categoría: identificador, palabra reservada, literales (cadena/numérica), operador o carácter de puntuación, además de que un componente léxico puede tener uno o varios lexemas.

Patrón es una regla que genera la secuencia de caracteres que puede representar a un determinado componente léxico (expresión regular).

Lexema es una cadena de caracteres que concuerda con un patrón que describe un componente léxico (valor de cadena).

Ejemplo de una cadena de código: const pi = 3.1416;

Lexemas Componentes léxico Patrón

const const Const

= Relacion <o<=o= o <> o > o >=

pi Identificador Letra seguida de letras o números

3.1416 numero Cualquier literal numerica

“hola mundo” literal Caracteres entre comillas

El analizador léxico recoge información sobre los componentes léxicos en sus atributos asociados. Los tokens influyen en las decisiones del análisis sintáctico, y los atributos, en la traducción de los tokens. En la practica los componentes léxicos suelen tener solo un atributo. Para efectos de diagnostico, puede considerarse tanto el lexema para un identificador como el numero de línea en el que se encontró por primera vez. Esta información puede ser almacenada en la tabla de símbolos para el identificador (estructura de datos).

Para la cadena E=M*C**2 de ejemplo, los componentes léxicos y los valores de atributo

asociado son:

<identificador, atributo para el símbolo E> <op_asignacion> <identificador, atributo para el símbolo M> <op_multiplica> <identificador, apuntador al símbolo C> <op_exponente> <numero, atributo valor 2>

Tome en cuenta que ciertas parejas no necesitan un valor de atributo. Los atributos relacionados con ese token deberán ser conservados y transferidos a alguna estructura de datos para que sean empleados en las siguientes etapas del análisis

Diagrama de transición.Los diagramas de transición describen las acciones

necesarias para reconocer un token. Formalmente, un diagrama de transición es una gráfica dirigida con arcos etiquetados. Y estos se construyen mediante los siguientes símbolos:

Símbolo DescripciónUn circulo simple representa a los nodos y estos a su vez se denominan “ estados “.

Un flecha representa a los arcos que van etiquetados con caracteres de entrada que indican “ Caracteres entrada” que pueden presentarse antes y después de cada estado.

Un circulo doble representa un estado final o de aceptación.

Siguiendo un diagrama de transición desde un estado inicial hasta un estado final se confirma que los caracteres en el token corresponden exactamente para los que el diagrama de transición fue diseñado.

Por ejemplo:

Este diagrama de transición permite detectar un identificador ( nombre de las variables ) se describe con una letra seguida por un número arbitrario de letras o dígitos.

1 2 3

4

No es

letra

Letra

Letra ódígito

No es letra o dígito

Autómatas finitos.Los diagramas de transición son una instrumentación de

un modelo formal denominado autómatas finitos, conocidos también como maquinas de estado finito o ( con menos frecuencia en la actualidad) máquinas secuenciales.

Los autómatas finitos vienen diferentes tipos:

No determinísticos (NFA, por su siglas en ingles).

Determinísticos (DFA, por la misma razón ).

Determinísticos mínimos.

Ejemplo : Autómata finito no determinístico.

0 1 2$

$

Letra ó dígito, $

Ejemplo : Automáta finito determinístico.

0 1 2$

$

Letra ó dígito

3

$

Letra ó dígito

Letra ó dígito

Ejemplo: Este automáta finito permite definir datos numéricos como son: enteros, reales y científicos.( parte de un analizador léxico).

q0 q1 q2 q3 q4 q5 q6 q7

ε|+|- Dígito

Dígito

. Dígito

Dígito

E|e ε|+|- Dígito

Dígito

E|e

5.3.-Creacion de Tablas de tokens

Tablas de Símbolos.

Es una estructura de datos que contiene un registro por cada identificador, con los campos para los atributos del identificador. La estructura de datos permite encontrar rápidamente el registro de cada identificador y almacenar o consultar rápidamente datos de ese registro.

Se examina la tabla de símbolos cada vez que se encuentra un nombre en el texto fuente. Si se descubre un nombre nuevo o nueva información sobre un nombre ya existente, se producen cambios en la tabla.

Muchos compiladores establecen una tabla en el momento del análisis lexicográfico y la llena con la información del último símbolo durante el análisis semántico, cuando se conoce más información acerca del símbolo.

Operaciones de la tabla de símbolos.

Las principales operaciones de las tablas de símbolos son :

Operación Inserción : - Se utiliza para almacenar la información proporcionada por las declaraciones de nombre cuando se procesan estas declaraciones.

Operación Búsqueda:- Es necesaria para recuperar la información asociada con un nombre cuando éste se utiliza en el código asociado.

Operación Eliminación:- Es necesaria para eliminar la información proporcionada por una declaración cuando está ya no se aplica.

Las propiedades de estás operaciones son dictadas por las reglas del lenguaje de programación que se está traduciendo. En particular, la información que se necesita almacenar en la tabla símbolo está función de la estructura y propósito de las declaraciones.

Atributos de símbolos.

Los atributos son independientes del lenguaje, pero podría incluir los caracteres en el nombre, su tipo, e inclusive información de asignación de almacenamiento tal como cuántos bytes ocupara el valor. Con frecuencia, el número de línea donde se declara el nombre que se registra, así como las líneas donde se hace referencia al símbolo. Si el lenguaje contiene ámbitos, como la mayoría los tiene, entonces el ámbito se introduce con frecuencia en la tabla de símbolos.

La clase y los atributos relacionados.Un nombre en un programa puede representar una

variable, un tipo, una constante, un parámetro, un registro, un campo de registro, un procedimiento o función, un arreglo, una etiqueta o un archivo, por nombrar sólo unas cuantas posibilidades. Éstos son valores para un atributo llamado “clase” de símbolo. Por supuesto, no todos los lenguajes tienen todas estas posibilidades o pueden describirse empleando otros términos.

Atributo de ámbito.

Los lenguajes estructurados en bloques permiten de declaraciones; es decir, un nombre puede redefinirse para ser de una clase diferente. Un problema semejante ocurre cuando procedimientos o paquetes son anidados redefinen un nombre. El ámbito del nombre se limita al bloque o procedimiento en el que se defina. El ámbito, representado quizás el número, es entonces un atributo para el nombre. Una técnica alternativa es tener una tabla de símbolos por separada para cada ámbito.

Atributos especiales.

Los lenguaje de propósito específicos a menudo tienen nombres especiales. Los lenguajes orientados a objetos, por ejemplo, pueden tener nombres de métodos, nombres de clase y objeto, así como los tipos usuales. El ámbito es de particular importancia en los lenguajes orientados a objetos, porque los nombre a menudo heredan operaciones desde la superclases que las contienen.

Otros atributos.Otros atributos para nombres incluyen los caracteres

reales en el identificador del nombre, el número de línea en el programa fuente donde este nombre se declara y los números de línea donde ocurren las referencias.

Ejemplo de un programa que será empleado para construir su tabla de símbolo.

1 PROGRAMA Principal

2 Global a,b

3 PROCEDIMIENTO P (PARAMETRO x )

4 LOCAL a

5 COMIENZA { P }

6 …..a……

7 …..b……

8 …..x…..

9 TERMINA { P }

10 COMIENZA { PRINCIPAL }

11 Llama P (a)

12 TERMINA { PRINCIPAL }

Otros atributos

Caracteres

Clase Ámbito Declaración

Referencia otros

Principal Programa 0 Línea 1

a Variable 0 Línea 2 Línea 11

b Variable 0 Línea 2 Línea 7

P Procedimiento

0 Línea 3 Línea 11 1 parámetro, x

x Parámetro 1 Línea 3 Línea 8

a Variable 1 Línea 4 Línea 6

Tabla de símbolo obtenida del programa anterior.

5.4.-Errores léxico

Manejo de errores.

Los programadores a menudo escriben programas incorrectos, y un buen compilador deberá ayudar al programador a identificar y localizar errores. Es más, considerar desde el principio el manejo de errores puede simplificar la estructura de un compilador y mejorar su respuesta a los errores.

La mitad del espacio ocupado por el código de muchos compiladores se dedica al manejo de errores. La detección, informe y recuperación de errores son mucho más notorios para el usuario promedio que la rapidez de un compilador o la rapidez del código emitido. Existen realmente cuatro facetas del manejo de errores :

Creación de errores. Detección de errores. Informe de errores. Recuperación de errores.

Creación de errores.EL diseño de un lenguaje afecta la clase de errores que

pueden ocurrir, y es la manera más fácil de cometer los errores.

Cuando un programador no completó entre comillas la cadena definida y se dirigió a una nueva línea. De nueva cuenta esto es un error muy fácil de cometer. Por ejemplo:

String cad= “ Si no cierra las comillas, entonces todo el resto del

programa será parte de la cadena de caracteres;

System. out. println (“Escribe la cadena “+ cad );

Estos probablemente fueron cometidos por un programador al agregar comentarios después de que el programa se había escrito. Por ejemplo:

int x=0 ; // esta es una variable de tipo entero.

float y=0.0F ; esta es una variable de tipo flotante.

Informe de errores.Con el fin de ser útil, un mensaje de error debería

informar al usuario dónde se encuentra el error y, tanto como sea posible, qué error es. Más formalmente los mensajes de error deberían informar la fuente del error y parametrizar el mensaje. Por ejemplo:

En línea 2, la palabra reservada inicial está mal escrita.

Fuente

Parámetros

Un manejador de errores se puede escribir en una forma modular cuando contiene una pequeño número de esquemas tal como

En Fuente Tipo Valor está mal escrita.

Cuando se llama al manejador, los valores reales se sustituyen por las plantillas Fuente, Tipo y Valor.

Otra cuestión del informe de errores es si se continúa informando apariciones repetidas del mismo error. ¿ Debería emitirse un mensaje de error todo el tiempo que se utiliza una variable no declarada ? .

La detección y la recuperación de errores son temas combinados en el que la detección de un error, a menudo, proporciona una firme pista acerca de cómo resolverlo. La detección de errores encuentra el error; la recuperación de errores intenta reparar el error lo suficiente para continuar con el análisis ( y quizá hallar más errores). La recuperación es algo heurístico, en el sentido de que es muy difícil asegurar que la “corrección” no informe de errores espurios ( los que no estaban allí ), o ignore otros errores que se encontraban ahí. Por ejemplo:

Como palabras reservadas extraviadas.

Delimitadores olvidados como los signos de punto y coma.

Los nombres de variables no declaradas.

Una recuperación de error simple es saltarse al final de la construcción actual, o al principio de la siguiente.

Detección y recuperación de errores.

Los errores en la programación pueden ser de los siguientes tipos:

Léxicos, producidos al escribir mal un identificador, una palabra clave o un operador.

Sintáctico, por una expresión aritméticas o paréntesis no equilibrados.

Semánticos, como un operador aplicado a un operador incompatible.

Lógicos, puede ser una llamada infinitamente recursiva.

Un buen compilador debe hacerse siempre teniendo también en mente los errores que se puede producir; con ello se consigue:

Simplificar la estructura del compilador.

Mejorar la respuesta ante los errores.

5.5.-Generadores de analizadores léxicos

5.6.-Aplicaciones ( Casos de estudios)