Lenguajes y Automatas

ANALIZADOR LÉXICO (SCANNER)

La fase de rastreo (scanner), tiene las funciones de leer el programa fuente como un archivo de

caracteres y dividirlo en tokens. Los tokens son las palabras reservadas de un lenguaje,

secuencia de caracteres que representa una unidad de información en el programa fuente. En

cada caso un token representa un cierto patrón de caracteres que el analizador léxico

reconoce, o ajusta desde el inicio de los caracteres de entrada. De tal manera es necesario

generar un mecanismo computacional que nos permita identificar el patrón de transición entre

los caracteres de entrada, generando tokens, que posteriormente serán clasificados. Este

mecanismo es posible crearlo a partir de un tipo específico de máquina de estados llamado

autómata finito.

FUNCIÓN DEL ANALIZADOR LÉXICO

Es la primera fase de un compilador. Su principal función consiste en leer la secuencia de

caracteres del programa fuente, carácter a carácter, y elaborar como salida la secuencia de

componentes léxicos que utiliza el analizador sintáctico. El analizador sintáctico emite la orden

al analizador léxico para que agrupe los caracteres y forme unidades con significado propio

llamados componentes léxicos (tokens). Los componentes léxicos representan:

o Palabras reservadas: if, while, do, …

o Identificadores: variables, funciones, tipos definidos por el usuario, etiquetas, …

o Operadores: =, >, <, >=, <=, +, *, …

o Símbolos especiales: ;, ( ), { }, …

o Constantes numéricas. literales que representan valores enteros y flotantes.

o Constantes de carácter: literales que representan cadenas de caracteres.

El analizador léxico opera bajo petición del analizador sintáctico devolviendo un componente

léxico conforme el analizador sintáctico lo va necesitando para avanzar en la gramática. Los

componentes léxicos son los símbolos terminales de la gramática. Suele implementarse como

una subrutina del analizador sintáctico. Cuando recibe la orden “obtén el siguiente componente

léxico”, el analizador léxico lee los caracteres de entrada hasta identificar el siguiente

componente léxico.

Además el analizador léxico es responsable de:

o Manejo de apertura y cierre de archivo, lectura de caracteres y gestión de posibles

o errores de apertura.

o Eliminar comentarios, espacios en blanco, tabuladores y saltos de línea.

o Inclusión de archivos y macros.

o Contabilizar número de líneas y columnas para emitir mensajes de error.

Una de las ventajas de separar el análisis léxico y análisis sintáctico es que facilita la

transportabilidad del traductor si se decide realizar cambios posteriores, por ejemplo cambiar

las etiquetas begin-end por llaves de apertura y cierre { }.

COMPONENTES LÉXICOS, 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;

CREACIÓN DE TABLA DE TOKENS.

Tabla: conjunto de pares clave-valor, llamados elementos de la tabla. La tabla de símbolos es una componente necesaria de un compilador. Al declarar un identificador (normalmente una sola vez), éste es insertado en la tabla. Cada vez que se utilice el identificador se realizará una búsqueda en la tabla para obtener la información asociada (el valor).

Búsqueda: dada la clave de un elemento, encontrar su valor.
Inserción: Dado un par clave-valor, añadir un elemento nuevo a la tabla.
Cambio de valor: Buscar el elemento y cambiar su valor.
Borrado: Eliminar un elemento de la tabla.
Longitud de búsqueda (o tiempo de acceso)

De una clave: Li = número de comparaciones con elementos de la tabla para encontrar esa clave. Máxima: LM = número máximo de comparaciones para encontrar cualquier clave. Media (esperada): Lm = número medio de comparaciones para encontrar un valor. Si la frecuencia de todas las claves es la misma:

Lm = (S Li)/N

Si la frecuencia de todas las claves no es la misma:

Lm = S pi.Li

Grado de ocupación:

s = n/N donde n=número de elementos en la tabla y N=capacidad máxima de la tabla.

Función de búsqueda: B : K→E asocia a cada clave k un elemento B(k).

Valor asociado a una clave k: v(B(k)). Puede ser múltiple, en cuyo caso normalmente se convierte en un puntero. Si está en la tabla puede almacenarse consecutivamente o en subtablas paralelas. Tablas de símbolos (identificadores) La clave es el identificador.

El valor está formado por:

Atributos del identificador: Puntero a la posición de memoria asignada. La clave puede sustituirse por un puntero. Los identificadores pueden estar empaquetados. La longitud del identificador puede especificarse en la tabla o delante del nombre, o ser implícita.

Tablas consecutivas: Todos los elementos ocupan posiciones de memoria adyacentes. Tablas ligadas: cada elemento apunta al siguiente. Tablas doblemente ligadas: cada elemento apunta al siguiente y al anterior. Tablas no ordenadas Inserción: en el primer lugar vacío.

ERRORES LÉXICOS

El análisis léxico constituye la primera fase, aquí se lee el programa fuente de izquierda a derecha y se agrupa en componentes léxicos (tokens), que son secuencias de caracteres que tienen un significado. Además, todos los espacios en blanco, líneas en blanco, comentarios y demás información innecesaria se elimina del programa fuente. También se comprueba que los símbolos del lenguaje (palabras clave, operadores,) se han escrito correctamente.

Como la tarea que realiza el analizador léxico es un caso especial de coincidencia de patrones, se necesitan los métodos de especificación y reconocimiento de patrones, y estos métodos son principalmente las expresiones regulares y los autómatas finitos. Sin embargo, un analizador léxico también es la parte del traductor que maneja la entrada del código fuente, y puesto que esta entrada a menudo involucra un importante gasto de tiempo, el analizador léxico debe funcionar de manera tan eficiente como sea posible.

Son pocos los errores simplemente en el nivel léxico ya que tiene una visión muy restringida de un programa fuente. El analizador léxico debe devolver el componente léxico de un identificador y dejar a otra fase se ocupe de los errores.

Suponga que una situación en la cual el analizador léxico no puede continuar porque ninguno de los patrones concuerda con un prefijo de la entrada. Tal vez la estrategia de recuperación más sencilla sea recuperación “EN MODO PANICO” (este método de recuperación es donde se borra caracteres sucesivos de la entrada hasta que el analizador léxico pueda encontrar un componente léxico bien formado). ¡¡Los programas no siempre son correctos!!

EL COMPILADOR TIENE QUE:

Reportar clara y exactamente la presencia de errores
Recuperarse de cada error lo suficientemente rápido para poder detectar errores subsiguientes:

    Tratar de evitar mensajes falsos de error
    Un error que produce un token erróneo
    Errores léxicos posibles

Un token o componente léxico es una cadena de caracteres que tiene un significado coherente en cierto lenguaje de programación. Ejemplos de tokens, podrían ser palabras clave (if, while, int), identificadores, números, signos, o un operador de varios caracteres. Son los elementos más básicos sobre los cuales se desarrolla toda traducción de un programa, surgen en la primera fase, llamada análisis léxico.

GENERADORES DE ANALIZADORES LÉXICOS

Se pueden usar varias técnicas para acelerar el algoritmo y ahorrar espacio
Las etiquetas pueden guardarse mediante dispersión para producir un sistema de firmas que acelere sus búsquedas
Como las tablas de transiciones son muy escasas, se pueden guardar en una lista corta que se consulte cada vez que se necesite hacer una transición a partir de un estado

Estas listas no suelen tener más de tres o cuatro elementos, así que su búsqueda será razonablemente rápida.

PROYECTO LENGUAJES Y AUTOMATAS

SE INGRESA LA EXPRESION PARA DESPUES DAR CLIC EN CONVERTIR EN “NFA”

SI PRESIONAMOS “DO SEEP” VA MOSTRANDO EL EQUIVALENTE A LO QUE ESTAMOS GENERANDO

SI PRESIONAMOS “DO ALL” NOS MUESTRA EL AUTOMATA FINITO COMPLETO

SI PRESIONAMOS LA OPCION “EXPORT” NOS MANDA A LA INTERFAZ DE AUTOMATA

FINALMENTE PODEMOS CONVERTIR A “EXPRESION REGULAR”

AUTOMATAS FINITOS

INICIAMOS DANDO CLIC EN LA OPCION “FINITE AUTOMATON”

ENSEGUIDA CREAMOS LOS ESTADOS “Q1, Q2,Q3”

RELACIONAMOS LOS ESTADOS DE LA SIGUIENTE MANERA

COMO CONSIGUIENTE DECLARAMOS EN ESTADO INICIAL Y EL ESTADO FINAL

PARA VALIDAR NUESTRO AUTOMATA DAMOS CLIC EN “STEP WITH CLOSURE” E INGRESAMOS UNA COMBINACION PARA VERIFICAR QUE REALMENTE FUNCIONE

SI VAMOS PRESIONANDO “STEP” NOS VA MOSTRANDO EN PANTALLA DE FORMA SOMBREADA LA TRAYECTORIA SI ES QUE ASI LO CUMPLE MIENTRAS LO VA ANALIZANDO

UNA VEZ ANALIZADO TODO, SI CUMPLE CON TODO, NOS MOSTRARA EL RECUADRO DE LA ESQUINA INFERIOR IZQUIERDA EN COLOR VERDE

EJERCICIO:

NUEVAMENTE INGRESAMOS ESTADOS Y RELACIONES, ASI COMO SU ESTADO INICIAL Y FINAL

INICIAMOS A ANALIZAR SI CUMPLE CON INGRESADO

SI CUMPLE NOS MOSTRARA AL FINAL EL RECUADRO EN COLOR VERDE

CONVERSION AFND A AFD

INICIAMOS CREANDO NUESTROS ESTADOS CON SUS RELACIONES UTILIZANDO LOS SIMBOLOS NECESARIOS

UNA VEZ REALIZADO, PROCEDEMOS A CONVERTIR A UN “AFD” SELECCIONANDO EN LA PARTE SUPERIOR IZQUIERDA LA OPCION “CONVERT” Y DESPUES EN “CONVERT TO DFA”

UNA VEZ DADO CLIC, PODEMOS VER EL RESULTADO FINAL DE LA CONVERSION

PRESIONAMOS EL APARTADO DONDE DICE “COMPLETE”

NOTAMOS QUE HEMOS OBTENIDO NUESTRO “AFD”

CODIGO DE UN AUTOMATA FINITO

Código Fuente en “C” AFD con Listas

Este programa en Lenguaje de Programación C es un Autómata Finito Determinista, El AFD esta definido por la expresión regular ε∪(b + ε)(ab)∗∪ (a + ε)(ba)∗. Esta expresión no acepta las subcadenas aa y bb.

El programa puede ser de gran utilidad en las materias sobre Teoría de Autómatas. Para armar un AFD distinto, lo que tienes que cambiar son las conexiones de los nodos, que se encuentran el método crear(), que es donde se arma el AFD, y obviamente, si el AFD que quieres construir tiene mas estados, pues tendrás que declarar mas nodos y si evalúa mas símbolos pues los agregas en el switch, ten en cuenta que agregar mas símbolos implica que tendrás que declarar mas enlaces dentro de la estructura.

El programa en C fue diseñado en Dev-C++, que si no lo tienes te recomiendo que lo descargues aquí.

Código Fuente en C

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

struct lista_elementos

{

int estado;

struct lista_elementos *a;

struct lista_elementos *b;

};

typedef struct lista_elementos nodo;

void crear(nodo *q0,nodo *q1,nodo *q2,nodo *q3,

nodo *actual, nodo *anterior);

void mostrar(nodo *pt,nodo *pt2,int j,char i);

main()

{

nodo *q0,*q1,*q2,*q3,*actual,*anterior;

int j=0,i=0,tamano=0,novalido=0; char cadena[100];

actual=(nodo*)malloc(sizeof(nodo));

q0=(nodo*)malloc(sizeof(nodo));

q1=(nodo*)malloc(sizeof(nodo));

q2=(nodo*)malloc(sizeof(nodo));

q3=(nodo*)malloc(sizeof(nodo));

crear(q0,q1,q2,q3,actual,anterior);

printf("\n\n\n\t AFD Que no acepte las subcadenas aa y bb\n\n");

printf(" Ingrese Cadena: ");

gets(cadena);

tamano = strlen(cadena);

while (i < tamano && novalido==0){

j=i+1;

switch(cadena[i]){

case 'a':

if(actual->a==NULL){

anterior=q0;

actual=anterior->a;

mostrar(anterior,actual,j,cadena[i]);

}else{

anterior=actual;

actual=anterior->a;

mostrar(anterior,actual,j,cadena[i]);

}

break;

case 'b':

if(actual->b==NULL){

anterior=q0;

actual=anterior->b;

mostrar(anterior,actual,j,cadena[i]);

}else{

anterior=actual;

actual=anterior->b;

mostrar(anterior,actual,j,cadena[i]);}

break;

default:

novalido=1;

break;

}

i++;

}

if(actual->estado==1||actual->estado==4||novalido==1){

printf("\n\n\t ------------------------- ");

printf("\n\t --- Cadena Rechazada! --- \n");

printf("\t ------------------------- \n\n");

}

else{

printf("\n\n\t ------------------------ ");

printf("\n\t --- Cadena Aceptada! --- \n");

printf("\t ------------------------ \n\n");

}

getchar();

}

void crear(nodo *q0,nodo *q1,nodo *q2,nodo *q3,nodo *actual, nodo *anterior)

{

q0->a=q2;

q0->b=q1;

q1->a=q2;

q1->b=q3;

q2->a=q3;

q2->b=q1;

q3->a=q3;

q3->b=q3;

q0->estado=1;

q1->estado=2;

q2->estado=3;

q3->estado=4;

actual->a=NULL;

actual->b=NULL;

anterior->a=NULL;

anterior->b=NULL;

}

void mostrar(nodo *pt,nodo *pt2, int j,char i)

{ int fuente=0,destino=0;

fuente=pt->estado;destino=pt2->estado;

fuente=fuente-1;destino=destino-1;

printf("\n\n Movimiento: %d",j);

printf(" Para el simbolo: %c",i);

if(j==0){

printf("\n\n\t Desde el Inicio");}

else{

printf("\n\n\t Del Estado: q%d",fuente);

printf("\t A el Estado: q%d",destino);

}

Lenguajes y Automatas

jueves, 3 de agosto de 2017

PARCIAL II

ANALIZADOR LÉXICO (SCANNER)

FUNCIÓN DEL ANALIZADOR LÉXICO

CREACIÓN DE TABLA DE TOKENS.